Re: Mitigating the long-lines penalty in vundo

[Eli Zaretskii <eliz@gnu.org>]

> From: JD Smith <jdtsmith@gmail.com>
> Date: Sun, 17 Dec 2023 12:49:27 -0500
> Cc: emacs-devel@gnu.org,
>  casouri@gmail.com
> 
> That said, with long lines (>10-20K columns, say) visible, the problem remains that overall Emacs is
> mildly but noticeably less responsive, in the mini-buffer, in other buffers, etc., until the vundo buffer is
> hidden.  Perhaps that’s just the minimum penalty paid for such long lines.

Long lines with faces and overlays, I should say.

>  The current-column docs do say:
> 
>  In a buffer with very long lines, the value will be an approximation,
>  because calculating the exact number is very expensive.
> 
>  The "very long lines" case happens when the line's length exceeds the
>  long-line-threshold, which in your case it most probably doesn't
>  (unless you lower long-line-threshold considerably).  So this part of
>  the doc string is not relevant to your problem.
> 
> I was only referring to the “very expensive” part. 

The "very expensive" part is also only when lines are around
long-line-threshold.  Again, not your case.

>  Yes. The problem is that vundo.el uses 'display' properties _a_lot_,
>  and those slow down current-column, because each time it sees a
>  'display' property whose value is a string, it needs to extract the
>  property value and calculate the width of that string, to account for
>  its width on display.
> 
> That would have indeed been a good explanation for the additional slowness, but in fact vundo does
> not use 'display properties:

I do see 'display' properties being used:

  (defun vundo--highlight-node (node)
    "Highlight NODE as current node."
    (unless vundo--highlight-overlay
      (setq vundo--highlight-overlay
	    (make-overlay (1- (vundo-m-point node)) (vundo-m-point node)))
      (overlay-put vundo--highlight-overlay
		   'display (vundo--translate "●"))
      (overlay-put vundo--highlight-overlay
		   'face 'vundo-highlight)
      ;; Make current node’s highlight override last saved node’s
      ;; highlight, should they collide.
      (overlay-put vundo--highlight-overlay 'priority 2))
    (move-overlay vundo--highlight-overlay
		  (1- (vundo-m-point node))
		  (vundo-m-point node)))

> Indeed this was a vundo problem in that there was no need to call current-column over and over for
> each node.  But the basic slowness of current-column remains, so unless there are low-hanging
> improvements to be made there, algorithms that need frequent column calculations would need to try
> other approaches.

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

> * Current column is reasonably fast counting long lines of plain text — 175ms total to compute each
>  column at 6000 nodes spread over 18K columns.
> * 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.

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

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

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.