[m-rev.] for review: improve stack usage of list.series/3 and `..`

[Julien Fischer]

For review by anyone.

Estimated hours taken: 1.5
Branches: main, release

Improve the stack usage of list.series/3 and `..`.

library/list.m:
	Improve the stack consumption of list.series/3 by
	generating the series in reverse and then reversing
	it.

	Reimplement `..` so that it doesn't call list.series/3 at all
	but just does the obvious thing and generates the list
	of integers in reverse to begin with, ie. from High to Low.
	On my laptop this ends up being about 4.5 times faster than
	the version that calls (the old) list.series/3 (as well
	as obviously running with constant stack space).

Julien.

Index: library/list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.136
diff -u -r1.136 list.m
--- library/list.m	1 Apr 2005 14:29:19 -0000	1.136
+++ library/list.m	4 Apr 2005 01:04:37 -0000
@@ -1990,17 +1990,36 @@

 %-----------------------------------------------------------------------------%

-list__series(I, OK, Succ) =
+list__series(I, OK, Succ) = Series :-
+	list__series_2(I, OK, Succ, [], Series0),
+	list__reverse(Series0, Series).
+
+:- pred list__series_2(T, pred(T), func(T) = T, list(T), list(T)).
+:- mode list__series_2(in, pred(in) is semidet, func(in) = out is det,
+	in, out) is det.
+
+list__series_2(I, OK, Succ, !Series) :-
 	( OK(I) ->
-		[I | list__series(Succ(I), OK, Succ)]
+		!:Series = [ I | !.Series ],
+		list__series_2(Succ(I), OK, Succ, !Series)
 	;
-	  	[]
-	).
+		true
+	).

 %-----------------------------------------------------------------------------%

-Lo `..` Hi =
-	list__series(Lo, ( pred(I::in) is semidet :- I =< Hi ), plus(1)).
+Lo `..` Hi = List :- successive_integers(Lo, Hi, [], List).
+
+:- pred successive_integers(int::in, int::in, list(int)::in, list(int)::out)
+	is det.
+
+successive_integers(Lo, Hi, !Ints) :-
+	( Lo =< Hi ->
+		!:Ints = [ Hi | !.Ints ],
+		successive_integers(Lo, Hi - 1, !Ints)
+	;
+		true
+	).

 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%

--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------