🏊‍♂️

ファイルディスクリプタから1行ずつ取得する関数

2021/08/12に公開約6,200字

ソースコードはここ.

https://github.com/tkoyasak/42-get_next_line.git

課題

渡されたファイルディスクリプタ(fd)からデータを読み込み, 関数を呼び出すごとに1行ずつ (改行文字は含む) 返す関数を作成する.
1度の読み取りは, コンパイル時に定義される定数(BUFFER_SIZE)バイト分だけ行うこと.

プロトタイプは以下のようにすること.

char	*get_next_line(int fd);

使用可能な標準Cライブラリで定義されている関数は以下の通り.

  • read
  • malloc
  • free

課題の目的としては以下の2つとのこと.

  • ライブラリとして使用できるような汎用性の高い関数を実装する
  • C言語におけるstatic変数を学ぶ

提出ファイル

  • get_next_line.c
  • get_next_line_utils.c
  • get_next_line.h

コンパイルは以下のように行う.

$ gcc -Wall -Wextra -Werror -D BUFFER_SIZE=xxx <file>.c

実装

2パターン (A・B) の実装を行なった.
読み込んだ文字列のうち返り値に含めなかった改行以降の文字列を, char *型のstatic変数memoで次回関数が呼ばれたときのために保存している.

static char	*memo;

実装の簡単な流れとしては, 以下の通り.

  1. *memoの中に改行は含まれるか?
    • いいえ → 2.へ
    • はい → 4.へ
  2. ファイルを読み込む. 読み込んだ文字列は, char *型の変数bufに格納される.
  3. 読み込んだbufの情報を保持する.
    • 実装A 文字列memobufを連結して, memoに再代入する.
    • 実装B 1.におけるノードの次となるノードを作成し, bufをノードのメンバ (memo) として保持する.
    • 実装A・実装B → 1.へ
  4. 改行文字までを返り値に設定する. 改行以降はmemoとして保存する.

実装A (src1)

読み込んだbufmemoの連結を先にすることがポイント. 改行のチェックは常にmemoの中を見れば良いことになり, 返り値の処理が1パターン(memoを分割)で良くなる.
マイナス要素は, 文字列memoの先頭に近いほどreadが行われる度に同じコピーが繰り返されるため冗長であることが挙げられる.

実装B (src2)

線形リストを用いて実装を行なった. ノードのメンバは以下の通り.

typedef struct s_node
{
	char		*memo;
	size_t		memo_len;
	char		*point_newline;
	struct s_node	*next;
}	t_node;
  • memo : 読み込んだbufまたは改行以降の文字列が代入される.
  • memo_len : 文字列memoの長さ. readの返り値を代入する.
  • point_newline : memoの中の改行の位置を示す. 改行が含まれなければ, NULLが代入される.
  • next : 次のノードを示すポインタ.

読み込んだbufmemoとしてそのまま保持する. またreadの返り値をmemo_lenとして保持しておくことで, 返り値作成の際に文字列の長さを数えるのが容易になる.
マイナス要素は, readを行う度に新たにbufとノードの領域確保を行うためmallocを呼び出す回数が多くなってしまうことが挙げられる.

実装C (src3)

この課題には, ボーナスが設定されている. 複数のfdに対応すること, である.
例えば, fd=3, fd=4, fd=3, fd=5と渡されたら, 順にfd=3の1行目, fd=4の1行目, fd=3の2行目, fd=5の1行目と返せるようにしましょう, ということ.

実装A, 実装Bでは, 以下のようにlimits.hに定義されたOPEN_MAXという同時にオープンできるfd数の上限値を定めているマクロを用いて, 配列で対応した.

static char	*memo[OPEN_MAX + 1];

実装Cでは, 線形リストを用いて実装した. 新しいfdが渡されたとき, 動的に確保して, 線形リストに連結して情報を保管する, という流れ.
static変数の宣言は以下のように, 線形リストの先頭を示すポインタを宣言する.

static t_fbuf	*head_fbuf;

また, ノードのメンバは以下の通り.

typedef struct s_fbuf
{
	int		fd;
	char		*memo;
	struct s_fbuf	*next;
}	t_fbuf;

ただ, 以下の検証には含めていない.

比較と検証

JUNさんの記事がとても勉強になった.
大まかな比較・検証だが, 実行したことをつらつらと書いていく.

実行環境は以下の通り.

  • Ubuntu 18.04.4

テスト用の関数は以下の通り.

test.c
#include "get_next_line.h"
#include <fcntl.h>

int	main(int ac, char **av)
{
	(void)ac;
	int	fd = open(av[1], O_RDONLY);
	char	*str = get_next_line(fd);
	while (str)
	{
		free(str);
		str = get_next_line(fd);
	}
	close(fd);
	return (0);
}

テスト用のテキストファイルは以下のコマンドで作成した. ファイルサイズは10MBとなった.

$ base64 /dev/urandom | head -c 10381941 | fold -w 100 > text.txt

BUFFER_SIZEによる実行時間の変化

実行時間については以下コマンドを実行した.
また, vオプションでプロセスの最大メモリ使用量が調べられるとのこと.

$ gcc get_next_line.c get_next_line_utils.c test.c -o test -D BUFFER_SIZE=xxx
$ time -v ./test text.txt

実装Aの結果は以下の通り.
|BUFFER_SIZE|実行時間[s]|最大メモリ使用量[kB]|
|---|---|---|---|
|1|7.04|1384|
|16|0.56|1316|
|64|0.21|1464|
|128|0.17|1324|
|256|0.17|1412|
|512|0.21|1336|
|1024|0.33|1392|
|4096|0.90|1360|
|65536|12.49|1568|
実装Bの結果は以下の通り.

BUFFER_SIZE 実行時間[s] 最大メモリ使用量[kB]
1 5.09 1312
16 0.40 1312
64 0.15 1312
128 0.11 1312
256 0.09 1352
512 0.12 1324
1024 0.17 1440
4096 0.31 1448
65536 3.97 1600

実装Aに比べて, 実装Bはめっちゃ速い!!!
以下プロファイルツールを用いて, 要因を探っていく.
また, BUFFER_SIZEを見ると256のときが最も速かった.

BUFFER_SIZEによるreadの呼び出し回数の変化

readのコール回数については以下コマンドを実行した.

$ gcc get_next_line.c get_next_line_utils.c test.c -o test -D BUFFER_SIZE=xxx
$ strace -ce trace=read ./test text.txt

結果は以下の通り.

BUFFER_SIZE read呼び出し回数
1 10381944
16 648875
64 162221
128 81112
256 40558
512 20281
1024 10142
4096 2538
65536 162

プロファイルツールを用いたボトルネックの特定

gcc付属のプロファイルツールgprofなるものがあるらしい.
各関数の呼び出し回数や消費時間を計測できるとのこと. 便利だ.
以下コマンドを実行した.

$ gcc -pg get_next_line.c get_next_line_utils.c test.c -o test -D BUFFER_SIZE=xxx
$ ./test text.txt
$ gprof ./test

BUFFER_SIZEにおける最も消費時間の大きかった関数を示す.
実装Aの結果は以下の通り.

BUFFER_SIZE 関数 呼び出し回数 消費時間[%] 消費時間[s]
1 gnl_strchr 10516773 33.87 0.60
16 gnl_strchr 783704 59.21 0.13
64 gnl_strlen 459266 62.63 0.05
128 gnl_strlen 297048 58.45 0.07
256 gnl_strlen 215940 41.26 0.07
512 gnl_strlen 175386 57.26 0.08
1024 gnl_strlen 155108 60.12 0.12
4096 gnl_strlen 139900 60.73 0.40
65536 gnl_strlen 135148 63.56 6.22

実装Bの結果は以下の通り.

BUFFER_SIZE 関数 呼び出し回数 消費時間[%] 消費時間[s]
1 read_fd 10516773 57.23 0.12
16 set_return_value 134832 100 0.01
64 gnl_strchr 297050 75.11 0.03
128 gnl_memcpy 215939 50.07 0.02
256 gnl_strchr 175387 25.04 0.01
512 gnl_strndup 134830 70.10 0.07
1024 gnl_strndup 134830 75.11 0.09
4096 gnl_strndup 134830 75.11 0.18
65536 gnl_strndup 134830 99.59 3.59

実装Aは, BUFFER_SIZEが大きくなるにつれてgnl_strlenの消費割合が大きくなった.
gnl_strjoinset_return_valueで必ずgnl_strlenが2回よばれる実装なので, それが積み重なって消費割合が大きくなったと考えられる.
自作strlenがネックとなるとすると, 実装Bのようにstrlenを使わずreadの返り値を利用する方法が得策と思われる.

実装Bの実行速度が速かったのは, readの返り値をノードのメンバとして保持しておくことで, 実装Aでネックとなったgnl_strlenを使用せずとも実装できたためと推定できる.
実装Bのボトルネックは, gnl_strndupとなった. この中で2ステップ(malloc/memcpy)を行うため, 時間がかかると思われる.

最後に

get_next_lineにかけた時間は, 総じて80時間ほどとなった. ライブラリとして利用できる汎用性の高い関数なので, 時間をかけて結果的に高速化できたのはとてもためになったと思う. 検証については, 前述の記事をなぞる形となったがプロファイルツールなど新しいことを学べて楽しかった.

2パターン書こうと思ったのは, 実装Aを提出したレビュー (42におけるコードレビュー) において指南を受けたためである. readで読み込んだbufをそのまま保持しておけば効率いい, なるほどと思った. 構造体を用いたためreadの返り値を利用して, strlenを使わずに実装することもできた.

ただ実装Bについては, コードレビューも MOULINETTE (42の自動採点システム) もパスしていないので, どこかでミスがあるかもしれない. 何か気づいたら投げていただけると助かります.

参考

https://jun-networks.hatenablog.com/entry/2020/12/18/100541
https://minus9d.hatenablog.com/entry/20140112/1389502918
https://qiita.com/awrznc/items/161b55c29e6596431ca4

Discussion

ログインするとコメントできます