Limit the size of the displayed history to speed up Vundo #68
Comments
|
Should be fine, someone did some experiments and it seems vundo works fine with larger undo history: #67. |
|
I've read that. In my case I have a 7.6 MB file of notes which I edit very often and the Vundo buffer takes about 25 s to open after doing Could it be Emacs struggling with very long lines that causes the slowdown? |
|
Ah, ok. If the slowdown is at the start when vundo generates the tree, then I think vundo is to blame. The size of the file doesn't make vundo faster or slower, I wonder what's the size of the undo history? I assume you use persistent undo history? Could you check out the file used to store undo history and report its size? Also, could you profile the undo tree generation for me: type |
Yes, sorry, I forgot to mention it.
It's 110 kB zst compressed.
Old profiler report |
|
Here is a profiler report from an instance with a cleaner config. 22121 98% - command-execute
20666 92% - funcall-interactively
20660 92% - execute-extended-command
20646 92% - command-execute
20626 92% - funcall-interactively
20617 92% - vundo
20031 89% - vundo-1
20013 89% - vundo--refresh-buffer
49 0% - vundo--draw-tree
34 0% - vundo--translate
31 0% - seq-mapcat
23 0% - seq-map
18 0% - apply
11 0% - #<compiled 0x1856cdad2b64f734>
5 0% - mapcar
2 0% #<subr F616e6f6e796d6f75732d6c616d626461_anonymous_lambda_11>
6 0% - apply
2 0% - seq-concatenate
2 0% apply
5 0% - vundo--build-tree
4 0% - vundo--sort-mod
3 0% - seq-sort
1 0% - apply
1 0% #<compiled -0x59ce19e634939fb>
18 0% - vundo-mode
1 0% face-remap-add-relative
1 0% - run-mode-hooks
1 0% - run-hooks
1 0% - global-font-lock-mode-enable-in-buffers
1 0% - turn-on-font-lock-if-desired
1 0% - turn-on-font-lock
1 0% font-lock-mode
3 0% - fit-window-to-buffer
3 0% - jit-lock-function
3 0% jit-lock-fontify-now
20 0% byte-code
1455 6% - byte-code
1455 6% - read-extended-command
1363 6% - completing-read-default
18 0% - command-execute
18 0% - funcall-interactively
17 0% - minibuffer-complete
17 0% - completion-in-region
17 0% - completion--in-region
17 0% - #<compiled -0x731a712fc48e962>
17 0% - apply
17 0% - #<compiled -0x17bc5b2160671e30>
17 0% - completion--in-region-1
17 0% - completion--do-completion
17 0% - completion-try-completion
17 0% - completion--nth-completion
17 0% - completion--some
17 0% - #<compiled 0xaf0040bd50f5b1c>
17 0% - completion-basic-try-completion
17 0% - #<subr F616e6f6e796d6f75732d6c616d626461_anonymous_lambda_49>
17 0% complete-with-action
1 0% - self-insert-command
1 0% undo-auto-amalgamate
1 0% - timer-event-handler
1 0% timer-inc-time
255 1% + ...
22121 98% - command-execute
20666 92% - funcall-interactively
20660 92% - execute-extended-command
20646 92% - command-execute
20626 92% - funcall-interactively
20617 92% - vundo
20031 89% - vundo-1
20013 89% - vundo--refresh-buffer
49 0% - vundo--draw-tree
34 0% - vundo--translate
31 0% - seq-mapcat
23 0% - seq-map
18 0% - apply
11 0% - #<compiled 0x1856cdad2b64f734>
5 0% - mapcar
2 0% #<subr F616e6f6e796d6f75732d6c616d626461_anonymous_lambda_11>
6 0% - apply
2 0% - seq-concatenate
2 0% apply
5 0% - vundo--build-tree
4 0% - vundo--sort-mod
3 0% - seq-sort
1 0% - apply
1 0% #<compiled -0x59ce19e634939fb>
18 0% - vundo-mode
1 0% face-remap-add-relative
1 0% - run-mode-hooks
1 0% - run-hooks
1 0% - global-font-lock-mode-enable-in-buffers
1 0% - turn-on-font-lock-if-desired
1 0% - turn-on-font-lock
1 0% font-lock-mode
3 0% - fit-window-to-buffer
3 0% - jit-lock-function
3 0% jit-lock-fontify-now
20 0% byte-code
1455 6% - byte-code
1455 6% - read-extended-command
1363 6% - completing-read-default
18 0% - command-execute
18 0% - funcall-interactively
17 0% - minibuffer-complete
17 0% - completion-in-region
17 0% - completion--in-region
17 0% - #<compiled -0x731a712fc48e962>
17 0% - apply
17 0% - #<compiled -0x17bc5b2160671e30>
17 0% - completion--in-region-1
17 0% - completion--do-completion
17 0% - completion-try-completion
17 0% - completion--nth-completion
17 0% - completion--some
17 0% - #<compiled 0xaf0040bd50f5b1c>
17 0% - completion-basic-try-completion
17 0% - #<subr F616e6f6e796d6f75732d6c616d626461_anonymous_lambda_49>
17 0% complete-with-action
1 0% - self-insert-command
1 0% undo-auto-amalgamate
1 0% - timer-event-handler
1 0% timer-inc-time
255 1% + ...Config: |
|
Thanks very much. The problem is, I couldn't tell what's taking the majority of time... Before we go further, may I ask you why you want to keep a large history, most of which you can't really meaningfully access? Since you asked for vundo to limit the displayed portion of the history, I assume you don't plan to utilize the wouldn't-be-shown part of the history? |
I don't want to keep a large history, I want not to lose it if I open a file, make a quick edit and close its buffer. I set the At first, seeing that Vundo was slow, I thought to ask you about introducing the history size limit, now I wonder whether setting it in Undo Fu Session would be better.
I'd like to know why. I took a look at the customisations available for |
|
@agreselin (not exactly related to the issue), but you might want to enable While it's nice to be able to save/restore undo-history exactly in the previous state, in practice I can't recall the last time I needed to traverse unused branches of previously saved sessions, so I enable linear undo history. This tends to make the undo history smaller with less overhead for vundo too. |
|
Hi @ideasman42 ! Thanks for the tip. With I agree that the full tree of previous sessions is rarely useful, but maybe the full tree of recent history is more useful than the linear history from long ago. Most likely, I'm overthinking my potential needs. Still, since we're discussing this I'm sharing the idea. For sure it's not a deal-breaker. |
|
@agreselin in practice the history created since last saving is often the full tree of recent history, but I suppose there could be exceptions to this where you want recent history to include branches from a previous session. If I understand what your getting at, it would be possible to prune early branches off the tree by some other method (keep N-number of branches so as not to store an unreasonable amount of history for e.g.). This might be nice to support although I don't find myself wanting such a feature. |
@ideasman42 I was thinking about deleting all nodes older than a certain amount of time and their branches. Would it be possible to do so? Sometimes I add something, say a reference, to my notes and then undo the insertion and save it somewhere else. It's happened that afterwards I couldn't find where I wrote down the reference and I retrieved it from the undone branch. After a week or so it's not of much use, but before that it may be. |
|
@agreselin you could remove them by date, although there would need to be time information in those branches (the user might have saved while working, but not necessarily). So I don't think it's something that's supported reliably. |
@ideasman42 Well, then the option of keeping the latest N branches is still interesting. But it could cut the history unexpectedly short if it has a lot of branches. What about just limiting the depth of the history? I mean, limit the number of nodes in the trunk and keep all branches. Then the worst that could happen is that Vundo slows down a bit. |
|
I wonder if your persistent history includes the save timestamps we are now using to highlight saved buffer states (the green circles)? If so, it would be possible to ascend the tree to a green circle at least some time in the past (1 month, say) and trim the tree up to that position, keeping the branches (it would need to be a saved state on the "main branch"). |
|
Yes, it includes time-stamps, it's just possible some branches don't include them. Although it's possible to use those time-stamps to prune all branches before a certain date - in the event they do exist. |
|
Hi, I've been using |
|
I can confirm that vundo's slowness with long chains is entirely related to (progn
(elp-instrument-function #'vundo--draw-tree)
(random "LONG-CHAIN-SLOW-DRAW")
(vundo-stress-test 5000 25 8 nil)
(elp-results))For me 2.35/2.5s is taken on A potential solution:
An uglier but maybe easier solution:
|
19075 😅 |
|
Here's how vundo launch performance behaves for a purely linear chain of undos as a function of final column number in the vundo buffer (approaching quadratic above a threshold): 
Pretty fast laptop. I suppose it's possible the |
|
Update: by modifying (when (> col 200)
(goto-char (point-max))
(insert "\n\n")
(setq col 0))Here's how the performance looks, switching from max column to number of edits (directly correlated for the current algorithm). This clearly demonstrates the conjecture that long lines are the culprit for poor vundo performance with deep undo trees. In all cases, at a given number of edits, the vundo buffer contains roughly the same number of drawn characters, they are just organized into fewer or more lines of differing maximum length. Again, emacs really hates drawing super long lines. Going below 80 columns improves times only modestly, so we are approaching the speed of the underlying draw algorithm, with its regex searches, lots of moves, etc. The smooth quadratic scaling with very long lines is an emacs display problem, not a vundo problem.
|
|
@jdtsmith Why not sidestep the long line problem? Rotate the tree by 90° and show it in a window on the left or right side? |
|
If someone implements one that works, I'lm more than happy to make it an option :-) |
|
What? And make it look like BTW, I simply cannot find anything in I've engaged on emacs-devel, and doubt has been cast on long lines as the culprit. We'll see if we can get to the bottom of it. If people want to try it, here the test code: ;; create and benchmark starting vundo with long linear undo trees
(defun vundo-linear-stress-test (nsen)
(interactive
(list (read-number "Number of edits (sentences): " 20000)))
(let* ((buf (get-buffer-create "*vundo-linear-test*"))
(res (cl-loop for nedits = 3 then (round (* nedits 1.25))
while (< nedits nsen) do
(with-current-buffer buf
(read-only-mode -1)
(font-lock-mode -1)
(erase-buffer)
(setq buffer-undo-list nil
pending-undo-list nil)
(dotimes (_ nedits)
(lorem-ipsum-insert-sentences 1)
(insert "\n")
(undo-boundary)))
collect (flatten-tree
(list nedits (with-current-buffer buf
(benchmark-call #'vundo))
(with-current-buffer " *vundo tree*"
(current-column))))
do (with-current-buffer (get-buffer " *vundo tree*")
(vundo-quit)))))
(with-output-to-temp-buffer "*vundo-linear-stress-test-results*"
(princ (format "%6s %10s %4s %10s %6s\n"
"Edits" "Time(s)" "GCs" "GCTime(s)" "Cols"))
(dolist (x res) (princ (apply #'format "%6d %10.3f %4d %10.3f %6d\n" x)))))) |
|
I just read the thread on emacs-devel, and Eli has a point: if it's because of redisplay, it should show up in the profile result as , but here we're seeing the time spent in |
|
Maybe |
|
I tried that and it didn't change anything. In fact that never runs with a purely linear tree, because there is always |
|
That's my best guess 🥲 I felt that counting columns might be slow when line is long. I don't really see anything else that could slow down drastically with longer lines |
|
The culprit was in fact just
|
|
@agreselin can you try out master and see what the launch time in your deep-history file is? |
|
~3 seconds. Moving to another node takes half a second or so. Another file in which Vundo was somewhat slow now hasn't any noticeable lag 👍 Btw I don't think rotating the tree is a bad idea. Someone willing to do that (I can't, sorry 🙏) could replicate Vim's undotree algorithm, which is pretty smart about keeping its tree narrow, see this picture. |
|
Moving shouldn't be so slow since the tree isn't redrawn, not sure why that is (though it could still be long-line display issues, Eli thinks that sets in a much longer lines, like 50K columns). This is with 19K columns, right? How long did it take to launch before? I'm not sure rotating will speed things much beyond the current algorithm. If you can |
Close to 26,000 now.
I didn't check before updating. Two weeks or so ago it was still around 20 s, if I remember correctly.
The results buffer is empty 🤔. If I invoke
I noticed while doing the test that Emacs in general is slower: even |
|
Yes, I also notice everything (minibuffer, other buffers) is a tad slow when such a long-line buffer is showing. What build/OS are you on? How big is your undo-limit to let so many accumulate? At some point you need to trim that thing :). |
|
I'm on my own build of Emacs 30.0.50 (with native compilation and PGTK) on Fedora 39.
It's 100 MB.. How much is yours? |
|
That's truly huge. I use: ;; Give undo a bit more rope: up to 2MB per buffer
(setq undo-limit 1000000
undo-strong-limit (* 2 undo-limit)) |
|
Sorry for the OT, I'm going to ask you a thing about I had dialed it down to 50 MB before you replied but I wasn't sure about going lower. My understanding is that if you copy-paste more than 2 MB of data, that edit fills your undo list and that and all older edits are discarded. Sometimes I edit big-ish dumps in Emacs and I'm afraid that if I copy-paste a large chunk to another buffer by mistake, it wipes the undo history of this other buffer. (My understanding comes mostly from |
|
2MB is about 30,000 lines of normal line length text. How often do you accidentally remove 30,000 lines of material? Note that additions are referenced in Unless you find yourself unwinding many thousands of nodes into history for some reason, this seems a far more sensible setup. And if you are that concerned about your data for some file, you might put it under revision control. |
|
Are there any downsides to keeping large limits? I never happened to hit even the default ones but with GBs of RAM I thought I could afford a bit of paranoia. Anyway, would it help Vundo much? I guess that before I pile up even 2 MB in changes the list of edits grows quite long. |
|
Yes it would help vundo and emacs not to have 25K long lines. Even with the latest fix, the performance is slowing relatively rapidly with increasing line length at that scale. Think of it not as a "RAM saving" limit, but a "keeping undo reasonable" limit. |
|
But if Vundo uses a horizontal layout and chokes Emacs with long lines that's a problem with Vundo, not with my configuration, in my opinion. Emacs doesn't choke on long undo histories. My file of notes is 8 MB in size, if I set the limits lower than that I'm only a wrong key stroke away after What makes undo reasonable is subjective, apparently, because other competent Elisp programmers use large undo limits, see Campbell Barton's suggestions here. |
|
Options are to implement a vertical layout, or come up with a drawing algorithm that limits the amount of displayed information. Sounds like @casouri is open to either. But a factor of >~10 improvement is nothing to dismiss. It also appears you haven't understood |
When the history gets very long Vundo takes quite a bit of time to start up and then it is rather slow. I guess limiting the length of the history would solve this, but how can I limit the size of just the displayed history?
PS: I use
can it slow down Vundo?
The text was updated successfully, but these errors were encountered: