今日だけ x86 とアセンブラな記録

こんばんは、siokoshou です。忘れられない CPU 命令は eieio です。
最近 x86 アセンブラがマイブームです。 x86 に詳しくなかったんですがインテルのマニュアルと古い本を何冊か読んでちょっとわかってきました。で、ネットをふらふらしてたらおもしろそうなネタが転がってたので、高速化にチャレンジしてみました。もっと速いコードが示されてるので実用的な意味はありませんが(^^;

CIDRブロックマッチってことですが、要は検索です。C で書いたものをアセンブラでも書いてみたら C のほうが速かったそうです。gcc (gas) だったので、Windows で Cygwin の gcc 3.4.4 を使いました。まだ 3 なんだ…。
長いのでコードは最後に。いじったのは cidr_lookup 関数だけ。アルゴリズムの大筋は変えてません。ちなみに cidr_initialize.c の初期化のソートの部分の HTML がくずれてます。まあわかるけど。
結果は2倍弱速くなりました。でも、C にはわずかにかなわず…。インラインアセンブラの前後の C 部分と連携してるところがまだ改良の余地ありです。でももう飽きたのでいいやｗ
マニュアル調べたり、AT&T 形式に混乱させられたり(Intel/MS 形式とソース、デスティネーションが逆なので間違う間違うｗ)、gdb の使い方勉強したり、オリンピック見たりで丸一日遊べ/学べました。

気を付けたポイントはメモリになるべく触らずレジスタ使う、ループの継続判断は本体の下で行って継続するなら若いアドレスに戻るようにする(静的分岐予測にあわせる)、アドレス指定方式を使いこなす、loop のようなデコードが大変な複雑な命令は使わず簡単な命令を使う、ってあたり。
(追記)やりたかったけどできなかった最適化は、依存関係のない命令を交互に置くってやつ。ちょっと無理(^^; だからこそハイパースレッディングが役に立つってことでもありますね。(/追記)

uint32_t output_index = 0;
uint32_t addr = 0;

char *cidr_lookup( void *ipaddr, int len )
{
  if ( len != 4 )
    return 0;

  addr = ntohl( * (uint32_t *) ipaddr );

  asm volatile (
      "push %eax;"
      "push %ebx;"
      "push %ecx;"
      "push %edx;"
      "push %esi;"
      "push %edi;"

      "xor  %edi, %edi;"		/* edi : cmin */
      "movl _listcount, %ecx;"	/* ecx : cmax */
      "movl _cidrlist, %ebx;"
      "movl _addr, %edx;"
      "jmp  bin_endif;"

    "binsearch:"
      "movl %ecx, %esi;"
      "add  %edi, %esi;"
      "shr  %esi;"				/* esi : half */
      "cmp  (%ebx, %esi, 4), %edx;"
      "jb   bin_low;"

/*
      "cmovnb %esi, %edi;"
      "cmovb  %esi, %ecx;"	/* too late... *)
*/

    /* bin_high *)			/* addr >= cidr */
      "movl %esi, %edi;"		/* cmin <= half */
      "jmp  bin_endif;"

    "bin_low:"				/* addr < cidr */
      "movl %esi, %ecx;"		/* cmax <= half */

    "bin_endif:"
      "movl %ecx, %eax;"
      "sub  %edi, %eax;"
      "cmp  $7, %eax;"
      "ja   binsearch;"


    /* linear search */
      "sub  %edi, %ecx;"		/* ecx : counter */
      "je   null_return;"		/* listcount == 0 */

      "movl _masklist, %esi;"

    "linear_loop:"
      "movl (%esi, %edi, 4), %eax;"
      "and  %edx, %eax;"
      "cmp  (%ebx, %edi, 4), %eax;"
      "je   lookup_end;"		/* if ( addr == cidr ) */

      "inc  %edi;"
      "dec  %ecx;"
      "jnz  linear_loop;"

    "null_return:"
      "movl $0xffffffff, %edi;"

    "lookup_end:"
      "movl %edi, _output_index;"	/* output */
      "pop %edi;"
      "pop %esi;"
      "pop %edx;"
      "pop %ecx;"
      "pop %ebx;"
      "pop %eax;"
  );

  if ( output_index == 0xffffffff )
    return NULL;

  return typelist[ output_index ];
}