Commit: patch 9.2.0935: reading an undo file is slow with many undo headers
Christian Brabandt <[email protected]> Tue, 11 Aug 2026 20:30:05 +0200
| Newsgroups | gmane.editors.vim.devel |
|---|---|
| Message-ID | <[email protected]> |
patch 9.2.0935: reading an undo file is slow with many undo headers Commit: https://github.com/vim/vim/commit/fccf613c8f5b550797c08a45a768e14adefd882f Author: Samuel Schlesinger <[email protected]> Date: Tue Aug 11 18:16:45 2026 +0000 patch 9.2.0935: reading an undo file is slow with many undo headers Problem: Reading an undo file resolves every stored sequence number with a linear scan over all headers, making loading quadratic in the number of undo states. Solution: Sort uhp_table on uh_seq once and resolve each reference with a binary search; the duplicate uh_seq check becomes a single pass over the sorted table (Samuel Schlesinger). At the default 'undolevels' of 1000 the quadratic cost is not measurable; it takes 'undolevels' in the tens of thousands to matter. Loading an undo file with 20000 states and 50 alternate branches with :rundo goes from 1.49s to 0.11s (min of 3, macOS arm64), with the same undotree(). Also make old_idx/new_idx/cur_idx and the loop index "i" long instead of short/int: they index uhp_table, whose length num_head is a long read from the file. A short index truncated above 32767 headers, making the restored b_u_oldhead/b_u_newhead/b_u_curhead pointers wrong in exactly the many-headers case this change is about. Add tests: a round-trip test with alternate branches that compares the entries of the tree and the text at every sequence number, a corruption test with a duplicated uh_seq, and a test for reading an undo file with zero headers, which is written when only the line for the "U" command is saved. closes: #20942 Co-Authored-By: Claude <[email protected]> Signed-off-by: Samuel Schlesinger <[email protected]> Signed-off-by: Christian Brabandt <[email protected]> diff --git a/src/testdir/test_undo.vim b/src/testdir/test_undo.vim index 21b9dcfda..0b3e8cc93 100644 --- a/src/testdir/test_undo.vim +++ b/src/testdir/test_undo.vim @@ -1004,4 +1004,143 @@ func Test_corrupted_undofile() let &undofile = _uf endfunc +" Test that an undo file with alternate branches round-trips: the tree +" structure and the text at every sequence number survive :wundo + :rundo. +func Test_undofile_branches() + CheckFeature persistent_undo + let save_ul = &undolevels + defer execute('let &undolevels = ' .. save_ul) + new Xubranches.txt + setl noswapfile + set ul=100 + call setline(1, 'a') + for i in range(5) + let &undolevels = &undolevels + call setline(1, 'main' .. i) + endfor + " create two alternate branches + silent undo 3 + let &undolevels = &undolevels + call setline(1, 'branch-a') + silent undo 2 + let &undolevels = &undolevels + call setline(1, 'branch-b') + + write + defer delete('Xubranches.txt') + wundo! Xubranches.undo + defer delete('Xubranches.undo') + let tree_before = undotree() + " remember the text at every undo state + let texts = {} + for seq in range(1, tree_before.seq_last) + exe 'silent undo ' .. seq + let texts[seq] = getline(1) + endfor + bwipe! + + edit Xubranches.txt + setl noswapfile + rundo Xubranches.undo + let tree_after = undotree() + call assert_equal(tree_before.seq_last, tree_after.seq_last) + " every field of the entries, including times and save numbers, must + " round-trip through the undo file exactly + call assert_equal(tree_before.entries, tree_after.entries) + for [seq, text] in items(texts) + exe 'silent undo ' .. seq + call assert_equal(text, getline(1), 'text at undo state ' .. seq) + endfor + + bwipe! +endfunc + +" Test that a duplicated sequence number in an undo file is detected. +func Test_undofile_duplicate_seq() + CheckFeature persistent_undo + let save_ul = &undolevels + defer execute('let &undolevels = ' .. save_ul) + new Xudupseq.txt + setl noswapfile + set ul=100 + call setline(1, 'one') + let &undolevels = &undolevels + call setline(1, 'two') + let &undolevels = &undolevels + call setline(1, 'three') + write + defer delete('Xudupseq.txt') + wundo! Xudupseq.undo + defer delete('Xudupseq.undo') + + " Overwrite the uh_seq of the second header with that of the first. A + " header starts with the magic bytes 0x5f 0xd0, followed by four 4-byte + " header references and then the 4-byte uh_seq. Require the references + " and uh_seq to be small numbers, so that a timestamp that happens to + " contain the magic bytes is not mistaken for a header. + let blob = readfile('Xudupseq.undo', 'B') + let headers = [] + for i in range(len(blob) - 22) + if blob[i] == 0x5f && blob[i + 1] == 0xd0 + let ok = v:true + for field in range(5) + let off = i + 2 + field * 4 + if blob[off] != 0 || blob[off + 1] != 0 || blob[off + 2] != 0 + \ || blob[off + 3] > 8 + let ok = v:false + break + endif + endfor + if ok + call add(headers, i) + endif + endif + endfor + call assert_true(len(headers) >= 2, 'found undo file headers') + let first = headers[0] + 18 + let second = headers[1] + 18 + " Check that the detected headers are the intended ones before patching + " any bytes: the headers are written oldest first, so the first two carry + " sequence numbers 1 and 2. + call assert_equal(0z00000001, blob[first : first + 3]) + call assert_equal(0z00000002, blob[second : second + 3]) + let blob[second : second + 3] = blob[first : first + 3] + call writefile(blob, 'Xudupseq.undo') + call assert_fails('rundo Xudupseq.undo', 'E825:') + + bwipe! +endfunc + +" Test reading an undo file with zero undo headers, which is written when +" only the line for the "U" command is saved, e.g. with 'undolevels' -1. +func Test_undofile_zero_headers() + CheckFeature persistent_undo + let save_ul = &undolevels + defer execute('let &undolevels = ' .. save_ul) + " The buffer must not collect any undo header, so create the file on disk + " directly and only change the buffer with 'undolevels' already negative. + call writefile(['hello', 'world'], 'Xuzero.txt', 'D') + set undolevels=-1 + edit Xuzero.txt + normal! x + wundo! Xuzero.undo + defer delete('Xuzero.undo') + bwipe! + + " Make the same change so that the buffer text matches the hash stored in + " the undo file, then read the undo file back. + edit Xuzero.txt + normal! x + let v:errmsg = '' + " a silent rejection of the undo file gives a warning, not an error + let v:warningmsg = '' + rundo Xuzero.undo + call assert_equal('', v:errmsg) + call assert_equal('', v:warningmsg) + normal! U + call assert_equal('hello', getline(1)) + + bwipe! +endfunc + " vim: shiftwidth=2 sts=2 expandtab diff --git a/src/undo.c b/src/undo.c index 748b38054..5dc154cc2 100644 --- a/src/undo.c +++ b/src/undo.c @@ -1816,6 +1816,44 @@ theend: vim_free(file_name); } +/* + * Compare undo headers on the sequence number, for sorting uhp_table in + * u_read_undo(). + */ + static int +uhp_seq_cmp(const void *v1, const void *v2) +{ + const u_header_T *u1 = *(u_header_T **)v1; + const u_header_T *u2 = *(u_header_T **)v2; + + return u1->uh_seq == u2->uh_seq ? 0 : u1->uh_seq > u2->uh_seq ? 1 : -1; +} + +/* + * Find the header with sequence number "seq" in "uhp_table", which has + * "num_head" entries and is sorted on uh_seq. + * Return the table index of the header or -1 when not found. + */ + static long +uhp_table_find(u_header_T **uhp_table, long num_head, long seq) +{ + long lo = 0; + long hi = num_head - 1; + + while (lo <= hi) + { + long mid = lo + (hi - lo) / 2; + + if (uhp_table[mid]->uh_seq < seq) + lo = mid + 1; + else if (uhp_table[mid]->uh_seq > seq) + hi = mid - 1; + else + return mid; + } + return -1; +} + /* * Load the undo tree from an undo file. * If "name" is not NULL use it as the undo file name. This also means being @@ -1837,10 +1875,10 @@ u_read_undo(char_u *name, char_u *hash, char_u *orig_name UNUSED) long old_header_seq, new_header_seq, cur_header_seq; long seq_last, seq_cur; long last_save_nr = 0; - short old_idx = -1, new_idx = -1, cur_idx = -1; + long old_idx = -1, new_idx = -1, cur_idx = -1; long num_read_uhps = 0; time_t seq_time; - int i, j; + long i; int c; u_header_T *uhp; u_header_T **uhp_table = NULL; @@ -2067,69 +2105,49 @@ u_read_undo(char_u *name, char_u *hash, char_u *orig_name UNUSED) # define SET_FLAG(j) # endif - // We have put all of the headers into a table. Now we iterate through the - // table and swizzle each sequence number we have stored in uh_*_seq into - // a pointer corresponding to the header with that sequence number. - for (i = 0; i < num_head; i++) + // We have put all of the headers into a table. Each header stores the + // sequence numbers of the headers it links to; resolve those into + // pointers. Sort the table on uh_seq once, so that every lookup is a + // binary search instead of a linear scan, which would be quadratic + // overall. Every entry is non-NULL: a header that failed to + // unserialize or a count mismatch was an error above. + if (num_head > 0) + qsort(uhp_table, (size_t)num_head, sizeof(u_header_T *), uhp_seq_cmp); + + // In the sorted table two headers with the same uh_seq are neighbours. + for (i = 0; i < num_head - 1; i++) { - uhp = uhp_table[i]; - if (uhp == NULL) - continue; - for (j = 0; j < num_head; j++) - if (uhp_table[j] != NULL && i != j - && uhp_table[i]->uh_seq == uhp_table[j]->uh_seq) - { - corruption_error("duplicate uh_seq", file_name); - goto error; - } + if (uhp_table[i]->uh_seq == uhp_table[i + 1]->uh_seq) { - int seq = uhp->uh_next.seq; - uhp->uh_next.ptr = NULL; - for (j = 0; j < num_head; j++) - if (uhp_table[j] != NULL && i != j - && uhp_table[j]->uh_seq == seq) - { - uhp->uh_next.ptr = uhp_table[j]; - SET_FLAG(j); - break; - } - } - { - int seq = uhp->uh_prev.seq; - uhp->uh_prev.ptr = NULL; - for (j = 0; j < num_head; j++) - if (uhp_table[j] != NULL && i != j - && uhp_table[j]->uh_seq == seq) - { - uhp->uh_prev.ptr = uhp_table[j]; - SET_FLAG(j); - break; - } - } - { - int seq = uhp->uh_alt_next.seq; - uhp->uh_alt_next.ptr = NULL; - for (j = 0; j < num_head; j++) - if (uhp_table[j] != NULL && i != j - && uhp_table[j]->uh_seq == seq) - { - uhp->uh_alt_next.ptr = uhp_table[j]; - SET_FLAG(j); - break; - } - } - { - int seq = uhp->uh_alt_prev.seq; - uhp->uh_alt_prev.ptr = NULL; - for (j = 0; j < num_head; j++) - if (uhp_table[j] != NULL && i != j - && uhp_table[j]->uh_seq == seq) - { - uhp->uh_alt_prev.ptr = uhp_table[j]; - SET_FLAG(j); - break; - } + corruption_error("duplicate uh_seq", file_name); + goto error; } + } + + // Resolve the sequence number "link".seq into a pointer to the header + // with that number. A number that does not match any header, including + // zero (written for a NULL pointer) and the own sequence number of the + // header "hidx", resolves to NULL. +# define SWIZZLE_SEQ(link, hidx) \ + do { \ + long fidx = uhp_table_find(uhp_table, num_head, (link).seq); \ + \ + if (fidx >= 0 && fidx != (hidx)) \ + { \ + (link).ptr = uhp_table[fidx]; \ + SET_FLAG(fidx); \ + } \ + else \ + (link).ptr = NULL; \ + } while (0) + + for (i = 0; i < num_head; i++) + { + uhp = uhp_table[i]; + SWIZZLE_SEQ(uhp->uh_next, i); + SWIZZLE_SEQ(uhp->uh_prev, i); + SWIZZLE_SEQ(uhp->uh_alt_next, i); + SWIZZLE_SEQ(uhp->uh_alt_prev, i); if (old_header_seq > 0 && old_idx < 0 && uhp->uh_seq == old_header_seq) { old_idx = i; @@ -2146,6 +2164,7 @@ u_read_undo(char_u *name, char_u *hash, char_u *orig_name UNUSED) SET_FLAG(i); } } +# undef SWIZZLE_SEQ // Now that we have read the undo info successfully, free the current undo // info and use the info from the file. diff --git a/src/version.c b/src/version.c index 3401ba30b..45ddeda96 100644 --- a/src/version.c +++ b/src/version.c @@ -763,6 +763,8 @@ static char *(features[]) = static int included_patches[] = { /* Add new patch number below this line */ +/**/ + 935, /**/ 934, /**/ -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/vim_dev/E1wtrEj-007Vet-JW%40256bit.org.