[vim/vim] ml_updatechunk() rescans all chunks on every line update (PR #21309)
Julien Voisin
Problem: ml_updatechunk() only resumes its chunk scan for strictly
consecutive line insertions; for line updates (e.g.
":substitute") and any other non-consecutive access it
restarts the scan from the first chunk, which is slow on
large buffers.
Solution: Resume the forward scan from the cached chunk position
whenever the wanted line is at or after it, falling back to a
full scan only when moving backwards or into another buffer,
and invalidate the cache when the chunk table is reset to a
single chunk.
The static resume cache was previously used only for the strictly consecutive ML_CHNK_ADDLINE fast path. Generalize it to cover all update types. Every mutation already leaves the cache pointing at the last touched chunk with a correct start line, and the structural changes (chunk split, collapse, reset) clear it, so resuming the forward scan is equivalent to a full scan from the start. This turns repeated in-order updates from O(chunks) per call into amortized O(1), while keeping the computed line offsets byte-identical.
Under callgrind the substitute workload drops 1.8% in total instructions and ml_updatechunk() self cost drops 63%, granting a 10% speed boost on ":%s/<int>/int32_t/ge" in a buffer containing src/*.c
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/21309
Commit Summary
- f960529 ml_updatechunk() rescans all chunks on every line update
File Changes
(1 file)
- M src/memline.c (26)
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.
h_east
h-east left a comment (vim/vim#21309)Measured over src/*.c concatenated (555627 lines), five runs each, median,
with the buffer written out identical in all three:
| master | PR | PR + the below | |
|---|---|---|---|
:%s/\<int\>/int32_t/ge |
0.235 | 0.201 | 0.185 s |
:g/\<int\>/d |
0.252 | 0.252 | 0.198 s |
A delete still rescans from the first chunk
Per the description and the new comment, the resume covers all update types
and makes repeated in-order updates amortized O(1). The ML_CHNK_DELLINE
branch of ml_updatechunk(), however, drops the cache before any of its
exits, so :g/pat/d starts at the first chunk on every call as before.
Of those exits only three move chunks around. The one that leaves them
alone, taken when the chunk is still large enough or is the first one, can
keep the cache: the deleted line came out of the chunk the cache points at,
and the chunks before it keep their lines. Against this PR:
diff --git a/src/memline.c b/src/memline.c --- a/src/memline.c +++ b/src/memline.c @@ -6041,9 +6041,8 @@ ml_updatechunk( } else if (updtype == ML_CHNK_DELLINE) { curchnk->mlcs_numlines--; - ml_upd_lastbuf = NULL; // Force recalc of curix & curline if (curix < buf->b_ml.ml_usedchunks - 1 && curchnk->mlcs_numlines + curchnk[1].mlcs_numlines <= MLCS_MINL) { @@ -6051,8 +6050,9 @@ ml_updatechunk( curchnk = buf->b_ml.ml_chunksize + curix; } else if (curix == 0 && curchnk->mlcs_numlines <= 0) { + ml_upd_lastbuf = NULL; // Force recalc of curix & curline buf->b_ml.ml_usedchunks--; mch_memmove(buf->b_ml.ml_chunksize, buf->b_ml.ml_chunksize + 1, buf->b_ml.ml_usedchunks * sizeof(chunksize_T)); return; @@ -6060,12 +6060,18 @@ ml_updatechunk( else if (curix == 0 || (curchnk->mlcs_numlines > 10 && curchnk->mlcs_numlines + curchnk[-1].mlcs_numlines > MLCS_MINL)) { + // The chunks are left as they are, the cached position stays + // valid. + ml_upd_lastbuf = buf; + ml_upd_lastcurline = curline; + ml_upd_lastcurix = curix; return; } // Collapse chunks + ml_upd_lastbuf = NULL; // Force recalc of curix & curline curchnk[-1].mlcs_numlines += curchnk->mlcs_numlines; curchnk[-1].mlcs_totalsize += curchnk->mlcs_totalsize; buf->b_ml.ml_usedchunks--; if (curix < buf->b_ml.ml_usedchunks)
Otherwise the description and the comment could name :s and line
insertions instead.
Disclosure
CONTRIBUTING.md asks for AI use in a contribution to be disclosed. Is this
one AI-assisted? What prompts the question is the rationale above: it has
the structural changes clearing the cache, which is not what the
ML_CHNK_DELLINE branch does.
—
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.
h_east
h-east left a comment (vim/vim#21309)See #21318
—
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.
Julien Voisin
jvoisin left a comment (vim/vim#21309)The code is organic locally source human-written. The only (local) LLM usage was to run the benchmarks. I blame my lack of familiarity with the code and writing the commit message before git commit -a --amend a bunch of times into it and forgetting to be thorough.
—
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.
Christian Brabandt
chrisbra left a comment (vim/vim#21309)Thanks
—
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.
h_east
h-east left a comment (vim/vim#21309)@jvoisin
Please provide some kind of reaction to the review, especially if you accept it.
I cannot tell whether you accepted this suggestion without checking the commit.
Also, it wouldn't hurt to at least say "Thanks."
—
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.
Julien Voisin
jvoisin left a comment (vim/vim#21309)Oh, sure. Thanks for the review, I incorporated your changes and added @copilot as helper
—
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.