Merge commit 'upstream/0.9'

30 files changed, 206 insertions, 65 deletions

diff --git a/INSTALL b/INSTALL
index 0b87f8e..6345095 100644
--- a/INSTALL
+++ b/INSTALL
@@ -2,38 +2,36 @@
                       INSTALLATION INSTRUCTIONS
 ----------------------------------------------------------------------
 
-* Unix (including MacosX)
-
 Build the library:
 
-	$ make
+	$ ocamlbuild benchmark.cma benchmark.cmxa
 
 If you want to test it, use (requires findlib)
 
-	$ make examples
-
-Install it (requires findlib):
+	$ ocamlbuild examples.byte
+	$ ocamlbuild examples.native
 
-	$ make install
+	The compiled programs are in _build/examples/.  You can run a
+	specific example, say examples/ar-ba.ml, in (say) native code
+	by issuing (you need not to compile the examples before if you
+	use this way):
 
-Clean up the build and examples directory:
+	$ ocamkbuild examples/ar-ba.native --
 
-	$ make clean
+Install it:
 
-Remove the installed library (requires findlib):
+	$ ./build/install
 
-	$ make uninstall
+Clean up the build and examples directory:
 
+	$ ocamlbuild -clean
 
-"findlib" is available at
-http://www.ocaml-programming.de/programming/download-caml.html
+Remove the installed library:
 
-If installing a bundle of libraries, these same commands work in the
-parent directory, and furthermore, the ordering of the build due to
-the library interdependies are taken care of for you.
+	$ ./build/uninstall
 
 
-* Windows
+* Windows (until ocamlbuild works properly on that platform)
 
 A file "Make.bat" is provided for compilation (you may want to comment
 some lines if you do not have ocamlopt working).  You will have to
diff --git a/LICENSE b/LICENSE
index 90eb57e..cee4c0a 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,5 +1,6 @@
 This Library is distributed under the terms of the GNU Lesser General
-Public License version 2.1 (included below).
+Public License version 2.1 (included below) or, at your option, any
+later version.
 
 As a special exception to the GNU Lesser General Public License, you
 may link, statically or dynamically, a "work that uses the Library"
diff --git a/META b/META
index 8cd4042..5cecc3c 100644
--- a/META
+++ b/META
@@ -1,6 +1,6 @@
 # Specifications for the Benchmark module             		-*-conf-*-
 name = "benchmark"
-version = "0.8"
+version = "0.9"
 description = "Benchmark running times of code."
 requires = "unix"
 archive(byte) = "benchmark.cma"
diff --git a/Make.bat b/Make.bat
deleted file mode 100644
index d3ed13c..0000000
--- a/Make.bat
+++ /dev/null
@@ -1,5 +0,0 @@
-ocamlc unix.cma -c benchmark.mli
-ocamlc -c benchmark.ml
-ocamlc -a -o benchmark.cma benchmark.cmo
-ocamlopt -c benchmark.ml
-ocamlopt -a -o benchmark.cmxa benchmark.cmx
diff --git a/Makefile b/Makefile
index ea0cc6b..e30a397 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,3 @@
-# $Id: Makefile,v 1.10 2007/01/31 16:41:49 chris_77 Exp $
-
 OCAMLCFLAGS=-dtypes
 OCAMLOPTFLAGS=-dtypes
 OCAMLDOCFLAGS=-html -stars -colorize-code -I +contrib
@@ -17,7 +15,10 @@ PKG_TARBALL  = ocaml-$(PKGNAME)-$(PKGVERSION).tar.gz
 SRC_WEB    = web
 SF_WEB     = /home/groups/o/oc/ocaml-benchmark/htdocs
 
-default: all
+default:
+	@echo -n "This project now uses 'ocamlbuild' for the build phase.  "
+	@echo -e "Please type\n\tocamlbuild all.otarget"
+	@echo "(If you nonetheless want to use 'make' type 'make all'.)"
 
 
 ######################################################################
@@ -146,7 +147,7 @@ include .depend
 .PHONY: clean distclean
 clean:
 	rm -f *~ *.cmi *.cmo *.cmx *.cma *.cmxa *.a *.o *.tmp
-	rm -f Make.bat $(PKG_TARBALL)
+	rm -f Make.bat $(PKG_TARBALL) *.dat
 	rm -rf doc/
 	cd examples/; $(MAKE) clean
 
diff --git a/README b/README
index 8533ec8..2cac0a6 100644
--- a/README
+++ b/README
@@ -1,10 +1,8 @@
-# $Id: README,v 1.2 2004/08/25 11:36:59 chris_77 Exp $
-
 
   Benchmark - measure/compare run-time of OCaml functions
 
 
-  Copyright 2004, Christophe Troestler
+  Copyright 2004-present, Christophe Troestler
 
   Copyright 2002-2003, Doug Bagley
   http://www.bagley.org/~doug/ocaml/
@@ -22,8 +20,8 @@ Send your comments, bug reports,... to chris_77@users.sourceforge.net
 
 This library is free software; you can redistribute it and/or modify
 it under the terms of the GNU Lesser General Public License version
-2.1 as published by the Free Software Foundation, with the special
-exception on linking described in file LICENSE.
+2.1 or later as published by the Free Software Foundation, with the
+special exception on linking described in file LICENSE.
 
 This library is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
diff --git a/_tags b/_tags
new file mode 100644
index 0000000..f6fe8a0
--- /dev/null
+++ b/_tags
@@ -0,0 +1,4 @@
+<**/*.ml>: dtypes
+<examples/*.{byte,native}>: use_unix, use_benchmark
+<examples/{try-if,ar-ba}.{byte,native}>: use_bigarray
+<examples/regexps.*>: use_str, use_pcre
diff --git a/all.itarget b/all.itarget
new file mode 100644
index 0000000..80aacce
--- /dev/null
+++ b/all.itarget
@@ -0,0 +1,4 @@
+benchmark.cma
+benchmark.cmxa
+examples.byte
+examples.native
diff --git a/benchmark.ml b/benchmark.ml
index 9bdba69..25cd492 100644
--- a/benchmark.ml
+++ b/benchmark.ml
@@ -2,7 +2,7 @@
    For comparing runtime of functions
    *********************************************************************
 
-   Copyright 2004-2007, Troestler Christophe
+   Copyright 2004-present, Troestler Christophe
    Christophe.Troestler(at)umh.ac.be
 
    Copyright 2002-2003, Doug Bagley
@@ -20,7 +20,6 @@
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the file
    LICENSE for more details.
 *)
-(* $Id: benchmark.ml,v 1.10 2007/01/31 16:41:49 chris_77 Exp $ *)
 
 open Printf
 
@@ -32,9 +31,9 @@ type t = {
   cstime : float;
   iters  : Int64.t;
   (* As of version 0.8, one had to change [iter] from [int] because,
-     as machines run fast, a number of iterations of 2^29 was no
+     as machines run faster, a number of iterations ~ 2^29 is no
      longer enough (2^29 is the largest > 0 power of 2 that [int] can
-     hold. *)
+     hold on a 32 bits platform. *)
 }
 
 type style = No_child | No_parent | All | Auto | Nil
@@ -43,8 +42,8 @@ let null_t =
   { wall = 0.; utime = 0.; stime = 0.; cutime = 0.; cstime = 0.; iters = 0L }
 
 let make n =
-  let tms = Unix.times () in
-  { wall = Unix.time ();
+  let tms = Unix.times() in
+  { wall = Unix.gettimeofday();
     utime = tms.Unix.tms_utime;   stime = tms.Unix.tms_stime;
     cutime = tms.Unix.tms_cutime; cstime = tms.Unix.tms_cstime;
     iters = n }
@@ -90,15 +89,15 @@ let to_string ?(style=Auto) ?(fwidth=5) ?(fdigits=2) b =
   let f x = sprintf "%*.*f" fwidth fdigits x in
   match style with
   | All ->
-      sprintf "%2.0f WALL (%s usr %s sys + %s cusr %s csys = %s CPU)%s"
-        b.wall (f b.utime) (f b.stime) (f b.cutime) (f b.cstime) (f(pt +. ct))
-        (iter_info pt)
+      sprintf "%s WALL (%s usr %s sys + %s cusr %s csys = %s CPU)%s"
+        (f b.wall) (f b.utime) (f b.stime) (f b.cutime) (f b.cstime)
+        (f(pt +. ct)) (iter_info pt)
   | No_child ->
-      sprintf "%2.0f WALL (%s usr + %s sys = %s CPU)%s"
-        b.wall (f b.utime) (f b.stime) (f pt) (iter_info pt)
+      sprintf "%s WALL (%s usr + %s sys = %s CPU)%s"
+        (f b.wall) (f b.utime) (f b.stime) (f pt) (iter_info pt)
   | No_parent ->
-      sprintf "%2.0f WALL (%s cusr + %s csys = %s CPU)%s"
-        b.wall (f b.cutime) (f b.cstime) (f ct) (iter_info ct)
+      sprintf "%s WALL (%s cusr + %s csys = %s CPU)%s"
+        (f b.wall) (f b.cutime) (f b.cstime) (f ct) (iter_info ct)
   | Nil -> ""
   | Auto -> assert false
 
@@ -111,7 +110,7 @@ let rec string_of_time t =
   else if t < 120 then "1m " ^ string_of_time(t - 60)
   else string_of_int(t / 60) ^ "m " ^ string_of_time(t mod 60)
 
-(* The time is rounded to the nearest integer: *)
+(* The time [t >= 0] is rounded to the nearest integer: *)
 let string_of_time t = string_of_time(truncate(t +. 0.5))
 
 
@@ -296,9 +295,12 @@ let null_printer = { print_indent = (fun _ -> ());  print = (fun _ -> ()) }
 (* Generic interface for performing measurments on a list of functions *)
 let testN ~test default_f_name  ?min_count ?min_cpu ~style
     ?fwidth ?fdigits ~repeat funs =
+  let length_name =
+    List.fold_left (fun m (n,_,_) -> max m (String.length n)) 0 funs in
   let result_of (name, f, x) =
-    printf "%10s: %!" (if name = "" then default_f_name else name);
-    let out = if style = Nil then null_printer else make_printer 12 in
+    printf "%*s: %!" length_name (if name = "" then default_f_name else name);
+    let out = if style = Nil then null_printer
+              else make_printer (length_name + 2) in
     let bm = test out ?min_count ?min_cpu ~style ?fwidth ?fdigits
       ~repeat name f x in
     (name, bm) in
@@ -311,7 +313,7 @@ let rec string_of_names funs =
 let latencyN ?min_cpu ?(style=Auto) ?fwidth ?fdigits ?(repeat=1) n funs =
   if n < 4L then invalid_arg "Benchmark.latencyN: n < 4";
   if style <> Nil then (
-    printf "Latencies for %Ld iterations@ of %s%s:\n%!" n
+    printf "Latencies for %Ld iterations of %s%s:\n%!" n
       (string_of_names funs)
       (if repeat > 1 then sprintf " (%i runs)" repeat else "");
   );
@@ -489,7 +491,9 @@ let by_rates (_,_,r1,_) (_,_,r2,_) = compare (r1:float) r2
 
 (* Check whether two rates are significantly different.  With a small
    [significance], a [true] returned value means that the rates are
-   significantly different. *)
+   significantly different.  [n1] is the number of repetitions of the
+   test1, [r1] is its mean rate and [s1] its standard deviation.
+   [n2], [r2] and [s2] are similar for the test2. *)
 let different_rates significance  n1 r1 s1  n2 r2 s2 =
   assert(n1 > 0 && n2 > 0);
   if n1 = 1 && n2 = 1 then true (* no info about distribution, assume
diff --git a/benchmark.mli b/benchmark.mli
index de3fcc8..4129613 100644
--- a/benchmark.mli
+++ b/benchmark.mli
@@ -17,7 +17,6 @@
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the file
    LICENSE for more details.
 *)
-(* 	$Id: benchmark.mli,v 1.6 2007/01/31 16:41:49 chris_77 Exp $	 *)
 
 (** This module implements benchmarking functions for measuring the
  * run-time of one or many functions using latency (multiple
@@ -43,9 +42,9 @@
  *
  * Time how long it takes to some piece of code:
  * {[
- * let t0 = Benchmark.make 0 in
+ * let t0 = Benchmark.make 0L in
  * (* do something here *)
- * let b = Benchmark.sub (Benchmark.make 0) t0 in
+ * let b = Benchmark.sub (Benchmark.make 0L) t0 in
  * print_endline "Benchmark results:";
  * print_endline (Benchmark.to_string b)                       ]}
  *)
diff --git a/benchmark.mllib b/benchmark.mllib
new file mode 100644
index 0000000..100d5e8
--- /dev/null
+++ b/benchmark.mllib
@@ -0,0 +1 @@
+Benchmark
diff --git a/examples/Makefile b/examples/Makefile
index 9f303ba..598b499 100644
--- a/examples/Makefile
+++ b/examples/Makefile
@@ -3,13 +3,13 @@
 # Just type "make"!
 
 # Do not require that the package be installed to try the examples
-REQUIRES 	= "str unix pcre"
+REQUIRES 	= "str unix pcre bigarray"
 BENCHMARK	= -I .. benchmark.cma
 
 EXAMPLES        := $(wildcard *.ml)
 PACKAGE_OPTS    := $(if $(REQUIRES), -package $(REQUIRES), )
 PREDICATE_OPTS  := $(if $(PREDICATES), -predicates $(PREDICATES), )
-ALL_OPTS	= $(PACKAGE_OPTS) $(PREDICATE_OPTS)
+ALL_OPTS	= -dtypes $(PACKAGE_OPTS) $(PREDICATE_OPTS)
 
 OCAMLC		= ocamlfind ocamlc
 OCAMLOPT	= ocamlfind ocamlopt
@@ -30,7 +30,7 @@ opt:  $(EXAMPLES:.ml=.com)
 .PHONY: clean clobber
 
 clean:
-	rm -f $(EXAMPLES:.ml=.exe) $(EXAMPLES:.ml=.com) *.o *.cm[iox] *~
+	rm -f $(EXAMPLES:.ml=.exe) $(EXAMPLES:.ml=.com) *.o *.cm[iox] *~ *.dat
 
 clobber: clean
 	rm -f $(EXAMPLES)
diff --git a/examples/ar-ba.ml b/examples/ar-ba.ml
new file mode 100644
index 0000000..98a28e8
--- /dev/null
+++ b/examples/ar-ba.ml
@@ -0,0 +1,26 @@
+(* Compare bigarray and standard float array access times.  *)
+
+open Bigarray
+
+let n = 1000
+
+let a = Array1.create float64 fortran_layout n
+let () = Array1.fill a 1.
+
+let f1 () =
+  let s = ref 0. in
+  for i = 1 to n do s := !s +. a.{i} done
+
+let b = Array.make n 1.
+
+let f2 () =
+  let s = ref 0. in
+  for i = 0 to n-1 do s := !s +. b.(i) done
+
+
+open Benchmark
+
+let () =
+  let res = throughputN ~repeat:5 3 [("ba", f1, ());
+                                     ("arr", f2, ()) ] in
+  tabulate res
diff --git a/examples/composition.ml b/examples/composition.ml
new file mode 100644
index 0000000..bd1fdcd
--- /dev/null
+++ b/examples/composition.ml
@@ -0,0 +1,49 @@
+(* Tries to show the profile cost of composing small functions. *)
+
+(* Small functions: permutations of [0 .. n-1] *)
+
+let n = 100000
+let rotate r = fun k -> (k + r) mod n
+let reverse i j = fun k -> if i <= k && k <= j then j + i - k else k
+let splice l i j = fun k ->
+  if k < j then if k < i then k else k + l + 1
+  else if k <= j + l then k - j + i
+  else let k' = k - l - 1 in if k' < i then k' else k
+
+
+open Benchmark
+open Printf
+
+let ncomp = 400 (* Number of compositions *)
+
+let make_perms =
+  (* Create a random list of transformations *)
+  Random.self_init();
+  let rec random_perm ((p_f, p_v) as acc) i =
+    if i <= 0 then acc else
+      let c = Random.int 3 in
+      (* New function *)
+      let p =
+        if c = 0 then rotate (Random.int n)
+        else if c = 1 then reverse (Random.int n) (Random.int n)
+        else (* c = 2 *) splice (Random.int n) (Random.int n) (Random.int n) in
+      (* Corresponding array transformer *)
+      let p_vec w v =
+        for i = 0 to Array.length v - 1 do w.(i) <- p v.(i) done in
+      random_perm (p :: p_f, p_vec :: p_v) (i - 1) in
+  random_perm ([], [])
+
+let () =
+  let ncomp = 300 in
+  let p_f, p_v = make_perms ncomp in
+  let v = Array.init n (fun k -> k) in
+  let do_f () =
+    let f = List.fold_left (fun f f0 -> (fun k -> f0(f k))) (fun k -> k) p_f in
+    Array.map f v
+  and do_v () =
+    snd(List.fold_left (fun (w,v) f -> f w v; (v,w)) (Array.make n 0, v) p_v)
+  in
+
+  let res = throughputN ~repeat:3 5 [("fun", do_f, ());
+                                     ("vec", do_v, ()) ] in
+  tabulate res
diff --git a/examples/let-try.com b/examples/let-try.com
deleted file mode 100755
index d9d430c..0000000
--- a/examples/let-try.com
+++ /dev/null
diff --git a/examples/let-try.exe b/examples/let-try.exe
deleted file mode 100755
index b69aa03..0000000
--- a/examples/let-try.exe
+++ /dev/null
diff --git a/examples/let-try.ml b/examples/let-try.ml
index 483ab93..11100d9 100644
--- a/examples/let-try.ml
+++ b/examples/let-try.ml
@@ -1,5 +1,3 @@
-(* $Id: let-try.ml,v 1.1 2006/07/08 09:11:35 chris_77 Exp $ *)
-
 (* Compare two possible implementations of let try x = ... with ... *)
 
 let k x = if x >= 0 then x else failwith "x < 0"
diff --git a/examples/loops.com b/examples/loops.com
deleted file mode 100755
index 693d600..0000000
--- a/examples/loops.com
+++ /dev/null
diff --git a/examples/loops.exe b/examples/loops.exe
deleted file mode 100755
index ffc736f..0000000
--- a/examples/loops.exe
+++ /dev/null
diff --git a/examples/loops.ml b/examples/loops.ml
index 25d7351..c0710e7 100644
--- a/examples/loops.ml
+++ b/examples/loops.ml
@@ -1,5 +1,3 @@
-(* $Id: loops.ml,v 1.1 2004/08/25 11:40:37 chris_77 Exp $ *)
-
 open Benchmark
 
 (* Test for the speed of recusion w.r.t. imperative loops to access
diff --git a/examples/match-array.com b/examples/match-array.com
deleted file mode 100755
index 5a694ae..0000000
--- a/examples/match-array.com
+++ /dev/null
diff --git a/examples/match-array.exe b/examples/match-array.exe
deleted file mode 100755
index 8157d23..0000000
--- a/examples/match-array.exe
+++ /dev/null
diff --git a/examples/numbers.com b/examples/numbers.com
deleted file mode 100755
index dfa2eb7..0000000
--- a/examples/numbers.com
+++ /dev/null
diff --git a/examples/numbers.exe b/examples/numbers.exe
deleted file mode 100755
index ef0a4b4..0000000
--- a/examples/numbers.exe
+++ /dev/null
diff --git a/examples/numbers.ml b/examples/numbers.ml
index 22bdc64..38d22b9 100644
--- a/examples/numbers.ml
+++ b/examples/numbers.ml
@@ -1,5 +1,3 @@
-(* $Id: numbers.ml,v 1.2 2007/01/31 16:41:49 chris_77 Exp $ *)
-
 open Printf
 open Benchmark
 
diff --git a/examples/regexps.com b/examples/regexps.com
deleted file mode 100755
index dcc82e4..0000000
--- a/examples/regexps.com
+++ /dev/null
diff --git a/examples/regexps.exe b/examples/regexps.exe
deleted file mode 100755
index 95fab9c..0000000
--- a/examples/regexps.exe
+++ /dev/null
diff --git a/examples/regexps.ml b/examples/regexps.ml
index adf7f8d..8773daf 100644
--- a/examples/regexps.ml
+++ b/examples/regexps.ml
@@ -1,5 +1,3 @@
-(* $Id: regexps.ml,v 1.2 2007/01/31 16:41:49 chris_77 Exp $ *)
-
 open Printf
 open Benchmark
 
diff --git a/examples/try-if.ml b/examples/try-if.ml
new file mode 100644
index 0000000..5ea18b3
--- /dev/null
+++ b/examples/try-if.ml
@@ -0,0 +1,34 @@
+open Bigarray
+
+let n = 100
+
+let a = Array1.create float64 fortran_layout n
+
+(* Base case: no test *)
+let f0 () =
+  for i = 1 to n do
+    let x = a.{i} in
+    ignore(x)
+  done;
+  ignore(0.)
+
+let f1 () =
+  for i = 1 to n+1 do
+    let x = try a.{i} with _ -> 0. in
+    ignore(x)
+  done
+
+let f2 () =
+  for i = 1 to n+1 do
+    let x = if i <= n then a.{i} else 0. in
+    ignore(x)
+  done
+
+open Benchmark
+
+let () =
+  let res = throughputN ~repeat:5 3 [("no test", f0, ());
+                                     ("try", f1, ());
+                                     ("if", f2, ())  ] in
+  print_endline "Bigarray bound checking:";
+  tabulate res
diff --git a/myocamlbuild.ml b/myocamlbuild.ml
new file mode 100644
index 0000000..2779b86
--- /dev/null
+++ b/myocamlbuild.ml
@@ -0,0 +1,35 @@
+open Ocamlbuild_plugin
+open Command
+;;
+
+Options.make_links := false;;
+
+dispatch begin function
+| After_rules ->
+    ocaml_lib "benchmark";
+
+    let pcre = [A"-I"; A"+pcre"] in
+    flag ["compile"; "ocaml"; "use_pcre"] (S pcre);
+    flag ["link"; "program"; "ocaml"; "byte"; "use_pcre"]
+      (S(pcre @ [A"pcre.cma"]));
+    flag ["link"; "program"; "ocaml"; "native"; "use_pcre"]
+      (S(pcre @ [A"pcre.cmxa"]));
+
+    let examples_rule ext =
+      let examples =
+        Array.fold_right begin fun f acc ->
+          if Pathname.get_extension f = "ml" then
+            ("examples" / Pathname.update_extension ext f) :: acc
+          else
+            acc
+        end (Pathname.readdir "examples") [] in
+      rule ("All examples " ^ ext)
+        ~prod:("examples." ^ ext)
+        ~deps:examples
+        (fun _ _ -> Nop) in
+
+    examples_rule "byte";
+    examples_rule "native";
+
+| _ -> ()
+end