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

[Eli Zaretskii <eliz@gnu.org>]

> Date: Sat, 25 Mar 2023 18:38:19 +0100
> Cc: gregory@heytings.org, 62352@debbugs.gnu.org
> From: Herman, Géza <geza.herman@gmail.com>
> 
> > IOW, it is not as simple as you seem to think.
> I didn't meant to imply that it is easy. It is certainly not. But, tbh, 
> while emacs is fluid most of the time, it can be very stuttery 
> sometimes. In my experience, this is usually caused by some lisp code. 
> But when it isn't, it is usually caused by some code in this area. When 
> I profile emacs, these functions (next_property_change and similar) are 
> usually on the top of the list. So it would make sense to optimize 
> around this area. Not just because of this issue, but in general.
> 
> 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.