Re: pls confirm what approach is more efficient

On 2006-01-17, Bart Demoen <bmd@xxxxxxxxxxxxxxxxx> wrote:
> mneuhaber22@xxxxxxxxxx wrote:
>> Hello, as I delved deeper into Prolog I encountered coroutining.
>> The task below is to sum the elements in a list.
>> Assuming a very large input list, please confirm (or deny) my belief
>> that sum1 is more efficient because of the tail recursion than sum2.
>> Efficiency here is defined to mean that less computer resources must be
>> consumed to arrive at the result.
>> I promise I will not spam the group with stupid questions unless it's
>> really important to ask.
>>
>> sum1([], S) :- S = 0.
>> sum1([H|T], S) :- freeze(S1, S is S1 + H), sum1(T, S1).
>>
>>
>> sum2([], S) :- S = 0.
>> sum2([H|T], S) :- sum2(T, S1), S is S1 + H.
>>
>
> In SICStus Prolog sum2 is about 16 times faster than sum1 and sum2 also
> consumes less heap and less local stack than sum1.
>
> In B-Prolog (which has a notoriously fast freeze/2 mechanism), sum2 is
> "only" 5 times faster. I didn't measure accurately the heap and local stack
> consumption, but my bet is that in B-Prolog, the heap consumption is about the same,
> and the local stack consumption is at least twice as big for sum1 as for sum2.

Just tried where SWI-Prolog stood.

t1 :-
numlist(1, 100000, L),
time(sum1(L, _Sum)).

t2 :-
numlist(1, 100000, L),
time(sum2(L, _Sum)).

% pl -G0 -T0 -L0 -s sum.pl
1 ?- t1.
% 1,200,002 inferences, 0.74 CPU in 0.83 seconds (89% CPU, 1621624 Lips)

Yes
2 ?- t2.
% 200,002 inferences, 0.23 CPU in 0.24 seconds (94% CPU, 869574 Lips)

% pl -O -G0 -T0 -L0 -s sum.pl
1 ?- t1.
% 1,200,002 inferences, 0.85 CPU in 0.92 seconds (92% CPU, 1411767 Lips)

Yes
2 ?- t2.
% 100,002 inferences, 0.14 CPU in 0.16 seconds (87% CPU, 714300 Lips)

Factors aren't too bad. Fun is that the -arithemtic- optimiser makes t1
slower and t2 faster. Something I've seen before. Arithmetic intensive
applications get faster using optimised arithmetic while applications
using only a little arithmetic get slower. Probably this is related to
cache behaviour (program is running on an AMD Athlon).

--- Jan
.