Es heißt ja immer, man soll als Programmierer nicht zu früh zu viel Zeit in Optimierungen stecken. Auf der anderen Seite heißt es, man soll überflüssige Speicherallokationen vermeiden. Aber wie viel bringt das? Und lohnt es sich, den Code weniger lesbar zu machen, wenn man dafür ein paar Millisekunden sparen kann? Was, wenn es viele Millisekunden sind? Was ist, wenn man durch die Optimierungen aufpassen muss, dass man nicht dem Borrow-Checker von Rust auf die Füße tritt?
Ich habe keine Antworten darauf, aber ich habe zumindest ein paar Zahlen erhoben, wie sich die ganzen Allokationen auswirken.
Disclaimer: Das Ganze hier hat keinen Anspruch auf methodisch korrekte Wissenschaftlichkeit. Dazu habe ich hier zu wenig Gedanken hereingesteckt, und reviews gab es auch keine. Insbesondere habe ich auch keine Ahnung, was man bei Benchmarks alles berücksichtigen muss.
Das Beispielproblem
Das Problem, dessen Lösung getestet werden soll:
- Lese eine Wörterbuch-Datei ein (words, eine Textdatei mit einem Wort pro Zeile)
- lege die einzelnen Wörter in einer Wörterbuch-Datenstruktur ab (typischerweise Hashtabellen)
- frage für ein Wort ab, ob es im Wörterbuch ist
Meine Wörterbuchdatei ist bei mir die Datei, die zufällig unter /usr/share/dict/words liegt, 976241 Bytes groß, 102774 Zeilen lang.
Grundlegend möchte ich zwei Ansätze testen:
- Lese die gesamte Datei in eine kontinuierliche Datenstruktur (array) ein, splitte sie und lege die Teilstrings (Verweise auf Bereiche der großen Datenstruktur) in einem Wörterbuch ab
- Lese die Datei Zeile für Zeile ein, allokiere für jede Zeile einen String und lege diesen String in einem Wörterbuch ab
Ach ja: Für praktische Zwecke ist das natürlich ziemlich dumm, wenn man eh die ganze Datei durchgeht und nur ein Wort abfragt, kann man sich das Ablegen sparen und vergleicht einfach jeden String mit dem gesuchten Wort. Das ist aber nicht das, was ich testen möchte.
Die ersten beiden Programme
Ich benutze natürlich erst einmal rust, weil es meine Lieblingssprache ist. Ansatz 1:
use std::collections::HashSet;
use std::fs::File;
use std::io::{BufReader, Read};
use std::path::Path;
fn with_big_string() -> std::io::Result<bool> {
let file = File::open(Path::new("/usr/share/dict/words"))?;
let mut reader = BufReader::new(file);
let mut content = String::with_capacity(1024 * 1024);
reader.read_to_string(&mut content)?;
let dict: HashSet<&str> = content.lines().collect();
Ok(dict.contains("banana"))
}
fn main() -> std::io::Result<()> {
if with_big_string()? {
println!("Oh, Banana!");
} else {
println!("No banana!");
}
Ok(())
}
Ich habe hier den Buffer für die Datei mal mit einer statisch definierten Kapazität versehen, die ließe sich aber auch ohne großen Aufwand aus den Metadaten der Datei auslesen.
Im Gegensatz dazu Ansatz 2:
use std::collections::HashSet;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::path::Path;
fn with_small_strings() -> std::io::Result<bool> {
let file = File::open(Path::new("/usr/share/dict/words"))?;
let reader = BufReader::new(file);
let dict: HashSet<String> = reader
.lines()
.collect::<std::io::Result<HashSet<String>>>()?;
Ok(dict.contains("banana"))
}
fn main() -> std::io::Result<()> {
if with_small_strings()? {
println!("Oh, Banana!");
} else {
println!("No banana!");
}
Ok(())
}
In rust hat der erste Ansatz den Vorteil, dass er weniger Allokationen durchführt. Der Zweite hingegen hat den Vorteil, dass man weniger Ärger mit dem borrow-checker hat, wenn man das HashSet herumreicht. Im ersten Fall muss immer garantiert sein, dass content, von dem das HashSet borrowed, noch existiert.
Für sehr große Dateien möchte man vermutlich nicht die ganze Datei am Stück einlesen. Ist hier aber auch irrelevant, denn dann würde man auch nicht den ganzen Inhalt in einem Wörterbuch ablegen wollen.
Benchmarking
So… wie misst man jetzt die zeitliche performance? Einfachster Fall: time
$ time target/release/big_string
Oh, Banana!
real 0m0,016s
user 0m0,012s
sys 0m0,004s
Das Dumme ist nur: aufgrund verschiedener Umstände schwankt dieser Wert ganz schön:
$ time target/release/big_string
Oh, Banana!
real 0m0,045s
user 0m0,038s
sys 0m0,006s
Also was tun? Man müsste das mehrmals ausführen, und einen Mittelwert bilden. Dazu gibt es einen Haufen tools. Ich habe mir das erstbeste (hyperfine) geschnappt, und damit losgelegt. Mit -m wird die Mindestanzahl von Durchläufen angegeben, mit -w wird das Programm ein paar Mal ohne Messung vor dem Benchmark ausgeführt, damit die Caches des Betriebssystems weniger Unterschied machen.
$ hyperfine -w 10 -m 500 target/release/big_string
Benchmark #1: target/release/big_string
Time (mean ± σ): 10.0 ms ± 0.2 ms [User: 8.6 ms, System: 1.6 ms]
Range (min … max): 9.6 ms … 10.9 ms 500 runs
Zehn Millisekunden. Gut. big_string ist Variante 1. Wie sieht es mit small_strings, also Variante 2 aus?
$ hyperfine -w 10 -m 500 target/release/small_strings
Benchmark #1: target/release/small_strings
Time (mean ± σ): 17.5 ms ± 0.6 ms [User: 14.9 ms, System: 2.7 ms]
Range (min … max): 16.8 ms … 20.9 ms 500 runs
17,5 Millisekunden. Das sind über 70% mehr. Klar, das Ding muss ja auch über 100000 Allokationen mehr machen.
Python, um Vergleichswerte zu haben
Damit könnte ich durch sein. Ich habe aber noch ein paar Vergleiche mit anderen Sprachen gezogen. Als erstes Python 3. Variante 1:
f = open("/usr/share/dict/words", "r", encoding="utf-8")
content = f.read()
dictionary = set(content.splitlines())
if "banana" in dictionary:
print("Oh, banana!")
else:
print("No banana!")
Und Variante 2:
f = open("/usr/share/dict/words", "r", encoding="utf-8")
dictionary = set(f)
if "banana\n" in dictionary:
print("Oh, banana!")
else:
print("No banana!")
Die Programme sind viel Übersichtlicher. In Variante 2 wird mit set(f) das Wörterbuch direkt aus der Datei in die Datenstruktur geladen. Das geht, weil geöffnete Dateien hier ein Iterator über die Zeilen der Datei sind.
Ich bin mir übrigens nicht sicher, ob der Code wirklich genau das macht, was ich erwarte, aber wenn ich die Dokus richtig verstanden habe, sollte er es tun. Die Ergebnisse:
$ hyperfine -w 10 -m 500 ./big_string.py
Benchmark #1: ./big_string.py
Time (mean ± σ): 30.6 ms ± 0.5 ms [User: 24.5 ms, System: 6.1 ms]
Range (min … max): 29.7 ms … 32.8 ms 500 runs
und Variante 2:
$ hyperfine -w 10 -m 500 ./small_strings.py
Benchmark #1: ./small_strings.py
Time (mean ± σ): 29.3 ms ± 0.6 ms [User: 23.6 ms, System: 5.7 ms]
Range (min … max): 28.4 ms … 32.0 ms 500 runs
Die nicht-Überraschung: Beide Varianten sind viel langsamer als die rust-Implementierung. Trotzdem recht schnell, für python-Verhältnisse, was vermutlich daran liegt, dass hinter set() und den io-Funktionen optimierter Code liegt.
Interessant ist jedoch, dass beide Varianten etwa gleich schnell sind. Variante 2 ist sogar minimal schneller. Ob das signifikant ist, kann ich nicht sagen. Warum das ist, auch nicht. Ich habe kein besonders gutes Verständnis davon, was bei Python unter der Haube vor sich geht. Bei rust schon eher, aber nur in der Theorie.
Go
Manche Leute sagen, man könne rust nicht mit Go vergleichen, weil die Sprachen für Unterschiedliche Zwecke gedacht sind. Andere Leute (sowohl rust- als auch Go-Fans) bereiten mit Vergnügen ausgefeilte Vergleiche zu. Ich halte mich hier zurück. Dieses Minimalbeispiel reicht nicht, um die Performance von rust und Go im Großen zu vergleichen. Und eigentlich geht es auch mehr um den Vergleich zwischen den beiden Varianten in Go.
Variante 1:
package main
import (
"bufio"
"fmt"
"io/ioutil"
"log"
"os"
"strings"
)
func main() {
file, err := os.Open("/usr/share/dict/words")
if err != nil {
log.Fatal(err)
}
read := bufio.NewReader(file)
contentBytes, err := ioutil.ReadAll(read)
if err != nil {
log.Fatal(err)
}
// just assume it is utf-8, this is sufficient for this test
content := string(contentBytes)
dict := make(map[string]bool)
for _, line := range strings.Split(content, "\n") {
dict[line] = true
}
if dict["banana"] {
fmt.Println("Oh, banana!")
} else {
fmt.Println("No banana!")
}
}
Variante 2:
package main
import (
"bufio"
"fmt"
"log"
"os"
)
func main() {
file, err := os.Open("/usr/share/dict/words")
if err != nil {
log.Fatal(err)
}
//read := bufio.NewReader(file)
scanner := bufio.NewScanner(file)
dict := make(map[string]bool)
for scanner.Scan() {
dict[scanner.Text()] = true
}
if err = scanner.Err(); err != nil {
log.Fatal(err)
}
if dict["banana"] {
fmt.Println("Oh, banana!")
} else {
fmt.Println("No banana!")
}
}
Und die Performance:
$ hyperfine -w 1 -m 500 ./big_string
Benchmark #1: ./big_string
Time (mean ± σ): 15.6 ms ± 0.6 ms [User: 17.4 ms, System: 4.9 ms]
Range (min … max): 14.6 ms … 19.8 ms 500 runs
Deutlich langsamer als die erste Variante in rust, aber auch schneller als die zweite Variante in rust. Und Variante 2?
$ hyperfine -w 1 -m 500 ./small_strings
Benchmark #1: ./small_strings
Time (mean ± σ): 18.3 ms ± 1.3 ms [User: 18.1 ms, System: 5.2 ms]
Range (min … max): 16.8 ms … 23.2 ms 500 runs
Das Bild bei Go ist also ähnlich zu dem in rust: die zweite Variante ist langsamer, auch wenn sie bei Go deutlich näher aneinanderliegen. Und der Unterschied zwischen Variante 2 in rust und go ist ziemlich klein.
Folgerungen
In rust und Go ist es tatsächlich besser, die ganze Datei am Stück einzuladen und dann zu zerlegen, um Allokationen zu sparen. Zumindest von der Performance her. Praktisch will man in rust vielleicht nicht immer den String, von dem geborrowed wurde mit herumschleppen. Da ist ein Vorteil von Go: Dank garbage collection braucht man hier keine Sorgen zu haben. In den meisten Fällen ist es vermutlich einfach egal und fällt damit unter die „keine vorzeitige Optimierung“-Regel.
Ausblick
Mir sind noch ein paar Variationen eingefallen, die ich mal ausprobieren möchte. Zum Beispiel wird hier die Hashtabelle nicht in der richtigen Größe pre-allokiert. Grund dafür ist, dass die Anzahl der Zeilen bei der ersten Allokation einfach noch nicht bekannt ist. Sowohl in rust als auch in Go könnte man aber einen Wert abschätzen (entweder indem man schummelt und einen passenden Wert einträgt, oder indem man die Länge der Datei nimmt und eine durchschnittliche Wortlänge annimmt, mit der man zumindest eine grobe Schätzung bekommt).
Auch interessant wäre, ob es einen Unterschied beim Abfragen von Werten aus dem Wörterbuch macht. Je nach Variante sind da alle Strings im Speicher ziemlich nah beieinander oder irgendwo im Speicher verteilt. Aufgrund der Art, wie in einer Hashtabelle Werte abgelegt werden ist meine Hypothese aber, dass es keinen großen Unterschied macht.
Damit kämen wir zur nächsten Idee: Vergleichen wir Hashtabellen mit B-Bäumen. Das ist aber auch recht langweilig, für diesen Fall sind B-Bäume vermutlich stark im Nachteil.
Das war's. Vielleicht nicht besonders nützlich, aber interessant.
