[erlang-questions] Interleave binaries

Hynek Vychodil hynek@REDACTED
Tue Aug 9 10:52:37 CEST 2011 

Just for curiosity I measured performance of different codes during
train travel and here are fastest implementations on mine notebook
(model name : Intel(R) Core(TM) i5 CPU M 520  @ 2.40GHz):

il_16(A, B) when is_binary(A), is_binary(B), size(A) =:= size(B) ->
il_16(A, B, <<>>).

il_16(<<
  A1:16, A2:16, A3:16, A4:16, A5:16, A6:16, A7:16, A8:16,
  A9:16, A10:16, A11:16, A12:16, A13:16, A14:16, A15:16, A16:16,
  RestA/binary>>,
  <<
  B1:16, B2:16, B3:16, B4:16, B5:16, B6:16, B7:16, B8:16,
  B9:16, B10:16, B11:16, B12:16, B13:16, B14:16, B15:16, B16:16,
  RestB/binary>>, Acc) ->
  il_16(RestA, RestB, <<Acc/binary,
    A1:16, B1:16, A2:16, B2:16, A3:16, B3:16, A4:16, B4:16,
    A5:16, B5:16, A6:16, B6:16, A7:16, B7:16, A8:16, B8:16,
    A9:16, B9:16, A10:16, B10:16, A11:16, B11:16, A12:16, B12:16,
    A13:16, B13:16, A14:16, B14:16, A15:16, B15:16, A16:16, B16:16
    >>);
il_16(<<A:16,RestA/binary>>, <<B:16,RestB/binary>>, Acc) ->
  il_16(RestA, RestB, <<Acc/binary,A:16, B:16>>);
il_16(<<>>, <<>>, Acc) -> Acc.

il_32(A, B) when is_binary(A), is_binary(B), size(A) =:= size(B) ->
il_32(A, B, <<>>).

il_32(<<
  A1:16, A2:16, A3:16, A4:16, A5:16, A6:16, A7:16, A8:16,
  A9:16, A10:16, A11:16, A12:16, A13:16, A14:16, A15:16, A16:16,
  A17:16, A18:16, A19:16, A20:16, A21:16, A22:16, A23:16, A24:16,
  A25:16, A26:16, A27:16, A28:16, A29:16, A30:16, A31:16, A32:16,
  RestA/binary>>,
  <<
  B1:16, B2:16, B3:16, B4:16, B5:16, B6:16, B7:16, B8:16,
  B9:16, B10:16, B11:16, B12:16, B13:16, B14:16, B15:16, B16:16,
  B17:16, B18:16, B19:16, B20:16, B21:16, B22:16, B23:16, B24:16,
  B25:16, B26:16, B27:16, B28:16, B29:16, B30:16, B31:16, B32:16,
  RestB/binary>>, Acc) ->
  il_32(RestA, RestB, <<Acc/binary,
    A1:16, B1:16, A2:16, B2:16, A3:16, B3:16, A4:16, B4:16,
    A5:16, B5:16, A6:16, B6:16, A7:16, B7:16, A8:16, B8:16,
    A9:16, B9:16, A10:16, B10:16, A11:16, B11:16, A12:16, B12:16,
    A13:16, B13:16, A14:16, B14:16, A15:16, B15:16, A16:16, B16:16,
    A17:16, B17:16, A18:16, B18:16, A19:16, B19:16, A20:16, B20:16,
    A21:16, B21:16, A22:16, B22:16, A23:16, B23:16, A24:16, B24:16,
    A25:16, B25:16, A26:16, B26:16, A27:16, B27:16, A28:16, B28:16,
    A29:16, B29:16, A30:16, B30:16, A31:16, B31:16, A32:16, B32:16
    >>);
il_32(<<A:16,RestA/binary>>, <<B:16,RestB/binary>>, Acc) ->
  il_32(RestA, RestB, <<Acc/binary,A:16, B:16>>);
il_32(<<>>, <<>>, Acc) -> Acc.

il_64(A, B) when is_binary(A), is_binary(B), size(A) =:= size(B) ->
il_64(A, B, <<>>).

il_64(<<
  A1:16, A2:16, A3:16, A4:16, A5:16, A6:16, A7:16, A8:16,
  A9:16, A10:16, A11:16, A12:16, A13:16, A14:16, A15:16, A16:16,
  A17:16, A18:16, A19:16, A20:16, A21:16, A22:16, A23:16, A24:16,
  A25:16, A26:16, A27:16, A28:16, A29:16, A30:16, A31:16, A32:16,
  A33:16, A34:16, A35:16, A36:16, A37:16, A38:16, A39:16, A40:16,
  A41:16, A42:16, A43:16, A44:16, A45:16, A46:16, A47:16, A48:16,
  A49:16, A50:16, A51:16, A52:16, A53:16, A54:16, A55:16, A56:16,
  A57:16, A58:16, A59:16, A60:16, A61:16, A62:16, A63:16, A64:16,
  RestA/binary>>,
  <<
  B1:16, B2:16, B3:16, B4:16, B5:16, B6:16, B7:16, B8:16,
  B9:16, B10:16, B11:16, B12:16, B13:16, B14:16, B15:16, B16:16,
  B17:16, B18:16, B19:16, B20:16, B21:16, B22:16, B23:16, B24:16,
  B25:16, B26:16, B27:16, B28:16, B29:16, B30:16, B31:16, B32:16,
  B33:16, B34:16, B35:16, B36:16, B37:16, B38:16, B39:16, B40:16,
  B41:16, B42:16, B43:16, B44:16, B45:16, B46:16, B47:16, B48:16,
  B49:16, B50:16, B51:16, B52:16, B53:16, B54:16, B55:16, B56:16,
  B57:16, B58:16, B59:16, B60:16, B61:16, B62:16, B63:16, B64:16,
  RestB/binary>>, Acc) ->
  il_64(RestA, RestB, <<Acc/binary,
    A1:16, B1:16, A2:16, B2:16, A3:16, B3:16, A4:16, B4:16,
    A5:16, B5:16, A6:16, B6:16, A7:16, B7:16, A8:16, B8:16,
    A9:16, B9:16, A10:16, B10:16, A11:16, B11:16, A12:16, B12:16,
    A13:16, B13:16, A14:16, B14:16, A15:16, B15:16, A16:16, B16:16,
    A17:16, B17:16, A18:16, B18:16, A19:16, B19:16, A20:16, B20:16,
    A21:16, B21:16, A22:16, B22:16, A23:16, B23:16, A24:16, B24:16,
    A25:16, B25:16, A26:16, B26:16, A27:16, B27:16, A28:16, B28:16,
    A29:16, B29:16, A30:16, B30:16, A31:16, B31:16, A32:16, B32:16,
    A33:16, B33:16, A34:16, B34:16, A35:16, B35:16, A36:16, B36:16,
    A37:16, B37:16, A38:16, B38:16, A39:16, B39:16, A40:16, B40:16,
    A41:16, B41:16, A42:16, B42:16, A43:16, B43:16, A44:16, B44:16,
    A45:16, B45:16, A46:16, B46:16, A47:16, B47:16, A48:16, B48:16,
    A49:16, B49:16, A50:16, B50:16, A51:16, B51:16, A52:16, B52:16,
    A53:16, B53:16, A54:16, B54:16, A55:16, B55:16, A56:16, B56:16,
    A57:16, B57:16, A58:16, B58:16, A59:16, B59:16, A60:16, B60:16,
    A61:16, B61:16, A62:16, B62:16, A63:16, B63:16, A64:16, B64:16
    >>);
il_64(<<A:16,RestA/binary>>, <<B:16,RestB/binary>>, Acc) ->
  il_64(RestA, RestB, <<Acc/binary,A:16, B:16>>);
il_64(<<>>, <<>>, Acc) -> Acc.

1> c(interleave, [native]).
{ok,interleave}
2> {ok, A} = file:read_file(uniprot_sprot.fasta).
{ok,<<">sp|Q197F8|002R_IIV3 Uncharacterized protein 002R
OS=Invertebrate iridescent virus 3 GN=IIV3-002R PE=4 SV=1\n"...>>}
3> {ok, B} = file:read_file(uniprot_sprot2.fasta).
{ok,<<">sp|Q197F8|002R_IIV3 Uncharacterized protein 002R
OS=Invertebrate iridescent virus 3 GN=IIV3-002R PE=4 SV=1\n"...>>}
6> [{M, 20*size(A)/lists:sum([element(1, timer:tc(interleave, M,
[A,B])) || _<-lists:seq(1,10)])} || M<-[il_16, il_32, il_64]].
[{il_16,181.14907627840208},
 {il_32,193.28636400539335},
 {il_64,184.31082640385935}]
7> c(interleave).
{ok,interleave}
8> [{M, 20*size(A)/lists:sum([element(1, timer:tc(interleave, M,
[A,B])) || _<-lists:seq(1,10)])} || M<-[il_16, il_32, il_64]].
[{il_16,87.1408557475168},
 {il_32,93.51646799197587},
 {il_64,98.28698318757078}]
9> size(A).
242838416

So testing data size was 231MB and achieved performance is almost
200MB/s in native and 100MB/s in byte code which surprised me. All
other so far published implementations are at least order of magnitude
slower. So I would use il_32 implementation.

On Mon, Aug 8, 2011 at 9:23 PM, Joe Armstrong <erlang@REDACTED> wrote:
> How about
>
> i(A,B) -> i(A,B,[]).
>
> i(<<A1,A2,AT/binary>>,<<B1,B2,BT/binary>>,L) ->
>    i(AT, BT, [B2,B1,A2,A1|L]);
> i(<<>>,<<>>, L) ->
>    list_to_binary(lists:reverse(L)).
>
> The good old "build-it-backwards and then reverse it " trick
> O(N) and tail-recursive.
>
>
> /Joe
>
> On Fri, Aug 5, 2011 at 11:26 PM, Bob Cowdery <bob@REDACTED> wrote:
>> Hi
>>
>> I'm wanting to interleave two binaries.
>>
>> Bin1 = <<0,1>>,
>> Bin2 = <<2,3>>,
>> << <<A,B,C,D>> || <<A,B>> <= Bin1, <<C,D>> <= Bin2 >>.
>> <<0,1,2,3>>
>>
>> Bin1 = <<0,1,2,3>>,
>> Bin2 = <<4,5,6,7>>,
>> << <<A,B,C,D>> || <<A,B>> <= Bin1, <<C,D>> <= Bin2 >>.
>> <<0,1,4,5,0,1,6,7,2,3,4,5,2,3,6,7>>
>>
>> whereas I want:
>> <<0,1,4,5,2,3,6,7>>
>>
>> I know what it does is what the documentation says but is there a way to
>> get a pure interleave efficiently. Perhaps there is a filter that would
>> work or a way to reduce the binary after merging without stepping
>> through the whole thing.
>>
>> Regards
>> Bob
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>



-- 
--Hynek (Pichi) Vychodil

Analyze your data in minutes. Share your insights instantly. Thrill
your boss.  Be a data hero!
Try GoodData now for free: www.gooddata.com

More information about the erlang-questions mailing list