Commit: patch 9.2.1036: syntax highlighting is slower than necessary

[Christian Brabandt]

patch 9.2.1036: syntax highlighting is slower than necessary

Commit: https://github.com/vim/vim/commit/f1b454912996d6417acd0d738de0eb7b60902c56
Author: Julien Voisin <julien...@dustri.org>
Date: Wed Sep 2 21:31:51 2026 +0000

patch 9.2.1036: syntax highlighting is slower than necessary

Problem: While advancing the syntax highlighting, store_current_state()
calls syn_stack_find_entry() about once per parsed line, and
that function rescans the state-cache list from its head every
time. With the list capped at 1000 entries this linear rescan
dominates the cost of highlighting a large file.
Solution: Keep a cached position to the entry last located in the list
and resume the scan from it when it is at or before the wanted
line, advancing the finger as new states are stored
(Julien Voisin).

The list is sorted by line number, so when the remembered entry is at or
before the wanted line the answer can only follow it, never precede it;
resuming from there returns the same entry as a scan from the head. The
"at or before" guard keeps this correct for any lookup order: a backward
or random-access lookup whose remembered entry is past the wanted line
falls back to a full scan. The pointer is cleared whenever an entry is
freed, the array is reallocated or the block is freed, so it cannot
dangle.

Parsing the syntax of a 20000-line C file is about a third faster, a
5000-line file about a quarter faster, benchmarked via something like
this:

```
call synID(1, 1, 1) " warm-up
let s = reltime()
for l in range(1, line('$')) | call synID(l, 1, 1) | endfor
call writefile([reltimefloat(reltime(s))], $T)
```

closes: #21166

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

diff --git a/src/structs.h b/src/structs.h
index 2953ccb02..216857de9 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -3183,6 +3183,8 @@ typedef struct {
* b_sst_array pointer to an array of synstate_T
* b_sst_len number of entries in b_sst_array[]
* b_sst_first pointer to first used entry in b_sst_array[] or NULL
+ * b_sst_search cached entry near the last accessed line, used as a
+ * start point for forward lookups, or NULL
* b_sst_firstfree pointer to first free entry in b_sst_array[] or NULL
* b_sst_freecount number of free entries in b_sst_array[]
* b_sst_check_lnum entries after this lnum need to be checked for
@@ -3191,6 +3193,7 @@ typedef struct {
synstate_T *b_sst_array;
int b_sst_len;
synstate_T *b_sst_first;
+ synstate_T *b_sst_search;
synstate_T *b_sst_firstfree;
int b_sst_freecount;
linenr_T b_sst_check_lnum;
diff --git a/src/syntax.c b/src/syntax.c
index 6f22d9ece..c55d1bc3a 100644
--- a/src/syntax.c
+++ b/src/syntax.c
@@ -1038,6 +1038,7 @@ syn_stack_free_block(synblock_T *block)
clear_syn_state(p);
VIM_CLEAR(block->b_sst_array);
block->b_sst_first = NULL;
+ block->b_sst_search = NULL;
block->b_sst_len = 0;
}
/*
@@ -1139,6 +1140,8 @@ syn_stack_alloc(void)
vim_free(syn_block->b_sst_array);
syn_block->b_sst_array = sstp;
syn_block->b_sst_len = len;
+ // The entries were moved to a new array, drop the stale pointer.
+ syn_block->b_sst_search = NULL;
}
}

@@ -1278,6 +1281,8 @@ syn_stack_cleanup(void)
static void
syn_stack_free_entry(synblock_T *block, synstate_T *p)
{
+ if (block->b_sst_search == p)
+ block->b_sst_search = NULL;
clear_syn_state(p);
p->sst_next = block->b_sst_firstfree;
block->b_sst_firstfree = p;
@@ -1294,13 +1299,27 @@ syn_stack_find_entry(linenr_T lnum)
synstate_T *p, *prev;

prev = NULL;
- for (p = syn_block->b_sst_first; p != NULL; prev = p, p = p->sst_next)
+ p = syn_block->b_sst_first;
+
+ // The list is sorted by line number and lookups while parsing advance
+ // monotonically, so resume from the last returned entry instead of
+ // rescanning from the start whenever it is at or before "lnum".
+ if (syn_block->b_sst_search != NULL
+ && syn_block->b_sst_search->sst_lnum <= lnum)
+ p = syn_block->b_sst_search;
+
+ for ( ; p != NULL; prev = p, p = p->sst_next)
{
if (p->sst_lnum == lnum)
+ {
+ syn_block->b_sst_search = p;
return p;
+ }
if (p->sst_lnum > lnum)
break;
}
+ if (prev != NULL)
+ syn_block->b_sst_search = prev;
return prev;
}

@@ -1389,6 +1408,8 @@ store_current_state(void)
sp = p;
sp->sst_stacksize = 0;
sp->sst_lnum = current_lnum;
+ // Resume the next forward lookup from the entry just stored.
+ syn_block->b_sst_search = sp;
}
}
if (sp != NULL)
diff --git a/src/version.c b/src/version.c
index 936ebc58a..6843673fe 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 */
+/**/
+ 1036,
/**/
1035,
/**/