vim-patch:9.2.0935: reading an undo file is slow with many undo headers (#41285)

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: vim/vim#20942

https://github.com/vim/vim/commit/fccf613c8f5b550797c08a45a768e14adefd882f

Co-authored-by: Samuel Schlesinger <sgschlesinger@gmail.com>
Co-authored-by: Claude <noreply@anthropic.com>

0 files changed, 0 insertions, 0 deletions