Help us understand the problem. What is going on with this article?

quadsortでコンパイルしたバイナリも確認してみる

メモ。quadsortのバイナリも見てみよう。

実験環境

kmtr@ubuntu:~/work/2020/0217_quad$ clang --version
clang version 9.0.0-2 (tags/RELEASE_900/final)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

kmtr@ubuntu:~/work/2020/0217_quad$ clang a.c -o a.o -c -O3 -pg -g
kmtr@ubuntu:~/work/2020/0217_quad$ objdump -S -d a.o

まとめ

・quadsortをコンパイルした結果は、レジスタ割り当てがうまくいくと、メモリへの書き込みがかなり減らせそうに見えた。
・「何もしない」がきちんと「何もしない」結果にできた。これはコンパイラが偉い、たぶん。

普通のSWAPを使った実装

なお、普通のSWAPは、
{a,b,c,d} と要素があったら、

sort{a,b} -> sort{b,c} ->sort{c,d} 
sort{b,c} -> sort{c,d}

で、ソートできる前提で。

ソースコード

ソースコードはこの部分。

サンプルコード
#define SWAPBY2(val,a,b) \
{\
        if ( val[a] > val[b] ) { \
                tmp = val[a]; \
                val[a] = val[b]; \
                val[b] = tmp; \
        } \
} \

void stdswap(int *val)
{
        int tmp; // shared
        SWAPBY2(val,0,1);
        SWAPBY2(val,1,2);
        SWAPBY2(val,2,3);

        SWAPBY2(val,1,2);
        SWAPBY2(val,2,3);
}

コンパイル結果

void stdswap(int *val)
{
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   53                      push   %rbx
   5:   50                      push   %rax
   6:   48 89 fb                mov    %rdi,%rbx
   9:   e8 00 00 00 00          callq  e <stdswap+0xe>
        int tmp; // shared
        SWAPBY2(val,0,1);
   e:   8b 0b                   mov    (%rbx),%ecx
  10:   8b 43 04                mov    0x4(%rbx),%eax
  13:   39 c1                   cmp    %eax,%ecx
  15:   7e 27                   jle    3e <stdswap+0x3e>
  17:   89 03                   mov    %eax,(%rbx)
  19:   89 4b 04                mov    %ecx,0x4(%rbx)
        SWAPBY2(val,1,2);
  1c:   8b 53 08                mov    0x8(%rbx),%edx
  1f:   39 d1                   cmp    %edx,%ecx
  21:   7f 24                   jg     47 <stdswap+0x47>
  23:   89 c8                   mov    %ecx,%eax
        SWAPBY2(val,2,3);
  25:   89 d1                   mov    %edx,%ecx
  27:   8b 73 0c                mov    0xc(%rbx),%esi
  2a:   39 f1                   cmp    %esi,%ecx
  2c:   7f 28                   jg     56 <stdswap+0x56>
  2e:   89 f2                   mov    %esi,%edx

        SWAPBY2(val,1,2);
  30:   89 ce                   mov    %ecx,%esi
  32:   39 f0                   cmp    %esi,%eax
  34:   7f 2c                   jg     62 <stdswap+0x62>
        SWAPBY2(val,2,3);
  36:   89 f0                   mov    %esi,%eax
  38:   39 d0                   cmp    %edx,%eax
  3a:   7f 30                   jg     6c <stdswap+0x6c>
  3c:   eb 34                   jmp    72 <stdswap+0x72>
        SWAPBY2(val,1,2);
  3e:   89 c1                   mov    %eax,%ecx
  40:   8b 53 08                mov    0x8(%rbx),%edx
  43:   39 d1                   cmp    %edx,%ecx
  45:   7e dc                   jle    23 <stdswap+0x23>
  47:   89 53 04                mov    %edx,0x4(%rbx)
  4a:   89 4b 08                mov    %ecx,0x8(%rbx)
  4d:   89 d0                   mov    %edx,%eax
        SWAPBY2(val,2,3);
  4f:   8b 73 0c                mov    0xc(%rbx),%esi
  52:   39 f1                   cmp    %esi,%ecx
  54:   7e d8                   jle    2e <stdswap+0x2e>
  56:   89 73 08                mov    %esi,0x8(%rbx)
  59:   89 4b 0c                mov    %ecx,0xc(%rbx)
  5c:   89 ca                   mov    %ecx,%edx
        SWAPBY2(val,1,2);
  5e:   39 f0                   cmp    %esi,%eax
  60:   7e d4                   jle    36 <stdswap+0x36>
  62:   89 73 04                mov    %esi,0x4(%rbx)
  65:   89 43 08                mov    %eax,0x8(%rbx)
        SWAPBY2(val,2,3);
  68:   39 d0                   cmp    %edx,%eax
  6a:   7e 06                   jle    72 <stdswap+0x72>
  6c:   89 53 08                mov    %edx,0x8(%rbx)
  6f:   89 43 0c                mov    %eax,0xc(%rbx)
}
  72:   48 83 c4 08             add    $0x8,%rsp
  76:   5b                      pop    %rbx
  77:   5d                      pop    %rbp
  78:   c3                      retq
  79:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)

ポイント

まじめにvalへの書き込みしすぎなのでは?という気がする。
下記のように、ebxレジスタのオフセット位置にデータを書き込む命令がいっぱいある…

  47:   89 53 04                mov    %edx,0x4(%rbx)
  4a:   89 4b 08                mov    %ecx,0x8(%rbx)

quadsortを使った実装

ソースコード

ソースコード
void quadswap(int *val)
{
    int tmp[4];

    if (val[0] > val[1]) {
        tmp[0] = val[1];
        tmp[1] = val[0];
    } else {
        tmp[0] = val[0];
        tmp[1] = val[1];
    }

    if (val[2] > val[3]) {
        tmp[2] = val[3];
        tmp[3] = val[2];
    } else {
        tmp[2] = val[2];
        tmp[3] = val[3];
    }

    if (tmp[1] <= tmp[2]) {
        val[0] = tmp[0];
        val[1] = tmp[1];
        val[2] = tmp[2];
        val[3] = tmp[3];
    } else if (tmp[0] > tmp[3]) {
        val[0] = tmp[2];
        val[1] = tmp[3];
        val[2] = tmp[0];
        val[3] = tmp[1];
    } else {
        if (tmp[0] <= tmp[2]) {
            val[0] = tmp[0];
            val[1] = tmp[2];
        } else {
            val[0] = tmp[2];
            val[1] = tmp[0];
        }

        if (tmp[1] <= tmp[3]) {
            val[2] = tmp[1];
            val[3] = tmp[3];
        } else {
            val[2] = tmp[3];
            val[3] = tmp[1];
        }
    }
}

コンパイル結果

0000000000000080 <quadswap>:

void quadswap(int *val)
{
  80:   55                      push   %rbp
  81:   48 89 e5                mov    %rsp,%rbp
  84:   53                      push   %rbx
  85:   50                      push   %rax
  86:   48 89 fb                mov    %rdi,%rbx
  89:   e8 00 00 00 00          callq  8e <quadswap+0xe>
    int tmp[4];

    if (val[0] > val[1]) {
  8e:   8b 33                   mov    (%rbx),%esi
  90:   8b 43 04                mov    0x4(%rbx),%eax
  93:   39 c6                   cmp    %eax,%esi
  95:   89 c2                   mov    %eax,%edx
  97:   0f 4d d6                cmovge %esi,%edx
  9a:   0f 4f f0                cmovg  %eax,%esi
    } else {
        tmp[0] = val[0];
        tmp[1] = val[1];
    }

    if (val[2] > val[3]) {
  9d:   8b 43 08                mov    0x8(%rbx),%eax
  a0:   8b 7b 0c                mov    0xc(%rbx),%edi
  a3:   39 f8                   cmp    %edi,%eax
  a5:   89 f9                   mov    %edi,%ecx
  a7:   0f 4d c8                cmovge %eax,%ecx
  aa:   0f 4f c7                cmovg  %edi,%eax
    } else {
        tmp[2] = val[2];
        tmp[3] = val[3];
    }

    if (tmp[1] <= tmp[2]) {
  ad:   39 c2                   cmp    %eax,%edx
  af:   7e 0f                   jle    c0 <quadswap+0x40>
        val[0] = tmp[0];
        val[1] = tmp[1];
        val[2] = tmp[2];
        val[3] = tmp[3];
    } else if (tmp[0] > tmp[3]) {
  b1:   39 ce                   cmp    %ecx,%esi
  b3:   7e 12                   jle    c7 <quadswap+0x47>
        val[0] = tmp[2];
  b5:   89 03                   mov    %eax,(%rbx)
        val[1] = tmp[3];
  b7:   89 4b 04                mov    %ecx,0x4(%rbx)
  ba:   89 f0                   mov    %esi,%eax
  bc:   89 d1                   mov    %edx,%ecx
  be:   eb 20                   jmp    e0 <quadswap+0x60>
        val[0] = tmp[0];
  c0:   89 33                   mov    %esi,(%rbx)
        val[1] = tmp[1];
  c2:   89 53 04                mov    %edx,0x4(%rbx)
  c5:   eb 19                   jmp    e0 <quadswap+0x60>
        val[2] = tmp[0];
        val[3] = tmp[1];
    } else {
        if (tmp[0] <= tmp[2]) {
  c7:   39 c6                   cmp    %eax,%esi
  c9:   89 f7                   mov    %esi,%edi
  cb:   0f 4f f8                cmovg  %eax,%edi
  ce:   0f 4d c6                cmovge %esi,%eax
  d1:   89 3b                   mov    %edi,(%rbx)
  d3:   89 43 04                mov    %eax,0x4(%rbx)
        } else {
            val[0] = tmp[2];
            val[1] = tmp[0];
        }

        if (tmp[1] <= tmp[3]) {
  d6:   39 ca                   cmp    %ecx,%edx
  d8:   89 d0                   mov    %edx,%eax
  da:   0f 4f c1                cmovg  %ecx,%eax
  dd:   0f 4d ca                cmovge %edx,%ecx
  e0:   89 43 08                mov    %eax,0x8(%rbx)
  e3:   89 4b 0c                mov    %ecx,0xc(%rbx)
        } else {
            val[2] = tmp[3];
            val[3] = tmp[1];
        }
    }
}
  e6:   48 83 c4 08             add    $0x8,%rsp
  ea:   5b                      pop    %rbx
  eb:   5d                      pop    %rbp
  ec:   c3                      retq

ポイント

メモリへの書き出しが少ない!

tmp[4]を導入し、それがレジスタに割り当てられることで、val[0..3]への書き出しが少なくなったような!

        if (tmp[0] <= tmp[2]) {
  c7:   39 c6                   cmp    %eax,%esi
  c9:   89 f7                   mov    %esi,%edi
  cb:   0f 4f f8                cmovg  %eax,%edi
  ce:   0f 4d c6                cmovge %esi,%eax
  d1:   89 3b                   mov    %edi,(%rbx)  val[0] = tmp[2]
  d3:   89 43 04                mov    %eax,0x4(%rbx)  val[1] = tmp[0]
        } else {
            val[0] = tmp[2];
            val[1] = tmp[0];
        }

何もしないが、何もしない!

Beautiful!! 並びかえを実行しない、という部分は本当になにも実行しないようになっている。

    if (tmp[1] <= tmp[2]) {
  ad:   39 c2                   cmp    %eax,%edx
  af:   7e 0f                   jle    c0 <quadswap+0x40>
        val[0] = tmp[0];
        val[1] = tmp[1];
        val[2] = tmp[2];
        val[3] = tmp[3];
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした