Erst vor ein paar Wochen habe ich ernsthaft mit Rust angefangen. Und ich sehe schon, wie ich nach nur ein paar weiteren Wochen immer idiomatischeren Rust-Code schreibe. Ein Beispiel mit einer Schleife, die ich jetzt als Iterator schreibe.

In der Project-Euler-Aufgabe 1 soll man die Vielfachen von 3 und 5 unter 1000 aufsummieren. In meiner Lösung habe ich dann einmal die Variante mit einer Schleife und Divisionsrest-Prüfung erstellt. Das ganze ließt sich prozedural und ist auch ohne Rust-Kenntnisse verständlich, die Syntax vieler Sprachen ist ja recht universell.

fn solution_division_check() -> i64 {
    let mut sum_of_multiples = 0;
    for i in 1..1000 {
        if i % 3 == 0 || i % 5 == 0 {
            sum_of_multiples += i;
        }
    }
    sum_of_multiples
}

Ich brauche für diese Schleife einen veränderbaren Akkumulator, auf den ich die Zahlen i addieren kann, sofern sie durch 3 oder 5 teilbar sind. Am Ende gebe ich den Akkumulator zurück.

Iteratoren

In Rust sind Iteratoren aber ziemlich zentral. Und somit kann man den Code auch komplett anders schreiben:

fn solution_division_check_iterator() -> i64 {
    (1..1000).filter(|&i| i % 3 == 0 || i % 5 == 0).sum()
}

Wir nehmen uns die Zahlen von 1 bis 1000 (exklusive) als Sequenz. Dann filtern wir diese Sequenz, sodass nur Elemente übrig bleiben, wenn sie durch 3 oder 5 teilbar sind. Das Resultat vom Filtern ist eine neue Sequenz. Und von dieser nehmen wir dann die Summe. Fertig ist das Ergebnis.

Dieser Code ist nur eine Zeile, braucht keine veränderbaren Variablen und ist mir, der funktionale Programmierung schätzt, eingängiger. Nun kann ich diese Syntax auch in Rust nutzen und freue mich sehr darüber.

Gleicher Maschinencode

Als ich den erzeugten Code mit cargo asm anschauen wollte, konnte ich die zweite Version gar nicht finden. Erst als ich das eine auskommentiert hatte, bekam ich das andere. Der Compiler war also schlau genug zu merken, dass es sich um exakt den gleichen Code handelt. Entsprechend wurde dedupliziert. Damit habe ich ehrlich gesagt nicht gerechnet.

Man muss sich also nicht mit funktionaler Programmierung zurückhalten aus Angst vor schlechterer Performance.

Untersuchen des erzeugten Codes

Schauen wir uns einmal den Code an, den der Rust-Compiler erzeugt hat:

.section .text.project_euler_rust::solutions::solution_0001::solution_division_check,"ax",@progbits
        .p2align        4
.type   project_euler_rust::solutions::solution_0001::solution_division_check,@function
project_euler_rust::solutions::solution_0001::solution_division_check:
        .cfi_startproc
        mov esi, 1
        xor ecx, ecx
        movabs r8, -3689348814741910323
        movabs r9, -6148914691236517205
        jmp .LBB57_1
        .p2align        4
.LBB57_3:
        shr rdx
        lea rdx, [rdx + 2*rdx]
        cmp rsi, rdx
        cmove rax, rsi
        inc rsi
        add rcx, rax
        cmp rsi, 1000
        je .LBB57_4
.LBB57_1:
        mov rax, rsi
        mul r8
        mov rdi, rdx
        shr rdi, 2
        mov rax, rsi
        mul r9
        lea rdi, [rdi + 4*rdi]
        mov rax, rsi
        cmp rsi, rdi
        je .LBB57_3
        xor eax, eax
        jmp .LBB57_3
.LBB57_4:
        mov rax, rcx
        ret

Den Code verstehe ich ehrlich gesagt selbst nicht mehr. Ich sehe die Schleife in den Jumps (je und jmp), die Addition in add, die Vergleiche in cmp. Multiplikation mit mul sowie das Kopieren von Variablen mit mov. Das lea ist »load effective address« und rechnet rdx := rdx + 2 * rdx aus, also rdx := 3 * rdx. Das ist clever, weil lea direkt im Chip verfügbar ist und somit schneller als die Multiplikation wäre. Genauso weiter unten mit rdi, das macht rdi := 5 * rdi. Aber diese total krummen Zahlen r8 und r9, die verstehe ich echt nicht. Zumal vermisse ich auch eine Divisions-Operation.

Erklärung durch KI

Ich habe mir den Code von KI (Claude Sonnet 4.6) erklären lassen und ich bin ziemlich beeindruckt, was der Compiler da getan hat. Hier einmal die Erklärung:

Initialisierung:

mov esi, 1          ; Schleifenzähler i = 1
xor ecx, ecx        ; Summe = 0
movabs r8, -3689348814741910323   ; Magische Konstante für Division durch 5
movabs r9, -6148914691236517205   ; Magische Konstante für Division durch 3

Die „magischen Konstanten" sind ein klassischer Compiler-Trick: Statt teurer div-Befehle wird mit einer Multiplikation + Shift approximiert, ob eine Zahl durch 3 bzw. 5 teilbar ist.

Prüfung i % 5 == 0:

mul r8              ; rsi * r8 → rdx enthält obere 64 Bit
shr rdi, 2          ; rdi = floor(i / 5)
lea rdi, [rdi + 4*rdi]  ; rdi = 5 * floor(i / 5)
cmp rsi, rdi        ; i == 5 * floor(i/5)?
je .LBB57_3         ; → ja: rax = i, sonst rax = 0

Prüfung: i % 3 == 0 (in .LBB57_3)

shr rdx             ; rdx = floor(i / 3)  (aus vorherigem mul r9)
lea rdx, [rdx+2*rdx]; rdx = 3 * floor(i / 3)
cmp rsi, rdx
cmove rax, rsi      ; i % 3 == 0 → rax = i  (sonst bleibt rax)
Akkumulation & Schleife
asmadd rcx, rax     ; Summe += rax  (= i, falls i%3==0 oder i%5==0, sonst 0)
inc rsi             ; i++
cmp rsi, 1000
je .LBB57_4         ; Abbruch wenn i == 1000

Also ein paar Dinge hatte ich schon erkannt, die Teilbarkeitsprüfung über magische Konstanten, Bit-Shift und Nutzen von lea ist schon beeindruckend.

Wieder etwas gelernt! Und ich bin auch froh, einen Compiler zu haben und (meiner Meinung nach) super lesbaren Rust-Code schreiben zu können.