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

[Ihor Radchenko]

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