Gigazineのこちらの記事がバズっていて気になったので、コンパイルして逆アッセンブルしてみた。ベンチマークはとってないので実行したら早いとかはあるのかもしれない。
追記：ベンチマークした
GigazineにLinked Listの実装の優劣の記事が書いてあった。
Linuxを生み出したリーナス・トーバルズが考える「優れたコード」はなにか？という記事があり一部でバズっていた。超かいつまむと、Linked Listの削除のコードとして
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;
}
}
よりも
void remove_elegant(IntList *l, IntListItem *target)
{
IntListItem **p = &l->head;
while ((*p) != target) {
p = &(*p)->next;
}
*p = target->next;
}
のほうが優れてるよねって話が書いてあります。個人的には後者のほうがぱっと読めるので読みやすさの観点では好きかなーと思います。
参照の参照を使うほうがパフォーマンスが良い？
ただ、後者のほうがパフォーマンス優れているだろうという言説を見かけてちょっと？となったわけですね。ループの回数も変わらないし、下手したらコンパイラ的には同じな可能性もあるよなーと思ったのでした。
逆アッセンブルして比較してみたら _remove_cs101のほうが早そう？
Githubにコードがそのままおいてあったので、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を作ります
- ここから５個に１個ずつ要素を間引きます
- これを５回繰り返します
要素数や繰り返しの数はベンチマークの時間が待てる程度（だいたい２分くらい）になるように調整しただけで、とくに深い意味はありません。
#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
どっちも１１５秒でした。何度かやったのですが２秒程度早かったり遅かったりで甲乙つけがたい感じです。つまり、誤差ですね・・・・