Path: utzoo!attcan!uunet!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: Arrays in Prolog Message-ID: <3840@goanna.cs.rmit.oz.au> Date: 26 Sep 90 09:43:06 GMT References: <90239.175243SCHMIED@DB0TUI11.BITNET> <1990Sep11.150245.26833@sics.se> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 45 Fernando Pereira actually said something extremely encouraging to me: he said that there were algorithms where something "one or two orders of magnitude faster" than N+K trees was needed (hence arrays). Now, my claim that N+K trees are a practical alternative to arrays is to be understood as a claim that a particular *data structure* (which can be inspected and manipulated as a plain Prolog data structure if need be) is a practical alternative. That's all. The claim is that a data structure is ok, not that it shouldn't be built in. Here's what I have in mind. 3+4 trees represented as perfectly ordinary Prolog terms can nevertheless be manipulated by built-in predicates that are implemented in hand-optimised machine code. The observable behaviour of such built-in predicates would be exactly the same as the observable behaviour of appropriate Prolog code, but it could be a lot faster. In fact, the attainable speedup is in exactly the "one or two orders of magnitude faster" ballpark that Fernando says we need. I haven't got all the figures I want yet. But on an Encore Multimax (NS32532), plain ordinary C code (not hand-optimised assembler) gave me the following average times to access any element of an N-element array represented as an 3+4 tree: N = 10 t = 8 usec 100 12 usec 1,000 16 usec 10,000 20 usec 100,000 24 usec 1,000,000 29 usec That's about a 4usec increase for every 10-fold expansion of the array. The C code behaved exactly like get_label/3 on p143 of the book, and this time does include loops to dereference, type checks, checks that the nodes of the tree have the right functor, and preparation to build missing parts of the tree and so on. I repeat, this is plain ordinary C code. Hand-optimised assembly code should be able to do somewhat better (at a rough guess, 3 usec steps rather than 4 usec, so that 1,000-element "arrays" might cost 13-usec per element access). There are more measurements to be made, but it looks as though 3+4 trees _are_ a practical alternative to arrays _if_ they are implemented well. -- Fixed in the next release.