Медленные побитовые операции
Я работаю над библиотекой Python, которая выполняет много побитовых операций над длинными битовыми строками, и я хочу найти битовый тип строки, который максимизирует его скорость. Я попробовал встроенный тип Python int, numpy, bitstring и bitarray, и удивительно, что Python int выигрывает, когда дело доходит до побитовых операций. Все, что я гуглил, говорит, что numpy должен быть намного быстрее для векторизованных операций, подобных этому Я использую NumPy неправильно как-то? Есть ли другая библиотека Python, которую я могу использовать, которая на самом деле улучшает встроенный в Python тип int?
from timeit import timeit
import random
size = 10000
def int_to_bits(i):
result = []
for _ in range(size):
result.append(i % 2)
i >>= 1
return result
x = random.randrange(2**size)
y = random.randrange(2**size)
print(x.bit_length(), y.bit_length())
x_bits = int_to_bits(x)
y_bits = int_to_bits(y)
t = timeit(
stmt='a & b',
setup='a = %d; b = %d' % (x, y)
)
print("raw ints:", t)
t = timeit(
stmt='a & b',
setup=('import numpy;'
'a = numpy.array(%r, dtype=int);'
'b = numpy.array(%r, dtype=int)') % (x_bits, y_bits)
)
print('numpy int array:', t)
t = timeit(
stmt='a & b',
setup=('import numpy;'
'a = numpy.array(%r, dtype=bool);'
'b = numpy.array(%r, dtype=bool)') % (x_bits, y_bits)
)
print('numpy bool array:', t)
t = timeit(
stmt='a & b',
setup=('import numpy;'
'a = numpy.packbits(%r);'
'b = numpy.packbits(%r)') % (x_bits, y_bits)
)
print('numpy packed bits:', t)
t = timeit(
stmt='a & b',
setup=('import bitstring;'
'a = bitstring.BitString(%r);'
'b = bitstring.BitString(%r)') % (x_bits, y_bits)
)
print('bitstring:', t)
t = timeit(
stmt='a & b',
setup=('import bitarray;'
'a = bitarray.bitarray(%r);'
'b = bitarray.bitarray(%r)') % (x_bits, y_bits)
)
print('bitarray:', t)
Результаты:
10000 10000
raw ints: 0.29606562735373115
numpy int array: 7.400762747057885
numpy bool array: 1.1108355715984288
numpy packed bits: 1.3064737574273284
bitstring: 380.9796937642803
bitarray: 1.4451143449501842
РЕДАКТИРОВАТЬ:
Похоже, что существует большая путаница в том, как отдельные операции над типами / длинами Python сравнимы с векторными операциями над целыми битовыми массивами. 10 000-битное значение Python int/long, если рассматривать его как битовую маску (используя оператор & точно так же, как мы можем сделать с int или long в C/C++), напрямую сопоставимо с массивом numy bool длиной 10 000, потому что они оба содержат одинаковое количество битов, хотя и представлены двумя разными способами. То же самое верно и для других способов представления 10000 битов, которые я пробовал, включая использование массивов битовых упаковок, массивов int и типов битовых массивов / строк из других библиотек. Все они сравнимы, потому что все они вычисляют одну и ту же функцию на одних и тех же последовательностях битов. Все, что здесь имеет значение, это то, что я могу представить все 10000 бит и что я могу выполнять побитовые операции над ними. Если кто-то может предложить более эффективный способ представления длинных последовательностей битов фиксированной длины, который позволяет использовать побитовые операторы (&, | и ~), это то, что я ищу.
Если вы по-прежнему не понимаете, как значение Python int/long может хранить ту же информацию, что и массив numpy bool или массив int с двоичными значениями, обратитесь к int_to_bits функция в коде выше; он демонстрирует, как извлечь биты из Python int/long, что показывает, что выполнение операции & на двух 10 000-битных целых числах по сути аналогично выполнению его поэлементно в списке или массиве из 10 000 логических значений.
2 ответа
Насколько я могу судить, встроенный Python 3 int это единственный из протестированных вами вариантов, который вычисляет & кусками более одного байта за раз. (Я не совсем понял, что все в исходном коде NumPy для этой операции делает, но не похоже, что он имеет оптимизацию для вычисления этого в блоках больше, чем dtype.)
bitarrayидет побайтово,- попытки bool и 1-bit-per-int NumPy идут постепенно,
- упакованная попытка NumPy идет побайтово, и
-
bitstringИсточник идет побайтово, а также делает некоторые вещи, которые мешают его попыткам набрать скорость через Cython, делая его, безусловно, самым медленным.
В отличие от int операция выполняется с использованием 15-битных или 30-битных цифр, в зависимости от значения параметра времени компиляции PYLONG_BITS_IN_DIGIT, Я не знаю, какая настройка по умолчанию.
Вы можете ускорить попытку NumPy, используя упакованное представление и больший тип d. Похоже, на моей машине 32-битный dtype работает быстрее всего, обойдя Python; Я не знаю, как это на вашей установке. Тестируя со 10240-битными значениями в каждом формате, я получаю
>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160, dtype=num
py.uint64)')
1.3918750826524047
>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160*8, dtype=n
umpy.uint8)')
1.9460716604953632
>>> timeit.timeit('a & b', 'import numpy; a = b = numpy.array([0]*160*2, dtype=n
umpy.uint32)')
1.1728465435917315
>>> timeit.timeit('a & b', 'a = b = 2**10240-1')
1.5999407862400403
Что вы пытаетесь проверить - это вообще векторные операции? Вы просто пытаетесь сравнить скорости 1 операции, и там победит простой python, потому что он не должен настраивать массивы или битовые массивы.
Как насчет попробовать следующее?
x = np.array([random.randrange(2**31)]*1000)
y = np.array([random.randrange(2**31)]*1000)
%timeit x & y # in ipython
%timeit [ a & b for (a,b) in zip(x,y)] # even though x and y are numpy arrays, we are iterating over them - and not doing any vector operations
Интересно, если
xxx = [random.randrange(2**31)] * 1000
yyy = [random.randrange(2**31)] * 1000
а потом
%timeit [a & b for (a,b) in zip(xxx,yyy)]
Чистые списки Python, итерирование по ним быстрее, чем итерирование по пустым массивам... немного противоречит интуиции. Не уверен почему.
Точно так же вы можете попробовать для цепочек битов и битрейров
Это то, что вы смотрите?