4要素の分岐しないソート (GCC用)

(こちらの記事の続き、おまけです)
「分岐しないソート」の、VC++向けのコードをGCC+Linux向けに修正してみました。

実はC言語によるソートである sort4l() のほうも相当速いので、私の手元の環境だと同じくらいの速度しか出なかった*1んですが、面白いのでオッケー。例えば {1,2,3,4} から生成される順列(24通り)を何百万回か食わすような処理を書いてみると Celeron 2.4GHz & Linux だとアセンブラ版が10%遅く、Athron64 3200+ & Linux/x86_64, gcc -m32 だとアセンブラ版が10%速く、ARM9 200MHz & Linux だと同じ速度でした。

まずx86向けから。

// for GCC + Linux/x86
void sort4(unsigned int *d) {
  __asm__ (
     "mov     (%0), %%eax;"
     "mov    4(%0), %%ebx;"
     "mov    8(%0), %%ecx;"
     "mov   12(%0), %%edx;"

     "cmp   %%ebx,  %%eax;"
     "cmova %%ebx,  %%eax;"
     "cmova  (%0),  %%ebx;"

     "cmp   %%edx,  %%ecx;"
     "cmova %%edx,  %%ecx;"
     "cmova 8(%0),  %%edx;"

     "mov   %%eax,  %%esi;"
     "cmp   %%ecx,  %%eax;"
     "cmova %%ecx,  %%eax;"
     "cmova %%esi,  %%ecx;"

     "mov   %%ebx,  %%esi;"
     "cmp   %%edx,  %%ebx;"
     "cmova %%edx,  %%ebx;"
     "cmova %%esi,  %%edx;"

     "mov   %%ebx,  %%esi;"
     "cmp   %%ecx,  %%ebx;"
     "cmova %%ecx,  %%ebx;"
     "cmova %%esi,  %%ecx;"

     "mov   %%eax,   (%0);"
     "mov   %%ebx,  4(%0);"
     "mov   %%ecx,  8(%0);"
     "mov   %%edx, 12(%0);"
     :: "D"(d)
     : "%eax", "%ebx", "%ecx", "%edx", "%esi", "memory" );
}

せっかくコードが短く、オブジェクトサイズ比で sort4l() の1/5以下なので、マクロにしてコード中にインラインで埋め込んでしまうのも良いかもしれません。当然ですが関数呼び出しのオーバーヘッドが減る分、ずいぶん速くなります。Cで書かれた sort4l() を、無理矢理 __attribute__((__always_inline__)) 等でインライン化するより、(気のせいかもしれませんが)スマートかと。

こんな感じ。

// for GCC + Linux/x86
#define SORT4(d)                                \
  ({                                            \
    unsigned int *d_ = (d);                     \
    __asm__                                     \
      (                                         \
       "mov     (%0),  %%eax;"                  \
       "mov    4(%0),  %%ebx;"                  \
       "mov    8(%0),  %%ecx;"                  \
       "mov   12(%0),  %%edx;"                  \
       "cmp    %%ebx,  %%eax;"                  \
       "cmova  %%ebx,  %%eax;"                  \
       "cmova   (%0),  %%ebx;"                  \
       "cmp    %%edx,  %%ecx;"                  \
       "cmova  %%edx,  %%ecx;"                  \
       "cmova  8(%0),  %%edx;"                  \
       "mov    %%eax,  %%esi;"                  \
       "cmp    %%ecx,  %%eax;"                  \
       "cmova  %%ecx,  %%eax;"                  \
       "cmova  %%esi,  %%ecx;"                  \
       "mov    %%ebx,  %%esi;"                  \
       "cmp    %%edx,  %%ebx;"                  \
       "cmova  %%edx,  %%ebx;"                  \
       "cmova  %%esi,  %%edx;"                  \
       "mov    %%ebx,  %%esi;"                  \
       "cmp    %%ecx,  %%ebx;"                  \
       "cmova  %%ecx,  %%ebx;"                  \
       "cmova  %%esi,  %%ecx;"                  \
       "mov    %%eax,   (%0);"                  \
       "mov    %%ebx,  4(%0);"                  \
       "mov    %%ecx,  8(%0);"                  \
       "mov    %%edx, 12(%0);"                  \
       :: "D"(d_)                               \
       : "%eax", "%ebx", "%ecx", "%edx", "%esi", "memory" \
       );                                       \
  })

次はx86_64向け。

// for GCC + Linux/x86_64
void sort4(unsigned int* d) {
  __asm__
    (
     "mov     (%0), %%r8d;"
     "mov    4(%0), %%r9d;"
     "mov    8(%0), %%r10d;"
     "mov   12(%0), %%r11d;"
     "cmp   %%r9d,  %%r8d;"
     "cmova %%r9d,  %%r8d;"
     "cmova   (%0), %%r9d;"
     "cmp   %%r11d, %%r10d;"
     "cmova %%r11d, %%r10d;"
     "cmova  8(%0), %%r11d;"
     "mov   %%r8d,  %%eax;"
     "cmp   %%r10d, %%r8d;"
     "cmova %%r10d, %%r8d;"
     "cmova %%eax,  %%r10d;"
     "mov   %%r9d,  %%eax;"
     "cmp   %%r11d, %%r9d;"
     "cmova %%r11d, %%r9d;"
     "cmova %%eax,  %%r11d;"
     "mov   %%r9d,  %%eax;"
     "cmp   %%r10d, %%r9d;"
     "cmova %%r10d, %%r9d;"
     "cmova %%eax,  %%r10d;"
     "mov   %%r8d,    (%0);"
     "mov   %%r9d,   4(%0);"
     "mov   %%r10d,  8(%0);"
     "mov   %%r11d, 12(%0);"
     :: "D"(d)
     : "%r8", "%r9", "%r10", "%r11", "%eax", "memory"
     );
}

おまけでARM向け。ARMというCPUは、殆ど全ての命令をconditionalに実行できます(条件実行機能)。ですので、分岐しないソートを簡単に実装できます。Armadillo-9で動作確認しました。

// for GCC + Linux/arm
void sort4(unsigned int* d) {
  __asm__ (
     "LDMIA %0, {r1-r4};"

     "MOV   r5, r1;"
     "CMP   r2, r1;"
     "MOVCC r1, r2;"
     "MOVCC r2, r5;"

     "MOV   r5, r3;"
     "CMP   r4, r3;"
     "MOVCC r3, r4;"
     "MOVCC r4, r5;"

     "MOV   r5, r1;"
     "CMP   r3, r1;"
     "MOVCC r1, r3;"
     "MOVCC r3, r5;"

     "MOV   r5, r2;"
     "CMP   r4, r2;"
     "MOVCC r2, r4;"
     "MOVCC r4, r5;"

     "MOV   r5, r2;"
     "CMP   r3, r2;"
     "MOVCC r2, r3;"
     "MOVCC r3, r5;"

     "STMIA %0, {r1-r4};"
     :: "g"(d)
     : "r1", "r2", "r3", "r4", "r5", "memory" );
}

以上です。http://www.nist.gov/dads/HTML/bitonicSort.html も参考になります。同じアルゴリズムですね。

*1:わたしが何か間違えていなければ