優れたコードをコンパイルしてみたら優れてない気がしたけどパフォーマンスは誤差だった

Gigazineの[こちらの記事](https://gigazine.net/news/20201208-linked-list-good-taste/)がバズっていて気になったので、コンパイルして逆アッセンブルしてみた。ベンチマークはとってないので実行したら早いとかはあるのかもしれない。
追記：ベンチマークした

# GigazineにLinked Listの実装の優劣の記事が書いてあった。
[Linuxを生み出したリーナス・トーバルズが考える「優れたコード」はなにか？](https://gigazine.net/news/20201208-linked-list-good-taste/)という記事があり一部でバズっていた。超かいつまむと、Linked Listの削除のコードとして

```C
void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
```
よりも

```C
void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
```
のほうが優れてるよねって話が書いてあります。個人的には後者のほうがぱっと読めるので読みやすさの観点では好きかなーと思います。

# 参照の参照を使うほうがパフォーマンスが良い？

ただ、後者のほうがパフォーマンス優れているだろうという言説を見かけてちょっと？となったわけですね。ループの回数も変わらないし、下手したらコンパイラ的には同じな可能性もあるよなーと思ったのでした。

https://mobile.twitter.com/ryo_grid/status/1468701889907019777

# 逆アッセンブルして比較してみたら _remove_cs101のほうが早そう？

[Github](https://github.com/mkirchner/linked-list-good-taste)にコードがそのままおいてあったので、O3でコンパイルしてobjdumpしてみたら様子がわかるかなと思いとりあえずやってみたのがこちら。

```
0000000000000000 <_remove_cs101>:
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 31 c0                        	xorl	%eax, %eax
       6: 48 89 fa                     	movq	%rdi, %rdx
       9: 0f 1f 80 00 00 00 00         	nopl	(%rax)
      10: 48 89 c1                     	movq	%rax, %rcx
      13: 48 8b 02                     	movq	(%rdx), %rax
      16: 48 8d 50 08                  	leaq	8(%rax), %rdx
      1a: 48 39 f0                     	cmpq	%rsi, %rax
      1d: 75 f1                        	jne	0x10 <_remove_cs101+0x10>
      1f: 48 8d 41 08                  	leaq	8(%rcx), %rax
      23: 48 85 c9                     	testq	%rcx, %rcx
      26: 48 8b 4e 08                  	movq	8(%rsi), %rcx
      2a: 48 0f 44 c7                  	cmoveq	%rdi, %rax
      2e: 48 89 08                     	movq	%rcx, (%rax)
      31: 5d                           	popq	%rbp
      32: c3                           	retq
      33: 66 2e 0f 1f 84 00 00 00 00 00	nopw	%cs:(%rax,%rax)
      3d: 0f 1f 00                     	nopl	(%rax)

0000000000000040 <_remove_elegant>:
      40: 55                           	pushq	%rbp
      41: 48 89 e5                     	movq	%rsp, %rbp
      44: 66 2e 0f 1f 84 00 00 00 00 00	nopw	%cs:(%rax,%rax)
      4e: 66 90                        	nop
      50: 48 89 f8                     	movq	%rdi, %rax
      53: 48 8b 0f                     	movq	(%rdi), %rcx
      56: 48 85 c9                     	testq	%rcx, %rcx
      59: 74 09                        	je	0x64 <_remove_elegant+0x24>
      5b: 48 8d 79 08                  	leaq	8(%rcx), %rdi
      5f: 48 39 f1                     	cmpq	%rsi, %rcx
      62: 75 ec                        	jne	0x50 <_remove_elegant+0x10>
      64: 48 8b 4e 08                  	movq	8(%rsi), %rcx
      68: 48 89 08                     	movq	%rcx, (%rax)
      6b: 5d                           	popq	%rbp
      6c: c3                           	retq
      6d: 0f 1f 00                     	nopl	(%rax)
```

おそらくループしているところがパフォーマンス支配的だろうというのでその部分を見てみましょう。
読むと`remove_cs101`は10~1dの間でループしているのですが、分岐が1dのみなのでなんかそこそこ効率良さそうに見えます。一方で`remove_elegant`は50~６２の間でループしているんですが、分岐が59, 62で２回行われていてそれに伴って比較も２回されていてなんかちょっと効率悪そうに思えます。
ただ、ループ抜けてからの処理は`remove_elegant`のほうがすっきりさっぱりしているので、このへんで何万回と呼ばれると差が出るかもなーという気がしたので試してみました。

# ベンチマーク

ryo_gridに「そのくらいぱっとベンチマークとってみたらいいのでは」と煽ってしまった結果、見事にブーメランしたので雑にですがベンチマークを取るコードを書いて動かしてみました。
内容としては

- 40万要素のLinked Listを作ります
- ここから５個に１個ずつ要素を間引きます
- これを５回繰り返します

要素数や繰り返しの数はベンチマークの時間が待てる程度（だいたい２分くらい）になるように調整しただけで、とくに深い意味はありません。

```C
#include "minunit.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "list.c"

#define N 400000
#define INTERVAL 5
#define LOOP 5

static IntListItem items[N];
static IntListItem *delete_target_items[N / INTERVAL];
static IntList l = { .head = NULL };

static IntList *reset_list()
{
    for (size_t i = 0; i < N - 1; ++i) {
        items[i].value = i;
        items[i].next = &items[i + 1];

        delete_target_items[i / INTERVAL] = &items[i];
    }
    items[N - 1].next = NULL;
    l.head = items;
    return &l;
}

void benchmark_cs101()
{
    for (size_t i = 0; i < N / INTERVAL; i++) {
        remove_cs101(&l, delete_target_items[i]);
    }
}

void benchmark_elegant()
{
    for (size_t i = 0; i < N / INTERVAL; i++) {
        remove_elegant(&l, delete_target_items[i]);
    }
}


int main()
{
    time_t start;
    time_t end;


    time(&start);
    printf("cs101 starts at %ld\n", start);
    for (size_t i = 0; i < LOOP; i++) {
        reset_list();
        benchmark_cs101();
    }
    time(&end);
    printf("cs101 ends at %ld\n", end);
    printf("cs101 time %ld\n", end - start);


    time(&start);
    printf("elegant starts at %ld\n", start);
    for (size_t i = 0; i < LOOP; i++) {
        reset_list();
        benchmark_elegant();
    }
    time(&end);
    printf("elegant ends at %ld\n", end);
    printf("elegant time %ld\n", end - start);


}
```

結果は以下です。

```
cs101 starts at 1639054638
cs101 ends at 1639054753
cs101 time 115
elegant starts at 1639054753
elegant ends at 1639054868
elegant time 115
```

どっちも１１５秒でした。何度かやったのですが２秒程度早かったり遅かったりで甲乙つけがたい感じです。つまり、誤差ですね・・・・