We're out of tree codes; now what?

[Mike Stump]

On Mar 22, 2007, at 9:13 AM, Doug Gregor wrote:
> 8-bit tree code (baseline):
>
> real    0m51.987s
> user    0m41.283s
> sys     0m0.420s
>
> subcodes (this patch):
>
> real    0m53.168s
> user    0m41.297s
> sys     0m0.432s
>
> 9-bit tree code (alternative):
>
> real    0m56.409s
> user    0m43.942s
> sys     0m0.429s

I hate to ask, did we see the time for 16 bit codes?  If it is faster  
than subcodes (51-53), maybe we just take the 4.5% memory hit and  
move on.  I ask, as I'd hate to saddle everyone with subcodes in the  
name of compile time, when there is any alternative that is better  
that doesn't cost as much in compile time.

I did some quick C measurements compiling expr.o from the top of the  
tree, with an -O0 built compiler with checking:

for a -g 8-bit code compile:
real    0m4.234s
user    0m4.104s
sys     0m0.126s

for a -g -O2 8-bit code compile:
real    0m23.202s
user    0m22.408s
sys     0m0.773s

for a -g 16-bit code compile:
real    0m4.249s					0.35% slower
user    0m4.121s
sys     0m0.124s

for a -g -O2 16-bit compile:
real    0m23.391s					0.81% slower
user    0m22.613s
sys     0m0.767s

If the disable-checking numbers hold up...  I think I'd rather eat  
the memory, retain most of the speed, and eliminate the complexity.

For a stage2 compiler (-O2) compiling expr.c:

for a -g 8-bit code compile:
real    0m2.633s
user    0m2.510s
sys     0m0.120s

for a -g -O2 8-bit code compile:
real    0m12.961s
user    0m12.195s
sys     0m0.755s

for a -g 16-bit code compile:
real    0m2.629s					0.15% slower
user    0m2.504s
sys     0m0.121s

for a -g -O2 16-bit code compile:
real    0m12.958s					0.023% slower
user    0m12.190s
sys     0m0.754s

All timings are best of 5 to get nice stable, comparable numbers.   
I'd anticipate that the slowdowns for C hold true to all languages  
and optimization passes.  I didn't try and optimize the memory  
savings, layout or time in creating my 16-bit patch, I applied the 8- 
 >16 obvious version.  My hope is that disable-checking numbers hold  
up reasonable well, and we can just use that version.  I'll accept a  
0.15% compiler.