one-time initialization

one-time initialization

[Michael Hicks]

I wonder if anyone knows how to optimize the following (simplified for the
sake of dicussion) situation:

let global = ref None
let init i =
  global := Some i
let f () =
  match (!global) with
    Some x -> x
  | None -> failwith "not initialized";;
let g() =
  match (!global) with
    ...

Essentially, there is some global state that is initialized once, and is
used by all functions in the module.  In a more realistic situation, this
state might be initialized by reading in a file.  Given that following
initialization the global state never changes, it should be conceivable to
eliminate the match and dereference; on my machine (pentium 166), the match
and dereference result in about a 30% slowdown.  I've fooled around with
some things, but haven't found anything that performs better than this
straightforward approach or is any more elegant.

Thanks,
Mike
-- 
Michael Hicks
Ph.D. Candidate, the University of Pennsylvania
http://www.cis.upenn.edu/~mwh            mailto://mwh@dsl.cis.upenn.edu
"I worked with an individual who plugged his power strip back into itself
and for the life of him could not understand why his computer would not
turn on."

Re: one-time initialization

[John Prevost]

Michael Hicks <mwh@dsl.cis.upenn.edu> writes:

> I wonder if anyone knows how to optimize the following (simplified for the
> sake of dicussion) situation:

The only alternative I can think of that might provide a significant
performance boost is to make the reference a "default" value when the
initialization hasn't yet been done.  Another alternative that may win
some speed (but I sort of doubt it) is to make the reference be to a
function that raises an exception, like so:

val global = (ref (fun () -> failwith "not initialized") :
	(mytype -> unit) ref)

let init i = global := fun () -> i

let f () = ... (!global ())
let g () = (!global ()) ...

this at least has the advantage that you don't have to have a big
hairy pattern match in every function.

jmp

Re: one-time initialization

[Xavier Leroy]

> I wonder if anyone knows how to optimize the following (simplified for the
> sake of dicussion) situation:
> 
> let global = ref None
> let init i =
>   global := Some i
> let f () =
>   match (!global) with
>     Some x -> x
>   | None -> failwith "not initialized";;
> let g() =
>   match (!global) with
>     ...
> 
> Essentially, there is some global state that is initialized once, and is
> used by all functions in the module.  In a more realistic situation, this
> state might be initialized by reading in a file.  Given that following
> initialization the global state never changes, it should be conceivable to
> eliminate the match and dereference;

The compiler certainly cannot do it for you, as it involves proving
that f and g are never applied before init is called...

> on my machine (pentium 166), the match
> and dereference result in about a 30% slowdown.  I've fooled around with
> some things, but haven't found anything that performs better than this
> straightforward approach or is any more elegant.

Here are a couple of faster, but perhaps less modular approaches:

* Get rid of the ref and the option, and initialize "global" with the
  right value the first time.  That involves reading the file when
  global is initialized, which might involve parsing (partially) the
  command-line to find the right file name.  E.g.:

  let global =
    let filename = <parse command line to find config file name, use default
                    file name if not found> in
    read_config_file global

  let f() = ... use global ...

* Keep the ref but get rid of the option.  You then need a dummy value
  of the type of your global state, and you're also no longer protected
  against forgetting to initialize it.

  let global = ref dummy_global_value
  let init i = global := i
  let f() = ... use !global ...

Regards,

- Xavier Leroy

one-time initialization

[Adam P. Jenkins]

Michael Hicks writes:
 > I wonder if anyone knows how to optimize the following (simplified for the
 > sake of dicussion) situation:
 > 
 > let global = ref None
 > let init i =
 >   global := Some i
 > let f () =
 >   match (!global) with
 >     Some x -> x
 >   | None -> failwith "not initialized";;
 > let g() =
 >   match (!global) with
 >     ...
 > 
 > Essentially, there is some global state that is initialized once, and is
 > used by all functions in the module.  In a more realistic situation, this
 > state might be initialized by reading in a file.  Given that following
 > initialization the global state never changes, it should be conceivable to
 > eliminate the match and dereference; on my machine (pentium 166), the match
 > and dereference result in about a 30% slowdown.  I've fooled around with
 > some things, but haven't found anything that performs better than this
 > straightforward approach or is any more elegant.

If you're reading the state from a file, then you could make global
not be a ref by writing

let global = readState "initFile"

You could even store the init filename in an environment variable so
that readState could read a different file on different program
invocations.

As far as getting rid of the pattern matching, if the state can only
be one of several choices, then you could make several versions of f()
and g(), one for each pattern, and assign them from readState.  That
is.

let (global, f, g) = readState "initFile"

where readState returns different functions for f() and g() depending
on what state it reads.
   

Adam

Re: one-time initialization

[Michael Hicks]

> val global = (ref (fun () -> failwith "not initialized") :
> 	(mytype -> unit) ref)
> 
> let init i = global := fun () -> i
> 
> let f () = ... (!global ())
> let g () = (!global ()) ...
> 
> this at least has the advantage that you don't have to have a big
> hairy pattern match in every function.

I've tried this and similar alternatives using classes and records, but they
all end up being slower than the naive approach I presented before.  :(

One thing I've thought of is to make the entire program a bunch of functors,
parameterized by their external module references and an additional
"initialization information" module.  Then, the toplevel "main" module would
execute some code to initialize the "initialization" module, and then invoke
all of the functors to construct a custom program based on the
initialization information.  Since my program is a long-running server
application, it might be worth this one-time cost.  On the other hand, I'm
not sure the gain will be worth re-architecting the whole program ...

Mike
-- 
Michael Hicks
Ph.D. Candidate, the University of Pennsylvania
http://www.cis.upenn.edu/~mwh            mailto://mwh@dsl.cis.upenn.edu
"I worked with an individual who plugged his power strip back into itself
and for the life of him could not understand why his computer would not
turn on."

Re: one-time initialization

[Gerd Stolpmann]

On Thu, 28 Jan 1999, Michael Hicks wrote:
>I wonder if anyone knows how to optimize the following (simplified for the
>sake of dicussion) situation:
>
>let global = ref None
>let init i =
>  global := Some i
>let f () =
>  match (!global) with
>    Some x -> x
>  | None -> failwith "not initialized";;
>let g() =
>  match (!global) with
>    ...
>
>Essentially, there is some global state that is initialized once, and is
>used by all functions in the module.  In a more realistic situation, this
>state might be initialized by reading in a file.  Given that following
>initialization the global state never changes, it should be conceivable to
>eliminate the match and dereference; on my machine (pentium 166), the match
>and dereference result in about a 30% slowdown.  I've fooled around with
>some things, but haven't found anything that performs better than this
>straightforward approach or is any more elegant.

If you encapsulate your module, there is a solution that may eliminate
the need of an 'option' type
(I assume that 'global' has type t ref, and that v is a known value of t):

module M :
  sig
    type initialized
    val init : t -> initialized
    val f : initialized -> t
    val g : initialized -> ...
  end =
  struct
    type initialized = unit
    let global = ref v
    let init i = global := i
    let f () = !global
    let g () = ...
  end
    

You can only call f and g if you have a value of type 'initialized', and your
only chance to get it is to call 'init'. This is a good example how to use
types as assertions about state. This simply means that the type checker prooves
for you that f and g are never called before init.

To get rid of dereferencing is impossible. Perhaps a mutable
record is faster in some cases.

--
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 100             
64293 Darmstadt     EMail:   Gerd.Stolpmann@darmstadt.netsurf.de (privat)
Germany                     
----------------------------------------------------------------------------