Replace lists with vectors for the main vundo-m lists

[ideasman42]

Prefer vectors as they can perform direct lookups without having to iterate over all items.

[casouri]

Before making large changes like this, is there really significant performance gain by changing to vector? I'm sure most of the nth in loops can be removed. I tried to run

(benchmark-run 1 (ert-run-tests 'vundo-test--4 #'ignore))

with the list version (master) and vector version (pr-use-vector) and they produce identical result, around 1.9s. Could you try it on your machine?

[ideasman42]

For more complex trees the improvement is measurable, this test creates a tree with more branches:

• master 32.44 seconds.
• pr-use-vector 28.82 seconds.

More generally, avoiding unnecessarily slow lookups means there is one less thing to have to investigate when looking into performance problems. Vectors make sense in this case too with fixed arrays that use a lot of index lookups.

---

Execute the following script with:

emacs -batch -l ./vundo.el -l ./test/vundo-test-speed.el -f ert-run-tests-batch-and-exit

;;; vundo-test-speed.el --- Tests for vundo  -*- lexical-binding: t; -*-
(require 'ert)
(require 'vundo)
(require 'subr-x)
(require 'cl-lib)

(defmacro vundo-test--setup (&rest body)
  "Setup and evaluate BODY."
  `(with-temp-buffer
     (buffer-enable-undo)
     (let ((vundo-glyph-alist vundo-unicode-symbols))
       ,@body)))

(ert-deftest vundo-test--4 ()
  "This tests complex buffers."
  (vundo-test--setup
   (let ((undo-limit most-positive-fixnum)
         (undo-strong-limit most-positive-fixnum)
         (inhibit-read-only t))
     (dotimes (i 1000)
       (dotimes (_ 2)
         (dotimes (_ 2)
           (dotimes (_ 4)
             (insert "\n")
             (undo-boundary))
           (dotimes (_ 2)
             (undo-only 1)
             (undo-boundary)))
         (undo-only 1)
         (undo-boundary))
       (undo-only 1)
       (undo-boundary))

     (with-current-buffer (vundo-1 (current-buffer))
       (vundo-stem-root)))

   (garbage-collect)))

(provide 'vundo-test)

;;; vundo-test-speed.el ends here

---

[casouri]

I don't think 11% is significant, considering even reasonably large undo-list takes no longer than 1s to process, and normal undo-list does not have as many branches as in your test.

But since this isn't some critical software, and after looking at the patch I can see that the change is manageable, I'll merge it. Could you do me a favor and revert all the mod-vect to mod-list? All these name changes obscure the actual code change in the diff, and I don't think it is necessary to change the name.

[ideasman42]

Pushed the name change.

[casouri]

Merged. Thanks!

[ideasman42]

I don't think 11% is significant, considering even reasonably large undo-list takes no longer than 1s to process, and normal undo-list does not have as many branches as in your test.

But since this isn't some critical software, and after looking at the patch I can see that the change is manageable, I'll merge it. Could you do me a favor and revert all the mod-vect to mod-list? All these name changes obscure the actual code change in the diff, and I don't think it is necessary to change the name.

We probably disagree on some of the details here, first - it seems likely that there are other bottlenecks in vundo's operation that avoiding slow list lookups only give minimal gains.

Nevertheless, I find it important to avoid unnecessary algorithmic complexity, especially when the performance degradation is non-linear, the worst-cases are potentially very bad - and having users manually find and report these worst cases ... which developers then need to verify and resolve isn't good use of anyone's time. So unless there are significant trade-offs, I think it's best to always avoid this kind of non-linear increase in complexity - making one less possible bottleneck when evaluating performance in the future. Also, it may be that if/when other areas are optimized the performance gain from using efficient list lookups is more noticeable by comparison.

[ideasman42]

Quick follow up, from profiling vundo startup - drawing the tree is the bottleneck.

Benchmarking this change with drawing the tree disabled:

• Before: 3.42 seconds
• After: 0.76 seconds

Increasing the tree size sees larger gains as you would expect.

[casouri]

We probably disagree on some of the details here, first - it seems likely that there are other bottlenecks in vundo's operation that avoiding slow list lookups only give minimal gains.

Nevertheless, I find it important to avoid unnecessary algorithmic complexity, especially when the performance degradation is non-linear, the worst-cases are potentially very bad - and having users manually find and report these worst cases ... which developers then need to verify and resolve isn't good use of anyone's time. So unless there are significant trade-offs, I think it's best to always avoid this kind of non-linear increase in complexity - making one less possible bottleneck when evaluating performance in the future. Also, it may be that if/when other areas are optimized the performance gain from using efficient list lookups is more noticeable by comparison.

I don't disagree. As I said I agree that vector is the right thing to do. And since it's not a big change (sans the name changes) I'm happy to merge it.

Quick follow up, from profiling vundo startup - drawing the tree is the bottleneck.

I'm aware of that. Vundo is pretty fast whenever I use it so I never find the need to optimize it further, especially when there isn't any trivial optimization for tree-drawing. Also moving along the tree is very cheap so the initial cost isn't that big of a deal for me. If you have some clever optimization for tree-drawing, I'm all ears :-)