[ggreer]

There's plenty of room for improvement. For example: if you run the same regex many times in a row, Vim rebuilds the DFA on each run. A cache of recently-used DFAs would avoid tons of wasted computation. Also, Vim doesn't free many regex-related data structures until you close the buffer they were invoked on. I had to work-around that bug when writing a plugin, since it caused Vim to use gigabytes of memory.

The best solution would probably be to switch to PCRE. Some Vim-specific stuff[1] would have to be special-cased, but Vim could get an order of magnitude speedup (and fix quite a few bugs) by using a modern, optimized, well-tested regex library.

1. Vim abuses regexes like nothing I've ever seen. You can even match line and column numbers with the regex engine: http://vimdoc.sourceforge.net/htmldoc/pattern.html#/\%l