Re: pls confirm what approach is more efficient

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@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.
>
>
>
> 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

.

Relevant Pages

  • Re: pls confirm what approach is more efficient
    ... > recursion is a good thing because it can be transformed into iteration, ... > therefore stack usage is constant. ... > something more efficient that doesn't consume resources linear to the ... > Prolog, how can the most resource efficient implementation be picked ...
    (comp.lang.prolog)
  • Re: Any use for recursion?
    ... In modern languages there is no overhead. ... popped back off the stack, the program counter being changed again. ... Recursion is ubiquitous in modern software. ...
    (comp.programming)
  • Re: Memory management strategy
    ... >>trading memory for speed ... The use of registers instead of the stack doesn't need inlining. ... >longer instructions to access smaller data than they were optimized for. ... square) but it didn't need recursion or some kind of stack. ...
    (comp.lang.c)
  • Re: grassfire algorithm in java
    ... > How many recursions did it take to overflow the stack? ... > say, recursion counting does. ... For debugging it MAY be a useful technique - but you are talking about using ...
    (comp.lang.java.programmer)
  • Re: Is this tai-recursion?
    ... There is no difference between tail-recursion and iteration. ... That's why tail-recursion is so simple, ... fetch next instruction from instruction pointer ... instructions will manipulate the processor stack. ...
    (comp.lang.scheme)