Eine CPU ist kein Zauberkasten, der Wunder vollbringen kann, sondern eine CPU muss genauso die Aufgaben mithilfe gewisser Grundbausteine und Algorithmen lösen. Für die CPU sind die Grundbausteine sogenannte Logikgatter, die bestimmte logische Operationen wie AND, OR, NOT umsetzen, weil diese Operationen mithilfe physikalischer Effekte in Transistoren nachgebaut werden können. Aus diesen Bausteinen für einen oder zwei Operanden entstehen dann komplexere Bausteine: Eine Addition von zwei Bits lässt sich zum Beispiel mit einem XOR für das Ergebnis und einem AND für den Überlauf umsetzen. Verschaltet man wiederum mehrere dieser Volladdierer lässt sich eine Addition von 64 Bits konstruieren, die dann für die Addition zweier Zahlen genutzt werden kann.

Die Multiplikation ist auch für Computer keine Grundoperation, sondern eine fortgesetzte Addition, oder umgekehrt ausgedrückt: wird die Multiplikation auf mehrere Additionsschritte zurückgeführt. In einem Video über »altes Multiplizieren« bin ich auf ein Verfahren gestoßen, dass mich sofort an Computer erinnert hat: Um zwei Zahlen zu multiplizieren, halbiert man jeweils die eine und verdoppelt die andere. Aus dieser Reihe von verdoppelten Zahlen streicht man all jene, in denen der andere Faktor gerade war, und bildet die Summe der verbliebenen Zahlen, die dem Produkt der beiden Zahlen entspricht.

Die Stichwörter halbieren, verdoppeln und gerade schreien förmlich nach einem Computer, da dieser aufgrund des Binärsystems sehr leicht diese Operationen durchführen kann:

ein Verdoppeln entspricht einer Verschiebung der Zahl nach links; x << n
ein Halbieren entspricht einer Verschiebung der Zahl nach rechts; x >> n
der Test auf ungerade (oder gerade) kann einfach durch die Prüfung des niederwertigsten Bits erfolgen; x & 1 == 1

Der Algorithmus für a * b ist damit leicht formuliert:

let mut res = 0;

while a > 0 {
    a = a >> 1;
    b = b << 1;
    if a & 1 == 1 {
        res += b;
    }
}

Schiebeoperationen lassen sich leicht in Hardware umsetzen, indem man die Leitungen des Eingangs entsprechend mit denen des Ausgangs um eine Stelle versetzt verschaltet. Der obige Algorithmus enthält also bis auf die Prüfung auf größer Null (bzw. ungleich Null) nur primitive Operationen.

Und mit einem kleinen Test zeigt sich, dass die Berechnung auch stimmt:

#[test]
fn test_shift() {
    assert_eq!(12 * 31, shift_mul(12, 31));
    assert_eq!(5 * 4, shift_mul(5, 4));
}

Geschwindigkeitsanalyse – Benchmarking

Jetzt war meine Frage, wie schnell denn der Algorithmus ist. Hierfür ist das klassische Mittel ein Benchmarking, für das Rust mit cargo bench die entsprechende Unterstützung bietet. Im Code muss man die Funktionalität test aktivieren und das Paket test1 einbinden. Damit kann man dann Funktionen definieren, die für die Geschwindigkeitsanalyse genutzt werden ähnlich wie die Testfunktionen. Diese Funktionen müssen mit dem Attribut bench markiert werden und einen Parameter vom Typ test::Bencher verwenden:

Das Paket test kommt mit Rust mit und muss nicht mit cargo add eingebunden werden. ↩

#![feature(test)]

extern crate test;

use test::{black_box, Bencher};

#[bench]
fn bench_shift(b: &mut Bencher) {
    b.iter(|| {
        for _ in 0..1000 {
            black_box(shift_mul(5, 4));
        }
    });
}

Ungünstig für der Analyse ist, dass der Compiler den Code optimiert. Er erkennt nämlich, dass das Ergebnis der Berechnung gar nicht genutzt wird und entfernt daher die gesamte Berechnung. Somit ist die Ausführungszeit immer 0 ns. Daher muss man die Berechnung der Funktion mit black_box kennzeichnen, damit sie bei der Optimierung nicht entfernt wird.

Das Ergebnis

Als Vergleich habe ich noch eine Funktion mit der üblichen Multiplikationsoperation hinzugefügt und beides dann verglichen.

#![feature(test)]

extern crate test;

pub fn simple_mul(a: u32, b: u32) -> u32 {
    a * b
}

pub fn shift_mul(mut a: u32, mut b: u32) -> u32 {
    let mut res = 0;

    while a > 0 {
        a = a >> 1;
        b = b << 1;
        if a & 1 == 1 {
            res += b;
        }
    }

    res
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::{black_box, Bencher};

    #[test]
    fn test_shift() {
        assert_eq!(12 * 31, shift_mul(12, 31));
        assert_eq!(5 * 4, shift_mul(5, 4));
    }

    #[bench]
    fn bench_simple(b: &mut Bencher) {
        b.iter(|| {
            for _ in 0..1000 {
                black_box(simple_mul(5, 4));
                black_box(simple_mul(7, 31));
                black_box(simple_mul(12, 27));
            }
        });
    }

    #[bench]
    fn bench_shift(b: &mut Bencher) {
        b.iter(|| {
            for _ in 0..1000 {
                black_box(shift_mul(5, 4));
                black_box(shift_mul(7, 31));
                black_box(shift_mul(12, 27));
            }
        });
    }
}

Das Ergebnis ist überraschend, denn der Algorithmus mit Schiebeoperationen ist genauso schnell wie die Multiplikation. Offenbar ist dies der Algorithmus, der in meiner CPU implementiert ist, denn die Zeitunterschiede sind minimal:

% cargo bench
    Finished bench [optimized] target(s) in 0.08s
     Running unittests (target/release/deps/foo-e15661dafac8f7a9)

running 3 tests
test tests::test_shift ... ignored
test tests::bench_shift  ... bench:         849 ns/iter (+/- 25)
test tests::bench_simple ... bench:         841 ns/iter (+/- 40)

test result: ok. 0 passed; 0 failed; 1 ignored; 2 measured; 0 filtered out; finished in 1.00s

Ein Blick unter die Haube

Oder ist der Optimizer doch intelligenter als gedacht? Merkt er vielleicht, dass der Codeblock einer Multiplikation entspricht und ersetzt ihn entsprechend? Tja, das lässt sich leicht im Assembler sehen und den kann man sich schön mit dem Compiler Explorer ansehen; in der Mitte ist der ARM-Assembler, rechts ist der x86-Assembler.

Wie sich zeigt, wird die Multiplikation mit der entsprechenden Anweisung umgesetzt und die Schleife mit den Schiebeoperationen und Vergleichen mit entsprechenden Sprüngen und Assembler-Anweisungen. Die Umsetzung der Multiplikation in meinem i7-4720HQ ist also genauso »lahm« wie die Bitschiebereien und Sprünge durch den Code – eine CPU kann eben auch nicht zaubern.

Die Mathematik dahinter und eine Erkenntnis

Warum ist eigentlich diese ganze Schieberei richtig? Erklären lässt sich dies mit Mathematik. Bekannt ist, dass jede Dezimalzahl auch eine Entsprechung im Binärsystems hat; $12_{10} = 1100_{2}$ und $27_{10} = 11011_{2}$ .

Diese beiden Binärzahlen kann man wie mit der normalen schriftlichen Multiplikation verrechnen und erhält damit einerseits Zeilen mit Null oder einer Zahl und andererseits ergibt sich die Rechtsverschiebung des zweiten Faktoren.

11011 * 1100
           0
          0
     11011
    11011
    --------
   101000100 = 324₁₀

Die schriftliche Multiplikation selbst beruht darauf, dass die kompakte Schreibweise einer Zahl abc für a·2² + b·2¹ + c·2⁰ steht. Bei der Multiplikation zweier solcher Summen muss man jedes Element der ersten Summe mit der zweiten Summe multiplizieren. Betrachtet man dann die $2^{n}$ als die n-fache Verschiebung nach links, so hat man den oben genutzten Algorithmus. Wenn die jeweiligen Stellen von abc Eins sind, entspricht dies der if-Entscheidung für Addieren.

\begin{matrix} abc \cdot mn & = (a \cdot 2^{2} + b \cdot 2^{1} + c \cdot 2^{0}) \cdot (m \cdot 2^{1} + n \cdot 2^{0}) \\ = a \cdot 2^{2} \cdot (m \cdot 2^{1} + n \cdot 2^{0}) + b \cdot 2^{1} \cdot (m \cdot 2^{1} + n \cdot 2^{0}) + c \cdot 2^{0} \cdot (m \cdot 2^{1} + n \cdot 2^{0}) \end{matrix}

Ticks im Assembler

Sprünge sind für die Ausführung immer schlecht, weshalb es günstiger ist, diese mit normalen Operationen zu emulieren. Daher habe ich an dieser Stelle nochmal den Assemblercode genauer angesehen und mir ist aufgefallen, dass es nur den Sprung für die Schleife gibt. Der Compiler hat bereits den zweiten Sprung für den Fall, dass die Bedingung nicht zutrifft, wegoptimiert.

        cbz     w0, .LBB1_3
        mov     w8, w0
        mov     w0, wzr
.LBB1_2:
        lsr     w9, w8, #1
        lsl     w1, w1, #1
        lsl     w8, w8, #30
        and     w8, w1, w8, asr #31
        add     w0, w8, w0
        mov     w8, w9
        cbnz    w9, .LBB1_2
.LBB1_3:
        ret

Für den ARM-Assembler steckt der Trick in den zwei Zeilen:

lsl     w8, w8, #30
and     w8, w1, w8, asr #31

Das Register w8 enthält den Wert von a zum Beginn des Schleifendurchlaufs. Mit lsl wird die 32-Bit-Zahl um 30 Stellen nach links verschoben, sodass am Ende das 2. Bit im 32. Bit steht. Dann ist der dritte Operand von and etwas magisch: w8, asr #31 steht für eine arithmetische Rechtsverschiebung, die besagt, dass die Zahl im Register w8 um 31 Stellen nach rechts verschoben und immer das Bit an der 32. Stelle aufgefüllt wird. Steht also im 32. Bit (1. Bit von w9/a >> 1) eine Eins, so hat das Ergebnis von asr an allen Stellen eine Eins, ist das 32. Bit eine Null, so sind danach alle Stellen Null.

Die bitweise Und-Verknüpfung mit w1 (der Variablen b) erhält den Wert oder setzt ihn auf Null. Und dieses Ergebnis kann immer wieder zu w0 (der Variablen res) hinzuaddiert werden. So wird der Sprung zu einer Berechnung umgewandelt, denn Sprünge bringen den Ablauf der Ausführung durcheinander und kosten die CPU viele Taktzyklen.

Andere Frameworks

Der Artikel »Guidelines on Benchmarking and Rust« gibt einen Überblick zum Framework criterion, welches detaillierte Informationen ausgibt und Grafiken generieren kann. Genauere Informationen gibt es in der Einführung zu criterion.

Ebenfalls ein Ersatz für das eingebaute libtest ist das Framework glassbench. Ein einfaches Beispiel zur Benutzung und die Dokumentation.