2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The point is that getting a single item from a list or array, and wrapping it into a Python object to return it to you, already takes over 100ns... So you are never going to achieve your stated goal. You need to either work at the C level (Cython), or run many operations in a single Python call (NumPy). If you outlined your algorithm in more detail, we would be able to provide more help. Also, this question seems a better fit for StackOverflow. \$\endgroup\$ – Jaime Jun 1 '14 at 17:11
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ AHAA! I had gmpy2 installed on my machine, for use with prime numbers, but I never even thought that it supported bitwise manipulation, thanks! \$\endgroup\$ – Nick Pandolfi Jun 3 '14 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.