Ich wurde kürzlich nach einem Code gefragt, um das Array "in-place" zu dezimieren / downsampling. Diese "Dezimierungs" -Funktion nimmt ein Array von Ints und speichert einen Eintrag bei einem geraden Index i in dem Array bei dem Index i/2 . Es tut es für alle Einträge im Array.
Dies würde alle geraden indizierten Einträge im ursprünglichen Array in die erste Hälfte des Arrays verschieben. Der Rest des Arrays kann dann auf 0 initialisiert werden. Das Gesamtergebnis ist ein Array, das alle geraden Indexeinträge im ursprünglichen Array (durch Verschieben in die erste Hälfte) und die zweite Hälfte des Arrays mit 0 erhält wird offenbar verwendet, um Signale in der Signalverarbeitung herunterzurechnen.
Der Code sieht ungefähr so aus:
%Vor%Nachdem ich grundlegende Verbesserungen vorgeschlagen habe, die bestimmte Variablen in Registern halten, kann ich keine weitere Möglichkeit finden, sie zu optimieren, aber ich bin mir nicht sicher, ob das nicht möglich ist.
Gibt es Möglichkeiten, das Speicherzugriffsmuster in der Schleife für eine bessere Cache-Leistung zu optimieren? Oder andere Möglichkeiten zur Optimierung der Hauptkopieoperationen beim Komprimieren / Downsampling des Arrays in die erste Hälfte ? (z.B. durch Vektorisierung für Plattformen, die es unterstützen)
%Vor%Gibt es Schleifenumwandlungen (z. B. Tiling / Strip-Mining), die zu hoch effizientem Code für eine solche Dezimierungsschleife führen können?
BEARBEITEN: Es gibt ein paar verschiedene Möglichkeiten, die in den folgenden Antworten vorgeschlagen werden, die scheinbar die Vorteile der Geldmengen- / Füll- oder Zeigerarithmetik nutzen, um Geschwindigkeitseffizienz zu erzielen. Diese Frage konzentriert sich hauptsächlich auf ob es wohldefinierte Loop-Transformationen gibt , die Lokalität oder Cache-Misses signifikant verbessern können (zB wenn es ein loop-nest mit zwei Loops wäre, könnte man in loop Tiling nachschauen Cache-Fehler optimieren)
Sie haben ein Array wie folgt:
%Vor%Sie wollen damit enden:
%Vor%Ich würde es so machen:
%Vor%Auf meinem System ist das ungefähr 20% schneller als Ihre ursprüngliche Version.
Nun liegt es an Ihnen, zu testen und uns mitzuteilen, ob es auf Ihrem System schneller ist!
Hier ist eine Version, die Zeigerarithmetik und Neuplazierung verwendet, die die Tatsache verwendet, dass std :: vector intern ein fortlaufendes Speicherlayout verwendet:
%Vor%Auf meinem Computer läuft dieser Code dreimal so schnell wie Ihr mit deaktivierten Optimierungen und ungefähr 30% schneller als Ihre Version, wenn er mit -o3 auf gcc7.2 kompiliert wird. Ich habe das mit einer Vektorgröße von 20 000 000 Elementen getestet.
Und ich denke das in deiner Versionszeile:
%Vor%sollte
sein %Vor%sonst werden zu viele Elemente auf Null gesetzt.
Unter Berücksichtigung von John Zwincks Frage habe ich einen kurzen Test mit memset und std :: fill anstelle von placement new durchgeführt.
Hier sind die Ergebnisse:
%Vor%Es scheint, dass memset bei großen Vektoren etwas schneller ist und std :: bei kleineren Vektoren etwas schneller ist. Aber der Unterschied ist sehr klein.
Meine Version eines Passes decimate() :
und testet dafür:
%Vor%Gehen Sie nicht zu sz, wenn Sie danach auf Null setzen.
Wenn sz sogar zu sz / 2 kommt, wenn nicht zu (sz-1) / 2.
%Vor%Ich habe alle hier gegebenen Antworten verglichen. Ich habe den Intel Compiler icc Version 15.0.3 benutzt. Optimierungsstufe O3 wurde verwendet.
%Vor%Alle Zeiten beziehen sich auf einen Vektor mit der Länge 100000000.
%Vor%Tags und Links c++ loops performance caching memory-access