# 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, skip: 2)
[10, 5, 0, 0, 0, 0, 0, 0, 0, 0]
iex> SimpleBitmap.msb(b, 10, cursor: 38)
[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: 54 s
Benchmarking get msb list...
Benchmarking get msb list skip N...
Benchmarking get msb list with random cursor...
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_get_msb_list_with_random_cursor.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 94140.89 0.0106 ms ±110.23% 0.00900 ms 0.0330 ms
unset random bits 46012.36 0.0217 ms ±57.87% 0.0210 ms 0.0580 ms
load bitmap 2433.74 0.41 ms ±27.38% 0.39 ms 0.72 ms
save bitmap 1132.84 0.88 ms ±41.45% 0.84 ms 1.38 ms
get msb list 651.70 1.53 ms ±14.33% 1.48 ms 2.52 ms
get msb list with random cursor 511.99 1.95 ms ±26.43% 1.84 ms 3.39 ms
get msb list skip N 189.12 5.29 ms ±32.41% 5.35 ms 8.62 ms
population count 74.11 13.49 ms ±5.06% 13.34 ms 16.19 ms
population count 1 50.11 19.96 ms ±3.97% 19.80 ms 23.25 ms
Comparison:
set random bits 94140.89
unset random bits 46012.36 - 2.05x slower
load bitmap 2433.74 - 38.68x slower
save bitmap 1132.84 - 83.10x slower
get msb list 651.70 - 144.46x slower
get msb list with random cursor 511.99 - 183.87x slower
get msb list skip N 189.12 - 497.79x slower
population count 74.11 - 1270.31x slower
population count 1 50.11 - 1878.82x 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.2.0) 94140.89 0.0106 ms ±110.23% 0.00900 ms 0.0330 ms
unset random bits (1.2.0) 46012.36 0.0217 ms ±57.87% 0.0210 ms 0.0580 ms
load bitmap (1.2.0) 2433.74 0.41 ms ±27.38% 0.39 ms 0.72 ms
save bitmap (1.2.0) 1132.84 0.88 ms ±41.45% 0.84 ms 1.38 ms
get msb list (1.2.0) 651.70 1.53 ms ±14.33% 1.48 ms 2.52 ms
get msb list with random cursor (1.2.0) 511.99 1.95 ms ±26.43% 1.84 ms 3.39 ms
get msb list skip N (1.2.0) 189.12 5.29 ms ±32.41% 5.35 ms 8.62 ms
population count (1.2.0) 74.11 13.49 ms ±5.06% 13.34 ms 16.19 ms
population count 1 (1.2.0) 50.11 19.96 ms ±3.97% 19.80 ms 23.25 ms
Comparison:
set random bits (1.2.0) 94140.89
unset random bits (1.2.0) 46012.36 - 2.05x slower
load bitmap (1.2.0) 2433.74 - 38.68x slower
save bitmap (1.2.0) 1132.84 - 83.10x slower
get msb list (1.2.0) 651.70 - 144.46x slower
get msb list with random cursor (1.2.0) 511.99 - 183.87x slower
get msb list skip N (1.2.0) 189.12 - 497.79x slower
population count (1.2.0) 74.11 - 1270.31x slower
population count 1 (1.2.0) 50.11 - 1878.82x 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.3.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.
