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

[Eli Zaretskii <eliz@gnu.org>]

> Date: Sat, 25 Mar 2023 22:39:34 +0100
> Cc: gregory@heytings.org, 62352@debbugs.gnu.org
> From: Herman, Géza <geza.herman@gmail.com>
> 
> >> I'm not necessarily suggesting a cache. Maybe it's better to actually
> >> always manage additional data structures. So, if a text property is
> >> added, it's not just set for the specific character area, but it will
> >> also modify search structures right away. So additional data structures
> >> were always in sync. Sure, it has some overhead. But if emacs does a lot
> >> of linear searches (and having a look at these functions, I see a lot of
> >> linear searches), this overhead will be quickly mitigated by the much
> >> faster searches. For example, if emacs had a list which only contained
> >> text segments with the composition property, the current 500-char area
> >> search will be much faster.
> > Emacs already handles text properties using an efficient data
> > structure, see intervals.c.  Feel free to suggest improvements to the
> > algorithms we use there.
> 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.

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