Fastest / most efficient random bit indexing in Python

Question

Using Python/Cython, I am trying to construct an efficient way to index boolean values. I have been trying to use the bitarray and/or bitstring packages to construct a fast, non memory intensive way to hold a lot of booleans. My goal was for a list like object that could be sliced as such, and actually managed the bool values in real bits of data:

>>> from bitarray import bitarray
>>> array = bitarray(1000000) # creates 1000000 allocated bits
>>> array.setall(False)
>>> array[4] # holds boolean values
False
>>> from timeit import timeit
>>> timeit(setup = 'from __main__ import array',
           stmt = 'array[500000]')
0.21002184844218164
# one million iterations, making each iteration 210 ns

>>> from bitstring import BitArray
>>> array = BitArray(1000000) # just as we did in the first example
>>> array[6] # all are False by default
False
>>> from timeit import timeit
>>> timeit(setup = 'from __main__ import array',
           stmt = 'array[500000]')
2.6748261753875795
# oh no, this one is very slow, each iteration takes 2674 ns

As you can see, there are already packages that construct this binary data and allow you to index it at random. Would it be possible to get to an even lower level to the RAM myself? 210ns is fast, but I would like to get indexing below 40ns on a 1000000 bit array. How can this be done?

Edit:

Individual item assignment to the boolean array after it is created, would be nice, but it is not required.

Answer 1

What exactly do you want to do with your array of booleans? If you used numpy, you could instantiate your boolean array as an array of uint8 one eighth the size of the boolean array, e.g.

In [38]: a = np.random.randint(256, size=(1000000//8,)).astype(np.uint8)

To extract items, you could do something like:

In [39]: def get_bools(a, i):
   ....:     b = i // 8
   ....:     o = i % 8
   ....:     mask = 1 << o
   ....:     return (a[b] & mask) != 0
   ....:

If you run this to extract a single item, the speed is appalling:

In [40]: idx = 500000

In [41]: %timeit get_bools(a, idx)
100000 loops, best of 3: 4.53 us per loop

But if you do it for 1000 items at once, things look (much) better:

In [42]: idx = np.random.randint(1000000, size=(1000,))

In [43]: %timeit get_bools(a, idx)
10000 loops, best of 3: 31.1 us per loop

Note that the last timing means ~30 ns per item retrieved, right where you wanted to be.

If you need to extract the boolean values one at a time, you are going to have to deal with the painful Python overhead. Notice that simply getting a single item from an array is terribly slow:

In [44]: %timeit a[62500]
10000000 loops, best of 3: 135 ns per loop

But if you can vectorize your code with numpy, or use a C array directly from cython, then you should have no problem in achieving your speed goal.

Answer 2

You may want to look at gmpy2. It provide an experimental integer type called xmpz that supports very fast bit indexing. It is about 3x faster than bitarray on my system.

$ python3 -m timeit -s "from bitarray import bitarray;array=bitarray(1000000);array.setall(False)" "array[500000]"
10000000 loops, best of 3: 0.127 usec per loop
$ python3 -m timeit -s "from gmpy2 import xmpz;array=xmpz(0)" "array[500000]"
10000000 loops, best of 3: 0.0417 usec per loop
$ python3 -m timeit -s "from gmpy2 import xmpz;array=xmpz(0);array[1000001]=1" "array[500000]"
10000000 loops, best of 3: 0.0433 usec per loop

Bit assignments, slicing, and iterating over bits are also supported.

Disclaimer: I maintain gmpy2. The xmpz type was originally created to experiment with mutable numbers (in-place operations actually change the underlying integer without creating a new object). Support for in-place bit manipulation seemed to be a good idea at the time...