[Ocaml-lib-devel] benchmarking enum approaches

[Alan P. <ap...@re...>]

I wrote a little program to benchmark the three approaches I've seen
discussed on the list for implementing streams/enums:

  1.  (e.next ()) returns an option
  2.  for-loop style, relying on the count (not suitable for
      streams, including filtered enums)
  3.  exception-catching style (the current implementation)

It tests folds over maps of enums of constant ints.

Runs of it (ocamlopt compiled, of course) demonstrate to me that:

  a)  The option-based approach is slowest, especially when doing lots
      of nested maps.

  b)  The for-loop approach is fastest.

  c)  The exception-based approach is in the middle, performance-wise.
      In the pathological case (only one map, with only five elements
      in the enum), this approach takes 1.4 times as much CPU as the
      for-loop approach.  With three nested maps, and 500 elements in
      the enum, it requires 1.13 times the CPU.

So I think the question is:  is it worth a 10-20% performance hit in
the library to unify the stream and enum types?

Another possibility would be to be clever about having fold and iter
use (e.count ()) when it is fast, and use exception catching when
(e.count ()) is slow, without actually having separate types.

Below is the program listing.  Please let me know if I screwed up
somewhere.

  Alan

------------------------------------------------------------

(* 
 * bench.ml
 *
 * Author:  Alan Post <ap...@re...>
 * Usage:   test performance of various implementations of Enum
 * 
 * 1:  option-based    (also suitable for streams)
 * 2:  count-based     (not suitable for streams)
 * 3:  exception-based (also suitable for streams)
 *)

type 'a enum_1 = { mutable next: unit -> 'a option; mutable count: unit -> int };;
type 'a enum_2 = { mutable next: unit -> 'a;        mutable count: unit -> int };;
exception No_more_elements;;

let rec fold_1 f x e =
    match e.next () with
        None -> x
      | Some v -> fold_1 f (f v x) e

and map_1 f e =
    { count = e.count;
      next  = (fun () ->
               match e.next () with
                   None -> None
                 | Some v -> Some (f v))}

and init_1 value num =
    let rnum = ref num in
    { count = (fun () -> !rnum);
      next = (fun () ->
              match !rnum with
                0 -> None
              | _ -> Some (decr rnum; value))}

and fold_2 f x e =
    let rec loop c accu =
        match c with
          0 -> accu
        | _ -> loop (c-1) (f (e.next ()) accu)
    in
    loop (e.count ()) x

and map_2 f e =
    { count = e.count;
      next = (fun () -> f (e.next ()))}

and init_2 value num =
    let rnum = ref num in
    { count = (fun () -> !rnum);
      next = (fun () ->
              match !rnum with
                0 -> raise No_more_elements
              | _ -> (decr rnum; value))}

and fold_3 f x e =
    let result = ref x in
    let rec loop () =
        result := f (e.next ()) !result;
        loop ()
    in
    try loop ()
    with No_more_elements -> !result

in
let map_3 = map_2
and init_3 = init_2
in
let nest f n =
    let rec loop f g n =
        match n with
          0 -> g
        | _ -> loop f (fun e -> f (g e)) (n-1)
    in loop f f n

and which = Sys.argv.(1)
and items = (int_of_string Sys.argv.(2))
and nests = (int_of_string Sys.argv.(3))
and iters = (int_of_string Sys.argv.(4))
in
let once = match which with
      "1" -> (fun () -> ignore (fold_1 (+) 0
                                       ((nest (map_1 (( * ) 2)) nests)
                                       (init_1 1 items))))
    | "2" -> (fun () -> ignore (fold_2 (+) 0
                                       ((nest (map_2 (( * ) 2)) nests)
                                       (init_2 1 items))))
    | "3" -> (fun () -> ignore (fold_3 (+) 0
                                       ((nest (map_3 (( * ) 2)) nests)
                                       (init_3 1 items))))
    |  _  -> raise (Invalid_argument which)
in
let rec loop n = if n == 0 then () else (once (); loop (n-1))
in
loop iters;
print_string "done\n";;