2005-11-03
先日の Fall Processor Forum 2005 において， Xbox 360 に搭載される PowerPC コアには simultaneous multithreading (SMT) の機構が搭載されていることが明らかにされた。 SMT とは，単一のコア内で複数のスレッドを同時に実行することによって資源の有効活用を狙う手法のことを呼ぶ。
プロセッサの資源は常に有効活用されているとは限らない。スーパースカラプロセッサでは命令レベルの並列性が高まることからある程度の資源の有効化が期待できるものの，実際には各種の依存性や競合・遅延の問題から処理は度々停止しており，資源にも空きが生じている。
これに対して， SMT では複数のスレッドの間で資源を共有することによって有効化を図る。ある時点において一方のスレッドでは使用されていない資源を他方のスレッドに割り当てることによって，資源の空き状態を減らすことができる。 SMT を行った場合，単一のスレッドに注目すると速度の低下が生じるが，全スレッドを総合して見れば，１サイクルあたりの命令実行数 (IPC; instructions per cycle) ― つまり「スループット」は向上すると考えることができる。
SMT によってスループットの向上を図るというアイデアは比較的昔から存在する [1] 。近代的な実装についてはカリフォルニア大学の Dean Tullsen 助教授らの研究が知られている。氏は 1996 年の時点でシミュレータを用いた SMT プロセッサの実験を行っている [2] 。このシミュレータは MIPSI と呼ばれる MIPS シミュレータをベースとしており， 8 スレッドまで並列実行可能な fine-grained multithreading 方式（後述）の SMT プロセッサをシミュレートするものだった。
この実験において Tullsen 氏らは， SMT によってスループットの向上が実現されることや，スーパースカラの機構に小規模な変更を加えるだけで SMT が実装可能であることなどを明らかにした。特に，大規模な機構の追加を行うこと無く実装が可能であるという点は重要視されていたようで，シミュレーションの設計も当時から 3 - 5 年後のトレンドとして予想されるプロセッサの仕様を反映した内容となっていた。民生品において SMT を実装した Intel の Hyper-threading が 2002 年に登場したことを考えると，氏らの予想はおおよそ的確であったと言えるかもしれない。
Tullsen 氏らが実装した SMT プロセッサは，複数のスレッドを同一サイクル内に実行するものではなく，１サイクル毎にスレッドを切り替えるというものだった。つまり，厳密に言えば複数のスレッドを同時に実行しているわけではなく，最小単位で切り替えていると言うのが正しい。これを純粋な SMT (pure SMT) と区別して fine-grained multithreading （fine-grained は「細挽き」の意）と呼ぶこともある。区別せずに両者を SMT と呼ぶ場合もあるので，その辺りは文脈から読み取る必要がある。
SMT の方式には，この他に coarse-grained multithreading と呼ばれる方式が存在する（coarse-grained は「粗挽き」の意）。 coarse-grained multithreading においては，命令のフェッチミスやメモリアクセスのキャッシュミスなどにより処理が停止した際にスレッドの切り替えが生じる。 coarse-grained multithreading を採用したアーキテクチャとしては， 2000 年に製品化された RS64 IV などが知られている [3] 。 RS64 は PowerPC のサーバー向け製品の一種であり， RS/6000 サーバー（後の pSeries）などに搭載されている。
これらの方式は一般に "pure SMT > fine-grained > coarse-grained" の順に高効率であることが知られている [4] [5] 。しかし，実装の複雑度としてはこの逆順になる。 RS64 IV が coarse-grained を採用したのは，実装上の制限によるものであったのか，あるいは設計上の意図であったのかは明らかでない。ただ文献 [3] においては， in-order 実行のアーキテクチャには coarse-grained が適していることや，単一のスレッドの処理速度に注目すれば coarse-grained の方が優れていることなどが理由として挙げられている。何にせよ，まだこの段階においては，並列化によってスループットの向上を図るというよりも，メモリ遅延をある程度埋め合わせることができればそれで良いという思想であったのだろうと思われる。
2005-11-07
SMT の有効性については， Tullsen ら [1] と Eskesen ら [2] の調査に詳しい。 Tullsen らは仮想的な SMT アーキテクチャに対しての調査をシミュレータ上で行ったのに対して， Eskesen らは PowerPC アーキテクチャに対しての調査を Turandot と呼ばれるシミュレータ上で行っている。 Turandot はスーパースカラおよび out-of-order 実行の機構を備えた PowerPC シミュレータであり， Eskesen らはこれにレジスタファイルの拡張等を施し SMT 対応させた。ちなみに，この SMT 対応拡張の施されたシミュレータは Figaro と名付けられている [3] 。
両者の調査は大筋において似た結果を報告している。どちらも２スレッドの SMT において平均で 30% 以上のスループットの向上が得られている。また， Tullsen らの報告では，スレッドを８個にまで増やした結果，最終的に約 84% のスループットの向上が得られたとされている。
両者の報告では共にスループットの向上が得られているものの，キャッシュミス率の増加や分岐予測ミス率の増加などのように，パフォーマンスの悪化の可能性を示唆する要素も見られる。 Tullsen らのシミュレータでは， SMT 対応のためにパイプラインのステージ数を増やしたところ，シングルスレッドのベンチマークにおいて約 2% のスループットの低下が見られた。ちなみに，このときに増やされたステージは， SMT 対応のために増強されたレジスタファイルへのアクセスを補うためのものであったとされている。
SMT によって大きく改善が見られた要素として，不要な命令フェッチの低減がある。「不要な命令フェッチ」とは，分岐予測を誤った際に命令キューないしはパイプラインから破棄される命令のことを指す。この時に破棄される命令の数は，分岐命令をフェッチしてからその分岐結果が反映されるまでにフェッチされた命令の数に従うことになるが， SMT プロセッサにおいては複数のスレッドの命令が交互にフェッチされることにより，その数は半減することになる。これは言い換えれば， SMT によって分岐命令のレイテンシが隠蔽されると解釈することができる。
不要な命令フェッチは， Tullsen らの報告では 17% の低下， Eskesen らの報告では 34.7% もの低下が見られる。一般に分岐予測ミス時のペナルティはパイプラインのステージ数が増えるほど増加することから，昨今の超長ステージパイプラインを備えたプロセッサにおいては更なる効果が期待されるものと思われる。
Eskesen らの報告では，ベンチマークの種別毎に分けた結果なども載せられており，非常に興味深い。特に SPECfp を始めとする浮動小数点系のベンチマークにおいて非常に低い成績が得られているのは目を引く。 SPECint では 39.42% ものスループット向上が得られているのに対して， SPECfp ではたったの 1.47% しか向上していない。
Eskesen らの分析によれば，このように Tullsen らの報告との間に食い違いが見られるのは，主にアーキテクチャの設計の違いに起因するものであると推察されている。例えば， Tullsen らのシミュレータは浮動小数点演算ユニットを３基積んでいるのに対して， Eskesen らのシミュレータは２基しか積んでいない。このように，アーキテクチャの設計によっては，処理の種類と SMT の効果との間に相関性が生じることは大いに考えられる。
もうひとつ，スレッド切り替えの規則に関連した調査の報告も興味深い。 Tullsen らの報告では "miss count" 方式（キャッシュミス待ちの最も少ないスレッドを優先的に選択する）が最も高い効率を示しているのに対して， Eskesen らの報告では "next-ready" 方式（待機状態のスレッド間をサイクル毎に切り替える）や "every-cycle" 方式（待機状態に関係無くサイクル毎に切り替える）のように優先付けの無い方式の方が高い効率を示している。それに対して coarse-grained 方式（キャッシュミス等により停止するまで現スレッドを維持する）は最も低い効率を示している。
現在一般に言われる "fine-grained" 方式とは， Eskesen らの分類における next-ready 方式や every-cycle 方式のように，スレッドの状態による優先順位付けを一切行わない方式のことを指すものと思われる。 Tullsen らの調査においては命令フェッチがボトルネックの一部となっていたことから miss count 方式が一定の効果を上げたものと推察されるが，近代的なアーキテクチャにおいてはスレッドの細かな切り替えを行いレイテンシの隠蔽効果を狙うことがスループット向上への近道であると思われる。 Eskesen らの調査において every-cycle 方式のような極めて単純な方式が非常に高い結果をもたらしていたことが，それを示唆している。
2005-11-13
プロセッサを効率良く動作させるには，プロセッサに対して絶え間なく命令を供給し続ける必要がある。これを阻害する要因はいくつか考えられるが，その中でも最も解決の困難な問題として分岐命令の存在が挙げられる。
プロセッサは分岐命令に遭遇すると，その結果が判明するまで次にフェッチすべき命令を決定することができない。昨今のプロセッサにおいてはクロック速度を高める目的からパイプラインの多段化が進められているが，パイプラインのステージ数が増えれば増えるほど，分岐結果が判明するまでの遅延も長くなってしまう。最近では分岐結果の判明までに 20 サイクル以上の遅延が発生することも珍しくない。
分岐が発生する度に命令フェッチを停止していたのでは非常に効率が悪いため，分岐結果の予測を行うことによって処理の停止を防ぐという手法が発達している。分岐命令をフェッチすると同時にその結果を正しく予測することができれば，処理を停止させることなく続行することができる。ただし予測に失敗すれば，相応のペナルティが生じることになる。
また，分岐予測の技術が重要となる理由として，プロセッサのスループットの向上が指摘される。スループット ― すなわち１サイクルあたりの命令実行数 (Instructions per Cycle; IPC) が増加すると，それに応じて一定期間内に分岐命令が出現する頻度も高まることになる。ゆえに，分岐予測失敗による性能低下を防ぐには，スループットの高さに応じて予測精度も高める必要がある。
実行時に分岐予測を動的に変化させるのではなく，コードに対して静的な分岐予測を行う方式のことを静的分岐予測と呼ぶ。
静的分岐予測の例としては BTFN 法などが挙げられる。 BTFN は "Backward Taken and Forward Not taken" の略であり，「前に戻る」方向への分岐は常に成立 (taken) とし，「後ろに飛ぶ」方向への分岐は常に不成立 (taken) と前提する。これは，「前に戻る」方向への分岐はループ処理であることが多く，成立である可能性が比較的高いという事実に基づいている。この方式は PA-RISC プロセッサや ARM プロセッサの一部において採用されている。 Yeh らによれば， BTFN 方式はループが主体のベンチマークにおいては 90% 以上もの精度が得られるものの，全体での平均を取ると 69% ほどにまで低下するとされている [1] 。
他の方式としては，コードの生成時に分岐予測を行い，これを「分岐ヒント」として生成コード内に埋め込む方式が挙げられる。この方式は，動的分岐予測の機構を備えたプロセッサにおいても実装されている場合が多い。「分岐ヒント」の情報は，「分岐ヒントビット」として分岐命令の中に組み込まれるものもあれば，「分岐ヒント命令」として分岐命令とは別に与えられるものもある。後者の方式は命令数が増加するという欠点があるものの，分岐命令のフェッチよりも前に予測を与えることが可能になることから，比較的単純な機構で遅延の無い分岐を実現することができるというメリットがある [2] 。
静的分岐予測に対して，実行時に分岐予測を動的に変化させる方式のことを動的分岐予測と呼ぶ。
動的分岐予測の方式としては，分岐履歴テーブル (Branch History Table; BHT) に n ビットカウンタの形で分岐履歴を保存する方式が広く用いられている。このカウンタのビット数には，専ら 1 ビットか 2 ビットが用いられる。一般に 1 ビットカウンタよりも 2 ビットカウンタの方が精度が高くなるが， 3 ビット以上のカウンタは変化への適応が遅くなり，逆に精度が落ちる傾向にあることが知られている [3] 。
昨今は n ビットカウンタ方式をベースとして予測精度を高める方法が色々と考案されている。中でも McFarling が考案した gshare 方式は，比較的単純な機構で高い精度が得られることで広く知られている [4] 。 gshare 方式は，分岐命令のアドレスに対する関連付けと，グローバルな分岐履歴に対する関連付けの， 2 レベルの履歴を複合的に用いるものだった。文献 [4] によれば平均で 94% もの予測精度が得られており，この時点で既に高い予測精度が実現されていることが分かる。
分岐が成立であると予測された場合には，分岐先アドレスの予測も行う必要がある。これに関しては，分岐命令のアドレスに対する関連付けを用いた分岐先バッファ (Branch Target Buffer; BTB) が広く用いられている。
BTB による分岐先予測の方式は，分岐先として固定アドレスを用いる場合には高い精度が得られるものの，分岐先として動的に変化するアドレス ― つまり間接分岐 (indirect branch) を用いる場合には精度が落ちるという欠点がある。 Driesen らの測定によれば，資源に制約の無い理想的な BTB を用いたとしても， SPECint95 ベンチマークにおける予測精度は 64% ほどであるとされている [5] 。
間接分岐は関数ポインタなどの実装に必要とされる。特に昨今は OOP 言語において仮想関数を多用することから間接分岐の重要性が増している。 Driesen らの測定によれば， Java High-level Class Modifier を SuperSPARC シミュレーター上で実行した際のプロファイルから， 47 命令に 1 回という非常に高い頻度で間接分岐命令が実行されていることが判明している [5] 。
Drisen らによれば， OOP に限らずともアプリケーションの種類によっては間接分岐が多用されている場合があるとされている。また，分岐予測ミス全般を見てみても，間接分岐に起因する予測ミスの割合は比較的高くなっている。今後は間接分岐に対する精度の改善を目的とした分岐先予測の改良も試みられるものと思われる。
2005-11-16
分岐の成立 (taken) 不成立 (not taken) の予測については， gshare 方式 [1] やその派生によって非常に高い精度が実現されている。これに対し，分岐先アドレスの予測については，分岐先バッファ (branch target buffer; BTB) を用いた予測が広く用いられているが，この方法は分岐先アドレスが変動する分岐，つまり間接分岐 (indirect branch) に対して予測精度が低くなるという欠点が存在する。
間接分岐は主に，関数からのリターンや，関数ポインタを介した関数呼び出しに用いられる。特に OOP 言語においては，仮想関数の実装に関数テーブルが用いられることから，間接分岐による予測ミスの影響が強く現れる可能性があると考えられる。
分岐先予測と間接分岐の関係については Driesen らの調査 [2] に詳しい。この調査では Shade シミュレータ [3] を用いた正確な実行コードの分析が行われている。つまり，単に生成コードの解析を行うのではなく，実際にシミュレータ上でプログラムを動作させたうえで，そこから間接分岐の発生する頻度と，それらがパフォーマンスに対して与える影響について測定を行っている。ちなみに，関数のリターン時に発生する間接分岐については，正確な予測を行うことが容易であるため，測定対象から除外されている。
測定の結果によれば， IDL コンパイラや JHM (Java High-level Class Modifier) において 47 命令に 1 回という非常に高い頻度で間接分岐が実行されている。また，これらの間接分岐のうち約 93% は仮想関数に起因するものであるとされている。
間接分岐が多用されるのは OOP 言語に限らない。 xlisp においても 69 命令に 1 回という比較的高い頻度で間接分岐が実行されているほか， perl においても 113 命令に 1 回という高めの頻度が見られる。また， perl については分岐先予測ミス率も非常に高くなっており，完全連想 (full associative) の BTB でも 31.80% という非常に高い確率で予測ミスが発生している。
逆に，間接分岐を用いていない例としては ijpeg ベンチマークなどが挙げられる。間接分岐の実行頻度は 5,770 命令に 1 回とされ，分岐先予測ミス率も 1.26% と低めになっている。
このように，間接分岐の頻度や分岐先予測ミス率は処理の種類によってばらつきがある。そして，場合によっては高いペナルティが払われている。特に，コンパイラやパーサの類にその傾向が見られる。
Driesen らは分岐先予測ミス率を減らすために，グローバル履歴との組み合わせによって２レベル予測を行うという手法を提案している。この改良によって， 4K エントリの BTB において平均で 24.92% もあった予測ミス率は 7.77% にまで低下している。また，履歴パス数の異なる２種のテーブルを組み合わせることによって適応度を高める方式 (hybrid predictor) では，ミス率を 6.72% にまで押し下げることに成功している。
グローバル履歴を用いた２レベル予測は gshare 方式でも用いられているものであり，仕組みとしては比較的単純なものであると言うことができる。ただし，分岐の成立・不成立の履歴であれば１ビットの履歴情報だけで済んでいたものが，分岐先の履歴となると数バイトの分岐先アドレスを履歴情報として扱わなくてはならない。これを現実的なハードウェア実装に収めるには何らかの省略を行う必要があり，文献では様々な省略の方法について検討と比較が行われている。
間接分岐に関する調査の結果からも分かるように，仮想関数の呼び出しには一定のコストが伴うものと考えられる。このコストについても Driesen らが詳細な調査を行っている [4] 。
この調査でも [2] と同じく Shade シミュレータが用いられている。測定の対象となっているのは実行時に処理された命令の量であり，生成コードに含まれる命令の量ではない。そのため，たとえ仮想関数の使用箇所が少なくとも，実行時にその箇所を頻繁に通過すれば高い値が測定される。
まず基準として「全くペナルティが生じない場合のコスト」を算出し，それに対して実行時に生じたオーバーヘッドの量を測定している。測定の結果によれば，最低で 4.7%, 最高で 47% のオーバーヘッドが生じており，中央値は 5.2% とされている。また，実行された命令のうち 3.7% ほどが仮想関数のディスパッチに費やされている。これは，割合としては低い値ではあるが，仮想関数のディスパッチ自体はさほど有意な処理ではないことを考慮すると，比較的高いコストであると感じられる。
Driesen らは，１回の仮想関数の呼び出しに必要とされるコストは最高で 2L+1B+1 サイクル（L はロード遅延， B は分岐予測ミスペナルティ）であると仮定している [5] 。測定に用いられたシミュレータの仕様にこれを当てはめると 9 サイクルとなる (L=1, B=6) が，実際に測定されたコストは中間値で 3.9 サイクルとなっている。ロード遅延の隠蔽や分岐予測によって 40% 程度にまでコストが軽減されていることが分かる。
ただし，昨今のプロセッサにおいてはロード遅延や予測ミスペナルティは非常に大きな値となっている。調査が行われた当時と比較すればコンパイラ技術も幾分進歩しているため単純な類推を行うことはできないが，少なくともその平均コストは倍増しているのではないかと思われる。特に，市場製品においては分岐先予測に関して大きな進歩が見られないため，増大するペナルティを予測精度の向上によって吸収することは期待できないものと思われる。
2005-11-21
IBM T.J. Watson Research Center の Matthews らは，文献 [1] において，ビデオゲームと他のマルチメディア系アプリケーションとの間に見られる処理負荷の性質の違いについて，測定と考察を行っている。
測定対象を動作させるプラットフォームには Macintosh G5 が使用された。測定手段としては PowerPC 970 に搭載されている Performance Monitor Counter (PMC) が利用されている。マルチメディア系アプリケーションとしては DVD プレイヤーと QuickTime プレイヤーが使用され，ビデオゲームとしては FPS （タイトル名は明らかにされていない）が使用された。なお， FPS では bot が 0 体の場合と 32 体の場合の２種類が扱われている。
測定結果は，大方において予想に近いものとなっている。マルチメディア系アプリケーションではフレームの更新タイミングの周辺に負荷が集中する様子が測定されている。ビデオゲームもフレーム更新の周辺に負荷が集中しているものの，その偏りは比較的緩く，全期間に渡って高負荷がもたらされている様子が分かる。
測定結果からは，マルチメディア系アプリケーションよりもビデオゲームの方がプロセッサに対して厳しい条件を課しているような印象を受ける。例えば IPC （サイクルあたりの命令実行数）に注目してみると， DVD プレイヤーは平均で 0.83 程度であるのに対して， FPS はその半分以下の 0.36 程度となっている。
メモリアクセス（キャッシュミス率）にも同様の傾向を見ることができる。特に L2 キャッシュミス率には顕著な差が現れている。 DVD プレイヤーでは L2 キャッシュミスは非常に低い頻度に抑えられており， 1,000 命令に 1 回未満という水準になっている。これに対して FPS の bot=0 では 1,000 命令に 4 回程度の頻度で L2 キャッシュミスが発生している。
次に分岐予測に注目してみると，両者の関係は複雑化する。 DVD プレイヤーでは 7.99% という比較的高い頻度の分岐予測ミスが検出されているのに対して， FPS の bot=0 では 5.33%, bot=32 では 5.91% とやや控え目の頻度に抑えられている。これは， DVD プレイヤーのような圧縮データの伸張処理では偏りの少ない条件判定処理が頻出するために分岐予測ミス率が高まるのではないかと思われる。
分岐先予測に注目すると， DVD プレイヤーでは僅か 0.25% の分岐先予測ミスしか検出されていないのに対して， FPS の bot=0 は 2.62%, bot=32 は 1.92% の分岐先予測ミスが検出されている。これは，測定に用いた FPS が C++ を使用していることから，仮想関数の多用によって分岐先予測ミス率が高まっているものと思われる。
2005-11-25
昨今のソフトウェアの中には，非常に高い頻度で仮想関数を用いているものがある [1] 。これらの仮想関数の呼び出しには一定のコストが必要とされる [2] 。したがって，そのコストを軽減することができれば，実行速度の向上が実現されるものと考えられる。
仮想関数の呼び出しコストを軽減する手法のひとつとして， thunk の導入が挙げられる。
通常，仮想関数の呼び出しを行う際には，多重継承への対応のために this ポインタにオフセットを加える必要がある。この処理は単一継承クラスにおいては無駄な負荷となりうる。そこで，オフセットを行わない仮想関数呼び出しをデフォルトとし，オフセットが必要な場合にはオフセット処理を含むアダプタ関数（これを thunk と呼ぶ）を経由することにする。
Thunk を導入することによって，単一継承クラスにおける仮想関数の呼び出しコストは軽減される。逆に，多重継承クラスにおける呼び出しコストは増加する。また，仮想関数のそれぞれと対となる thunk を用意することになるため，コードサイズが増加する可能性もある。しかし，多くのプログラムでは単一継承が多数を占めるため，ほとんどの場合において効果的な高速化となりうる [2] 。
呼び出しコストを軽減する手法とは異なるアプローチとして，仮想関数を呼び出す際の動的ディスパッチを静的ディスパッチに置換する手法が考えられる [3] 。
プログラムの全体に渡ってクラス構造を解析し，その中に一度もオーバーライドされていない仮想関数が存在した場合，その関数を動的ディスパッチによって呼び出す必要は無く，単純に静的ディスパッチへと置換することができる。
このような仮想関数は，仮想関数として定義されていること自体が無駄であるとも考えられるが，設計手法としては意味を持つこともある。例えば，将来的な拡張の手段として仮想関数を用いるという設計はしばしば見られるが，最終的にそれらすべてが必ずオーバーライドされるとは限らない。
Sweeney らによれば，あるベンチマーク群のクラス構造の解析を行ったところ，平均して 12.5% ものデータメンバがソフトウェアの動作に影響を及ぼさないものであったとされている [4] 。このような調査結果からも類推されるように，一定の規模を越えたプログラムには必ずと言ってよいほどに無駄なクラスメンバが存在する。このような無駄を排除し効率化を図るには，コンパイラが通常行う翻訳単位内での最適化だけではなく，プログラム全体での構造解析を行う必要があると考えられる。
仮想関数の静的ディスパッチ化は，オーバーライドが行われていたとしても，なおも意味を持つ場合がある。
例として以下のようなクラス構造を想定する。基底クラス Base と派生クラス SubA, SubB が存在し，それぞれが仮想関数 vfunc() をオーバーライドしている。
ここで，もし， SubA よりも SubB のインスタンスの方が圧倒的に数が多く， SubB::vfunc() の呼び出し回数も圧倒的に多いとすれば，以下のような特殊な判定を行い， SubB::vfunc() の呼び出しを静的ディスパッチ化することによって，動的ディスパッチの回数を減らすことができる。
このような最適化を行うには，まず「SubB::vfunc() の呼び出し回数が圧倒的に多い」という情報を何処からか得なくてはならない。このような情報は，実行時の状況や入力されるデータの内容によっても異なってくるため，ソースコードの静的な分析から得ることは難しい。
この問題を解決するには，実行時のプロファイル情報を用いる方法が適切であると考えられる。すなわち，典型的な試行を何度か行い，その実行時のプロファイル情報から最適化のヒントを得て，それを再ビルド時に最適化情報として反映させる。 Microsoft Visual C++ 2005 に搭載された Profile-Guided Optimization (PGO) 機能では，このような手順による仮想関数の静的ディスパッチ化が実際に行われている [5] [6] 。
2005-11-30
データ構造の選択はパフォーマンスやメモリ効率を追求する上で重要な要素となる。データの用途やハードウェアの特性に合わせて適切な構造を選択することが求められる。
STL [1] や Boost [2] のようなテンプレートライブラリ（ジェネリックライブラリ）は，あらゆるクラスに適用可能なデータ構造とアルゴリズムの実装を提供する。これは，内容物を特定しないという意味で総称的 (generic) であり，内容物は抽象的に扱われるが，データ構造自体はさほど強く抽象化されない [3] [4] 。コンセプト (concept) と呼ばれる概念によって記述された仕様を把握したうえで，実装に関しても部分的に理解しておく必要がある。
例えば， STL において単位時間でのランダムアクセスを保証するコンテナは vector と deque が挙げられるが，この両者の違いは先頭要素への挿入が定数時間であるかどうかという他に， vector は速度面で有利であり， deque はメモリ効率面で有利であるという違いがある [5] 。この違いは両者の構造的な違いから生じるものであるが，仕様からは伝わりにくい部分であり，部分的にでも実装を理解しておくことが重要であると感じられる場面でもある。
もう一例を挙げる。連想コンテナの一種である map の実装は，一般に red-black tree のようなバランス木を用いており，要素の検索・追加・削除には O(log n) のコストが必要とされる [6] 。ゆえに，速度が重要視される場合には map ではなくハッシュテーブルを用いた方が良いと考えられる。また， red-black tree の実装ではノード毎に左・右・親の３つのポインタと色情報が必要とされるため，要素毎に消費されるメモリ量が割高になることがある（特に 64-bit アーキテクチャにおいては顕著になる）。これらの理由から， map は連想コンテナとして必ずしも適切な実装であるとは限らない。
Judy Array [7] は trie [8] と呼ばれる順序木 (ordered-tree) の一種を用いた連想配列構造であり， Baskins および Hewlett-Packard 社によって開発された。 Judy Array の最大の特徴はパフォーマンスの追求であり，設計には CPU のデータキャッシュ機構との親和性が織り込まれている [9] 。そのために，高速かつメモリ効率の良い連想配列構造の例として文献から参照されることがある。
確かに技術解説の文書を参照する限りでは，これが非常に練りこまれた設計であることが伝わってくるが，その狙いが実際のハードウェアに適合するかどうかは測定を行ってみなければ量りかねる部分がある。 Barrett はこの問題に焦点を当て，即席のハッシュテーブルとのパフォーマンスの比較を行っている [10] 。
測定は非常に詳細に行われており，かつ興味深い結果が得られている。 Judy Array のパフォーマンスはハッシュテーブルのそれに近いものの，入力されるキー列がランダムな順列の場合は，検索・追加・削除共にハッシュテーブルと同程度かそれ以下のパフォーマンスとなっている。 Judy Array の方が優れている点としては，キーが順列に近い形で入力された場合のパフォーマンスと，要素数が多くなった場合の消費メモリ量などが挙げられる。しかし逆にそれ以外の要素に関しては，ハッシュテーブルと比較して特に大きく優れているわけではなく，むしろハッシュテーブルの方が優れている部分も決して少なくない。
Barrett の調査は実際に測定を行ってみることの重要性を物語っている。 Judy Array は特定の用途には適しているが，その範囲は元の文献で提示されているよりも狭いことが分かる。あるいは，他のアーキテクチャ（例えば L1 キャッシュミスペナルティが非常に大きいアーキテクチャなど）の上では相対的なパフォーマンスが向上するかもしれない。いずれにせよ，ハードウェアの特性に合わせた最適化をデータ構造のレベルで行うことの難しさを表していると感じられる。