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

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

# 実験環境

```plaintext
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}
```
で、ソートできる前提で。

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

```c:サンプルコード
#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);
}
```

## コンパイル結果

```plaintext
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を使った実装
## ソースコード

```c:ソースコード
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]への書き出しが少なくなったような！

```c
        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!! 並びかえを実行しない、という部分は本当になにも実行しないようになっている。

```c
    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];
```