Commits

Yit Phang Khoo committed cfc4ce1

Move benchmarks into a new directory Benchmarks.

Comments (0)

Files changed (105)

Benchmarks/BenchmarkAdapton/runbenchmarkadapton.ml

+open Adapton.Statistics
+
+let list_filter_task (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float) =
+    L.memo_filter (fun x -> log (1. +. x) < log 1.5)
+
+let list_map_task (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float) =
+    L.memo_map (module L) (fun x -> log (1. +. x) +. log 1.5)
+
+let list_tfold_min_task (type a) (type b) (module L : Adapton.Signatures.SAListType.S with type t = a and type SAData.t = b and type data = float) =
+    L.memo_tfold min
+
+let list_tfold_sum_task (type a) (type b) (module L : Adapton.Signatures.SAListType.S with type t = a and type SAData.t = b and type data = float) =
+    L.memo_tfold (+.)
+
+let list_quicksort_task (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float) =
+    L.memo_quicksort Pervasives.compare
+
+let list_mergesort_task (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float) =
+    L.memo_mergesort Pervasives.compare
+
+let list_updown1_task
+        (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float)
+        (type b) (module B : Adapton.Signatures.SAType.S with type t = b and type data = bool)
+        xs b =
+    let up = L.memo_quicksort Pervasives.compare in
+    let down = L.memo_quicksort (fun x y -> -(Pervasives.compare x y)) in
+    L.thunk (fun () -> L.force (if B.force b then up xs else down xs))
+
+let list_updown2_task
+        (type a) (module L : Adapton.Signatures.SAListType.S with type t = a and type data = float)
+        (type b) (module B : Adapton.Signatures.SAType.S with type t = b and type data = bool)
+        xs b =
+    let up = L.memo_quicksort Pervasives.compare xs in
+    let down = L.memo_quicksort (fun x y -> -(Pervasives.compare x y)) xs in
+    L.thunk (fun () -> L.force (if B.force b then up else down))
+
+let tasks = [
+    ( "filter", `List list_filter_task );
+    ( "map", `List list_map_task );
+    ( "tfold(min)", `One list_tfold_min_task );
+    ( "tfold(sum)", `One list_tfold_sum_task );
+    ( "quicksort", `List list_quicksort_task );
+    ( "mergesort", `List list_mergesort_task );
+    ( "updown1", `Flip list_updown1_task );
+    ( "updown2", `Flip list_updown2_task );
+    ( "exptree", `ExpTree );
+]
+
+let opt_sa = ref (fst (List.hd Adapton.All.sa_list))
+let opt_task = ref "filter"
+let opt_input_size = ref 1
+let opt_repeat_count = ref 1
+let opt_edit_count = ref 1
+let opt_take_count = ref 1
+let opt_random_seed = ref 1
+let opt_monotonic = ref false
+
+let header ff = Printf.fprintf ff "%24s %24s %8d %8d %20d" !opt_sa !opt_task !opt_take_count !opt_input_size !opt_random_seed
+let stats ff s =
+    Printf.fprintf ff "\"time\": %.17g, \"heap\": %.17g, \"stack\": %.17g, \"update\": %.17g, \"evaluate\": %.17g, \"dirty\": %.17g, \"clean\": %.17g"
+        s.time s.heap s.stack s.update s.evaluate s.dirty s.clean
+let max_heap_stack ff ( heap, stack ) = Printf.fprintf ff "\"max-heap\": %.17g, \"max-stack\": %.17g" (word_bytes heap) (word_bytes stack)
+let units =
+    "\"units\": { \"time\": \"seconds\", \"heap\": \"bytes\", \"stack\": \"bytes\", "
+    ^ "\"update\": null, \"evaluate\": null, \"dirty\": null, \"clean\": null, "
+    ^ "\"max-heap\": \"bytes\", \"max-stack\": \"bytes\" }"
+
+let show_config () =
+    let list_printer printer ff list =
+        ignore (List.fold_left (fun b x -> Printf.fprintf ff "%(%)%a" b printer x; ", ") "" list)
+    in
+    let task_printer ff task =
+        Printf.fprintf ff "{ \"name\": %S, \"take\": %S }"
+            (fst task) (match snd task with `One _ -> "one" | `List _ -> "list" | `Flip _ -> "flip" | `ExpTree -> "exptree")
+    in
+    Printf.printf "{ \"modules\": [ %a ], \"tasks\": [ %a ] }\n%!"
+        (list_printer (fun ff -> Printf.fprintf ff "%S")) (fst (List.split Adapton.All.sa_list))
+        (list_printer task_printer) tasks;
+    exit 0
+
+let exptree (module SA : Adapton.Signatures.SAType) rng =
+    if !opt_input_size < 4 then begin
+        Printf.eprintf "Task %s only supports -I n where n >= 4\n%!" !opt_task;
+        exit 1
+    end;
+    if !opt_take_count != 1 then begin
+        Printf.eprintf "Task %s only supports -T 1\n%!" !opt_task;
+        exit 1
+    end;
+    let module F = SA.Make (Adapton.Types.Float) in
+    let module E = struct
+        type e = e' SA.thunk
+        and e' = Num of float | Op of op * e * e
+        and op = Plus | Mul | Minus | Div
+        module E = SA.Make (struct
+            type t = e'
+            let hash seed = function
+                | Num f -> Hashtbl.seeded_hash seed f
+                | Op  ( op, x, y ) -> SA.hash (SA.hash (Hashtbl.seeded_hash seed op) x) y
+            let equal x y = x == y || match x, y with
+                | Num x, Num y -> x == y
+                | Op ( op1, x1, y1 ), Op ( op2, x2, y2 ) -> op1 == op2 && SA.equal x1 x2 && SA.equal y1 y2
+                | _ -> false
+        end)
+        include E
+        let rand_num () = Num (Random.State.float rng 1.0)
+        let rand_op x y =
+            let op = if Random.State.bool rng then
+                if Random.State.bool rng then Plus else Mul
+            else
+                if Random.State.bool rng then Minus else Div
+            in
+            if Random.State.bool rng then
+                Op ( op, x, y )
+            else
+                Op ( op, y, x )
+        let eval = F.memo (module E) begin fun eval e -> match E.force e with
+            | Num f -> f
+            | Op ( Plus, x, y ) -> F.force (eval x) +. F.force (eval y)
+            | Op ( Mul, x, y ) -> F.force (eval x) *. F.force (eval y)
+            | Op ( Minus, x, y ) -> F.force (eval x) -. F.force (eval y)
+            | Op ( Div, x, y ) -> let y = F.force (eval y) in F.force (eval x) /. (if y == 0. then 1. else y)
+        end
+    end in
+    SA.tweak_gc ();
+    Gc.compact ();
+    let start_time = get_time () in
+
+    let x =
+        let rec make_xs n acc = if n > 0 then
+            make_xs (n - 1) (E.const (E.rand_num ())::acc)
+        else
+            let rec make_xs acc n = function
+                | x::y::rest ->
+                    let x = if Random.State.bool rng then
+                        if Random.State.bool rng then E.Op ( E.Plus, x, y ) else E.Op ( E.Mul, x, y )
+                    else
+                        if Random.State.bool rng then E.Op ( E.Minus, x, y ) else E.Op ( E.Div, x, y )
+                    in
+                    make_xs (E.const x::acc) (n + 1) rest
+                | y::[] when n > 0 -> make_xs [] 0 (y::acc)
+                | y::[] -> y
+                | [] -> make_xs [] 0 acc
+            in
+            make_xs [] 0 acc
+        in
+        make_xs !opt_input_size []
+    in
+
+    Printf.eprintf "%t\n%!" header;
+    begin try
+        let take, setup_stats = measure begin fun () ->
+            let ys = Array.init !opt_repeat_count (fun _ -> E.eval x) in
+            let take () = Array.iter (fun y -> ignore (F.force y)) ys in
+            take ();
+            take
+        end in
+        let setup_stats = finish setup_stats 1 in
+        let setup_top_heap_stack = get_top_heap_stack () in
+
+        if SA.is_self_adjusting then begin
+            let half = int_of_float (floor (log (float_of_int !opt_input_size) /. log 2. /. 2.)) in
+            let rec do_edits past n update_stats take_stats edit_count =
+                if n == 0 then
+                    ( update_stats, take_stats, edit_count )
+                else begin
+                    let past =
+                        let now = get_time () in
+                        if now -. past < 20. then
+                            past
+                        else begin
+                            let heap, stack = get_top_heap_stack () in
+                            Printf.eprintf "%t edit %10d %9.2fMB %9.2fMB\n%!"
+                                header n (word_megabytes heap) (word_megabytes stack);
+                            now
+                        end
+                    in
+
+                    let update_stats', take_stats', edit_count' = if !opt_monotonic then
+                        (* add/remove one leaf *)
+                        let rec change add x = match E.force x with
+                            | E.Op ( op, a, b ) ->
+                                let dir = Random.State.bool rng in
+                                let y = if dir then a else b in
+                                begin match E.force y with
+                                    | E.Num _ as z ->
+                                        if add then
+                                            E.update_const y (E.rand_op (E.const z) (E.const (E.rand_num ())))
+                                        else
+                                            E.update_const x (E.force (if dir then b else a))
+                                    | _ ->
+                                        change add y
+                                end
+                            | E.Num _ ->
+                                failwith "change"
+                        in
+
+                        let (), update_stats = measure (fun () -> change false x) in
+                        let (), take_stats = measure (fun () -> SA.refresh (); take ()) in
+                        let (), update_stats' = measure (fun () -> change true x) in
+                        let (), take_stats' = measure (fun () -> SA.refresh (); take ()) in
+
+                        ( add update_stats update_stats', add take_stats take_stats', 2 )
+                    else
+                        (* swap two nodes *)
+                        let rec pick n x =
+                            if n == 0 then x else match E.force x with
+                                | E.Op ( op, a, b ) ->
+                                    let dir = Random.State.bool rng in
+                                    pick (n - 1) (if dir then a else b)
+                                | E.Num _ ->
+                                    failwith "pick"
+                        in
+                        let a = pick half x in
+                        let b =
+                            let rec pick_b () = let b = pick half x in if b == a then pick_b () else b in
+                            pick_b ()
+                        in
+                        let (), update_stats = measure begin fun () -> match E.force a, E.force b with
+                            | E.Op ( aop, a1, a2 ), E.Op ( bop, b1, b2 ) ->
+                                if Random.State.bool rng then
+                                    if Random.State.bool rng then begin
+                                        E.update_const a (E.Op ( aop, a1, b1 ));
+                                        E.update_const b (E.Op ( bop, a2, b2 ));
+                                    end else begin
+                                        E.update_const a (E.Op ( aop, b2, a2 ));
+                                        E.update_const b (E.Op ( bop, b1, a1 ));
+                                    end
+                                else
+                                    if Random.State.bool rng then begin
+                                        E.update_const a (E.Op ( aop, b1, a2 ));
+                                        E.update_const b (E.Op ( bop, a1, b2 ));
+                                    end else begin
+                                        E.update_const a (E.Op ( aop, a1, b2 ));
+                                        E.update_const b (E.Op ( bop, b1, a2 ));
+                                    end
+                            | _ ->
+                                failwith "swap"
+                        end in
+
+                        let (), take_stats = measure (fun () -> SA.refresh (); take ()) in
+
+                        ( update_stats, take_stats, 1 )
+                    in
+
+                    do_edits past (pred n)
+                        (add update_stats update_stats')
+                        (add take_stats take_stats')
+                        (edit_count + edit_count')
+                end
+            in
+            let update_stats, take_stats, edit_count = do_edits 0. !opt_edit_count zero zero 0 in
+            let edit_top_heap_stack = get_top_heap_stack () in
+            let update_stats = finish update_stats !opt_edit_count in
+            let take_stats = finish take_stats !opt_edit_count in
+            Printf.printf "{ \"setup\": { %a, %a }, \"edits\": { \"update\": { %a }, \"take\": { %a }, %a }, %s }\n%!"
+                stats setup_stats max_heap_stack setup_top_heap_stack stats update_stats stats take_stats max_heap_stack edit_top_heap_stack units;
+            Printf.eprintf "%t ... done (%9.2fs) %9.3gs edit %9.3gs\n%!"
+                header (get_time () -. start_time) setup_stats.time (update_stats.time +. take_stats.time)
+        end else begin
+            Printf.printf "{ \"setup\": { %a, %a }, %s }\n%!"
+                stats setup_stats max_heap_stack setup_top_heap_stack units;
+            Printf.eprintf "%t ... done (%9.2fs) %9.3gs\n%!" header (get_time () -. start_time) setup_stats.time
+        end
+
+    with e ->
+        let err = Printexc.to_string e in
+        Printf.printf ("{ \"error\": %S }\n%!") err;
+        Printf.eprintf "%s\n%!" err;
+        Printf.eprintf "%t ... done (%9.2fs)\n%!" header (get_time () -. start_time)
+    end;
+    exit 0
+
+let _ =
+    Arg.parse (Arg.align [
+        ( "-c", Arg.Unit show_config, " output available configuration" );
+        ( "-m", Arg.Symbol ( (fst (List.split Adapton.All.sa_list)), (fun s -> opt_sa := s) ), "list module" );
+        ( "-t", Arg.Symbol ( (fst (List.split tasks)), (fun s -> opt_task := s) ), "list task" );
+        ( "-I", Arg.Set_int opt_input_size, "size input size" );
+        ( "-R", Arg.Set_int opt_repeat_count, "count repeat count" );
+        ( "-T", Arg.Set_int opt_take_count, "count take count" );
+        ( "-E", Arg.Set_int opt_edit_count, "count edit count" );
+        ( "-S", Arg.Set_int opt_random_seed, "seed random seed" );
+        ( "-M", Arg.Set opt_monotonic, "monotonic edits" );
+    ]) (fun s -> raise (Arg.Bad ("extraneous argument " ^ s))) (Sys.argv.(0) ^ " [options]");
+
+    let rng = Random.State.make [| !opt_random_seed |] in
+    Random.init (Random.State.bits rng);
+    let module SA = (val (List.assoc !opt_sa Adapton.All.sa_list)) in
+    begin match List.assoc !opt_task tasks with
+        | `ExpTree -> exptree (module SA) rng
+        | _ -> ()
+    end;
+    let module SABool = SA.Make (Adapton.Types.Bool) in
+    let module SAList = Adapton.SAList.Make (SA) in
+    let module SAFloatList = SAList.Make (Adapton.Types.Float) in
+    SA.tweak_gc ();
+    Gc.compact ();
+    let task = match List.assoc !opt_task tasks with
+        | `One task ->
+            if !opt_take_count != 1 then begin
+                Printf.eprintf "Task %s only supports -T 1\n%!" !opt_task;
+                exit 1
+            end;
+            `One (task (module SAFloatList))
+        | `List task ->
+            `List (task (module SAFloatList))
+        | `Flip task ->
+            if !opt_monotonic then begin
+                Printf.eprintf "Task %s does not support -M\n%!" !opt_task;
+                exit 1
+            end;
+            `Flip (task (module SAFloatList) (module SABool))
+        | `ExpTree ->
+            failwith "exptree"
+    in
+
+    let start_time = get_time () in
+
+    let xs = ref (SAFloatList.const `Nil) in
+    let xss = Array.init !opt_input_size begin fun _ ->
+        xs := SAFloatList.const (`Cons (Random.State.float rng 1.0, !xs));
+        !xs
+    end in
+    let xs = !xs in
+    let last = ref 0 in
+
+    let b = SABool.const false in
+
+    Printf.eprintf "%t\n%!" header;
+    try
+        let take, setup_stats = measure begin fun () ->
+            let take = match task with
+                | `List task ->
+                    let yss = Array.init !opt_repeat_count (fun _ -> task xs) in
+                    (fun () -> Array.iter (fun ys -> ignore (SAFloatList.take ys !opt_take_count)) yss)
+                | `One task ->
+                    let ys = Array.init !opt_repeat_count (fun _ -> task xs) in
+                    (fun () -> Array.iter (fun y -> ignore (SAFloatList.SAData.force y)) ys)
+                | `Flip task ->
+                    let yss = Array.init !opt_repeat_count (fun _ -> task xs b) in
+                    (fun () -> Array.iter (fun ys -> ignore (SAFloatList.take ys !opt_take_count)) yss)
+                | `ExpTree ->
+                    failwith "exptree"
+            in
+            take ();
+            take
+        end in
+        let setup_stats = finish setup_stats 1 in
+        let setup_top_heap_stack = get_top_heap_stack () in
+
+        if SA.is_self_adjusting then begin
+            let rec do_edits past n update_stats take_stats edit_count =
+                if n == 0 then
+                    ( update_stats, take_stats, edit_count )
+                else begin
+                    let past =
+                        let now = get_time () in
+                        if now -. past < 20. then
+                            past
+                        else begin
+                            let heap, stack = get_top_heap_stack () in
+                            Printf.eprintf "%t edit %10d %9.2fMB %9.2fMB %6.0fs left\n%!"
+                                header n (word_megabytes heap) (word_megabytes stack)
+                                (float_of_int n *. (get_time () -. start_time) /. float_of_int (!opt_edit_count - n));
+                            now
+                        end
+                    in
+
+                    let update_stats', take_stats', edit_count' = match task with
+                        | `List _ | `One _ when !opt_monotonic ->
+                            (* delete then re-insert *)
+                            let edit = Random.State.int rng !opt_input_size in
+                            let zs = xss.(edit) in
+
+                            let ( z', zs' ), delete_update_stats = measure begin fun () ->
+                                match SAFloatList.force zs with
+                                    | `Cons ( z', zs' ) ->
+                                        SAFloatList.update_const zs (SAFloatList.force zs');
+                                        ( z', zs' )
+                                    | `Nil ->
+                                        failwith "delete"
+                            end in
+
+                            let (), delete_take_stats = measure begin fun () ->
+                                SA.refresh ();
+                                take ()
+                            end in
+
+                            let (), insert_update_stats = measure begin fun () ->
+                                SAFloatList.update_const zs (`Cons ( z', zs' ))
+                            end in
+
+                            let (), insert_take_stats = measure begin fun () ->
+                                SA.refresh ();
+                                take ()
+                            end in
+
+                            ( add delete_update_stats insert_update_stats, add delete_take_stats insert_take_stats, 2 )
+
+                        | `List _ | `One _ ->
+                            (* split into two and swap *)
+                            let edit = 1 + Random.State.int rng (!opt_input_size - 2) in
+                            let edit = if edit = !last then edit + 1 else edit in
+                            let zs = xss.(edit) in
+
+                            let (), update_stats = measure begin fun () ->
+                                match SAFloatList.force xs with
+                                    | `Cons _ as xs' ->
+                                        begin match SAFloatList.force xss.(!last) with
+                                            | `Cons _ as last' ->
+                                                begin match SAFloatList.force zs with
+                                                    | `Cons _ as zs' ->
+                                                        SAFloatList.update_const xs zs';
+                                                        SAFloatList.update_const xss.(!last) xs';
+                                                        SAFloatList.update_const zs last';
+                                                        last := edit;
+                                                    | `Nil ->
+                                                        failwith "swap"
+                                                end
+                                            | `Nil ->
+                                                failwith "swap"
+                                        end
+                                    | `Nil ->
+                                        failwith "swap"
+                            end in
+
+                            let (), take_stats = measure begin fun () ->
+                                SA.refresh ();
+                                take ()
+                            end in
+
+                            ( update_stats, take_stats, 1 )
+
+                        | `Flip _ ->
+                            (* change one value *)
+                            let edit = Random.State.int rng !opt_input_size in
+                            let value = Random.State.float rng 1.0 in
+                            let zs = xss.(edit) in
+
+                            let (), update_stats = measure begin fun () ->
+                                SABool.update_const b (not (SABool.force b));
+                                match SAFloatList.force zs with
+                                    | `Cons ( _, zs' ) ->
+                                        SAFloatList.update_const zs (`Cons ( value, zs' ))
+                                    | `Nil ->
+                                        failwith "flip"
+                            end in
+
+                            let (), take_stats = measure (fun () -> SA.refresh (); take ()) in
+                            let (), update_stats' = measure (fun () -> SABool.update_const b (not (SABool.force b))) in
+                            let (), take_stats' = measure (fun () -> SA.refresh (); take ()) in
+
+                            ( add update_stats update_stats', add take_stats take_stats', 2 )
+
+                        | `ExpTree ->
+                            failwith "exptree"
+                    in
+
+                    do_edits past (pred n)
+                        (add update_stats update_stats')
+                        (add take_stats take_stats')
+                        (edit_count + edit_count')
+                end
+            in
+            let update_stats, take_stats, edit_count = do_edits 0. !opt_edit_count zero zero 0 in
+            let edit_top_heap_stack = get_top_heap_stack () in
+            let update_stats = finish update_stats edit_count in
+            let take_stats = finish take_stats edit_count in
+            Printf.printf "{ \"setup\": { %a, %a }, \"edits\": { \"update\": { %a }, \"take\": { %a }, %a }, %s }\n%!"
+                stats setup_stats max_heap_stack setup_top_heap_stack stats update_stats stats take_stats max_heap_stack edit_top_heap_stack units;
+            Printf.eprintf "%t ... done (%9.2fs) %9.3gs edit %9.3gs\n%!"
+                header (get_time () -. start_time) setup_stats.time (update_stats.time +. take_stats.time)
+        end else begin
+            Printf.printf "{ \"setup\": { %a, %a }, %s }\n%!"
+                stats setup_stats max_heap_stack setup_top_heap_stack units;
+            Printf.eprintf "%t ... done (%9.2fs) %9.3gs\n%!" header (get_time () -. start_time) setup_stats.time
+        end
+
+    with e ->
+        let err = Printexc.to_string e in
+        Printf.printf ("{ \"error\": %S }\n%!") err;
+        Printf.eprintf "%s\n%!" err;
+        Printf.eprintf "%t ... done (%9.2fs)\n%!" header (get_time () -. start_time)

Benchmarks/BenchmarkAdapton/runbenchmarkadapton.py

+#!/usr/bin/env python
+
+import json, os, psutil, random, subprocess, sys, time, threading, traceback
+from collections import defaultdict, OrderedDict
+from itertools import chain, imap, izip, product, cycle
+
+runbenchmarkadapton_native = "%s%s%s" % ( os.path.splitext(__file__)[0], os.path.extsep, "native" )
+
+
+def driver(( module, task, size, repeat, take, edit, monotonic, seed )):
+    driver_start_time = time.time()
+    rng = random.Random(seed)
+    results = OrderedDict((
+        ( "module", module ), ( "task", task ),
+        ( "size", size ), ( "repeat", repeat), ( "take", take ), ( "edit", edit ), ( "monotonic", monotonic ),
+        ( "seed", seed ) ))
+    try:
+        cmd = [ runbenchmarkadapton_native, "-m", "%s" % ( module, ), "-t", str(task), "-I", str(size), "-R", str(repeat), "-T", str(take), "-E", str(edit) ]
+        if monotonic:
+            cmd.append("-M")
+        cmd.extend(( "-S", str(seed) ))
+        native = subprocess.Popen(cmd, stdout=subprocess.PIPE, env={ "BENCHMARK_SALIST_ENV": " " * rng.randrange(4096) })
+        results.update(json.load(native.stdout, object_pairs_hook=OrderedDict))
+        return results
+
+    except Exception, KeyboardInterrupt:
+        error = traceback.format_exc()
+        results["error"] = error
+        print>>sys.stderr, error
+        print>>sys.stderr, "%32s %24s %4d %10d %20d ... error (%9.2fs)" % ( module, task, take, size, seed, time.time() - driver_start_time )
+        return results
+    finally:
+        try:
+            native.kill()
+        except:
+            pass
+
+
+def physical_cpu_count():
+    if sys.platform.startswith("darwin"):
+        cpu_count = int(subprocess.check_output([ "sysctl", "-n", "hw.physicalcpu" ]))
+    elif sys.platform.startswith("linux"):
+        import re
+        re_cpuinfo = re.compile(r"siblings\s+: ([0-9]+).*?cpu cores\s+: ([0-9]+)", re.MULTILINE | re.DOTALL)
+        cpu_count = int(sum(map(lambda m: float(m.group(2)) / float(m.group(1)), re_cpuinfo.finditer(open("/proc/cpuinfo").read()))))
+    else:
+        print>>sys.stderr, "Warning: physical_cpu_count() not implemented for %s; using %d" % ( sys.platform, multiprocessing.cpu_count() )
+    global physical_cpu_count
+    physical_cpu_count = lambda: cpu_count
+    return cpu_count
+
+
+if __name__ == "__main__":
+    import argparse, errno, gzip, multiprocessing, pprint, re, urllib
+
+    config = json.loads(subprocess.check_output([ runbenchmarkadapton_native, "-c" ]))
+    config["modules"] = map(str, config["modules"])
+    config["baselines"] = [ config["modules"][-1] ]
+    config["takes"] = { str(m["name"]) : str(m["take"]) for m in config["tasks"] }
+    config["tasks"] = config["takes"].keys()
+    config["output"] = "Results/BenchmarkAdapton"
+
+    parser = argparse.ArgumentParser()
+    subparsers = parser.add_subparsers(dest="subparser")
+
+    benchmark = subparsers.add_parser("benchmark", help="run benchmark")
+    benchmark.add_argument("-O", "--output", metavar="DIRECTORY",
+        help="run benchmark and store results in a subdirectory of %(metavar)s (default: \"%(const)s\")", default=config["output"])
+    benchmark.add_argument("-L", "--label", metavar="LABEL", help="optionally append %(metavar)s to result directory")
+    benchmark.add_argument("-P", "--processes", metavar="N", help="run %(metavar)s benchmarks in parallel", default=physical_cpu_count(), type=int)
+    benchmark.add_argument("-m", "--modules", metavar="MODULE",
+        help="apply benchmark to %(metavar)s(s) (default: \"%(default)s\")", nargs="+", default=config["modules"], choices=config["modules"])
+    benchmark.add_argument("-b", "--baselines", metavar="BASELINE",
+        help="compare modules against %(metavar)s(s) (default: \"%(default)s\")", nargs="+", default=config["baselines"], choices=config["modules"])
+    benchmark.add_argument("-t", "--tasks", metavar="TASK",
+        help="apply benchmark to %(metavar)s(s) (default: \"%(default)s\")", nargs="+", default=config["tasks"], choices=config["tasks"])
+    benchmark.add_argument("-I", "--input-sizes", metavar="SIZE",
+        help="run benchmarks with input size (default: 100000 10000 1000 100 50000 5000 500 50 200000 20000 2000 200 20)",
+        nargs="+", default=( 100000, 10000, 1000, 100, 50000, 5000, 500, 50, 20000, 2000, 200, 20 ), type=int)
+    benchmark.add_argument("-R", "--repeat-count", metavar="REPEAT",
+        help="repeat the computation on the same input %(metavar)s times per cycle (default: 1)",
+        default=1, type=int)
+    benchmark.add_argument("-T", "--take-counts", metavar="TAKE", help="take only the first %(metavar)s elements of each output (default: 1)",
+        nargs="+", default=( 1, ), type=int)
+    benchmark.add_argument("-E", "--edit-count", metavar="COUNT", help="average self-adjusting benchmarks over %(metavar)s edits ",
+        default=250, type=int)
+    benchmark.add_argument("-M", "--monotonic", help="make monotonic edits ", action="store_true")
+    benchmark.add_argument("-S", "--random-seeds", metavar="SEED", help="run benchmark for seeds (default: 5 random seeds)",
+        nargs="+", default=random.sample(xrange(sys.maxint >> 1), 5), type=int)
+
+    resummarize = subparsers.add_parser("resummarize", help="resummarize benchmark results")
+    resummarize.add_argument("-I", "--inputs", metavar="DIRECTORY",
+        help="resummarize benchmark results in %(metavar)s(s) (default: \"%(default)s\")", nargs="+", default=( os.path.join(config["output"], "latest"), ))
+    resummarize.add_argument("-O", "--output", metavar="DIRECTORY",
+        help="save benchmark summary in %(metavar)s (default: if only one directory is given for -I/--inputs, the same directory; "
+            + "otherwise, a subdirectory in \"%s\")" % ( config["output"], ), nargs="?")
+    resummarize.add_argument("-L", "--label", metavar="LABEL", help="optionally append %(metavar)s to summary directory")
+    resummarize.add_argument("-b", "--baselines", metavar="BASELINE",
+        help="compare modules against %(metavar)s(s) (default: \"%(default)s\")", nargs="+", default=config["baselines"], choices=config["modules"])
+
+    args = parser.parse_args()
+
+    if args.subparser == "resummarize":
+        inputs = args.inputs
+        if args.output is None:
+            if len(inputs) == 1:
+                output = inputs[0]
+                if args.label:
+                    output += " " + args.label.strip()
+                    os.makedirs(output)
+                if inputs[0] == os.path.join(config["output"], "latest") and os.path.islink(inputs[0]):
+                    output_label = os.path.basename(os.readlink(inputs[0]))
+                else:
+                    output_label = os.path.basename(output)
+            else:
+                output_label = time.strftime("%Y-%m-%d-%H-%M-%S summary")
+                if args.label:
+                    output_label += " " + args.label.strip()
+                output = os.path.join(config["output"], output_label)
+                os.makedirs(output)
+                latest = os.path.join(config["output"], "latest")
+                try:
+                    os.unlink(latest)
+                except OSError:
+                    pass
+                try:
+                    os.symlink(output_label, latest)
+                except OSError:
+                    print>>sys.stderr, traceback.format_exc()
+                    print>>sys.stderr, "warning: cannot create latest symlink to summary"
+        else:
+            output = args.output
+            if args.label:
+                output += " " + args.label.strip()
+            os.makedirs(output)
+            output_label = os.path.basename(output)
+    else:
+        assert args.subparser == "benchmark"
+        if args.processes < 1 or args.processes > physical_cpu_count():
+            parser.error("-P/--processes must be between 1 and %d (the total number of physical processor cores)" % ( physical_cpu_count(), ))
+        if len(set(args.input_sizes)) > 1 and len(set(args.take_counts)) > 1:
+            parser.error("either -I/--input-sizes or -T/--take-counts must be given only one unique value")
+        elif len(set(args.input_sizes)) == 1 and len(set(args.take_counts)) == 1:
+            parser.error("-I/--input-sizes and -T/--take-counts must not both be given only one unique value each")
+        if min(args.input_sizes) < 4:
+            for task in args.tasks:
+                if config["takes"][task] == "exptree":
+                    parser.error("-t/--tasks \"%s\" only supports -I/--input-sizes n where n >= 4" % ( task, ))
+        if len(set(args.take_counts)) > 1 or any(take != 1 for take in args.take_counts):
+            for task in args.tasks:
+                if config["takes"][task] == "one" or config["takes"][task] == "exptree" :
+                    parser.error("-t/--tasks \"%s\" only supports -T/--take-counts 1" % ( task, ))
+        if args.monotonic:
+            for task in args.tasks:
+                if config["takes"][task] == "flip":
+                    parser.error("-t/--tasks \"%s\" does not support -M/--monotonic" % ( task, ))
+        for baseline in args.baselines:
+            if baseline not in args.modules:
+                args.modules.append(baseline)
+
+        output_label = time.strftime("%Y-%m-%d-%H-%M-%S")
+        if args.monotonic:
+            output_label += " monotonic"
+        if args.label:
+            output_label += " " + args.label.strip()
+        output = os.path.join(args.output, output_label)
+        os.makedirs(output)
+        inputs = [ output ]
+        latest = os.path.join(args.output, "latest")
+        try:
+            os.unlink(latest)
+        except OSError:
+            pass
+        try:
+            os.symlink(output_label, latest)
+        except OSError:
+            print>>sys.stderr, traceback.format_exc()
+            print>>sys.stderr, "warning: cannot create latest symlink to benchmark"
+
+        print>>sys.stderr, "Using random seeds %s" % ( args.random_seeds, )
+
+        pool = multiprocessing.Pool(processes=args.processes, maxtasksperchild=1)
+
+        @apply
+        class heartbeat(object):
+            def __init__(self):
+                self.flags = []
+            def __enter__(self):
+                flag = threading.Event()
+                thread = threading.Thread(target=self.run, args=( flag, ))
+                thread.daemon = True
+                self.flags.append(flag)
+                thread.start()
+            def __exit__(self, exc_type, exc_val, exc_tb):
+                self.flags.pop().set()
+            def run(self, flag):
+                start = time.time()
+                max_load = 0
+                min_free = float("inf")
+                while not flag.is_set():
+                    elapsed = time.time() - start
+                    load = os.getloadavg()
+                    free = psutil.virtual_memory().free / 1024 / 1024
+                    max_load = max(max_load, *load)
+                    min_free = min(min_free, free)
+                    print>>sys.stderr, "==== Elapsed: %5ds  ==== Load: %5.2f %5.2f %5.2f (max: %5.2f) ==== Mem: %6dM free (min: %6dM) ====" \
+                        % ( elapsed, load[0], load[1], load[2], max_load, free, min_free )
+                    flag.wait(3)
+
+        with heartbeat:
+            for task in args.tasks:
+                results = []
+                try:
+                    # don't use pool.apply_async, it triggers http://bugs.python.org/issue10332
+                    for result in pool.imap_unordered(driver, ( ( module, task, size, args.repeat_count, take, args.edit_count, args.monotonic, seed )
+                            for take in args.take_counts
+                            for size in args.input_sizes
+                            for seed in args.random_seeds
+                            for module in random.sample(args.modules, len(args.modules)) )):
+                        # don't use extend, so that if an exception or interrupt occurs, we still have some results
+                        results.append(result)
+                except Exception:
+                    traceback.print_exc()
+                except KeyboardInterrupt:
+                    pool.terminate()
+                    pool.join()
+                    sys.exit()
+                finally:
+                    if len(args.input_sizes) > 1:
+                        assert len(args.take_counts) == 1
+                        results = OrderedDict((
+                            ( "label", "take count = %d" % args.take_counts[0] ),
+                            ( "x-axis", "size" ),
+                            ( "x-label", "input size" ),
+                            ( "data", results )
+                        ))
+                    else:
+                        assert len(args.input_sizes) == 1 and len(args.take_counts) > 1
+                        results = OrderedDict((
+                            ( "label", "input size = %d" % args.input_sizes[0] ),
+                            ( "x-axis", "take" ),
+                            ( "x-label", "take count" ),
+                            ( "data", results )
+                        ))
+                    with gzip.open(os.path.join(output, "%s-%04d.json.gz" % ( task, len(results) )), "w") as jsonfile:
+                        json.dump(results, jsonfile, indent=4, separators=( ",", ":" ))
+
+    print>>sys.stderr, "Generating summary in %s ..." % ( output, )
+    files = sorted(set(chain.from_iterable( ( file for file in os.listdir(path) if file.endswith(".json.gz") ) for path in inputs )))
+
+
+    import math
+    from decimal import Decimal
+    from matplotlib.backends.backend_agg import FigureCanvasAgg as FigureCanvas
+    from matplotlib.figure import Figure
+    from matplotlib.ticker import Formatter
+    from scipy import stats
+
+    class Tee(object):
+        def __init__(self, stream, name, *args, **kwargs):
+            self.stream = stream
+            self.file = open(name, *args, **kwargs)
+        def __enter__(self):
+            self.file.__enter__()
+            return self
+        def __exit__(self, exc_type, exc_val, exc_tb):
+            return self.file.__exit__(exc_type, exc_val, exc_tb)
+        def write(self, s):
+            self.stream.write(s)
+            self.file.write(s)
+
+    class EngFormatter(Formatter):
+        def __init__(self, places=3):
+            self.places = places
+
+        def __call__(self, num, pos=None):
+            num = Decimal(str(num))
+
+            if num != 0:
+                exp = Decimal(math.floor(abs(num).log10() / 3) * 3)
+            else:
+                exp = Decimal(0)
+
+            mantissa = num / ( 10 ** exp )
+            result = "%.*g" % ( self.places, mantissa )
+            if exp != 0:
+                result += "e%+d" % ( exp, )
+            return result
+
+    styles = defaultdict(( { "color": color, "linestyle": linestyle, "marker": marker, "markersize": markersize }
+        for color, ( linestyle, ( marker, markersize ) ) in izip(
+            cycle(( "black", "darkblue", "darkred", "darkgreen", "darkcyan", "dimgray" )),
+            cycle(product(( "-", "--", "-." ), ( ( ".", 8 ), ( "^", 6 ), ( "s", 4 ), ( "*", 7 ), ( "D", 4 ) ))) )).next)
+
+    scalings = defaultdict(lambda: ( ( 1.01, ( "from-scratch", "propagate" ) ), ))
+    scalings["time"] += ( (  1.01, ( "propagate", ) ), )
+    scalings["evaluate"] += ( (  1.01, ( "propagate", ) ), )
+
+
+    with open(os.path.join(output, "index.html"), "w") as htmlfile:
+        print>>htmlfile, "<!doctype html>"
+        print>>htmlfile, "<meta charset=utf-8>"
+        print>>htmlfile, "<title>%s</title>" % ( output_label, )
+        print>>htmlfile, "<style>figure.inline-figure { display: inline-block; margin: 0; }</style>"
+
+        with Tee(sys.stderr, os.path.join(output, "summary.txt"), "w") as txtfile:
+            for file in files:
+                print>>txtfile, "    Summarizing %s ..." % ( file, )
+                label = file[:-8]
+                summary = os.path.join(output, label)
+                print>>htmlfile, "<h1 id=\"%s\">%s</h1>" % ( label, label )
+
+                try:
+                    os.makedirs(summary)
+                except OSError as e:
+                    if e.errno != errno.EEXIST:
+                        raise
+
+                results = None
+                for path in inputs:
+                    filepath = os.path.join(path, file)
+                    print>>txtfile, "        Loading %s ..." % ( filepath, ),
+                    try:
+                        more_results = json.load(gzip.open(filepath), object_pairs_hook=OrderedDict)
+                        if not results:
+                            results = more_results
+                        else:
+                            if more_results["label"] != results["label"]:
+                                raise ValueError("inconsistent label in results:\nexpected: %s\ngot: %s" % ( results["label"], more_results["label"] ))
+                            if more_results["x-axis"] != results["x-axis"]:
+                                raise ValueError("inconsistent x-axis in results:\nexpected: %s\ngot: %s" % ( results["x-axis"], more_results["x-axis"] ))
+                            if more_results["x-label"] != results["x-label"]:
+                                raise ValueError("inconsistent x-label in results:\nexpected: %s\ngot: %s" % ( results["x-label"], more_results["x-label"] ))
+                            results["data"].extend(more_results["data"])
+                    except IOError as e:
+                        if e.errno != errno.ENOENT:
+                            raise
+                        print>>txtfile, " not found"
+                    except Exception:
+                        traceback.print_exc()
+                    else:
+                        print>>txtfile, " done"
+
+                table = OrderedDict( ( key, {} ) for key in ( "time", "heap", "stack", "update", "evaluate", "clean", "dirty", "max-heap", "max-stack" ) )
+                units = {}
+                editables = set()
+                for record in results["data"]:
+                    try:
+                        for key in table.iterkeys():
+                            table[key].setdefault("from-scratch", {}).setdefault(record["module"], {}) \
+                                .setdefault(record[results["x-axis"]], []).append(record["setup"][key])
+                        if units and units != record["units"]:
+                            raise ValueError("inconsistent units in results:\nexpected: %s\ngot: %s" % ( pprint.pformat(units), pprint.pformat(record["units"]) ))
+                        units.update(record["units"])
+                    except Exception:
+                        traceback.print_exc()
+                        if "error" in record:
+                            pprint.pprint(dict(record))
+                    else:
+                        if "edits" in record:
+                            editables.add(record["module"])
+                            try:
+                                for key in table.iterkeys():
+                                    if key.startswith("max-"):
+                                        table[key].setdefault("propagate", {}).setdefault(record["module"], {}) \
+                                            .setdefault(record[results["x-axis"]], []).append(record["edits"][key])
+                                    else:
+                                        table[key].setdefault("propagate", {}).setdefault(record["module"], {}) \
+                                            .setdefault(record[results["x-axis"]], []).append(record["edits"]["update"][key] + record["edits"]["take"][key])
+                                        table[key].setdefault("update", {}).setdefault(record["module"], {}) \
+                                            .setdefault(record[results["x-axis"]], []).append(record["edits"]["update"][key])
+                            except Exception:
+                                traceback.print_exc()
+                                if "error" in record:
+                                    pprint.pprint(dict(record))
+
+                xmax = {}
+                ymax = {}
+                for measurement, measurement_table in table.iteritems():
+                    xmax[measurement] = {}
+                    ymax[measurement] = {}
+                    for timing, module_table in measurement_table.iteritems():
+                        for module, xvalues in module_table.iteritems():
+                            for xvalue, yvalues in xvalues.iteritems():
+                                avg = stats.tmean(yvalues)
+                                xvalues[xvalue] = avg
+                                xmax[measurement][timing] = max(xmax[measurement].get(timing, 0), xvalue)
+                                ymax[measurement][timing] = max(ymax[measurement].get(timing, 0), avg)
+                            module_table[module] = OrderedDict(sorted(xvalues.iteritems()))
+                        measurement_table[timing] = OrderedDict(
+                            sorted(module_table.iteritems(), key=lambda ( module, xvalues ): max(xvalues.itervalues()), reverse=True))
+
+                for measurement, measurement_table in table.iteritems():
+                    for yadjust, timings in scalings[measurement]:
+                        if timings == ( "propagate", ) and not editables:
+                            continue
+                        print>>txtfile, "        Plotting %s (%.2fx of %s)" % ( measurement, yadjust, timings )
+                        pdffilename = "%s-%s-%s-%s.pdf" % ( label, measurement, yadjust, "-".join(timings) )
+                        with open(os.path.join(summary, pdffilename), "w") as pdffile:
+                            fig = FigureCanvas(Figure(figsize=( 3.5, 3 ))).figure
+                            ax = fig.add_subplot(1, 1, 1)
+                            ax.set_title(results["label"], fontsize=8)
+                            ax.set_xlabel(results["x-label"], fontsize=8)
+                            if units[measurement]:
+                                ax.set_ylabel("%s (%s)" % ( measurement, units[measurement] ), fontsize=8)
+                            else:
+                                ax.set_ylabel("%s" % ( measurement, ), fontsize=8)
+                            for axis in ( ax.get_xaxis(), ax.get_yaxis() ):
+                                axis.set_major_formatter(EngFormatter())
+                                axis.set_ticks_position("none")
+                            if hasattr(ax, "tick_params"):
+                                ax.tick_params(labelsize=7)
+                            for side in ( "left", "bottom" ):
+                                ax.spines[side].set_color("silver")
+                                ax.spines[side].set_linestyle("dotted")
+                                ax.spines[side].set_linewidth(0.5)
+                            for side in ( "right", "top" ):
+                                ax.spines[side].set_visible(False)
+                            ax.grid(linewidth=0.5, linestyle=":", color="silver")
+
+                            for timing in ( "from-scratch", "propagate" ):
+                                if timing == "propagate" and not editables:
+                                    continue
+                                module_table = measurement_table[timing]
+                                for module, xvalues in module_table.iteritems():
+                                    xvalues, yvalues = zip(*xvalues.iteritems())
+                                    print>>txtfile, "            %50s ... %s" \
+                                        % ( "%s (%s)" % ( module, timing ), " ".join( format(yvalue, "9.3g") for yvalue in yvalues ) )
+                                    ax.plot(xvalues, yvalues, clip_on=False, label="%s (%s)" % ( module, timing ), markeredgecolor="none",
+                                        **styles[module, timing])
+                            ax.set_xbound(lower=0)
+                            ax.set_ybound(lower=0, upper=yadjust * max( ymax[measurement].get(timing, 0) for timing in timings ))
+
+                            try:
+                                ax.legend(loc="best", prop={ "size": 8 }, frameon=False, fancybox=False)
+                            except TypeError:
+                                ax.legend(loc="best", prop={ "size": 8 }, fancybox=False)
+
+                            if hasattr(fig, "tight_layout"):
+                                fig.tight_layout(pad=0.5)
+
+                            fig.savefig(pdffile, format="pdf")
+                            print>>htmlfile, "<figure class=inline-figure><img src=%s></figure>" \
+                                % ( os.path.join(label, urllib.pathname2url(pdffilename)), )
+
+
+                if editables:
+                    for measurement in ( "time", "evaluate" ):
+                        for baseline in args.baselines:
+                            pdffilename = "%s-%s-%s-overhead.pdf" % ( label, baseline, measurement )
+                            with open(os.path.join(summary, pdffilename), "w") as pdffile:
+                                fig = FigureCanvas(Figure(figsize=( 3.5, 3 ))).figure
+                                ax = fig.add_subplot(1, 1, 1)
+                                ax.set_title(results["label"], fontsize=8)
+                                ax.set_xlabel(results["x-label"], fontsize=8)
+                                ax.set_ylabel("%s overhead\nX (from-scratch) / %s (from-scratch)" % ( measurement, baseline ), fontsize=8, multialignment="center")
+                                for axis in ( ax.get_xaxis(), ax.get_yaxis() ):
+                                    axis.set_major_formatter(EngFormatter())
+                                    axis.set_ticks_position("none")
+                                if hasattr(ax, "tick_params"):
+                                    ax.tick_params(labelsize=7)
+                                for side in ( "left", "bottom" ):
+                                    ax.spines[side].set_color("silver")
+                                    ax.spines[side].set_linestyle("dotted")
+                                    ax.spines[side].set_linewidth(0.5)
+                                for side in ( "right", "top" ):
+                                    ax.spines[side].set_visible(False)
+                                ax.grid(linewidth=0.5, linestyle=":", color="silver")
+
+                                print>>txtfile, "        Plotting %s overhead using baseline %s ..." % ( measurement, baseline )
+                                for module in table[measurement]["from-scratch"].iterkeys():
+                                    if module == baseline:
+                                        continue
+                                    xvalues, overheads = zip(*( ( xvalue, yvalue / table[measurement]["from-scratch"][baseline][xvalue] ) \
+                                        for xvalue, yvalue in table[measurement]["from-scratch"][module].iteritems() ))
+                                    print>>txtfile, "            %32s ... %s" % ( module, " ".join( format(overhead, "9.3g") for overhead in overheads ) )
+                                    ax.plot(xvalues, overheads, clip_on=False, label=module, markeredgecolor="none", **styles[module, "from-scratch"])
+                                ax.set_xbound(lower=0)
+                                ax.set_ybound(lower=0)
+
+                                try:
+                                    ax.legend(loc="best", prop={ "size": 8 }, frameon=False, fancybox=False)
+                                except TypeError:
+                                    ax.legend(loc="best", prop={ "size": 8 }, fancybox=False)
+
+                                if hasattr(fig, "tight_layout"):
+                                    fig.tight_layout(pad=0.5)
+
+                                fig.savefig(pdffile, format="pdf")
+                                print>>htmlfile, "<figure class=inline-figure><img src=%s></figure>" \
+                                    % ( os.path.join(label, urllib.pathname2url(pdffilename)), )
+
+
+                        for baseline in args.baselines:
+                            pdffilename = "%s-%s-%s-speedup.pdf" % ( label, baseline, measurement )
+                            with open(os.path.join(summary, pdffilename), "w") as pdffile:
+                                fig = FigureCanvas(Figure(figsize=( 3.5, 3 ))).figure
+                                ax = fig.add_subplot(1, 1, 1)
+                                ax.set_title(results["label"], fontsize=8)
+                                ax.set_xlabel(results["x-label"], fontsize=8)
+                                ax.set_ylabel("%s speed-up\n%s (from-scratch) / X" % ( measurement, baseline ), fontsize=8, multialignment="center")
+                                for axis in ( ax.get_xaxis(), ax.get_yaxis() ):
+                                    axis.set_major_formatter(EngFormatter())
+                                    axis.set_ticks_position("none")
+                                if hasattr(ax, "tick_params"):
+                                    ax.tick_params(labelsize=7)
+                                for side in ( "left", "bottom" ):
+                                    ax.spines[side].set_color("silver")
+                                    ax.spines[side].set_linestyle("dotted")
+                                    ax.spines[side].set_linewidth(0.5)
+                                for side in ( "right", "top" ):
+                                    ax.spines[side].set_visible(False)
+                                ax.grid(linewidth=0.5, linestyle=":", color="silver")
+
+                                print>>txtfile, "        Plotting %s speed-up using baseline %s ..." % ( measurement, baseline )
+                                for module in table[measurement]["from-scratch"].iterkeys():
+                                    if module == baseline:
+                                        continue
+                                    if module in editables:
+                                        timing = "propagate"
+                                    else:
+                                        timing = "from-scratch"
+                                    xvalues, speedups = zip(*( ( xvalue, table[measurement]["from-scratch"][baseline][xvalue] / yvalue ) \
+                                        for xvalue, yvalue in table[measurement][timing][module].iteritems() ))
+                                    print>>txtfile, "            %50s ... %s" \
+                                        % ( "%s (%s)" % ( module, timing ), " ".join( format(speedup, "9.3g") for speedup in speedups ) )
+                                    ax.plot(xvalues, speedups, clip_on=False, label="%s (%s)" % ( module, timing ), markeredgecolor="none",
+                                        **styles[module, timing])
+                                ax.set_xbound(lower=0)
+                                ax.set_ybound(lower=0)
+
+                                try:
+                                    ax.legend(loc="best", prop={ "size": 8 }, frameon=False, fancybox=False)
+                                except TypeError:
+                                    ax.legend(loc="best", prop={ "size": 8 }, fancybox=False)
+
+                                if hasattr(fig, "tight_layout"):
+                                    fig.tight_layout(pad=0.5)
+
+                                fig.savefig(pdffile, format="pdf")
+                                print>>htmlfile, "<figure class=inline-figure><img src=%s></figure>" \
+                                    % ( os.path.join(label, urllib.pathname2url(pdffilename)), )
+
+
+                    for module in editables:
+                        print>>txtfile, "        Plotting %s details ..." % ( module, )
+                        pdffilename = "%s-%s-details.pdf" % ( label, module )
+                        with open(os.path.join(summary, pdffilename), "w") as pdffile:
+                            fig = FigureCanvas(Figure(figsize=( 3.5, 3 ))).figure
+                            ax = fig.add_subplot(1, 1, 1)
+                            ax.set_title("%s details; %s" % ( module, results["label"] ), fontsize=8)
+                            ax.set_xlabel(results["x-label"], fontsize=8)
+                            ax.set_ylabel("time (%s)" % ( units["time"], ), fontsize=8)
+                            for axis in ( ax.get_xaxis(), ax.get_yaxis() ):
+                                axis.set_major_formatter(EngFormatter())
+                                axis.set_ticks_position("none")
+                            if hasattr(ax, "tick_params"):
+                                ax.tick_params(labelsize=7)
+                            for side in ( "left", "bottom" ):
+                                ax.spines[side].set_color("silver")
+                                ax.spines[side].set_linestyle("dotted")
+                                ax.spines[side].set_linewidth(0.5)
+                            for side in ( "right", "top" ):
+                                ax.spines[side].set_visible(False)
+                            ax.grid(linewidth=0.5, linestyle=":", color="silver")
+
+                            for timing in ( "propagate", "update" ):
+                                xvalues, yvalues = zip(*table["time"][timing][module].iteritems())
+                                print>>txtfile, "            %24s ... %s" \
+                                    % ( timing, " ".join( format(yvalue, "9.3g") for yvalue in yvalues ) )
+                                ax.plot(xvalues, yvalues, clip_on=False, label="%s" % ( timing, ), markeredgecolor="none", **styles[module, timing])
+                            ax.set_xbound(lower=0)
+                            ax.set_ybound(lower=0)
+
+                            try:
+                                ax.legend(loc="best", prop={ "size": 8 }, frameon=False, fancybox=False)
+                            except TypeError:
+                                ax.legend(loc="best", prop={ "size": 8 }, fancybox=False)
+
+                            if hasattr(fig, "tight_layout"):
+                                fig.tight_layout(pad=0.5)
+
+                            fig.savefig(pdffile, format="pdf")
+                            print>>htmlfile, "<figure class=inline-figure><img src=%s></figure>" \
+                                % ( os.path.join(label, urllib.pathname2url(pdffilename)), )
+
+        import cgi
+        print>>htmlfile, "<h1 id=\"summary\">Summary</h1>"
+        print>>htmlfile, "<pre>"
+        print>>htmlfile, cgi.escape(open(os.path.join(output, "summary.txt")).read())
+        print>>htmlfile, "</pre>"
+
+        print>>htmlfile, "<style>div#header { position: fixed; top: 0; right: 0; padding: 0.5em; background: white }</style>"
+        print>>htmlfile, "<div id=\"header\">"
+        print>>htmlfile, "<a href=\"#summary\">Summary</a>"
+        for label in ( file[:-8] for file in files ):
+            print>>htmlfile, "<a href=\"#%s\">%s</a>" % ( label, label )
+        print>>htmlfile, "</div>"

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/TITLE

+Vary number of sheets; number of changes is fixed at 10

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2test-1156-2013.11.14.xlsx

Binary file added.

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2testeagersatotalorder.csv

+2, 10, 0.029212, 253952, 138, 420, 5768, 244, 0
+2, 10, 0.029367, 253952, 184, 420, 5693, 227, 7
+2, 10, 0.029488, 253952, 106, 420, 5443, 136, 0
+2, 10, 0.029507, 253952, 106, 420, 5581, 182, 0
+2, 10, 0.029469, 253952, 144, 420, 5575, 180, 0
+2, 10, 0.028108, 253952, 138, 420, 5325, 96, 0
+2, 10, 0.029152, 253952, 176, 420, 5823, 262, 0
+2, 10, 0.029580, 253952, 172, 420, 5615, 194, 0
+3, 10, 0.053693, 634880, 244, 620, 11698, 224, 4
+3, 10, 0.058461, 634880, 138, 620, 12326, 305, 5
+3, 10, 0.057739, 634880, 238, 620, 13099, 638, 0
+3, 10, 0.054458, 634880, 198, 620, 11449, 194, 0
+3, 10, 0.054807, 634880, 198, 620, 12047, 146, 0
+3, 10, 0.052070, 634880, 210, 620, 11395, 84, 0
+3, 10, 0.056672, 634880, 238, 620, 12592, 458, 0
+3, 10, 0.056419, 634880, 220, 620, 12496, 440, 6
+4, 10, 0.126895, 1142784, 246, 820, 28943, 2007, 35
+4, 10, 0.101842, 1269760, 288, 820, 23210, 482, 2
+4, 10, 0.108055, 1269760, 240, 820, 24785, 793, 5
+4, 10, 0.101370, 1269760, 288, 820, 22059, 542, 6
+4, 10, 0.094389, 1269760, 288, 820, 20275, 442, 0
+4, 10, 0.115084, 1269760, 256, 820, 26042, 1224, 30
+4, 10, 0.101368, 1269760, 292, 820, 22068, 484, 0
+4, 10, 0.107223, 1142784, 292, 820, 24843, 682, 8
+5, 10, 0.167977, 2031616, 330, 1020, 35986, 382, 4
+5, 10, 0.231494, 2031616, 318, 1020, 48296, 1870, 20
+5, 10, 0.228730, 1904640, 346, 1020, 47958, 1644, 12
+5, 10, 0.231730, 2031616, 324, 1020, 45208, 806, 0
+5, 10, 0.212181, 1904640, 348, 1020, 44217, 1402, 8
+5, 10, 0.176544, 1904640, 318, 1020, 39219, 952, 4
+5, 10, 0.240692, 1904640, 356, 1020, 50464, 2351, 19
+5, 10, 0.237654, 2031616, 312, 1020, 47857, 1794, 0
+6, 10, 0.324244, 3174400, 424, 1220, 63986, 716, 12
+6, 10, 0.353661, 3301376, 406, 1220, 75721, 1104, 0
+6, 10, 0.292006, 2920448, 400, 1220, 59770, 1112, 6
+6, 10, 0.470495, 4317184, 346, 1220, 96430, 2585, 143
+6, 10, 0.331875, 3174400, 330, 1220, 68271, 1680, 28
+6, 10, 0.368979, 2793472, 412, 1220, 69352, 1663, 5
+6, 10, 0.437113, 3936256, 378, 1220, 84671, 1930, 20
+6, 10, 0.490071, 3682304, 406, 1220, 99040, 4085, 15
+7, 10, 0.865683, 7110656, 478, 1420, 163792, 4281, 61
+7, 10, 0.408438, 3936256, 468, 1420, 83160, 176, 0
+7, 10, 0.598873, 5459968, 438, 1420, 114351, 1306, 0
+7, 10, 0.832157, 7110656, 466, 1420, 150503, 4210, 154
+7, 10, 1.170209, 8634368, 444, 1420, 203700, 4973, 137
+7, 10, 0.537874, 4952064, 414, 1420, 101146, 820, 6
+7, 10, 0.973403, 6602752, 476, 1420, 180158, 6793, 107
+7, 10, 0.520530, 4571136, 454, 1420, 97684, 1424, 4
+10, 10, 5.786310, 35299328, 612, 2020, 781114, 3621, 117
+10, 10, 5.879530, 25268224, 646, 2020, 813142, 13598, 762
+10, 10, 4.521012, 24760320, 660, 2020, 620373, 4125, 69
+10, 10, 3.666189, 24252416, 658, 2020, 484844, 1112, 24
+10, 10, 4.335880, 24125440, 652, 2020, 590265, 5388, 102
+10, 10, 8.853823, 31744000, 646, 2020, 1073107, 21084, 2282
+10, 10, 5.330309, 24252416, 640, 2020, 691836, 12984, 414
+10, 10, 12.109556, 42663936, 612, 2020, 1298877, 25121, 2993
+12, 10, 19.350194, 61202432, 772, 2420, 1834931, 11542, 400
+12, 10, 9.473370, 35680256, 778, 2420, 1025398, 4176, 76
+12, 10, 47.125485, 107421696, 780, 2420, 3155517, 18934, 1456
+12, 10, 16.106348, 69963776, 784, 2420, 1681295, 7414, 42
+12, 10, 32.143508, 75804672, 772, 2420, 3182976, 26599, 1299
+12, 10, 33.587287, 90660864, 784, 2420, 2908902, 40590, 7786
+12, 10, 25.739363, 101326848, 750, 2420, 2296481, 15216, 1180
+12, 10, 13.827426, 58028032, 780, 2420, 1440861, 10782, 416
+13, 10, 50.937077, 108945408, 818, 2620, 3583976, 30270, 2422
+13, 10, 37.447039, 86216704, 840, 2620, 2923728, 15898, 3928
+13, 10, 20.521833, 67043328, 844, 2620, 1622564, 3926, 166
+13, 10, 69.188095, 99930112, 798, 2620, 5464668, 67598, 9700
+13, 10, 30.851311, 104501248, 800, 2620, 2734840, 12735, 1405
+13, 10, 44.013298, 139419648, 838, 2620, 3168757, 10956, 506
+13, 10, 58.738188, 119738368, 804, 2620, 3819590, 22910, 1864
+13, 10, 19.642678, 71106560, 832, 2620, 1704326, 3699, 53
+14, 10, 154.301017, 193677312, 892, 2820, 7791437, 48039, 1209
+14, 10, 79.694805, 149069824, 892, 2820, 4872074, 27046, 6656
+14, 10, 80.007738, 162656256, 828, 2820, 4533828, 18481, 2531
+14, 10, 63.123666, 152117248, 892, 2820, 4495399, 16726, 1160
+14, 10, 164.029795, 262117376, 892, 2820, 7621989, 25196, 768
+14, 10, 44.278199, 99041280, 900, 2820, 3009652, 17743, 1079
+14, 10, 117.991945, 177004544, 904, 2820, 6416869, 24297, 883
+14, 10, 73.137325, 169551872, 892, 2820, 5203778, 28236, 4978
+15, 10, 169.761363, 341848064, 964, 3020, 7380437, 5755, 147
+15, 10, 536.876216, 403206144, 952, 3020, 13876783, 24288, 2258
+15, 10, 285.854488, 333946880, 930, 3020, 9555748, 25275, 5067
+15, 10, 307.746367, 309821440, 948, 3020, 9817285, 33868, 6268
+15, 10, 221.935436, 223130624, 926, 3020, 10918558, 52332, 6984
+15, 10, 316.997250, 327606272, 964, 3020, 10969011, 39363, 5845
+15, 10, 249.147212, 283322368, 964, 3020, 9188407, 13601, 569
+15, 10, 120.300939, 184369152, 952, 3020, 6534648, 7697, 463

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2testlazysabidi.csv

+2, 10, 0.015153, 126976, 94, 420, 914, 34, 0
+2, 10, 0.015932, 126976, 114, 420, 978, 32, 0
+2, 10, 0.015273, 126976, 94, 420, 884, 25, 0
+2, 10, 0.015641, 126976, 102, 420, 921, 25, 0
+2, 10, 0.015257, 126976, 96, 420, 926, 26, 0
+2, 10, 0.015593, 126976, 84, 420, 861, 13, 0
+2, 10, 0.015274, 126976, 104, 420, 881, 32, 0
+2, 10, 0.015945, 126976, 98, 420, 905, 31, 0
+3, 10, 0.018125, 126976, 78, 620, 1424, 26, 0
+3, 10, 0.018344, 126976, 162, 620, 1533, 37, 0
+3, 10, 0.018390, 126976, 90, 620, 1518, 39, 0
+3, 10, 0.018722, 126976, 116, 620, 1468, 24, 0
+3, 10, 0.018620, 126976, 164, 620, 1508, 49, 0
+3, 10, 0.018629, 126976, 120, 620, 1490, 25, 0
+3, 10, 0.018049, 126976, 126, 620, 1532, 45, 0
+3, 10, 0.018588, 126976, 128, 620, 1416, 31, 0
+4, 10, 0.021573, 126976, 154, 820, 2204, 75, 0
+4, 10, 0.022732, 126976, 116, 820, 2652, 54, 0
+4, 10, 0.022737, 126976, 134, 820, 2723, 49, 0
+4, 10, 0.021757, 126976, 182, 820, 2047, 17, 0
+4, 10, 0.021329, 126976, 122, 820, 2101, 70, 0
+4, 10, 0.022633, 126976, 154, 820, 2546, 66, 0
+4, 10, 0.021471, 126976, 190, 820, 2210, 98, 0
+4, 10, 0.022908, 126976, 102, 820, 2497, 32, 0
+5, 10, 0.026981, 126976, 100, 1020, 3617, 82, 0
+5, 10, 0.027189, 126976, 108, 1020, 3651, 85, 0
+5, 10, 0.027263, 126976, 108, 1020, 3787, 128, 0
+5, 10, 0.027637, 126976, 110, 1020, 3420, 66, 0
+5, 10, 0.027518, 126976, 92, 1020, 3535, 86, 0
+5, 10, 0.027194, 126976, 106, 1020, 3594, 79, 0
+5, 10, 0.033054, 126976, 108, 1020, 3500, 114, 0
+5, 10, 0.027060, 126976, 78, 1020, 3527, 119, 0
+6, 10, 0.036065, 126976, 190, 1220, 5168, 139, 0
+6, 10, 0.036333, 126976, 78, 1220, 5103, 133, 0
+6, 10, 0.039171, 126976, 82, 1220, 6227, 70, 0
+6, 10, 0.039683, 126976, 106, 1220, 5896, 149, 0
+6, 10, 0.037741, 126976, 78, 1220, 5045, 230, 0
+6, 10, 0.032631, 126976, 108, 1220, 4235, 45, 0
+6, 10, 0.037523, 126976, 108, 1220, 4629, 196, 0
+6, 10, 0.035415, 126976, 104, 1220, 5358, 106, 0
+7, 10, 0.043975, 126976, 108, 1420, 5510, 344, 93
+7, 10, 0.045452, 253952, 102, 1420, 5970, 341, 0
+7, 10, 0.046865, 126976, 104, 1420, 5163, 166, 0
+7, 10, 0.045746, 126976, 102, 1420, 5483, 165, 0
+7, 10, 0.044537, 126976, 96, 1420, 5518, 187, 0
+7, 10, 0.043267, 126976, 184, 1420, 5399, 223, 0
+7, 10, 0.050306, 126976, 92, 1420, 6240, 57, 0
+7, 10, 0.062839, 253952, 120, 1420, 7541, 157, 0
+10, 10, 0.095210, 380928, 228, 2020, 8782, 208, 4
+10, 10, 0.091251, 380928, 390, 2020, 8293, 531, 0
+10, 10, 0.098398, 380928, 204, 2020, 9384, 609, 4
+10, 10, 0.068821, 380928, 234, 2020, 8260, 445, 26
+10, 10, 0.084841, 380928, 232, 2020, 7711, 161, 0
+10, 10, 0.107192, 380928, 120, 2020, 8768, 483, 0
+10, 10, 0.087399, 380928, 122, 2020, 7542, 443, 4
+10, 10, 0.093655, 380928, 198, 2020, 6806, 373, 0
+12, 10, 0.158112, 380928, 448, 2420, 8094, 1338, 9
+12, 10, 0.156859, 380928, 470, 2420, 8051, 586, 0
+12, 10, 0.195868, 380928, 470, 2420, 8615, 850, 7
+12, 10, 0.063022, 380928, 462, 2420, 7932, 928, 175
+12, 10, 0.111878, 380928, 512, 2420, 8546, 383, 10
+12, 10, 0.185403, 380928, 370, 2420, 8402, 766, 0
+12, 10, 0.041753, 380928, 380, 2420, 6072, 936, 458
+12, 10, 0.187609, 380928, 360, 2420, 9260, 768, 26
+13, 10, 0.193498, 380928, 100, 2620, 8856, 1197, 36
+13, 10, 0.290318, 380928, 106, 2620, 9162, 1153, 0
+13, 10, 0.178090, 380928, 190, 2620, 9700, 395, 3
+13, 10, 0.076091, 380928, 92, 2620, 8635, 1246, 156
+13, 10, 0.205401, 380928, 108, 2620, 7832, 973, 38
+13, 10, 0.369606, 380928, 108, 2620, 9422, 286, 0
+13, 10, 0.221917, 380928, 98, 2620, 8218, 979, 3
+13, 10, 0.171302, 380928, 106, 2620, 8759, 1160, 5
+14, 10, 0.388694, 380928, 106, 2820, 9218, 417, 2
+14, 10, 0.584058, 380928, 108, 2820, 7069, 620, 0
+14, 10, 0.347272, 380928, 184, 2820, 8034, 982, 0
+14, 10, 0.335505, 380928, 164, 2820, 8270, 1037, 3
+14, 10, 0.338073, 380928, 110, 2820, 7682, 547, 79
+14, 10, 0.304502, 380928, 106, 2820, 8282, 499, 0
+14, 10, 0.524231, 634880, 164, 2820, 9094, 1274, 0
+14, 10, 0.278381, 380928, 108, 2820, 8787, 1034, 146
+15, 10, 0.743366, 634880, 228, 3020, 7555, 763, 1
+15, 10, 0.244092, 380928, 108, 3020, 7658, 791, 51
+15, 10, 0.736027, 634880, 134, 3020, 7642, 1302, 0
+15, 10, 0.430673, 634880, 108, 3020, 11043, 1800, 244
+15, 10, 0.342010, 380928, 108, 3020, 7776, 1092, 29
+15, 10, 0.543283, 380928, 106, 3020, 8002, 593, 0
+15, 10, 0.550388, 380928, 102, 3020, 8070, 709, 8
+15, 10, 0.571945, 634880, 196, 3020, 8185, 1001, 18

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2testnonsaeager.csv

+2, 10, 0.014234, 0, 90, 0, 4827, 0, 0
+2, 10, 0.013190, 0, 90, 0, 4827, 0, 0
+2, 10, 0.013833, 0, 102, 0, 4827, 0, 0
+2, 10, 0.013825, 0, 102, 0, 4827, 0, 0
+2, 10, 0.013418, 0, 96, 0, 4827, 0, 0
+2, 10, 0.013399, 0, 98, 0, 4827, 0, 0
+2, 10, 0.014151, 0, 102, 0, 4827, 0, 0
+2, 10, 0.013336, 0, 112, 0, 4827, 0, 0
+3, 10, 0.017973, 0, 108, 0, 10709, 0, 0
+3, 10, 0.016909, 0, 106, 0, 10269, 0, 0
+3, 10, 0.018338, 0, 120, 0, 10401, 0, 0
+3, 10, 0.016922, 0, 90, 0, 10489, 0, 0
+3, 10, 0.016875, 0, 106, 0, 10445, 0, 0
+3, 10, 0.017307, 0, 146, 0, 10665, 0, 0
+3, 10, 0.017262, 0, 108, 0, 10357, 0, 0
+3, 10, 0.017963, 0, 142, 0, 10577, 0, 0
+4, 10, 0.024042, 0, 92, 0, 19275, 0, 0
+4, 10, 0.025313, 0, 172, 0, 20155, 0, 0
+4, 10, 0.022162, 0, 106, 0, 19803, 0, 0
+4, 10, 0.022648, 0, 146, 0, 18043, 0, 0
+4, 10, 0.025234, 0, 178, 0, 19935, 0, 0
+4, 10, 0.025371, 0, 76, 0, 19979, 0, 0
+4, 10, 0.023787, 0, 118, 0, 18263, 0, 0
+4, 10, 0.025977, 0, 130, 0, 21035, 0, 0
+5, 10, 0.038005, 126976, 200, 0, 33429, 0, 0
+5, 10, 0.035569, 126976, 158, 0, 32989, 0, 0
+5, 10, 0.034287, 126976, 214, 0, 33957, 0, 0
+5, 10, 0.037279, 126976, 210, 0, 34177, 0, 0
+5, 10, 0.047827, 126976, 96, 0, 36685, 0, 0
+5, 10, 0.036358, 126976, 84, 0, 34661, 0, 0
+5, 10, 0.039498, 126976, 132, 0, 36861, 0, 0
+5, 10, 0.037644, 126976, 172, 0, 33649, 0, 0
+6, 10, 0.055492, 126976, 144, 0, 56559, 0, 0
+6, 10, 0.053940, 126976, 226, 0, 52027, 0, 0
+6, 10, 0.059517, 126976, 214, 0, 56955, 0, 0
+6, 10, 0.064521, 126976, 242, 0, 64787, 0, 0
+6, 10, 0.057853, 126976, 192, 0, 59287, 0, 0
+6, 10, 0.061417, 126976, 220, 0, 58979, 0, 0
+6, 10, 0.062005, 126976, 214, 0, 63819, 0, 0
+6, 10, 0.060471, 126976, 214, 0, 59551, 0, 0
+7, 10, 0.092186, 126976, 92, 0, 95089, 0, 0
+7, 10, 0.091320, 126976, 262, 0, 93681, 0, 0
+7, 10, 0.094648, 126976, 196, 0, 98257, 0, 0
+7, 10, 0.094926, 126976, 214, 0, 91085, 0, 0
+7, 10, 0.110806, 126976, 214, 0, 105033, 0, 0
+7, 10, 0.087277, 126976, 256, 0, 97641, 0, 0
+7, 10, 0.074256, 126976, 180, 0, 79645, 0, 0
+7, 10, 0.119645, 126976, 224, 0, 110357, 0, 0
+10, 10, 0.366548, 126976, 108, 0, 339599, 0, 0
+10, 10, 0.330547, 126976, 108, 0, 335243, 0, 0
+10, 10, 0.441907, 126976, 108, 0, 396667, 0, 0
+10, 10, 0.513589, 126976, 108, 0, 457123, 0, 0
+10, 10, 0.359088, 126976, 108, 0, 431955, 0, 0
+10, 10, 0.347832, 126976, 108, 0, 319095, 0, 0
+10, 10, 0.381262, 126976, 108, 0, 371807, 0, 0
+10, 10, 0.439691, 126976, 108, 0, 397503, 0, 0
+12, 10, 0.763130, 253952, 342, 0, 1083347, 0, 0
+12, 10, 1.022675, 253952, 372, 0, 884819, 0, 0
+12, 10, 0.560856, 126976, 108, 0, 549847, 0, 0
+12, 10, 1.508336, 253952, 364, 0, 1229603, 0, 0
+12, 10, 1.192925, 253952, 244, 0, 1116611, 0, 0
+12, 10, 0.896967, 253952, 346, 0, 788811, 0, 0
+12, 10, 1.032066, 253952, 398, 0, 891683, 0, 0
+12, 10, 1.270484, 253952, 226, 0, 1127919, 0, 0
+13, 10, 1.632584, 253952, 422, 0, 1623169, 0, 0
+13, 10, 2.055085, 380928, 392, 0, 1783065, 0, 0
+13, 10, 1.700256, 253952, 426, 0, 1490817, 0, 0
+13, 10, 2.258716, 380928, 444, 0, 1759789, 0, 0
+13, 10, 1.922434, 253952, 440, 0, 1373601, 0, 0
+13, 10, 2.487363, 380928, 428, 0, 1974685, 0, 0
+13, 10, 1.501979, 253952, 426, 0, 1545817, 0, 0
+13, 10, 1.438387, 253952, 282, 0, 1109117, 0, 0
+14, 10, 3.701446, 380928, 472, 0, 3000179, 0, 0
+14, 10, 3.598876, 380928, 444, 0, 3163331, 0, 0
+14, 10, 2.760275, 380928, 444, 0, 2450355, 0, 0
+14, 10, 3.098720, 380928, 454, 0, 2350519, 0, 0
+14, 10, 2.376413, 380928, 472, 0, 2403231, 0, 0
+14, 10, 2.210533, 253952, 420, 0, 1592267, 0, 0
+14, 10, 2.789968, 380928, 472, 0, 2356151, 0, 0
+14, 10, 2.766881, 380928, 450, 0, 1860535, 0, 0
+15, 10, 5.033478, 380928, 486, 0, 3437041, 0, 0
+15, 10, 4.595912, 380928, 500, 0, 4149533, 0, 0
+15, 10, 5.813292, 380928, 500, 0, 4987117, 0, 0
+15, 10, 3.487085, 380928, 454, 0, 2884929, 0, 0
+15, 10, 4.566618, 380928, 458, 0, 3323609, 0, 0
+15, 10, 4.213161, 380928, 500, 0, 2997481, 0, 0
+15, 10, 5.030834, 380928, 500, 0, 4041205, 0, 0
+15, 10, 3.760436, 380928, 484, 0, 3007469, 0, 0

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2tests.sh

+
+BIN=../../_product
+
+touch runas2testlazysabidi.csv
+touch runas2testeagersatotalorder.csv
+touch runas2testnonsaeager.csv
+
+for sht in 2 3 4 5 6 7 10 12 13 14 15; do
+    for samp in 1 2 3 4 5 6 7 8; do
+    echo "sheet depth=$sht/20; same number=$samp"
+    args="--Random.self_init --stats-test $sht"
+    $BIN/runas2.native --adapton-module LazySABidi $args --stats-out runas2testlazysabidi.csv
+    $BIN/runas2.native --adapton-module NonSAEager $args --stats-out runas2testnonsaeager.csv
+    $BIN/runas2.native --adapton-module EagerSATotalOrder $args --stats-out runas2testeagersatotalorder.csv
+    done   
+done

Benchmarks/BenchmarkAs2/runas2test-results-1156-2013.11.14/runas2tests.sh~

+
+BIN=../../_product
+
+touch runas2testlazysabidi.csv
+touch runas2testeagersatotalorder.csv
+touch runas2testnonsaeager.csv
+
+for sht in 2 3 4 5 6 7 10 12 13 ; do
+#for sht in 2 3 4 5 6 7 10 12 15 17 20 ; do
+#for sht in 17 20 22 25 ; do
+    for samp in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32; do
+    echo "sheet depth=$sht/20; same number=$samp"
+    args="--Random.self_init --stats-test $sht"
+    $BIN/runas2.native --adapton-module LazySABidi $args --stats-out runas2testlazysabidi.csv
+    $BIN/runas2.native --adapton-module NonSAEager $args --stats-out runas2testnonsaeager.csv
+    $BIN/runas2.native --adapton-module EagerSATotalOrder $args --stats-out runas2testeagersatotalorder.csv
+    done   
+done

Benchmarks/BenchmarkAs2/runas2test-results-1320-2013.11.14/TITLE

+Vary number of changes; number of sheets is 15

Benchmarks/BenchmarkAs2/runas2test-results-1320-2013.11.14/runas2testeagersatotalorder.csv

+15, 2, 13.347360, 65265664, 964, 3004, 1476031, 970, 18
+15, 2, 8.579499, 37584896, 940, 3004, 974207, 363, 3
+15, 2, 8.936224, 47362048, 964, 3004, 1131951, 90, 2
+15, 2, 13.175599, 69455872, 940, 3004, 1541901, 940, 4
+15, 2, 6.791586, 46981120, 952, 3004, 889528, 68, 0
+15, 2, 16.719869, 51044352, 924, 3004, 1450675, 1684, 156
+15, 2, 4.571374, 31744000, 940, 3004, 652911, 12, 0
+15, 2, 10.717379, 63868928, 958, 3004, 1302753, 760, 4
+15, 5, 30.308732, 136372224, 962, 3010, 2857778, 10155, 2715
+15, 5, 56.477271, 128245760, 952, 3010, 4113065, 7882, 530
+15, 5, 22.544383, 69455872, 964, 3010, 1980631, 4220, 32
+15, 5, 52.828797, 175480832, 958, 3010, 4108652, 12288, 4984
+15, 5, 107.397352, 215605248, 942, 3010, 5090944, 2931, 67
+15, 5, 61.691896, 147165184, 952, 3010, 3677254, 13569, 6785
+15, 5, 38.744301, 126341120, 964, 3010, 3025682, 9705, 135
+15, 5, 90.860910, 156815360, 946, 3010, 4828832, 5515, 675
+15, 7, 153.037841, 251832320, 930, 3014, 7160224, 23516, 5836
+15, 7, 176.130723, 258015232, 958, 3014, 7636936, 24700, 7494
+15, 7, 118.679995, 176027648, 952, 3014, 6458397, 32896, 8058
+15, 7, 191.010854, 258269184, 958, 3014, 7847508, 32659, 2979
+15, 7, 79.104854, 153894912, 958, 3014, 4831212, 11914, 666
+15, 7, 62.776834, 185131008, 938, 3014, 4309512, 15566, 4258
+15, 7, 78.120174, 185131008, 958, 3014, 4599598, 10133, 687
+15, 7, 130.971105, 181067776, 958, 3014, 6741064, 13915, 1377
+15, 10, 194.520657, 248911872, 926, 3020, 9419053, 30628, 3104
+15, 10, 204.320189, 268665856, 958, 3020, 9319640, 36467, 12821
+15, 10, 490.166466, 423759360, 952, 3020, 17542887, 66280, 14940
+15, 10, 112.063119, 247095296, 934, 3020, 5695066, 3775, 27
+15, 10, 277.649419, 325178368, 942, 3020, 12227951, 24307, 717
+15, 10, 572.205485, 370094592, 948, 3020, 20976310, 72400, 10448
+15, 10, 33.645221, 146784256, 958, 3020, 3167731, 498, 0
+15, 10, 287.773066, 273496064, 958, 3020, 11105290, 60208, 20506
+15, 15, 1013.424941, 594147840, 952, 3030, 25311792, 39407, 3913
+15, 15, 196.222329, 284289024, 958, 3030, 8515639, 80157, 9603
+15, 15, 328.088013, 283985920, 932, 3030, 9967233, 52254, 2608
+15, 15, 1029.843293, 479710208, 924, 3030, 28264084, 111879, 15901
+15, 15, 251.250332, 236683264, 952, 3030, 11058994, 57641, 4495
+15, 15, 264.871863, 294154240, 940, 3030, 10268073, 30053, 2283
+15, 15, 502.207278, 380325888, 914, 3030, 16532198, 45641, 7955
+15, 15, 808.717250, 531339776, 958, 3030, 24191473, 131361, 10669
+15, 17, 1468.376630, 590227456, 946, 3034, 29493570, 106152, 29786
+15, 17, 599.767169, 408674304, 964, 3034, 16458769, 74759, 11327
+15, 17, 565.677462, 411729920, 964, 3034, 17356726, 101785, 15453
+15, 17, 1447.917294, 625876480, 954, 3034, 38789268, 151020, 35750
+15, 17, 494.136313, 371902976, 948, 3034, 14649295, 42102, 8984
+15, 17, 690.166814, 479131136, 948, 3034, 18910838, 43187, 3769
+15, 17, 511.448587, 371861504, 958, 3034, 15891246, 92842, 19908
+15, 17, 1207.660549, 645034496, 952, 3034, 27196718, 75055, 7185
+15, 20, 1284.648780, 620844032, 966, 3040, 31680178, 93511, 8945
+15, 20, 1404.797245, 624714240, 946, 3040, 35843781, 127766, 17724
+15, 20, 929.786754, 509845504, 952, 3040, 31192075, 111855, 10161
+15, 20, 874.729285, 529436160, 954, 3040, 26381329, 102212, 12506
+15, 20, 342.681995, 309638144, 904, 3040, 16743413, 116522, 28320
+15, 20, 1044.394593, 569554432, 950, 3040, 21947896, 40011, 4337
+15, 20, 1852.106581, 752218112, 964, 3040, 41222909, 121861, 12773
+15, 20, 1160.325333, 551807488, 954, 3040, 42119669, 249318, 62848
+15, 23, 2626.163536, 982441984, 946, 3046, 50476035, 171250, 19548
+15, 23, 1598.392356, 642491392, 958, 3046, 54377383, 206912, 30060
+15, 23, 2240.120266, 822093312, 946, 3046, 51072782, 153383, 20003
+15, 23, 2377.602142, 924039680, 958, 3046, 42134120, 160277, 38095
+15, 23, 1447.134735, 622838272, 958, 3046, 38904160, 168353, 28919
+15, 23, 570.207592, 433978368, 958, 3046, 21360195, 119381, 10601
+15, 23, 716.053340, 431988736, 964, 3046, 23815319, 227702, 38668
+15, 23, 644.795555, 443204096, 946, 3046, 20074999, 88066, 19132
+15, 25, 644.059347, 415204352, 946, 3050, 18585393, 210501, 9925
+15, 25, 615.025672, 431698944, 958, 3050, 17480372, 90292, 3748
+15, 25, 1541.656739, 645435904, 942, 3050, 45959242, 146940, 14066
+15, 25, 771.715002, 460526592, 952, 3050, 26504788, 261011, 37559
+15, 25, 1376.979972, 628547584, 958, 3050, 39895541, 102645, 8775
+15, 25, 1050.549904, 523543040, 954, 3050, 33971139, 139532, 27830
+15, 25, 1605.629575, 697549824, 920, 3050, 36909391, 171309, 10851
+15, 25, 3684.460468, 1130861568, 952, 3050, 68653693, 192466, 9848
+15, 27, 1561.263696, 634121728, 964, 3054, 33243455, 140742, 19886
+15, 27, 3100.053627, 1013382144, 942, 3054, 57191940, 239197, 61509
+15, 27, 3016.988871, 946362880, 918, 3054, 77361567, 338053, 92715
+15, 27, 752.216637, 428183552, 948, 3054, 32107661, 219390, 26940
+15, 27, 2166.254431, 835996160, 958, 3054, 34173842, 85933, 6471
+15, 27, 2182.448035, 851780608, 942, 3054, 54924653, 264649, 61175
+15, 27, 2501.049887, 828016640, 932, 3054, 61941016, 386496, 121824
+15, 27, 1268.391269, 600303616, 948, 3054, 35231684, 144767, 21957
+15, 30, 2978.435576, 975885312, 964, 3060, 61818895, 265810, 51076

Benchmarks/BenchmarkAs2/runas2test-results-1320-2013.11.14/runas2testlazysabidi.csv

+15, 2, 0.166721, 380928, 124, 3004, 4997, 445, 0
+15, 2, 0.260413, 380928, 104, 3004, 5233, 8, 0
+15, 2, 0.247752, 380928, 106, 3004, 5027, 460, 0
+15, 2, 0.301685, 380928, 106, 3004, 5276, 196, 0
+15, 2, 0.218111, 380928, 108, 3004, 6888, 574, 0
+15, 2, 0.207101, 380928, 108, 3004, 4337, 0, 0
+15, 2, 0.216293, 380928, 108, 3004, 5789, 74, 0
+15, 2, 0.222889, 380928, 108, 3004, 5681, 557, 0
+15, 5, 0.390834, 380928, 102, 3010, 6391, 579, 0
+15, 5, 0.201315, 380928, 108, 3010, 6584, 240, 30
+15, 5, 0.499141, 634880, 134, 3010, 6450, 1243, 40
+15, 5, 0.342103, 380928, 100, 3010, 6852, 452, 2
+15, 5, 0.098623, 380928, 106, 3010, 6926, 403, 92
+15, 5, 0.639221, 634880, 144, 3010, 7224, 845, 0
+15, 5, 0.363472, 380928, 106, 3010, 6327, 209, 0
+15, 5, 0.368733, 380928, 108, 3010, 6376, 487, 0
+15, 7, 0.496657, 634880, 124, 3014, 8219, 1606, 0
+15, 7, 0.040357, 380928, 122, 3014, 4278, 615, 304
+15, 7, 0.455901, 380928, 204, 3014, 7094, 549, 6
+15, 7, 0.414354, 380928, 114, 3014, 7456, 754, 5
+15, 7, 0.634799, 634880, 154, 3014, 7410, 1051, 0
+15, 7, 0.228447, 380928, 108, 3014, 7141, 143, 5
+15, 7, 0.464656, 380928, 106, 3014, 7393, 289, 0
+15, 7, 0.434422, 380928, 160, 3014, 7963, 330, 0
+15, 10, 0.620390, 634880, 124, 3020, 7929, 1277, 8
+15, 10, 0.392923, 634880, 124, 3020, 10419, 1041, 0
+15, 10, 0.800972, 634880, 238, 3020, 8704, 1640, 1
+15, 10, 0.691557, 380928, 108, 3020, 8339, 609, 0
+15, 10, 0.458653, 634880, 126, 3020, 8185, 1130, 2
+15, 10, 0.620096, 634880, 108, 3020, 8469, 669, 10
+15, 10, 0.569901, 634880, 160, 3020, 7131, 1039, 1
+15, 10, 0.264978, 634880, 154, 3020, 9307, 1876, 189
+15, 15, 1.112926, 634880, 150, 3030, 9456, 1064, 22
+15, 15, 0.839425, 634880, 108, 3030, 8671, 1468, 15
+15, 15, 1.023201, 634880, 108, 3030, 11583, 1442, 2
+15, 15, 0.582472, 761856, 124, 3030, 9769, 1235, 6
+15, 15, 0.626558, 634880, 162, 3030, 9776, 1206, 15
+15, 15, 0.964855, 634880, 174, 3030, 9775, 2585, 39
+15, 15, 0.447379, 634880, 162, 3030, 11986, 2629, 113
+15, 15, 0.754257, 761856, 214, 3030, 10192, 3178, 30
+15, 17, 0.421232, 634880, 110, 3034, 11839, 2646, 143
+15, 17, 0.693469, 634880, 124, 3034, 11180, 1889, 4
+15, 17, 0.922496, 634880, 124, 3034, 10695, 1690, 12
+15, 17, 0.476516, 761856, 110, 3034, 11399, 1971, 177
+15, 17, 0.736674, 634880, 224, 3034, 10771, 1604, 71
+15, 17, 0.564887, 634880, 234, 3034, 10618, 1024, 0
+15, 17, 0.843358, 634880, 134, 3034, 9876, 1335, 334
+15, 17, 0.761704, 634880, 120, 3034, 10600, 1348, 15
+15, 20, 0.977513, 634880, 124, 3040, 9864, 606, 8
+15, 20, 1.059084, 634880, 154, 3040, 13146, 3252, 6
+15, 20, 0.397208, 380928, 108, 3040, 11118, 1142, 230
+15, 20, 1.119338, 761856, 124, 3040, 10037, 1794, 4
+15, 20, 0.436312, 634880, 124, 3040, 11424, 2832, 138
+15, 20, 0.976623, 634880, 124, 3040, 12810, 2686, 40
+15, 20, 0.841410, 634880, 238, 3040, 11312, 2778, 71
+15, 20, 0.440619, 761856, 200, 3040, 12314, 4058, 301
+15, 23, 1.228843, 634880, 106, 3046, 10786, 1095, 24
+15, 23, 0.847593, 634880, 146, 3046, 11106, 2646, 20
+15, 23, 0.994031, 634880, 228, 3046, 12235, 3715, 93
+15, 23, 1.292906, 634880, 124, 3046, 11560, 3553, 47
+15, 23, 1.256587, 634880, 116, 3046, 11878, 2161, 9
+15, 23, 0.656361, 634880, 124, 3046, 12896, 2880, 42
+15, 23, 1.018296, 634880, 124, 3046, 12676, 3527, 17
+15, 23, 1.540230, 634880, 196, 3046, 11175, 2198, 26
+15, 25, 0.715011, 761856, 108, 3050, 14827, 2892, 3
+15, 25, 0.084053, 380928, 108, 3050, 10749, 3575, 1872
+15, 25, 1.036259, 634880, 208, 3050, 12214, 3182, 61
+15, 25, 0.663656, 634880, 104, 3050, 12571, 2351, 4
+15, 25, 0.849305, 761856, 194, 3050, 11437, 1577, 46
+15, 25, 0.976260, 761856, 116, 3050, 13976, 2865, 56
+15, 25, 1.598831, 634880, 174, 3050, 12009, 2578, 176
+15, 25, 0.789292, 634880, 156, 3050, 11693, 2658, 65
+15, 27, 0.740477, 634880, 110, 3054, 13298, 3171, 265
+15, 27, 1.049382, 634880, 124, 3054, 14714, 3986, 41
+15, 27, 0.076322, 380928, 106, 3054, 12357, 3968, 2157
+15, 27, 0.750794, 761856, 150, 3054, 14005, 4157, 315
+15, 27, 0.767693, 634880, 204, 3054, 13200, 2570, 18
+15, 27, 0.769127, 634880, 108, 3054, 11287, 1001, 6
+15, 27, 1.040524, 634880, 184, 3054, 12855, 2919, 29
+15, 27, 0.106141, 380928, 102, 3054, 9729, 3104, 1184
+15, 30, 1.669169, 634880, 124, 3060, 12770, 3036, 69
+15, 30, 0.113770, 634880, 154, 3060, 10696, 4692, 2493

Benchmarks/BenchmarkAs2/runas2test-results-1320-2013.11.14/runas2testnonsaeager.csv

+15, 2, 1.400347, 253952, 396, 0, 1199041, 0, 0
+15, 2, 1.289421, 253952, 356, 0, 829621, 0, 0
+15, 2, 1.477868, 253952, 284, 0, 1054369, 0, 0
+15, 2, 1.648564, 253952, 438, 0, 939613, 0, 0
+15, 2, 2.035669, 253952, 480, 0, 1220665, 0, 0
+15, 2, 1.749711, 253952, 444, 0, 1281265, 0, 0
+15, 2, 1.125064, 253952, 454, 0, 839821, 0, 0
+15, 2, 0.986741, 253952, 482, 0, 819961, 0, 0
+15, 5, 2.109256, 380928, 468, 0, 1566325, 0, 0
+15, 5, 1.724404, 380928, 472, 0, 1881637, 0, 0
+15, 5, 1.605708, 253952, 400, 0, 1362157, 0, 0
+15, 5, 1.688882, 380928, 400, 0, 1563373, 0, 0
+15, 5, 2.031925, 380928, 482, 0, 1526485, 0, 0
+15, 5, 1.600676, 253952, 382, 0, 1192357, 0, 0
+15, 5, 2.615245, 380928, 500, 0, 1835557, 0, 0
+15, 5, 2.554147, 380928, 476, 0, 1726981, 0, 0
+15, 7, 2.069492, 380928, 458, 0, 2091773, 0, 0
+15, 7, 3.474802, 380928, 454, 0, 2728509, 0, 0
+15, 7, 2.785770, 380928, 500, 0, 2380445, 0, 0
+15, 7, 4.181038, 380928, 482, 0, 2979133, 0, 0
+15, 7, 3.979767, 380928, 472, 0, 3101181, 0, 0
+15, 7, 2.555713, 380928, 492, 0, 1794845, 0, 0
+15, 7, 4.470805, 380928, 420, 0, 3706909, 0, 0
+15, 7, 2.264841, 380928, 500, 0, 1812413, 0, 0
+15, 10, 3.222189, 380928, 478, 0, 3179597, 0, 0
+15, 10, 2.885900, 380928, 444, 0, 2598489, 0, 0
+15, 10, 4.780633, 380928, 486, 0, 3886589, 0, 0
+15, 10, 5.709041, 380928, 472, 0, 4619189, 0, 0
+15, 10, 4.599839, 380928, 500, 0, 3892353, 0, 0
+15, 10, 4.959689, 380928, 500, 0, 3466917, 0, 0
+15, 10, 4.853572, 380928, 472, 0, 3800657, 0, 0
+15, 10, 7.251029, 380928, 500, 0, 6120953, 0, 0
+15, 15, 7.747761, 380928, 494, 0, 6507741, 0, 0
+15, 15, 9.585274, 380928, 482, 0, 6819229, 0, 0
+15, 15, 4.697308, 380928, 492, 0, 6046045, 0, 0
+15, 15, 6.280362, 380928, 500, 0, 4991773, 0, 0
+15, 15, 7.968060, 380928, 494, 0, 5890909, 0, 0
+15, 15, 9.393323, 380928, 492, 0, 6989021, 0, 0
+15, 15, 7.514189, 380928, 482, 0, 5659037, 0, 0
+15, 15, 9.545757, 380928, 500, 0, 5786653, 0, 0
+15, 17, 10.690588, 380928, 500, 0, 6998581, 0, 0
+15, 17, 3.150357, 380928, 482, 0, 2364229, 0, 0
+15, 17, 9.427497, 380928, 478, 0, 6610789, 0, 0
+15, 17, 5.218270, 380928, 482, 0, 4687381, 0, 0
+15, 17, 7.913092, 380928, 482, 0, 5603653, 0, 0
+15, 17, 7.829601, 380928, 454, 0, 6161725, 0, 0
+15, 17, 6.748550, 380928, 494, 0, 5075317, 0, 0
+15, 17, 8.755053, 380928, 476, 0, 7209181, 0, 0
+15, 20, 15.431755, 380928, 500, 0, 8966833, 0, 0
+15, 20, 8.318148, 380928, 482, 0, 5677057, 0, 0
+15, 20, 10.037118, 380928, 486, 0, 7975045, 0, 0
+15, 20, 8.058064, 380928, 500, 0, 6446749, 0, 0
+15, 20, 12.774820, 380928, 494, 0, 9009421, 0, 0
+15, 20, 8.413663, 380928, 500, 0, 6550489, 0, 0
+15, 20, 8.460283, 380928, 494, 0, 8962465, 0, 0