[Ocaml-lib-devel] [PATCH] updated enum: now concat uses t.fast

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

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/ocaml-extlib/extlib-dev/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 exception-based implementation.
+		 * A tail-recursive 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 exception-based
+		 *   implementation.
+		 * A tail-recursive 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 5-10% 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 ()))
+