efficiency, deep lists

[Richard Carlsson]

On 2 Oct 2001, Luke Gorrie wrote:

> Luke Gorrie <luke@REDACTED> writes:

> For benchmarking, here's the list-of-lists version, which is just
> Ulf's incr2 with the recursive call moved from where the continuation
> is created to where the continuation is invoked:

This was interesting, so I did some benchmarks of my own. The results
seem to have little variance, and I think they can be trusted:

		Time   GC     Reclaimed
	incr1:  11100  40000  2.1e7   ;naive
	incr2:  7200   25005  1.5e7   ;fun-continuation
	incr3:  6800   10014  2.0e7   ;bad foldl-version
	incr3': 11900  44000  4.7e7   ;corrected foldl-version
	incr4:  7400   5003   2.1e7   ;flatten first
	incr5:  9000   30001  1.1e7   ;continuation as data
	incr6:  5200   10002  1.0e7   ;list-of-lists only
	incr7:  9200   53342  2.4e7   ;tail recursive version of 5
	incr8:  7600   26668  2.3e7   ;tail recursive version of 6
	incr9:  8000   20738  1.6e7   ;fun-continuation (any depth)

Explanations: incr3 was incorrectly implemented - the returned list is
in the wrong order, and since it did not compute the same function, it
could execute more efficiently than incr1, even though they seem to be
very similar at first glance. The corrected incr3' looks as follows:

	incr3(List) ->
	    lists:reverse(lists:foldl(
		    fun(L, Acc) ->
			    lists:reverse(incr11(L)) ++ Acc
		    end, [], List)).

and as can be seen above, it is comparable to incr1.

incr5 and incr6 are those implemented by Luke. As the table shows, incr6
is clearly the fastest implementation, but note that incr2 is not bad in
comparison to incr1 and incr4. incr7 and incr8 are tail-recursive
versions of Luke's implementations, using an accumulator argument and
reversing the final list before returning. The measurements show that
there is apparently no advantage to that technique in this case.

The really interesting version is incr9, which both uses funs as
continuations and handles lists of any depth. The code is very elegant,
and as you can see from the table, it is actually more efficient than
incr5.

	/Richard

Code for incr7-9:

 incr7(L) -> lists:reverse(incr77(L, [], [])).

 %% incr77(DeepList, [Continuation], [Accumulator])
 incr77([H|T], C, A) when list(H) ->
     incr77(H, [T|C], A);
 incr77([H|T], C, A) ->
     incr77(T, C, [H+1|A]);
 incr77([], [C|Cs], A) ->
     incr77(C, Cs, A);
 incr77([], [], A) ->
     A


 incr8(L) -> lists:reverse(incr88(L, [])).

 incr88([H|T], A) when list(H) ->
     incr888(H, T, A);
 incr88([], A) ->
     A.

 incr888([H|T], C, A) ->
     incr888(T, C, [H+1|A]);
 incr888([], C, A) ->
     incr88(C, A).


 incr9(L) -> incr99(L, fun () -> [] end).

 incr99([H|T], C) when list(H) ->
     incr99(H, fun () -> incr99(T, C) end);
 incr99([H|T], C) ->
     [H+1|incr99(T, C)];
 incr99([], C) ->
     C().



Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/