regexp NFA compilation reallocates scratch buffers each time by jvoisin · Pull Request #21307 · vim/vim · GitHub
Skip to content

regexp NFA compilation reallocates scratch buffers each time - #21307

Closed
jvoisin wants to merge 1 commit into
vim:masterfrom
jvoisin:nfa_realloc
Closed

jvoisin wants to merge 1 commit into
vim:masterfrom
jvoisin:nfa_realloc

Conversation

@jvoisin

@jvoisin jvoisin commented Sep 14, 2026

Copy link
Copy Markdown
Contributor

Problem: Every NFA regexp compilation allocates and frees two temporary
scratch buffers, the postfix list and the fragment stack, even
though the NFA states themselves are already allocated in a
single block; this repeats for every pattern, e.g. the hundreds
of autocmd patterns and syntax items loaded when opening a file.
Solution: Keep the postfix list and the fragment stack allocated between
compilations, growing them only when a larger one is needed, and
free them once in free_regexp_stuff().

The backtracking engine already uses this approach: it keeps its "regstack" and "backpos" scratch buffers across invocations, allocating them only when not present, and frees them in free_regexp_stuff(). Apply the same reuse to the NFA "post_start" postfix list and the post2nfa() fragment stack by making them grow-only statics. Only the scratch memory management changes; the compiled program and matching are unaffected.

Measured with callgrind (instructions retired), against baseline:

  • opening a single C file: ~3%
  • opening a Vim script file: ~2.5%
  • cold start opening a file (full runtime): -3%
  • repeated ":runtime! syntax/c.vim" (x40): -2.5%
  • opening 51 real source files in a session: -2%

Problem:  Every NFA regexp compilation allocates and frees two temporary
          scratch buffers, the postfix list and the fragment stack, even
          though the NFA states themselves are already allocated in a
          single block; this repeats for every pattern, e.g. the hundreds
          of autocmd patterns and syntax items loaded when opening a file.
Solution: Keep the postfix list and the fragment stack allocated between
          compilations, growing them only when a larger one is needed, and
          free them once in free_regexp_stuff().

The backtracking engine already uses this approach: it keeps its "regstack"
and "backpos" scratch buffers across invocations, allocating them only when
not present, and frees them in free_regexp_stuff(). Apply the same reuse to
the NFA "post_start" postfix list and the post2nfa() fragment stack by making
them grow-only statics. Only the scratch memory management changes; the
compiled program and matching are unaffected.

Measured with callgrind (instructions retired), against baseline:
- opening a single C file:                   ~3%
- opening a Vim script file:                 ~2.5%
- cold start opening a file (full runtime):  -3%
- repeated ":runtime! syntax/c.vim" (x40):   -2.5%
- opening 51 real source files in a session: -2%

Signed-off-by: Jules Voisin <julien.voisin@example.com>

@chrisbra chrisbra left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks, I have only 2 minor style issue, but I can fix those while merging

Comment thread src/regexp_nfa.c

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can now drop the braces here

Comment thread src/regexp_nfa.c

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can now drop the braces here

@chrisbra chrisbra closed this in 09c21a4 Sep 15, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants