typing a value cache

typing a value cache

[Christophe DEHLINGER]

Hi all,

I'm trying to find an elegant way to build a data structure.
My program must deal with a large collection (1000+) of unary functions. 
The collection should be dynamically expandable, but I may have it be 
constant and known at compile time if I have no other choice. These 
functions may use other functions of the collection in their body.
As the exact same function calls will very often be made during 
execution, I wanted to build a cache structure in which frequently asked 
values would be stored.
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.

Simple example, with 3 functions f:int -> bool, g:bool->string, h:unit->int
Initially :
. f n = n>0
. g b = if b then "yo" else (string_of_bool (f 5))
. h () = String.length (g false)
Then my program then tries to evaluate h () for some purpose. The 
following entries are then added to the cache:
1) f : 5 -> true
2) g : false -> "true"
3) h : () -> 4
It then evaluates g true. The following entry is then added to the cache:
4) g : true -> "yo"
Then, if the body of f is changed to something else (e.g. (=) 0), 
entries 1, 2 and 3 should be removed from the cache, but not 4.

My question is : how do I build this cache thing in ocaml ? Is there a 
way to avoid coding type information ?
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 
compared (by value) in general, so dependencies cannot be removed (as it 
involves parsing a list of dependencies (of type no_type_cache_key list) 
and trying to find a particular notype_cache_key value in it). This can 
be worked around with some info duplication, but all in all although 
this approach seems to work, it is definitely unwieldy and has shortcomings
- too ugly to tell. Suffice to say it involves camlp4.
So, have I missed the simple-and-obvious solution to this problem ?

Cheers,
Christophe

__________________________

Ce message (et toutes ses pièces jointes éventuelles) est confidentiel et établi à l'intention exclusive de ses destinataires. Toute utilisation de ce message non conforme à sa destination, toute diffusion ou toute publication, totale ou partielle, est interdite, sauf autorisation expresse. L'IFP décline toute responsabilité au titre de ce message.

This message and any attachments (the message) are confidential and intended solely for the addressees. Any unauthorised use or dissemination is prohibited. IFP should not be liable for this message.

Visitez notre site Web / Visit our web site : http://www.ifp.fr
__________________________

Re: [Caml-list] typing a value cache

[Virgile Prevosto]

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 ();;
-----------------------------------------------------------------------