[erlang-questions] Reverses Order of Bytes in Binary

[Vincent de Phily]

On Friday 09 January 2015 18:18:26 Max Lapshin wrote:
> Ah, really.  I should be ashamed.
> 
> reverse(Bin) ->
>   reverse(Bin, []).
> 
> reverse(<<>>, Acc) -> list_to_binary(Acc);
> reverse(<<C,Bin/binary>>, Acc) -> reverse(Bin, [C|Acc]).

I microbenched various implementations with small and large binaries trying to 
get rid of the intermediate list representation and was really surprised by 
the results :

l(B) -> list_to_binary(lists:reverse(binary_to_list(B))).

b(Bin) -> b(Bin, []).
b(<<>>, Acc) -> list_to_binary(Acc);
b(<<C,Bin/binary>>, Acc) -> b(Bin, [C|Acc]).

b1(Bin) -> b1(Bin, <<>>).
b1(<<>>, Acc) -> Acc;  
b1(<<C,Bin/binary>>, Acc) -> b1(Bin, <<C,Acc/binary>>).

b2(B) -> b2(B,byte_size(B)-1,<<>>).
b2(B,0,Acc) -> <<Acc/binary,(binary:at(B,0))>>;
b2(B,N,Acc) -> b2(B,N-1,<<Acc/binary,(binary:at(B,N))>>).


I consistently get l/1 fastest:
l                   10225
b                   14247
b1                 339329
b2                  50249

I'm surprised that the list/binary conversions are that cheap (compared to 
directly parsing/building the binary) because of all the small memory 
allocations they need to do.

Is there some native optimisation they use that plain erlang can't use ? 
Typically, does list_to_binary/1 construct the binary in a more efficient way 
than is possible from plain erlang ? When decontructing l/1 into its 3 steps I 
find that binary_to_list takes just slightly longer than reverse, and 
list_to_binary takes a good bit less.

For what it's worth, binary:reverse/1 could probably be much faster if 
implemented as a bif. I wonder if it'd be worth it to have some kind of 
binary:preallocate/2 function.

-- 
Vincent de Phily