English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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):
>   http://alain.frisch.fr/soft.html#memo

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