In which cases/problems is Prolog faster than Java? - PROLOG

On 2008-05-19, Christina <christine.uk2000@gmail.com> wrote:
> I have implemented sorting algorithms like merge sort, tree sort and
> bubble sort in both Java and Trinc-Prolog, hoping to prove that Prolog
> runs faster than Java....Unfortunately, for large amount of data
> (30000 input size), Trinc-Prolog dies and Java runs in 2 or 3
> miliseconds....for small input, still Java is better in comparison
> with Trinc-Prolog. I will also test minimax algorithm for checkers,

I don't think Trinc-Prolog is known for speed. Better try YAP. No decent
Prolog should have problems with a list of 30,000 items. Still,
merge-sort on 30,000 items in SWI-Prolog takes 0.25 seconds on my
machine (AMD 5400+). YAP might get this down by a factor 10. Built-in
sort in SWI-Prolog does the job in about 2.5 milliseconds :-)

> both in Java and in Prolog, but this will take some time....firstly, I
> am interested in small problems that would prove Prolog's efficiency
> over Java.

I guess basically the answer is none. Like no program runs faster in
Java than it runs in well a crafted assembler program. The value of
Prolog is mostly in expressing the problem more concisely. It is best
at problems that involve some form of non-deterministic search.

Cheers --- Jan

> I want to know which problems work better in Prolog than in Java, so
> that I can continue my study.
> Thank you,
> Christine

On Mon, 19 May 2008 13:00:38 -0700, Christina wrote:

> I have implemented sorting algorithms like merge sort, tree sort and
> bubble sort in both Java and Trinc-Prolog, hoping to prove that Prolog
> runs faster than Java....Unfortunately, for large amount of data
> (30000 input size), Trinc-Prolog dies

Either your version of mergesort is crappy, or Trinc-Prolog stinks :-)
Probably both.
Show us your mergesort please. A reasonable mergesort in SWI-Prolog
(not the fastest around) sorts 30000 elements easily.

Cheers

Bart

On 19 Mai, 23:05, bart demoen <b...@cs.kuleuven.be> wrote:
> Show us your mergesort please. A reasonable mergesort in SWI-Prolog
> (not the fastest around) sorts 30000 elements easily.

% MERGE SORT
/* merge_sort(Xs, Ys) is true if Ys is a sorted permutation of the
list Xs.*/
group::merge_sort(List, SortedList):-
length(List, Length),
merge_sort_1(Length, List, SortedList, []).

/* merge_sort_1(N, Xs, Ys, Zs) is true if Ys is a sorted permutation
of */
/* the first N elements of the list Xs, and Zs are the remaining
elements */
/* of
Xs. */
merge_sort_1(0, Rest, [], Rest):-!.
merge_sort_1(1, [A|Rest], [A], Rest):-!.
merge_sort_1(2, [A,B|Rest], C, Rest):- A =< B, !, C = [A,B].
merge_sort_1(2, [A,B|Rest], C, Rest):- !, C = [B,A].
merge_sort_1(N, List, Sorted, Rest):-
N1 is N // 2, N2 is N - N1,
merge_sort_1(N1, List, SortedLeft, TempList),
merge_sort_1(N2, TempList, SortedRight, Rest),
ordered_merge(SortedLeft, SortedRight, Sorted).

/* ordered_merge(Xs, Ys, Zs) is true if Zs is an ordered list
obtained */
/* from merging the ordered lists Xs and
Ys. */
ordered_merge([X|Xs], [Y|Ys], [Y|Zs]):-
Y =< X, !,
ordered_merge([X|Xs], Ys, Zs).
ordered_merge([X|Xs], Ys, [X|Zs]):-
ordered_merge(Xs, Ys, Zs).
ordered_merge([], Ys, Ys).

/* length(Xs, L) is true if L is the number of elements in the list
Xs. */
length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number
of */
/* elements in the list
Xs. */
length_1([], L, L).
length_1([_|Xs], L0, L):- L1 is L0 + 1, length_1(Xs, L1, L).

I am running Trinc-Prolog R3b RC1 Trial version.
I have also installed SWI-Prolog and Logtalk, now I'm working on
converting the Trinc-Prolog
version of merge sort into the corresponding SWI-Prolog.
Does minimax algorithm work faster in Prolog than in Java?

Christina schreef:
> hoping to prove that Prolog runs faster than Java....

> I want to know which problems work better in Prolog than in Java, so
> that I can continue my study.

You might want to have a look at these numbers:

http://shootout.alioth.debian.org/gp...ng2=javaclient
http://shootout.alioth.debian.org/gp...ng2=javaclient

These numbers seem to suggest that "proiving" that Prolog runs faster
than Java will not be easy.

Cheers,
Peter

Christina wrote:

> Does minimax algorithm work faster in Prolog than in Java?

Some 10 years ago, when Java was only byte-code emulated, there was a
paper (or tech report) by (I think) Spanish people (UPM probably) who
showed with some benchmarks that Java and Prolog had roughly the same
performance (on some benchmarks, including qsort if I remember
right). I repeated some of those benchmarks myself at that time and it
depended a bit on which Prolog system one uses, and how one writes
particular constructs (if-then-else or multiple clauses with cut for
instance), but Java and Prolog were indeed close in speed.

In the mean time, Java execution technology has moved to JIT with
accordingly higher performance, while Prolog has mainly stayed
emulated. So you should expect that Java implementations are faster
(by an order of magnitude) than Prolog implementations. And that's all
you will be able to compare anyway: one implementation versus another
implementation, not one language versus another language. It's all in
the compiler technology that is used, nothing intrinsic in the
language, at least not for toy benchmarks where "everything is known".

BTW, you version of mergesort runs on lists of 30000 elements easily
in SWI, so you should blame the Trinc-Prolog implementation, not
Prolog - again the implementation and not a language.

A couple of weeks ago, a colleague from the numerical ****ysis group
said proudly that he had written a Sudoku solver and that he was
positively impressed that his program found the solution to a
newspaper puzzle in under 2 minutes. Now we know it is easy to write a
Sudoku solver in Prolog (and even easier in Prolog+constraints) that
solves puzzles in about a millisecond. It turned out that my colleague
had written his solver in MatLab ... so Prolog is faster than MatLab ?


Cheers

Bart Demoen

On 2008-05-20, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> Christina wrote:
>
>> Does minimax algorithm work faster in Prolog than in Java?
>
> Some 10 years ago, when Java was only byte-code emulated, there was a
> paper (or tech report) by (I think) Spanish people (UPM probably) who
> showed with some benchmarks that Java and Prolog had roughly the same
> performance (on some benchmarks, including qsort if I remember
> right). I repeated some of those benchmarks myself at that time and it
> depended a bit on which Prolog system one uses, and how one writes
> particular constructs (if-then-else or multiple clauses with cut for
> instance), but Java and Prolog were indeed close in speed.
>
> In the mean time, Java execution technology has moved to JIT with
> accordingly higher performance, while Prolog has mainly stayed
> emulated. So you should expect that Java implementations are faster
> (by an order of magnitude) than Prolog implementations. And that's all
> you will be able to compare anyway: one implementation versus another
> implementation, not one language versus another language. It's all in
> the compiler technology that is used, nothing intrinsic in the
> language, at least not for toy benchmarks where "everything is known".

To match the speed of Java (or other procuedural languages with unsafe
arithmetic) you have to do a lot of work. You need some form of JIT
and global ****ysis. I once benchmarked a little program doing a lot
of integer arithmetic and it turned out it was spending most of its
time in the (C) low level addition and multiplication functions doing
the actual work, just because it needs to do all the overflow checking
switching between C bounded arithmetic and unbounded arithmetic. Only
a global ****ysis that can do a check at entry of the loop and fall
back to a fast algorithm without these checks if conditions are met.
This seems language dependent. If the language doesn't guarantee safe
arithmetic the programmer is responsible (and cleverly moves the check
outside the loop or `forgets' about it all along), otherwise the
implementation. Ok, the Prolog standard allows for both. SWI-Prolog
implements safe arithmetic.

Another example is merge-sort. Implemented straightforwardly in
Prolog, it will produce a lot of garbage lists in the process. That
way you'll never win using Prolog. Not allowing destructive
assignment makes the language less vulnerable for programming
mistakes, but it also makes (some) algorithms slower. Only ****ysis
may be able to translate the one into the other, providing both good
performance and safety.

All in all though, performance generally isn't that important. The
simple fact that the slowest implementation of Prolog is the most
popular indicates there are other implementation/community aspects
that matter more :-)

Cheers --- Jan

Christina wrote:

> I have implemented sorting algorithms like merge sort, tree sort and
> bubble sort in both Java and Trinc-Prolog, hoping to prove that Prolog
> runs faster than Java....Unfortunately, for large amount of data
> (30000 input size), Trinc-Prolog dies and Java runs in 2 or 3
> miliseconds....for small input, still Java is better in comparison
> with Trinc-Prolog. I will also test minimax algorithm for checkers,
> both in Java and in Prolog, but this will take some time....firstly, I
> am interested in small problems that would prove Prolog's efficiency
> over Java.
> I want to know which problems work better in Prolog than in Java, so
> that I can continue my study.
> Thank you,
> Christine

Problems that involve unification, depth first search, recursion,
serious list manipulation will be better implemented in Prolog.

Its not just the speed. Its the process of implementing the solution.
You will require two or three times the amount of code to implement
unification and DFS, and list processing in Java than it takes in
Prolog.

also after you done implementing it in Java maintaining it will be
(somewhat of a challenge)

So comparing qsort, bubble sort, etc is not a good metric.

There are list manipulation techniques in Prolog that can easily be done
in a single line
of Prolog that would require many lines of Java. The same is true for
Prolog algorithms
that rely on unification, DFS and recursion. I've had to convert Prolog
code to Java and
C++ its (almost) never a pretty sight. And the C++ and Java
programmers that have
to maintain it always feel trepidation.

On May 20, 5:25 am, Cameron Hughes <cahug...@cc.ysu.edu> wrote:
> Christina wrote:
> > I have implemented sorting algorithms like merge sort, tree sort and
> > bubble sort in both Java and Trinc-Prolog, hoping to prove that Prolog
> > runs faster than Java....Unfortunately, for large amount of data
> > (30000 input size), Trinc-Prolog dies and Java runs in 2 or 3
> > miliseconds....for small input, still Java is better in comparison
> > with Trinc-Prolog. I will also test minimax algorithm for checkers,
> > both in Java and in Prolog, but this will take some time....firstly, I
> > am interested in small problems that would prove Prolog's efficiency
> > over Java.
> > I want to know which problems work better in Prolog than in Java, so
> > that I can continue my study.
> > Thank you,
> > Christine
>
> Problems that involve unification, depth first search, recursion,
> serious list manipulation will be better implemented in Prolog.
>
> Its not just the speed. Its the process of implementing the solution.
> You will require two or three times the amount of code to implement
> unification and DFS, and list processing in Java than it takes in
> Prolog.
>
> also after you done implementing it in Java maintaining it will be
> (somewhat of a challenge)
>
> So comparing qsort, bubble sort, etc is not a good metric.
>
> There are list manipulation techniques in Prolog that can easily be done
> in a single line
> of Prolog that would require many lines of Java. The same is true for
> Prolog algorithms
> that rely on unification, DFS and recursion. I've had to convert Prolog
> code to Java and
> C++ its (almost) never a pretty sight. And the C++ and Java
> programmers that have
> to maintain it always feel trepidation.


Suggestions for new benchmarks game problems are welcome, make them on
the discussion forum or preferably make a feature request

http://shootout.alioth.debian.org/gp...x/faq.php#help


The difficulty we run up against trying to find problems that show
Prolog in a good light is that in other languages the functionality
for the obvious solutions to those problems is in a library rather
than in the language.

And it's awkward simply requiring recursion or requiring lists (rather
than allowing iteration and arrays) so if you know of specific
problems which have solutions that are awkward but not impossible
using iteration and arrays ...

On Tue, 20 May 2008 09:47:24 -0700 (PDT)
Isaac Gouy <igouy2@yahoo.com> wrote:

> On May 20, 5:25 am, Cameron Hughes <cahug...@cc.ysu.edu> wrote:
> > Christina wrote:
> > > I have implemented sorting algorithms like merge sort, tree sort and
> > > bubble sort in both Java and Trinc-Prolog, hoping to prove that Prolog
> > > runs faster than Java....Unfortunately, for large amount of data
> > > (30000 input size), Trinc-Prolog dies and Java runs in 2 or 3
> > > miliseconds....for small input, still Java is better in comparison
> > > with Trinc-Prolog. I will also test minimax algorithm for checkers,
> > > both in Java and in Prolog, but this will take some time....firstly, I
> > > am interested in small problems that would prove Prolog's efficiency
> > > over Java.
> > > I want to know which problems work better in Prolog than in Java, so
> > > that I can continue my study.
> > > Thank you,
> > > Christine
> >
> > Problems that involve unification, depth first search, recursion,
> > serious list manipulation will be better implemented in Prolog.
> >
> > Its not just the speed. Its the process of implementing the solution.
> > You will require two or three times the amount of code to implement
> > unification and DFS, and list processing in Java than it takes in
> > Prolog.
> >
> > also after you done implementing it in Java maintaining it will be
> > (somewhat of a challenge)
> >
> > So comparing qsort, bubble sort, etc is not a good metric.
> >
> > There are list manipulation techniques in Prolog that can easily be done
> > in a single line
> > of Prolog that would require many lines of Java. The same is true for
> > Prolog algorithms
> > that rely on unification, DFS and recursion. I've had to convert Prolog
> > code to Java and
> > C++ its (almost) never a pretty sight. And the C++ and Java
> > programmers that have
> > to maintain it always feel trepidation.
>
>
> Suggestions for new benchmarks game problems are welcome, make them on
> the discussion forum or preferably make a feature request
>
> http://shootout.alioth.debian.org/gp...x/faq.php#help
>
>
> The difficulty we run up against trying to find problems that show
> Prolog in a good light is that in other languages the functionality
> for the obvious solutions to those problems is in a library rather
> than in the language.
>
> And it's awkward simply requiring recursion or requiring lists (rather
> than allowing iteration and arrays) so if you know of specific
> problems which have solutions that are awkward but not impossible
> using iteration and arrays ...
>

Seems kinda pointless. The place where Prolog shines over other
languages is in saving _programmer_ time, not machine time.

Dhu