[erlang-questions] Basic question about Erlang binaries

[Igor Ribeiro Sucupira]

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
> bit:

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
like this:

<<_: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:seq(1, 1000000)).
lists:foreach(fun(_) -> <<_:1048575, Bit:1, _/binary>> = Binary end,
lists:seq(1, 1000000)).

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.
Igor.

>  How are you
> doing the pattern matching?
>
> Sean
>
> Igor Ribeiro Sucupira wrote:
>>
>> Hello.
>>
>> 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?
>>
>> Thanks.
>> Igor.
>>
>>
>
>
> ________________________________________________________________
> 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.