Stress-testing vundo

[jdtsmith]

See this gist for an undo/vundo stress-test function, vundo--stress-test. It has been revealing to play with.

These setting definitely pushing the limits:

Undo stress test complete:
    10000 sentences inserted
    1500 undo chains of max length 12

    buffer-undo-list = 1948846 bytes
Buffer has 6394 lines, 39009 words, and 278099 characters.
Launching vundo: 
Elapsed time: 9.235434s (0.088656s in 1 GCs)
Mark set

this one ranges from 5-10s (6s more typical). Even with this gargantuan tree, navigation is still quite smooth (again, 8 yo hardware here). Using a to head up the tree works reliably, even as the length of the buffer-undo-list grows beyond 1/2 million. This is really impressive @casouri.

You can start to break things by going to extremes (here I've added a navigation to root benchmark too):

Undo stress test complete:
    15000 sentences inserted
    5000 undo chains of max length 9
    undo-limits: 50000000 strong: 80000000 outer: 100000000
    buffer-undo-list: length  261871,  23663505 bytes
Buffer has 16699 lines, 103312 words, and 736540 characters.
> Launching vundo: 
Elapsed time: 16.320850s (0.225208s in 2 GCs)
> Navigating to tree root: 
Elapsed time: 91.042314s (5.147266s in 42 GCs)
    buffer-undo-list: length  277581,  24490891 bytes

Here navigation starts to stutter (though basically still usable), and you get the dreaded "No possible route" message sometimes. Also assertions occasionally fail when navigating to a child branch:

Debugger entered--Lisp error: (cl-assertion-failed ((not (and (consp buffer-undo-list) (null (car buffer-undo-list)))) nil))
  cl--assertion-failed((not (and (consp buffer-undo-list) (null (car buffer-undo-list)))))
  vundo--move-to-node(#s(vundo-m :idx 4 :children ... :parent ... :prev-eqv nil :next-eqv ... :undo-list ... :point 10 :prev-saved-ts nil) #s(vundo-m :idx 14 :children ... :parent ... :prev-eqv nil :next-eqv nil :undo-list ... :point 12 :prev-saved-ts nil) #<buffer *vundo-stress-test*> [... ... ... ... ... ... ... ... ... ... ... ... ... ... ...])
  vundo-forward(1)
  funcall-interactively(vundo-forward 1)
  command-execute(vundo-forward)

Speed seems independent of whether vundo is native-compiled, which is good (time is spent outside vundo).

Originally posted by @jdtsmith in https://github.com/casouri/vundo/issues/66#issuecomment-1472083089

[jdtsmith]

Transferred to a new issue so that issue #66 is focused on the timestamp lossage.

[jdtsmith]

Launch vundo on very wide trees (not much branching) is slow, and moving around often results in a "step function" assertion fail -> extreme tree truncation, when navigating from the root of the tree:

Undo stress test complete:
    10000 sentences inserted
    100 undo chains of max length 5
    undo-limits: 1000000 strong: 2000000 outer: 24000000
    buffer-undo-list: length   20390,    570505 bytes
Buffer has 9730 lines, 58718 words, and 419693 characters.
> Launching vundo: 
Elapsed time: 25.259663s (0.097968s in 2 GCs)
> Navigating to tree root: 
Elapsed time: 1.991425s (0.460695s in 8 GCs)
    buffer-undo-list: length   59277,   1001621 bytes
Trimmed to: 19822
Trimmed to: 19821
Trimmed to: 19820
Trimmed to: 19819
Trimmed to: 19818
Trimmed to: 19817
Trimmed to: 19672
Trimmed to: 19526
Trimmed to: 19384
Trimmed to: 19345
Trimmed to: 19318
Trimmed to: 19241
Trimmed to: 19134
Trimmed to: 19095
vundo--list-subtract: Assertion failed: (> len1 len2)
Refresh
Trimmed to: 287
Trimmed to: 294
Trimmed to: 293
Trimmed to: 292
Trimmed to: 291
Trimmed to: 290
Trimmed to: 289
Trimmed to: 306
Trimmed to: 305

[casouri]

I like the idea very much! If you are interested, could you tidy it up and add it under /test? It would be handy for generating random undo trees. I'll investigate into the assertion failure.

[jdtsmith]

Great; see #69. I cleaned up the reporting a bit and made root-navigation optional.

The assertion failures usually happen while navigating near the root of a large tree, which may make sense since that represents the maximum "loop back" of the linear undo history. These are a common type:

vundo--move-to-node: Assertion failed: (not (and (consp buffer-undo-list) (null (car buffer-undo-list))))

followed by a refresh and vundo--move-to-node: No possible route.