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

[Ihor Radchenko <yantar92@gmail.com>]

Mattias Engdegård <mattiase@acm.org> writes:

>> we have to insert a new element and shift the :begin keys of all the
>> elements below:
>> 
>> (:begin 1 "headline 1" ...)
>> (:begin 13 "new" ...)
>> (:begin 13+7 "subheadline" ...)
>> (:begin 28+7 "headline 2" ...)
>
> Forgive my ignorance, but wouldn't this call for some sort of interval tree where the children's offset are relative to their parents? Then shifting keys in an interval only requires modifying a few upper nodes.

Yes. However, using an interval tree will just trade O(N) shifting upon
buffer modification to O(logN) upon accessing :begin keys. We have a lot
of places in code relying on quick access to :begin and using offsets in
interval will often mean O(NlogN) for accessing :begin instead of O(N) +
O(N) for shift + access. We might do tricks to optimise O(logN) into O(1)
on sequential element access, but it will restrict the API.

>> B-trees may be an option, but I do not
>> see how they would be advantageous compared to AVL trees. We do
>> everything in memory.
>
> Locality matters in memory too! Well-implemented B-trees are usually competitive with binary trees even in RAM. I have no idea how easy that would be to pull off in Elisp, though.

That makes sense. However, AFAIU 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. When we use arrays of lists in Elisp, I doubt that they
are going to be stored in continuous memory segments.

> (I've rarely had good experience with splay trees but I suppose they can be useful in the right circumstances.)

Curiously, it is a very common opinion in internet forums. People do say
that splay trees can be good, but never have real world examples. I
guess, I can only try and see how it goes.

>> This is really counter-intuitive. I am wondering how much can be the
>> difference in practice. At least by orders of magnitude.
>
> Did you expect a difference in orders of magnitude? Implementation choices do not often come that clear-cut.
>
> C primitives can often be faster than ones implemented in Lisp even if using a less clever algorithm (for example, try comparing `memq` against a set implemented as a balanced binary tree lookup in Lisp).

I see.

> We also have to contend with a rather antique garbage collector.

I really hope that the recent WIP branch implementing a new asynchronous
garbage collector is going to be ready soon.

Best,
Ihor