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.