Cache::LRU が速い理由 - Articles Advent Calendar 2010 Hacker先日、オンメモリなキャッシュモジュール Cache::LRU を書きました。Kazuho's Weblog: Cache::LRU (a handy and fast in-memory cache module in pure-perl) を見ていただければ、Cache::LRU が他のモジュールより速いことは明らかだと思います。速度差の原因としては機能や実装上の差異もあるのですが、設計上の工夫も Cache::LRU が速い理由のひとつです。 LRU (Least Recently Used) アルゴリズムを備えたキャッシュを実装しようと思うと、 エントリルックアップのためのハッシュ アクセス順を表現するためのリスト の２種類を組み合わせる必要があります。リストを表現する手法としては配列を利用するものとリンクリストを利用するものがありますが、Perl だと前者のほうが速い、ということは
