Desafío de Python simple: el XOR de Bitwise más rápido en buffers de datos

Reto:

Realice un XOR a nivel de bits en dos búferes de igual tamaño. Se requerirá que los buffers sean del tipo str python ya que este es tradicionalmente el tipo para buffers de datos en python. Devuelve el valor resultante como un str . Haz esto lo más rápido posible.

Las entradas son dos cadenas de 1 megabyte (2 ** 20 bytes).

El desafío es vencer sustancialmente mi algoritmo ineficiente usando Python o módulos de Python de terceros existentes (reglas relajadas: o crear su propio módulo). Los aumentos marginales son inútiles.

 from os import urandom from numpy import frombuffer,bitwise_xor,byte 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 aa=urandom(2**20) bb=urandom(2**20) def test_it(): for x in xrange(1000): slow_xor(aa,bb) 

    Related of "Desafío de Python simple: el XOR de Bitwise más rápido en buffers de datos"

    Primer bash

    El uso de scipy.weave y SSE2 intrinsics da una mejora marginal. La primera invocación es un poco más lenta ya que el código debe cargarse desde el disco y almacenarse en caché, las invocaciones posteriores son más rápidas:

     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() 

    Segundo bash

    Teniendo en cuenta los comentarios, volví a visitar el código para averiguar si se podía evitar la copia. Resulta que leí mal la documentación del objeto de cadena, así que aquí va mi segundo bash:

     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) 

    La diferencia es que la cadena está asignada dentro del código C. Es imposible que se alinee en un límite de 16 bytes como lo requieren las instrucciones del SSE2, por lo tanto, las regiones de memoria no alineadas al principio y al final se copian utilizando el acceso de bytes.

    Los datos de entrada se entregan utilizando matrices numpy de todos modos, porque el weave insiste en copiar los objetos str Python a std::string s. frombuffer no se copia, por lo que está bien, pero la memoria no está alineada a 16 bytes, por lo que necesitamos usar _mm_loadu_si128 lugar del más rápido _mm_load_si128 .

    En lugar de usar _mm_store_si128 , usamos _mm_stream_si128 , lo que asegurará que todas las escrituras se transmitan a la memoria principal tan pronto como sea posible, de esta manera, la matriz de salida no usa las valiosas líneas de caché.

    Tiempos

    En cuanto a los tiempos, la entrada de slow_xor en la primera edición se refirió a mi versión mejorada (en línea en forma de bits xor, uint64 ), uint64 esa confusión. slow_xor refiere al código de las preguntas originales. Todos los tiempos se realizan para 1000 carreras.

    • 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)

    El código se compiló usando gcc 4.4.3 y he verificado que el comstackdor realmente usa las instrucciones SSE.

    Comparación de rendimiento: numpy vs. Cython vs. C vs. 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: $3=@2$2/$2;%.1f 

    Para reproducir los resultados, descargue http://gist.github.com/353005 y escriba make (para instalar dependencias, escriba: sudo apt-get install build-essential python-numpy python-scipy cython gfortran , dependencias para Boost.Python , pyublas No se incluyen debido a que requieren intervención manual para funcionar.

    Dónde:

    • slow_xor() es de la pregunta del OP
    • faster_slow_xor() , inline_xor() , inline_xor_nocopy() son de la respuesta de @Torsten Marek
    • cython_xor() y cython_vectorised() son de la respuesta de @ gnibbler

    Y xor_$type_sig() son:

     ! 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 

    Se usa desde Python de la siguiente manera:

     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  #include  #include  #include  #include  namespace { namespace py = boost::python; template 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 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(a); char* bi = py::extract(b); char* end = bi + n; if (n < 2*alignment) xor_(bi, end, ai, bi); else { assert(n >= 2*alignment); // applying Marek's 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 pyublas::numpy_vector xorcpp_pyublas_inplace(pyublas::numpy_vector a, pyublas::numpy_vector b) { xor_(b.begin(), b.end(), a.begin(), b.begin()); return b; } } BOOST_PYTHON_MODULE(xorcpp) { py::def("xorcpp_inplace", xorcpp_str_inplace); // for strings py::def("xorcpp_inplace", xorcpp_pyublas_inplace); // for numpy } 

    Se usa desde Python de la siguiente manera:

     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() 

    Aquí están mis resultados para cython

     slow_xor 0.456888198853 faster_xor 0.400228977203 cython_xor 0.232881069183 cython_xor_vectorised 0.171468019485 

    La vectorización en cython elimina aproximadamente el 25% del bucle for en mi computadora. Sin embargo, más de la mitad del tiempo se invierte en construir la cadena de python (la statement de return ). No creo que la copia adicional pueda ser evitada (legalmente) como la matriz puede contener bytes nulos.

    La forma ilegal sería pasar una cadena de Python y mutarla en su lugar y duplicar la velocidad de la función.

    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): (c)[i]=(a)[i]^(b)[i] return c[:1048576] 

    Una aceleración fácil es usar un ‘trozo’ más grande:

     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 

    con uint64 también importado de numpy por supuesto. Lo timeit en 4 milisegundos, frente a 6 milisegundos para la versión en byte .

    Su problema no es la velocidad del método xOr de NumPy, sino más bien con todas las conversiones de tipos de datos / búferes. Personalmente, sospecho que el punto de esta publicación puede haber sido realmente jactarse de Python, porque lo que está haciendo aquí es procesar TRES GIGABITAS de datos en marcos de tiempo a la par con lenguajes no interpretados, que son intrínsecamente más rápidos.

    El siguiente código muestra que, incluso en mi humilde computadora, Python puede xOr “aa” (1MB) y “bb” (1MB) en “c” (1MB) mil veces (total 3GB) en menos de dos segundos . En serio, ¿cuánto más quieres mejorar? ¡Especialmente de un lenguaje interpretado! El 80% del tiempo se invirtió en llamar a “frombuffer” y “tostring”. El xOringing real se completa en el otro 20% del tiempo. Con 3GB en 2 segundos, sería difícil mejorar eso sustancialmente solo con el uso de memcpy en c.

    En caso de que se tratara de una pregunta real, y no solo de alardear de Python, la respuesta es codificar para minimizar el número, la cantidad y la frecuencia de las conversiones de tipo, como “frombuffer” y “tostring”. El xOr’ing real ya es muy rápido.

     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 

    De todos modos, el “test_it2” anterior logra exactamente la misma cantidad de xOr-ing que “test_it”, pero en 1/5 del tiempo. La mejora de velocidad 5x debe calificar como “sustancial”, ¿no?

    El XOR a nivel de bits más rápido es “^”. Puedo escribir mucho más rápido que “bitwise_xor” 😉

    Python3 tiene int.from_bytes e int.to_bytes , por lo tanto:

     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") 

    Es más rápido que IO, un poco difícil de probar qué tan rápido es, se ve como 0.018 .. 0.020s en mi máquina. Extrañamente la "little" conversión endiana es un poco más rápida.

    CPython 2.x tiene la función subyacente _PyLong_FromByteArray , no se exporta pero se puede acceder a través de ctypes:

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

    Los detalles de Python 2 se dejan como ejercicio para el lector.

    Si desea realizar operaciones rápidas en tipos de datos de matriz, debe probar Cython (cython.org). Si le das las declaraciones correctas, debería poder comstackr hasta el código C puro.

    ¿Qué tanto necesita la respuesta como una cadena? Tenga en cuenta que el método c.tostring() tiene que copiar los datos en c a una nueva cadena, ya que las cadenas de Python son inmutables ( c es mutable). Python 2.6 y 3.1 tienen un tipo de bytearray , que actúa como str ( bytes en Python 3.x) excepto por ser mutable.

    Otra optimización es usar el parámetro out para bitwise_xor para especificar dónde almacenar el resultado.

    En mi maquina me sale

     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%) 

    Con el código al final de este post. Tenga en cuenta, en particular, que el método que utiliza un búfer preasignado es dos veces más rápido que crear un nuevo objeto (cuando se opera en trozos de 4 bytes ( uint64 )). Esto es consistente con el método más lento haciendo dos operaciones por porción (xor + copia) al 1 (solo xor) del más rápido.

    Además, FWIW, a ^ b es equivalente a bitwise_xor(a,b) , y a ^= b es equivalente a bitwise_xor(a, b, a) .

    Entonces, 5x de aceleración sin escribir ningún módulo externo 🙂

     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) 

    Podrías probar la diferencia simétrica de los bitsets de sage.

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

    La forma más rápida (en el sentido de la velocidad) será hacer lo que Max. S recomendado. Implementarlo en C.

    El código de soporte para esta tarea debe ser bastante simple de escribir. Es solo una función en un módulo que crea una nueva cadena y hace el xor. Eso es todo. Cuando haya implementado un módulo como ese, es sencillo tomar el código como plantilla. O incluso toma un módulo implementado de otra persona que implementa un módulo de mejora simple para Python y simplemente tira todo lo que no es necesario para su tarea.

    La parte realmente complicada es simplemente hacer lo correcto con RefCounter-Stuff. Pero una vez que se dio cuenta de cómo funciona, es manejable, también porque la tarea en cuestión es realmente simple (asigne un poco de memoria y devuélvala), no se deben tocar los parámetros (ref.).