<p>Den 23/10/2012 14.00 skrev "Jesper Louis Andersen" <<a href="mailto:jesper.louis.andersen@erlang-solutions.com">jesper.louis.andersen@erlang-solutions.com</a>>:<br>
><br>
> 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.</p>

<p>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).</p>

<p>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...</p>