Mal zwei schneller als Bitverschiebung, für Python 3.x-Ganzzahlen?

150

Ich habe mir die Quelle der sortierten Container angesehen und war überrascht, diese Zeile zu sehen :

self._load, self._twice, self._half = load, load * 2, load >> 1

Hier loadist eine ganze Zahl. Warum Bitverschiebung an einer Stelle und Multiplikation an einer anderen verwenden? Es erscheint vernünftig, dass die Bitverschiebung schneller ist als die integrale Division durch 2, aber warum nicht auch die Multiplikation durch eine Verschiebung ersetzen? Ich habe die folgenden Fälle verglichen:

  1. (Zeiten teilen)
  2. (Verschiebung, Verschiebung)
  3. (Zeiten, Verschiebung)
  4. (verschieben, teilen)

und festgestellt, dass # 3 durchweg schneller ist als andere Alternativen:

# self._load, self._twice, self._half = load, load * 2, load >> 1

import random
import timeit
import pandas as pd

x = random.randint(10 ** 3, 10 ** 6)

def test_naive():
    a, b, c = x, 2 * x, x // 2

def test_shift():
    a, b, c = x, x << 1, x >> 1    

def test_mixed():
    a, b, c = x, x * 2, x >> 1    

def test_mixed_swapped():
    a, b, c = x, x << 1, x // 2

def observe(k):
    print(k)
    return {
        'naive': timeit.timeit(test_naive),
        'shift': timeit.timeit(test_shift),
        'mixed': timeit.timeit(test_mixed),
        'mixed_swapped': timeit.timeit(test_mixed_swapped),
    }

def get_observations():
    return pd.DataFrame([observe(k) for k in range(100)])

Geben Sie hier die Bildbeschreibung ein Geben Sie hier die Bildbeschreibung ein

Die Frage:

Ist mein Test gültig? Wenn ja, warum ist (multiplizieren, verschieben) schneller als (verschieben, verschieben)?

Ich führe Python 3.5 unter Ubuntu 14.04 aus.

Bearbeiten

Oben ist die ursprüngliche Aussage der Frage. Dan Getz liefert in seiner Antwort eine hervorragende Erklärung.

Der Vollständigkeit halber finden Sie hier Beispielabbildungen für größere, xwenn Multiplikationsoptimierungen nicht zutreffen.

Geben Sie hier die Bildbeschreibung ein Geben Sie hier die Bildbeschreibung ein

hilberts_drinking_problem
quelle
3
Wo hast du definiert x?
JBernardo
3
Ich würde wirklich gerne sehen, ob es einen Unterschied zwischen Little Endian und Big Endian gibt. Wirklich coole Frage übrigens!
LiGhTx117
1
@ LiGhTx117 Ich würde erwarten, dass dies nichts mit den Operationen zu tun hat, es xsei denn, es ist sehr groß, denn das ist nur eine Frage, wie es im Speicher gespeichert ist, oder?
Dan Getz
1
Ich bin neugierig, was ist mit Multiplizieren mit 0,5 anstatt durch 2 zu dividieren? Aufgrund früherer Erfahrungen mit der Programmierung von Mips-Baugruppen führt die Division normalerweise ohnehin zu einer Multiplikationsoperation. (Das würde die Präferenz der Bitverschiebung anstelle der Division erklären)
Sayse
2
@ Sayse, das es in Gleitkomma konvertieren würde. Hoffentlich ist eine ganzzahlige Bodenteilung schneller als eine Rundreise durch Gleitkommazahlen.
Dan Getz

Antworten:

155

Dies scheint darauf zurückzuführen zu sein, dass die Multiplikation kleiner Zahlen in CPython 3.5 so optimiert ist, wie dies bei Linksverschiebungen durch kleine Zahlen nicht der Fall ist. Positive Linksverschiebungen erzeugen immer ein größeres ganzzahliges Objekt, um das Ergebnis als Teil der Berechnung zu speichern. Bei Multiplikationen der in Ihrem Test verwendeten Sortierung wird dies durch eine spezielle Optimierung vermieden und ein ganzzahliges Objekt mit der richtigen Größe erstellt. Dies ist im Quellcode der Ganzzahlimplementierung von Python zu sehen .

Da Ganzzahlen in Python eine beliebige Genauigkeit haben, werden sie als Arrays von ganzzahligen "Ziffern" gespeichert, wobei die Anzahl der Bits pro ganzzahliger Ziffer begrenzt ist. Im allgemeinen Fall sind Operationen mit ganzen Zahlen keine einzelnen Operationen, sondern müssen den Fall mehrerer "Ziffern" behandeln. In pyport.h ist diese Bitbegrenzung als 30 Bit auf einer 64-Bit-Plattform oder ansonsten als 15 Bit definiert. (Ich werde diese 30 von nun an einfach aufrufen, um die Erklärung einfach zu halten. Beachten Sie jedoch, dass das Ergebnis Ihres Benchmarks davon abhängt, ob Sie Python verwenden, das für 32-Bit kompiliert wurdex es weniger als 32.768 beträgt oder nicht .)

Wenn die Ein- und Ausgänge einer Operation innerhalb dieser 30-Bit-Grenze bleiben, kann die Operation anstelle der allgemeinen Methode auf optimierte Weise behandelt werden. Der Beginn der Implementierung der Ganzzahlmultiplikation ist wie folgt:

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit digits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

Wenn Sie also zwei Ganzzahlen multiplizieren, wobei jede in eine 30-Bit-Ziffer passt, erfolgt dies als direkte Multiplikation mit dem CPython-Interpreter, anstatt mit den Ganzzahlen als Arrays zu arbeiten. ( MEDIUM_VALUE()Wird ein positives ganzzahliges Objekt aufgerufen, erhält es einfach seine erste 30-Bit-Ziffer.) Wenn das Ergebnis in eine einzelne 30-Bit-Ziffer passt,PyLong_FromLongLong() wird dies bei einer relativ kleinen Anzahl von Operationen bemerkt und ein einstelliges ganzzahliges Objekt zum Speichern erstellt es.

Im Gegensatz dazu werden Linksverschiebungen nicht auf diese Weise optimiert, und jede Linksverschiebung behandelt die Ganzzahl, die als Array verschoben wird. Insbesondere wenn Sie im Quellcode nachsehen, ob long_lshift()bei einer kleinen, aber positiven Linksverschiebung immer ein zweistelliges ganzzahliges Objekt erstellt wird, wenn die Länge später auf 1 gekürzt werden soll: (meine Kommentare in /*** ***/)

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
    /*** ... ***/

    wordshift = shiftby / PyLong_SHIFT;   /*** zero for small w ***/
    remshift  = shiftby - wordshift * PyLong_SHIFT;   /*** w for small w ***/

    oldsize = Py_ABS(Py_SIZE(a));   /*** 1 for small v > 0 ***/
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;   /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
    z = _PyLong_New(newsize);

    /*** ... ***/
}

Ganzzahlige Division

Sie haben nicht nach der schlechteren Leistung der Ganzzahl-Bodenteilung im Vergleich zu Rechtsschichten gefragt, da dies Ihren (und meinen) Erwartungen entspricht. Das Teilen einer kleinen positiven Zahl durch eine andere kleine positive Zahl ist jedoch auch nicht so optimiert wie kleine Multiplikationen. Jeder //berechnet mit der Funktion sowohl den Quotienten als auch den Rest long_divrem(). Dieser Rest wird für einen kleinen Divisor mit einer Multiplikation berechnet und in einem neu zugewiesenen ganzzahligen Objekt gespeichert , das in dieser Situation sofort verworfen wird.

Dan Getz
quelle
1
Es ist eine interessante Beobachtung mit der Abteilung, danke für den Hinweis. Es versteht sich von selbst, dass dies insgesamt eine hervorragende Antwort ist.
hilberts_drinking_problem
Eine gut recherchierte und schriftliche Antwort auf eine ausgezeichnete Frage. Es könnte interessant sein, Diagramme für das Timing xaußerhalb des optimierten Bereichs anzuzeigen.
Barmar