Put another way: you can arrange the loads in the alist search
so that there's a longer distance between the load and when
the data is actually used, which might reduce pipeline stalls.

Beyond that, you could apply compression to the pages containing
cons cells.  This could be done either by the virtual memory
system, or by dedicated hardware between the main memory the
the largest cache level.  IBM has a memory controller product that
does the latter (although it's not optimized for Lisp as far
as I know.)

My own perceptions I think come mostly from 15+ years online and talking
largely to people who in practice vote for what they affectionately call
the "Stupid Party", but would jump to a realistic alternative in a
second.

  Are you kidding or something?

| The longest sequence of dependent loads in the alist search has length
| N+1, vs. 2N-1 for the plist.  This is assuming you have a machine that
| can have multiple loads 'in the air' at once.

  How the hell is caar+cdr any different from car+cddr?

  How do you normally set up alists and plists?  Even after a copy-tree (or
  GC) that copies cons celle so they are allocated in the order they are
  visited, the distances are _exactly_ the same.  Just work it out.

| Put another way: you can arrange the loads in the alist search so that
| there's a longer distance between the load and when the data is actually
| used, which might reduce pipeline stalls.

  Please show me how this is done.  I think you are aggressively clueless
  by now, but I am always open to refinement and even contradiction if you
  just do something smarter.

Regards,
--
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

With a plist one has to cdr past all elements so this opportunity
would be lost.

I still don't think it's a good enough reason to prefer one data structure
of another.  The whole reason we use Lisp and not C is that we value the
optimization of design time over this degree of microoptimization of
execution time.

Not that you shouldn't mention this kind of trivia, because it's quite fun
to know.  And it may even be useful in some discussions with people who are
obsessed with this kind of optimization.

But I, for one, will still be using mostly plists even though I acknowledge
the possibility in some implementations that I'll lose the occasional
prefetch assist.

Btw, in the MOO programming language, I created a concept called the
"i-list" which I found was massively more efficient there because of
idiosyncracies of the MOO byte-code interpreter.  The win wouldn't be
as big in CL, but might have some benefits. The structure looks like:

 ( sequence-of-keys . vector-of-values )

More usefully, these are generally understood to mean that a "left-wing"
party tends toward socialism and a "right-wing" party toward fascism,
although generally not very far along.[1] :)

In practice, the major "left-wing" and "right-wing" parties in Australia
are both very conservative parties, focusing mostly on improving
business conditions based on the theory that a better economy means a
better life for everyone in the country, no matter what you have to
sacrifice to improve the economy.[2]

The distinguishing factor between the two is that the "left-wing" Labour
party focus on improving small business while the "right-wing"
Liberal[3] are focused on improving large, typically multinational,
business.

As far as I can tell, American politics has a greater degree of
difference between the two parties[4] but the fundamental structure is the
same -- two parties, differing mostly on what size of business to
support.

        Daniel

(Was that sufficiently inflammatory? I probably should have stuck to my
guns and not answered your post. Ah, well.)

Footnotes:
[1]  This is based on a biased sample of the people I know, or at least
     the perception that it is "generally understood" is.

[2]  This includes expendable things such as education, public health
     care, support for the unemployed and the poor and the like.

[3]  Yes, I find this name highly amusing myself, since they are the
     more conservative of the two, though not by much.

[4]  There seems to be a stronger support for social support in the, er,
     democrats. (or is it Republicans? The one that isn't in power,
     anyway.)

In the United States, all elections for members of Congress are
"winner-take-all", that is, there is an election for a single seat,
and whoever captures the most votes, by a plurality, wins that seat.
A similar rule prevails in British elections for the House of Commons,
the Canadian House of Commons, and many others.

This is to be contrasted with non-winner-take-all systems, in which
there may be several seats open for election at once, and some system
of proportional representation or transferrable vote is used.  For
example, the Board of Supervisors in San Francisco, CA and the City
Council of Cambridge, MA, both have at large members elected in such a
fashion.

In a winner-take-all system, there are very strong pressures towards a
two-party system; it's nearly automatic.  Canada is a curious
exception at present, with two prominent opposition parties, both of
which are strongly regional,

  What is all this?  Clearly both parties have very much in common.  They
  are both political parties, or members of the American political party
  family.  People from both parties should just come together and discuss
  their common ground and be friends, not fight against each other.  Their
  internal differences are unimportant compared the commonalities.  For
  instance, they are both American.  That must count for something.  Both
  parties have symbols, and both parties have some concerns for some group
  of the population that are largely symbolic.  Seen from afar, such as the
  individual voter, there is no material difference between the two, and
  people who wish to learn about the politics of one party may learn from
  the literature of the other and from congretating with people of the
  other party.  After all, the sin taxes both parties favor are the same,
  and they both display the same antics.  So, why don't you Americans adopt
  a one-party system like several European, African, and Latin American
  countries have had so much success with?  Then, peace will break out and
  real and toy Lisps shall live happily ever after.

  Yeah, the damn liberal media are _everywhere_!

(defun fast-assoc-eq (key lst)
  (and
   (consp lst)
   (if key
       (let (pair pair2 rest k1 k2)
         ;; The loop has been unrolled once.
         ;; Note that there is at least one load between a
         ;; use and the load on which it depends (except for
         ;;  the line marked *)
         (loop
           (setq rest (cdr lst))
           (setq pair (car lst))
           (unless (consp rest)
              (return (and (eq (car pair) key) pair)))  ; *
           (setq pair2 (car rest))
           (setq k1   (car pair))
           (setq k2   (car pair2))
           (setq lst  (cdr rest))
           (when (eq k1 key) (return pair))
           (when (eq k2 key) (return pair2))
           (unless (consp lst) (return nil))))
     ;; special case for null key -- same as above but check that
     ;; pair, pair2 are not null.
     (fast-assoc-eq-nil lst))))

The distance between some of the loads and uses could be increased
further by additional unrolling/software pipelining.

    So, can a Republican be a Democrat?  I don't know for sure, but
  certain elements of the Republican party have recently engaged in such
  speculation to a degree that is reminiscent of the anti-Trotskyite
  Communist Party in 1934.

    As an independent, I find that my time is micro-optimized by
  avoiding political discussion with people who speak a different
  "dialect" from myself - which means that I rarely speak politics with
  anyone.  I tend to stay off of both political party lists (plists) and
  association lists (alists).  

    The only exception is the stream of correspondence between my
  representatives and myself.  Sometimes it seems like the direction is
  :output only from one or the other.  The system does (provide
  two-way-communication) but doesn't (require ) it.

    Of course, as a native Texan (currently indirected through
  Pennsylvania), we often SCHEME for a minimalist government, where
  features are added only by unanimous consent.  This means that we tend
  to decry MACRO-economic issues as being unhygienic.  We sometimes have
  trouble getting consensus on what the actual standard definition of
  government is, with some claiming that the Articles of Confederation
  are the last legitimate specification, Constitutional Conventions
  not-withstanding.

    But, it really does seem to come back down to an issue of
  packaging.  After all, most Texans prefer it to seem as if we had the
  whole fully-featured universe to ourselves, even if that means we have
  to import things from "out there."  The only thing we tend to
  studiously avoid is hash....

    I cdr listed much much more, but I fear that this is no longer pun
  for (rest comp.lang.lisp).

This is the third reference (I think) to Trotskyite purges in almost as
many days on comp.lang.lisp (with *no* counterbalancing Macarthyism crys
or "Let a thousand flowers bloom (so we can crush the
blossems)" quotes). By the rule of three, I think this establishes a
corollary of Godwin's law permitting me to hunt down all you
counter-revolutionary, godless, toy-lisp wielding symbolic processors!

Hmm. Perhaps this is a proof that the participants on comp.lang.lisp *are*
bots, and have gotten caught in a wierd race condition....

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

  But the _exact_ same thing can be done for the property list!

  I do not think you have worked this out for property lists to see how
  similar the effect is.

  *sigh*  

In the alist, you can fit two loads between each of the main
cdr loads (loading a car, and a caar; note that with software
pipelining these will be loads from farther back in the alist.)

In the plist, there is only one 'off the critical path' car
per *two* cdrs.  There simply isn't enough extra work to fit
into the dead space after each load on the critical path.

In contrast, there *is* a dependency between the cdr and
the cddr for the plist, and this dependency cannot be
gotten rid of.

  Nonsense.  Have you worked this out for plists?  Yes or no?

| In the plist, there is only one 'off the critical path' car
| per *two* cdrs.  There simply isn't enough extra work to fit
| into the dead space after each load on the critical path.

  Nonsense.