Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Cache algorithms: implementation or library available?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-09-23 (07:54)
From: Hugo Ferreira <hmf@i...>
Subject: Re: [Caml-list] Cache algorithms: implementation or library available?
Hi Martin,

Martin Jambon wrote:
> Hugo Ferreira wrote:
>> Hello,
>> I would like to know if anyone has or knows of an Ocaml
>> library or open-source code implementation of some cache
>> algorithms (example: least recently used).
> There are so many possible access patterns and trade-offs:
> - speed requirements?
> - memory requirements?
> - constant size or just bounded?
> - is the probability of accessing an element a function of time?

I cannot say. It really depends on the convergence of the
algorithm which in turn depends on the data. I don't really
have enough information at this point to choose.

> I see two frequent use cases:
> a.  some elements are accessed more frequently than others regardless of time
> b.  recently-accessed elements have a higher probability of being accessed

I think (b) is the more appropriate one. As the algorithm converges so
does the probability of accessing a given key rise.

> Alain Frisch provides an implementation of roughly a hash table in which
> buckets hold only one element, which looks great at least for case (a):

I've looked at the code ("tiny module" indeed).
May be of use to me. Don't like the use Obj.magic
and the Lazy module. Easy enough to adapt though.

Funny enough I was expecting complicated uses if the Weak module.


> Martin