Edit: Keine Multiplikation oder Zweige woot.

Hier ist der generierte Code. Laut MSVC ++ Instrumentation Profiler (meine Tests) und die Tests des OP, sie fast die gleichen durchführen.

Ich denke, 280Z28 und Christopher haben den Assembler-Golf besser abgedeckt als ich, und das betrifft den wahlfreien Zugriff.

Was Sie tatsächlich tun, scheint jedoch ganze Arrays zu verarbeiten. Offensichtlich aus Gründen der Speicher-Caching Sie dies bereits tun wollen, wenn möglich, da die Vermeidung eines Cache-Miss ist eine viel, viele Male bessere Optimierung als die Vermeidung einer kleinen Verzweigung.

In diesem Fall können Sie zuerst mit einer geeigneten Schrankenprüfung die innere Schleife in sogenannten "Bindestrichen" machen. Überprüfen Sie, ob die nächsten k-Inkremente nicht zu einem Überlauf in der kleinsten Dimension eines Arrays führen, und streichen Sie dann k Schritte mit einer neuen Even-more-inner-Schleife, die den "physischen" Index nur jedes Mal um 1 erhöht ein anderes Idiv zu machen. Sie oder der Compiler können diese Schleife ausrollen, Duffs Gerät usw. verwenden.

Wenn der Kernel klein ist, und insbesondere wenn er eine feste Größe hat, dann ist das (oder ein Vielfaches davon mit geeignetem Abrollen, um gelegentlich subtrahieren statt hinzufügen) wahrscheinlich der Wert, der für die Länge des "Bindestrichs" verwendet wird. . Kompilierzeitkonstante Strichlänge ist wahrscheinlich am besten, da Sie (oder der Compiler) die Strichschleife vollständig abwickeln und die Fortsetzungsbedingung beenden können. Solange dies den Code nicht zu groß macht, um schnell zu sein, ersetzt er im Wesentlichen die gesamte Positiv-Modulo-Operation durch ein ganzzahliges Inkrement.

Wenn der Kernel keine feste Größe hat, aber in seiner letzten Dimension oft sehr klein ist, sollten Sie verschiedene Versionen der Vergleichsfunktion für die gebräuchlichsten Größen in Betracht ziehen, wobei die Dash-Schleife in jedem Fall vollständig abgerollt wird.

Eine andere Möglichkeit besteht darin, den nächsten Punkt zu berechnen, bei dem ein Überlauf auftritt (in einem der beiden Arrays), und dann auf diesen Wert zu springen. Sie haben immer noch eine Fortsetzungsbedingung in der Dash-Schleife, aber es geht so lange wie möglich nur mit Inkrementen.

Wenn es sich bei der Operation um eine numerische Gleichheit oder eine andere einfache Operation handelt (ich weiß nicht, was eine "Korrelation" ist), könnten Sie sich SIMD-Anweisungen oder ähnliches ansehen. In diesem Fall sollte die Bindestrichlänge a sein Vielfache des breitesten Vergleichs für einen einzelnen Befehl (oder eine entsprechende SIMD-Operation) in Ihrer Architektur. Dies ist jedoch nicht etwas, mit dem ich Erfahrung habe.

Ohne einen Zweig, aber ein bisschen fummelnd:

Ohne Multiplikation:

Dies ergibt:

Ganzzahl-Multiplikation ist viel schneller als Division. Bei einer großen Anzahl von Aufrufen mit einem bekannten N können Sie die Division durch N durch Multiplikation mit einer Pseudo-Umkehrung von N ersetzen.

Ich werde dies an einem Beispiel illustrieren. N = 29 nehmen. Berechne dann einmal eine Pseudoinverse 2 ^ 16 / N: K = 2259 (abgeschnitten von 2259.86 ...). Ich nehme an, ich bin positiv und ich * K passt auf 32 Bits.

In meinem Beispiel nehmen wir I = 753, wir erhalten Quo = 25 und Mod = 28. (keine Entschädigung erforderlich)

BEARBEITEN.

In Ihrem 3D-Faltungsbeispiel sind die meisten Aufrufe von i% n mit i in 0..n-1, also in den meisten Fällen eine erste Zeile wie

wird die kostspielige und hier nutzlose idiv umgehen.

Wenn Sie genügend RAM haben, richten Sie alle Dimensionen auf Potenzen von 2 aus und verwenden Sie Bit-Manipulationen (shift und) anstelle von Divisionen.

EDIT 2.

Ich habe es tatsächlich bei 10 ^ 9 Anrufen versucht. i% n: 2.93s, mein Code: 1.38s. Denken Sie daran, es impliziert eine Grenze für I (I * K muss auf 32 Bits passen).

Noch ein Gedanke: Wenn Ihre Werte x + dx sind, wobei x in 0..n-1 und dx klein ist, dann deckt das Folgende alle Fälle ab:

Ich habe alle Vorschläge in gcc -O3 unter Verwendung von TSC (außer der für konstantes N) getaktet, und alle haben die gleiche Zeit (innerhalb von 1%) gebraucht.

Mein Gedanke war, dass entweder ((i% n) + n)% n (keine Verzweigung) oder (i + (n & lt; & lt; 16))% n (offensichtlich fehlgeschlagen für große n oder extrem negative i) wäre schneller, aber sie nahmen alle die gleiche Zeit.

Ich mag den Ausdruck wirklich:

Die Demontage ist sehr kurz:

r = ((i% n) + n)% n;

Es hat keine Sprünge (2 idivs, die kostspielig sein könnten), und es kann vollständig inlined sein, den Overhead eines Funktionsanrufs vermeidend.

Was denkst du?

Wenn Sie genügend Reichweite haben, erstellen Sie eine Nachschlagetabelle - zwei Dim-Arrays. Sie können auch die Funktion Inline machen und sicherstellen, dass es sich um den erzeugten Code handelt.

Wenn Sie auch garantieren können, dass ich nie kleiner als -n ist, können Sie den optionalen Zusatz einfach vor den Modulo setzen. Auf diese Weise brauchen Sie den Zweig nicht, und der Modulo schneidet aus, was Sie hinzugefügt haben, wenn Sie das nicht brauchen.

Wenn i kleiner als -n ist, können Sie diese Methode weiterhin verwenden. In einem solchen Fall wissen Sie wahrscheinlich genau, in welchem ​​Bereich sich Ihre Werte befinden. Daher können Sie, anstatt n zu i hinzuzufügen, x * n zu i addieren, wobei x eine ganze Zahl ist, die Ihnen einen ausreichenden Bereich bietet. Für zusätzliche Geschwindigkeit (auf Prozessoren, die keine Single-Cycle-Multiplikation haben), könnten Sie links verschieben anstatt zu multiplizieren.

Wenn Sie garantieren können, dass die Dimensionen Ihres Arrays immer Potenzen von zwei sind, können Sie dies tun:

Wenn Sie weiterhin garantieren können, dass Ihre Dimensionen aus einer bestimmten Teilmenge stammen, können Sie Folgendes tun:

Hier ist Christopher's Version mit einem Fallback auf Jason's wenn Rechtsverschiebung nicht arithmetisch ist.

Die Fallback-Version sollte langsamer sein, da sie imul anstelle von and verwendet.