第三回 トリグラムのインデクサ、ToyIndを作ろう

大規模な全文検索のためのインデクサだけれど仕様が簡単になるようにいろいろ制約はある、ToyIndを作ろう。

01. 全文検索入門

全文検索システムとは、大量のファイルがあって、その中から特定の単語やフレーズなどが含まれているファイルや行を高速で探すソフトウェアの事です。 Luceneやそれの上に作られたElasticsearchなどが有名です。

文字を検索するだけならファイルを順番に開いて先頭から文字を探していけば良いのですが、これでは全ファイルサイズに比例した時間がかかってしまいます。そこで全文検索システムというと、普通はインデックスと呼ばれる仕組みで、全ファイルをなめずに検索を可能にするものを指します。

逆に言うと、データが多くなければ単なるgrepになってしまうので、全文検索システムというと対象となるファイルやデータが巨大である事が前提となります。

インデックスとトリグラム

例えば「print」という単語で検索する事を考えます。ファイルが20万ファイルあったとして、一つのファイルを検索するのに0.05秒かかるとすると、1万秒もかかってしまいます。ですが、printという単語が入っているファイルは実際はもっとずっと少ない、例えば100ファイルとかだった場合、5秒程度で済む事になります。この、目的の単語が含まれているファイルの数は全体に比べて少ない、という事に着目したのが、インデックスのアイデアとなります。

ですが、単純にすべての単語に対してその単語が含まれているファイルの一覧を作る場合、例えばprintlnなどのように他の単語の中に入っている単語をどう扱うか、という問題が出てきます。 printlnという単語で調べれば引っかかるけれど、検索としてはprintで検索しても引っかかって欲しい。

そこでより単純に、n-gramという方法でインデックスを作るのが一般的です。例えばn=3の場合をトリグラムと呼び、この第三回で作るものもトリグラムの予定なのでトリグラムの説明をしましょう。

printlnという単語があったとします。これを3文字ずつに分割してインデックスを作る、というのがトリグラムのアイデアです。

具体例を挙げましょう。hoge.txtというファイルにprintlnという単語があったとします。そうしたら、pri, rin, int, tlnに分けて、それぞれに対してhoge.txtにあったぞ、という情報を記録します。

printという単語を検索する場合、最初のpriのインデックスを引いて対象のファイルを絞り込み、あとは1ファイルずつ開いて検索していきます。当然priが入っているがprintが入ってないファイル、例えばpriorityとか入っているファイルも検索の対象になってしまいますが、少し考えれば変に偏る特殊なトリグラムを除けばかなり絞れる事が分かると思います（ユニフォームに分布してて大文字と小文字を区別して数字も入れると何分の一に絞れそうか計算してみてください）。

一般的にはn-gramのインデックスはunigram、bigramを用意して、さらに必要だったらtrigramくらいを用意するのが一般的ですが、この第三回では単純化のためにトリグラムだけのインデックスを作る事にします。プロジェクトの名前はToyIndとしましょう。

trigramでは2文字や1文字では検索出来ない事になりますが、そこは勉强目的のおもちゃなので3文字以上の単語しか検索出来ないと割り切ります。

基本的な前提と仕様

このシリーズは基本的には「学びの少ない機能は徹底的に削る事で学習の費用対効果を最大にする」というコンセプトで、なるべくいろいろな事を割り切るようにしています。

ですが、全文検索の説明でも言ったように、インデクサは規模が小さいとただのgrepで十分なので何を作っているのか意味がわかりません。そこで、ToyIndは対象となるファイル数はかなり多いとします。想定しているのはLinuxのカーネルやWebKitなどの大規模なオープンソースのコードを対象にしようかな、と思っていますが、英語主体で取り回しが大変なほどの規模じゃない対象で入手が簡単なものだったらなんでも良いとは思っています。 (別に自然言語でも良いのですが、Wikipediaは経験上少し大きすぎてファイルを持ってきたり展開するのが大変なので、もうちょっと小さい手頃なのがいいかな、とは思っている)。

また前提として、すごく大きなファイルが混じっていたりはしない、という事にします。一つのファイルを開いて先頭から調べるのはそれほど時間はかからない、という想定。中身はだいたい英語だが英語以外も混ざっている、という対象とします。

トリグラムの対象となる文字としては、[a-z], [A-Z], [0-9] のトリグラムをインデックスにする事にし、それ以外の文字はインデックスには含めません。

インデクサは最初に全部のインデックスを作り、そこから新しくドキュメントが追加されたりはしないとします。

実際の具体的な仕様は実装を進めていく中で解説を追加していきます。

ToyIndの基本構成

ToyIndは大きく２つの機能からなります。

ファイル名からidへのマップ、及びidからファイル名へのマップ（文書内ではファイルインデックスと呼ぶ）
トリグラムからid listへのマップ（トリグラムインデックスと呼ぶ）

idはUInt64。

上記２つの機能があった時、ある単語を検索するのは、以下の3ステップで行う事が出来ます。

トリグラムからファイルidを取り出す
ファイルidからファイルパスを取り出す
ファイルを開いて検索

そこで、この第三回ではファイルインデックスとトリグラムインデックスを様々な方法で実装しては比較していく、というのが基本的な作業となります。

最初はこれらを手抜きで実装して全体を動かし、それで規模を増やすとどういう問題が出てくるのかを見る事から始めます。

初期の実装方針

ファイルインデックスもトリグラムインデックスも、それぞれ独立して実装出来て、かなり実装の選択肢も多く時間をかけて実装が出来ます。そこでこうしたそれぞれがそれなりに大きなシステムを作る場合、進め方にはいくつかの自由度があります。

今回はなるべく早く全体を結合して動かし、そのあと全体を動かしつつ個々のモジュールを改善していくのを目指しましょう。

Big Bang IntegrationとEvolutionary Delivery

それぞれのモジュールをバラバラに作りこんで、最後にえいっとインテグレートするのをビッグバンインテグレーションと言います。一方でなるべく早くインテグレーションを行い、それを継続的に更新していくのをevolutionary deliveryと呼びます。

ある程度の規模になるとevolutionary deliveryを行うメリットがとても強くなるので、なるべくプロジェクト開発も早期のインテグレーション、早期のイテレーションを目指すのが良いでしょう。現実では組織の壁などでなかなか早期のインテグレーションが難しい事もあるので、かなり意図的にプロジェクトを進めないとそうはなってくれない事も多くあります。

なるべく早く結合するといっても個々のモジュールが動いている必要はあり、それらを動かすのもそれなりに大変な作業になります。そこで実装する時には、「なるべく簡単にハリボテを作るには、どういうハリボテにするのが良いか？」という事を頑張って考えていくとともに、「最初に全体を動かすにはどこから進めていくのが良いか？」という事を考えていく必要もあります。

この第三回ではこの辺の事を考えるのは私の作業になってしまいますが、そうした視点で最初に作りたいと説明したものと実際に作るものの違いなどを見ていくと、この辺の努力が分かるかもしれません。

02. 全部のファイルを開いて検索、を実装する

最初はインデックス無しで検索するコードを書いてみます。これを基本として他の方法と比較していきます。

最初に作るものの概要

単語とディレクトリを指定すると、そのディレクトリ以下のファイルを開いて単語を探し、単語があったら、「パス名:その行」という表示をするプログラムを作ります。正規表現の無いgrepのようなものですね。

例えば以下のような出力です。

./test_data/ZipSourceCodeReading/Write.kt:        DataOutputStream(BufferedOutputStream(FileOutputStream(postIndexFile))).use {

また、拡張子でテキストっぽく無いものはスキップするようにします。具体的には .png とか .jpg とかです。

プロジェクトの作成と基本的なコードを書く

まずプロジェクトとしては第二回のToyRelの時と同様、ToyIndという名前でsourcesの下に作ります。ブランチとしてはtoyindでいいでしょう。

対象とするディレクトリの指定はとりあえずグローバル変数かなにかに書いておくのが良いと思います。 Scratch.fsxからもProgram.fsからも出来る感じにしておいてください。

まずは指定ディレクトリの下のファイルのすべてに対して、一行ずつ読んでマッチするか調べるのがいいと思います。

ファイルやディレクトリを操作するには、DirectoryInfoやStreamReaderを使っても良いのですが、スクリプト的にF#を使っている時はFileやDirectoryを使う方がいいでしょう。

この辺は Common I/O Tasks - Microsoft Learnが良く書かれています。

今回だったら、

あたりが良いでしょう。

ストリームとパイプライン

F#はパイプラインを使うのが便利な言語で、皆もパイプライン演算子をここまで使ってきた事でしょう。

パイプラインと組み合わせるのに都合の良いデータ構造としてストリームがあります。F#で言う所のseqやlistですね。いろいろな機能をストリームとして返すと、いろいろな演算が使えて便利です。

例えば今回のように、ある特定のディレクトリ以下の全ファイルに対してなにかをやりたい、としたとします。その時に、例えばDirectoryInfoでは以下のような感じでそのディレクトリの直下にあるディレクトリの一覧やファイルの一覧が得られます。

let di = DirectoryInfo("./")
di.EnumerateDirectories()
di.EnumerateFiles()

これを使えば、一番上のディレクトリから始めて、まず自身のディレクトリ内のファイルを処理したあとに、自身の直下のディレクトリそれぞれに対して再帰的に同じ事をする、というコードを書く事が出来ますし、何も考えなければそう書く人は多いでしょう。

でも少し切り口を変えて、指定されたディレクトリの下の全ファイルをseqとして返すような関数を作り、それを使うように書くと、そうした再帰のコードの中にロジックが埋め込まれて再利用しづらいものよりも、ずっと見通しも良く書けて、他の所でも再利用出来たりします。

このように、問題を分割する時にseqを返す関数とそれに対してmapしたりfilterしたりといった事で処理する部分に分ける、というのは探してみるとすごく多くの問題に対して出来るものです。再帰やループで書きたくなるような問題を前にした時は、少し「ストリームにする事でアクション的な処理を外に出せないかな？」と考えてみるのは有益です。

FileやDirectory系のAPIはFileInfoやDirectoryInfoに比べてだいぶ最近に書かれたものなので、そうした視点で見るといろいろと参考になる事も多いと思います。

なお、ストリームに関しての処理を探したい時は、まずChoosing between collection functions · F# for Fun and Profitから探してみて、これで見つからない時にはじめてSeq (FSharp.Core)などを探すのが良いと思います。最初に後者のドキュメントや適当にぐぐったものを見てもなかなか欲しいものが見つからないので、まずFun and Profitの方を見るのがコツです。

テストデータにfparsecのソースを試してみる

一番簡単な全文検索のプログラムが出来たので、これで様々なサイズのファイル群を検索してみてどうなるか見てみましょう。

まずは比較的小さな規模として、FParsecのコードなど検索してみましょう。 githubからコードを取得し、特定の場所に置きます。

とりあえずToyIndのディレクトリの下にtest_targetというディレクトリを掘り、そこに置く事にします。つまり souces/ToyInd/test_target/fparsec というディレクトリの下にfparsecのコードを置く感じですね。

test_target以下は.gitignoreに加えてコミットしないようにしておいてください。また、検索の対象としては.gitなどの不要なディレクトリは削除しておいてください。 VSCodeでtoyindのディレクトリを開く時に変にロードされてしまう事もあるかもしれないので、 fsprojやslnなどのファイルも必要に応じて削除してしまいましょう。

基本的な計測を行う

検索対象を置いたら、まずファイル数や行数をなんとなく調べておきます。

$ find . -type f | wc -l
     175

$ find . -type f | xargs wc -l
...
   74443 total

$ du -h
...
11M

という事で、175ファイル、74K行、11MBくらいのようです。 timeコマンドで時間を図っていましょう。 pipe3という単語をagやgrepで調べてみます。

Mac版だとgrepに -R オプションが使えますが、これは環境によっては使えないかもしれないので他の方法で調べてみてください。

$ time ag pipe3
...
ag pipe3  0.02s user 0.02s system 99% cpu 0.040 total

$ time grep -R pipe3
...
grep -R pipe3  0.16s user 0.01s system 99% cpu 0.173 total

agだと20msec, grepだと160msecくらいでしょうか。

メモリ使用量も測るバージョンのtimeが /usr/bin/time の方にあるのが普通です（何もつけないtimeはshの組み込みコマンドだったりする）。自分の手元のMacだと-lのオプションを使う事でメモリ使用量が測れるようです。

$ /usr/bin/time -l ag pipe3
...
        0.03 real         0.01 user         0.02 sys
             3727360  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
                2984  page reclaims
                  26  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                   0  messages sent
                   0  messages received
                   0  signals received
                  10  voluntary context switches
                 160  involuntary context switches
            76502781  instructions retired
            57790386  cycles elapsed
             3231744  peak memory footprint

$ /usr/bin/time -l grep -R pipe3
...
        0.20 real         0.15 user         0.01 sys
             1396736  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
                 471  page reclaims
                   0  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                   0  messages sent
                   0  messages received
                   0  signals received
                 251  voluntary context switches
                  12  involuntary context switches
          1560448993  instructions retired
           657863973  cycles elapsed
              974848  peak memory footprint

とりあえずpeak memory footprintに相当するメモリ量と、realの時間を計測する事にしましょう。単位は好きにしてください。

この/usr/bin/timeのアウトプットは使っているOSで結構変わる所と思います。 Linux系列だとフォーマットを指定したり出来るはず。そういう機能が無い場合は適当なシェルスクリプトなどでrealの時間とメモリ量を抜き出すスクリプトを作ってください。

出力としてはcsvでいいでしょう。以下のような感じでためていける感じにしたい。

label, time, memory
fparsec_ag, 0.03, 3231744
fparsec_grep, 0.20, 974848

同様に、上で書いたfsでの検索の時間なども調べて時間を教えて下さい。 Unix系の環境だったらfsのコードも同じように測ればいいでしょう。

調べる時はReleaseモードで、しかもビルドは別に行う方がいいでしょう。つまり、例えば以下のような感じです。

$ dotnet build -c Release
$ /usr/bin/time -l  bin/Release/net6.0/ToyInd

Windowsでは以下に示すBenchmarkDotNetで測るのがいいと思います。

BenchmarkDotNetで時間とメモリを計測する

F# 上でメモリと時間を測るなら、BenchmarkDotNetを使うのが手頃に思います。これは本来はベンチマーク計測用プログラムなので用途が違いますが、簡易な計測にも手頃なのでこれを使う事にしましょう。

いつものように以下のようにパッケージを追加し、

$ dotnet add package benchmarkdotnet

以下のような感じで一回だけのテスト結果が表示されます。

open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running
open BenchmarkDotNet.Jobs
open BenchmarkDotNet.Engines

[<SimpleJob (RunStrategy.ColdStart, targetCount=1)>]
[<MemoryDiagnoser>]
type ProductBench() =
  [<Benchmark>]
  member _.Product() =
     // ここにテスト対象のコードを書く
     runAll ()


[<EntryPoint>]
let main _ = 
  BenchmarkRunner.Run<ProductBench>() |> ignore
  0

これでコマンドラインから以下のように実行する。

$ dotnet run -c Release

これで表示されるMeanとAllocatedで良いでしょう。たぶんちゃんと調べればこれらの値を取得する方法もあるはずなので、誰か調べてPRください。

規模の違うデータセットをいくつか用意する

簡単に持ってこれて取り回しが大変なほどはでかく無い程度の大きなデータセットを追加する。

fsharpのコンパイラ等 dotnet/fsharp: The F# compiler, F# core library, F# language service, and F# tooling integration for Visual Studio
mongodb/mongo: The MongoDB Database
Elsevier open access articles

名前	ファイル数	行数	duのバイナリサイズ	grepの時間
fparsec	175	74443	11M	0.22
fsharp	10452	442042	127M	2.57
mongo	37155	534676	573M	12.07
elsevier	40098	7266898	7.1G	?

他にllvm、Chromium、Linuxカーネルあたりとかどうだろう。誰か調べて表に追記したりリンク足したりしてください。 2〜3GBくらいのが欲しい気はする。grepで数分掛かるくらいの。

なお、ソースコードじゃなくても手頃な英文テキストがあるならそれでもいいです。ダウンロードが簡単で検索が興味が湧くものがあればいい。日本語Wikipediaくらいのサイズの自然言語のなにかがあればいいかなぁ。

（Elsevierという科学論文の出版社が公開している論文のデータセットを追加しました。検索した単語は”higgs”です。）

またこれらのデータセットに検索を試す手頃な単語も調べておいてくれると。だいたい数件程度のヒットがあるようなのが理想ですが、あまり多すぎなければOKです（consoleへの出力の時間が問題になるようなのは測りたい事が測れないので）。

fparsecならattempt、fsharpならgenerics、mongoならpagingとかでどうでしょう？

03. ファイルインデックスをオンメモリで実装してみる

ベースラインとなるものが出来たら、次はインデクサと、それを用いた全文検索を作ります。全文検索は最初に書いた通り、大きく以下の２つのモジュールが必要です。

ファイルパスとidのマップ
トリグラムとidのインデックス

本題は2なので、まずはなるべく手抜きで1を実装する事を考えます。

1を便宜上ファイルインデックスと呼ぶ事にします。

満たしたい要件を考える

まず大前提として、同じパスでは同じidが返ってきて欲しい。あるパスに一度idを降ったら、次以降はそのパスで引くと同じidを返して欲しいです。

例えばファイルの一覧を取得するAPIでは、別のファイルシステムにコピーした場合などには順番が変わるかもしれません。そこで最低ラインとして、最初に一度降った対応関係は覚えておく必要があります。

一度idとの対応関係を作ったら、そのあとにファイルが追加される事は気にしなくてOKです。

この対応関係は、対象ごとに作りたい。具体的にはfparsec用のマップ、llvm用のマップ、など。そこでtest_target以下のディレクトリ名と対応する形で、test_indexというディレクトリの下に作る事にしましょう。

例えば、以下のターゲットに対しては、

souces/ToyInd/test_target/fparsec

以下の場所にファイルのパスとidのマップの情報を書きます。

souces/ToyInd/test_index/fparsec

idはfparsec内で一意になるようにし、fparsecの1とllvmの1は別のパスを表す事にします。

保存のフォーマットを考える

まずはメモリ上にすべてのパスを持つ事にします。一度降ったidがそれ以後保証されるように、ファイルにパスのリストを書いて、その先頭からのインデックス（一番最初を1とする）をidとする、でいいでしょう。

こうした時にどういうフォーマットを選ぶのか、というのは自由度がありますが、まずはテキストファイルで、一行一パスの行指向のフォーマットが良いでしょう。 Unixのツールは行指向のテキストファイルに向いたものが多く、このフォーマットなら grep -n などを使って簡単に確かめる事も出来ます。

ファイル名はpath_list.txtとしましょう。つまり、 test_target/fparsec のファイルインデックス用のデータは test_index/fparsec/path_list.txt に保存する事にします。

createFileIndexでこのファイルを作り、loadFileIndexでこのファイルを読み込んでこの各行をキー、その行数をvalueとするdictを作ります。

そしてこのdictに対してlookupFileIdみたいな関数でパスからidをlookupできるようにしましょう。

簡単に計測しておく

この手抜き実装ではファイルのパスをすべてメモリに持つ必要があるため、ファイル数が増えていくとだいたい線形に消費メモリが増えていく事が予想されます。それを確認しておきましょう。

以下を計測して、どのくらいの規模まではこの実装で行けそうかを確認します。

path_list.txtを作るのにかかる時間
path_list.txtのファイルサイズ
path_list.txtをロードしてlookup一回するのに掛かる時間とメモリ
path_list.txtをロードしてlookupを1000回するのに掛かる時間（ロードの時間を引いてlookupの時間が概算できる程度の回数。試してみてもと適切な回数があればフィードバックください）

これらがターゲットの規模を増やすとどう増えていくかを調べてみてください。（レポジトリにcsvとかmdで記録するか、google spread sheetとかで記録してgitterにはるかしてください）。

04. トリグラムのインデックスを作る

次にトリグラムのインデックスを作ります。トリグラムに対して、それのあったファイルのidのリストが返ってくるようなデータ構造を作りたい。

仕様としてはa-z, A-Z, 0-9 くらいをターゲットとします。数字が居るかは微妙ですが。

Unix的にディレクトリをDBとして使う

今回はトリグラムのうち、最初の1文字をディレクトリ名にしたいと思います。そして続きの2文字をファイルのbasenameとする。ただしMacなどでは大文字と小文字のディレクトリ名がデフォルトでは同一視されてしまうので、大文字はアンダースコアで始まるとしましょう。

例えばJclというトリグラムなら、ディレクトリは_j、ファイルはcl.txtとします。

ファイルの中は、最初は一行一idで、テキストで数字を書いていきたいと思います。

こうしたプレーンなテキストファイルとディレクトリを使うのは、デバッグのしやすさや開発のしやすさなどメリットが大きい。このディレクトリとプレーンテキストを使ったシステム開発は使える所も多いので、基本的な考え方を学んでおきましょう。

一つのディレクトリにファイル数が2万を超えるといろいろとオーバーヘッドが目立ってくる傾向にあるので、仕様を考える時には一つのディレクトリにファイル数がそこまで多くならないように考えるのが大切です。今回のケースですと、トリグラムは(26*2)+10の3乗なので、全てをファイルにすると2万ファイルよりも多くなりそうです。一方で最初の一文字でユニフォームにばらければ3844ファイルなので、多少偏りがあっても2万ファイルくらいには収まりそうです。収まらなければ最初二文字でディレクトリを作ったりします。

Unix的なディレクトリとテキストファイルの使い方

今回紹介したようなディレクトリとテキストファイルを使うシステムというのはUnixではちょくちょく見られます。古くはterminfo(Studying Casesに詳しい)などが有名で、 /usr/share/terminfo/の下をlsすると雰囲気はわかります。

最近ではgitがこのようなディレクトリをDB的に使う事で有名です（Git - Git Objectsに詳しい）。 gitはハッシュを求めてその最初二文字をディレクトリに、残りをファイル名に使います。 .git/objects/ 下や、そのディレクトリの一つを選んでさらにその中をlsしてみると雰囲気は分かると思います。

後半ではこれと似たような手法でファイルインデックスの方もディレクトリにしたいと思います。

Unix的なファイルの使い方にはいくつか特徴があります。

テキスト指向：4バイトの数字は4バイトのバイナリの方が容量は少なくて済みますしパースも必要無いのでロードも早いですが、それよりもテキストの拡張性と開発用意生を好む。
行指向：ファイルのidのリストを保存する場合、カンマ区切りで一行に収めるよりは、一行一idにして別々の行にする方を好む。
ディレクトリに分けてスケールさせる：先頭の文字などでディレクトリを分けて各ディレクトリ内のエントリの数はそんなに多くならないようにディレクトリで分ける。

テキストにしておけば、4バイトでは足りなくなった時も既存のデータは変更の必要がありません。また、バイナリデータよりも少しパースに手間がかかります。

こうした無駄は実際には問題になる事は少なく、その代わり得られる開発や保守の容易さは非常に大きいので、まずはUnix的なテキストとディレクトリから始めて見て、あとで問題になったら他の手段に差し替えるというのは良い進め方です。実際gitがこれだけ使われている事を思えば、この手法が最初思うよりもずっと本格的なシステムの運用に耐える事が分かるでしょう。

この第三回でUnix的なファイルやディレクトリの使い方を体験しておきましょう。

05. もう少し真面目に計測環境を整える

トリグラムのインデクサが出来てそれを用いた検索を実装出来たら、用意した様々な規模のデータセットで試してみましょう。そうすると、すごく遅かったりすごくメモリを食ったりすると思います。

ここではそれを確認しつつ、問題となる場所を探してみましょう。

プロファイラを使ってもいいのですが、fsharpはいまいち良いプロファイラが無く、特にMac上では手頃なのが無い。という事で割とWindows以外を使っている人も多いfsharp-lessonとしては、自分で簡単な計測環境を作る事にします。実際こうした計測環境を作るのも実務では良くあるので、一度作っておくのも良いと思います。以下では自分が良くやる計測方法を実装してみます。

いくつかの規模で検索してみる

用意したデータセットに対して、最初に作った全部開く検索とトリグラムを使った検索の時間や使用メモリなどを比較していきましょう。ついでにインデックスのサイズや作成に掛かる時間も記録します。

ある程度以上の規模だとすごく時間が掛かるようになると思うので、使い物にならないくらい遅い所まで確認出来たら、それより大きいサイズの計測はしなくて良いです。

実行時間記録の仕様

基本的にはストップウォッチのようなものを作ります。測りたい所の最初でbeginをし、終わる所でendをする訳ですが、それを様々な場所で計測してききたいので、文字列のidでそれぞれの計測を指定出来るようにします。

とりあえずMeasureというモジュールのbeginとendで計測するとすると、

Measure.begin "インデックス作成"
// 何かのコード
Measure.end "インデックス作成"

というような事をすると、このbeginとendで挟まれた間に掛かる時間が記録されるとします。また、普通は一つの関数は何度も呼ばれるものなので、その中の特定の場所の時間を測ろうとすると、複数回呼ばれる事になります。記録するのは時間の和と回数とします。

文字列の引数の役割を満たすべく、以下のようなケースを考えてみましょう。

Measure.begin "１つ目"
// 何かのコード1
// 何かのコード2
Measure.begin "２つ目"
// 何かのコード3
Measure.end "１つ目"
// 何かのコード4
Measure.end "２つ目"

この時は、”１つ目”の時間は

何かのコード1
何かのコード2
何かのコード3

となるのが期待値です。

“２つ目”は、

何かのコード3
何かのコード4

となるのが期待値です。

回数は、以下のように同一のキーで複数回呼ばれた時に、

Measure.begin "１つ目"
// 何かのコード1
Measure.end "１つ目"
// 何かのコード2
Measure.begin "１つ目"
// 何かのコード3
Measure.end "１つ目"

この場合は「何かのコード1、何かのコード3で掛かった時間の合計」と、「2回」という２つの情報が記録されるという事です。

これらはグローバル変数にmutableな辞書か何かで保存しておき、mainの最後の所で出力する形にするのがいいでしょう。

大雑把な構成

ここまでの仕様を各自が実装してもらえば良いですが、いくつか自分が想定している事もヒントとして書いておきます。

この手の計測では正確さよりも副作用の少なさが重要となります。自分だったらTickCountを使うでしょうか。

Environment.TickCount Property (System) - Microsoft Learn

記録するのは時間と回数なので、以下のようなレコード

type Entry { Time: int; Num: int }

をvalueにして、キーは文字列とした辞書をMeasureモジュールに定義して、それに記録していくと思います。

また、現在計測中の値を測るのも別の辞書として持つかもしれない。つまり、beginの時のtickを保存しておくだけの辞書。そして、endが呼ばれたらendの時のtickをbeginの時のtickから引いて、Timeに+=する感じでどうでしょうか？

どこで時間が掛かっているかを測ってみよう

これを使って、時間が掛かる所を測っていきましょう。まずいちばん上のレイヤーでどこに掛かっているかを調べて、その中で一番時間を食っている関数を見つけたらその関数の中をさらに調べていく、という感じで、2分探査的にやっていくのが良いと思います。

まずは

ファイルのマップのロード
最初からファイルIDの一覧を得るまで
各ファイルを検索する時間

あたりから測ってみましょう。

また最初に一番上のレイヤーで調べた値の合計がちゃんと前の節で測った全体の時間とだいたい一致しているかも確認しておきましょう。

時間計測で考える事

時間を計測する時に気をつけておく事をいくつか書いておきます。

まず、計測はやってみるとめちゃくちゃたくさん呼んで測りたくなります。最終的にはループの下の方などで特定の区間を知りたい、となるのが良くあるパターンですが、こういう所では数百万回のオーダーで呼ばれる事もよくあります。計測の方法を作る時には、めちゃくちゃたくさん呼ばれる事になる、というのは知っておくと良い所でしょう。

また、今言った事と矛盾するようですが、めちゃくちゃたくさん呼ばれると、正確に測るのはほぼ不可能になります。副作用が大きくなりすぎて、本当に知りたい事はなかなか簡単には測れない。これは洗練されたプロファイラが使える環境でも同様です。本当に知りたい事は、なかなか簡単には測れないものです。だから測る側でいろいろと工夫する必要が出てくる。

だから、軽くて少し不正確なTickCountを使うか、より正確に測れる高精度のTimerを使うかは、実際の所はどちらでも良い事が多いです。どちらにせよ正確に知りたい事はうまく測れないので、測る側もいろいろ工夫する必要が出てきて試行錯誤する事になります。

また、どこを測りたいかは探索的な作業で、予め何を測りたいかを決めるのは難しい事が多い。つまり最初にDiscriminated Unionなどで測るキーを全て決めるのは難しく、文字列をキーにしておく方がいいだろう、と思う所でもあります（その分mapを引くオーバーヘッドが出てしまいますが）。 beginとendでtypoするとうまく測れなかったりいまいちな所もありますが、測りたい区間は意外とキレイには指定出来ない事もあるので、結局文字列で原始的にbeginとendを指定する方が良い、というのもありがちです。

また、オーバーヘッドを測る為に簡単に空関数に差し替えられるような仕組みは入れておくといいでしょう。

第三回トリグラムのインデクサ、ToyIndを作ろう