bug#62352: Very slow scroll-down-line with a lot of text properties

[Herman]

On 3/26/23 06:55, Eli Zaretskii wrote:
> > The problem is not there. The problem is that find_composition is only
> > interested in the composition property, yet it scans all the properties
> > linearly.
> It doesn't scan linearly.  It calls next-single-property-change, which
> traverses the interval tree we use for storing text properties.
> Please take a look at the implementation of
> next-single-property-change in textprop.c.
It finds the starting point by traversing the tree (presumably an 
O(log(number_of_properties)) operation (that's good), but then scans 
linearly. My example buffer has a different property for (almost) all 
characters, this means that this function will search the tree for ~500 
elements to conclude that there is no such property around. And it does 
this operation for every single character visible in the window, or 
something like this.

> > And it scans it for 500 characters. This file has a lot of
> > properties, this means a lot of unnecessary and duplicated work (because
> > it does this for each character displayed, or something like this). If
> > the composition property had its own list, then this problem wouldn't exist.
> If the composition property had its own data structure, Emacs would
> need to search them both when it looks for a change in _any_ property
> (something that happens quite a lot in other places), and handle
> various combinations of hits in both data structures.  That'd be a
> significant complication for a small gain.
If that's the case, then emacs could have a data structure which 
contains all the properties (like now), and one which points only to the 
composition properties. Yes, this is a complication, it will make emacs 
generally a little bit slower, but it would avoid freezes.

But maybe this is not the correct solution. I have a feeling that this 
500-character search area is not a good solution for the problem it 
tries to solve. Maybe it's a result of some optimization that was 
relevant a long time ago, but now it isn't, and it is actually a 
de-optimization if the buffer contains a lot of properties.

A lot of people wouldn't care if emacs used a little more CPU power in 
general (as an example, during general editing, it would use 30% CPU 
instead of 20%), if this means that there is no stuttering. That's why 
people (me included) set the garbage collector threshold to a high 
value, because of the introduced micro-stuttering by the GC. But I'm not 
even sure that having more specialized search structures would actually 
slow down emacs in general. Maybe the net result would be that not only 
emacs won't freeze, but it would also become generally faster.