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

[Mattias Engdegård]

23 jan. 2022 kl. 13.44 skrev Ihor Radchenko <yantar92@gmail.com>:

> I tried to understand the printer code, but it appears to be too complex
> for me. Maybe I am just not familiar enough with the C part of Emacs.

It's complex partly because of its age, but also because we ask a lot it. While 
it would be nice to extend it and the reader to handle arbitrarily complex 
structures, I'm not sure your case is a motivation strong enough since the 
complexity of your data structure is more accidental than essential.

> While I understand how the illustrated example is difficult for the
> reader, note that recursion is _not_ in the car slot. Each list element
> is a structure like (key . forward-vector) with key being the stored
> value and forward-vector storing forward references to the next
> elements. Conceptually, ordinary list is just a degenerate case of skip
> list with forward-vector storing a single forward-reference to the next
> element in the list.

Sorry, my mistake -- the recursion is through the stacked conses and vectors in 
the cdr position, which changes absolutely nothing at all. Your data structure 
is not a list in the Lisp sense, which is the only recursion that the reader 
and printer can handle without consuming stack.

> Since your last message, I have dived into the more recent literature on
> data structures.

That's the spirit!

> It looks like skip lists are not that bad - similar to
> even older AVL-tree they got updated with finger search facilities and
> auto-adjustments to non-random data [1,2]. However, a systematic
> comparison between AVL-trees, skip lists, and splay trees reveals that
> insertion into skip lists perform up to 2x worse compared to AVL-trees,
> especially for random insertion [3]. Ref. [3] generally agrees with my
> measurements. On the other hand, Ref. [3] showed that average lookup
> time should be 2x faster in skip lists - very different from my
> implementation. I may be doing something wrong.

Emacs Lisp as an implementation environment comes with its own set of 
constraints, data structures and primitives that strongly affect what 
algorithms will be practical and is very different from C, say.

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

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

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

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

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