LRU queue or heap data structure implementation?

[Richard Cameron]

Has anyone implemented a heap data structure or have any thoughts  
about how to efficiently implement an LRU queue in Erlang?

The context is that I'm interested in using an ets table as a simple  
data cache. I want to be able to throw values into the table and have  
a background process purge old items as the table grows large. The  
aim is to produce a protocol compatible implementation for memcached  
<http://www.danga.com/memcached/> which I'm finally getting round to  
writing after being all enthusiastic about it several months ago  
<http://lists.danga.com/pipermail/memcached/2005-August/001579.html>.

In production, the cache is likely to get quite big (gigabytes) and  
consist of lots of smallish objects. I'm trying to work out whether  
an LRU implementation done purely with Erlang lists and tuples is  
likely to be efficient enough to be worthwhile, or whether it's  
better to just have a background O(n) process which periodically  
sweeps the whole cache to gather statistics and purge old items. This  
clearly depends on the read/write profile of the cache, but I want to  
get a feel for how quick an LRU queue could be made to work.

Richard.