Pythonで使えるLRUを比較する

高速化の為にローカルにキャッシュを設けたい、でもメモリを無駄遣いする気はない、といった場合にLRU(Least Recentry Used)キャッシュを使うのはよくあるパターンです。
pythonでLRUキャッシュをさがすといくつか選択肢が見つかります。

$ pip search lru
pylru - A least recently used (LRU) cache implementation
ciutils - Helpers to use in CI environments (e.g. use
xmlrunner together with `test` command)
repoze.lru - A tiny LRU cache implementation and decorator
darts.util.lru - Simple dictionary with LRU behaviour
velruse - Simplifying third-party authentication for web
applications.
lrucache - Least-recently-used (LRU) cache module
pyplugin - Python NPAPI plugin for XULRunner
lru - A simple LRU cache implementation

中でもpylru, repoze.lru, lruが使えたので入れて比べてみました（lrucacheはName or service not known> while getting http://bad.dynu.ca/%7eevan/lrucache/lrucache-0.2.tar.gz (from http://pypi.python.org/simple/lrucache/)とか出てインストールできませんでした。）

結論を先にネタバレするとpylru推奨です。

使い方

使い方はそれぞれこんな感じです
pylru

import pylru
# 追加
cache = pylru.lrucache(1000) # サイズを指定
cache[0] = 10 # []=で、代入
# 参照
assert cache[1] == 1 # []でアクセス
try:
  cache[1]
  assert False
except KeyError: # 見つからなければKeyErrorが投げられる
  pass

lru

import lru
cache = lru.LRUCache(1000)
# 追加
cache[0] = 10
# 参照
assert cache[1] == 1
try:
  cache[1]
  assert False
except KeyError:
  pass

repoze.lru

import repoze.lru
cache = repoze.lru.LRUCache(1000)
# 挿入はput
cache.put(0,10)
# 参照はget
assert cache.get(0) == None
assert cache.get(1) == 1

pylruとlruが[]によるアクセス、repoze.lruはset,getメソッドでアクセスするようです。
どれを使っても困らなさそうなので比較ベンチを取ってみます。

ベンチマーク

CPU AMD Phenom(tm) II X4 955
OS Linux2.6.35-30-generic-pae
Python 2.6.6

サイズ10000固定でn回操作するのにかかった時間のグラフです(縦軸が秒、横軸がn)
各ベンチマークはそれぞれ10回ずつ行って平均を取りました*1。
サイズを変動させた方のベンチマークのほうが興味深かったのですが後述する理由により固定です*2

各種目のベンチマークは長いのでこちらへ
https://gist.github.com/1319383

lruのput(紫)だけ致命的に遅くて他のグラフが下に潰れています。
lruのputが一体何やってるのか調べてないですがこれでは比較になりません。
なのでlruのputを省いてグラフを描いてみます。

lruはgetも他と比べて遅いようですが、何かオフセットのような物があるのは何なんでしょう…？
勾配はpylruに近いのですが最小のたかが100000要素のget操作に1.9秒もかかっています。
repoze.lruのput(紫)はpylruのput(緑)と比べて遅いようです。
その代わりrepoze.lruのget(水色)はpylruのget(赤)より僅かに速いようです。

この比較から、一番バランスが取れて性能が出せているのはpylru。repoze.lruはgetが僅かに速いですがput操作が遅いです。
また、lruは致命的にputが遅いので非推奨と感じました。というかlruの470万回のputで1600秒とか掛かってて時間かかり過ぎで当初の予定通りのベンチマークが取れなかったです…。

結論: pylru推奨。lruは地雷。

以下は取るだけとったフルの比較
get - 通常のランダムなget(命中率)
fail_get - 存在しないキーでのget
suc_get - 存在するキーでのget
put - 存在しないキーでのput
put_ovw - 存在するキーでのput
put_rnd - ランダムなキーでのput

lru超遅い

安定してるpylru

比較的遅いrepoze.lru

pylruのgetとrepoze.lruのgetの比較を拡大

pylruとrepoze.lruの全面比較
getは大差無いがputで倍速以上の差が出ている