Einfache Python Herausforderung: Schnellster bitweise XOR auf Datenpuffer

https://stackoverflow.com/questions/2119761

22-09-2019
|

Frage

Herausforderung:

Führen Sie eine bitweise XOR auf zwei gleich große Puffer. Die Puffer werden benötigt, der Python str Typ sein, da diese für die Datenpuffer in Python traditionell der Typ ist. Bringen Sie den resultierenden Wert als str. Tun Sie dies so schnell wie möglich.

Die Eingänge sind zwei 1 Megabyte (2 ** 20 Byte) Strings.

Die Herausforderung besteht darin, wesentlich schlug meinen ineffizienten Algorithmus mit Python oder bestehende Dritten Python-Modulen (gelockerte Regeln:. Oder Ihr eigenes Modul erstellen). Marginal erhöht sind nutzlos

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)

Lösung

First Try

Mit scipy.weave und SSE2 intrinsics gibt eine marginale Verbesserung. Der erste Aufruf ist ein bisschen langsamer, da der Code von der Festplatte geladen werden muss und zwischengespeichert, nachfolgende Aufrufe sind schneller:

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

Second Try

Unter Berücksichtigung der Kommentare, revisited ich den Code, um herauszufinden, ob das Kopieren vermieden werden könnte. Stellt sich heraus, ich die Dokumentation des String-Objekt falsch gelesen, also hier geht mein zweiter Versuch:

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)

Der Unterschied besteht darin, dass die Zeichenfolge innerhalb des C-Code zugeordnet ist. Es ist unmöglich, es zu einer 16-Byte-Grenze ausgerichtet haben, wie sie durch die SSE2 Anweisungen erforderlich, deshalb wird die nicht ausgerichteten Speicherbereiche am Anfang und das Ende sind byteweise Zugriff kopiert werden.

Die Eingangsdaten werden auf jeden Fall bei der Verwendung numpy Arrays übergeben, weil weave besteht auf dem Kopieren von Python str Objekte std::strings. frombuffer nicht kopiert werden, so dass diese in Ordnung ist, aber der Speicher ist nicht auf 16 Byte ausgerichtet, so dass wir auf dem Einsatz _mm_loadu_si128 anstelle des schnelleren _mm_load_si128 benötigen.

Statt mit _mm_store_si128 verwenden wir _mm_stream_si128, die sicherstellen, dass alle Schreibvorgänge in dem Hauptspeicher gestreamt werden so bald wie möglich --- Auf diese Weise muss das Ausgangsarray nicht wertvolle Cachezeilen aufbrauchen.

Timings

Wie bei den Timings, der slow_xor Eintrag in der ersten Bearbeitung auf meine verbesserte Version bezeichnet (Inline bitweise xor, uint64), entfernte ich diese Verwirrung. slow_xor bezieht sich auf den Code aus der ursprünglichen Frage. Alle Timings sind für 1000 Läufe durchgeführt.

slow_xor: 1.85s (1x)
faster_slow_xor: 1,25 s (1.48x)
inline_xor: 0.95s (1,95x)
inline_xor_nocopy time: 0.32s (5.78x)

Der Code kompiliert wurde mit gcc 4.4.3 und ich habe festgestellt, dass der Compiler tatsächlich die SSE-Befehle verwendet.

Andere Tipps

Performance-Vergleich: 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

Ergebnisse reproduzieren, herunterladen http://gist.github.com/353005 und Typ make (installieren Abhängigkeiten, Typ: sudo apt-get install build-essential python-numpy python-scipy cython gfortran, Abhängigkeiten für Boost.Python, pyublas sind aufgrund nicht enthalten sie manuelle Eingriffe zur Arbeit erfordern)

Dabei gilt:

ist slow_xor() von der Frage des OP
faster_slow_xor(), inline_xor(), inline_xor_nocopy() sind von @Torsten Marek Antwort
cython_xor() und cython_vectorised() sind von @ gnibbler der beantworten

Und xor_$type_sig() sind:

! 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

Es ist aus Python wie folgt verwendet:

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'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<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
}

Es ist aus Python wie folgt verwendet:

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

Hier sind meine Ergebnisse für cython

slow_xor   0.456888198853
faster_xor 0.400228977203
cython_xor 0.232881069183
cython_xor_vectorised 0.171468019485

Vektorisierung in cython Rasuren etwa 25% auf dem for-Schleife auf meinem Computer, aber mehr als die Hälfte der Zeit damit verbracht baute den Python-String (die return-Anweisung) - Ich glaube nicht, die zusätzliche Kopie vermieden werden kann (legal) wie die Array null-Bytes enthalten kann.

Die illegale Art und Weise in einem Python-String zu übergeben wäre und es an Ort und Stelle mutiert und würde die Geschwindigkeit der Funktion verdoppeln.

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]

Eine einfache Speedup ist einen größeren 'Brocken' zu verwenden:

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

mit uint64 auch von numpy natürlich importiert. Ich timeit dies bei 4 Millisekunden vs 6 Millisekunden für die byte Version.

Ihr Problem ist nicht die Geschwindigkeit der NumPy der XOR-Methode, sondern mit all dem Puffern / Datentypkonvertierungen. Persönlich vermute ich, dass der Sinn dieser Stelle kann wirklich zu prahlen Python gewesen sein, denn was machen Sie denn hier ist die Verarbeitung drei Gigabytes von Daten in Zeitrahmen auf einer Stufe mit nicht-interpretierte Sprachen, die sind von Natur aus schneller.

Der Code unten zeigt, dass auch auf meinem bescheidenen Computer Python kann xor "aa" (1MB) und "bb" (1MB) in "c" (1MB) tausend Mal (insgesamt 3 GB) in unter 2 Sekunden . Im Ernst, wie viel Verbesserung wünschen Sie? Vor allem aus einer interpretierten Sprache! 80% der Zeit ruft „frombuffer“ und „tostring“ ausgegeben. Das tatsächliche xor-ing in dem anderen 20% der Zeit abgeschlossen. Bei 3GB in 2 Sekunden, würden Sie hart gedrückt, um auf das zu verbessern im Wesentlichen auch nur mit Hilfe von memcpy in c.

Falls dies war eine echte Frage, und nicht nur verdeckte über Python prahlt, ist die Antwort auf Code, um die Anzahl, Menge und Häufigkeit der Typumwandlungen wie „frombuffer“ und „tostring“ zu minimieren. Die eigentliche XOR-Verknüpfung ist blitzschnell bereits.

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

Wie auch immer, die „test_it2“ oben erfüllt genau die gleiche Menge an XOR-ing als „test_it“ tut, aber in 1/5 der Zeit. 5x Geschwindigkeitsverbesserung sollte als „wesentlich“ qualifizieren, nicht wahr?

Die schnellste bitweise XOR ist "^". Ich kann das Typ viel schneller als "bitwise_xor"; -)

Python3 hat int.from_bytes und int.to_bytes, also:

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 ist schneller als IO, irgendwie schwer zu testen, wie schnell es ist, sieht aus wie 0.018 .. 0.020s auf meiner Maschine. Merkwürdiger "little"-Endian-Umwandlung ist ein wenig schneller.

hat CPython 2.x die zugrunde liegende Funktion _PyLong_FromByteArray, wird es nicht exportiert, sondern erreichbar über ctypes:

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

Python 2 Details sind links als Übung für den Leser.

Wenn Sie schnelle Operationen auf Array-Datentypen tun wollen, dann sollten Sie versuchen, Cython (cython.org). Wenn Sie ihm, die richtigen Erklärungen geben soll es in der Lage sein, um reinen C-Code zu kompilieren nach unten.

Wie stark müssen Sie die Antwort als String? Beachten Sie, dass die c.tostring() Methode muss Kopieren die Daten in c auf eine neue Zeichenfolge, als Python-Strings sind unveränderlich (und c ist wandelbar). Python 2.6 und 3.1 haben einen bytearray Typen, der wie str (bytes in Python 3.x) wirkt mit Ausnahme wandelbar zu sein.

Eine weitere Optimierung ist mit dem out Parameter bitwise_xor angeben, wo das Ergebnis zu speichern.

Auf meinem Rechner bekomme ich

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

mit dem Code am Ende dieses Beitrags. Hinweis insbesondere, dass das Verfahren eines vorab zugeordneten Puffer verwendet, ist doppelt so schnell wie ein neues Objekt zu erzeugen (wenn sie auf 4-Byte (uint64) Chunks in Betrieb). Dies steht im Einklang mit der langsameren Methode tut zwei Operationen pro Chunk (xor + Kopie) an die schneller ist 1 (nur xor).

Auch FWIW, a ^ b entspricht bitwise_xor(a,b) und a ^= b entspricht bitwise_xor(a, b, a).

So, 5x Speedup ohne externe Module schreiben:)

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)

Sie könnten versuchen, die symmetrische Differenz der Bitsets von Salbei.

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

Der schnellste Weg (speedwise) wird, was Max tun. S empfohlen. Implementieren Sie es in C.

Der Stütz Code für diese Aufgabe sollte ziemlich einfach sein, zu schreiben. Es ist nur eine Funktion in einem Modul eine neue Zeichenfolge zu schaffen und die xor tun. Das ist alles. Wenn Sie ein Modul wie das umgesetzt haben, ist es einfach, den Code als Vorlage zu nehmen. Oder Sie nehmen auch ein Modul von jemand anderem ausgeführt, dass Geräte eine einfache Erweiterungsmodul für Python und nur werfen alles nicht für die Aufgabe benötigt werden.

Der eigentliche komplizierte Teil ist einfach, den RefCounter-Stuff richtig zu machen. Aber einmal klar, wie es funktioniert, es ist überschaubar - auch weil die Aufgabe in der Hand wirklich einfach ist. (Zuteilen etwas Speicher und schicken Sie es - params nicht berührt (Ref weise) werden)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow