Re: [Caml-list] Cache algorithms: implementation or library available?

[Hugo Ferreira <hmf@inescporto.pt>]

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.

Thanks,
Hugo.


> 
> Martin
>