- Beim Verkleinern der Struktur zur Protokollierung von ICMP Echo Requests in einem Konnektivitäts-Monitoring-System sank die Speichernutzung des Ringpuffers von 12 KiB auf 4 KiB
- Als statt
sent_ns und received_ns beide zu speichern nach dem Empfang nur noch die Latenz erhalten blieb und dafür eine Union verwendet wurde, schrumpfte das Array auf 8 KiB
- Nanosekunden-Genauigkeit wurde durch 100-Mikrosekunden-Einheiten ersetzt und
received in ein Bitfeld umgewandelt, aber wegen Struct Padding ergab sich keine weitere Einsparung
- Indem statt der Quelladresse ein Teil der Bedeutung des ICMP-
identifier durch einen 4-Bit-Zähler ersetzt wurde, schrumpfte die Struktur auf 8 Byte und ein Array mit 512 Elementen auf 4 KiB
- Die Anwendung hatte keine Speicherbeschränkung, daher gab es keinen praktischen Bedarf, aber es wurde zu einem Optimierungsexperiment, das sogar Feldanordnung und die Kosten des Bitzugriffs betrachtete
Problemstellung: Wie Ping-Protokolle gespeichert werden
- Das Konnektivitäts-Monitoring-System sendet ICMP Echo Requests an mehrere Server und beobachtet die durchschnittliche Latenz und den Paketverlust über Intervalle von 1, 5 und 15 Minuten
- Die zuerst naheliegende Speicherform war ein Ringpuffer mit 512 Einträgen, wobei jeder Eintrag Sendezeitpunkt, Empfangszeitpunkt, Quelladresse, Sequenznummer und Empfangsstatus enthält
- Die Größe des anfänglichen Struktur-Arrays
pings_rb[512] wurde mit 12 KiB gemessen
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Erste Einsparung: Sendezeitpunkt und verstrichene Zeit per Union zusammenführen
- Der tatsächlich gewünschte Wert ist nach dem Empfang die Latenz
received - sent, daher müssen Sendezeitpunkt und verstrichene Zeit nicht gleichzeitig gespeichert werden
- In der Struktur, die
sent_ts und elapsed_ts per Union zusammenfasst, wird derselbe Slot vor dem Senden als Sendezeitpunkt und nach dem Empfang als verstrichene Zeit verwendet
- Nach dieser Änderung schrumpfte das 512er-Array von 12 KiB auf 8 KiB
struct ping_timestamp_2 {
union {
uint64_t sent_ts;
uint64_t elapsed_ts;
};
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
Zweiter Versuch: geringere Präzision und Bitfelder
- Ping-Zeiten werden in Zehner-, Hunderter- oder Tausender-Millisekunden gemessen, daher ist es nicht nötig, volle Nanosekunden-Präzision zu speichern
- Wenn die Zeiteinheit auf 100 Mikrosekunden, also 0,1 ms, umgestellt wird, sind mit 43 Bit bis zu 20 Jahre Ping-Tracking möglich
- Für den Wahrheitswert von
received 8 Bit zu verwenden ist übertrieben, daher wurde ein Bitfeld eingesetzt
- Das Array von
ping_timestamp_3 blieb jedoch ebenfalls bei 8 KiB, sodass keine weitere Einsparung entstand
struct ping_timestamp_3 {
uint64_t sent_or_elapsed_ts: 43;
uint64_t received: 1;
uint64_t seq_no: 16;
in_addr_t source_addr;
};
Warum die Größe wegen Struct Padding nicht kleiner wurde
- Bei
ping_timestamp_2 werden am Ende Padding-Bytes angehängt, um die Alignment-Anforderungen zu erfüllen
ping_timestamp_3 legt Zeit, Empfangsstatus und Sequenznummer in die ersten 8 Byte, danach bleiben aber Quelladresse und Padding übrig- Trotz Bitfeldern bleiben 36 Bit Padding übrig, sodass die Gesamtgröße der Struktur nicht sinkt
- Allein ein
bool auf ein Bit zu reduzieren löst die Probleme von Speicherlayout und Alignment nicht
Quelladresse entfernen und ein 4-Bit-Zähler
- Während das Produkt in mobilen Datennetzen läuft, ändert sich die Quelladresse häufig, deshalb speicherte die bisherige Struktur die Quelladresse
- Wenn sich die Adresse ändert, wird auch die Sequenznummer zurückgesetzt; in der Vergangenheit wurden schon gleichzeitig Pakete mit unterschiedlichen Quelladressen und derselben Sequenznummer verarbeitet
- ICMP Echo Requests haben ein 16-Bit-Feld
identifier, mit dem die Anwendung die von ihr gesendeten Pakete identifizieren kann
- Da nicht alle 16 Bit benötigt werden, werden die übrigen 4 Bit als rollierender Zähler verwendet, der bei Änderungen der Quelladresse inkrementiert wird
- Dieser Zähler wird passend zu Quelladressänderungen erhöht, die an anderer Stelle der Anwendung überwacht werden
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
Endergebnis und Feldanordnung
- Die endgültige Struktur entfernt das Feld für die Quelladresse und speichert Zeit, Empfangsstatus, Zähler und Sequenznummer in 64 Bit
- Das Ringpuffer-Array mit 512 Elementen ist damit 4 KiB groß und passt auf eine Datenseite
- Gegenüber den ursprünglichen 12 KiB werden insgesamt 8 KiB eingespart
- Die Reihenfolge der Felder wurde so angepasst, dass
seq_no an einer 16-Bit-Grenze liegt und beim Laden ohne Shift mit einem einzelnen ldrh-Befehl gelesen werden kann
- Zum Lesen von
elapsed_or_sent_ts ist nur eine Maske nötig
Zusätzliche Optimierung: Kosten für den Zugriff auf das Empfangs-Bit senken
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
Fazit
- Das Optimierungsergebnis reduzierte die Speichernutzung von 12 KiB auf 4 KiB, obwohl die Anwendung selbst nicht speicherbeschränkt ist
- Unabhängig vom praktischen Bedarf wurde daraus ein Experiment zu Struct-Layout, Padding, Bitfeldern und den Kosten des Zugriffs auf Instruktionsebene
- Im letzten Kommentar wird klargestellt, dass sogar der Ausdruck „Problem“ locker verwendet wurde und nicht einmal ein Benchmark durchgeführt wurde
1 Kommentare
Lobste.rs-Meinungen
Ich finde: Wenn der Tag kommt, an dem es keinen Spaß mehr macht, über solche Probleme nachzudenken, ist das der Tag, an dem man mit dem Programmieren aufhört
Vorzeitige Optimierung macht immer Spaß
Sich mit den Folgen herumzuschlagen, nachdem man erkannt hat, warum diese Optimierung verfrüht war, macht meistens keinen Spaß
Der Teil mit den 43 Bit für den Zeitstempel ist etwas verwirrend. 24 Bit scheinen auszureichen
Wenn von einem Ringpuffer mit 512 Einträgen die Rede ist, klingt es so, als würde alle 2 Sekunden ein neuer Ping gesendet und als würde man die Pings der letzten 17 Minuten und 4 Sekunden verfolgen
Als ersten Schritt könnte man Delta-Encoding gegenüber einem idealen Timer/Zähler verwenden. Wenn man die letzte Sendezeit in 2-Sekunden-Schritten erhöht und auf den Ringpuffer-Index schaut, lässt sich leicht erkennen, wann ein Paket hätte gesendet werden sollen; man müsste dann nur noch speichern, ob es exakt pünktlich, 0,1 ms zu spät, 2,3 ms zu spät usw. gesendet wurde
Auch die verstrichene Zeit müsste wohl nicht über 17 Minuten und 4 Sekunden hinausgehen, weil der Ping danach ohnehin abläuft. 512 × 2s = 10,240,000 × 100μs, daher reichen bei dieser Genauigkeit etwa 23,3 Bit aus, oder 24 Bit, wenn man es aufrunden möchte. Die rund 6.536.216 übrigen ungültigen Bitmuster ließen sich vielleicht noch anderweitig nutzen
Zusätzlich könnte man mit 24 Bit die Genauigkeit für „gesendet“ deutlich erhöhen und so den Quantisierungsfehler verringern. Selbst bei Mikrosekunden-Genauigkeit könnte ein Ping noch bis zu 16 Sekunden verspätet gesendet werden, was ziemlich großzügig wirkt
Ich weiß nicht, ob die Reduktion eines Samples von 64 Bit auf 48 Bit der Performance helfen oder eher schaden würde. Es würde mich nicht überraschen, wenn das je nach 32-Bit-/64-Bit-Umgebung auf x86 und ARM unterschiedlich ausfällt
Allerdings passt schon die ursprüngliche Größe sehr leicht in den Datencache ziemlich alter Prozessoren, daher scheint es unwahrscheinlich, dass die Speicherersparnis einen Unterschied macht
Ich bin ziemlich sicher, dass genau das der Grund ist, warum wir verfrüht optimieren. Es ist ein Spaßsport
Wenn man Systeme entwirft oder mit systemnahen Programmiersprachen arbeitet, ist vorzeitige Optimierung ehrlich gesagt eines meiner Lieblingsdinge
Zumindest gibt es die Hoffnung, dass man später Zeit und Speicher spart. Das mittlere Ergebnis ist nur, dass die Kopfschmerzen etwas schlimmer werden, weil man herausfinden muss: „Warum habe ich das so gebaut?“; im schlimmsten Fall — und manchmal ist das sogar besser — wird die Optimierung während des Entwurfs so groß, dass man das Projekt selbst gar nicht mehr umsetzt. Dann schließt man das Programm mit dem Gedanken: „Ah, das ist viel zu verknotet, warum mache ich das überhaupt?“