avy-goto-line is slow in visual-line-mode

[sebmiq]

Copy the following paragraph 15 times in a buffer

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Call visual-line-mode and split-window-right.

Now try avy-goto-line. There is a significant delay before the line decorations appear.

(Is there any way to get a precise number here ?)

[abo-abo]

Here's how I tested it:

(progn
  (elp-instrument-function 'line-move-visual)
  (elp-instrument-package "avy")
  (setq unread-command-events (listify-key-sequence "jj"))
  (avy-goto-line)
  (elp-results))

I evaluate this code in *scratch*, with the second buffer holding the lorem ipsum text.

Here's the result:

avy-goto-line                  1           0.289760433   0.289760433
avy--line                      1           0.289749301   0.289749301
avy--line-cands                1           0.151209476   0.151209476
line-move-visual               54          0.1495741659  0.0027698919
avy-process                    1           0.138535343   0.138535343
avy--process-1                 1           0.138408367   0.138408367
avy-read                       1           0.138328969   0.138328969
avy--overlay-pre               70          0.1380280499  0.0019718292
avy--overlay-at-full           63          0.1376733359  0.0021852910
avy--overlay                   70          0.0008244939  1.177...e-05
avy--old-str                   70          0.0002514059  3.591...e-06
avy--update-offset-and-str     63          0.000166347   2.640...e-06
avy-traverse                   9           0.000161274   1.791...e-05
avy-pre-action-default         1           0.000116404   0.000116404
avy-push-mark                  1           8.1398e-05    8.1398e-05
avy-tree                       1           6.6755e-05    6.6755e-05
avy--key-to-char               131         3.766...e-05  2.875...e-07
avy-candidate-beg              70          3.053...e-05  4.361...e-07
avy-subdiv                     7           1.343e-05     1.918...e-06
avy--remove-leading-chars      3           9.495...e-06  3.165...e-06
avy-mouse-event-window         2           4.472e-06     2.236e-06
avy-window-list                2           3.483e-06     1.7415e-06
avy-candidate-wnd              7           1.972e-06     2.817...e-07
avy-action-goto                1           1.261e-06     1.261e-06
avy--done                      1           1.244e-06     1.244e-06
avy--style-fn                  1           1.08e-06      1.08e-06
avy--make-backgrounds          1           5.19e-07      5.19e-07

As you can see, the total time it took was 0.28 seconds. Out of that, 54 calls to line-move-visual consumed 0.15 seconds.

Now compare with the results for the same buffer, but with 14 newlines inserted:

avy-goto-line                  1           0.001648925   0.001648925
avy--line                      1           0.001638178   0.001638178
avy--line-cands                1           0.000999542   0.000999542
avy-process                    1           0.000635356   0.000635356
avy--process-1                 1           0.000541503   0.000541503
avy-read                       1           0.000503282   0.000503282
avy--overlay-pre               22          0.0003597499  1.635...e-05
avy--overlay                   22          0.0001956049  8.891...e-06
avy-pre-action-default         1           8.6021e-05    8.6021e-05
avy-push-mark                  1           5.7304e-05    5.7304e-05
avy--old-str                   22          5.4401e-05    2.472...e-06
avy-traverse                   3           3.3346e-05    1.111...e-05
avy-tree                       1           2.9425e-05    2.9425e-05
avy--key-to-char               38          1.0913e-05    2.871...e-07
avy-candidate-beg              22          8.419e-06     3.826...e-07
avy-subdiv                     2           7.351e-06     3.6755e-06
avy-candidate-wnd              22          6.237e-06     2.834...e-07
avy--remove-leading-chars      2           4.377...e-06  2.188...e-06
avy-mouse-event-window         1           2.429e-06     2.429e-06
avy-window-list                2           2.361e-06     1.1805e-06
avy-action-goto                1           1.463e-06     1.463e-06
avy--done                      1           1.039e-06     1.039e-06
avy--style-fn                  1           7.69e-07      7.69e-07
avy--make-backgrounds          1           4.49e-07      4.49e-07

All processing took 0.0016 seconds. So I can conclude that the 0.138 seconds that avy-process took in the first case is due to inserting overlays when the visual-line-mode is on.

More measurements or PRs, or ideas for improvement are welcome. But I think it boils down to: Emacs is slow with long lines, and visual-line-mode is especially slow. So it's best to avoid long lines until they're fixed in the Emacs core.

[sebmiq]

Thank you for the detailed analysis.

Now compare with the results for the same buffer, but with 14 newlines inserted:

I still get a slow behavior (elp report is identical to your slow one) if I insert newlines between the paragraphs, even with a mostly empty init file. Even if I break every line in each paragraph, or add an empty line between each line, line-move-visual still takes 0.1s.

Can you not reproduce ?

So it's best to avoid long lines until they're fixed in the Emacs core.

Are you by any chance aware of any work or discussion pertaining to this ? I can only find references to issues with very long lines.

[abo-abo]

I still get a slow behavior (elp report is identical to your slow one) if I insert newlines between the paragraphs

I meant insert newlines and turn off visual-line-mode.

[abo-abo]

Are you by any chance aware of any work or discussion pertaining to this ?

People are aware of the issue, it seems. But we will likely need a big rewrite of the C structures that store the buffers.

[sstepashka]

I am experiencing the same issue now.

Once I use Emacs w/ native compilation enabled, it gets much faster. Which likely indicates the problem on Elisp side, not C level representation of the buffer?

[sstepashka]

And, I wander why would ace-jump-line-mode always be snappy regardless of visual-line-mode?

[sstepashka]

Seems like, ACE just ignores visual like and searches for beginning of string:

(ace-jump-do "^")

[sstepashka]

I am using this as a workaround for now:

(defun init--avy-goto-line (&optional arg)
  (interactive "P")
  (let ((visual-line-mode nil))
    (avy-goto-line arg)))