Subject: bug#52753: 29.0.50; Printing long list-like structures fails

From: Mattias Engdegård <[email-masked]>
Date: Sun, 30 Jan 2022 11:16:24 +0100

30 jan. 2022 kl. 10.16 skrev Ihor Radchenko <[email-masked]>:

> the speedup will only be relevant when
> explicitly allocated C arrays are used to store B-tree segments: all the
> tree data must be physically located within continuous segment of RAM
> address space.

Lisp vectors are contiguous in memory, and your keys are small integers and thus unboxed.

> People do say
> that splay trees can be good, but never have real world examples.

The trouble with splay trees seems to be that they require a very skewed access distribution to be worthwhile -- every read of something that isn't the latest accessed element becomes a tree modification. But that implies that the access pattern exhibits spatial and/or temporal locality, which makes caching an attractive alternative (explicit or those in your computer).