https://lists.gnu.org/archive/html/coreutils/2014-08/msg0001...
Side note wrt deallocations being somewhat slow: could something like Boehm conservative GC speed that up, by grouping all the deallocations together, or by doing them on a separate thread?
I've seen programs building ASTs with hundreds of millions of nodes, where all the nodes were allocated by a separate malloc call, and ref-counted... More than one-third of the startup time (which was counted in minutes) was calls to malloc and free. Some optimizations were made, but in the end we ended up reducing the size of the AST instead of fixing the allocations.
Last time I did any serious parser work I used a pool allocator so I could free all the nodes at once, so allocation was just a compare + increment operation. Although that was forced on me by the difficulties of error recovery in yacc.
You can think of it like treating C as a garbage collected language, except the garbage collection cycle occurs only once at the end of the program :P
It really can be an effective trick. Deallocation isn't free, and under certain loads can be quite expensive.
The 1000+ leaks in the C version might actually be what's giving it the slight run-time advantage.