Poptrieがどうやって生まれたか，記憶に残っているうちに書き残すことにします。雑記なのでまとまりがないです。基本，時系列です。

Poptrie研究のきっかけは2013年の博士審査の直前くらいに遡ります。ルーティングテーブルルックアップに興味を持ったのは，博士を取得する直前に何か新しい研究を始めようと思い，OSを自作しようといろいろな資料を眺めていたころです。x86のページテーブルのTranslation Lookaside Buffer (TLB)にContent Addressable Memory (CAM)が使われていることを知りました。ちょうど1年半くらい前のSIGCOMMでGPGPUを応用したPacketShaderが発表されたころで、CPUにCAMが載っているなら，Forwarding Information Base (FIB)に使われているTernary CAM (TCAM)もGeneral-Purpose TCAMとして載ったらおもしろいなぁ，と思ったわけです。当時ハードウェアアーキテクチャを勉強し始めたばかりだったので恥ずかしげもなく，専門家につぶらな瞳で「TCAM CPUに積めないですかね？積めないならPCIeで拡張ボードとしてどうですかね？」と聞いたら，「CPUは無理。載っても大容量は無理。PCIeで拡張ボード載せてもPCIeはレイテンシが大きいから単なるメモリのTCAMだとGeneral-Purposeにするのは難しい。」と言われたのです。今考えると当然ですよね。Intel FM10KのようにNICに付けた方が現実的なわけですが，容量は小さく，大容量は厳しいですね。

その後，大学教員になり，2013年夏のIETF 87@ベルリンのインターコンチネンタルホテルの真ん前のギリシャ料理屋でS先生とS博士とお昼を食べながらルーティングテーブル爆発の話をしているときに，ふと思いついて「いまどきメモリ32 GiB以上が当たり前だし，IPv4アドレスを1対1対応させればO(1)で検索可能になるんじゃないですかね？」と言ったらS先生に「それやってみたら？」と言ってもらいました。そこでさくっと適当に実装してみたら，，，はい，O(1)のはずなのに100 Mlpsくらいしか出ないんですよね。ここで気づく「DRAMにアクセスしたら負けなんだ。たとえO(1)でも」ということに。

O(1)には夢があるが，決して銀の弾丸ではない。計算量=計算時間（計算速度）ではない，と思い知らされたわけですね。Radix treeに立ち戻ります。そこからMultiway trieやDIR-24-8-BASICのような配列ベースの最適化は手法を調べるのですが，どうしても木の深さを浅くしようとするとメモリ量が大きくなってしまいました。一方で，圧縮をしようとすると圧縮操作が命令数を食ってしまって10 ns/lookup (=100 Mlps)の壁を破れないんですよね。当時の実験ノートを見ると二分木と配列が大量に書かれていました。確かにベルリンから帰る飛行機でひたすら考えていた記憶があります。

調べる中で生まれたアイディア（後にこの点はTree BitMapなどでも行っていることが判明するので新規性はないですが…）が「ポインタが8バイトも食っているのが問題なので，Multiway trieの複数の子ノードを配列にしてポインタを1つに集約する」というものです。ただ，この拡張を行うと，子ノードを固定長の配列にする都合上，どうしてもメモリ効率が悪くなります。例えば，32分木の場合，10.0.0.0/8の1つの経路について，ルートの子ノード配列は，0.0.0.0/5, 8.0.0.0/5, ・・・, 240.0.0.0/5, 248.0.0.0/5の32個の経路に分割されます。このうち，8.0.0.0/5が10.0.0.0/8を含むため，子ノードが有効なノードとなります。それ以外のノードについては空になります。8.0.0.0/5の子ノードは，8.0.0.0/10, 8.64.0.0/10, ・・・, 15.128.0.0/10, 15.192.0.0/10の32個の配列となります。このうち4ノードが10.0.0.0/8の経路を表しており，他の28ノードは空になります。このように，空のノードが無視できないほどのメモリ領域を消費してしまうことになります。

この空ノードを圧縮することからPoptrieは始まりました。まず，最初に経路の入っているノードが，1経路に対して複数のノードにまたがってしまうことはこの段階では無視しました。一方，経路も子ノードへのリンクもない空ノードは無駄でしかありません。これを減らそうと考えました。空ノードを子ノード配列から除くのであれば，ノードの有無を表すビット列と空ノードではないノードの配列を使えば，空ノードが1ビットで表せます。このときはサーベイ不足で知りませんでしたが，この考え方はTree BitMapと同じですね。

ここでPoptrieの名前の由来であるpopcnt命令が出てきます。きっかけは，またOS開発に話が戻るのですが，ベルリンから日本に帰ってIntelのSoftware Developer's Manualを読んでいたときにpopcntという謎の命令に出会いました。大学教員，7月末〜8月は講義がないから研究が捗るんですよね。このpopcnt命令を使えば，ノードの有無を表すビット列と空ノードではないノード配列から，ノードを辿るときに，キーに対応する配列インデックスを1命令で計算できることに気づきました。ちなみに，この後にサーベイをして見つかったTree BitMapでは，あるビット列に含まれるビットの数を数えるのにテーブルを使っています。Tree BitMapは16分木なので，16ビット分，つまり65536個のエントリからなる変換テーブルでビットの数を数えています。1エントリ1バイトなら64 KiBで収まるのでキャッシュにより高速に実行できます。ただこれを64分木に拡張しようとすると2^64個のエントリを持つテーブルが必要となり，現実的ではないです。popcnt命令を利用することで，64分木までmultiway trieを拡張でき，木の深さを抑えています。ちなみに，論文にも書きましたが，popcnt命令が無い場合は，ビットシフトとAND命令のビット演算十数命令で代替できます。

ここまでが，Poptrieの基本的なアイディアですが，

まず，最初に経路の入っているノードが，1経路に対して複数のノードにまたがってしまうことはこの段階では無視しました

と書いたように，1経路が複数のノードにまたがってしまい，64分木のような多分木の構造では某大なメモリを消費してしまいます。Tree BitMapでは，これを防ぐために，木が下に続く場合（つまりPoptrieのinternal node）のみ，配列で持ち，木の途中で経路がある場合は二分木を持たせています。この二分木の探索が遅いので，Poptrieではleafにも上述の配列とビット列による簡潔データ構造の考えを導入しました。

これらの最適化により，internal nodeが子internal node配列へのポインタ（4バイト），leaf配列へのポインタ（4バイト），internal node配列圧縮用のビット列（8バイト），leaf配列圧縮用のビット列（8バイト）の24バイトとなり，キャッシュラインサイズ（主なCPUで64バイト）に合わなくなってしまいました。8バイト何かを追加してより速くできないかと考えましたが，参照するデータが増えると命令数も増えるのでいまのところ用途は見つかっていません。

ここまでの話は開発の話で，実験は基本的に32ビットの乱数列に対して経路検索を行うものでした。1パケットあたり数nsの話なので，計測メトリックは巨大な乱数列に対する平均検索速度しか計測できませんでした。木構造に対する経路検索はプレフィックス長が長いほど深くまで探索します。探索の深さが深くなるほど計算量は大きくなるので，そのような経路検索が性能の最悪量を評価する上で最適に思えますが，一部の経路だけ検索するとキャッシュヒット率が上がってしまうという問題があります。そこで論文では，キャッシュヒット率が悪くなるように乱数列を入力としながら，1経路検索ごとにかかるCPUサイクル数を計測することで，経路のプレフィックス長（正確にはRadix treeにおける探索の深さ）ごとの傾向を評価しました。

なお，1経路探索ごとにかかるCPUサイクル数は，Intel CPUのPerformance Monitoring Counter (PMC)と呼ばれる機能を使っています。これもOS開発しているときに見つけた機能ですね。あとこだわった部分は，ルータもどきのシングルタスクOSを作って，UDPパケットを入力し，そのペイロードに入っているアドレスに対し経路検索をし，その結果とPMCによる計測結果をUDPパケットとして出力するようにして計測した点です。乱数生成など，経路検索に関係ない処理を外に出す一方で，NICの入出力など実際のルータでキャッシュを汚しうる処理も含めたシステムとしての評価を行いました。まぁ，これは半分（以上）趣味でもありますが，シングルタスクOS，性能評価にはやっぱり良いですね。バックグラウンドプロセスも外乱もほとんどないので再現性で悩むことが少ないです。

ここからは論文投稿です。2014年6月にCoNEXTに（単著で）投稿したんですが，Review結果は散々なものでした。確かにあの論文でアルゴリズムを理解できたらすごい（いや，Reviewerの1名からは「おれ理解できたぞすごいだろ」的なコメントが付いていたレベルで…）。そして，まだキャッシュミスや1ルックアップごとのCPUサイクル数についての議論が甘かった。

ここからは自分だけのことでないので，既に公開している情報だけ書きます。CFI 2016で学生向けに発表したスライドから。CoNEXT投稿後，後の共著者になる小原さんと議論したときに『CoNEXT落ちたらSIGCOMMな』と言われ，その通りになった，というお話。論文については，小原さんが再実装できる文章になるまで一緒に書き直すという作業をしました。SIGCOMM qualityにまで引っ張り上げて頂いた小原さんには本当に感謝です。

実験の追い込みと論文執筆は死にそうでしたね。大学に何日泊まったことか。いや，シャワーを浴びに頻繁に帰ってはいたので，正確には泊まっていない（と主張している）。上で書いたパケットごとの性能評価，1回実験するのに7〜10時間くらいかかるんです。ある日は，とある先輩の結婚式の前に実験を走らせて，帰ってきてまた次の実験，そして仮眠へ，という流れですね。割と睡眠は取れていた気がします。

論文執筆についてもいろいろと思い出はあるのですが，こちらも個人の話じゃないので省略。論文締め切り前は割と悟りを開いた感じになっていたので，最後の1日はformattingが合っているか，ひたすら確認していましたね。

ということで，憶えている範囲でPoptrie開発の裏側について，書き殴ってみました。しばらくネットワークシステム研究の方に体重をかけていましたが，またネットワークアルゴリズム系の研究もしようかな，と思ったので，過去を振り返ってみました。

（2018年7月7日）