> Could you, perhaps, try running with font-lock-maximum-decoration set to
 > 2 for C Mode?  This gives a speed advantage of around a factor of 3 over
 > decoration level 3, at a cost of some inaccuracies.

Hardly any better.  Setting it to 1 doesn't improve things much either.
The optimized build with decorations at level 3 outperforms the debug
build with decorations at level 1 by an order of magnitude.

I used the attached file test2.el.  If you want to try it set
‘font-lock-maximum-decoration’ to the according value and adapt the path
to frame.c to the one of your emacs src directory.  With emacs -Q
evaluate the test2.el file and do M-x foofoo.  Here I get the following
results for my debug build (the call count is 169):

font-lock-maximum-decoration  elapsed  average
3                             1.999    0.012
2                             1.765    0.010
1                             1.466    0.009

In comparison the optimized build with ‘font-lock-maximum-decoration’ 3
gets me:

3                             0.409    0.002

martin