Re: line buffer as Red Black Trees instead of linear

[Alin Soare]

>
> Emacs works bad with buffers with long lines. This would work well, and all
> the others atomic operations, like random access, search, will preserve the
> current speed.

You cannot help redisplay with long lines by giving it random access
to buffer text.

This is right. Redisplay is one, and computing the result of some functions is another thing.

I did not check the flow of the calls that take place in that situation, but I am sure that it happens at the level of buffer access, Some atomic procedures of access to buffer are linear in time, instead of constant or logarithmic in the worse case.

I provided a solution in which all atomic accesses to buffer are in good time.

 

Long lines slow down redisplay because it needs to scan the entire
line to see how tall it will be on display.  For that, you must scan
the line in its entirety, since Emacs supports variable-size fonts and
images on the same line, so determining the height of a line requires
to find the largest display element (character glyph or image)
displayed on that line.

If we put at each node of a red-black tree an attribute which says how tall the block of text at that node is  --  (for example, if there are 2K characters at that block, all identical, we already computed 2K of all the line, and pass to the next node, where there may be 5K or 0.5K characters, and it is GUARANTEED that in the worse case we have log # of nodes ).

Then re-computing the glyph size will be logarithmic in the worse case, because we need to check maximum a log # of nodes, to detect all the properties of a line.

Each node must also have an attribute that says how many lines are at the left of that node, another attrib that says how many chars are at the left, and each node must also have a pointer to the next node, such that the nondeterministic finite automata that use lazy search (for example in search-forward) will take constant time on each change of state (as it is now). 

 

How can random access to buffer text help here?

I repeat : it is very long since I read the code of emacs, so I cannot remember the details of all the operations, but while I was working on the tutorial in which I present the details how I deduced the formla of red-black trees, I realized that these are the wonderful data structure to work with in emacs buffers.

I knew that emacs loops in buffer data structure, hence the slow operations in the cases that I said in my prev. message .