From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <hmf@inescporto.pt>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.5 required=5.0 tests=AWL,SPF_SOFTFAIL 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by yquem.inria.fr (Postfix) with ESMTP id 009D1BBAF
	for <caml-list@yquem.inria.fr>; Wed, 23 Sep 2009 09:54:39 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AugBALtwuUrVhjEXkGdsb2JhbACaeAEBAQEJCQwHEwO6U4QbBQ
X-IronPort-AV: E=Sophos;i="4.44,437,1249250400"; 
   d="scan'208";a="33340924"
Received: from ihsmtp01voda.lis.interhost.com (HELO ihsmtp01cons.lis.interhost.com) ([213.134.49.23])
  by mail2-smtp-roc.national.inria.fr with ESMTP; 23 Sep 2009 09:54:39 +0200
Received: from [192.168.1.64] ([77.54.65.202]) by ihsmtp01cons.lis.interhost.com with Microsoft SMTPSVC(6.0.3790.3959);
	 Wed, 23 Sep 2009 08:50:58 +0100
Message-ID: <4AB9D439.4070304@inescporto.pt>
Date: Wed, 23 Sep 2009 08:54:33 +0100
From: Hugo Ferreira <hmf@inescporto.pt>
User-Agent: Thunderbird 2.0.0.23 (X11/20090817)
MIME-Version: 1.0
To: Martin Jambon <martin.jambon@ens-lyon.org>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Cache algorithms: implementation or library available?
References: <4AB8A6F1.7090802@inescporto.pt> <4AB8B44F.6040503@ens-lyon.org>
In-Reply-To: <4AB8B44F.6040503@ens-lyon.org>
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-OriginalArrivalTime: 23 Sep 2009 07:50:58.0507 (UTC) FILETIME=[9680F9B0:01CA3C22]
X-Spam: no; 0.00; ocaml:01 trade-offs:01 bounded:01 frisch:01 hash:01 frisch:01 wrote:01 wrote:01 caml-list:01 probability:01 probability:01 alain:01 alain:01 jambon:01 algorithm:01 

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
>