[vim/vim] pattern_match(): cache the compiled program of the last pattern (PR #20941)
Samuel Schlesinger (Vim Github Repository) <[email protected]> Tue, 04 Aug 2026 15:04:14 -0700
| Newsgroups | gmane.editors.vim.devel |
|---|---|
| Message-ID | <vim/vim/pull/[email protected]> |
----==_mimepart_6a7261de3347d_fb1180431989
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
## Problem
"=3D~", match(), matchstr(), matchlist(), matchbufline(), matchstrlist()
and split() compile their pattern on every call. A script matching a
list of items against one pattern compiles it once per item, which can
dwarf the cost of the match itself.
## Solution
Keep the compiled program of the last pattern in a cache. The cache
owns the program only between uses: eval_regcomp() hands it to the
caller and empties the cache, and eval_regfree() adopts the program the
caller ends up with =E2=80=94 so the automatic engine falling back to the
backtracking engine, which frees the original program, needs no special
handling and vim_regfree() is unchanged. Patterns whose compilation
depends on state outside the cache key ("~" and bracket classes) are
not cached; the key covers 'regexpengine' and 'encoding', and
'ignorecase' applies at execution time as before.
Benchmarks (min of 3, macOS arm64):
- filter() of 100000 items with a plugin-sized pattern: 0.239s -> 0.065s
- a generated 200-branch alternation over 10000 items: 0.512s -> 0.059s
- a short inline pattern over 100000 items: 0.120s -> 0.081s
<details>
<summary>Benchmark scripts</summary>
```vim
let g:items =3D map(range(100000), {_, v -> 'item_' .. v .. '_suffix'})
let g:medpat =3D '\v^%(foo|bar|baz|junk|other|thing)_%(\d{1,6})_%(suffix|pr=
efix|infix)$'
let t0 =3D reltime()
call filter(copy(g:items), {_, v -> v =3D~# g:medpat})
echo reltimefloat(reltime(t0))
let g:bigpat =3D '^\%(' .. join(map(range(200), {_, v -> 'name' .. v}), '\|=
') .. '\)$'
let t0 =3D reltime()
call filter(copy(g:items)[0 : 9999], {_, v -> v =3D~# g:bigpat})
echo reltimefloat(reltime(t0))
let t0 =3D reltime()
call filter(copy(g:items), {_, v -> v =3D~# '^item_\d\+9_'})
echo reltimefloat(reltime(t0))
```
</details>
Adds Test_eval_pattern_cache() covering "~" staying current across
:substitute, execution-time 'ignorecase', 'regexpengine' changes and
the fallback-replaced program; it also passes 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/20941
-- Commit Summary --
* pattern_match(): cache the compiled program of the last pattern
* test: cover the semantics around the eval pattern cache
-- File Changes --
M src/alloc.c (1)
M src/eval.c (109)
M src/evalfunc.c (16)
M src/proto/eval.pro (3)
M src/testdir/test_eval_stuff.vim (46)
-- Patch Links --
https://github.com/vim/vim/pull/20941.patch
https://github.com/vim/vim/pull/20941.diff
--=20
Reply to this email directly or view it on GitHub:
https://github.com/vim/vim/pull/20941
You are receiving this because you are subscribed to this thread.
Message ID: <vim/vim/pull/[email protected]>
--=20
--=20
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
---=20
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 e=
mail to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/vim_dev/vim=
/vim/pull/20941%40github.com.
----==_mimepart_6a7261de3347d_fb1180431989
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<h2 dir=3D"auto">Problem</h2>
<p dir=3D"auto">"=3D~", match(), matchstr(), matchlist(), matchbufline(), m=
atchstrlist()<br>
and split() compile their pattern on every call. A script matching a<br>
list of items against one pattern compiles it once per item, which can<br>
dwarf the cost of the match itself.</p>
<h2 dir=3D"auto">Solution</h2>
<p dir=3D"auto">Keep the compiled program of the last pattern in a cache. =
The cache<br>
owns the program only between uses: eval_regcomp() hands it to the<br>
caller and empties the cache, and eval_regfree() adopts the program the<br>
caller ends up with =E2=80=94 so the automatic engine falling back to the<b=
r>
backtracking engine, which frees the original program, needs no special<br>
handling and vim_regfree() is unchanged. Patterns whose compilation<br>
depends on state outside the cache key ("~" and bracket classes) are<br>
not cached; the key covers 'regexpengine' and 'encoding', and<br>
'ignorecase' applies at execution time as before.</p>
<p dir=3D"auto">Benchmarks (min of 3, macOS arm64):</p>
<ul dir=3D"auto">
<li>filter() of 100000 items with a plugin-sized pattern: 0.239s -> 0.06=
5s</li>
<li>a generated 200-branch alternation over 10000 items: 0.512s -> 0.059=
s</li>
<li>a short inline pattern over 100000 items: 0.120s -> 0.081s</li>
</ul>
<details>
<summary>Benchmark scripts</summary>
<div class=3D"highlight highlight-source-viml" dir=3D"auto"><pre class=3D"n=
otranslate"><span class=3D"pl-k">let</span> <span class=3D"pl-smi"><span cl=
ass=3D"pl-k">g:</span>items</span> <span class=3D"pl-k">=3D</span> <span cl=
ass=3D"pl-en">map</span>(<span class=3D"pl-en">range</span>(<span class=3D"=
pl-c1">100000</span>), {_, <span class=3D"pl-c1">v</span> <span class=3D"pl=
-k">-</span>> <span class=3D"pl-s"><span class=3D"pl-pds">'</span>item_<=
span class=3D"pl-pds">'</span></span> .. <span class=3D"pl-c1">v</span> .. =
<span class=3D"pl-s"><span class=3D"pl-pds">'</span>_suffix<span class=3D"p=
l-pds">'</span></span>})
<span class=3D"pl-k">let</span> <span class=3D"pl-smi"><span class=3D"pl-k"=
>g:</span>medpat</span> <span class=3D"pl-k">=3D</span> <span class=3D"pl-s=
"><span class=3D"pl-pds">'</span>\v^%(foo|bar|baz|junk|other|thing)_%(\d{1,=
6})_%(suffix|prefix|infix)$<span class=3D"pl-pds">'</span></span>
<span class=3D"pl-k">let</span> t0 <span class=3D"pl-k">=3D</span> <span cl=
ass=3D"pl-en">reltime</span>()
<span class=3D"pl-c1">call</span> <span class=3D"pl-en">filter</span>(<span=
class=3D"pl-en">copy</span>(<span class=3D"pl-smi"><span class=3D"pl-k">g:=
</span>items</span>), {_, <span class=3D"pl-c1">v</span> <span class=3D"pl-=
k">-</span>> <span class=3D"pl-c1">v</span> <span class=3D"pl-k">=3D</sp=
an>~# <span class=3D"pl-smi"><span class=3D"pl-k">g:</span>medpat</span>})
<span class=3D"pl-c1">echo</span> <span class=3D"pl-en">reltimefloat</span>=
(<span class=3D"pl-en">reltime</span>(t0))
<span class=3D"pl-k">let</span> <span class=3D"pl-smi"><span class=3D"pl-k"=
>g:</span>bigpat</span> <span class=3D"pl-k">=3D</span> <span class=3D"pl-s=
"><span class=3D"pl-pds">'</span>^\%(<span class=3D"pl-pds">'</span></span>=
.. <span class=3D"pl-en">join</span>(<span class=3D"pl-en">map</span>(<spa=
n class=3D"pl-en">range</span>(<span class=3D"pl-c1">200</span>), {_, <span=
class=3D"pl-c1">v</span> <span class=3D"pl-k">-</span>> <span class=3D"=
pl-s"><span class=3D"pl-pds">'</span>name<span class=3D"pl-pds">'</span></s=
pan> .. <span class=3D"pl-c1">v</span>}), <span class=3D"pl-s"><span class=
=3D"pl-pds">'</span>\|<span class=3D"pl-pds">'</span></span>) .. <span clas=
s=3D"pl-s"><span class=3D"pl-pds">'</span>\)$<span class=3D"pl-pds">'</span=
></span>
<span class=3D"pl-k">let</span> t0 <span class=3D"pl-k">=3D</span> <span cl=
ass=3D"pl-en">reltime</span>()
<span class=3D"pl-c1">call</span> <span class=3D"pl-en">filter</span>(<span=
class=3D"pl-en">copy</span>(<span class=3D"pl-smi"><span class=3D"pl-k">g:=
</span>items</span>)[<span class=3D"pl-c1">0</span> : <span class=3D"pl-c1"=
>9999</span>], {_, <span class=3D"pl-c1">v</span> <span class=3D"pl-k">-</s=
pan>> <span class=3D"pl-c1">v</span> <span class=3D"pl-k">=3D</span>~# <=
span class=3D"pl-smi"><span class=3D"pl-k">g:</span>bigpat</span>})
<span class=3D"pl-c1">echo</span> <span class=3D"pl-en">reltimefloat</span>=
(<span class=3D"pl-en">reltime</span>(t0))
<span class=3D"pl-k">let</span> t0 <span class=3D"pl-k">=3D</span> <span cl=
ass=3D"pl-en">reltime</span>()
<span class=3D"pl-c1">call</span> <span class=3D"pl-en">filter</span>(<span=
class=3D"pl-en">copy</span>(<span class=3D"pl-smi"><span class=3D"pl-k">g:=
</span>items</span>), {_, <span class=3D"pl-c1">v</span> <span class=3D"pl-=
k">-</span>> <span class=3D"pl-c1">v</span> <span class=3D"pl-k">=3D</sp=
an>~# <span class=3D"pl-s"><span class=3D"pl-pds">'</span>^item_\d\+9_<span=
class=3D"pl-pds">'</span></span>})
<span class=3D"pl-c1">echo</span> <span class=3D"pl-en">reltimefloat</span>=
(<span class=3D"pl-en">reltime</span>(t0))</pre></div>
</details>
<p dir=3D"auto">Adds Test_eval_pattern_cache() covering "~" staying current=
across<br>
:substitute, execution-time 'ignorecase', 'regexpengine' changes and<br>
the fallback-replaced program; it also passes 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> <a href=3D'https://github.com/vim/vim/pull/20941'>https://gi=
thub.com/vim/vim/pull/20941</a></p>
<h4>Commit Summary</h4>
<ul>
<li><a href=3D"https://github.com/vim/vim/pull/20941/commits/fa471fe5803e=
55025f1d50caeb0062f33df74a0f" class=3D"commit-link">fa471fe</a> pattern_ma=
tch(): cache the compiled program of the last pattern</li>
<li><a href=3D"https://github.com/vim/vim/pull/20941/commits/8880891fc6ae=
ba554df90e546a9b60554201575f" class=3D"commit-link">8880891</a> test: cove=
r the semantics around the eval pattern cache</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/20941/files">5&n=
bsp;files</a>)</p>
<ul>
<li>
<strong>M</strong>
<a href=3D"https://github.com/vim/vim/pull/20941/files#diff-4907ceb74ff=
bc48dc681461fd341de2e2080248c93548cb2fc226b85512a7b48">src/alloc.c</a>
(1)
</li>
<li>
<strong>M</strong>
<a href=3D"https://github.com/vim/vim/pull/20941/files#diff-3f6891fec05=
432f415cfd49150db67e2bc72d20e0a94a4e3ac762f7ff55f9921">src/eval.c</a>
(109)
</li>
<li>
<strong>M</strong>
<a href=3D"https://github.com/vim/vim/pull/20941/files#diff-a4bde4e6cdd=
803bf45433cf5966ea421ac70ddc84534709877f40751436b87e4">src/evalfunc.c</a>
(16)
</li>
<li>
<strong>M</strong>
<a href=3D"https://github.com/vim/vim/pull/20941/files#diff-4a13e4a7dc8=
90b2ca22931bae419d37ab92dcfde917a30e794e767cb96b731e3">src/proto/eval.pro</=
a>
(3)
</li>
<li>
<strong>M</strong>
<a href=3D"https://github.com/vim/vim/pull/20941/files#diff-ee694b3ded1=
3ca9258e45af481aa1b81b4c83d6119b4d5b752021e10587a200c">src/testdir/test_eva=
l_stuff.vim</a>
(46)
</li>
</ul>
<h4>Patch Links:</h4>
<ul>
<li><a href=3D'https://github.com/vim/vim/pull/20941.patch'>https://githu=
b.com/vim/vim/pull/20941.patch</a></li>
<li><a href=3D'https://github.com/vim/vim/pull/20941.diff'>https://github=
.com/vim/vim/pull/20941.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/20941">view it on GitHub</a>, or <a href=3D"https://github.com/notif=
ications/unsubscribe-auth/ACY5DGHGKBTDTSXJEBSZIWL5IJMV5AVCNFSNUABEKJSXA33TN=
F2G64TZHM2DAOJZG42DQMR3JFZXG5LFHM2TANRVGI4TKMJWGWQXMAQ">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/ACY5DGHYHGCD2YP7EBNPPLL5IJMV5A5CNFSNUABEM5UWIORPF5TWS5=
BNNB2WEL2QOVWGYUTFOF2WK43UF42DEMBXGQ3TSNRVGCTHEZLBONXW5KTTOVRHGY3SNFRGKZFFM=
V3GK3TUVJTG633UMVZF62LPOM">iOS</a> and <a href=3D"https://github.com/notifi=
cations/mobile/android/ACY5DGCRJJO4LQ6OYAJWAJL5IJMV5A5CNFSNUABEM5UWIORPF5TW=
S5BNNB2WEL2QOVWGYUTFOF2WK43UF42DEMBXGQ3TSNRVGCTHEZLBONXW5KTTOVRHGY3SNFRGKZF=
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/ACY5DGFZ4EPYBK4XS3VQANL5IJM=
V5BFCNFSM6AAAAAC43QF3EGWGG33NNVSW45C7OR4XAZNFJFZXG5LFVJRW63LNMVXHIX3JMTHQAA=
AAAEW6URJ5UZZGKYLTN5XKU43VMJZWG4TJMJSWI.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><vim/vim/pull/209=
41</span><span>@</span><span>github</span><span>.</span><span>com></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/20941",
"url": "https://github.com/vim/vim/pull/20941",
"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 "vim_dev" 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" 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/20941%40github.com?utm_medium=3Demail&utm_source=3Dfoo=
ter">https://groups.google.com/d/msgid/vim_dev/vim/vim/pull/20941%40github.=
com</a>.<br />
----==_mimepart_6a7261de3347d_fb1180431989--