そのOSSで注目されている機能を理解したくてコードを開くときが多いです。

大抵のちゃんとしたソフトウェアはコード規模が数万行を超えているので、毎秒1行読んでも端から読んだら1時間では終わりません。ですのでいかにコードを読まずにあたりを付けるかが鍵です。ドキュメント内でそのソフトウェア固有の単語の中から興味のあるものを抜き出し、git cloneしてその単語がある場所を検索してそれっぽい物を見つけます。後はその前後の処理を読んだり普通の事をしています。

例えば知り合いから「Redis使っているんだけどLPOPコマンドがやけに遅いんだよね、データをいっぱい入れているせいかも知れないけどコードからわかる事ある？」と調査を依頼されたとします。

Visual Studio CodeでRedisのコードを開いて「おそらくLPOPコマンドは文字列リテラルの形でコードの中に入ってるはず」とあたりを付けた上でcommand.cに該当する行を見つけます。

redisCommandTable構造体の配列に叩き込んでいるようなのでこの構造体の参照箇所をエディタに探してもらうとserver.cでserver.command構造体に登録している所が見つかるのでdictAddがどうやら文字列→void*の変換を行うdictへの登録作業だなとあたりを付けて、このserver.commandsに触っている箇所をリストアップして貰います。

lookupCommand関数でredisCommand構造体のポインタを返してもらっているのでdictの中身には立ち入らずに今度はこの関数を呼んでる箇所からそれっぽい所を探します。

するとprocessCommand関数というメインっぽい場所が見つかるのでここの処理をざっと読みます。コメントがたくさん書かれていてありがたいですね。

この関数自体は長大ですが、幸いにも大半の行がエラー処理とEarly Returnで埋まっているのでコメントを眺めながら読みすすめて行くと /* Exec the command */ とそれっぽい物が見つかるので大体の処理の流れに納得が行ったのでそこのcall関数の中でcmd->proc(c)している行を見つけて安心します。

後はLPOPの構造体のprocの箇所から参照しているlpopCommand関数から読み始めます。popGenericCommand関数の先頭操作版なんですね。コメントなどの雰囲気からどうやらlistTypePop関数に本命の処理がありそうです。

エンコーディング周りのよくわからない判定しているところはさておき、where == LIST_HEADと書いてある箇所が多分それっぽく、削除が重いというのでlpDelete関数がそれだろうなと定義へ飛びます。すると中身はlpInsertが一行だけ書かれており数秒フリーズしますがコメントをよく読むとどうやら削除も更新も挿入もこの関数の引数でスイッチして行っているようです。

異様な引数の多さといつの間にか引数の型がunsigned char*の羅列になっている事に嫌な予感を感じながらコードを読んでいくとdelete操作のときにmemmoveしている箇所を見つけます。

        memmove(dst+enclen+backlen_size,
                dst+replaced_len,
                old_listpack_bytes-poff-replaced_len);

先頭削除の場合dstはlistpackの先頭、enclen,backlenは0, replaced_lenは削除対象のデータ長,poffはヘッダ分だけのオフセットですのでよく読むと配列の先頭以外の全要素を移動しているっぽいことがわかります。listという名前だけれどlistpackは実体として単一の配列の中にデータをエンコードして埋め込む事でポインタによるオーバーヘッドの削減を行って容量の効率化をしていることがわかります[listpack.md]。つまり先頭要素を消すとリストの内部のデータ量に比例するコピーコストが掛かることがわかるので当初の質問に対して「Listに値詰め込み過ぎなんじゃないですかね？コード見た感じO(1)じゃなさそうですよ」という返事をします。

なおこの記事は適当に架空のストーリーを想定したものであって、実際にredisを使っている現場でLPOPがパフォーマンス問題にぶち当たっているかは僕は一切知りませんし、もう少しコードを読んでみたら配列のリスト等の構造を使って解決しているかも知れません。あくまで「こういう雰囲気でコードを読んでいきます」という僕のケーススタディでした。

なお一般論としては目的の関数を見つけたらそれのユニットテストを読むとか、ドキュメントを漁るとか長い関数名で検索して誰かのブログ記事が当たる事を祈るとか様々な作法があると思いますし、Chromiumぐらい巨大なものになってくるとエディタのサポートで読むのも限界があるのでCode Searchのようなサービスに依存することになります。