[vim/vim] u_read_undo(): use a sorted table to swizzle sequence numbers (PR #20942)
Samuel Schlesinger
Problem
When reading an undo file every sequence number is resolved to a header
pointer with a linear scan over all headers, which makes loading
quadratic in the number of undo states.
Solution
Sort the headers on uh_seq once and resolve each reference with a
binary search. The duplicate-uh_seq corruption check becomes a single
pass over the sorted table.
Benchmark (min of 3, macOS arm64): :rundo of an undo file with 20000
states and 50 alternate branches: 1.74s -> 0.12s, with the same
undotree() seq_last.
Generate: in a new buffer make 20000 setline() changes, each separated
with :let &undolevels = &undolevels to start a new undo block, then
50 branches via :undo 100 followed by a new change; :write the text
and :wundo the undo file. Measure: edit the written file and time
:rundo with reltime().
Adds a round-trip test with alternate branches that compares the tree
structure and the text at every sequence number, and a corruption test
with a duplicated uh_seq; both also pass unpatched.
AI assistance is acknowledged with Co-Authored-By trailers on the
commits, per AGENTS.md.
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/20942
Commit Summary
- 2d6aa98 u_read_undo(): use a sorted table to swizzle sequence numbers
- 5fb39b8 test: cover undo file round-trip with branches, duplicate uh_seq
File Changes
(2 files)
- M src/testdir/test_undo.vim (110)
- M src/undo.c (139)
Patch Links:
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.