[PATCH 1 of 2 RFC] util: reimplement lrucachedict

[Durham Goode]

On 11/23/15 1:28 AM, Gregory Szorc wrote:
> # HG changeset patch
> # User Gregory Szorc <gregory.szorc at gmail.com>
> # Date 1448252535 28800
> #      Sun Nov 22 20:22:15 2015 -0800
> # Node ID 5d0aff0739984ebdcc5c99a84d338749cd702119
> # Parent  160d7e207cc161543c0486c4de223b30621cd6d9
> util: reimplement lrucachedict
>
> Previous experience has taught me that collections.deque has pretty
> bad performance characteristics. As part of attempting to more
> aggressively use the existing lrucachedict, collections.deque
> operations were frequently showing up in profiling output, negating
> benefits of caching.
>
> Searching the internet seems to tell me that the most efficient
> way to implement an LRU cache in Python is to have a dict indexing
> the cached entries and then to use a doubly linked list to track
> freshness of each entry. So, this patch replaces our existing
> lrucachedict with a version based on a doubly linked list.
Do you have imperical numbers to prove this is faster?