<div><div>Interesting comments. What exactly is getting copied? The accumulator binary? In this case the allocated size of the binary (doesn't it default to 256bytes or the twice initial contents, whichever is larger?) is much greater than the size of the bytes stuffed into it for accumulation. (See comments at the very end -- the Erlang docs state that the initial iteration will cause the binary to be copied.)</div>
<div><br></div><div>In any case, I would hope that such operations are linear to the size of the sequence. On the other hand, I think the costs of the operations on each is the salient point, no? In this case binaries appear to be more expensive both to iterate over (through destructuring) and accumulate.</div>
<div><br></div><div>I didn't necessarily think that these types of operations on binaries were faster, but there has been some fuss over binaries in the text processing side of things -- web servers, json parsers, etc. The reason I ran this little test was that while creating a json parser I wanted to see for myself.</div>
<div><br></div><div>I suppose a lot of the binary excitement has to do with just "utf8 in, utf8 out" efficiency. </div><div><br></div><div>Still, I think it would be surprising to some to find binaries slower for normal iterative processing. Culturally, Erlang list strings have a bad rep. Binaries to the rescue!</div>
<div><br></div><div>I wasn't able to find documentation comparing binary string to list string operations. However, there is advice as to the most efficient way to iterate over and accumulate binary strings.</div><div>
<br></div><div>From "Programming Efficiently with Binaries and Bit Strings":</div><div><div>- When you are building new bit strings make sure you append new data to the end of an old bit string</div><div>- When you iterate over a bit string use a direct style matching similar to what you would do for lists</div>
</div><div><br></div><div>And from the section on optimizations:</div><div><br></div><div><div>The basis of this optimization is that it the emulator can create bit strings with extra uninitialized space, so if a bit string is built by continuously appending to a binary the data does not need to be copied if there is enough uninitialized data at the end of the bit string.</div>
</div><div><br></div><div>One point I don't quite understand here:</div><div><br></div><div><a href="http://www.erlang.org/doc/efficiency_guide/binaryhandling.html#match_context">http://www.erlang.org/doc/efficiency_guide/binaryhandling.html#match_context</a></div>
<div><br></div><div>is is this function:</div><div><span style="font-family:Courier,monospace;font-size:medium"><br></span></div><div><span style="font-family:Courier,monospace;font-size:medium">my_list_to_binary(List) -></span></div>
<div><span style="font-family:Courier,monospace;font-size:medium">    my_list_to_binary(List, <<>>).</span></div><div><pre style="font-family:Courier,monospace;font-size:medium">my_list_to_binary([H|T], Acc) ->
    my_list_to_binary(T, <<Acc/binary,H>>);
my_list_to_binary([], Acc) ->
    Acc.</pre></div><div>the first iteration in my_list_binary/2 that Acc will be copied, but it will not be copied after this. I don't know why any copying occurs at all, since it is evident that in this case the initial binary <<>> is used solely for the append operation in the first clause. From what I understand, it is multiple references that cause copying to occur upon append, since the append operation may result the movement of the binary in memory, and the other references would otherwise become invalid. I only see one reference threading through this function.</div>
<div><br></div><div>I would think it would be allocated in my_list_to_binary/1, passed by reference, have an initial size of 256, be appended to without any copying, and only maybe be copied if the accumulation exceeded 256 bytes (the binary may be moved when it is extended.) Is the implication is that the initial blank binary <<>> is a different type of binary, say fixed-length or static, and that the first append operation triggers the copy of that binary into a newly allocated extendable binary (with initial size twice the original or 256 whichever is bigger)?</div>
<div><br></div><div>I really have to stop obsessing over this and move on, its a wonder where the mind goes when one has a cold...</div><div><br></div><div>Erik.</div><div>
<div><br>On Tuesday, October 23, 2012, Erik Søe Sørensen  wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p>Den 23/10/2012 14.00 skrev "Jesper Louis Andersen" <<a>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>
</blockquote></div></div></div>