Home > Archive > Prolog > January 2006 > pls confirm what approach is more efficient
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
pls confirm what approach is more efficient
|
|
| mneuhaber22@berlin.com 2006-01-17, 3:59 am |
| 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.
| |
| Bart Demoen 2006-01-17, 3:59 am |
| mneuhaber22@berlin.com 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.
You may ask why that can be.
But I will respond with asking: why do you think sum1 is faster or more memory efficient ?
And why do you think that sum1 is tail recursive ?
Finally, a more efficient sum than sum1 and sum2, and also one which does not need a linear amount
of heap or local stack (linear in input list):
sum(L,N) :- sum(L,0,N).
sum([],N,N).
sum([X|R],I,N) :- I2 is I + X, sum(R,I2,N).
Cheers
Bart Demoen
| |
| Jan Wielemaker 2006-01-17, 3:59 am |
| On 2006-01-17, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> mneuhaber22@berlin.com wrote:
>
> 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
| |
| mneuhaber22@berlin.com 2006-01-17, 7:04 pm |
| To answer your question, I read in a book about Prolog that tail
recursion is a good thing because it can be transformed into iteration,
therefore stack usage is constant. I wasn't able to transform sum2 into
something more efficient that doesn't consume resources linear to the
size of the list (example that you provide is wondeful). So I was
determined to write the that function in a tail recursive fashion no
matter what. The result was sum1, which upon reflection and upon
analyzing with 'statistics/0' turns out to be a dud. sum1 cannot be
made iterative because freeze causes uninstantiated variables to be
remembered on the stack...
My problem is this - all my professional life I've known C and C++ and
have been writing high performance OS kernel and driver code. Now I
have to write a high performance (realtime) C++ application residing in
userspace that calls into Prolog for decision support and it's very
important to me to keep resource usage as small as possible. The big
challenge is this - if there are several ways to write a function in
Prolog, how can the most resource efficient implementation be picked
out?
Can all left recursive functions be transformed into right recursive?
Can all predicates that consume resources proportionate to the size of
the input set be rewritten cleverly to consume constant resources?
If the answer to these questions is no, then what classes of problems
lend themselves to more efficient rewrite and how?
I wish I could understand your thinking that led you to write sum/3.
Bart Demoen wrote:
> mneuhaber22@berlin.com wrote:
>
> 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.
>
>
>
> You may ask why that can be.
> But I will respond with asking: why do you think sum1 is faster or more memory efficient ?
> And why do you think that sum1 is tail recursive ?
>
> Finally, a more efficient sum than sum1 and sum2, and also one which does not need a linear amount
> of heap or local stack (linear in input list):
>
> sum(L,N) :- sum(L,0,N).
> sum([],N,N).
> sum([X|R],I,N) :- I2 is I + X, sum(R,I2,N).
>
>
>
> Cheers
>
> Bart Demoen
| |
| Jan Wielemaker 2006-01-17, 7:04 pm |
| On 2006-01-17, mneuhaber22@berlin.com <mneuhaber22@berlin.com> wrote:
> To answer your question, I read in a book about Prolog that tail
> recursion is a good thing because it can be transformed into iteration,
> therefore stack usage is constant. I wasn't able to transform sum2 into
> something more efficient that doesn't consume resources linear to the
> size of the list (example that you provide is wondeful). So I was
> determined to write the that function in a tail recursive fashion no
> matter what. The result was sum1, which upon reflection and upon
> analyzing with 'statistics/0' turns out to be a dud. sum1 cannot be
> made iterative because freeze causes uninstantiated variables to be
> remembered on the stack...
Good. Coroutining can help in making it easier to write an application
that does things at the right moment and thus avoid unnecessary
recomputation. Its generally slower than well carefully crafted code as
freeze isn't free. It must store the frozen goal somewhere and restart
it when the time is ready. In some cases sorting out the proper
scheduling of goals when writing the code is hard or even impossible if
it depends on unknown input. Dynamic scheduling is your friend now, but
its an expensive one. In other words, you trade performance for
high-level writing.
> My problem is this - all my professional life I've known C and C++ and
> have been writing high performance OS kernel and driver code. Now I
> have to write a high performance (realtime) C++ application residing in
> userspace that calls into Prolog for decision support and it's very
> important to me to keep resource usage as small as possible. The big
Good. I do quite a bit of low level C hacking myself. Both have
their merits and the combination can deal with many problems :-)
> challenge is this - if there are several ways to write a function in
> Prolog, how can the most resource efficient implementation be picked
> out?
The issue isn't much different from C/C++. You roughly have to know
what is expensive and what is cheap in Prolog (a profiler helps here)
and know the design patterns that give you the cleanest and fastest
solution. "The Craft of Prolog" by Richard O'Keefe is the book to
read.
> Can all left recursive functions be transformed into right recursive?
Its a question for more theoretical people, but considering that any
recursive procedure can be translated into a non-recursive one the
answer is probably `yes'. In many cases, the result won't get prettier.
Without any doubt, any Prolog program can be translated into a C
program, then you can remove recursion and you'll have a fast but
complicated program :-)
> Can all predicates that consume resources proportionate to the size of
> the input set be rewritten cleverly to consume constant resources?
If the algorithm allows for that in C, you can get it done in Prolog
too.
> If the answer to these questions is no, then what classes of problems
> lend themselves to more efficient rewrite and how?
> I wish I could understand your thinking that led you to write sum/3.
The extra variable is known as `accumulator'. It replaces the variable
you increment (accumulate) destructively in C to do the job. Remember
you can't change the variable value in Prolog! More advanced Prolog
texts will explain the use of accumulators.
Success --- Jan
> Bart Demoen wrote:
>
| |
|
| mneuhaber22@berlin.com wrote:
> Can all left recursive functions be transformed into right recursive?
The answer to this wouldn't help you.
> Can all predicates that consume resources proportionate to the size of
> the input set be rewritten cleverly to consume constant resources?
Is this asking whether the (space) complexity classes
linear-space and constant-space are equal ? I bet they are not :-)
> If the answer to these questions is no, then what classes of problems
> lend themselves to more efficient rewrite and how?
I have no answer.
> I wish I could understand your thinking that led you to write sum/3.
Ah, this is an easy one :-) It is standard practice in declarative
languages.
The general technique is called "accumulating parameter" and you do it
all the time in C; e.g. the sum function would be something like:
accu = 0;
while is_list(L)
{
accu = accu + head(L);
L = L->next;
}
return(accu);
Often, when you would transform a recursive C-function into a while loop
(or a for), you would introduce such a variable that holds the value
"up-to-now". It accumuilates until it has the final value. The
equivalent in Prolog is: transforming a left-recursive predicate
into a tail-recursive one (the while loop) with an extra parameter.
Saumya Debray has some paper(s) about it and his PhD Thesis contains
stuff about it as well - to do it automatically I mean.
Cheers
Bart Demoen
| |
| Walter 2006-01-23, 9:56 pm |
| Bart et al. have some good responses. I would like to respond to your
question re: why isn't sum1 tail recursive.
Tail recursion works because you can reuse the stack space (etc) of the
current call for the recursive call. To do this there must be no choice
points, and no variables to remember. In the case of sum1, freeze had to
stash the continuation somewhere, so it was not "really" usefully tail
recursive in the sense you were looking for.
The programming pattern for tail recursion on lists is
p([]).
p([H|T]) :- handle(H), p(T).
with of course other arguments and conditions that make it useful.
since prolog does not have assignments (eg x=x+1;) and iteration,
you pass x+1 into the recursive call, which compilers turn into iteration.
There is some cost converting between C and Prolog data representations, so
you will have the same engineering considerations you have when using C and
SQL (for example). The fewer times you have to cross the interface, the more
efficient your code will be. In my experience Prolog is now as fast as C for
symbolic processing. See my paper in ICLP05.
Walter Wilson
| |
| Walter 2006-01-23, 9:56 pm |
| Hmmmm, on my version of SICStus (3.12.3 x86-win32-nt-4) on my tired old
laptop i get roughly equivalent results of about 580ms to sum a 100000
element list:
| ?-
length(L,100000),make2(L),statistics(run
time,T),sum2(L,S),statistics(runtime
,T2).
L = [1,1,1,1,1,1,1,1,1,1|...],
S = 100000,
T = [18748,270],
T2 = [19328,580] ?
yes
| ?-
length(L,100000),make2(L),statistics(run
time,T),sum1(L,S),statistics(runtime
,T2).
L = [1,1,1,1,1,1,1,1,1,1|...],
S = 100000,
T = [19599,271],
T2 = [20181,582] ?
yes
| ?-
On SWI i get different performance: sum2 is slightly faster than SICStus,
but sum1 is 10x slower:
2 ?- t1(100000,T2).
T2 = [12117, 5798]
Yes
3 ?- t2(100000,T2).
T2 = [12728, 411]
"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1137484813.899612@seven.kulnet.kuleuven.ac.be...
> mneuhaber22@berlin.com wrote:
.. . .
> In SICStus Prolog sum2 is about 16 times faster than sum1 and sum2 also
> consumes less heap and less local stack than sum1.
>
|
|
|
|
|