Since this theme has been raised again in issue32422 and old patches no longer apply clearly I have updated patches and benchmark results on 64 bit.

$ ./python -m perf timeit -s "from functools import lru_cache; f = lru_cache(512)(lambda x: x); a = list(range(500))*100" -- "list(map(f, a))"

Unpatched:    Mean +- std dev: 3.03 ms +- 0.02 ms
get-del-set:  Mean +- std dev: 5.73 ms +- 0.04 ms
pop-set:      Mean +- std dev: 4.63 ms +- 0.04 ms
move_to_end:  Mean +- std dev: 3.57 ms +- 0.06 ms


$ ./python -m perf timeit -s "from functools import lru_cache; f = lru_cache(512)(lambda x: x); a = list(range(50000))" -- "list(map(f, a))"

Unpatched:    Mean +- std dev: 6.65 ms +- 0.11 ms
get-del-set:  Mean +- std dev: 15.5 ms +- 0.1 ms
pop-set:      Mean +- std dev: 15.4 ms +- 0.1 ms
move_to_end:  Mean +- std dev: 15.5 ms +- 0.2 ms


All patches cause significant slowdown (around 2.3x) in the case of many misses.