Conversation
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
Signed-off-by: Julien Voisin <julien.voisin@dustri.org>
There was a problem hiding this comment.
Three of these lines restate the "if" and the "for" below them; what cannot
be read off the code is the precondition, and the complexity belongs in the
commit message.
| * When the wanted line is at or after the cached chunk (and the chunk | |
| * structure has not changed since, indicated by ml_upd_lastbuf) resume the | |
| * forward scan from the cached position instead of restarting at the first | |
| * chunk. This makes repeated in-order updates (e.g. ":s") amortized O(1) | |
| * instead of O(chunks) per call. | |
| * The scan resumes at the cached chunk while ml_upd_lastbuf is set: the | |
| * chunks have not moved since the last call. |
|
Measured over src/*.c concatenated (555627 lines), five runs each, median,
A delete still rescans from the first chunkPer the description and the new comment, the resume covers all update types Of those exits only three move chunks around. The one that leaves them 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 DisclosureCONTRIBUTING.md asks for AI use in a contribution to be disclosed. Is this See AGENTS.md
Like this: |
2 participants
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