Vektoren vergleich in C



  • dachschaden schrieb:

    • int main() macht man so in C++. In C sollte es int main(void) sein. Jede Funktion, die keinen Parameter übernimmt, sollte void in der Parameterliste haben.

    Quatsch.



  • dachschaden schrieb:

    Andromeda schrieb:

    Probier mal das:

    Schlechter lesbar, produziert noch mehr Maschinencode, und die Jumps sind immer noch nicht weg:

    movapd xmm0,xmm1
    mov    QWORD PTR [rsp+0x8],rsi
    call   400650 <sqrt@plt>
    mov    rsi,QWORD PTR [rsp+0x8]
    jmp    40088c <compVecLen+0x2c>
    movapd xmm0,xmm1
    call   400650 <sqrt@plt>
    jmp    4008b7 <compVecLen+0x57>
    

    Bei mir sind keine calls und jmps dabei:

    10:       return (((amountv2-amountv1)<1)-1)|(amountv1!=amountv2);
    004010E2   mov         ecx,dword ptr [ebp-8]
    004010E5   sub         ecx,dword ptr [ebp-4]
    004010E8   xor         eax,eax
    004010EA   cmp         ecx,1
    004010ED   setl        al
    004010F0   sub         eax,1
    004010F3   mov         edx,dword ptr [ebp-4]
    004010F6   xor         ecx,ecx
    004010F8   cmp         edx,dword ptr [ebp-8]
    004010FB   setne       cl
    004010FE   or          eax,ecx
    


  • Andromeda schrieb:

    return (((amountv2-amountv1)<1)-1)|(amountv1!=amountv2);
    

    🙂

    Nonsens.
    Bitoperatoren auf negative int loszulassen ist einfach nur dumm und ahnlungslos.



  • Wutz schrieb:

    Andromeda schrieb:

    return (((amountv2-amountv1)<1)-1)|(amountv1!=amountv2);
    

    🙂

    Nonsens.
    Bitoperatoren auf negative int loszulassen ist einfach nur dumm und ahnlungslos.

    Dann check mal diese hübsche Variante: 😃

    return ((amountv2-amountv1)<0) - ((amountv2-amountv1)>0);
    


  • Wutz schrieb:

    dachschaden schrieb:

    • int main() macht man so in C++. In C sollte es int main(void) sein. Jede Funktion, die keinen Parameter übernimmt, sollte void in der Parameterliste haben.

    Quatsch.

    http://stackoverflow.com/questions/693788/is-it-better-to-use-c-void-arguments-void-foovoid-or-not-void-foo

    Daniel Earwicker schrieb:

    Means different things in C and C++! In C it means "could take any number of parameters of unknown types", and in C++ it means the same as foo(void).

    Variable argument list functions are inherently un-typesafe and should be avoided where possible.

    Und wenn man sich nicht daran gewöhnen will, dann gibt man überall konsequent (void) an. Inwiefern das Quatsch ist, musst du mal erklären.

    Andromeda schrieb:

    Bei mir sind keine calls und jmps dabei

    Schau dir den kompletten Maschinencode der Funktion an. In dem Teil, in dem ich die alte Variante drin hab, sind am Ende auch keine Jumps mehr, aber in der Funktion generell bleiben sie noch.

    Und das einzige, was dein Code macht, ist den Endcode weiter aufzublähen.

    Andromeda schrieb:

    Dann check mal diese hübsche Variante

    Das einzige, was man dieser Variante zugutehalten kann, ist dass der Compiler hier nicht rbx zwischenspeichert - obwohl er theoretisch auch das sub rsp,0x18 entfernen könnte. Red Zone und so (auf Linux, mit GCC kompiliert).* Ansonsten hat der gesamte Code noch mehr Calls und Jumps drin als zuvor:

    sub    rsp,0x18
    mov    ecx,DWORD PTR [rdi]
    mov    edx,DWORD PTR [rdi+0x4]
    mov    eax,DWORD PTR [rdi+0x8]
    pxor   xmm0,xmm0
    imul   ecx,ecx
    imul   edx,edx
    imul   eax,eax
    add    edx,ecx
    add    eax,edx
    cvtsi2sd xmm0,eax
    sqrtsd xmm2,xmm0
    ucomisd xmm2,xmm2
    jp     4008d0 <compVecLen+0x70>
    mov    ecx,DWORD PTR [rsi]
    mov    edx,DWORD PTR [rsi+0x4]
    mov    eax,DWORD PTR [rsi+0x8]
    pxor   xmm0,xmm0
    imul   ecx,ecx
    imul   edx,edx
    imul   eax,eax
    add    edx,ecx
    add    eax,edx
    cvtsi2sd xmm0,eax
    sqrtsd xmm1,xmm0
    ucomisd xmm1,xmm1
    jp     4008e5 <compVecLen+0x85>
    cvttsd2si eax,xmm2
    cvttsd2si edx,xmm1
    sub    edx,eax
    mov    eax,edx
    shr    eax,0x1f
    test   edx,edx
    setg   dl
    add    rsp,0x18
    movzx  edx,dl
    sub    eax,edx
    ret    
    mov    QWORD PTR [rsp+0x8],rsi
    call   400650 <sqrt@plt>
    mov    rsi,QWORD PTR [rsp+0x8]
    movapd xmm2,xmm0
    jmp    40088b <compVecLen+0x2b>
    movsd  QWORD PTR [rsp+0x8],xmm2
    call   400650 <sqrt@plt>
    movsd  xmm2,QWORD PTR [rsp+0x8]
    movapd xmm1,xmm0
    jmp    4008b2 <compVecLen+0x52>
    nop    DWORD PTR [rax+0x0]
    

    EDIT: sub eingefügt.

    EDIT:
    *Ach, nee, ich bin blöd. In der Funktion wird ein Call zu sqrt gemacht, welches sich an das ABI halten muss, und die resetten den Stack natürlich. Red Zone geht nur in Leaf-Funktionen.



  • dachschaden schrieb:

    Schau dir den kompletten Maschinencode der Funktion an. In dem Teil, in dem ich die alte Variante drin hab, sind am Ende auch keine Jumps mehr, aber in der Funktion generell bleiben sie noch.

    Der Aufruf der sqrt-Funktion braucht sicherlich Calls, aber Jumps finde ich schon ziemlich schräg, wenn einfach nur straight durchgerechnet wird.

    Aber gut, Compilerentwickler wissen was sie tun. Sollte man jedenfalls meinen. 🙂



  • Tergo schrieb:

    ...
    

    Nochmal übersichtlicher wird es wenn du dir angewöhnst (z.b. ab 3 Fallunterscheidungen) switch anzuwenden:

    switch( compVecLen(V1,V2) ) {
      case  0: printf("|V1| = |V2|"); break;
      case  1: printf("|V1| > |V2|"); break;
      case -1: printf("|V1| < |V2|"); break;
      default: puts("Fehler!");
    }
    

    Du sparst wieder eine Variable (result).
    Als nächstes wäre eine Prüfung der Usereingaben bei scanf sinnvoll.


  • Mod

    Andromeda schrieb:

    Wutz schrieb:

    Andromeda schrieb:

    return (((amountv2-amountv1)<1)-1)|(amountv1!=amountv2);
    

    🙂

    Nonsens.
    Bitoperatoren auf negative int loszulassen ist einfach nur dumm und ahnlungslos.

    Dann check mal diese hübsche Variante: 😃

    return ((amountv2-amountv1)<0) - ((amountv2-amountv1)>0);
    

    Auch nicht besser. amount2v2-amountv1 oder amountv2-amountv1 kann immer noch überlaufen und UB bedingen.



  • camper schrieb:

    Auch nicht besser. amount2v2-amountv1 oder amountv2-amountv1 kann immer noch überlaufen und UB bedingen.

    Wie sollen die denn überlaufen?. Das sind beides nichtnegative Werte


  • Mod

    DirkB schrieb:

    camper schrieb:

    Auch nicht besser. amount2v2-amountv1 oder amountv2-amountv1 kann immer noch überlaufen und UB bedingen.

    Wie sollen die denn überlaufen?. Das sind beides nichtnegative Werte

    Ah stimmt, hätte mehr als die letzte Seite lesen sollen.
    Trotzdem witzig, dass über Mikrooptimierungen auf Assemblerebene diskutiert wird, anstatt erst mal auf das überflüssige Wurzelziehen zu verzichten.



  • camper schrieb:

    Trotzdem witzig, dass über Mikrooptimierungen auf Assemblerebene diskutiert wird, ...

    Gibt es da keine Signum-Funktion?

    camper schrieb:

    ... anstatt erst mal auf das überflüssige Wurzelziehen zu verzichten.

    Tja, erstmal die letzten Promille raus kitzeln, bevor wir dann die Prozente raus holen.



  • camper schrieb:

    Trotzdem witzig, dass über Mikrooptimierungen auf Assemblerebene diskutiert wird, anstatt erst mal auf das überflüssige Wurzelziehen zu verzichten.

    Jemand erwähnte, dass das if/elseif/else um den Rükgabewert zu kriegen, kürzer zu coden sei. Damit ging das los. 😃

    Aber du bringst mich auf eine Idee: anstatt die echte Länge des Vektors auszurechnen, müsste für einen Größenvergleich die Summe der Beträge der Komponenten ausreichend sein.

    Also statt: echte_laenge = sqrt (a*a + b*b + c*c + ...)
    richtwert = abs(a) + abs(b) + abs(c) + ...

    Oder?



  • Andromeda schrieb:

    Also statt: echte_laenge = sqrt (a*a + b*b + c*c + ...)
    richtwert = abs(a) + abs(b) + abs(c) + ...

    Nein, so einfach ist es dann doch nicht

    Die Quadrate musst du noch bilden, aber auf die Wurzel kannst du verzichten.
    Denn es gilt:
    0 ≤ d < f <=> 0 ≤ sqrt(d) < sqrt(f)



  • Andromeda schrieb:

    Jemand erwähnte, dass das if/elseif/else um den Rükgabewert zu kriegen, kürzer zu coden sei. Damit ging das los.

    Nein, mir geht es primär um zwei Dinge:
    - Lesbarkeit
    - Kürze

    Dann kommt Geschwindigkeit. Wenn du genug Erfahrung hast, kannst du alle drei kombinieren.

    Dein Code ist weniger gut lesbar, er mag kürzer im Quellcode sein, generiert aber mehr Maschinencode. Geschwindigkeit habe ich nicht getestet.

    Andromeda schrieb:

    Also statt: echte_laenge = sqrt (a*a + b*b + c*c + ...)
    richtwert = abs(a) + abs(b) + abs(c) + ...

    Oder?

    Ist nicht äquivalent. Das abs sparen wir uns mal grad:

    richtwert_falsch_1 = 10 + 5 + 5; /*20*/
    richtwert_falsch_2 = 20 + 0 + 0; /*20, würde also passen*/
    
    richtwert_korrekt_1 = 10*10 + 5*5 + 5*5; /*150*/
    richtwert_korrekt_2 = 20*20 + 0*0 + 0*0; /*400 - und plötzlich passt es nicht mehr*/
    

    Glücklicherweise sind Multiplikationen meines Wissens nicht so teuer wie Divisionen.



  • Dirk, Dachschaden: Danke! 🙂



  • Kurze Anekdote:

    Ein Programm lief sehr langsam, wenn man viele Variablen verwendete. perf hat mir als Verursacher die Funktion exp() angezeigt (über 40% der Gesamtlaufzeit).

    Es wurde vielfach für einen double-vector der Länge n für alle i,j aus [0..n-1], i!=j jeweils exp(v[i] - v[j]) berechnet. Berechnet man allerdings exp(i) für alle Elemente vor und macht dann eine Division statt der Subtraktion, wird der Code plötzlich wieder schnell... (in meinem Fall war n ~ 20)

    Also: gerade diese komplizierten Funktionen wie exp, sqrt, ln klug zu ersetzen oder gar ganz drauf zu verzichten, kann sich lohnen!



  • Wo wir grad so schön beim Thema sind ...

    float Q_rsqrt( float number )
    {
    	long i;
    	float x2, y;
    	const float threehalfs = 1.5F;
    
    	x2 = number * 0.5F;
    	y  = number;
    	i  = * ( long * ) &y;                       // evil floating point bit level hacking
    	i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    	y  = * ( float * ) &i;
    	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
    
    	return y;
    }
    

    https://en.wikipedia.org/wiki/Fast_inverse_square_root


Anmelden zum Antworten