c - 効率的な整数比較関数

Question

このcompare関数は、2 つの引数を取りa、bそれらの順序を表す整数を返す関数です。aが より小さい場合、b結果は負の整数になります。aが より大きい場合、b結果は正の整数になります。それ以外の場合、aとbは等しく、結果はゼロです。

この関数は、標準ライブラリのソートおよび検索アルゴリズムをパラメータ化するためによく使用されます。

compare文字の関数を実装するのは非常に簡単です。引数を単純に減算します。

int compare_char(char a, char b)
{
    return a - b;
}

これは、通常、2 つの文字の差が整数に収まると見なされるためです。(この仮定は、 のシステムには当てはまらないことに注意してくださいsizeof(char) == sizeof(int)。)

通常、2 つの整数の差は 1 つの整数に収まらないため、このトリックは整数の比較には使用できません。たとえば、それがより小さいINT_MAX - (-1) = INT_MINことを示唆しています(技術的には、オーバーフローは未定義の動作につながりますが、モジュロ演算を想定しましょう)。INT_MAX-1

では、整数に対して効率的に比較関数を実装するにはどうすればよいでしょうか? これが私の最初の試みです：

int compare_int(int a, int b)
{
    int temp;
    int result;
    __asm__ __volatile__ (
        "cmp %3, %2 \n\t"
        "mov $0, %1 \n\t"

        "mov $1, %0 \n\t"
        "cmovg %0, %1 \n\t"

        "mov $-1, %0 \n\t"
        "cmovl %0, %1 \n\t"
    : "=r"(temp), "=r"(result)
    : "r"(a), "r"(b)
    : "cc");
    return result;
}

6命令未満で実行できますか? より効率的で、それほど単純ではない方法はありますか?

Answer 1

これには分岐がなく、オーバーフローやアンダーフローの影響を受けません:

return (a > b) - (a < b);

を使用gcc -O2 -Sすると、これは次の 6 つの命令にコンパイルされます。

xorl    %eax, %eax
cmpl    %esi, %edi
setl    %dl
setg    %al
movzbl  %dl, %edx
subl    %edx, %eax

さまざまな比較実装をベンチマークするためのコードを次に示します。

#include <stdio.h>
#include <stdlib.h>

#define COUNT 1024
#define LOOPS 500
#define COMPARE compare2
#define USE_RAND 1

int arr[COUNT];

int compare1 (int a, int b)
{
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

int compare2 (int a, int b)
{
    return (a > b) - (a < b);
}

int compare3 (int a, int b)
{
    return (a < b) ? -1 : (a > b);
}

int compare4 (int a, int b)
{
    __asm__ __volatile__ (
        "sub %1, %0 \n\t"
        "jno 1f \n\t"
        "cmc \n\t"
        "rcr %0 \n\t"
        "1: "
    : "+r"(a)
    : "r"(b)
    : "cc");
    return a;
}

int main ()
{
    for (int i = 0; i < COUNT; i++) {
#if USE_RAND
        arr[i] = rand();
#else
        for (int b = 0; b < sizeof(arr[i]); b++) {
            *((unsigned char *)&arr[i] + b) = rand();
        }
#endif
    }

    int sum = 0;

    for (int l = 0; l < LOOPS; l++) {
        for (int i = 0; i < COUNT; i++) {
            for (int j = 0; j < COUNT; j++) {
                sum += COMPARE(arr[i], arr[j]);
            }
        }
    }

    printf("%d=0\n", sum);

    return 0;
}

でコンパイルした 64 ビット システムでgcc -std=c99 -O2の正の整数 ( USE_RAND=1) の結果:

compare1: 0m1.118s
compare2: 0m0.756s
compare3: 0m1.101s
compare4: 0m0.561s

C のみのソリューションのうち、私が提案したものが最速でした。user315052 のソリューションは、わずか 5 つの命令にコンパイルしたにもかかわらず、処理が遅くなりました。スローダウンの原因は、命令が 1 つ少ないにもかかわらず、条件付き命令があるためと考えられます ( cmovge)。

全体として、FredOverflow の 4 命令アセンブリの実装は、正の整数を使用した場合に最も高速でした。ただし、このコードは整数範囲 RAND_MAX のみをベンチマークしたため、オーバーフローを個別に処理し、これらはテストで発生しないため、4 命令テストは偏っています。速度は、分岐予測の成功によるものである可能性があります。

整数の全範囲 ( USE_RAND=0) を使用すると、4 命令のソリューションは実際には非常に遅くなります (他は同じです)。

compare4: 0m1.897s

Answer 2

以下は、私にとって常にかなり効率的であることが証明されています。

return (a < b) ? -1 : (a > b);

を使用gcc -O2 -Sすると、これは次の5つの命令にコンパイルされます。

xorl    %edx, %edx
cmpl    %esi, %edi
movl    $-1, %eax
setg    %dl
cmovge  %edx, %eax

---

Ambroz Bizjakの優れたコンパニオン回答のフォローアップとして、彼のプログラムが上記で投稿されたものと同じアセンブリコードをテストしたとは確信していませんでした。そして、コンパイラの出力を詳しく調べていると、コンパイラがどちらの回答にも掲載されているものと同じ命令を生成していないことに気づきました。そこで、私は彼のテストプログラムを取り、私たちが投稿したものと一致するようにアセンブリ出力を手動で変更し、結果の時間を比較しました。2つのバージョンはほぼ同じように比較されているようです。

./opt_cmp_branchless: 0m1.070s
./opt_cmp_branch:     0m1.037s

他の人が同じ実験を試み、私の観察を確認または否定できるように、各プログラムのアセンブリを完全に投稿しています。

以下は、cmovge命令（(a < b) ? -1 : (a > b)）を含むバージョンです。

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d=0\n"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
.LFB20:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pushq   %rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        movl    $arr.2789, %ebx
        subq    $8, %rsp
        .cfi_def_cfa_offset 32
.L9:
        leaq    4(%rbx), %rbp
.L10:
        call    rand
        movb    %al, (%rbx)
        addq    $1, %rbx
        cmpq    %rbx, %rbp
        jne     .L10
        cmpq    $arr.2789+4096, %rbp
        jne     .L9
        xorl    %r8d, %r8d
        xorl    %esi, %esi
        orl     $-1, %edi
.L12:
        xorl    %ebp, %ebp
        .p2align 4,,10
        .p2align 3
.L18:
        movl    arr.2789(%rbp), %ecx
        xorl    %eax, %eax
        .p2align 4,,10
        .p2align 3
.L15:
        movl    arr.2789(%rax), %edx
        xorl    %ebx, %ebx
        cmpl    %ecx, %edx
        movl    $-1, %edx
        setg    %bl
        cmovge  %ebx, %edx
        addq    $4, %rax
        addl    %edx, %esi
        cmpq    $4096, %rax
        jne     .L15
        addq    $4, %rbp
        cmpq    $4096, %rbp
        jne     .L18
        addl    $1, %r8d
        cmpl    $500, %r8d
        jne     .L12
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        addq    $8, %rsp
        .cfi_def_cfa_offset 24
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE20:
        .size   main, .-main
        .local  arr.2789
        .comm   arr.2789,4096,32
        .section        .note.GNU-stack,"",@progbits

以下のバージョンでは、ブランチレスメソッド（(a > b) - (a < b)）を使用しています。

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d=0\n"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
.LFB20:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pushq   %rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        movl    $arr.2789, %ebx
        subq    $8, %rsp
        .cfi_def_cfa_offset 32
.L9:
        leaq    4(%rbx), %rbp
.L10:
        call    rand
        movb    %al, (%rbx)
        addq    $1, %rbx
        cmpq    %rbx, %rbp
        jne     .L10
        cmpq    $arr.2789+4096, %rbp
        jne     .L9
        xorl    %r8d, %r8d
        xorl    %esi, %esi
.L19:
        movl    %ebp, %ebx
        xorl    %edi, %edi
        .p2align 4,,10
        .p2align 3
.L24:
        movl    %ebp, %ecx
        xorl    %eax, %eax
        jmp     .L22
        .p2align 4,,10
        .p2align 3
.L20:
        movl    arr.2789(%rax), %ecx
.L22:
        xorl    %edx, %edx
        cmpl    %ebx, %ecx
        setg    %cl
        setl    %dl
        movzbl  %cl, %ecx
        subl    %ecx, %edx
        addl    %edx, %esi
        addq    $4, %rax
        cmpq    $4096, %rax
        jne     .L20
        addq    $4, %rdi
        cmpq    $4096, %rdi
        je      .L21
        movl    arr.2789(%rdi), %ebx
        jmp     .L24
.L21:
        addl    $1, %r8d
        cmpl    $500, %r8d
        jne     .L19
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        addq    $8, %rsp
        .cfi_def_cfa_offset 24
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE20:
        .size   main, .-main
        .local  arr.2789
        .comm   arr.2789,4096,32
        .section        .note.GNU-stack,"",@progbits

Answer 3

わかりました、私はそれを 4 つの命令にまとめることができました :) 基本的な考え方は次のとおりです。

半分の確率で、差は整数に収まるほど小さいです。その場合は差額をご返却ください。それ以外の場合は、数字の 1 を右にシフトします。重要な問題は、MSB にどのビットをシフトするかです。

簡単にするために 32 ビットの代わりに 8 ビットを使用した 2 つの極端な例を見てみましょう。

 10000000 INT_MIN
 01111111 INT_MAX
---------
000000001 difference
 00000000 shifted

 01111111 INT_MAX
 10000000 INT_MIN
---------
111111111 difference
 11111111 shifted

キャリー ビットをシフト インすると、最初のケースでは 0 (ただしINT_MINは と等しくないINT_MAX) が生成され、2 番目のケースでは負の数が生成されます (ただしINT_MAXは より小さくはありませんINT_MIN)。

しかし、シフトを行う前にキャリー ビットを反転すると、適切な数値が得られます。

 10000000 INT_MIN
 01111111 INT_MAX
---------
000000001 difference
100000001 carry flipped
 10000000 shifted

 01111111 INT_MAX
 10000000 INT_MIN
---------
111111111 difference
011111111 carry flipped
 01111111 shifted

キャリー ビットを反転することが理にかなっている深い数学的な理由があると確信していますが、まだわかりません。

int compare_int(int a, int b)
{
    __asm__ __volatile__ (
        "sub %1, %0 \n\t"
        "jno 1f \n\t"
        "cmc \n\t"
        "rcr %0 \n\t"
        "1: "
    : "+r"(a)
    : "r"(b)
    : "cc");
    return a;
}

100 万のランダム入力に加えて、INT_MIN、-INT_MAX、INT_MIN/2、-1、0、1、INT_MAX/2、INT_MAX/2+1、INT_MAX のすべての組み合わせでコードをテストしました。すべてのテストに合格しました。私が間違っていることを証明できますか？

Answer 4

その価値のために、SSE2の実装をまとめました。vec_compare1と同じアプローチを使用しますcompare2が、必要なSSE2算術命令は3つだけです。

#include <stdio.h>
#include <stdlib.h>
#include <emmintrin.h>

#define COUNT 1024
#define LOOPS 500
#define COMPARE vec_compare1
#define USE_RAND 1

int arr[COUNT] __attribute__ ((aligned(16)));

typedef __m128i vSInt32;

vSInt32 vec_compare1 (vSInt32 va, vSInt32 vb)
{
    vSInt32 vcmp1 = _mm_cmpgt_epi32(va, vb);
    vSInt32 vcmp2 = _mm_cmpgt_epi32(vb, va);
    return _mm_sub_epi32(vcmp2, vcmp1);
}

int main ()
{
    for (int i = 0; i < COUNT; i++) {
#if USE_RAND
        arr[i] = rand();
#else
        for (int b = 0; b < sizeof(arr[i]); b++) {
            *((unsigned char *)&arr[i] + b) = rand();
        }
#endif
    }

    vSInt32 vsum = _mm_set1_epi32(0);

    for (int l = 0; l < LOOPS; l++) {
        for (int i = 0; i < COUNT; i++) {
            for (int j = 0; j < COUNT; j+=4) {
                vSInt32 v1 = _mm_loadu_si128(&arr[i]);
                vSInt32 v2 = _mm_load_si128(&arr[j]);
                vSInt32 v = COMPARE(v1, v2);
                vsum = _mm_add_epi32(vsum, v);
            }
        }
    }

    printf("vsum = %vd\n", vsum);

    return 0;
}

この時間は0.137秒です。

同じCPUとコンパイラでのcompare2の時間は0.674秒です。

したがって、SSE2の実装は、予想どおり（4ワイドSIMDであるため）約4倍高速です。

Answer 5

このコードには分岐がなく、5つの命令を使用します。これは、cmov*命令が非常に高価な最近のIntelプロセッサで他のブランチレスの代替品よりも優れている可能性があります。欠点は、非対称の戻り値（INT_MIN + 1、0、1）です。

int compare_int (int a, int b)
{
    int res;

    __asm__ __volatile__ (
        "xor %0, %0 \n\t"
        "cmpl %2, %1 \n\t"
        "setl %b0 \n\t"
        "rorl $1, %0 \n\t"
        "setnz %b0 \n\t"
    : "=q"(res)
    : "r"(a)
    , "r"(b)
    : "cc"
    );

    return res;
}

このバリアントは初期化を必要としないため、4つの命令のみを使用します。

int compare_int (int a, int b)
{
    __asm__ __volatile__ (
        "subl %1, %0 \n\t"
        "setl %b0 \n\t"
        "rorl $1, %0 \n\t"
        "setnz %b0 \n\t"
    : "+q"(a)
    : "r"(b)
    : "cc"
    );

    return a;
}

Answer 6

たぶんあなたは次のアイデアを使うことができます（疑似コードで;私は構文に慣れていないのでasm-codeを書きませんでした）：

1. 数字を引く（result = a - b）
2. オーバーフローがない場合は、完了しました（jo命令と分岐予測はここで非常にうまく機能するはずです）
3. オーバーフローが発生した場合は、堅牢な方法を使用してください（return (a < b) ? -1 : (a > b)）

編集：さらに簡単にするために：オーバーフローがあった場合は、ステップ3の代わりに、結果の符号を反転します。

Answer 7

整数を64ビット値に昇格させることを検討できます。