Constant structures optimisation? (Re: CRC16 in erlang)

[Thomas Lindgren]

--- Thomas Johnsson <thomas@REDACTED> wrote:

> Thomas Lindgren wrote:
> 
> >--- Rudolph van Graan <rvg@REDACTED>
> wrote:
> >
> >  
> >
> >>Hi Joe,
> >>
> >>Here is one which I wrote some time ago. It does
> >>work, but there  
> >>might be some issues. (No guarantees on speed!)
> >>    
> >>
> >
> >Here is an easy speedup:
> >
> >-define(CRC16Def, {...}).
> >
> >crc_index(N) -> element(N+1, ?CRC16Def).
> >
> >This is O(1) time rather than O(N) and 1/2 the
> space
> >of the original definition. Pretty good, but
> there's
> >more.
> >  
> >
> 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). When this is
available, the cost would be about the same as
building the table once and passing it around, or even
a bit better.

Best,
Thomas


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com