* 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.