[erlang-questions] list vs binary performarnce, destructuring and consing

[Erik Søe Sørensen]

Den 23/10/2012 14.00 skrev "Jesper Louis Andersen" <
jesper.louis.andersen@REDACTED>:
>
> There is no reason to believe binaries to be faster than lists for this
benchmark. The list construction can take its cells from the process heap
and since it is garbage collected, doing so is an (amortized) O(1) pointer
move. The reverse takes O(N). So we are looking at N*O(1) + O(N) = O(N).
The binary construction has to reallocate the binary once in a while which
imposes a copy on the binary to make it larger. In the worst case, and when
it is badly implemented, this is an O(N^2) operation. If it is better
implemented, we can shave it down to O(N lg N) or thereabout, depending on
the slack amount we want to allocate. But it does not seem as cheap as the
other solution, barring constants.

The normal slack amount to use is some factor times the current length -
eg. a doubling. This gives O(n) amortized cost (remember that while you do
need to copy O(lg n) times, you need to copy far less than n elements each
time - it sums up to <2n copyings).

So asymptotically it should be at level with lists (I'm fairly certain that
BEAM is smart about this) - but the constant factor is still wanting...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20121023/eb82a1fd/attachment.htm>