Berechnung von "(id - (id % width)) / width" beschleunigen?

[Maxim (Gast)]

Lässt sich der Ausruck

int k = (id - (id % width)) / width;

in C irgendwie schneller berechnen? Alle variablen sind Integer.

[ich (Gast)]

k=id/width

[Peter II (Gast)]

Maxim schrieb:
> int k = (id - (id % width)) / width;

sollte da nicht

int k = id/width;

reichen? Oder ich verseht gerade nicht was du erreichen willst.

[Maxim (Gast)]

Ähm, tatsächlich. Ist allerdings nicht schneller. Wahrscheinlich 
optimiert der Compiler den Ausdruck sowieso.

Danke schön.

[Peter II (Gast)]

hast du mal den ASM code verglichen - ich kann mir kaum vorstellen das 
der compiler das versteht.

Nicht das du irgendwo anders ein zeitproblem hast.

[Maxim (Gast)]

Jo, habe woanders noch eine Größe zweimal berechnet. Vorberechnen hat 
nochmal ca. 10% Geschwindigkeit gebracht.

Es geht darum, Indices für die Ausgabe der berechneten Werte zu 
bestimmen (FFT). Diese Prozedur verschlingt bei Radix-2 FFT ca. die 
Hälfte der Zeit, wenn man das out-of-place macht (was ich machen muss, 
da ich OpenCL nutze und in-place wegen der Synchronisierung nicht für 
große FFTs geht).

    int id = get_global_id(0);  // thread index

    // width of each FFT block in the current stage
    int width = (int)exp2((float)(stage - 1));
    
    // the offset for a certain FFT block in the output index
    int offset = id / width;
    
    // input and output indices
    int inA = id;
    int inB = id + NThread;
    int outA = id % width + offset * 2 * width;
    int outB = outA + width;

inA, inB sind die Indices der beiden Eingänge und outA, outB der 
Ausgänge. Ich habe schon einiges optimiert und dadurch ca. doppelte 
Geschwindigkeit erreicht. Aber vielleicht gibt es noch weitere 
Möglichkeiten, die ich nicht sehe?

(Für Skizze siehe http://cnx.org/content/m12012/latest/#fig:inplace )

[Peter II (Gast)]

Maxim schrieb:
> int width = (int)exp2((float)(stage - 1));

kann man das nicht als Tabelle ablegen? das dürfte die meiste zeit in 
dem code brauchen. Welcher werte kann stage erreichen?

[Rufus Τ. F. (rufus)]

stage scheint ein int zu sein (anders kann ich mir den cast nach float 
nicht erklären), und stage scheint auch nicht kleiner als 1 zu werden.

Damit aber kann statt der floatingpoint-Routine exp2 auch einfach eine 
Schiebeoperation durchgeführt werden:

> int width = 1 << (stage - 1);

[Maxim (Gast)]

Ja, stage ist Integer und geht nicht über 24. Ich habe deutlich zu wenig 
Erfahrung mit C. Danke für die Tipps an alle!

[Maxim (Gast)]

Der Trick hat 25% mehr Geschwindigkeit gebracht!

[Maik M. (myco)]

int offset = id / width;
int outA = id % width + offset * 2 * width;

könnte man, wenn ich mich nicht vertan habe auch so lösen:

int frc = id % width;
int outA = frc + (id-frc)<<1;

vorausgesetzt du benötigst offset nicht nochmal, sollte das auch 
schneller sein

[Maik M. (myco)]

was mir gerade aufgefallen ist, so könnte es auch gehen:

int outA = id<<1 - id%width;

[Vlad T. (vlad_tepesch)]

Maik M. schrieb:
> was mir gerade aufgefallen ist, so könnte es auch gehen:
> int outA = id<<1 - id%width;

wo kommt das minus her

*2 durch shifts optimieren macht der Compiler.
Zumal es auch nicht immer sinn macht.
"x*8" rechnet zB ein Avr schneller als "x<<3"

Maik M. schrieb:
> int offset = id / width;
> int outA = id % width + offset  2  width;

-->

outA = id % width + (id / width)* 2 * width;
     = id % width + id * 2 ;

[Maik M. (myco)]

Vlad Tepesch schrieb:
> outA = id % width + (id / width)* 2 * width;
>      = id % width + id * 2 ;

bei ganzzahliger Division verschwinden die Nachkommastellen

outA = 3 % 2 + (3 / 2) * 2 * 2 = 1 + 4;
outA = 3 % 2 + 3 * 2 = 1 + 6;

zu deiner Frage mit dem Minus:

Ausgangsgleichung:
int outA = (id % width) + (id / width) * 2 * width;

(id/width)*width = id - (id % width)

daraus ergibt sich:
int outA = (id % width) + (id - (id % width)) * 2;
int outA = (id % width) + 2*id - 2*(id % width);
int outA = 2*id - (id % width);
int outA = id<<1 - (id % width);

[Maxim (Gast)]

Vlad Tepesch schrieb:
> daraus ergibt sich:
> int outA = (id % width) + (id - (id % width)) * 2;
> int outA = (id % width) + 2*id - 2*(id % width);
> int outA = 2*id - (id % width);
> int outA = id<<1 - (id % width);

Weitere 10%, danke! ;)
Wobei 2*id und id<<1 gleich schnell sind.

[Vlad T. (vlad_tepesch)]

Maxim schrieb:
> Weitere 10%, danke! ;)

aber achtung
Das verändert das Ergebnis.

Maik M. schrieb:
> bei ganzzahliger Division verschwinden die Nachkommastellen


Es treten bei meiner Rechnung weniger Rundungsfehler auf - kann ja aber 
sein, dass das gewollt war

Maxim schrieb:
> Wobei 2*id und id<<1 gleich schnell sind.

das schrieb ich ja: solche optimierungen sollte man dem Compiler 
überlassen.
wenn man Multiplikation meint, schreibt man das was mein meint, nämlich 
*
und wenn man die bitschiebeoperation will, schreibt man <<
Der Compilier weiß schon ganz gut, wie das optimal umgesetzt wird.

[Maxim (Gast)]

Vlad Tepesch schrieb:
> aber achtung
> Das verändert das Ergebnis.

Warum? Ich dachte, die beiden Berechnungswege

int outA = (id % width) + (id - (id % width)) * 2;

und

int outA = id<<1 - (id % width);

würde identische Ergebnisse liefern.

[Vlad T. (vlad_tepesch)]

Maxim schrieb:
> Warum? Ich dachte, die beiden Berechnungswege

du hast falsch zitiert, ich hab nur meinen Namen gelesen und dachte du 
hattest meine Zeilen übernommen

[Hans-jürgen H. (hjherbert)]

int width = 1 << (stage - 1);
int outA = id<<1 - (id % width);

ergibt für stage = 1...24 dasgleiche wie

int width = 1 << (stage - 1);
int outA = id<<1 - (id & (width-1) );

weil width nur eine 2-er-Potenz sein kann.

x%256 == x&(255)