base64 encoding using the new binary syntax

Bjorn Gustavsson <>
Tue Sep 26 18:15:53 CEST 2000


 writes:

> Bjorn Gustavsson writes:
> 
>  > The bit syntax as currently implemented always copies binaries
>  > in construction expressions such as:
>  > 
>  > 	<<Acc/binary, P:6, Q:6, R:6, S:6>>
> 
> Interesting. Maybe it'd be useful to add a few lines to the online
> manual (http://www.erlang.org/doc/r7a/doc/extensions/part_frame.html)
> about performance---I'd been assuming that all the assertions made in
> Tony and Klacke's original paper were true, e.g. they guarantee O(1)
> concatenation. Now that I think about it, I remember someone saying
> that "segmented binaries" hadn't been implemented, so I should have known.

There are some information about performance issues in the bit syntax 
documentation in R7B.

> 
> So, I think it's now something like:
> 
> Operation                       big-O     Notes
> ----------------------------------------------------------------------
> <<A:N/binary, B:M/binary>>.     O(M + N)  i.e. it copies

Correct.

> <<A:N/binary, B:M/binary>> = X. O(M + N)  if this also copies, otherwise O(1)

In matching, byte-aligned binaries are not copied. They are split using a sub binary.
The sub binary object contains a reference to the original binary, the starting
position in it and the length.

Non-aligned binaries as in

	<<_:3, A:N/binary, _:5>> = X,
	A.

are copied into a new binary. (There will be no copy if A is not used later
in the function.)

> <<_:N/binary, B:M/binary>> = X. O(M)      just guessing, O(1) if the above is
> <<A:N/binary, _:M/binary>> = X. O(N)      just guessing, ditto

Yes, O(1).

Actually, as your examples are written, neither A nor B will be used after the
match, so no sub binaries will be created. Basically your examples
just verify that

	size(X) == N+M

> 
> The other thing which might be worth mentioning in the "what was
> dropped" section is case-insensitve string matching. 
> 
> Updated performance:
> 
>               Matthias bitsyntax      Björn bitsyntax	'mimencode' program
>     -------------------------------------------------------------------
>     encoding: 1.07 s                  0.33s		0.045s
>     decoding: 10.2 s                  0.75s		0.035s

The difference between our versions will increase if you run it on
larger files.

>   
> That seems reasonable.
> 
> Matthias
> 

/Bjorn

-- 
Björn Gustavsson            Ericsson Utvecklings AB
      ÄT2/UAB/F/P
			    BOX 1505
+46 8 727 56 87 	    125 25 Älvsjö



More information about the erlang-questions mailing list