Re: [Maxima-discuss] list element access time, was: merge sort

[Henry B. <hb...@pi...>]

I should note that CDR-ing down a list, all of whose nodes are
already in a cache, can be hundreds of times faster than when
those nodes are in main memory.

However, even one non-cached node in the list will kill the speed.

Ideally, the Lisp allocator and Lisp GC should cooperate with the
memory caching system to make sure that none of the CDR's in a
list will ever collide in the cache.

If the CPU chip companies would be more forthcoming about exactly
how the cache lines are allocated, then such cooperation could be
implemented.

With today's long cache lines (256 bytes?), and the ability to
write back only those portions of a line that has changed, there
should be plenty of degrees of freedom to enable the allocator
and GC to assure non-collision.

At 10:06 AM 7/10/2016, Gunter Königsmann wrote:
>Weird:
>
>I was always convinced that the access times for random list elements
>were a unavoidable characteristic of lists.  When Robert told me that
>this isn't completely true I instantly thought of a lisp caching the
>address and index of the last element of a double-linked list that was
>referenced to by a "random access" operator.
>
>Now that I have learned that a second scheme to increase efficiency of
>this use-case exists I wonder if there might be more (and maybe even
>better) "the matrix"-like instances of cases where (in respect to
>access-times) "some rules can be bent".  It is also interesting if they
>are currently in use.  But I would claim the original problem to be solved:
>I felt the need for documenting the fact that some actions are slow for
>lists and instead of complaining wrote the respective chapter.  If it
>grew too long/too technical or if it is lacking important facts I beg to
>change it accordingly.  ...and thanks to Robert's remark the manual now
>is prepared for a lisp that bends the rules a little so even if the
>thing I documented one day will be implementation-specific again we are
>prepared for it => we are the proud owners of future-proof documentation ;-)
>Also I've learned something new today - which I am not too unhappy about.
>
>Thanks a lot for this,
>and kind regards,
>
>  Gunter.