README.md

# Simple Bitmap

Simple bitmap is to provide very basic functionality for a bitmap, which allows to set arbitrary bits (within system limit), check the membership and get the index of the MSB (most significant bit).

## Usage

Below code illustrates typical use cases for the simple bitmap:

```elixir
iex> b = SimpleBitmap.new()
%SimpleBitmap{data: 0}
iex> b = SimpleBitmap.set(b, 5)
%SimpleBitmap{data: 32}
iex> b = SimpleBitmap.set(b, 10)
%SimpleBitmap{data: 1056}
iex> b = SimpleBitmap.set(b, 38)
%SimpleBitmap{data: 274877908000}
iex> b = SimpleBitmap.set(b, 179)
%SimpleBitmap{data: 766247770432944429179173513575154591809369835969709088}
iex> SimpleBitmap.msb(b)
179
iex> SimpleBitmap.msb(b, 10)
[179, 38, 10, 5, 0, 0, 0, 0, 0, 0]
iex> SimpleBitmap.msb(b, 10, 2)
[10, 5, 0, 0, 0, 0, 0, 0, 0, 0]
iex> SimpleBitmap.popcount(b)
4
```

If you'd know more, just look into the test cases and the source code itself. After all, the whole code is just < 200 LOC.

## Performance

We use [benchee](https://github.com/PragTob/benchee) to do the performance benchmark. The bitmap size is 1M bits. Here's the result for 1.0.0:

```bash
$ make bench
Benchmark the simple bitmap...
Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.8.1
Erlang 21.2.4

Benchmark suite executing with the following configuration:
warmup: 1 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 48 s


Benchmarking get msb list...
Benchmarking get msb list skip N...
Benchmarking load bitmap...
Benchmarking population count...
Benchmarking population count 1...
Benchmarking save bitmap...
Benchmarking set random bits...
Benchmarking unset random bits...
Generated benchmarks/output/bitmap.html
Generated benchmarks/output/bitmap_comparison.html
Generated benchmarks/output/bitmap_get_msb_list.html
Generated benchmarks/output/bitmap_get_msb_list_skip_n.html
Generated benchmarks/output/bitmap_load_bitmap.html
Generated benchmarks/output/bitmap_population_count.html
Generated benchmarks/output/bitmap_population_count_1.html
Generated benchmarks/output/bitmap_save_bitmap.html
Generated benchmarks/output/bitmap_set_random_bits.html
Generated benchmarks/output/bitmap_unset_random_bits.html

Name                          ips        average  deviation         median         99th %
set random bits          104.89 K     0.00953 ms   ±109.89%     0.00799 ms      0.0300 ms
unset random bits         48.05 K      0.0208 ms    ±61.20%      0.0200 ms      0.0570 ms
load bitmap                2.91 K        0.34 ms    ±15.75%        0.34 ms        0.54 ms
save bitmap                1.21 K        0.83 ms    ±12.19%        0.81 ms        1.12 ms
get msb list               0.68 K        1.48 ms     ±9.02%        1.46 ms        1.99 ms
get msb list skip N       0.194 K        5.14 ms    ±35.02%        5.13 ms        8.82 ms
population count         0.0762 K       13.13 ms     ±9.77%       12.93 ms       17.52 ms
population count 1       0.0526 K       19.02 ms     ±4.95%       18.86 ms       22.61 ms

Comparison:
set random bits          104.89 K
unset random bits         48.05 K - 2.18x slower
load bitmap                2.91 K - 36.09x slower
save bitmap                1.21 K - 86.94x slower
get msb list               0.68 K - 155.28x slower
get msb list skip N       0.194 K - 539.59x slower
population count         0.0762 K - 1377.02x slower
population count 1       0.0526 K - 1994.62x slower
Suite saved in external term format at benchmarks/benchee/bitmap.benchee
Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.8.1
Erlang 21.2.4

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 0 ns



Name                                  ips        average  deviation         median         99th %
set random bits (1.1.0)          104.89 K     0.00953 ms   ±109.89%     0.00799 ms      0.0300 ms
unset random bits (1.1.0)         48.05 K      0.0208 ms    ±61.20%      0.0200 ms      0.0570 ms
load bitmap (1.1.0)                2.91 K        0.34 ms    ±15.75%        0.34 ms        0.54 ms
save bitmap (1.1.0)                1.21 K        0.83 ms    ±12.19%        0.81 ms        1.12 ms
get msb list (1.1.0)               0.68 K        1.48 ms     ±9.02%        1.46 ms        1.99 ms
get msb list skip N (1.1.0)       0.194 K        5.14 ms    ±35.02%        5.13 ms        8.82 ms
population count (1.1.0)         0.0762 K       13.13 ms     ±9.77%       12.93 ms       17.52 ms
population count 1 (1.1.0)       0.0526 K       19.02 ms     ±4.95%       18.86 ms       22.61 ms

Comparison:
set random bits (1.1.0)          104.89 K
unset random bits (1.1.0)         48.05 K - 2.18x slower
load bitmap (1.1.0)                2.91 K - 36.09x slower
save bitmap (1.1.0)                1.21 K - 86.94x slower
get msb list (1.1.0)               0.68 K - 155.28x slower
get msb list skip N (1.1.0)       0.194 K - 539.59x slower
population count (1.1.0)         0.0762 K - 1377.02x slower
population count 1 (1.1.0)       0.0526 K - 1994.62x slower
```

Benchmark code is in [benchmarks/bitmap.exs](./benchmarks/bitmap.exs).

## Installation

The package can be installed by adding `simple_bitmap` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:simple_bitmap, "~> 1.0.0"}
  ]
end
```

## Caveats

If your bitmap size is > 10M and < 30M, please modify the benchmark script (change `max_index` to 10000000) and redo the benchmark. Please expect performance drop and see if the metrics are still good for your use case.

If you want a bitmap size > 30M, as for now this solution doesn't work due to system limit:

```elixir
iex(1)> b = SimpleBitmap.new()
%SimpleBitmap{data: 0}
iex(2)> SimpleBitmap.set(b, 33000000); :ok
:ok
iex(3)> SimpleBitmap.set(b, 34000000); :ok
** (SystemLimitError) a system limit has been reached
    (simple_bitmap) lib/simple_bitmap.ex:154: SimpleBitmap.do_set/2
```

A simple solution/workaround to that is to put a list of integers in the `data` field of the bitmap.