Ответ 1

Первая попытка

Используя scipy.weave и SSE2 intrinsics дает незначительное улучшение. Первый вызов немного медленнее, так как код нужно загружать с диска и кэшировать, последующие вызовы выполняются быстрее:

import numpy
import time
from os import urandom
from scipy import weave

SIZE = 2**20

def faster_slow_xor(aa,bb):
    b = numpy.fromstring(bb, dtype=numpy.uint64)
    numpy.bitwise_xor(numpy.frombuffer(aa,dtype=numpy.uint64), b, b)
    return b.tostring()

code = """
const __m128i* pa = (__m128i*)a;
const __m128i* pend = (__m128i*)(a + arr_size);
__m128i* pb = (__m128i*)b;
__m128i xmm1, xmm2;
while (pa < pend) {
  xmm1 = _mm_loadu_si128(pa); // must use unaligned access 
  xmm2 = _mm_load_si128(pb); // numpy will align at 16 byte boundaries
  _mm_store_si128(pb, _mm_xor_si128(xmm1, xmm2));
  ++pa;
  ++pb;
}
"""

def inline_xor(aa, bb):
    a = numpy.frombuffer(aa, dtype=numpy.uint64)
    b = numpy.fromstring(bb, dtype=numpy.uint64)
    arr_size = a.shape[0]
    weave.inline(code, ["a", "b", "arr_size"], headers = ['"emmintrin.h"'])
    return b.tostring()

Вторая попытка

Принимая во внимание комментарии, я пересмотрел код, чтобы узнать, можно ли избежать копирования. Оказывается, я неправильно прочитал документацию о строковом объекте, поэтому вот моя вторая попытка:

support = """
#define ALIGNMENT 16
static void memxor(const char* in1, const char* in2, char* out, ssize_t n) {
    const char* end = in1 + n;
    while (in1 < end) {
       *out = *in1 ^ *in2;
       ++in1; 
       ++in2;
       ++out;
    }
}
"""

code2 = """
PyObject* res = PyString_FromStringAndSize(NULL, real_size);

const ssize_t tail = (ssize_t)PyString_AS_STRING(res) % ALIGNMENT;
const ssize_t head = (ALIGNMENT - tail) % ALIGNMENT;

memxor((const char*)a, (const char*)b, PyString_AS_STRING(res), head);

const __m128i* pa = (__m128i*)((char*)a + head);
const __m128i* pend = (__m128i*)((char*)a + real_size - tail);
const __m128i* pb = (__m128i*)((char*)b + head);
__m128i xmm1, xmm2;
__m128i* pc = (__m128i*)(PyString_AS_STRING(res) + head);
while (pa < pend) {
    xmm1 = _mm_loadu_si128(pa);
    xmm2 = _mm_loadu_si128(pb);
    _mm_stream_si128(pc, _mm_xor_si128(xmm1, xmm2));
    ++pa;
    ++pb;
    ++pc;
}
memxor((const char*)pa, (const char*)pb, (char*)pc, tail);
return_val = res;
Py_DECREF(res);
"""

def inline_xor_nocopy(aa, bb):
    real_size = len(aa)
    a = numpy.frombuffer(aa, dtype=numpy.uint64)
    b = numpy.frombuffer(bb, dtype=numpy.uint64)
    return weave.inline(code2, ["a", "b", "real_size"], 
                        headers = ['"emmintrin.h"'], 
                        support_code = support)

Разница в том, что строка выделена внутри кода C. Невозможно выровнять его по 16-байтовой границе, как того требуют инструкции SSE2, поэтому неаудированные области памяти в начале и конце копируются с использованием байтового доступа.

В любом случае входные данные передаются с использованием массивов numpy, потому что weave настаивает на копировании объектов Python str на std::string s. frombuffer не копирует, так что это нормально, но память не выровнена на 16 байт, поэтому нам нужно использовать _mm_loadu_si128 вместо более быстрого _mm_load_si128.

Вместо использования _mm_store_si128 мы используем _mm_stream_si128, который гарантирует, что любые записи будут переданы в основную память как можно скорее. Таким образом, выходной массив не использует ценные строки кеша.

Задержки

Что касается таймингов, запись slow_xor в первом редактировании относится к моей улучшенной версии (встроенная побитовая xor, uint64), я удалил эту путаницу. slow_xor относится к коду из исходных вопросов. Все тайминги выполняются для 1000 прогонов.

• slow_xor: 1.85s (1x)
• faster_slow_xor: 1.25s (1.48x)
• inline_xor: 0.95s (1.95x)
• inline_xor_nocopy: 0.32s (5.78x)

Код был скомпилирован с использованием gcc 4.4.3, и я убедился, что компилятор действительно использует инструкции SSE.

Ответ 2

Сравнение производительности: numpy против Cython против C против Fortran vs. Boost.Python(pyublas)

| function               | time, usec | ratio | type         |
|------------------------+------------+-------+--------------|
| slow_xor               |       2020 |   1.0 | numpy        |
| xorf_int16             |       1570 |   1.3 | fortran      |
| xorf_int32             |       1530 |   1.3 | fortran      |
| xorf_int64             |       1420 |   1.4 | fortran      |
| faster_slow_xor        |       1360 |   1.5 | numpy        |
| inline_xor             |       1280 |   1.6 | C            |
| cython_xor             |       1290 |   1.6 | cython       |
| xorcpp_inplace (int32) |        440 |   4.6 | pyublas      |
| cython_xor_vectorised  |        325 |   6.2 | cython       |
| inline_xor_nocopy      |        172 |  11.7 | C            |
| xorcpp                 |        144 |  14.0 | boost.python |
| xorcpp_inplace         |        122 |  16.6 | boost.python |
#+TBLFM: [email protected]$2/$2;%.1f

Чтобы воспроизвести результаты, загрузите http://gist.github.com/353005 и введите make (для установки зависимостей введите: sudo apt-get install build-essential python-numpy python-scipy cython gfortran, зависимости для Boost.Python, pyublas не включаются из-за необходимости ручного вмешательства в работу)

Где:

• slow_xor() - это вопрос OP
• faster_slow_xor(), inline_xor(), inline_xor_nocopy() из @Torsten Marek ответ
• cython_xor() и cython_vectorised() из @gnibbler answer

И xor_$type_sig():

! xorf.f90.template
subroutine xor_$type_sig(a, b, n, out)
  implicit none
  integer, intent(in)             :: n
  $type, intent(in), dimension(n) :: a
  $type, intent(in), dimension(n) :: b
  $type, intent(out), dimension(n) :: out

  integer i
  forall(i=1:n) out(i) = ieor(a(i), b(i))

end subroutine xor_$type_sig

Используется из Python следующим образом:

import xorf # extension module generated from xorf.f90.template
import numpy as np

def xor_strings(a, b, type_sig='int64'):
    assert len(a) == len(b)
    a = np.frombuffer(a, dtype=np.dtype(type_sig))
    b = np.frombuffer(b, dtype=np.dtype(type_sig))
    return getattr(xorf, 'xor_'+type_sig)(a, b).tostring()

xorcpp_inplace() (Boost.Python, pyublas):

xor.cpp:

#include <inttypes.h>
#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <boost/python.hpp>
#include <pyublas/numpy.hpp>

namespace { 
  namespace py = boost::python;

  template<class InputIterator, class InputIterator2, class OutputIterator>
  void
  xor_(InputIterator first, InputIterator last, 
       InputIterator2 first2, OutputIterator result) {
    // `result` migth `first` but not any of the input iterators
    namespace ll = boost::lambda;
    (void)std::transform(first, last, first2, result, ll::_1 ^ ll::_2);
  }

  template<class T>
  py::str 
  xorcpp_str_inplace(const py::str& a, py::str& b) {
    const size_t alignment = std::max(sizeof(T), 16ul);
    const size_t n         = py::len(b);
    const char* ai         = py::extract<const char*>(a);
    char* bi         = py::extract<char*>(b);
    char* end        = bi + n;

    if (n < 2*alignment) 
      xor_(bi, end, ai, bi);
    else {
      assert(n >= 2*alignment);

      // applying Marek algorithm to align
      const ptrdiff_t head = (alignment - ((size_t)bi % alignment))% alignment;
      const ptrdiff_t tail = (size_t) end % alignment;
      xor_(bi, bi + head, ai, bi);
      xor_((const T*)(bi + head), (const T*)(end - tail), 
           (const T*)(ai + head),
           (T*)(bi + head));
      if (tail > 0) xor_(end - tail, end, ai + (n - tail), end - tail);
    }
    return b;
  }

  template<class Int>
  pyublas::numpy_vector<Int> 
  xorcpp_pyublas_inplace(pyublas::numpy_vector<Int> a, 
                         pyublas::numpy_vector<Int> b) {
    xor_(b.begin(), b.end(), a.begin(), b.begin());
    return b;
  }
}

BOOST_PYTHON_MODULE(xorcpp)
{
  py::def("xorcpp_inplace", xorcpp_str_inplace<int64_t>);     // for strings
  py::def("xorcpp_inplace", xorcpp_pyublas_inplace<int32_t>); // for numpy
}

Используется из Python следующим образом:

import os
import xorcpp

a = os.urandom(2**20)
b = os.urandom(2**20)
c = xorcpp.xorcpp_inplace(a, b) # it calls xorcpp_str_inplace()

Ответ 3

Вот мои результаты для cython

slow_xor   0.456888198853
faster_xor 0.400228977203
cython_xor 0.232881069183
cython_xor_vectorised 0.171468019485

Векторизация в cython бреет около 25% от цикла for на моем компьютере. Однако более половины времени тратится на построение строки python (оператор return) - я не думаю, что дополнительную копию можно избежать ( юридически), поскольку массив может содержать нулевые байты.

Нелегальный способ состоял бы в том, чтобы передать строку Python и изменить его на месте и удвоить скорость функции.

xor.py

from time import time
from os import urandom
from numpy import frombuffer,bitwise_xor,byte,uint64
import pyximport; pyximport.install()
import xor_

def slow_xor(aa,bb):
    a=frombuffer(aa,dtype=byte)
    b=frombuffer(bb,dtype=byte)
    c=bitwise_xor(a,b)
    r=c.tostring()
    return r

def faster_xor(aa,bb):
    a=frombuffer(aa,dtype=uint64)
    b=frombuffer(bb,dtype=uint64)
    c=bitwise_xor(a,b)
    r=c.tostring()
    return r

aa=urandom(2**20)
bb=urandom(2**20)

def test_it():
    t=time()
    for x in xrange(100):
        slow_xor(aa,bb)
    print "slow_xor  ",time()-t
    t=time()
    for x in xrange(100):
        faster_xor(aa,bb)
    print "faster_xor",time()-t
    t=time()
    for x in xrange(100):
        xor_.cython_xor(aa,bb)
    print "cython_xor",time()-t
    t=time()
    for x in xrange(100):
        xor_.cython_xor_vectorised(aa,bb)
    print "cython_xor_vectorised",time()-t

if __name__=="__main__":
    test_it()

xor_.pyx

cdef char c[1048576]
def cython_xor(char *a,char *b):
    cdef int i
    for i in range(1048576):
        c[i]=a[i]^b[i]
    return c[:1048576]

def cython_xor_vectorised(char *a,char *b):
    cdef int i
    for i in range(131094):
        (<unsigned long long *>c)[i]=(<unsigned long long *>a)[i]^(<unsigned long long *>b)[i]
    return c[:1048576]

Ответ 4

Легкое ускорение заключается в использовании большего "куска":

def faster_xor(aa,bb):
    a=frombuffer(aa,dtype=uint64)
    b=frombuffer(bb,dtype=uint64)
    c=bitwise_xor(a,b)
    r=c.tostring()
    return r

с uint64, конечно, также импортируется из numpy. я timeit это на 4 миллисекундах, против 6 миллисекунд для версии byte.

Ответ 5

Ваша проблема заключается не в скорости метода NumPy xOr, а со всеми преобразованиями типа буферизации/данных. Лично я подозреваю, что точка этого сообщения, возможно, действительно заключалась в том, чтобы хвастаться Python, потому что то, что вы здесь делаете, обрабатывает три GIGABYTES данных в таймфреймах наравне с не интерпретируемыми языками, которые по своей природе быстрее.

В приведенном ниже коде показано, что даже на моем скромном компьютере Python может xOr "aa" (1MB) и "bb" (1MB) в "c" (1MB) тысячу раз (всего 3 ГБ) менее чем за две секунды. Серьезно, сколько еще нужно улучшить? Особенно из интерпретируемого языка! 80% времени было потрачено на вызов "frombuffer" и "tostring". Фактическое xOr-ing завершается в других 20% случаев. При 3 ГБ за 2 секунды вам будет трудно улучшить это, по сути, даже используя memcpy в c.

В случае, если это был реальный вопрос, а не просто скрытое хвастовство о Python, ответ заключается в том, чтобы свести к минимуму количество, количество и частоту ваших преобразований типов, таких как "frombuffer" и "tostring". Фактическое xOr'ing уже молниеносно.

from os import urandom
from numpy import frombuffer,bitwise_xor,byte,uint64

def slow_xor(aa,bb):
    a=frombuffer(aa,dtype=byte)
    b=frombuffer(bb,dtype=byte)
    c=bitwise_xor(a,b)
    r=c.tostring()
    return r

bb=urandom(2**20)
aa=urandom(2**20)

def test_it():
    for x in xrange(1000):
    slow_xor(aa,bb)

def test_it2():
    a=frombuffer(aa,dtype=uint64)
    b=frombuffer(bb,dtype=uint64)
    for x in xrange(1000):
        c=bitwise_xor(a,b);
    r=c.tostring()    

test_it()
print 'Slow Complete.'
#6 seconds
test_it2()
print 'Fast Complete.'
#under 2 seconds

В любом случае, "test_it2" выше выполняет точно такое же количество xOr-ing, что и "test_it", но в 1/5 раза. 5-кратное повышение скорости должно квалифицироваться как "существенное", нет?

Ответ 6

Самый быстрый побитовый XOR - "^". Я могу набрать это гораздо быстрее, чем "bitwise_xor"; -)

Ответ 7

Python3 имеет int.from_bytes и int.to_bytes, таким образом:

x = int.from_bytes(b"a" * (1024*1024), "big")
y = int.from_bytes(b"b" * (1024*1024), "big")
(x ^ y).to_bytes(1024*1024, "big")

Это быстрее, чем IO, как бы трудно проверить, насколько быстро это выглядит, выглядит как 0.018.. 0.020s на моей машине. Странно "little" -endian преобразование немного быстрее.

CPython 2.x имеет базовую функцию _PyLong_FromByteArray, она не экспортируется, а доступна через ctypes:

In [1]: import ctypes
In [2]: p = ctypes.CDLL(None)
In [3]: p["_PyLong_FromByteArray"]
Out[3]: <_FuncPtr object at 0x2cc6e20>

Детали Python 2 остаются в виде упражнения для читателя.

Ответ 8

Если вы хотите выполнять быстрые операции с типами данных массива, вы должны попробовать Cython (cython.org). Если вы дадите ему правильные объявления, он должен будет скомпилировать до чистого кода c.

Ответ 9

Насколько вам нужен ответ в виде строки? Обратите внимание, что метод c.tostring() должен копировать данные в c в новую строку, поскольку строки Python неизменяемы (и c изменяет). Python 2.6 и 3.1 имеют тип bytearray, который действует как str (bytes в Python 3.x), за исключением того, что он изменен.

Другая оптимизация использует параметр out для bitwise_xor, чтобы указать, где хранить результат.

На моей машине я получаю

slow_xor (int8): 5.293521 (100.0%)
outparam_xor (int8): 4.378633 (82.7%)
slow_xor (uint64): 2.192234 (41.4%)
outparam_xor (uint64): 1.087392 (20.5%)

с кодом в конце этого сообщения. Обратите внимание, в частности, что метод с использованием предварительно распределенного буфера в два раза быстрее, чем создание нового объекта (при работе с 4-байтовыми (uint64) фрагментами). Это согласуется с более медленным методом, выполняющим две операции на кусок (xor + copy) до более быстрого 1 (просто xor).

Кроме того, FWIW, a ^ b эквивалентен bitwise_xor(a,b), а a ^= b эквивалентен bitwise_xor(a, b, a).

Итак, 5-кратное ускорение без написания каких-либо внешних модулей:)

from time import time
from os import urandom
from numpy import frombuffer,bitwise_xor,byte,uint64

def slow_xor(aa, bb, ignore, dtype=byte):
    a=frombuffer(aa, dtype=dtype)
    b=frombuffer(bb, dtype=dtype)
    c=bitwise_xor(a, b)
    r=c.tostring()
    return r

def outparam_xor(aa, bb, out, dtype=byte):
    a=frombuffer(aa, dtype=dtype)
    b=frombuffer(bb, dtype=dtype)
    c=frombuffer(out, dtype=dtype)
    assert c.flags.writeable
    return bitwise_xor(a, b, c)

aa=urandom(2**20)
bb=urandom(2**20)
cc=bytearray(2**20)

def time_routine(routine, dtype, base=None, ntimes = 1000):
    t = time()
    for x in xrange(ntimes):
        routine(aa, bb, cc, dtype=dtype)
    et = time() - t
    if base is None:
        base = et
    print "%s (%s): %f (%.1f%%)" % (routine.__name__, dtype.__name__, et,
        (et/base)*100)
    return et

def test_it(ntimes = 1000):
    base = time_routine(slow_xor, byte, ntimes=ntimes)
    time_routine(outparam_xor, byte, base, ntimes=ntimes)
    time_routine(slow_xor, uint64, base, ntimes=ntimes)
    time_routine(outparam_xor, uint64, base, ntimes=ntimes)

Ответ 10

Вы можете попробовать симметричную разницу в битах набора шага.

http://www.sagemath.org/doc/reference/sage/misc/bitset.html

Ответ 11

Самый быстрый способ (по скорости) будет делать то, что Макс. S рекомендуется. Реализуйте его в C.

Вспомогательный код для этой задачи должен быть довольно простым для записи. Это всего лишь одна функция в модуле, создающем новую строку и выполняющая xor. Все это. Когда вы реализовали один такой модуль, просто взять код в качестве шаблона. Или вы даже берете модуль, реализованный от кого-то другого, который реализует простой модуль повышения для Python и просто выбрасывает все, что не нужно для вашей задачи.

Реальная сложная часть - это просто, правильная настройка RefCounter-Stuff. Но однажды понял, как это работает, это управляемо - также, поскольку задача под рукой очень проста (выделить некоторую память и вернуть ее), параметры не должны касаться (Ref-wise)).