[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2004-12-01 (14:09) |
From: | Virgile Prevosto <virgile.prevosto@m...> |
Subject: | Re: [Caml-list] typing a value cache |
Le 30.11.2004, à 09:59:57, Christophe DEHLINGER a écrit: > Now things get tricky: the body of any function may change during > execution (so I actually deal with function references rather than > functions). When this happens, the cache entries corresponding to the > function calls that used this function during evaluation become > obsolete, and thus should be removed from the cache. So - and this is > the hard part typing-wise - this means that the cache must somehow > record the dependencies between function calls. > > I have found (I think) two ways to do that: > - defining notype_cache and no_type_cache_key, two class types with > methods to handle addition of a dependency in a cache. They are > inherited respectively by ('a,'b) cache and ('a,'b) cache_key. Each > function of type 'a->'b in the collection has its own ('a,'b) cache. > Seems to work fine, but notype_cache_key object instances cannot be Hello, I'm not sure I really understand your solution, but I'd say that a way to handle this problem would be to store together with a given cached value the actions needed to remove the other cached values that depend on it (for instance under the form of unit -> unit functions). Then, each time you're about to erase a value, you perform the corresponding actions. If they are correctly coded, you should then be able to recursively remove the obsolete cached values, and only them. I include at the bottom of this message a small module which seems to do the trick (at least on your 3-functions example), but is of course absolutely not tested on a large set of functions. Hope this might help. -- E tutto per oggi, a la prossima volta Virgile ------------------------------------------------------------------------ module Cache: sig type ('a, 'b) t val create: ('a -> 'b) -> ('a, 'b) t val app: ('a, 'b) t -> 'a -> 'b val modify: ('a, 'b) t -> ('a -> 'b) -> unit end = struct type ('a, 'b) t = { mutable f: 'a -> 'b; (* the function's body. *) cache: ('a, 'b * (unit -> unit) list) Hashtbl.t (* cached result, with the list of erasures to perform if the value becomes inaccurate. *) } let create f = { f = f; cache = Hashtbl.create 13} let cont = ref None (* how to remove the cached result that performs the current call (None = call from a non-monitored function).*) let remove cache x = (* remove all dependencies wrt a given value. *) try let (_,l) = Hashtbl.find cache x in List.iter (fun x -> x ()) l; Hashtbl.remove cache x with Not_found -> () let app f x = try (let (res, dep) = Hashtbl.find f.cache x in print_endline "cached"; match !cont with None -> res | Some cont -> Hashtbl.replace f.cache x (res, cont::dep); res) with Not_found -> let prec_cont = !cont in cont := Some (fun () -> remove f.cache x); let res = f.f x in let dep = match prec_cont with None -> [] | Some n -> [n] in Hashtbl.add f.cache x (res,dep); cont := prec_cont; res let modify f new_f = f.f <- new_f; Hashtbl.iter (fun _ -> fun (_,l) -> List.iter (fun x -> x()) l) f.cache; Hashtbl.clear f.cache end let f = Cache.create (fun n -> n > 0);; let g = Cache.create (fun b -> if b then "yo" else string_of_bool (Cache.app f 5));; let h = Cache.create (fun () -> String.length (Cache.app g false));; Cache.app h ();; Cache.app g false;; Cache.app f 5;; Cache.app g true;; Cache.modify f (fun n -> n = 0);; Cache.app f 5;; (* recomputed. *) Cache.app g true;; (* still cached. *) Cache.app h ();; -----------------------------------------------------------------------