Re: Mitigating the long-lines penalty in vundo

[JD Smith <jdtsmith@gmail.com>]

> On Dec 17, 2023, at 1:07 PM, Eli Zaretskii <eliz@gnu.org> wrote:
> 
> I do see 'display' properties being used:
> 
>  (defun vundo--highlight-node (node)
>       <snip>
> (overlay-put vundo--highlight-overlay
>   'display (vundo--translate "●”)) ...

That’s just a single display property on the one character wide overlay used to indicate the current node.  The test showed faces and unicode are what lead to the significant current-column slowdown (though I wouldn’t be surprised if ‘display would make it yet worse!).

> Lisp programs are not supposed to need frequent column calculations,
> certainly not several times on the same line.

Maybe then it’s worth a word of warning in the current-column docs mentioning this in the context of faces, unicode, and long-line performance?

>> * current-column is quite slow counting unicode characters: about 21x slower than the ascii
>> equivalents.  Perhaps this is because unicode chars can have non-standard widths, so emacs
>> needs to do some additional checks?
> 
> No.  I can understand why non-ASCII characters are somewhat slower,
> since each one of them is several bytes, not just one, and we convert
> the multibyte representation into a codepoint on the fly.  But 21-fold
> slowdown sounds excessive.

Results may vary by system/font I suppose; perhaps others could run the simple test in my last message (no non-default packages required) and report back what slowdown factor they get.

>> * But this isn’t the full story, because current-column is also (separately) quite slow counting plain
>> characters with attached faces: 33x slower than the fast case. This one seems less intuitive to me.
>> Can faces also (in principle) alter the character width (like italic for example)?
> 
> When buffer text has faces (or any other text properties, really)
> current-column uses a slower algorithm, because the faster one will
> yield incorrect results.

I see.  I had noticed the slowdown does not depend on whether faces alternate or just a single face is used, so this makes sense.

>> * Combining these two (unicode chars with alternating faces) is the worst case — 43x slower than
>> the fast case of unadorned plain chars.  This was vundo’s case.
> 
> Then vundo is better redesigned to avoid such massive reliance on
> current-column.

Yes indeed, and it has been already!  The fix was quite trivial [1].  I was speaking more generally to current-column performance.  You could imagine algorithms that legitimately do need to keep a dynamically updating measure of the column.

> There's one more factor to consider here: current-column always starts
> from the beginning of the line.  If vundo needs to call current-column
> many times on the same line, it loses because it each time starts from
> BOL, in effect throwing away the results of the previous calculation.
> This wastes CPU cycles.  It might be better to use sum char-width
> values of individual characters instead.

Definitely; it’s clear how repetitive/wasteful this is.  I wonder, similar to line-numbers, could we cache current-column at various points along a line and apply a delta?  I.e. for computing line numbers differentially we have

(count-lines start end) 

which linum and others use to good effect.  Is there a similar

(count-columns start end)?  

This could be useful for algorithms that truly need frequent, up-to-date column info (not vundo, luckily).

Thanks for your help and analysis.

[1] https://github.com/casouri/vundo/pull/85