Constant structures optimisation? (Re: CRC16 in erlang)

[Mikael Pettersson]

Thomas Lindgren writes:
 > > No, it is going to be O(N') (where N' is the size of
 > > the table), since 
 > > the structure ?CRC16Def will be built every time !
 > 
 > Yes indeed, but recall that the table has a constant
 > size N' ... The constant cost hidden inside "O(1)" is
 > pretty hefty of course, as discussed. (By the same
 > reasoning, the cost of looking up the element in the
 > list is really constant too, since it is bounded by at
 > most 254 linked list traversals. So I'll definitely
 > admit I did give a too pessimistic O() for the
 > original code :-) 
 > 
 > Passing around the table is still likely to be far
 > faster in practice than either the original or the
 > first optimized version, just as one might expect ...
 > 
 > Note that, in the past, Hipe could build constant
 > terms (such as this table) once and for all at compile
 > time. I'm not sure if that functionality still remains
 > (e.g., there were some GC issues).

I didn't look at the original CRC16 source code, but
HiPE most definitely still recognises constant terms
(except binaries I think), allocates them once when the code
is loaded, and references them in constant time at runtime.

(There are GC issues. We have workarounds in place, but
they are not perfect. In particular, there is an upper
bound on the total amount of memory a system can devote
to constant terms. We and the OTP folks are aware of the
issues; suffice it to say that the solution is non-trivial
but there has been some progress recently.)

OTOH, replacing computation with lookups in large
constant data structures isn't always a win. You're
trading instruction execution for larger D-cache footprint:
this often looks _very_ good in micro-benchmarks, but
tends to be unfair and suboptimal in larger applications.

/Mikael