[vim/vim] NFA regexp matching is slower than necessary (PR #21202)
Julien Voisin
Problem: NFA regexp matching is slower than necessary because addstate()
tracks the recursion depth in a static variable.
Solution: Pass the recursion depth as a function parameter so it stays in a
register instead of being spilled to memory around every recursive
call.
addstate() is called very frequently and recursively. Storing the depth counter in a static variable forces the compiler to reload and store it in memory around each recursive call, since it cannot prove the recursion does not modify it. Passing it as a parameter keeps it in a register and drops the increment/decrement bookkeeping on every return path. The recursion limit behavior is unchanged.
This reduces the instruction count of NFA matching by roughly 4% on state-heavy patterns. Benchmarking was done with something like:
set re=0
let s:word = repeat('abc123 def456 ghijk_lmnop QRSTUV wxyz0 ', 4000)
for i in range(120)
let s = s:word | let s = substitute(s, '\%#=2\(\a\+\)\(\d\+\)', '\2\1', 'g')
let s = s:word | let s = substitute(s, '\%#=2\a\+\d\+', 'X', 'g')
call matchstr(s:word, '\%#=2\(\a\|\d\|_\)\{3,}')
endfor
qa!
and taskset -c 7 perf stat -e instructions ./vim -u NONE -N -X -es -S /tmp/nfabench/count.vim
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/21202
Commit Summary
- f4928ef NFA regexp matching is slower than necessary
File Changes
(1 file)
- M src/regexp_nfa.c (37)
Patch Links:
—
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.
Christian Brabandt
chrisbra left a comment (vim/vim#21202)thanks
—
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.