これについてもう少しホンキで考えてみる。
背景
ここでの話題は、TeX 処理系の内部処理における、「制御綴名からそれに対応する制御綴のオブジェクト*1への写像」の実装である。例えば、“foo”という文字列から“\foo に関する情報をもつオブジェクト”を得る、という処理を指す。
このような「文字列から（何かへ）の写像」はハッシュテーブルで実装されるのが一般的である。そして TeX 処理系（Knuth のオリジナルの実装、およびそれを拡張したもの―ー現用の処理系は全てこれに該当する）でもハッシュテーブルが使われている。その実装の効率がどうであるかを問題にしたい。
※以降では漸近的な時間計算量のみを問題にする。
データ構造と制御綴の関係をチョット述べておく
TeX 言語には配列（array）の機能がない。なので、アルゴリズムの実装において配列データ型が必要になった場合は何らかの工夫が必要になる。その一つが「制御綴を用いた擬似配列」である。（もう一つは、前回紹介した“\doリスト”のような「構造をもったトークン列を利用する方法」である。）
「擬似配列」方式においては
myArray := [
Snowman,Duck,Sushi]
という配列（変数*2）を次のように表す。((\@namedef は LaTeX の内部マクロであり、与えられた文字列を名前とする制御綴に対する \def を行う。例えば、\@namedef{foo}{...} は \def\foo{...} と等価になる。))
\@namedef{myArray/1}{Snowman}
\@namedef{myArray/2}{Duck}
\@namedef{myArray/3}{Sushi}
%→ \@N を整数変数とすると、"myArray"の \@N 番目の要素は
% \@nameuse{myArray/\number\@N} で取得できるただし、こういう「擬似配列」を広範に用いると、「フツーに組版をするプログラム（というか文書）」と比べて桁違いに多くの制御綴を扱う必要性が生じる。これに対応するため、現在通用している TeX 処理系では、使用可能な制御綴の個数の上限が大幅に引き上げられている（Knuth オリジナルでは 2100、現用では 50 万弱）。
TeX 処理系のハッシュテーブルの実際
基本的に、現用の処理系のハッシュテーブルの実装はチェイン法である。*3パラメタは次のようになっている。
これをみると、現用の処理系のテーブルサイズの値は最大容量と比べて明らかに過小であることが判る。（恐らく“無理やり拡張している”せいでテーブルサイズが増やせないのだと思う。）従って、制御綴の個数が数万のオーダに達した後では、理論上はハッシュテーブルの検索の所要時間は個数に比例することになる。
となると、「擬似配列」を用いたデータ構造・アルゴリズムの時間計算量を解析する場合に、「現実的な範囲」においてこの性能劣化を考慮すべきかが問題になる。
チョット実験してみる
というわけで、調べてみた。
- 事前に「英大文字 10 文字のランダムな文字列」50 万個からなるリストを作っておく。
- 実験用文書“Set-n”（n＝1，1000，10000，100000，470000*5）
\documentclass{article} \begin{document} \let\xyzNAMWONSSEY\relax % 全部で100万行 \let\xyzEMOHOGKCUD\relax \let\xyzIHSUSSIXET\relax ………… \end{document}
ここで\xyz...の制御綴の大文字部分は、先述のリストの先頭 n 個の部分リストにあるものを順番に使い、使い切ったら最初に戻る。従って、\xyz...の制御綴は延べで 100 万個出現するが、そのうち異なるものは n 個である。 - 比較対照用文書“Base”
\documentclass{article} \begin{document} \relax % 全部で100万行 \relax \relax ………… \end{document}
- 「“Base”対“Set-1”」の時間差が「let の処理 100 万回にかかる時間」、「“Set-1”対“Set-n”」が「制御綴が n 個に増えたことによる追加の所要時間」になる。
- TeX 処理系として TeX Live 2018 最新の latex コマンドを使った。
- 5 回のウォームアップの後、100 回のコンパイル時間を計測した。
結果
| 文書 | 所要時間平均(秒) | 標準偏差(秒) |
|---|---|---|
| Base | 2.383 | 0.017 |
| Set-1 | 3.366 | 0.027 |
| Set-1000 | 3.383 | 0.027 |
| Set-10000 | 3.405 | 0.027 |
| Set-100000 | 3.543 | 0.026 |
| Set-470000 | 5.154 | 0.064 |
- Base と Set-1 の差： 0.983 秒
- Set-1 と Set-1000 の差： 0.017 秒
- Set-1 と Set-10000 の差： 0.039 秒
- Set-1 と Set-100000 の差： 0.177 秒
- Set-1 と Set-470000 の差： 1.788 秒
考察小並感
“対数的な視点”でみると、制御綴 100000 個というのは「上限が目の前に迫っている」状況であり、TeX での処理としては「かなり無理がある」状態である気がする。「無理のない範囲」、すなわち 100000 個以下で考えるならば、TeX 処理系のハッシュテーブルの性能劣化は無視してかまわない、のではないかと。
まとめ
（画像省略）
*1:この「オブジェクト」というのは TeX 処理系の実装プログラムが保持するデータのことを指す仮の用語。TeX 言語ではなくて内部処理の話をしていることに注意。
*2:「擬似配列」方式では、配列は変数に束縛された形でのみ存在できる。つまり、「第一級の値」ではない。
*3:Knuth のオリジナルの実装は少し複雑であるが、それから変更が加えられている。
*4:ハッシュテーブルの容量が 615000 なのに上限が 50 万弱となるのは、別の容量制限の影響のため。
*5:470000 はほぼ上限に近い値。（480000 だと容量超過のエラーになった。LaTeX カーネルが“50 万弱”の一部を既に使っていることに注意。）
