4

I have defined a module Comp whose operations are quite costly. In most of the cases, for a value of type Comp.t, a value of type int can be calculated, which can be used to accelarate many operations. So I define a type x as follows which represents 2 cases: 1) the integer has been calculated 2) otherwise

type x = A of (Comp.t, int) | B of Comp.t

A function convert: x -> x has been written to try to calculate the integer for a Comp.t, it is possible that this integer does not exist, this function is costly as well:

let convert (v: x): x =
  match v with
  | A _ -> v
  | B c -> 
    try to calculate the integer "i" from "c", 
    return "A (c, i)" if the integer is found; otherwise, return "B c". 

Initially, a comparaison function less than can be written like this:

open Comp

let lt (x0: x) (x1: x): bool =
  let x0, x1 = Comp.convert x0, Comp.convert x1 in
  match x0, x1 with
    | A (c0, i0), A (c1, i1) -> 
      i0 < i1 (* which is very fast *)
    | A (c0, _), B c1 | B c0, A (c1, _) | B c0, B c1 -> 
      Comp.lt c0 c1 (* which is quite slow *)

...
let b0 = lt x0_o x1_o in
let b1 = le x0_o x1_o in (* "le" call "convert" too *) 
let b2 = ge x0_o x1_o in (* "ge" call "convert" too *)
...

As convert is costly, and there are many other functions than lt which may call it from time to time (e.g. le, ge), I would like to make the conversion impact the value outside. For instance, I want the lt to change the value of x0_o and x1_o, so that the functions later (e.g. le, ge) receive arguments which probably have already been converted, that results in a faster computation for the whole block.

So I guess something like mutable record should be used, could anyone give me an example? Also, in general, is it a good idea to do this (permitting side effects) to optimise the computation?

2
  • why would "the integer not be found"?
    – newacct
    Jun 26, 2013 at 5:50
  • the integer is something I define myself... In some cases, I consider it does not make sense to have an integer... Well, it is true that a special value can be associated in these cases...
    – SoftTimur
    Jun 26, 2013 at 11:52

1 Answer 1

2

I think what you want to do is memoize (https://en.wikipedia.org/wiki/Memoization) the function Comp.convert (if it's pure):

This memoization code uses a hashtable to store the results instead of recalculating them (replaced the function Comp.convert with a very simple one to test the code):

let convert x = x +  3

let convert_m' () = 
  let tbl = Hashtbl.create 100 in
  (fun x -> if Hashtbl.mem tbl x then Hashtbl.find tbl x else 
      begin 
        let n = convert x in
        Hashtbl.add tbl x n;
        n 
      end
  )

let convert_m = convert_m' ()
let b = convert_m 6
2
  • Thank you... The structure of Comp.t is complicated, so I am afraid the complexity of Hashtbl.mem and Hashtbl.find is high?
    – SoftTimur
    Jun 25, 2013 at 20:49
  • It doesn't matter, Hashtbl is generic, you can use "complex" structures with it.
    – snf
    Jun 25, 2013 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.