Home > front end >  Run time difference between chained functions and a list of functions in OCaml
Run time difference between chained functions and a list of functions in OCaml

Time:12-24

For registering unit functions to be called later, I came up with this solution using a (unit -> unit) ref that chains the functions together:

let callbacks = ref @@ fun () -> ()

let add_callback f =
  let old_callbacks = !callbacks in
  callbacks := (fun () -> f (); old_callbacks ())

(* ... call add_callback many times ... *)

(* eventually, run all the callbacks I stacked: *)
!callbacks ()

I am wondering how it compares to that other solution using a stack of functions (unit -> unit) list ref:

let callbacks = ref []

let add_callback f =
  callbacks := f :: !callbacks

(* ... call add_callback many times ... *)

(* eventually, run all the callbacks I stacked: *)
List.iter (fun f -> f ()) !callbacks

Are there differences in how they are represented in memory?

If I were to register a huge amount of functions, which solution would be the best in terms of memory and of unstacking time? For these 2 criteria, is there a better yet solution?

CodePudding user response:

In both cases you have a list of functions. In the first case the nodes of the list are function closures. In the second case they are cons elements. I don't know the ins and outs of closure representation in OCaml but I would guess that a closure is bigger than a cons element (which takes 3 memory slots for header, car, and cdr (to use the old school terminology)).

When it comes time to call, both cases are going to fetch a pointer to the next function and call it. In the first case the pointer will be fetched from the environment (variable bindings) of the closure. In the second case it will be fetched from the cons. I suspect that environments are accessed approximately as efficiently as cons cells. I.e., the code can use fixed offsets rather than a symbolic lookup.

These are just guesses. It would actually be interesting (and entertaining) to code up the two different methods and compare them.

  • Related