[vim/vim] u_read_undo(): use a sorted table to swizzle sequence numbers (PR #20942)

----==_mimepart_6a7261e053200_e0118039754
Content-Type: text/plain; charset="UTF-8"

## 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.

<details>
<summary>Benchmark method</summary>

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().
</details>

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 --

  * u_read_undo(): use a sorted table to swizzle sequence numbers
  * test: cover undo file round-trip with branches, duplicate uh_seq

-- File Changes --

    M src/testdir/test_undo.vim (110)
    M src/undo.c (139)

-- Patch Links --

https://github.com/vim/vim/pull/20942.patch
https://github.com/vim/vim/pull/20942.diff

-- 
Reply to this email directly or view it on GitHub:
https://github.com/vim/vim/pull/20942
You are receiving this because you are subscribed to this thread.

Message ID: <vim/vim/pull/[email protected]>

-- 
-- 
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/vim/vim/pull/20942%40github.com.

----==_mimepart_6a7261e053200_e0118039754
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<h2 dir=3D"auto">Problem</h2>
<p dir=3D"auto">When reading an undo file every sequence number is resolved=
 to a header<br>
pointer with a linear scan over all headers, which makes loading<br>
quadratic in the number of undo states.</p>
<h2 dir=3D"auto">Solution</h2>
<p dir=3D"auto">Sort the headers on uh_seq once and resolve each reference =
with a<br>
binary search.  The duplicate-uh_seq corruption check becomes a single<br>
pass over the sorted table.</p>
<p dir=3D"auto">Benchmark (min of 3, macOS arm64): :rundo of an undo file w=
ith 20000<br>
states and 50 alternate branches: 1.74s -&gt; 0.12s, with the same<br>
undotree() seq_last.</p>
<details>
<summary>Benchmark method</summary>
<p dir=3D"auto">Generate: in a new buffer make 20000 setline() changes, eac=
h separated<br>
with <code class=3D"notranslate">:let &amp;undolevels =3D &amp;undolevels</=
code> to start a new undo block, then<br>
50 branches via <code class=3D"notranslate">:undo 100</code> followed by a =
new change; <code class=3D"notranslate">:write</code> the text<br>
and <code class=3D"notranslate">:wundo</code> the undo file.  Measure: edit=
 the written file and time<br>
<code class=3D"notranslate">:rundo</code> with reltime().</p>
</details>
<p dir=3D"auto">Adds a round-trip test with alternate branches that compare=
s the tree<br>
structure and the text at every sequence number, and a corruption test<br>
with a duplicated uh_seq; both also pass unpatched.</p>
<p dir=3D"auto">AI assistance is acknowledged with Co-Authored-By trailers =
on the<br>
commits, per AGENTS.md.</p>

<hr>

<h4>You can view, comment on, or merge this pull request online at:</h4>
<p>&nbsp;&nbsp;<a href=3D'https://github.com/vim/vim/pull/20942'>https://gi=
thub.com/vim/vim/pull/20942</a></p>

<h4>Commit Summary</h4>
<ul>
  <li><a href=3D"https://github.com/vim/vim/pull/20942/commits/2d6aa98d84a5=
96f6f31c3cb9e74bf6ac71e4e680" class=3D"commit-link">2d6aa98</a>  u_read_und=
o(): use a sorted table to swizzle sequence numbers</li>
  <li><a href=3D"https://github.com/vim/vim/pull/20942/commits/5fb39b8914d4=
40682998b8e7d41cfb95050ab9c9" class=3D"commit-link">5fb39b8</a>  test: cove=
r undo file round-trip with branches, duplicate uh_seq</li>
</ul>

<h4 style=3D"display: inline-block">File Changes </h4> <p style=3D"display:=
 inline-block">(<a href=3D"https://github.com/vim/vim/pull/20942/files">2&n=
bsp;files</a>)</p>
<ul>
  <li>
    <strong>M</strong>
    <a href=3D"https://github.com/vim/vim/pull/20942/files#diff-569759a4eee=
950d0f5f9d8ef1532e775d5d0e349335c0884698570e131521685">src/testdir/test_und=
o.vim</a>
    (110)
  </li>
  <li>
    <strong>M</strong>
    <a href=3D"https://github.com/vim/vim/pull/20942/files#diff-3cbdb63e7cd=
bc1a5bcf26f07bb9686dd850628091f4bc4cab365db5f106e5551">src/undo.c</a>
    (139)
  </li>
</ul>

<h4>Patch Links:</h4>
<ul>
  <li><a href=3D'https://github.com/vim/vim/pull/20942.patch'>https://githu=
b.com/vim/vim/pull/20942.patch</a></li>
  <li><a href=3D'https://github.com/vim/vim/pull/20942.diff'>https://github=
.com/vim/vim/pull/20942.diff</a></li>
</ul>

<p style=3D"font-size:small;-webkit-text-size-adjust:none;color:#666;">&mda=
sh;<br />Reply to this email directly, <a href=3D"https://github.com/vim/vi=
m/pull/20942">view it on GitHub</a>, or <a href=3D"https://github.com/notif=
ications/unsubscribe-auth/ACY5DGGBZXLZBVUMVOR6EL35IJMWBAVCNFSNUABEKJSXA33TN=
F2G64TZHM2DAOJZG42DQMR3JFZXG5LFHM2TANRVGI4TKNBXHCQXMAQ">unsubscribe</a>.<br=
 />Triage notifications, keep track of coding agent tasks and review pull r=
equests on the go with GitHub Mobile for <a href=3D"https://github.com/noti=
fications/mobile/ios/ACY5DGF5D5CRZ4DO4MDP77D5IJMWBA5CNFSNUABEM5UWIORPF5TWS5=
BNNB2WEL2QOVWGYUTFOF2WK43UF42DEMBXGQ3TSOJSGSTHEZLBONXW5KTTOVRHGY3SNFRGKZFFM=
V3GK3TUVJTG633UMVZF62LPOM">iOS</a> and <a href=3D"https://github.com/notifi=
cations/mobile/android/ACY5DGHT3RZQGTSRYZ3CQXL5IJMWBA5CNFSNUABEM5UWIORPF5TW=
S5BNNB2WEL2QOVWGYUTFOF2WK43UF42DEMBXGQ3TSOJSGSTHEZLBONXW5KTTOVRHGY3SNFRGKZF=
FMV3GK3TUVZTG633UMVZF6YLOMRZG62LE">Android</a>. Download it today!
<br />You are receiving this because you are subscribed to this thread.<img=
 src=3D"https://github.com/notifications/beacon/ACY5DGAZ5G7F467MQEQDTST5IJM=
WBBFCNFSM6AAAAAC43QF44WWGG33NNVSW45C7OR4XAZNFJFZXG5LFVJRW63LNMVXHIX3JMTHQAA=
AAAEW6URTWUZZGKYLTN5XKU43VMJZWG4TJMJSWI.gif" height=3D"1" width=3D"1" alt=
=3D"" /><span style=3D"color: transparent; font-size: 0; display: none; vis=
ibility: hidden; overflow: hidden; opacity: 0; width: 0; height: 0; max-wid=
th: 0; max-height: 0; mso-hide: all">Message ID: <span>&lt;vim/vim/pull/209=
42</span><span>@</span><span>github</span><span>.</span><span>com&gt;</span=
></span></p>
<script type=3D"application/ld+json">[
{
"@context": "http://schema.org",
"@type": "EmailMessage",
"potentialAction": {
"@type": "ViewAction",
"target": "https://github.com/vim/vim/pull/20942",
"url": "https://github.com/vim/vim/pull/20942",
"name": "View Pull Request"
},
"description": "View this Pull Request on GitHub",
"publisher": {
"@type": "Organization",
"name": "GitHub",
"url": "https://github.com"
}
}
]</script>

<p></p>

-- <br />
-- <br />
You received this message from the &quot;vim_dev&quot; maillist.<br />
Do not top-post! Type your reply below the text you are replying to.<br />
For more information, visit <a href=3D"http://www.vim.org/maillist.php">htt=
p://www.vim.org/maillist.php</a><br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;vim_dev&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]">vim_dev+uns=
[email protected]</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
vim_dev/vim/vim/pull/20942%40github.com?utm_medium=3Demail&utm_source=3Dfoo=
ter">https://groups.google.com/d/msgid/vim_dev/vim/vim/pull/20942%40github.=
com</a>.<br />

----==_mimepart_6a7261e053200_e0118039754--