From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA13845; Wed, 30 Jun 2004 13:06:07 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA13825 for ; Wed, 30 Jun 2004 13:06:06 +0200 (MET DST) Received: from relay.felk.cvut.cz (relay.felk.cvut.cz [147.32.80.7]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i5UB65SH029678 for ; Wed, 30 Jun 2004 13:06:05 +0200 Received: from k333.felk.cvut.cz (k333.felk.cvut.cz [147.32.87.5]) by relay.felk.cvut.cz (8.12.11/8.12.11) with ESMTP id i5UB5x2Y032020 for ; Wed, 30 Jun 2004 13:05:59 +0200 (CEST) (envelope-from kybic@fel.cvut.cz) Received: from K333/SpoolDir by k333.felk.cvut.cz (Mercury 1.48); 30 Jun 04 13:05:59 +0100 Received: from SpoolDir by K333 (Mercury 1.48); 30 Jun 04 13:05:55 +0100 Received: from biogw-i-06.felk.cvut.cz (147.32.84.19) by k333.felk.cvut.cz (Mercury 1.48) with ESMTP; 30 Jun 04 13:05:46 +0100 To: caml-list@pauillac.inria.fr Subject: [Caml-list] Q: automatic forgetting cache, module Weak, Gc control From: Jan Kybic Date: 30 Jun 2004 13:05:46 +0200 Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2.93 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-MailScanner-felk: Found to be clean X-MailScanner-SpamCheck-felk: not spam, SpamAssassin (score=-4.9, required 5, BAYES_00 -4.90) X-Miltered: at concorde with ID 40E29E9D.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caching:01 memoizing:01 hash:01 val:01 memo:01 hashtbl:01 hashtbl:01 retrieve:99 implemented:01 implemented:01 circumvent:01 floats:01 hash:01 420:99 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hello, I am implementing a complicated numerical computation algorithm in OCaml. (Basically, it is a Fast Mulipole Method accceleration for a Boundary Element Method.) There is a lot of intermediate results of several different types that are expensive to calculate but that are used repeatedly in subsequent calculations. Therefore, I am caching (memoizing) these intermediate results using a hash table, like this: val f : ('a -> 'b) -> ('a -> 'b) let memo f = let h = Hashtbl.create 11 in fun x -> try Hashtbl.find h x with Not_found -> let r = f x in ( Hashtbl.add h x r; r ) This works fine for smaller problems and the calculation is much accelerated. However, when the problem gets big and the amount of memory needed to store the intermediate results exceeds the amount of available RAM, the operating system (Linux) starts to swap the cache memory to disk. At this point, it is no longer advantageous to cache the values, it is actually faster to recalculate them then to retrieve them from the disk. The solution seems to be to implement a forgetting LRU (last-recently-used) cache of a fixed maximum size. Here come my questions: 1) Has anyone implemented that in Ocaml already? I have found http://bleu.west.spy.net/~dustin/projects/ocaml/doc/Lru.html Do you have any experience with it? 2) I have several different types of objects (functions) to cache and it is difficult to find out a priori, how much memory should be devoted to each type, if each cache is implemented separetely. It would be nice to be able to make all caches share the same pool but storing values of different type (and size) in the same structure conflicts with the type safety. Should I use the Obj module to circumvent this, or is there a more elegant way around? 3) Many (but not all) of the precomputed values are floats. Does it pay off to treat them separately? Is there a way to avoid storing them boxed, say in a hash-table? 4) An ideal way would seem to be using the Weak module and the weak hash table implemented there. Will that work as expected? From reading the documentation I have the impression that the garbage collection will probably collect the weak values too early, at first minor collection. Is it correct? Is there a way to tune the garbage collector to leave the weak values alone as long as the total memory usage is below a certain threshold? Thanks very much in advance for all your thoughts and ideas. Jan -- ------------------------------------------------------------------------- Jan Kybic tel. +420 2 2435 7264 or , http://cmp.felk.cvut.cz/~kybic ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners