Commit: patch 9.2.1115: ml_updatechunk() rescans all chunks on every line update

[Christian Brabandt]

patch 9.2.1115: ml_updatechunk() rescans all chunks on every line update

Commit: https://github.com/vim/vim/commit/8692965f52a8e13084a6cb4d726ddc5f3b25c2c6
Author: Julien Voisin <julien...@dustri.org>
Date: Wed Sep 16 18:33:35 2026 +0000

patch 9.2.1115: ml_updatechunk() rescans all chunks on every line update

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 only when the chunk table is
changed.

The static resume cache was previously used only for the strictly
consecutive ML_CHNK_ADDLINE fast path. This commit generalizes it to cover all
update types: every mutation leaves the cache pointing at the last
touched chunk with a correct start line; the exits that move chunks
around (split, collapse, reset) clear it, while the ones that leave the
chunk table intact keep it, including the ML_CHNK_DELLINE exit that only
decrements a line count. This turns repeated in-order updates (":s", line
insertions and deletions such as ":g/pat/d") from O(chunks) per call
into amortized O(1).

With 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

closes: #21309

Signed-off-by: Julien Voisin <julien...@dustri.org>
Signed-off-by: Christian Brabandt <c...@256bit.org>

diff --git a/src/memline.c b/src/memline.c
index 8e68d3361..aa2a76891 100644
--- a/src/memline.c
+++ b/src/memline.c
@@ -5842,7 +5842,6 @@ ml_updatechunk(
int updtype)
{
static buf_T *ml_upd_lastbuf = NULL;
- static linenr_T ml_upd_lastline;
static linenr_T ml_upd_lastcurline;
static int ml_upd_lastcurix;

@@ -5868,6 +5867,7 @@ ml_updatechunk(
buf->b_ml.ml_usedchunks = 1;
buf->b_ml.ml_chunksize[0].mlcs_numlines = 1;
buf->b_ml.ml_chunksize[0].mlcs_totalsize = 1;
+ ml_upd_lastbuf = NULL; // invalidate resume cache
}

if (updtype == ML_CHNK_UPDLINE && buf->b_ml.ml_line_count == 1)
@@ -5878,29 +5878,25 @@ ml_updatechunk(
buf->b_ml.ml_usedchunks = 1;
buf->b_ml.ml_chunksize[0].mlcs_numlines = 1;
buf->b_ml.ml_chunksize[0].mlcs_totalsize = (long)buf->b_ml.ml_line_len;
+ ml_upd_lastbuf = NULL; // invalidate resume cache
return;
}

/*
* Find chunk that our line belongs to, curline will be at start of the
* chunk.
+ * The scan resumes at the cached chunk while ml_upd_lastbuf is set: the
+ * chunks have not moved since the last call.
*/
- if (buf != ml_upd_lastbuf || line != ml_upd_lastline + 1
- || updtype != ML_CHNK_ADDLINE)
+ if (buf != ml_upd_lastbuf || line < curline)
{
- for (curline = 1, curix = 0;
- curix < buf->b_ml.ml_usedchunks - 1
+ curline = 1;
+ curix = 0;
+ }
+ for (; curix < buf->b_ml.ml_usedchunks - 1
&& line >= curline + buf->b_ml.ml_chunksize[curix].mlcs_numlines;
curix++)
- curline += buf->b_ml.ml_chunksize[curix].mlcs_numlines;
- }
- else if (curix < buf->b_ml.ml_usedchunks - 1
- && line >= curline + buf->b_ml.ml_chunksize[curix].mlcs_numlines)
- {
- // Adjust cached curix & curline
curline += buf->b_ml.ml_chunksize[curix].mlcs_numlines;
- curix++;
- }
curchnk = buf->b_ml.ml_chunksize + curix;

if (updtype == ML_CHNK_DELLINE)
@@ -6043,7 +6039,6 @@ 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)
@@ -6053,6 +6048,7 @@ ml_updatechunk(
}
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));
@@ -6062,10 +6058,16 @@ ml_updatechunk(
&& 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--;
@@ -6077,7 +6079,6 @@ ml_updatechunk(
return;
}
ml_upd_lastbuf = buf;
- ml_upd_lastline = line;
ml_upd_lastcurline = curline;
ml_upd_lastcurix = curix;
}
diff --git a/src/version.c b/src/version.c
index 768fa662e..8eb908fe9 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 */
+/**/
+ 1115,
/**/
1114,
/**/