How to efficiently set one bit at a time in an Erlang binary whithout going imperative?

Question

As an exercise I am working on a parallel implementation of the Sieve of Eratosthenes. As part of that I am implementing a sequence of bitmaps, using one bit per number to save memory. Reading bits one at a time appear to work fine, but setting them is slow, especially when I use large binaries.

getBit(Bin, N, Size)->
    R=Size-N-1,
    <<_:N,Bit:1,_:R>> = Bin,
    Bit.

setBit(Bin, N, Size)->
    R=Size-N-1,
    <<A:N,_:1,B:R>> = Bin,
    <<A:N,1:1,B:R>>.

Is there a way to do this well in functional Erlang, perhaps similar to how Arrays work? I have read about hipe_bifs:bytearray_update but would prefer to keep my coding style functional.

Answer 1

Generally one can not do it better then with complexity of O(log(n)) for both get and set operations, since Erlang is functional language. You can archive O(log(n)) using some type of trees. array, dict, gb_trees and gb_sets modules does this.

So if you need to make it as fast as possible you have to go imperative - you could try hipe_bifs module, process dictionary and ets tables.

Answer 2

You can store your bitmaps as integers (if they are not longer than ~1000 bits):

-module(z).
-export([get_bit/2, set_bit/2]).

get_bit(N, B) -> N band bit_to_int(B) > 0.
set_bit(N, B) -> N bor bit_to_int(B).

bit_to_int(B) -> 1 bsl B.

---

You might try your version w/o passing the Size, and padding to bytes:

getBit(Bin, N)->
    <<_:N/bitstring,Bit:1,_/bitstring>> = Bin,
    Bit.

setBit(Bin, N)->
    <<A:N,_:1,B/bitstring>> = Bin,
    <<A:N,1:1,B>>.

%OR:
setBit(Bin, N)->
    PSize = 8 - ((N + 1) rem 8),
    <<A:N,_:1, Pad:PSize,B/bytes>> = Bin,
    <<A:N,1:1,Pad:PSize,B>>.

Can be better or worse :-)