 |
|
Informatiker-FrageWie kann man in einem grossen Array von 16-Bit-Werten die Summe der gesetzten Bits am effizientesten ermitteln? Hierbei handelt es sich um eine Standard-Frage aus dem Informatiker-Wissensschatz, die auch Google schon ihren Bewerbern gestellt hat.[1][2] AntwortIch habe mir mal den Spass gegönnt und es mit meinem Wissen als Senior-Informatikingenieur angegangen. Herausgekommen ist eine Visual-Studio-Lösung (Source-Code) mit vielen Kommentaren, in der die Optimierungsschritte aufgezeigt und die Geschwindigkeiten gemessen werden. Wer interessiert ist kann die gesamte Solution oder auch nur das auf jeder Windows-Maschine ausführbare Programm herunterladen und auf der eigenen Maschine laufenlassen. Im Folgenden zeige ich auf, welche Optimierungsschritte man machen kann. Ausgangslage ist ein Array namens 'array', das mit einer grossen Menge an 16-Bit-Integer-Werten gefüllt ist. In meiner Lösung sind es eine Million, aber man kann es im Programm einstellen. Eine erste, naive und geradeaus-programmierte Lösung.
Fangen wir mal an das zu optimieren. Die innere Schleife kann man schon mal mit einer Shift-Operation (">>") schreiben anstatt mit Divisionen:
Um auch den Modulo-Operator '%' zu vermeiden (Kombination von Division und Subtraktion), kann man auch mit AND ('&') arbeiten:
Der Vergleich auf ungleich 0 ist auch eine Spur schneller als ein Vergleich mit 'probeBit', da 0 eine Konstante ist und der Prozessor dafür bereits eine Hardwareinstruktion hat. Wer schon etwas länger im Informatikbusiness ist, kennt dies zB. unter dem Namen 'BEQ' (Branch if equal). Die Frage ist aber, ob die IL das auch so abbildet. Nun sieht man, dass 'bitCount' und 'probeBit' für jedes Array-Element einmal ausgeführt werden. Es handelt sich dabei um COM-Operationen. Diese sehen natürlich beim 2. Mal, dass es diese Variable schon gibt, es muss aber dennoch stets nachgeschaut werden (man kann das selber austesten, indem man im Debugger während eines Breaks eine komplett neue Variable deklariert). Generell kann man immer Laufvariablen nach aussen aus einem Loop ziehen. Dadurch verliert man aber auch etwas an Kontrolle, die der Compiler für einen durchführt, dass die Variablen nicht an einem ungeplanten Ort zugegriffen werden. Das ist aber in unserem Fall völlig irrelevant. Der Loop ist überschaubar und wir wollen ja Speed haben.
Wir können nun auch noch auf 'elementBits' verzichten und direkt 'count' erhöhen:
Bringt nicht viel, aber ne Spur schon. Der Test auf das tiefste Bit ist in C# etwas aufwändig. In anderen Programmiersprachen gibt es häufig eine Funktion 'Odd(x)' (Test auf ungerade), die das machen kann. Diese fehlt aber in C#. Denkt man etwas ausserhalb der Box sieht man, dass ja auch das Vorzeichen ein Bit darstellt. Man kann also anstatt das tiefste Bit auch einfach das höchste Bit testen:
Jetzt würde man denken, gibt es nichts mehr zu vereinfachen. Doch weit gefehlt. Bereits im Jahre 1960 hat Peter A. Wegner eine noch einfachere Methode gefunden, die gesetzten Bits in einem Wort zu zählen. Diese Methode sieht wie folgt aus.
Moment mal, ein Minus-Eins kombiniert mit einem AND, wie soll das denn gehen? Das ist gar nicht so einfach zu durchschauen. Meine Analyse ergibt folgendes:
Fazit: In beiden Fällen, gerade oder ungerade, wird jeweils genau eine Eins in eine Null verwandelt. Es ist stets die am meisten rechts stehende. Wir können demnach bei jedem Durchlauf den 'count' erhöhen bis der Wert auf 0 geht. Als letzte Methode könnte man noch in Betracht ziehen, ob vielleicht der Einsatz von volatile etwas bringen könnte. Diese Anweisung gibt es erst in den neueren C# Versionen. Sie sagt dem Compiler, er solle eine Variable in einem Register halten anstatt sie ständig im Speicher zu aktualisieren. Ich vermute aber, dass es kaum etwas bringen wird, denn der Compiler ist selber auch schon mit einer schlauen Logik ausgestattet, die solche Dinge üblicherweise selber optimiert. Nun ist aber wirklich fertig mit Optimieren. Noch weiter kann man mit diesem Ansatz nicht mehr gehen. Immerhin haben diese Massnahmen bereits einen Faktor von 9.3 gegenüber dem Geradeaus-programmierten gebracht. Wir würden etliches gewinnen, wenn wir die Schleife zum Zählen der Bits in einem Wort loswerden könnten. Das würde gehen durch die Vorherberechnung der Bits in einem 16-Bit-Wert und Speicherung in einer Lookup-Tabelle. Zuerst kann man mal etwas konservativ sein und die Tabelle nur für 8 Bits machen, das spart etwas Speicherplatz:
Das Befüllen kann durch eine rekursive Routine gemacht werden. Die Aufgabe "Fülle eine Tabelle für x+1 Bits" kann ja zerlegt werden in "Fülle die untere Hälfte mit den Summen wo das Bit 0 ist" und "Fülle die obere Hälfte mit den Summen wo das Bit 1 ist und daher dazuaddiert wird". Für eine schnelle Ausführung ist auch stets zu beachten, dass Arrays gleich zu Beginn auf die volle Grösse dimensioniert werden. Andernfalls kann es vorkommen, dass das Array beim Wachsen in mehreren Schritten vergrössert und dabei umkopiert wird. So würde viel Rechenpower verschwendet werden. Die Zählmethode basierend auf einem solchen Array ist äusserst simpel und daher sehr effizient:
Die Messungen zeigen, dass das Befüllen der Tabelle fast keine Zeit verbraucht. Je grösser das zu berechnende Array ist, umso mehr lohnt es sich, eine Tabelle zu erstellen. In meinem Beispiel mit 1 Million Werten nimmt die Tabellenerstellung 3 Promille von einem Prozent der Arrayberechnung ein. Bei einem Array mit nur 10'000 Werten sind es immer noch nur 3 Promille. Es lohnt sich also in jedem Fall, so eine Tabelle zu machen. Aber haben wir nun damit etwas gewonnen? Ja, enorm viel. Die Methode mit Lookup-Tabelle ist um einen Faktor 25 schneller als die geradeaus-programmierte Version. Was können wir hier noch verbessern? Nun, der Einsatz der BitConverter-Klasse riecht nach Aufwand. Machen wir das doch mal selber, ist ja kein Hexenwerk:
Tatsächlich! Nicht nur bei Mama schmeckt das Selbstgemachte besser, auch in der Informatik. Es ist nahezu um einen Faktor 4 schneller. Wenn das ja so viel gebracht hat, wieso nicht gleich alle 65536 Werte vorherberechnen? Heutzutage hat ein Computer Gigabytes an Speicher. So eine Tabelle braucht ja nur 64 kB, denn in einem 16-Bit-Wert kann es maximal 16 Bits geben. Wir brauchen also mindestens 5 Bits für die Codierung. Die Tabelle könnte daher bei Bedarf kompakt in 40'960 Bytes oder weniger aufbewahrt werden. Das stellt keine grosse Hürde dar, wenn wir es nicht gerade in einen Microcontroller einbauen wollen. Wir müssen nur noch ein kleines Hindernis umgehen, nämlich dass das Array Integer-Werte enthält, und die können negativ sein. In Endeffekt sieht die Zählmethode dann so aus:
Jetzt sind wir bereits beim Faktor 30 angelangt. Das hat sich extrem ausgezahlt. Können wir dies noch mehr tunen? Den Vergleich mit dem if kann man etwas vereinfachen, indem man die 'value' vorher positiv macht:
Bringt aber nur einen unwesentlichen Zugewinn, der Faktor ist immer noch gleichbleibend um die 30. Jede Operation innerhalb des Loops sollte vermieden werden. Wie wär's wenn wir dem Compiler beibringen könnten, den Integer als Vorzeichenlosen Integer anzuschauen? Wir können damit auch noch die Laufvariable im Loop loswerden:
Yep. Die Messung zeigt, wir sind jetzt etwa 100 Mal schneller als die geradeaus-programmierte Lösung. Nun kann man sich noch etwas der Tabellen-Erzeugung widmen. Warum eine Tabelle vorherberechnen, die sowieso immer konstant ist? Ist es nicht vielleicht schneller, die Tabelle einfach zu laden? Dazu speichern wir sie einfach in eine Datei und betten diese in die Resourcen des Programms ein. Bei Bedarf können wir sie dann laden. Die Messung zeigt, dass es ca. 1% schneller ist, die Tabelle zu laden, als sie zu berechnen:
Falls wir dabei etwas Platz sparen wollen, können wir die Lookup-Table komprimieren. Die Zahlen in ihr sind ja auf den Bereich 0..16 begrenzt, wobei die 0 nur gerade einmal am Anfang vorkommt, und die 16 nur gerade einmal am Ende. Wenn wir diese zwei Werte hardcoden schrumpft der Zahlenbereich auf 1..15 und wir brauchen nur noch 4 Bits pro Zahl. Wir können also die Tabelle auf die Hälfte schrumpfen:
Beim Laden packen wir sie dann wieder so aus:
Die Messung zeigt, dass dies etwa gleich schnell ist wie die unkomprimierte Version, aber wir verkleinern die Programmgrösse um 32 kB.
Gehen wir nochmals zurück zur Berechnung basierend auf so einer Tabelle. Wie sieht es aus, wenn wir zudem auch noch alles in einen Block von unchecked platzieren? Da könnten doch noch ein paar Overflow-Tests wegfallen, oder? Nein, die Messungen zeigen leider kaum einen Unterschied. Aber vielleicht können wir aus dem Compiler noch weitere Optimierungen rauskitzeln. Es gibt ja noch das Reflection-Attribut "[MethodImpl(MethodImplOptions.AggressiveInlining)]". Doch leider auch hier, Fehlanzeige. Das alles bringt kaum eine Verschnellerung. Noch eine Idee: Wie wär's, wenn man die Tabelle nicht lädt, sondern direkt in den Code reinprogrammiert? Hier ist C# leider nicht so gut ausgestattet wie C. In C gibt es einen ausgefeilten Präprozessor, im dem - analog zu Programmiersprachen - Methoden programmiert werden können, die sogar Parameter annehmen. Mit soetwas wäre es ein leichtes, die Tabelle rekursiv generieren zu lassen. Im Gegensatz dazu sind im C#-Präprozessor nur ein paar wenige rudimentare Befehle verfügbar und schon gar keine Methoden mit Parametern. Man muss es also anders machen. Man könnte beispielsweise den T4-Mechanismus (Text Templates) verwenden, mit dem man Code generieren kann. Obwohl ich schon intensiv damit gearbeitet habe, war mir das nun doch zu viel für diese Studie. Ich habe nur eine sehr simple Methode implementiert: In der Solution hat es ein paar Routinen drin, die den Sourcecode mit einem StringBuilder generieren und ihn in die Zwischenablage kopieren. Von dort habe ich ihn dann in den Sourcecode eingefügt. Die Messung zeigt, dass dieser Ansatz schlechter ist als die 16-Bit Lookup-Tabelle. Man verliert etwas mehr als einen Faktor 3 an Geschwindigkeit. "Einen hab ich noch" [Steve Jobs]: Die folgende Idee beruht auf meinem C-Wissen: In C ist es so, dass der Compiler ein grosses switch-Statement in eine Lookup-Tabelle umwandelt. Sehr gute Idee der Autoren. Wenn das bei C# auch der Fall wäre, könnte man die Tabelle in Form eines switch-Statements codieren. Dieser Versuch ist in der Datei "LookupTables.cs" enthalten. Die Zählmethode basierend auf so einem 8-Bit-switch würde sich dann so gestalten:
Leider verliert man hierdurch gleich einen Faktor von 10. Die Annahme, dass der Compiler das switch als Tabelle implementiert, kann also bei C# ausgeschlossen werden. Dieser Ansatz funktioniert nicht. Ich habe noch versucht, ein 16-Bit switch zu implementieren, aber ein switch mit 65536 Zeilen überforderten den Compiler. Witzigerweise friert er ein bei der Kompilation. Wäre etwas für einen Eintrag in eine hypothetische Seite "Wie man einen C# Compiler in den Wahnsinn treibt". Auch der Visual Studio-Texteditor hat seine liebe Mühe mit dem Statement, er hängt zwischenzeitlich mehrere Sekunden bis Minuten. Auch den konnten wir also in den Wahnsinn treiben (:-)
MessresultateKommen wir jetzt zu den harten Fakten. Dies sind die Messergebnisse, wenn der Compiler den Code nicht optimiert (Checkbox in den Einstellungen des Projekts). Die angezeigten Zeiten sind in Ticks (1 Tick = 100 Nanosekunden). Klick auf Bild vergrössert:
|
||
|
|
||
| |
||
| © 2018 Andres Rohr. Dieses Thema stammt vom Autor selbst. Es ist nicht einfach vom Internet runterkopiert.
|
||
