Der schnellste Weg, eine ganze Zahl im Bereich 0-255 festzuhalten

  • Ich arbeite an einem Bildverarbeitungscode, der Pixelwerte außerhalb des normalen Bereichs von 0 bis 255 erzeugen kann, und ich möchte sie wieder in den gültigen Bereich einklemmen. Ich weiß, dass es sättigende SIMD-Anweisungen gibt, die dies zu einem strittigen Punkt machen, aber ich versuche im Moment, den Standard-C ++ - Code einzuhalten.

    Für meinen Athlon II ist Folgendes zu tun:

     inline
    BYTE Clamp(int n)
    {
        n &= -(n >= 0);
        return n | ((255 - n) >> 31);
    }
     

    Dies kompiliert sich mit MSVC 6.0 in die folgende Assembly:

     setns dl
    neg   edx
    and   eax, edx
    mov   edx, 255
    sub   edx, eax
    sar   edx, 31
    or    dl, al
     

    Ist eine Verbesserung möglich?

    13 October 2014
    Jamal
7 answers
  • Versuchen Sie

      int x=n>255?255:n;
     ... x<0?0:x ...
     

    Ich würde erwarten, dass dies

    produzieren wird
      mov eax,n
     cmp eax,255
     cmovgt eax,255 ; conditional mov instruction
     test eax,eax
     cmovlt  eax,0
     

    Wenn Sie MSVC SIX verwenden, erhalten Sie möglicherweise keine bedingte Verschiebungsanweisung. Wechseln Sie zu einer modernen Version von Visual Studio.

    03 December 2011
    Peter
  • Hier ist mein Versuch:

     unsigned char clamp(int n){
        int a = 255;
        a -= n;
        a >>= 31;
        a |= n;
        n >>= 31;
        n = ~n;
        n &= a;
        return n;
    }
     

    Es werden 7 Anweisungen kompiliert - was dasselbe ist Ihre aktuelle Version. Es kann also schneller sein oder nicht. Ich habe es jedoch nicht zeitlich festgelegt. Ich denke jedoch, dass dies alles Anweisungen für einen einzelnen Zyklus sind.

     mov eax, 255
    sub eax, ecx
    sar eax, 31
    or  al , cl
    sar ecx, 31
    not cl
    and al , cl
     
    03 December 2011
    buckley
  • Fazit 2011-12-05:

    Ich habe alle Vorschläge mit VS 2010 Express erneut versucht. Der generierte Code hat sich nicht viel geändert, aber die Registerbelegung hatte Auswirkungen auf die Gesamtergebnisse. Eine leichte Modifikation der von Ira Baxter vorgeschlagenen unkomplizierten Implementierung kam zum Sieger.

     inline
    BYTE Clamp(int n)
    {
        n = n>255 ? 255 : n;
        return n<0 ? 0 : n;
    }
    
        cmp  ecx, 255
        jle  SHORT $LN8
        mov  ecx, 255
    $LN8:
        test ecx, ecx
        sets bl
        dec  bl
        and  bl, cl
     

    Ich habe eine wertvolle Lektion gelernt mit diesem. Ich begann mit der Annahme, dass das kleine Treiben alles schlagen würde, das einen Zweig enthielt. Ich hatte eigentlich keinen Code ausprobiert, der eine if-Anweisung oder einen ternären Operator enthielt. Das war ein Fehler, denn ich hatte nicht mit der Leistung der in eine moderne CPU eingebauten Verzweigungsvorhersage gerechnet. Eine ternäre Lösung erwies sich als die schnellste, insbesondere wenn der Compiler in einem der Fälle seinen eigenen Bit-Twiddling-Code ersetzte. Der Gesamtzeitpunkt für diese Funktion innerhalb meines Benchmark-Algorithmus stieg von 0,24 Sekunden auf 0,19 Sekunden. Dies ist sehr nahe an den 0,18 Sekunden, die sich ergeben haben, als ich die Klemme vollständig entfernt habe.

    17 December 2014
    Mark Ransom
  • Verwenden von GCC / LLVM unter MacOS X und 64-Bit-Kompilierung und Generieren des Assemblers mit:

     gcc -S -Os clamp.c
     

    wobei clamp.c enthält:

     typedef unsigned char BYTE;
    
    BYTE Clamp_1(int n)
    {
        n &= -(n >= 0);
        return n | ((255 - n) >> 31);
    }
    
    BYTE Clamp_2(int n)
    {
        if (n > 255)
            n = 255;
        else if (n < 0)
            n = 0;
        return n;
    }
     

    Der Assembler für die beiden Funktionen (mit Prolog und Epilog ) ist:

         .section        __TEXT,__text,regular,pure_instructions
        .globl  _Clamp_1
    _Clamp_1:
    Leh_func_begin1:
        pushq   %rbp
    Ltmp0:
        movq    %rsp, %rbp
    Ltmp1:
        movl    %edi, %eax
        shrl    $31, %eax
        xorl    $1, %eax
        negl    %eax
        andl    %edi, %eax
        movl    $255, %ecx
        subl    %eax, %ecx
        sarl    $31, %ecx
        orl     %eax, %ecx
        movzbl  %cl, %eax
        popq    %rbp
        ret
    Leh_func_end1:
    
        .globl  _Clamp_2
    _Clamp_2:
    Leh_func_begin2:
        pushq   %rbp
    Ltmp2:
        movq    %rsp, %rbp
    Ltmp3:
        cmpl    $256, %edi
        jl      LBB2_2
        movl    $255, %edi
        jmp     LBB2_4
    LBB2_2:
        testl   %edi, %edi
        jns     LBB2_4
        xorl    %edi, %edi
    LBB2_4:
        movzbl  %dil, %eax
        popq    %rbp
        ret
    Leh_func_end2:
     

    Die pushq, popq und ret sind der Funktionsaufruf-Overhead. Ihr Code (Clamp_1()) enthält 11 Anweisungen. meins bis 9 (aber bei mir gibt es zwei Sprünge, die bei der Pipeline-Ausführung Verwüstungen verursachen können). Keiner nähert sich den 7 Anweisungen in Ihrer optimierten Version.

    Wenn ich jedoch GCC 4.6.1 für denselben Code verwende, ist die Ausgabe des Assemblers:

         .text
        .globl _Clamp_1
    _Clamp_1:
    LFB0:
        movl    %edi, %eax
        movl    $255, %edx
        notl    %eax
        sarl    $31, %eax
        andl    %edi, %eax
        subl    %eax, %edx
        sarl    $31, %edx
        orl     %edx, %eax
        ret
    LFE0:
        .globl _Clamp_2
    _Clamp_2:
    LFB1:
        xorl    %edx, %edx
        testl   %edi, %edi
        movl    $255, %eax
        cmovns  %edi, %edx
        cmpl    $255, %edx
        cmovle  %edx, %eax
        ret
    LFE1:
     

    Nun sehe ich 8 Anweisungen in Clamp_1 und 6 in Clamp_2 neben ret.


    Weitere Experimente zeigen, dass es einen Unterschied in der Ausgabe zwischen gcc -Os -S clamp.c und gcc -S -Os clamp.c; Ersteres erzeugt die optimierten (kleineren) Leistungen; Letzteres erzeugt die ausführlichere Ausgabe.

    03 December 2011
    Jonathan Leffler
  • Das Ergebnis kann ein wenig davon abhängen, ob sich die Pixeldaten voraussichtlich häufiger innerhalb des Bereichs befinden als außerhalb des Bereichs. Dies kann im ersten Fall schneller sein:

     int clamp(int n)
    {
        if ((unsigned) n <= 255) {
            return n;
        }
        return (n < 0) ? 0 : 255;
    }
     
    21 December 2013
    William Morris
  • Verwenden Sie Ihre & lt; 0 klemmen und das & gt; Wie geht es weiter?

     inline 
    BYTE Clamp(int n)
    {
      n &= -(n >= 0);
      return n | ~-!(n & -256);
    }
     

    Die Demontage der zweiten Zeile (unten) auf meinem Computer hat eine zusätzliche Anweisung, aber keine (teuren) Verschiebungen.

     mov  eax, ecx
    and  eax, -256
    neg  eax
    sbb  eax, eax
    or   eax, ecx
     
    03 December 2011
    DocMax
  •  unsigned char clamp(int n) {
        return (-(n >= 0) & n) | -(n >= 255);
    }
     

    Sie können dies optimieren, wenn Sie - (a & gt; = b)

    optimieren können
    04 December 2011
    anders.norgaard