Interesting. I had never even considered not pre-allocating space for it... :-) In a "real" implementation, you also need space to store sub-capture locations.

Interesting. I had never even considered not pre-allocating space for it... :-) In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win. There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)