Subject: Re: data hygiene [Re: Why is Scheme not a Lisp?] From: Erik Naggum <erik@naggum.net> Date: Thu, 21 Mar 2002 07:43:48 GMT Newsgroups: comp.lang.lisp Message-ID: <3225685440358243@naggum.net> * Carl Shapiro | There is a small amount of load parallelism in list traversal that can be | exploited when using an alist. I do not think there is, at least if this means that the similar facility _cannot_ be exploited exactly equally well when using plist. An exactly equal amount of load parallelism is available for plists, namely to prefetch one cons cell forward. However, both alists and plists need to consult one _more_ cons cell per iteration. The alist finds it pointed to by the car, plist by the cdr. As I have tried to explain already, there can be no difference between alists and plists in this regard. There are many other interesting differences between alists and plists. First of all, assoc is not a cheap function. It has :key and :test arguments that, if the call is not inlined, cause a rather horrible degradation of performance. Second, assoc uses eql by default, whereas getf uses eq. This means that every mismatch must check for the type, and that might involve a function call. (For this reason, I always use :test #'eq when I think eql is the wrong choice (which is most of the time), and this also does wonders by interpreting the :test argument in a compiler-macro to call the proper internal function.) Third, and a consequence of the two preceding, alists can represent keys that plists cannot have, so they clearly have different uses. Where they do overlap, plists are far superior, however. Let me explain why in some detail, and start with a _severely_ simplified definition of assoc, almost a caricature, and I renamed them alist-get and plist-get: (defun alist-get (alist key) (do ((alist alist (cdr alist)) (cons (car alist) (car alist))) ((or (not alist) (and cons (eq key (car cons)))) (cdr cons)))) (defun plist-get (plist key) (do ((plist plist (cddr plist))) ((or (not plist) (eq (car plist) key)) (cadr plist)))) I wanted to get a really good grip on what these were doing, so I macroexpanded them and tinkered a little with the expansion: (defun alist-get-expand (alist key) (let (cons) (tagbody loop (setq cons (car alist)) (cond ((eq alist nil) (go end)) ((eq cons nil)) ((eq key (car cons)) (go end))) (setq alist (cdr alist)) (go loop) end) (cdr cons))) (defun plist-get-expand (plist key) (tagbody loop (cond ((eq plist nil) (go end)) ((eq key (car plist)) (go end))) (setq plist (cddr plist)) (go loop) end)) This is assembly in Common Lisp, but so much more readable than C. (For that reason, I have used (eq x nil) instead of (not x).) These also produce the smallest code I can get squeezed out for these functions in all CL implementations I have access to, and of those, Allegro CL has produced by _far_ the tigher code. (I am _amazed_, Duane! But if you had let ecx be used for temporary storage when it was not going to be used for argcount, you would have saved two extraneous memory accesses per iteration, and one, maybe two, cost-free register moves. Although there will always be a level 1 cache line for this memory, there is still a dependency on this access that could be eliminated.) Now, considering these differences in the implementation, there is no doubt that both functions need to cdr down a list and can prefetch that cdr cell access. There is no way to prefetch the car of the cell before it is actually needed, but the above function has been carefully written to allow prefetching the caar access. However, the savings created by this change is easily consumed by the extra test for nil elements. The distance between the first possible time the prefetch can be executed and the actual reference is, however, only two compares and two branches not taken (if carefully coded) | Before examining the car of some element, one could prefetch the cdr. But this is _exactly_ the same for alists and plists. The plist has to do two cdrs in succession and the alist has to two cars in succession. | This may increase the likelihood of the next list element being in cache | by the time you are ready for it. But not the caar of the alist any more than the cddr of the plist. | Joe Marshall's paper describing the architecture of the LMI K-Machine | mentions that its compiler would emit such instructions to prefetch list | elements when compiling mapping primitives. Sure, it helps tremendously if you are _not_ going to dive into another cons cell. If you are going to dive into another cons cell, it matters not whether it is in the car or in the cdr of the cell you are looking at. I mean, if you scan a list one element at time and do something between each memory reference, find, prefetch the cdr, but just because you can scan the list marginally more efficiently in one direction does not mean that the other direction is irrelevant. | With a plist one has to cdr past all elements so this opportunity would | be lost. You seem to think that getting the key of an association is _free_. This is so puzzling it is truly beyond my intellectual capacity to figure out how you can arrive at this conclusion, which looks completely bizarre, as if you have completely ignored the fact that you are _not_ comparing the car of each cons you visit, you visit the car of the car of each cons you visit. The fact that an alist and a plist requires equally many cons cells _should_ have been such an important clue. After having spent several hours on this, including returning to the entertaining Intel architecture manuals (because they show such an inner beauty despite the incredibly boneheaded instruction set), I conclude that any possible savings in prefetching that cdr cell will now take 300 million years to amortize the cost of the research. (This message has been composed on and off over several days, so it still needs a lot of editing, which I am not inclined to give it.) /// -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.