[caml] Closures and efficiency

[caml] Closures and efficiency

[Christopher Jeris]

I have a sort of naive question regarding the efficiency of higher-order
functions in data structures, and how well the Ocaml compiler does common
subexpression elimination on these.

The problem is the following.  I wish to write a universal voice editor
for music synthesizers.  Now a voice of a synth is characterized by a
large set of parameters, and this set (the names, ranges, meanings of each
parameter) is different for each synth.  The first thing it occurred to me
to do was to write a type:

type yamaha_AN1x_patch = { name: string; (* lots of parameters *) }
type yamaha_FS1R_patch = (* ... continue ad nauseam *)

But types are not first class; there is no way to write a general piece of
code which will look at a record type, see what its fields are and do
something (like display an edit window) which depends on the types of the
fields.  So instead I write types for meta-data:

type parameter = { name: string; doc: string; values: param_value_set; ... }
and param_value_set =
  Enumeration of enum_value list
| Int_subrange of int * int
| Strings
| ...
and enum_value = { name: string; encoded_value: int }

Now the description of a synth's voice architecture looks like

val yamaha_AN1x_patch =
  [ {name = "Patch name"; values = Strings};
    {name = "Filter cutoff frequency"; values = Int_subrange (0, 127)};
    ... ]

Okay.  Now synths can dump information about their voices via the MIDI
port, and the protocol for decoding this "sysex dump" into an intelligible
voice description is different for each synth.  So I need to have a way,
for each parameter appearing in each synth architecture, to specify its
translation to and from the raw byte-strings which appear on the MIDI
port.  If this were a C program, there would be one big translation
function that would do something like

- to encode an enumerated value, use its index in the list of enumerated
values for this parameter
- to encode a string value, use its ASCII representation
- to encode a member of an integer subrange, use its value minus the
bottom value of this subrange
...

But this is too monolithic, and in Ocaml we can put functional values in
data structures ... so I would rather have, along with each parameter, a
little function "encoder: param_value -> bytestring" and
"decoder: bytestring -> param_value" which know how to do the translation
for _this_ parameter.

Here's the nub of my question.  In a typical synth architecture there are
very many parameters which take values 0..127.  If I had a function

  int_subrange_encoder: int -> int -> param_value -> bytestring

which took the bounds of a subrange and generated an encoder function for
values of that subrange, and then in a voice-architecture description I
had a list of very many records each of which contained an entry

  int_subrange_encoder 0 127

would I suddenly have six million little closures, or would the compiler
do common-subexpression elimination on them ?  Or am I just taking a
totally wrongheaded approach ?

thanks,
Chris Jeris

Re: [caml] Closures and efficiency

[Xavier Leroy]

> Here's the nub of my question.  In a typical synth architecture there are
> very many parameters which take values 0..127.  If I had a function
> 
>   int_subrange_encoder: int -> int -> param_value -> bytestring
> 
> which took the bounds of a subrange and generated an encoder function for
> values of that subrange, and then in a voice-architecture description I
> had a list of very many records each of which contained an entry
> 
>   int_subrange_encoder 0 127
> 
> would I suddenly have six million little closures, or would the compiler
> do common-subexpression elimination on them ?

As of now, the compiler doesn't do any common subexpression
elimination.  Notice that CSE over function applications is hard,
because the compiler must make sure that the function has no side-effects.
E.g. assume your function int_subrange_encoder prints something after
receiving its first two arguments:

        let int_subrange_encoder lo hi =
          print_string "subrange_encoder was here!";
          fun param -> ...

Then, CSE would be incorrect.

An easy thing to do is to let-bind the partial applications that
occur frequently:

        let int_encoder = int_subrange_encoder 0 127

and then use "int_encoder" instead of "int_subrange_encoder 0 127"
in your descriptions.

Hope this helps,

- Xavier Leroy

Re: [caml] Closures and efficiency

[Francois Pottier]

Hello,

> Here's the nub of my question.  In a typical synth architecture there are
> very many parameters which take values 0..127.  If I had a function
> 
>   int_subrange_encoder: int -> int -> param_value -> bytestring
> 
> which took the bounds of a subrange and generated an encoder function for
> values of that subrange, and then in a voice-architecture description I
> had a list of very many records each of which contained an entry
> 
>   int_subrange_encoder 0 127
> 
> would I suddenly have six million little closures, or would the compiler
> do common-subexpression elimination on them ?

I don't know if the compiler performs CSE for expressions which involve
function applications (it would have to prove that the function
int_subrange_encoder does not perform side effects, which I think
it doesn't -- but I could be wrong).

However, if you're worried by memory consumption, you can easily create
a memoizing version of int_subrange_encoder. Here is a generic "memoize"
function which accepts any 1-parameter function f and returns a
memoizing version of it. (You can adapt it for 2 arguments if you wish,
or uncurry the function int_subrange_encoder, as I have done below.)

  let memoize f =
    let table = Hashtbl.create 1023 in
    fun argument ->
      try
	Hashtbl.find table argument
      with Not_found ->
	let result = f argument in
	Hashtbl.add table argument result;
	result

Of course, memoizing a function f only makes sense if it is applicative,
i.e. it returns the same result when applied twice, and it performs no
observable side effects. You can write:

  let int_subrange_encoder (x, y) =
    ...

  let memoized_int_subrange_encoder =
    memoize int_subrange_encoder

Hope this helps,

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/