[vim/vim] pattern_match(): cache the compiled program of the last pattern (PR #20941)

[Samuel Schlesinger]

Problem

"=~", 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 — 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

Benchmark scripts

let g:items = map(range(100000), {_, v -> 'item_' .. v .. '_suffix'})

let g:medpat = '\v^%(foo|bar|baz|junk|other|thing)_%(\d{1,6})_%(suffix|prefix|infix)$'
let t0 = reltime()
call filter(copy(g:items), {_, v -> v =~# g:medpat})
echo reltimefloat(reltime(t0))

let g:bigpat = '^\%(' .. join(map(range(200), {_, v -> 'name' .. v}), '\|') .. '\)$'
let t0 = reltime()
call filter(copy(g:items)[0 : 9999], {_, v -> v =~# g:bigpat})
echo reltimefloat(reltime(t0))

let t0 = reltime()
call filter(copy(g:items), {_, v -> v =~# '^item_\d\+9_'})
echo reltimefloat(reltime(t0))

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

• fa471fe pattern_match(): cache the compiled program of the last pattern
• 8880891 test: cover the semantics around the eval pattern cache

File Changes

(5 files)

• 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

—
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.Message ID: <vim/vim/pull/20941@github.com>