Here's an updated version of my patch to enum.ml, including using fast
in Enum.concat. A try block on every call to next() was quite
expensive. I wasn't able to think of anything useful to do with
t.count (as opposed to tn.count) in concat, though.
If it's more convenient, I've also posted my modified enum.ml at:
http://recalcitrant.org/~apost/enum.ml
 /usr/local/src/ocamlextlib/extlibdev/enum.ml Tue Jun 3 19:21:46 2003
+++ ./enum.ml Sun Jun 8 19:20:07 2003
@@ 24,7 +24,7 @@
mutable fast : bool;
}
(* raised by 'next' functions, should NOT goes outside the API *)
+(* raised by 'next' functions, should NOT go outside the API *)
exception No_more_elements
let _dummy () = assert false
@@ 50,7 +50,7 @@
f (n  1  !count));
clone = (fun () > init !count f);
fast = true;
 }
+ }
let force t =
let rec clone enum count =
@@ 158,90 +158,153 @@
t.clone()
let iter f t =
 let rec loop () =
 f (t.next());
 loop();
 in
 try
 loop();
 with
 No_more_elements > ()
+ if t.fast then
+ (* 10% faster than the exceptionbased implementation.
+ * A tailrecursive approach was slower than the for loop.
+ * Unfortunately, "for _ =" is not allowed.
+ *)
+ for idx = 1 to t.count () do
+ f (t.next ())
+ done
+ else
+ let rec loop () =
+ f (t.next());
+ loop();
+ in
+ try
+ loop();
+ with
+ No_more_elements > ()
let iteri f t =
 let rec loop idx =
 f idx (t.next());
 loop (idx+1);
 in
 try
 loop 0;
 with
 No_more_elements > ()
+ if t.fast then
+ for idx = 0 to (t.count ())  1 do
+ f idx (t.next ())
+ done
+ else
+ let rec loop idx =
+ f idx (t.next());
+ loop (idx+1);
+ in
+ try
+ loop 0;
+ with
+ No_more_elements > ()
let iter2 f t u =
 let rec loop () =
 f (t.next()) (u.next());
 loop ()
 in
 try
 loop ()
 with
 No_more_elements > ()
+ if t.fast then
+ for idx = 1 to min (t.count ()) (u.count ()) do
+ f (t.next ()) (u.next ())
+ done
+ else
+ let rec loop () =
+ f (t.next()) (u.next());
+ loop ()
+ in
+ try
+ loop ()
+ with
+ No_more_elements > ()
let iter2i f t u =
 let rec loop idx =
 f idx (t.next()) (u.next());
 loop (idx + 1)
 in
 try
 loop 0
 with
 No_more_elements > ()
+ if t.fast then
+ for idx = 0 to (min (t.count ()) (u.count ()))  1 do
+ f idx (t.next ()) (u.next ())
+ done
+ else
+ let rec loop idx =
+ f idx (t.next()) (u.next());
+ loop (idx + 1)
+ in
+ try
+ loop 0
+ with
+ No_more_elements > ()
let fold f init t =
 let acc = ref init in
 let rec loop() =
 acc := f (t.next()) !acc;
 loop()
 in
 try
 loop()
 with
 No_more_elements > !acc
+ if t.fast then begin
+ (* Runs in 61% of the time required by the exceptionbased
+ * implementation.
+ * A tailrecursive approach was 5% slower than the for loop.
+ *)
+ let acc = ref init in
+ for idx = 1 to (t.count ()) do
+ acc := f (t.next ()) !acc
+ done;
+ !acc
+ end
+ else
+ let acc = ref init in
+ let rec loop() =
+ acc := f (t.next()) !acc;
+ loop()
+ in
+ try
+ loop()
+ with
+ No_more_elements > !acc
let foldi f init t =
 let acc = ref init in
 let rec loop idx =
 acc := f idx (t.next()) !acc;
 loop (idx + 1)
 in
 try
 loop 0
 with
 No_more_elements > !acc
+ if t.fast then begin
+ let acc = ref init in
+ for idx = 0 to (t.count ())  1 do
+ acc := f idx (t.next ()) !acc
+ done;
+ !acc
+ end
+ else
+ let acc = ref init in
+ let rec loop idx =
+ acc := f idx (t.next()) !acc;
+ loop (idx + 1)
+ in
+ try
+ loop 0
+ with
+ No_more_elements > !acc
let fold2 f init t u =
 let acc = ref init in
 let rec loop() =
 acc := f (t.next()) (u.next()) !acc;
 loop()
 in
 try
 loop()
 with
 No_more_elements > !acc
+ if t.fast then begin
+ let acc = ref init in
+ for idx = 0 to (min (t.count ()) (u.count ()))  1 do
+ acc := f (t.next ()) (u.next ()) !acc
+ done;
+ !acc
+ end
+ else
+ let acc = ref init in
+ let rec loop() =
+ acc := f (t.next()) (u.next()) !acc;
+ loop()
+ in
+ try
+ loop()
+ with
+ No_more_elements > !acc
let fold2i f init t u =
 let acc = ref init in
 let rec loop idx =
 acc := f idx (t.next()) (u.next()) !acc;
 loop (idx + 1)
 in
 try
 loop 0
 with
 No_more_elements > !acc
+ if t.fast then begin
+ let acc = ref init in
+ for idx = 0 to (min (t.count ()) (u.count ()))  1 do
+ acc := f idx (t.next ()) (u.next ()) !acc
+ done;
+ !acc
+ end
+ else
+ let acc = ref init in
+ let rec loop idx =
+ acc := f idx (t.next()) (u.next()) !acc;
+ loop (idx + 1)
+ in
+ try
+ loop 0
+ with
+ No_more_elements > !acc
let find f t =
+ (* Using count is slower on long enums, and only 510% faster on very
+ * short ones, so don't bother.
+ *)
let rec loop () =
let x = t.next() in
if f x then x else loop()
@@ 293,40 +356,73 @@
from2 next (fun () > filter f (t.clone()))
let rec filter_map f t =
 let rec next () =
 match f (t.next()) with
  None > next()
  Some x > x
 in
+ let rec next () =
+ match f (t.next()) with
+  None > next()
+  Some x > x
+ in
from2 next (fun () > filter_map f (t.clone()))
+(*
+ * Note that e.next can change, but only from false to true.
+ *
+ * TODO: given that ta.count is called O(N) times, perhaps its result should be
+ * cached locally instead. This could be significant in the case where
+ * ta is a deeply nested append.
+ *)
let rec append ta tb =
 let append_next = ref _dummy in
 append_next := (fun () >
 try
 ta.next()
 with
 No_more_elements >
 append_next := tb.next;
 !append_next ());
 {
 count = (fun () > ta.count() + tb.count());
 next = (fun () > !append_next ());
 clone = (fun () > append (ta.clone()) (tb.clone()));
+ let e = {
+ count = _dummy;
+ next = _dummy;
+ clone = _dummy;
fast = ta.fast && tb.fast;
}
+ and append_count = ref (fun () > (ta.count ()) + (tb.count ()))
+ and append_clone = ref (fun () > append (ta.clone ()) (tb.clone ()))
+ and append_next = ref _dummy in
+ let ta_done () =
+ append_count := tb.count;
+ append_clone := tb.clone;
+ append_next := tb.next;
+ e.fast < tb.fast;
+ !append_next ()
+ in
+ append_next :=
+ if ta.fast then
+ (fun () >
+ match ta.count () with
+  0 > ta_done ()
+  _ > ta.next ())
+ else
+ (fun () >
+ try
+ ta.next()
+ with
+ No_more_elements > ta_done ());
+ e.count < (fun () > !append_count ());
+ e.next < (fun () > !append_next ());
+ e.clone < (fun () > !append_clone ());
+ e
let rec concat t =
let concat_ref = ref _dummy in
 let rec concat_next() =
 let tn = t.next() in
 concat_ref := (fun () >
 try
 tn.next()
 with
 No_more_elements >
 concat_next());
+ let rec concat_next () =
+ let tn = t.next () in
+ concat_ref :=
+ if tn.fast then
+ (fun () >
+ match tn.count () with
+  0 > concat_next ()
+  _ > tn.next ())
+ else
+ (fun () >
+ try
+ tn.next ()
+ with
+ No_more_elements >
+ concat_next ());
!concat_ref ()
in
concat_ref := concat_next;
 from2 (fun () > !concat_ref ()) (fun () > concat (t.clone()))
\ No newline at end of file
+ from2 (fun () > !concat_ref ()) (fun () > concat (t.clone ()))
+
