Constant structures optimisation? (Re: CRC16 in erlang)

Thomas Johnsson <>
Tue Jan 31 15:58:59 CET 2006


Thomas Lindgren wrote:

>--- Rudolph van Graan <> 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 !
At least that is the way it looks by looking at the -S output of the 
compiler:

-module(stest).
-compile(export_all).
-define(t,{aa,bb,cc}).
crc_index(N) -> element(N, ?t).

erlc -S stest.erl    =====> stest.S :
....
{function, crc_index, 1, 6}.
  {label,5}.
    {func_info,{atom,stest},{atom,crc_index},1}.
  {label,6}.
    {test_heap,4,1}.
    {put_tuple,3,{x,1}}.
    {put,{atom,aa}}.
    {put,{atom,bb}}.
    {put,{atom,cc}}.
    {bif,element,{f,0},[{x,0},{x,1}],{x,0}}.
    {'%live',1}.
    return.

At least at this level of the code it looks like big structure constants 
are built at every call anyway.
The beaviour looks similar for lists.
But perhaps some lower level of the compiler discovers this and puts the 
constant in a constant area?

-- Thomas

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20060131/4a25f128/attachment.html>


More information about the erlang-questions mailing list