ファイル読み込みはmmapが早い？

# TL;DR

Linuxのreadとmmapどちらが早いかは、CPUの世代や種類によって変わるようだ

# readとmmap、どちらが早い？

[メモ帳で開くとファイルの最終アクセス日が更新されない](https://qiita.com/diizuka-biz/items/9a4bc6ab7afd547741c2)の記事では、Windowsのメモ帳でより早くファイルを読むために、ReadFileではなく、CreateFileMappingを使っている事がわかりました。

どうしてCreateFiieMappingの方が早いのか調べたいのですが、Windowsはソースコードを公開していないので調べられません。一方で、LinuxにはCreateFileMappingに相当するシステムコールmmapがあり、ソースも公開されています。

果たしてLinuxでもreadよりmmapの方が早いのか。ネットで調べると、早い、いや早くない、と賛否両論の記事が沢山出てきます。代表例を幾つか挙げます。

1. 早い https://www.atmarkit.co.jp/ait/articles/1201/18/news133_2.html 2012年
1. 早くない https://kazuhooku.hatenadiary.org/entry/20131010/1381403041 2013年
1. 早い https://gigazine.net/amp/20201031-mmap-system-faster-system-call 2020年

この中で[2020年のGigazineの記事](https://gigazine.net/amp/20201031-mmap-system-faster-system-call)では、readとmmapの速度比較をして、長時間かかる内部処理の一覧を出しています。一番処理に時間がかかっているのが、以下のメモリ間コピー処理です。

- read: copy_user_enhanced_fast_string
- mmap: \_\_memmove_avx_unaligned_erms

## 時間がかかるのは、mmap内部の処理ではない

\_\_memmove_avx_unaligned_erms は、カーネルではなく[libcでの処理](https://i.gzn.jp/img/2020/10/31/mmap-faster-system-call/060.png)です。あれ？mmapはシステムコールなのに、何故libcの処理が出てくるのでしょうか？ わざわざユーザ空間でメモリ間コピーしているのは何故でしょうか？

mmapでマッピングしたメモリ領域を書き換えると、ファイルの内容が変わってしまいます。
メモ帳のように、編集後に保存するか破棄するか選べるようにしたいときには、mmapした後、ユーザ空間でファイルの内容を一旦別メモリにコピーし、コピー後の領域を編集する必要があります。

恐らく上記Giganizeの記事での速度比較は、このようなメモ帳的なユースケースを想定して、以下のような処理にかかる時間を計測し比較したのだと思います。Aのreadの中と、Bのmemmoveにメモリ間コピー処理があり、ここに一番時間がかかっています。

```c:speedtest.cc
// #include等は省略
static const char* FILE = "largefile.txt"
static struct stat S;
static int DUMMY = stat(FILE, &S);

void read_file() {
   int fd = open(FILE, 0);
   char* dest = malloc(S.st_size);
   read(fd, dest, s.st_size); // A
   // ここでdestの中身を編集しても、ファイルの中身は変わらない
}

void mmap_file() {
   int fd = open(FILE, 0);
   char* src = mmap(NULL, s.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
   char* dest = malloc(S.st_size);
   memmove(dest, src, s.st_size); // B
   // ここでdestの中身を編集しても、ファイルの中身は変わらない
}
```

AとBでのコピー処理が、実際はどういう実装になっているのか、気になりませんか？Gigazineの記事では、BがAVXを使っているという事しかわかりません。私は気になって、いてもたってもいられません。
実装での処理方式がわかれば、速度計測で早くなったり遅くなったりするヒントが分かるかもしれません。早速、Linuxカーネルとlibcのソースを探検して調べてみましょう。　　　　　　　　　　

## ソースコードの準備
今回調査する環境は以下です。

- Ubuntu 20.04.1
    - Linux 4.19.104
    - glibc-2.31
- x86_64用のソースコードを調査

まずはソースコードをダウンロードして展開します。

```text:Linuxカーネル
$ wget https://cdn.kernel.org/pub/linux/kernel/v4.x/linux-4.19.104.tar.xz
$ tar Jxvf linux-4.9.104.tar.xz
```

```text:glibc(libc6)ソース
$ sudo vi /etc/apt/sources-list
apt-src のコメントを外す
$ sudo apt update -y
$ sudo apt install -y dpkg-dev
$ apt source libc6
```

## readでのメモリコピー
まずは、read内でのメモリコピー処理を探しましょう。
カーネルソース中の、copy_user_enhanced_fast_string 関数の定義を見ます。

```
$ cd linux-4.19.104
$ grep -R copy_user_enhanced_fast_string
- 中略 -
arch/x86/lib/copy_user_64.S:ENTRY(copy_user_enhanced_fast_string)
```

どうやらアセンブラのようです。

```
$ less arch/x86/lib/copy_user_64.S
-中略-
ENTRY(copy_user_enhanced_fast_string)
-中略-
1:      rep
        movsb
-略-
```

ストリング命令rep movsbを使ってコピーしています。16bitの時代からある、x86の命令です。
レジスタrsiで示すメモリアドレスから、レジスタrdiが示すメモリアドレスへ、レジスタrcxのバイト分コピーします。素直な実装ですね。

## mmapした後のメモリコピー
libcのmemmoveのソースを調べます。

```sh
$ cd glibc-2.31a
$ grep -R __memmove_avx_unaligned_erms
sysdeps/x86_64/multiarch/ifunc-impl-list.c:                           __memmove_avx_unaligned_erms)
ChangeLog.old/ChangeLog.18:     __memmove_avx_unaligned_erms, __memmove_avx512_unaligned_2,
```

sysdeps/x86_64/multiarch/ifunc-impl-list.c を見ると、CPUの世代毎に追加されたメモリコピー命令の違いを隠蔽するために、様々な世代のCPUで使うメモリ間コピー処理関数へのポインタを配列として保持しているだけでした。__memmove_avx_unaligned_erms の中身の実装はどこでしょうか？

関数名を幾つかに分割して何度か検索してみると... それっぽいものを見つけました。

```sh
$ grep -R __memmove | grep unaligned_erms
-中略-
sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S:ENTRY (MEMMOVE_SYMBOL (__memmove, unaligned_erms))
-中略-
```

MEMMOVE_SYMBOLを調べると、以下のマクロを使い __memmove_avx_unaligned_erms というシンボル名の関数をアセンブラ内で定義していました。

```c:sysdeps/x86_64/multiarch/memmove-avx-unaligned-erms.S
# define MEMMOVE_SYMBOL(p,s)      p##_avx_##s
```

というわけで、memmove-vec-unaligned-erms.S に実装がありそうです。

中を見ると... ありました。256bitのAVXのベクトル命令を使って、ループ処理でメモリコピーしています。256bit=32バイトのベクトルレジスタ4本(%VEC(0)～%VEC(3))を使ってコピーするので、ループ1回で32×4=128バイトコピーします。

```c:sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S
- 中略 -
# define VEC_SIZE       32
# define VMOVU          vmovdqu
# define VMOVA          vmovdqa
- 中略 -
ENTRY (MEMMOVE_SYMBOL (__memmove, unaligned_erms)) # __memmove_avx_unaligned_erms の関数シンボル作成
- 中略 -
L(loop_4x_vec_forward):
        /* Copy 4 * VEC a time forward.  */
        VMOVU   (%rsi), %VEC(0)               # 32バイト読み取り
        VMOVU   VEC_SIZE(%rsi), %VEC(1)       # 次の32バイト読み取り
        VMOVU   (VEC_SIZE * 2)(%rsi), %VEC(2) # 次の32バイト読み取り
        VMOVU   (VEC_SIZE * 3)(%rsi), %VEC(3) # 次の32バイト読み取り
        addq    $(VEC_SIZE * 4), %rsi
        subq    $(VEC_SIZE * 4), %rdx
        VMOVA   %VEC(0), (%rdi)               # 32バイト書き込み
        VMOVA   %VEC(1), VEC_SIZE(%rdi)       # 次の32バイト書き込み
        VMOVA   %VEC(2), (VEC_SIZE * 2)(%rdi) # 次の32バイト書き込み
        VMOVA   %VEC(3), (VEC_SIZE * 3)(%rdi) # 次の32バイト書き込み
        addq    $(VEC_SIZE * 4), %rdi
        cmpq    $(VEC_SIZE * 4), %rdx  # もうおしまい？
        ja      L(loop_4x_vec_forward) # 残ってるならば、ループ先頭に戻る
```


## IntelのOptimizationi Manualによる解説
readではrep movsb、mmap後のmemmoveではAVX命令を使っていました。どちらが早いのか、机上検証してみましょう。

Intelは、処理を早くするには、どう書けばよいかというマニュアルを出しています。
https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf

これの p.184 (3-66) Table 3-5に、第3世代Coreプロセッサであるivy bridge(2012年)でのrep movsbと128bit AVXとの速度比較があります(図1)。サイズが大きい時は、rep movsbの方が早いとあります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/695115/779d1852-8555-be85-848c-d6e75780ed1d.png)
図1: IIntel® 64 and IA-32 Architectures Optimization Reference Manual p.184 (3-66)より引用

一方、先ほど見たmemmoveでは256bitの AVX命令を使います。2020年時点での最新のIntelのチップは第10世代CoreプロセッサComet Lake です。マニュアルでの環境とは大分違います。実際、Gigazineの記事ではrep movsbよりも256bit AVXの方が早いです。

今回は同期I/Oを調べましたが、非同期I/Oを使ってディスクI/O待ち時間を隠蔽し、スループットを向上させると結果が変わるかもしれません。

いずれにせよ、個人的な感触としてはreadとmmapどちらが早いという事は一概には言えず、CPUの進化により、どちらが早いかが変わり得る、というのが答えだと考えています。

## 商標
- Windowsは，米国Microsoft Corporationの米国およびその他の国における登録商標または商標です
- Linuxは、Linus Torvalds氏の日本およびその他の国における登録商標または商標です。
- Intel Core は、アメリカ合衆国および／またはその他の国における Intel Corporation の商標です。 
- 記載の会社名、製品名、サービス名等はそれぞれの会社の商標または登録商標です。