[erlang-questions] Basic question about Erlang binaries
Igor Ribeiro Sucupira
Sat Sep 26 08:25:13 CEST 2009
On Sat, Sep 26, 2009 at 1:29 AM, Sean Cribbs <seancribbs@REDACTED> wrote:
> If the position of this bit is constant, I would think so, e.g. for the 33rd
Well... formally, if the bit position is constant, you can access that
position in constant time, even if the access time of an arbitrary
position in an arbitrary Erlang binary is linear. ;-)
Just to state the question more clearly:
Is there a way to retrieve the value of an arbitrary bit position of
an arbitrary Erlang binary in guaranteed constant time?
> <<_:32, Bit:1/integer, _Rest/binary>> = Binary.
That pattern matching never works, as the number of bits in _Rest will
never be a multiple of 8 (so it can never be an Erlang binary).
> I am not certain of the implementation details of binaries, but I believe
> it's simple pointer arithmetic.
>From my tests, it doesn't seem to be. I was doing the pattern matching
<<_:X, Bit:1, _:Y>> = Binary.
Where X + 1 + Y is, of course, the number of bits in Binary (known at
that point, obviously) and X + 1 is the position I want to access.
I also tried something similar to what you did (only making sure I
only picked positions which were at the end of some octet), but in
both cases the pattern matching seems to take linear time with respect
to the desired position.
> If that's the case, then it would be
> proportional to the offset into the binary that you wanted.
If it was just pointer arithmetic, it would be constant (not
proportional to the offset). But, as I said, it doesn't seem to be.
Try this in the shell:
Binary = term_to_binary(lists:seq(1, 1000000)).
lists:foreach(fun(_) -> <<_:7, Bit:1, _/binary>> = Binary end,
lists:foreach(fun(_) -> <<_:1048575, Bit:1, _/binary>> = Binary end,
The second statement takes some seconds to run, while the third one
will take forever (of course I haven't waited :-)).
Thank you for replying.
> How are you
> doing the pattern matching?
> Igor Ribeiro Sucupira wrote:
>> Can I retrieve the value of a specific bit position of an arbitrary
>> Erlang binary in guaranteed constant time?
>> >From some tests I've made, it seems pattern matching to pick a
>> specific bit near the middle of a binary takes linear time with
>> respect to the size of the binary. Is that correct?
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
"The secret of joy in work is contained in one word - excellence. To
know how to do something well is to enjoy it." - Pearl S. Buck.
More information about the erlang-questions