I recently hacked together a small yacc for C. Initially, I was programming
as if I lived in the future and performance was not a problem.
However, with this LALR state generation you can't be too
silly, as I soon discovered. Processing this C89 grammar
took around 8 minutes, that was not really acceptable as bison could deal with
it in a fraction of second! After eliminating a few massive
performance hogs (sorted array to represent a set, loop invariant
in a loop), I was processing the above C grammar in 5 seconds.
Much better! Then comes my point, at that time the profiler was saying
that my code was fairly fast and accounted for less than a second
of runtime. The issue turned out to be in my use of malloc/free
in the libc. I used the following pattern:
- Allocate initialize some memory to store a temporary,
- if condition C is true, store the pointer
- otherwise, free the memory.
The case 3 happened much more often than the case 2 so I thought
that glibc's allocation code would simply give me the same
block all the time. Switching to the scheme below got
me a 5x speedup, so I guess I was wrong!
- Initialize a statically allocated object A,
- if condition C is true, allocate some memory and copy A to it,
then store the pointer
- otherwise, do nothing.
The conclusion I can draw is
that objects likely to be short-lived should really not be
allocated dynamically. This makes me wonder how, for instance,
C++'s RAII and Rust's automatic liveness mechanisms handle this
kind of performance problems. The speed of my yacc is now similar
to bison's after only 10% of the code was changed. This proves
the point that, instead of designing for speed, we should design
for simplicity and then, improve.