Re: [patch] cse.c: Speed up cse_reg_info maintainance - Part 2

[bernds_cb1 at t-online dot de (Bernd Schmidt)]

> > Uhh, can't we just allocate the array once at the start of cse_main 
> > (where we know the highest current register number, NREGS) and 
> > deallocate it when we're done?  That shouldn't be too much overhead, and 
> > we wouldn't keep stuff allocated while we're not using it.
>
> I could do that, but can I try it after this patch is installed?  (I
> am not going to go away after this patch is installed. :-)
> Technically, if we have n functions in a module, each of which uses n
> registers, the total cost of array initialization would be quadratic
> in n.

Well, technically yes, but still linear in the size of the input (number 
of functions).

I appreciate the desire to reduce the number of memory allocations, but 
I also worry about memory footprint.  For small numbers of registers it 
shouldn't matter too much, but once it becomes a question whether to 
allocate 128k or 256k entries, this may be significant, especially since 
you could end up initializing a large number of unused entries.

I'll preapprove your patch if you make one modification, to add a 
reasonable limit (dunno, maybe 2k registers?) beyond which the size of 
the table is no longer the smallest usable power of two, but the exact 
number of elements needed.


Bernd