Performance und C#: Geht das schneller?

Soeben ist eine Anfrage hereingekommen: Bei einer bestehenden 3D Applikation wartet der Anwender oft mehrere Minuten auf ein Ergebnis und er fragt an, ob man das schneller machen könne.

Der Anfrage ist ein konkretes Beispiel beigelegt. Da sollen 10'000 Linien aufwendig im 3D-Raum transformiert werden. Mal überlegen, mein Rechner läuft mit 3 GHz, macht also etwa 3'000'000'000 Operationen pro Sekunde. Um in einer Sekunde fertig zu werden, dürfen pro Linie 300'000 Operationen verbraucht werden. Im Beispiel dauert es 100 Sekunden, also 30’000'000 Operationen für die Transformation einer einzigen Linie? Das könnte unter Umständen schon schneller gehen.

Bei der Berechnung ist mein 8-Kern Prozessor zu 12% ausgelastet. Wenn jeder Kern mitrechnen würde, wären wir bis zu 8 Mal schneller. Mit der Task Parallel Library geht das ganz einfach: Eine For-Schleife mit voneinander unabhängigen Berechnungen durch eine Parallel.For-Schleife ersetzen, fertig. Hmm, warum geht das jetzt nicht 8 Mal schneller? Und warum schwanken die Berechnungszeiten so stark? Nachdem ich den Blog «The CLR Thread Pool ‘Thread Injection’ Algorithm» von Matt Warren gelesen habe ist das Problem klar. Ich setze die minimale Anzahl Threads vor Beginn der Berechnung auf einen genügend hohen Wert und das Verhalten entspricht meinen Erwartungen. Geblieben sind die Schwierigkeiten beim Debugging: Nach dem ersten Breakpoint im Parallel.For hält der Debugger nochmals am ersten Breakpoint, ohne beim zweiten Breakpoint im Parallel.For gestoppt zu haben. Aber für eine fast 8-mal schnellere Performance nehme ich das in Kauf. So, jetzt nochmals die Zeiten messen und für später ablegen. Ich führe dieselbe Berechnung hintereinander mit 1, 2, 3… Kernen durch. Zuerst wird die Performance wie erwartet besser, aber dann geht die Performance stark zurück. Dazu lenkt mich jetzt auch noch das Lüftergeräusch ab. Das Lüftergeräusch erinnert mich an die alte Mess-Weisheit «Wer misst, misst Mist»: Mit meinem Messvorgehen habe ich in erster Linie gemessen, wann der Prozessor wegen Überhitzung gedrosselt wird. Jetzt lege ich nach jedem Test eine Pause ein und die Ergebnisse entsprechen wieder meinen Erwartungen.

Weiter. Vielleicht sollte ich die «Single Instruction Multiple Data» SIMD Fähigkeit des Prozessors via System.Numerics ausnutzen, damit können 4 Float Operationen gleichzeitig abgearbeitet werden. Ich verwende jedoch Doubles, da können dann 2 Operationen gleichzeitig abgearbeitet werden, also ein Performancegewinn von 2. Dafür ist der Code etwas weniger flüssig lesbar.

Im Extremfall könnte man die Berechnungen auf der Grafikkarte durchführen, beispielsweise mit CUDA von Nvidia. In meinem Rechner steckt eine Grafikkarte mit 3072 CUDA-Rechenkernen, also ein Performance-Gewinn von 3000. Beim Lesen des Datenblatts erfahre ich, dass für Double Berechnungen 96 Rechenkerne zur Verfügung stehen. Ein Performance Gewinn von 100, wobei die Komplexität vom Programm stark steigen würde. CUDA Programme werden nicht in C# geschrieben, sondern in C++. Da stellen sich dann viele neue Fragen, beispielsweise wie im Falle von einem Fehler die Exception vom C++ Teil in den C# Teil wandert. Weiter brauchen dann alle eine entsprechende Grafikkarte (auch die virtuellen Test-Server).

Dann gibt es noch die Mikro-Optimierungen. Diese sind etwas in Verruf geraten, da einige Programmierer beim Coden vorwiegend die Performance optimiert haben und weniger die Lesbarkeit. Das Ergebnis war dann komplizierter Code für kaum wahrnehmbare Performanceverbesserungen. Ich optimiere beim Coden hauptsächlich auf Lesbarkeit. Ganz am Schluss prüfe ich, ob es Stellen gibt, an denen eine höhere Performance dem Anwender spürbare Vorteile bringt. Anschliessend schätze ich ab, wie lange ich für diese Optimierungen brauchen werde, wieviel Arbeit der Anwender sparen wird und ob sich das wirtschaftlich gesehen in absehbarer Zeit auszahlen wird. Welche Benutzeroperation optimiert werden könnte weiss ich jetzt. Diese verteilt sich jedoch auf 1000 Codezeilen. Welche davon soll ich optimieren? Da gab es doch diesen Spruch «Optimieren ohne Messen ist Zeitverschwendung». Also nehme ich die Datei, bei welcher der Anwender durch die lange Wartezeit aufgehalten wird, führe die Benutzeroperation durch und messe mit einem Profiler, an welcher Stelle am meisten Zeit verbraucht wird. Diese Stelle, welche meist millionenfach durchlaufen wird, optimiere ich und messe anschliessend, was meine Optimierung gebracht hat. Dabei messe ich auch handgestoppt auf dem echten System, da der Profiler, die Einstellung Debug/Release Mode, die Hardware etc. die Messresultate stark verfälschen können. Da der optimierte Code in der Regel weniger gut lesbar ist, nehme ich alle Optimierungen zurück, die dem Benutzer keine klare Verbesserung bringen. Trotz strukturiertem Vorgehen ist es ein zeitintensives Gepröbel, meine Erwartungen werden von den Messungen oft nicht bestätigt. Ich versuche dann beispielsweise, die Zugriffe auf den Hauptspeicher durch die Verwendung von kompakte Datenstrukturen zu reduzieren (die Zugriffszeit auf eine Variable liegt bei meinem Rechner für den L1 Cache bei 2 ns und für das RAM bei 70 ns). Um mein Gefühl für lohnenswerte Anpassungen in diesem Bereich zu verbessern, lese ich nochmals das Paper «What Every Programmer Should Know About Memory» von Ulrich Drepper durch, alles verstanden habe ich auch diesmal nicht, die Sache ist sehr komplex und Vorhersagen bleiben schwierig (Beispiel: Lohnt sich die Parallelisierung, wenn bei jeder 1000-ten Iteration Prozessorkern 1 eine Cache-Line in seinem L1 Cache ändert, welche Prozessorkern 2 auch in seinem L1 Cache hält?). Meine Vorhersagefähigkeit verbessert sich zwar leicht, doch ich mache weiterhin die meisten «Verbesserungen» wieder rückgängig, da der erwartete Effekt nicht eingetreten ist. Bei den erfolgreichen Optimierungen füge ich einen Kommentar hinzu, damit sie beim nächsten «Lesbarkeits-Refactoring» nicht aus Versehen rückgängig gemacht werden. Am Schluss läuft die Berechnung etwa 4 Mal schneller.

In meiner Applikation werden umfangreiche Lookup-Tabellen angelegt, die etwa 1 GB Speicher belegen. Dieser wird dann irgendwann vom Garbage Collector wieder freigegeben, was einige 100 Millisekunden dauert. Dies kann in meinem Fall zu einem Zeitpunkt passieren, in dem der Anwender die Verzögerung deutlich wahrnimmt. Dem Anwender würde ich diese paar 100 Millisekunden zumuten, aber die Applikation wird auch in Produktionslinien mit Realtime Anforderungen eingesetzt. Daher erzwinge ich einen Collect und die damit verbundene Verzögerung gleich anschliessend an das Öffnen der Datei (das mehrere Sekunden dauert). Dort fällt sie dem Benutzer nicht auf und stört auch die Produktionslinie nicht. Da habe ich also doch einmal einen Fall gefunden, der nicht unter die Regel #1 «When to call GC.Collect(): Don’t» aus Rico Mariani’s Blog fällt.

Mehrere Wochen später: Die Berechnung läuft jetzt etwa 10 Mal schneller. Der Code ist nur an ganz wenigen Stellen schwergewichtig auf Performance optimiert (statt nur auf Lesbarkeit). Die Auswirkungen von Performanceoptimierungen kann ich leider nach wie vor nicht zuverlässig vorhersehen, daher werde ich auch weiterhin jede solche «Optimierung» mit einer anschliessenden Messung überprüfen.

Folgendes Beispiel zeigt eine Methode und ihre optimierte Variante. Es handelt sich dabei nicht um Produktivcode. Das Ziel dabei war, viele mögliche Optimierungen in ein übersichtliches Beispiel zu packen (in Produktivcode würde Point3D vermutlich nicht mit Doubles ersetzt, da der Performancegewinn klein ist und die Lesbarkeit stark leidet).

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Media.Media3D;

namespace PerformanceExample
{
    internal static class CenterOfBoundingBoxCalculator
    {
        // Lock for the multithreaded loop.
        private static object theLock = new object();

        /// 
        /// Original code.
        /// 
        public static Point3D CalculateOriginal(IEnumerableIEnumerable> polylines)
        {
            var minValues = new Point3D(double.MaxValue, double.MaxValue, double.MaxValue);
            var maxValues = new Point3D(double.MinValue, double.MinValue, double.MinValue); 

            foreach (var line in polylines)
            {
                foreach (var point in line)
                {
                    minValues.X = Math.Min(minValues.X, point.X);
                    minValues.Y = Math.Min(minValues.Y, point.Y);
                    minValues.Z = Math.Min(minValues.Z, point.Z);

                    maxValues.X = Math.Max(maxValues.X, point.X);
                    maxValues.Y = Math.Max(maxValues.Y, point.Y);
                    maxValues.Z = Math.Max(maxValues.Z, point.Z);
                }
            }

            return (Point3D)(((Vector3D)maxValues + (Vector3D)minValues) / 2.0);
        }

        /// 
        /// Performance optimized to allow fluent, interactive positioning.
        /// Release mode: 1749 ms => 113 ms.
        /// 
        /// 
        /// This remark has just been added, because this example is used in a blog. In practice,
        /// I would just add the summary above.
        /// - Replaced IEnumerable with List: 1749 ms => 1229 ms.
        /// - Replaced Math.Min and Math.Max with "if smaller/larger => assign". 1229 ms => 984 ms.
        /// - Use double instead of Point3D for intermediate results. 984 ms => 934 ms.
        /// - Use for loops instead of forech loops. 934 ms => 334 ms.
        /// - Use Parallel.For instead of for. 334 ms => 113 ms. With 4 (8) cores, ProcessorCount = 8.
        ///   When all thread pool threads are in use (sleeping), without SetMinThreads => 423 ms (!).
        /// - Remove Project Properties > Build > Prefer 32-bit. 113 ms => 68 ms.
        /// - Further remark: with PLINQ you get 212 ms and very compact code.
        /// 
        public static Point3D CalculatePerformanceOptimized(ListList> polylines)
        {
            ThreadPool.GetMinThreads(out int workerThreads, out int completionPortThreads);
            int sufficientWorkerThreads = workerThreads + 2 * Environment.ProcessorCount;
            ThreadPool.SetMinThreads(sufficientWorkerThreads, completionPortThreads);
 
            double minX = double.MaxValue;
            double minY = double.MaxValue;
            double minZ = double.MaxValue;
            double maxX = double.MinValue;
            double maxY = double.MinValue;
            double maxZ = double.MinValue;
 
            Parallel.For(0, polylines.Count, polylineIndex =>
            {
                double innerMinX = double.MaxValue;
                double innerMinY = double.MaxValue;
                double innerMinZ = double.MaxValue;
                double innerMaxX = double.MinValue;
                double innerMaxY = double.MinValue;
                double innerMaxZ = double.MinValue;
 
                List line = polylines[polylineIndex];
                for (int pointIndex = 0; pointIndex  line.Count; pointIndex++)
                {
                    Point3D point = line[pointIndex];
                    if (point.X < innerMinX) { innerMinX = point.X; }
                    if (point.Y < innerMinY) { innerMinY = point.Y; }
                    if (point.Z < innerMinZ) { innerMinZ = point.Z; }
 
                    if (point.X > innerMaxX) { innerMaxX = point.X; }
                    if (point.Y > innerMaxY) { innerMaxY = point.Y; }
                    if (point.Z > innerMaxZ) { innerMaxZ = point.Z; }
                }
 
                lock (theLock)
                {
                    if (innerMinX < minX) { minX = innerMinX; }
                    if (innerMinY < minY) { minY = innerMinY; }
                    if (innerMinZ < minZ) { minZ = innerMinZ; }
 
                    if (innerMaxX > maxX) { maxX = innerMaxX; }
                    if (innerMaxY > maxY) { maxY = innerMaxY; }
                    if (innerMaxZ > maxZ) { maxZ = innerMaxZ; }
                }
            });
 
            ThreadPool.SetMinThreads(workerThreads, completionPortThreads);
 
            return new Point3D(minX + maxX / 2.0, minY + maxY / 2.0, minZ + maxZ / 2.0);
        }
    }
}

Anschliessend schreibe ich diesen Blog und bitte einen Kollegen mit viel Erfahrung, den Inhalt zu reviewen. Er macht mich darauf aufmerksam, dass die Sache doppelt so schnell läuft, wenn man beim Builden die Option «Prefer 32-Bit» abwählt. Wie konnte ich das im Beispielprogramm nur vergessen? Vielleicht, weil die Zahl der Einstellungen, die einen signifikanten Einfluss auf die Performance haben, so gross ist. Weiter merkt er an, dass er eine PLINQ Variante erstellt hat, die nur um Faktor 3 langsamer ist, wie der handoptimierte Code. An PLINQ habe ich gar nicht gedacht, bei meinem nächsten Performance-Problem werde ich ganz am Anfang überprüfen, ob mit PLINQ eine einfache, genügend schnelle Lösung resultiert.

Zuletzt notiere ich Folgendes in mein kleines, schwarzes Büchlein.

Ansätze Performanceoptimierung. Siehe Blog «C# und Performance: Geht das schneller?»:

• PLINQ
• Task Parallel Library
• Handoptimierungen (z.B. die Daten kompakt ablegen, um die Caches gut zu nutzen)
• Numerics (SIMD)
• CUDA