Fill list with counting numbers in swi-prolog
bill....@mail.com
I thought this could be done this way:
create_list(N,L) :- length(L,N), forall(between(1,N,X), nth1(X,L,X)).
However, this does not seem to work (the list is returned with
uninstantiated variables).
When I run the code with trace, it seems to work fine.
Can anyone say what I am doing wrong?
k...@kymhorsell.com
why not just use setof(X,between(X,1,N),L).
--
[Tautology 101:]
As noted, the USA is big, and not monolithic in its behavior.
-- John Larkin <jjla...@highNOTlandTHIStechnologyPART.com>, 27 Feb 2011 15:13 -0800
Paulo Moura
The forall/2 built-in predicate implements a generate and test loop
using negation. Thus, it can check that for all solutions of the first
argument (the generator), the second argument (the test) is true. But
it will not return any instantiations.
You can write, however, the create_list/2 predicate without using
second-order predicates (such as for all/2 or setof/3). The basic idea
is to construct the list while walking from 1 to N.
Cheers,
Paulo
Jan Burse
> bill....@mail.com wrote:
>> I am trying to fill a list of given length N with numbers 1,2,3,...,N.
>> I thought this could be done this way:
>> create_list(N,L) :- length(L,N), forall(between(1,N,X), nth1(X,L,X)).
>> However, this does not seem to work (the list is returned with
>> uninstantiated variables).
>> When I run the code with trace, it seems to work fine.
>> Can anyone say what I am doing wrong?
>
> why not just use setof(X,between(X,1,N),L).
>
bill....@mail.com
Thanks for the quick response.
That clears things up.
bart demoen
> Thanks for the quick response.
> That clears things up.
Paulo's answer is spot-on: it tells the OP WHY his approach does not
work, gives a good hint at what to discover for the OP-self
and says explicitly "second-order preds ... you can do without".
Several +points for Paulo, several -points for the others.
One additional "fact" the OP might be interested in: some timings
of the three versions of the predicate you wanted - timings in millisecs
for 1000 times creating a list of a 1000 consecutive numbers:
setof findall nofrills ala Paulo
hProlog 2960 2210 150
SWI 7259 6661 1309
YAP 2040 1020 400
SISCtus 4170 3640 850
XSB 3480 2070 640
ECLiPse 3840 3690 1470
Cheers
Bart Demoen
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
k...@kymhorsell.com
...
> Or how about good old findall(X,between(X,1,N),L)?
Will normally do the right thing (but at least with the Prolog's I've
made over the years) why take the chance on the ordering? :)
--
[Rain as the origin of SLR:]
The slow rise of sea level is caused by rain. Water transfer the soil to see.
The acceleration during the last 50 years is caused by using gas and oil
instead of coal. Gas and oil are changed into water during combustion.
So the slow or the accelerated rise of sea level is not a problem.
-- Szczepan Bialek <sz.b...@wp.pl>, 28 May 2011 09:50 +0200
Jan Burse
> findall nofrills overhead
> hProlog 2210 150 2060
> SWI 6661 1309 5352
> YAP 1020 400 620
> SISCtus 3640 850 2790
> XSB 2070 640 1430
> ECLiPse 3690 1470 2220
hProlog is champion nofrills (best list tail recursion).
YAP is champion overhead (best findall).
Combine YAP findall and hProlog list tail recursion,
would give a nice Prolog. Where the findall solution,
now eventually 620+150~770, would even beat a many
nofrills solutions.
But would need figures of between without findall
to better judge the perspective.
Bye
Jan Burse
> findall nofrills
> SWI 6661 1309
BTW: Cannot reproduce the SWI ratio of approximately
5:1 between findall and nofrills. I get only a 5:2 ratio.
I get for 1000 times running:
range1 in 234 ms
range2 in 171 ms
between1 in 422 ms
true in 0 ms
The test predicates are:
range1(L,L,[L]).
range1(L,H,[L|R]) :- L<H, N is L+1, range1(N,H,R).
range1 :- range1(1,1000,_).
range2(L,L,X,[L|X]).
range2(L,H,X,Y) :- L<H, N is H-1, range2(L,N,[H|X],Y).
range2 :- range2(1,1000,[],_).
between1(L,_,L).
between1(L,H,X) :- L<H, N is L+1, between1(N,H,X).
between1 :- findall(X,between1(1,1000,X),_).
The SWI Prolog version is:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.10.4)
Copyright (c) 1990-2011 University of Amsterdam, VU Amsterdam
k...@kymhorsell.com
It is not impossible to use macros or partial evaluation techniques to
specialise at least some setof/bagof's.
But efficiency is the primary considertion of only engineers, n'est pas? :)
--
[Debunking SR?]
The only problem is you can't do arithmetic,
Einstein's calculation is tau = t * sqrt(1-v^2/c^2),
ref: http://www.fourmilab.ch/etexts/einstein/specrel/www/figures/img61.gif
2.2usec * sqrt(1-0.999^2) = 0.098362 usec [OOPS!]
and NOT the measured 64 usec.
-- "Androcles" <Headm...@Hogwarts.physics_ae>, 30 Dec 2010 10:53:02 -0000
Jan Burse
> But efficiency is the primary considertion of only engineers, n'est pas? :)
>
Wouldn't say so. Engineers are like physician (not physicist).
They call you in when there is a problem. Typical problem
of the end-user: Spider webs all around his head, because
of waiting so long for the computer to produce a result.
Bye
van...@vsta.org
> Or how about good old findall(X,between(X,1,N),L)?
But isn't a "classic" Prolog solution worth mentioning?
create_list(1,[1]).
create_list(N,[1|L]) :- build_list(2,N,L).
build_list(Top,Top,[Top]).
build_list(N,Top,[N|T]) :- plus(N,1,N1), build_list(N1,Top,T).
Sorry, my Prolog math system is... minimal. But I hope you get the idea.
--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html
afa
> bill.car...@mail.com wrote:
> > I am trying to fill a list of given length N with numbers 1,2,3,...,N.
> > I thought this could be done this way:
> > create_list(N,L) :- length(L,N), forall(between(1,N,X), nth1(X,L,X)).
> > However, this does not seem to work (the list is returned with
> > uninstantiated variables).
> > When I run the code with trace, it seems to work fine.
> > Can anyone say what I am doing wrong?
>
> why not just use setof(X,between(X,1,N),L).
>
comprehension:-) You can just do the following (using list
comprehension in B-Prolog):
create_list(N,L) :- L @= [I : I in 1..N].
Take a look at my web page for links to solutions for ASP and Prolog
programming contests. I believe that Prolog in general must borrow
these constructs from functional programming for it to gain wider
acceptance. You just ask people to leave Prolog if you persuade them
to use findall/setof for this kind of purposes.
Cheers,
Neng-Fa
Bill Carson
I have a question concerning the execution time:
how comes the second-order pred-version is so much slower?
When I look up the implementation of the 'findall'-predicate, I see the
following (GNU version):
'$findall'(Template, Generator, Instances, Func) :-
'$check_list_arg'(Instances, Func),
'$store_solutions'(Template, Generator, Stop, Func),
'$call_c_test'('Recover_Solutions_2'(Stop, 0, Instances)).
'$store_solutions'(Template, Generator, Stop, Func) :-
'$call_c'('Stop_Mark_1'(Stop)),
( '$call'(Generator, Func, 3, true),
'$call_c'('Store_Solution_1'(Template)),
fail
; true
).
(C-code not included)
So basically, this predicate runs the :Goal until it returns false, and
then reconstructs the found solutions.
Can anyone tell me why this is so much slower than a straightforward
version of the fill-the-list script?
Surely, the rebuilding of the found solutions is quite cumbersome, but
then again, we don't have to deal with the recursive calls of ourselves
like in the straightforward version.
I am quite surprised there is such a great difference in execution time
for a simple goal like filling a list with integers.
The imperative world is all about compiler-optimization to reduce such
difference in speed, but apparently the declarative languages are not
fretting too much about it?
Sure, the difference here is quite small, but I am certain there are
cases where a second-order predicate can make the code much more readable/
maintainable, and after all, isn't that what we're after when using a
language like Prolog?
Andrew Davison
> I have a question concerning the execution time:
> how comes the second-order pred-version is so much slower?
> When I look up the implementation of the 'findall'-predicate, I see the
> following (GNU version):
>
Out of interest running with the latest gprolog, the findall version is
about 50% slower than nofrills, compared to the latest SWI which is
about 100% or more. Thw SWI (64-bit) was a bit faster though overall
than gprolog (32-bit).
Using findall + the builtin between/3 (SWI) was faster but still not as
fast as nofrills.
Using findall + builtin for/3 (gprolog) was faster than nofrills.
Prolog range1 range2 findall+between1 findall+builtin
--------------------------------------------------------------------
SWI 249 218 577 390
gprolog 374 375 530 250
mine 515 562 780 359
*Just for the mix, I have included results for my homebrew Prolog.
- agd
Andrew Davison
> Prolog range1 range2 findall+between1 findall+builtin
> --------------------------------------------------------------------
>
> SWI 249 218 577 390
> gprolog 374 375 530 250
> mine 515 562 780 359
>
>
Time is in ms. Of course the findall+builtin does very little actual
Prolog stuff!
Jan Burse
> SWI 249 218 577 390
The finding that range2 is a little faster in SWI Prolog
seems to be stable. Or has it to do that range1 is executed
first. I am still not sure.
Andrew Davison
it doesn't seem to be order related, just is a tiny bit faster.
bart demoen
> bart demoen schrieb:
> > findall nofrills
>> SWI 6661 1309
>
> BTW: Cannot reproduce the SWI ratio of approximately 5:1 between findall
> and nofrills. I get only a 5:2 ratio.
Please try my range3:
range3(I,J,In,Out) :-
K is J - I, K >= 0,
integer(K),
range3helper(K,J,In,Out).
range3helper(I,J,In,Out) :-
(I == 0 ->
Out = [J|In]
;
J1 is J - 1,
I1 is I - 1,
range3helper(I1,J1,[J|In],Out)
).
range3 :- range3(1,1000,[],_).
Is 5:1 now closer ?
Jan Burse
bart demoen schrieb:
> Please try my range3:
>
> range3(I,J,In,Out) :-
> K is J - I, K>= 0,
> integer(K),
> range3helper(K,J,In,Out).
>
> range3helper(I,J,In,Out) :-
> (I == 0 ->
> Out = [J|In]
> ;
> J1 is J - 1,
> I1 is I - 1,
> range3helper(I1,J1,[J|In],Out)
> ).
>
> range3 :- range3(1,1000,[],_).
>
> Is 5:1 now closer ?
range3 versus range2/1:
range3 uses integer check, ok this is fair enough,
because it would loop without and a float difference
with a non-zero fraction, because of the way termination
is checked. And there is no big penalty for it, since
it is done once per range3 call.
range3helper uses two substractions and if-then-else.
The two substractions are needed since the termination
check is a constant check to zero now. But an extra
subtraction can be expensive. And the if-then-else can
also be expensive when not cleverly compiled.
But lets give it a try:
Either a bug or feature? SWI translates it into, turns
the substraction into an addition:
range3helper(A, C, D, B) :-
( A==0
-> B=[C|D]
; F is C+ -1,
E is A+ -1,
range3helper(E, F, [C|D], B)
).
Here are the results (again 1000 runs):
range1 in 219 ms
range2 in 171 ms
range3 in 94 ms
And the winner is: range3? And well now we have 5:1.
My hypothesis: The unification and clause backtracking
is slower than the arithmetic and the if-then-else.
In range1 and range2 there is an L = L unification, and
a clause choice point and not an if-then-else choice point.
But now we need a between3 as well, isn't it. Maybe we fall
back to 5:2. Interestingly we fall back to something
around 4:1:
Here are the results (again 1000 runs):
between1 in 484 ms
between3 in 374 ms
Here is the between3:
between3(I,J,Out) :-
K is J - I, K >= 0,
integer(K),
between3helper(K,I,Out).
between3helper(I,J,Out) :-
Out = J; I\==0, J1 is J + 1, I1 is I - 1,
between3helper(I1,J1,Out).
between3 :- findall(X,between3(1,1000,X),_).
Best Regards
Jan Burse
> My hypothesis: The unification and clause backtracking
> is slower than the arithmetic and the if-then-else.
> In range1 and range2 there is an L = L unification, and
> a clause choice point and not an if-then-else choice point.
Additional hypothesis: The tail recursion, since both variables
are replaced, is also efficienter.
Bart Demoen
> I have a question concerning the execution time: how comes the
> second-order pred-version is so much slower?
Several things - not so much the fact that the Goal is meta-called:
that's minor.
The Generator in findall/3 produces solutions by
backtracking - backtracking is expensive.
The creation of a new solution (with between/3 it is a small
integer) is peanuts compared to what findall/3 has to do for every
new solution, and which is not specialized for this very simple case.
In particular, '$call_c'('Store_Solution_1'(Template)) is very expensive
(at least its equivalent in hProlog is, and I assume the same is true in
GNU)
Most implementations of findall/3 around copy the solution list
an extra time - not a very big cost in this case, but it adds up.
Also note that if the Generator throws an exception, one wants the
findall/3 to end gracefully, and then rethrow the exception: that costs
in setting up the findall/3.
And ISO requires an extra test on the third argument of findall/3 - again
small cost, but it adds up ...
All in all, specializing findall/3 for the particular call (with
between/3 as Generator) would help - but one would need to be able to
specialize it up to the level of the C-implementation of
'$call_c'('Store_Solution_1'(Template)), meaning one needs the type
and the mode ... not very Prolog like. And all that would probably
still not cut the time up to the nofrills version, because of the
backtracking.
So, one needs an extra step: use the Ueda transformations as in his
paper "Making exhausive search programs deterministic" (part I and II,
ICLP86 and ICLP87 resp.)
Bart Demoen
> hProlog is champion nofrills (best list tail recursion). YAP is champion
> overhead (best findall).
Only because I made some bad decisions (related to keeping some things
thread local in findall/3) recently when a student of mine introduced
multi-threading in hProlog - when I find time to turn those decisions
back, the timing for findall will go back to the old one, i.e. a
factor 3 faster.
Mats Carlsson
> I am trying to fill a list of given length N with numbers 1,2,3,...,N.
> I thought this could be done this way:
>
> create_list(N,L) :- length(L,N), forall(between(1,N,X), nth1(X,L,X)).
SICStus/ECLiPSe style:
create_list(N,L) :-
( for(I,1,N),
foreach(I,L)
do true
).
| ?- create_list(8,L).
L = [1,2,3,4,5,6,7,8] ?
Jan Burse
How about the per-formance?
Mats Carlsson
1000 times creating a list of a 1000 consecutive numbers takes about
50 msec on my 2.8 GHz Intel box.
Bill Carson
I don't fully understand why the temporary storing of found results
causes so much delay.
When I look up the implementation in hProlog (which you referred), I get:
findall(Template,Goal,List,Tail) :-
'dollar_dollar_findall_init'(I),
(
call(Goal),
'dollar_dollar_findall_add'(Template,I),
fail
;
'dollar_dollar_findall_get_solutions'(L,T,I),
List = L,
Tail = T
).
With the equivalent of GNU's '$call_c'('Store_Solution_1'(Template)) thus
being:
int findall_add()
{
dlong * arg1, arg2, arg3 ;
dlong * to, h ;
int size ;
// arg3 = ptoc_tag(3);
// {
// int t = cell_tag(arg3) ;
// if ((t != XSB_REF) && (t != XSB_REF1)) return(0) ;
// }
//
// arg1 = ptoc_tag(1);
// arg2 = ptoc_tag(2);
//
// current_findall = findall_solutions + int_val(arg2) ;
// if (current_findall->tail == 0)
// fatal_message("internal error 1 in findall") ;
//
// to = current_findall->top_of_chunk ;
// if ((to+2) > (current_findall->current_chunk + FINDALL_CHUNCK_SIZE
-1)) {
// if (! get_more_chunk()) return(0) ;
// to = current_findall->top_of_chunk ;
// }
//
// h = to + 2 ;
// gl_bot = (dlong *)glstack.low ; gl_top = (dlong *)glstack.high ;
//
// if (init_findall_trail() &&
// (0 <= (size = findall_copy_template_to_chunk(arg1,to,&h)))) {
// findall_untrail() ;
// current_findall->top_of_chunk = h ;
// /* 2 because of ./2 of solution list */
// current_findall->size += size + 2 ;
// bld_free((to+1)) ;
// /* link in new template now */
// *(dlong *)(*(current_findall->tail)) = makelist(to);
// current_findall->tail = to+1 ; /* fill in new tail */
// return(1);
// }
//
// findall_untrail() ;
// return FALSE;
} /* findall_add */
Basically, the adding of elements to a temporary list and then rebuilding
it only adds a O(n) factor, which should be negligible for large input
values, no? (Or does the allocation/freeing of heap memory causes the
delay?)
Finally, I am right when I say that the lesson I could from this is that
it is always better to replace backtracking procedures with recursive
calls whenever feasible?
afa
I am curious about B-Prolog's numbers. Don't bother if you are tired
of dealing with me or B-Prolog after compiling the TPLP special issue
on Prolog implementation:-).
Cheers,
Neng-Fa
Ulrich Neumerkel
However,
?- create_list(0,[_|_]).
Loops!
Kish Shen
> setof findall nofrills ala Paulo
> hProlog 2960 2210 150
> SWI 7259 6661 1309
> YAP 2040 1020 400
> SISCtus 4170 3640 850
> XSB 3480 2070 640
> ECLiPse 3840 3690 1470
The timing for the 'nofrills' for ECLiPSe seems to be rather slow
relative to the other systems, and so different to what I expected, that
I decided to try and verify it. I used your range3 predicate that you
posted, and ran that 1000 times on a Linux box (not sure of the exact
spec (it is a VM), but it is running 32 bit Linux), on SWI and ECLiPSe.
SWI 5.10.4 110
ECLiPSe 6.0#186 40
Times in ms. On the same machine, running the version with do loops
(posted by Mats) took 60ms.
I used cputime to get the timings for SWI, but just used the time
returned by the toplevel in ECLiPSe. In the ECLiPSe case, this includes
the time taken for garbage collection, although I don't think this was
significant here.
I also compiled with 'nogbgcomp', which produces (slightly) faster
(non-debuggable) code. Without this, the range3 example took 50ms.
So I am not sure why your results for ECLiPSe is so slow (relative to
the other systems)...
Cheers,
Kish
Bart Demoen
> But efficiency is the primary considertion of only engineers, n'est pas?
> :)
I have been hesitating to ask, but did you mean "n'est-ce pas?" ?
I was hesitating mainly because French is just my third best (natural)
language, but if it is your mother tongue, it would presumptuous of me
to try to correct your use of French of course.
Apart from that, your :) at the end gives a humorous light touch to what
you say, so I assume you are joking and just trying to rattle some
people's chains.
One sees contempt for efficiency care in this and other
newsgroups regularly. (I don't care that much about contempt for
engineers: it is just jealousy (*) :-).
I understand efficiency is not everybody's prime consideration.
Like I understand that the majority of people does not have garbage
collection as their prime concern. But without GC, society stops working.
Someone has to care about GC, and about efficiency.
Since I enjoy those issues, it can just as well be me :-)
You can care about something else - each of us can have a whale of time
without doing harm.
Cheers
Bart Demoen
(*) I am not an engineer myself, and proud of it :-)
k...@kymhorsell.com
> On Sat, 23 Jul 2011 23:05:37 +0000, kym wrote:
>> But efficiency is the primary considertion of only engineers, n'est pas?
>> :)
> I have been hesitating to ask, but did you mean "n'est-ce pas?" ?
No, it was a bait for correctiod Engineers.
bart demoen
> create_list(N,L) :- L @= [I : I in 1..N].
What I dislike about list comprehensions in B-Prolog (and the same
about
do/2 in SICStus or ECLiPSe) is that one can't really do meta-
programming
with it; in B-Prolog, it is just a matter of speed (lots of it) while
in SICStus/ECLiPSe, also some things just don't compile (but it might
be fixed
in releases more recent than the one I use of course).
Here is what I mean:
direct(_,N) :- L @= [I : I in 1..N], fail, use(L).
direct(M,N) :- M > 0, M1 is M - 1, direct(M1,N).
meta1(_,Term) :- L @= Term, fail, use(L).
meta1(M,Term) :- M > 0, M1 is M - 1, meta1(M1,Term).
meta2(_,Term) :- L @= [I : I in Term], fail, use(L).
meta2(M,Term) :- M > 0, M1 is M - 1, meta2(M1,Term).
meta3(_,Term) :- L @= [I : Term], fail, use(L).
meta3(M,Term) :- M > 0, M1 is M - 1, meta3(M1,Term).
time the queries
?- N = 1000, direct(N,N).
?- N = 1000, Term = ([I : I in 1..N]), meta1(N,Term).
?- N = 1000, Term = (1..N), meta2(N,Term).
?- N = 1000, Term = (I in 1..N), meta3(N,Term).
ans see how happy that makes you :-)
Cheers
Bart Demoen
bart demoen
> ...
You quote C-code I used until 2002 for booting hProlog only; I wrote
that C-code some 15 years ago, but it belongs to XSB: it is still in
XSB/emu/findall.c; I had forgotten about it :-)
Anyway, the hProlog findall_add code is similar.
> Basically, the adding of elements to a temporary list and then
> rebuilding it only adds a O(n) factor, which should be negligible for
> large input values, no? (Or does the allocation/freeing of heap memory
> causes the delay?)
Both between(1,N,X) and findall(X,between(1,N,X),L) are O(N), so
indeed, the extra O(N) does not change the complexity, but the
constant
factor difference is huge in the case of small integers (see later).
If it were just copying small ints, findall_add would be basically
*something = h+LIST_TAG;
*h++ = the_small_tagged_int;
*h = nil_atom;
something = h++;
but it doesn't know about the type, so apart from checking for
overflow, find the correct something (nested findalls are possible),
it
also needs to (or wants to) do some initialization (and do some
epilogue) for possible cyclic terms (or just keeping internal
sharing), and for keeping variable identity; it also keeps track of
the size of the solutions list+contents so that the final copy back
does not need to check for overflow at each step (that's XSB/hProlog
specific perhaps, but other systems pay back that cost at some point
anyway - and double).
Just to have a better idea, I specialized some C-code in findall for
the case the solution is a small integer. Here is the result:
setof findall
not specialized 2060 1210
specialized 1600 730
YAP 2230 1050 (just for reference)
Same program+query as mentioned in a reply to a post by Neng-Fa.
> Finally, I am right when I say that the lesson I could from this is that
> it is always better to replace backtracking procedures with recursive
> calls whenever feasible?
If only things would be so simple ... but no.
If the cost of computing the next solution is high (say O(n^5)) and
you need relatively many of them (say n == 100), then there is a good
chance that the backtracking+findall solution wins over a
(deterministic) recursive solution, because you might save massively
on locality of reference and garbage collection. Somewhere in between
O(n) and O(n^5) there is a grey zone where performance answers have
more fuzzy answers.
Cheers
Bart Demoen
Jan Burse
> You can write, however, the create_list/2 predicate without using
> second-order predicates (such as for all/2 or setof/3). The basic idea
> is to construct the list while walking from 1 to N.
How do you know that setof/3 is second order? Lets apply
the following criteria, a predicate is higher order if
it makes use of call/n with n>1. Then for example the p
redicate (;)/2:
A; _ :- A.
_; B :- B.
Would not be higher order, it only makes use of an implicit
call/1. But the following predicate checklist/2 would
be higher order:
checklist(F,[]).
checklist(F,[H|T]) :- call(F,H), checklist(F,T).
since it makes use of call/2. But I don't think that setof/3
needs call/n with n>1. So what makes it second order?
Bye
bart demoen
> I am curious about B-Prolog's numbers. Don't bother if you are tired
> of dealing with me or B-Prolog
I am not tired of dealing with you or B-Prolog ... well, not at the
moment :-)
setof findall nofrills my_between
B-Prolog 7650 1990 190 430
SICStus 4810 4200 1010 1040
YAP 2230 1050 310 460 (*)
SWI 7609 6900 1350 2340 (with -O)
ECLiPSe 4230 3840 1100 970 (with :- nodbgcomp.)
XSB 4190 2610 750 1210
hProlog 2060 1210 170 390 (**)
Prolog code at http://people.cs.kuleuven.be/~bart.demoen/numbers.pl
Query: ?- t(1000).
(*) that is my local YAP 6.0.5 that I hacked a bit to make the
emulator significantly faster - the hack is basically working
around a problem with gcc 4.4.3 which did not exist in gcc 2.3;
probably, YAP (and other emulators) have been suffering from this
for a long time :-(
Vitor wrote to me that the hack will go into one of the next
releases - but I think he will find a better way to achieve the
same effect :-)
(**) the setof/findall figures have improved since earlier posts - I
reconsidered some recent (bad) decisions; this is not specialized
for small ints (see another post)
Note that B-Prolog and YAP do not retain internal sharing on findall
(and/or copy_term) - I got confused interpreting global_stack_used in
ECLiPSe about the findall issue, but copy_term does not retain all
internal sharing.
Differences of 15% are not important and usually result from
circumstantial evidence, rather than collateral damage.
Cheers
Bart Demoen
Jan Burse
> setof findall my_between overhead
> B-Prolog 7650 1990 430 5660 (363%)
> SICStus 4810 4200 1040 610 (19%)
> YAP 2230 1050 460 1180 (200%)
> SWI 7609 6900 2340 709 (15%)
> ECLiPSe 4230 3840 970 490 (17%)
> XSB 4190 2610 1210 1580 (112%)
> hProlog 2060 1210 390 850 (103%)
When implementing setof, one can use findall
plus some witness calculation and some sorting.
In the above table I have calculated the setof
overhead, both absolute and relative:
overhead_abs = findall - setof
overhead_rel = overhead_abs / (findall - my_between)
The absolute champion in setof is ECLiPSe. The
relative champion in setof is SWI Prolog!
Best Regards
bart demoen
> The absolute champion in setof is ECLiPSe. The
> relative champion in setof is SWI Prolog!
I warned about 15% differences and
still someone makes such definite statements ... sigh :-(
Jan Burse
For those with some time on their hands,
interesting additional benchmark cases
would be:
Big Integers:
?- findall(X-Y,between(10000000000000000000001,
10000000000000000001000,X),L).
Variables:
fresh(_).
?- findall(X-Y,(between(1,1000,X),fresh(Y)),L).
Best Regards
Bart Demoen
> For those with some time on their hands,
you must be joking ...
> interesting additional
> benchmark cases would be:
Can you define what you want to measure, not in terms of the concrete
benchmark, but in a more abstract way, so that the concrete benchmark
can be put to the test itself ?
So, what do you want to uncover what we do not know already ?
Unless you are just throwing out bait for those who have "time on their
hands", so that you can do something useful in the mean time while others
are stalling ? If on the other hand you really think that what you propose
will reveal something interesting ... why not do the benchmarking
yourself ?
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
Jan Burse
> why not do the benchmarking yourself ?
An alternate hypothesis could be that somebody did
the benchmark already, and has only to open the
drawer. So I was just curious. Of course opening the
drawer does also take some time.
Bye
Jan Burse
> Can you define what you want to measure, not in terms of the concrete
> benchmark, but in a more abstract way, so that the concrete benchmark
> can be put to the test itself ?
It was in the headings:
> Big Integers:
> Variables:
I guess these headings could sound cryptic to Johnny can't
program. But otherwise I don't see any problem with these
headings.
The idea is of course not to reveal to much, and not to do
some discussion before hand. This would lower the suspense
and thrill to any Johnny/Joana that tries the things by
himself/herself.
And it would also reduce the diversity in test set-ups
and interpretations. Until now the test set-ups were mere
product based. But what else could one do, variate the
n, i.e. the number of list elements?
Anyway, anybody who has time on their hands, please have a
lot of fun. Testing and especially benchmarking is great
fun and gives you a lot of practical experience and
insight.
Best Regards
Jan Burse
> fun and gives you a lot of practical experience and
> insight.
Any numbers you later publish are probably only the
tip of iceberg of the experience you had. And those
numbers will be anyway outdated the time you publish
them since Prolog systems etc.. are constantly
evolving. The journey is the reward.
afa
Here are the timings I have got:
> ?- N = 1000, direct(N,N).
0.046s
> ?- N = 1000, Term = ([I : I in 1..N]), meta1(N,Term).
1.286s
> ?- N = 1000, Term = (1..N), meta2(N,Term).
1.476s
> ?- N = 1000, Term = (I in 1..N), meta3(N,Term).
1.411s
The first one is fast since list comprehension is translated into tail-
recursive predicates, and all others are interpreted since the
compiler has no information about the iterators. Your example does not
affect my happiness:-) because I never do meta-programming with these
constructs. In functional programming, you get syntax or type errors,
and in B-Prolog you get speed-down. Take a look at the example
programs I have posted to this news group:
http://www.sci.brooklyn.cuny.edu/~zhou/comp_lang_prolog.pl
and also programs for several competitions:
Third ASP Competition:
http://www.cs.nmsu.edu/ALP/2011/06/bpsolvers-solutions-to-the-third-asp-competition-problems/
Prolog programming contest 2011:
http://www.sci.brooklyn.cuny.edu/~zhou/prolog_contest/pc2011.txt
Prolog programming contest 2010:
http://www.sci.brooklyn.cuny.edu/~zhou/prolog_contest/pc2010.txt
Prolog programming contest 2009:
http://www.cs.nmsu.edu/ALP/2010/08/how-to-solve-it-with-b-prolog/
No foreach or list-comprehension is meta-interpreted.
Cheers,
Neng-Fa
afa
> setof findall nofrills my_between
> B-Prolog 7650 1990 190 430
The hot spot in setof for the benchmark is sort/2. After improving the
built-in to avoid sorting for already sorted integer lists (in version
7.5#8), I got the following times on my Windows PC:
setof findall nofrills my_between
2241 2165 264 457
Cheers,
Neng-Fa
bart demoen
# Big Integers:
#
# ?- findall(X-Y,between(10000000000000000000001,
# 10000000000000000001000,X),L).
What is the Y doing there - anything bigint related ?
What did you want to learn ? Whether the Prolog system has bigints or
not ? (B-Prolog, XSB, GNU don't) Whether they hook up to gmp or not ?
(SWI and YAP do, SISCtus and hProlog don't - I don't know about ECLiPSe,
but surely, one can find out without benchmarking). How systems deal with
bigints in findall ? (there are way better benchmarks to find out about
that).
# Variables:
#
# fresh(_).
#
# ?- findall(X-Y,(between(1,1000,X),fresh(Y)),L).
What did you want to learn ? About the efficiency of metacalling a
conjunction, about the call to a predicate that compiles to a simple
"proceed" instruction (in the WAM), about the ability/eagerness of the
Prolog system to do inlining or partial evaluation ... The figure you
get out of this "benchmark" is explaining nothing but "this is what I
got out of doing the benchmark".
Since this is summer time, and lots of people might have lots of time
on their hands, I guess any benchmark suggestion goes ... here is
another one:
?- setof(Z,(between(10000000000,10000010000,X),
name(X,XL),
sort(XL,XLs),
append(XLs,[0'a],XLsa),
nrev(XLsa,XLsar))^
(between(10000000000,10000010000,X),
name(X,XL),
sort(XL,XLs),
append(XLs,[0'a],XLsa),
nrev(XLsa,XLsar),
name(Z,XLsar)), L).
Do this at the toplevel (preferably on a 48 bit machine with only 16Kb
for the user data segment, but if not, don't hold back !), so that you
are bound to miss some actions there, and then suspense ... what do we
conclude from it ?
Two things:
un train peut en cacher un autre
and
week of programming can save half an hour of thinking
# The idea is of course not to reveal to much, and not to do
# some discussion before hand.
The idea seems to be rather "let's underestimate the readers of this
news group; let's name then Johnny and Joana, and assume they have no
brain; let's pretend we can give the some crappy toys and hope they keep
themselves busy".
Please, a little more respect for c.l.p., even in summertime.
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
Jan Burse
> # Big Integers:
> #
> # ?- findall(X-Y,between(10000000000000000000001,
> # 10000000000000000001000,X),L).
>
> What is the Y doing there - anything bigint related ?
Oh, this is a typo on my side, should read:
Big Integers:
?- findall(X,between(10000000000000000000001,
10000000000000000001000,X),L).
> The idea seems to be rather "let's underestimate the readers of this
> news group; let's name then Johnny and Joana, and assume they have no
> brain; let's pretend we can give the some crappy toys and hope
> they keep themselves busy".
>
> Please, a little more respect for c.l.p., even in summertime.
I guess I have pushed some buttons of yours. You know
I can post on c.l.p. and mention Johnny and Joana, and
this reference can be outside c.l.p. The Johnny was
a reference to:
Johnny can't program:
http://www.youtube.com/watch?v=M-FUZy1GSkg
You can also google the term, since its not necessarily
mentioned in the above video, but the problem has spured
a couple of articles on the web with the corresponding
heading.
> week of programming can save half an hour of thinking
Please don't try to sell me any stance about proper
engineering. Practical simulation is on equal foot
with theoretical methods in many circumstances, even
sometimes the only solution or an important
complementation.
If you show such a negative attituded towards things that
are or should be part of a CS curiculum and write such
crappy responses, you neither help anybody reading
usnet nor do you help your own reputation.
I guess you have some of the best reputations here
concerning Prolog, and I really don't understands what
bothers you and forces you to throw mud towards me.
What is exactly that bothers you?
Bye
Bart Demoen
> Your example does not affect my
> happiness:-) because I never do meta-programming with these constructs.
I assume you wouldn't care about the subway if you never took it.
Would you by the same token also defend the position that the subway
is not needed ?
More to the point: Prolog has advertised itself as easy to do
meta-programming in; if that ease (in principle) comes with
25-fold speed-down (in practice), what a pity.
> In functional programming, you get syntax or type errors, and in
> B-Prolog you get speed-down.
I agree that speed-down is better than errors - but can we please have
less speed-down ?
Cheers
Bart Demoen
Bart Demoen
> The hot spot in setof for the benchmark is sort/2. After improving the
> built-in to avoid sorting for already sorted integer lists
You forgot to mention here that I told you that that was the problem with
the B-Prolog setof ...
:-)
Bart Demoen
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
Bart Demoen
> ...
I find it next to impossible to keep up with all most recent versions
of all Prolog systems, but I should at least have mentioned very
explicitly I was using a very old ECLiPSe version when I showed some
timings - my only defense: the version number was mentioned in the
numbers.pl I had put on the net.
Anyway, to put at least one record straight, the timings are
setof findall nofrills my_between
oldECLiPSe 4230 3840 1100 970 (with :- nodbgcomp.)
newECLiPSe 3830 3510 290 810 (with :- nodbgcomp.)
oldECLiPSe Version 5.10 #126 (i386_linux)
newECLiPSe Version 6.0 #183 (x86_64_linux)
There is a marked improvement in nofrills due to the new improved
compiler by Joachim Schimpf - I was aware of this new compiler and
should have promptly downloaded the new version - mea culpa.
Cheers
Bart Demoen
--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---
Jan Burse
> setof findall nofrills my_between
> oldECLiPSe 4230 3840 1100 970 (with :- nodbgcomp.)
> newECLiPSe 3830 3510 290 810 (with :- nodbgcomp.)
The new eclipse is indeed fast.
Something else. I am looking for a test case that
combines findall/3, between/3 and nofrills that has
a certain appeal, i.e. some motivation behind it.
Now in wiki there is a funny example, the computation
of a perfect number:
perfect(N) :-
between(1, inf, N), U is N // 2,
findall(D, (between(1,U,D), N mod D =:= 0), Ds),
sumlist(Ds, N).
The appeal here is more for the mathematically
inclined.
Any other interesting findall examples around?
Best Regards
Jan Burse
!Curiosity killed the cat!
One more solution for between:
between4(Lo,Hi,_) :- Lo>Hi, !, fail.
between4(Lo,_,Lo).
between4(Lo,Hi,X) :- Lo2 is Lo+1, between4(Lo2,Hi,X).
Bart Demoen
> perfect(N) :-
> between(1, inf, N), U is N // 2,
> findall(D, (between(1,U,D), N mod D =:= 0), Ds), sumlist(Ds, N).
>
> The appeal here is more for the mathematically inclined.
>
> Any other interesting findall examples around?
Why did you think this is an interesting findall example ?
Did you try to run it ?
I bet you didn't.
[
0) ERROR: is/2: Arithmetic: `inf/0' is not a function
just citing SWI 5.11.25
]
Note the []: it is not a big issue, but as far as posting
interesting findall examples to the net ...
1) your perfect/1 is in terms of delivered answer N
O(N^2) (ignoring some details that make it worse)
and we know that the fifth answer is 33,550,336
so there is little chance it will be ever computed;
non-terminating-in-practice programs have a relevance problem
2) there is a whole theory about the numbers of divisors of N - for
the mathematically inclined I presume (apparently not for you) -
and for the other programmers, it is easy to check that up the
number of divisors of N is real small compared to N (and they are
all small integers in any Prolog implementation these days); for
the fifth answer N = 33,550,336, the number of divisors is just 63;
meaning: the findall lists are short
3) apart from all the theory about \sigma_0, there is a lay-man's
theory about the numbers of divisors of N based on its prime
factors and their multiplicity; a straithforward implementation of
that is only slightly more challenging, and way more efficient than
your program
Your program spends most of its time (99%+) in things not related to
findall/3 ...
Findall/3 is not stretched anywhere near to its limits in you program.
So, why exactly did you think this is an interesting findall example ?
Just curious. Maybe your post didn't get any attention (apart from
mine) because noone else bothers to disagree publicly ?
We don't have to agree on what is mud or not - but can we work towards
a better definition of "interesting findall example" ?
Bart Demoen
> Lets apply the following
> criteria, a predicate is higher order if it makes use of call/n with
> n>1.
Maybe you have noticed in the mean time: if you change the widely accepted
definition/criterium of something, you get no response - because people
don't even bother to point out that fact.
Maybe start by looking at one of the seminal papers on higher-order in
Prolog by David H.D. Warren ...
Jan Burse
> On Sat, 06 Aug 2011 20:58:27 +0200, Jan Burse wrote:
>
>
>> perfect(N) :-
>> between(1, inf, N), U is N // 2,
>> findall(D, (between(1,U,D), N mod D =:= 0), Ds), sumlist(Ds, N).
>>
>> The appeal here is more for the mathematically inclined.
>>
>> Any other interesting findall examples around?
>
> Why did you think this is an interesting findall example ?
> Did you try to run it ?
> I bet you didn't.
Pitty we didn't bet, because you would have lost
this bet. But you can send me a chocolate bar out
of courtesy, preferably white milk chocolate, with
nuts and rice crispies (+).
Here are some results (in milliseconds) so far:¨
gprolog: 118
SWI: 140
B-Prolog: 280
SICStus: 458
Jekejeke Prolog 0.9.0: 1'313
The test program was:
between1(Lo,Hi,_) :- Lo>Hi, !, fail.
between1(Lo,_,Lo).
between1(Lo,Hi,X) :- Lo2 is Lo+1, between1(Lo2,Hi,X).
sumlist1(L,S) :- sumlist1(L,0,S).
sumlist1([],I,I).
sumlist1([X|Y],I,O) :- H is I+X, sumlist1(Y,H,O).
perfect(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,(between1(1,Y,Z), X mod Z =:= 0),L),
sumlist1(L,X).
perfect :-
perfect(500,_),
fail.
suite :-
bench(3,perfect).
The relation between the results is not in
accordance with what I recently archived,
especially on the 64bit plattform. For more
information see (*), (**) and (***).
So the above example seems to be very well
suited to elaborate some still existing weak
spots in my interpreter.
Best Regards
(*)
http://www.facebook.com/photo.php?fbid=177506725651216
(**)
http://www.facebook.com/photo.php?fbid=177557452312810
(***)
http://www.facebook.com/photo.php?fbid=176655842402971
(+)
http://www.facebook.com/photo.php?fbid=177849172283638
Jan Burse
> Maybe you have noticed in the mean time: if you change the widely accepted
> definition/criterium of something, you get no response - because people
> don't even bother to point out that fact.
>
> Maybe start by looking at one of the seminal papers on higher-order in
> Prolog by David H.D. Warren ...
Conclusion 1) is that findall is not higher order, since it
makes no use of call/n with n>1. And (;)/2 is also
not higher order.
Conclusion 2) is that finall is higher order, since it
makes use of call/n with n>=1. And (;)/2 is also higher
order.
Which conclusion is right, or does neither of
the conclusions apply? Is the notion second order
involved because of some other aspect of findall?
Bye
Jan Burse
> So, why exactly did you think this is an interesting findall example ?
> Just curious. Maybe your post didn't get any attention (apart from
> mine) because noone else bothers to disagree publicly ?
Maybe because you and me are the only people currently not
spending some vacation quality time at some sunny place, but
instead sitting behind a computer screen....?
Bye
Jan Burse
> Your program spends most of its time (99%+) in things not related to
> findall/3 ... Findall/3 is not stretched anywhere near to its
> limits in you program.
Well this is a light handed claim by you, which is not
justifiable hypothesis in my opinion, given the low range
of 1..500. Findall involves two problems, executing the
inner goal and collecting the results.
In my example the inner goal will backtrack over its
conjunction up to 250 times. And the findall itself
will be invoked 500 times.
Whether the test case spends a lot of time findall or not,
depends on the number of factors that are collected in
the result list. If this number is high, then also
some time will be spent in sumlist. If this number is low
not much time will be spent in sumlist.
You were trying to convey a feeling for the number of
factors from the next perfect number, which has 63
factors, and you were judging this number of factors
as low. This contradicts my observation that a low
number implies more spending in findall, and your
claim that there is -1% spending in findall.
Well to be precise it confirms that there is not
much spending in collecting results. But it does not
confirm that the total running time does not reflect
the spending in the transition from the findall
invokation to the inner goal, both the prologue and
epilogue of this transition, and the execution of
the inner goal itself.
We can even be more precise, the number between 1
and 500 with the most factors is 360. It has 23
factors, namely:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,
18, 20, 24, 30, 36, 40, 45, 60, 72,
90, 120, 180]
But the average number of factors for the numbers
between 1 and 500 is (a prolog program that sums
the length of L in perfect/2 is easily conceived
for this purpose):
2650 / 500 = 5.3.
So in each iteration of the test case, we measure
1 step of between
1 step of findall
i/2 steps of inner between
i/2 steps of inner conjunction
i/2 steps of inner mod
5.3 steps of collecting factors
5.3 steps of sumlist
In total:
500 steps of between
* 500 steps of findall invocation
31375 steps of inner between
* 31375 steps of inner conjunction
31375 steps of inner mod
* 2650 steps of collecting factors
2650 steps of sumlist
I have marked the findall related steps with an asterisk.
To judge whether the non asterisk make up 99%+ is difficult
to judge in the current stage, since I don't know the
corresponding weights. But lets assume constant weights for
the moment, and look at the percentage.
500+31375+31375+2650 = 65900 ~ 66%
* 500+31375+2650 = 34525 ~ 34%
Total: 100425 ~ 100%
So the test case will spend 34% of the time in findall
related regions. If the non-findall related regions are
already heavily optimized, then the weight of these
regions will be lower, and the percentage spent in
findall related regions will be above 34%.
On the other hand when the findall is also already
optimized, and eventually the inner conjunction, the
invokation and the collection are neglible, then
the percentage spent in the findall region will be
below 34%. Eventually even go down to 1%. But I am
pretty sure that this is not yet the case for Jekejeke
Prolog.
The correct answer needs further empirical
verification. And eventually a contrast with
some nofrill counterpart, but not sure whether this
would work out well. But the findall can easily
be replaced by a nofrill list construction of
factors.
Best Regards
Jan Burse
Finally could pin-point the problem with findall. It is not that it is
not possible to have a fast calculation of perfect numbers via findall
in Jekejeke Prolog. One has just to massage a little bit the inner goal
of findall. And it seems that the rest of findall is efficient. What the
problem is with the low-performing variants of calling the inner goal is
not yet clear to me. Most of the other Prolog systems seem to be immune
to the way the inner goal is called, except for GNU Prolog, which shows
a similar pattern than Jekejeke Prolog, with additional problems in
findall_two and findall_one_right. GNU Prolog makes also a case for a
findall solution that can be faster than a nofrills solution.
The figures in milliseconds, lower is better:
Test gprolog SWI B-Prolog SICStus 0.9.0
nofrills 144 109 277 431 214
findall_two 170 109 241 432 320
findall_one_right 169 109 242 434 318
findall_one_left 89 94 239 423 311
findall_zero 85 125 241 426 313
findall_due 167 109 241 437 1'906
findall_uno_right 164 109 239 438 1'788
findall_uno_left 87 94 239 423 310
Main: HP EliteBook 8560p
Java: JDK 1.6.0_26 (64-bit)
gprolog GNU Prolog 1.4.0
SWI Multi-threaded, 64 bits, Version 5.10.4
B-Prolog B-Prolog Version 7.5#8
SICStus SICStus 4.2.0 (x86-win32-nt-4)
The test code:
/**
* Prolog code for finding a perfect number.
*
* Copyright 2011, XLOG Technologies GmbH, Switzerland
* Jekejeke Prolog 0.9.0 (a fast and small prolog interpreter)
*/
between1(Lo,Hi,_) :- Lo>Hi, !, fail.
between1(Lo,_,Lo).
between1(Lo,Hi,X) :- Lo2 is Lo+1, between1(Lo2,Hi,X).
sumlist1([],0).
sumlist1([X|Y],R) :- sumlist1(Y,H), R is X+H.
/* no frills solution */
factors(Lo,Hi,_,[]) :- Lo>Hi, !.
factors(Lo,Hi,X,[Lo|R]) :- X rem Lo =:= 0, !, Lo2 is Lo+1,
factors(Lo2,Hi,X,R).
factors(Lo,Hi,X,R) :- Lo2 is Lo+1, factors(Lo2,Hi,X,R).
nofrills(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
factors(1,Y,X,L),
sumlist1(L,X).
nofrills :-
nofrills(500,_).
/* inner goal pred solution two meta */
factors_two(Y,X,Z) :-
A=between1(1,Y,Z), B=(X rem Z =:= 0), A, B.
findall_two(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,factors_two(Y,X,Z),L),
sumlist1(L,X).
findall_two :-
findall_two(500,_).
/* inner goal pred solution one right meta */
factors_one_right(Y,X,Z) :-
A=(X rem Z =:= 0), between1(1,Y,Z), A.
findall_one_right(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,factors_one_right(Y,X,Z),L),
sumlist1(L,X).
findall_one_right :-
findall_one_right(500,_).
/* inner goal pred solution one left meta */
factors_one_left(Y,X,Z) :-
A=between1(1,Y,Z), A, X rem Z =:= 0.
findall_one_left(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,factors_one_left(Y,X,Z),L),
sumlist1(L,X).
findall_one_left :-
findall_one_left(500,_).
/* inner goal pred solution zero meta */
factors_zero(Y,X,Z) :-
between1(1,Y,Z), X rem Z =:= 0.
findall_zero(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,factors_zero(Y,X,Z),L),
sumlist1(L,X).
findall_zero :-
findall_zero(500,_).
/* inner goal conjunction solution due parameters */
due(A,B) :- A, B.
findall_due(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,due(between1(1,Y,Z), (X rem Z =:= 0)),L),
sumlist1(L,X).
findall_due :-
findall_due(500,_).
/* inner goal conjunction solution uno right parameters */
uno_right(Y,Z,B) :- between1(1,Y,Z), B.
findall_uno_right(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,uno_right(Y,Z, (X rem Z =:= 0)),L),
sumlist1(L,X).
findall_uno_right :-
findall_uno_right(500,_).
/* inner goal conjunction solution uno left parameters */
uno_left(A,X,Z) :- A, X rem Z =:= 0.
findall_uno_left(Hi,X) :-
between1(1,Hi,X),
Y is X // 2,
findall(Z,uno_left(between1(1,Y,Z), X,Z),L),
sumlist1(L,X).
findall_uno_left :-
findall_uno_left(500,_).
Best Regards
Bart Demoen schrieb:
Jan Burse
Got it fixed, problem was some variable ordering in the unification
which got messed up recently. The effect was a unusually high number
of derefs:
Messed Up Normal
nofrills 6'064'320 4'551'919
findall 108'835'364 4'614'607
Now the runtime results are as expected, in accordance with the
proportions of other banchmarks made so far:
Test gprolog SWI B-Prolog SICStus Jekejeke
nofrills 144 109 277 431 185
findall 167 109 241 437 147
Puh, this was pure adrenalin.
Best Regards
Jan Burse schrieb:
Bart Demoen
> Conclusion 1) is that findall is not higher order, since it makes no use
> of call/n with n>1. And (;)/2 is also not higher order.
>
> Conclusion 2) is that finall is higher order, since it makes use of
> call/n with n>=1. And (;)/2 is also higher order.
findall/3 is higher-order: it's definition quantifies over predicates.
as for ;/2:
either ;/2 is not a predicate, so it is not higher-order;
or you could consider ;/2 a predicate, and in that case it is HO.
Jan Burse
> Now in wiki there is a funny example, the computation
> of a perfect number:
>
> perfect(N) :-
> between(1, inf, N), U is N // 2,
> findall(D, (between(1,U,D), N mod D =:= 0), Ds),
> sumlist(Ds, N).
Can the perfect number example be traced back to?
http://groups.google.com/group/comp.lang.prolog/tree/browse_frm/month/1988-12/54b6809382290289
Post in comp.lang.prolog from Dec 16, 1988,
by Thomas Sj|land, titled Christmas pleasure.
Look at the funny divides:
divides(I,D) :- I is I//D*D.
So he is checking I==(I//D)*D, no rem or mod those times?
And it is a nofrills solution, no findall those times?
Best Regards
Bart Demoen
> The figures in milliseconds, lower is better:
Redoing your tests gives me similar figures for all systems
except for SICStus Prolog: I get figures that are between 10 and
2 times FASTER than what you obtained.
How did you load the program into SICStus Prolog ?
Did you declare all predicates dynamic ? Only for SICStus,
or for all other systems alike ?
Cheers
Jan Burse
I am comparing with SICStus in interpreter mode.
Not in compiled mode. Compiled mode is of course
faster.
I have a couple of Prolog systems identified
as compilers, and already done some tests as
well, but not yet for the findall stuff.
For compilers I also see factors of 2-10.
Interpreter mode is important in an upcoming
application, with high frequency clause add/
remove for thread_local predicates. So I am
mainly scoping my testing to some interpreters
around.
But who knows with all the advances in compilers
etc.. maybe will have to drop my assumptions
about focussing on interpreters some time sooner
or later. But there are still some compilers
around that even write files during the
compile step!
Bye
Bart Demoen
> ...
The bottom line is that you keep denying that Jeke compiles and
interpretes what it has compiled to, and that this is of a
very different nature than what SICStus does with consult/1:
all the evidence you have provided so far points to that.
Of course, it is a good way to make your system look better, but
it is utterly unfair.
If you want to convince us, please provide your source code.
Jan Burse
> The bottom line is that you keep denying that Jeke compiles and
> interpretes what it has compiled to, and that this is of a
Could be. SWI is also on my list of interpreters,
and similar to Jekejeke it compiles/interprets on
the fly. I don't care what you call it, the main
criteria is whether the given Prolog system has
multiple execution modes:
Mode 1: Fast execution, usually called "compiled",
but maybe slower during consult, maybe different
footprint, maybe restricted to static predicates.
Mode 2: Slow execution, usually called "interpreted",
maybe faster during consult, maybe different
footprint, maybe used in connection with dynamic
predicates.
So Jekejeke Prolog is in the row of those systems
that do not have two modes of execution. Similar
to SWI Prolog. SWI Prolog writes in his doc for
compile/1:
Compile files. SWI-Prolog doesn't distinguish
between compilation and consult.
Same for Jekejeke,
> Of course, it is a good way to make your system look
> better, but it is utterly unfair.
Yes an no. Since my interpreter is anyway slow,
at the current stage, it does make any sense
to compare with fast compilers. Because to have
comparable numbers I would need to invent some
methods of scaling.
So you have a ordering of the Prolog systems
along their performance:
P1, ..., Pn, Pn+1, ..., Pm
So Jekejeke Prolog is somewhere along Pm, slowest.
And what I call the "compilers" it is along P1 ..
Pn. And what I call the "interpreters" it is along
Pn+1 ... Pm.
When I compare with what I call the interpreters I
do not have to scale, I just use the exact same
number of test iterations for my system and the
other systems. And can have a look at the absolute
figures as well if I want.
If I would now compare with compilers, benchmarking
would be much more complicated for me, to interpret
the numbers. Already because the compilers are much
faster the runtimes tend to go into the range where
measurement granularity is more seen. So I would
need to change the number of iterations.
When I change the number of iterations GC behaviour
changes, and the test results become incompatible
to compare. I would also change the number of
iterations in my tests. But then I can wait for
ages for one test to complete, well not ages, but
around a minute instead a few seconds.
Etc.. Etc..
> If you want to convince us, please provide
> your source code.
Convince of what? The main characteristics of Jekejeke
Prolog is that it is a PLM. The source code is not
available. But an evaluation version is available.
This should suffice to put Jekejeke Prolog to the
test.
You can also run Jekejeke Prolog on any Plattform/
Architecture you want. Minimal requirement is that
there is a Java VM. This should show at least that no
native code is involved. You can even run it in an
applet. I don't know whether it is allowed to compile
Java bytecode on the fly in an applet. But this would
give evidence that also no Java bytecode is involved.
Jekejeke is explicitly an experiment not in some
abstract machine code generation, but more in fiddling
with the implementation of some very rough primitives.
Optimizing there, and doing it in a pure OO way.
The primities are documented here:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/02_reference/05_theories/02_inspect/03_intermediate.html
The friendly/0 and friendly/1 predicates are
only available in the development environment version.
You might call my Prolog system a compiler based on
the existence of this intermediate code, I wouldn't
mind. Nothing is gained or lost by just putting
labels on things.
Best Regards
Jan Burse
> Jekejeke is explicitly an experiment not in some
> abstract machine code generation, but more in fiddling
> with the implementation of some very rough primitives.
> Optimizing there, and doing it in a pure OO way.
> The primities are documented here:
> http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/02_reference/05_theories/02_inspect/03_intermediate.html
>
>
> The friendly/0 and friendly/1 predicates are
> only available in the development environment version.
> You might call my Prolog system a compiler based on
> the existence of this intermediate code, I wouldn't
> mind. Nothing is gained or lost by just putting
> labels on things.
The optimizations that can be seen as movements
or eliminations in the intermediate form are
documented here:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/05_optimizations/package.html
Best Regards
Jan Burse
> If I would now compare with compilers, benchmarking
> would be much more complicated for me, to interpret
But of course by not comparing with compilers,
I miss some insights. But at the moment I
am fully satisified with the insights from
the "interpreters". The insights there
anyway translate to the "compilers", so again
nothing is lost. And more can gained later.
Bye
bart demoen
# Well this is a light handed claim by you, which is not
# justifiable hypothesis in my opinion, given the low range
# of 1..500.
Uh, you just plucked the number 500 out of thin air, right ?
The message I responded to had inf, not 500.
But let me go with 500 for a moment and do a little less hand-waving;
with hProlog profiling, I get per predicate how many/often WAM
instructions are executed (I did give a 10-fold weight to non-WAM
instructions related to findall/3 - an overestimate, but ok).
For 500, the ratio instructions in findall/3 versus instructions in
the benchmark but not in findall/3, is
4%
For 5000, this is
0.4%
Just to anticipate a possible question: my findall/3 checks input as
ISO requires, and catches any exceptions from the generator; this
requires extra work for setting up findall, and it is put on the
findall/3 account.
You still think that my hypothesis is not justifiable ?
My "light-handed claim" was based on understanding the benchmark,
knowing quite well how my Prolog implementation works, and on a little
math knowledge about how the number of divisors grows: d(n) = o(n^eps)
for every eps > 0 (I must admit that I thought it was log(n), but
maybe not).
So, loosely speaking, as the 500 grows to inf, the 1% goes to
zero. But even at 500, the 1% was a very good guesstimate.
I am happy that in the mean time you discovered how the conjunction in
the second argument of findall/3 can make things look bad (I was
careful in the above profiling to exclude that, because it would skew
the results in favour of my 1%). Part of this is ISO requirements
(that some systems implement in a suboptimal way). But also note that
(especially for SICStus) the module system sits in the way of doing a
fast metacall, and SICStus even tries goal expansion on metacall (at
least it used to do that - I am not sure about the most recent
release).
Bart Demoen
bart demoen
# I don't care what you call it, the main
# criteria is whether the given Prolog system has
# multiple execution modes:
#
# Mode 1: Fast execution, usually called "compiled",
# but maybe slower during consult, maybe different
# footprint, maybe restricted to static predicates.
# Mode 2: Slow execution, usually called "interpreted",
# maybe faster during consult, maybe different
# footprint, maybe used in connection with dynamic
# predicates.
#
# So Jekejeke Prolog is in the row of those systems
# that do not have two modes of execution.
That puts hProlog and Jeke in the same row of systems: hProlog has
only one mode of execution. Can you see how unfair it would be to
compare hProlog (always compiled) with SICStus consulted ?
AFAIK, YAP has only one mode of execution as well, and same for XSB.
# SWI Prolog writes in his doc for compile/1:
#
# Compile files. SWI-Prolog doesn't distinguish
# between compilation and consult.
#
# Same for Jekejeke,
Same for hProlog, YAP, XSB ...
Where are your comparisons with those systems ? I can understand you
wouldn't like to compare with hProlog: it might not run on
non-(linux&intel)-like systems (because I have no time for that), but
how about YAP and XSB ?
# You might call my Prolog system a compiler based on
# the existence of this intermediate code, I wouldn't
# mind.
A small step for us, a big step for humankind :-)
I am so happy you say this: Jeke is a compiler like SICStus
(compiled), SWI, YAP, B-Prolog (compiled) and hProlog and [long list
should follow]
Native code is not the issue: those systems don't do native code in
their compiled mode (YAP does a bit experimentally).
# Nothing is gained or lost by just putting labels on things.
Right, however, after putting labels on things, the next step cannot
be avoided ...
I can understand (and even appreciate) that you are not in the
business of performance, but then why publish performance figures ?
Especially if those performance figures compare apples with pears
without being totally open about it.
If you have different goals than performance, excellent: tell us
about it, show what is special about Jeke - maybe its unique features
that can only by achieved in a non-performant mode and that nobody
else has, perfect ! Try to publish it, but please don't give us "Jeke
is faster than SISCtus in its slowest mode" (referees will reject it -
not a treath, just a prediction).
You note that "compilation can ... factor 1..10": 5 is about the
factor between SWI and hProlog - both implementations follow the same
compilation/emulator design though with different design decision.
GNU-Prolog compiles a bit deeper than hProlog (to subroutine-threaded
code actually), but it doesn't really get more speed out of it.
SICStus abandoned (suspended) its native code generation, partly
because it gave only a factor 2 over emulation ...
Things are less simple than they appear.
Cheers
Bart Demoen
Jan Burse
I don't know what is wrong with you that you don't
understand the schema for benchmarking that I am
applying and that you turn around the words in my
mouth. First of all the main criteria for picking
some Prolog systems into the ensemble of my testing
is the following chain, and sadly I have to repeat
myself here from my previous post:
P1,..,Pn,Pn+1,...Pm
fast slow
So I draw the line n somewhere and call everthing
below n "compiler" and everything above n "interpreters".
So if your hProlog is below the line n, then it will
currently count as "compiler". And it will be not
subject to a official comparison with Jekejeke Prolog
sometime soon, because of the scaling problems I have
already mentioned in my previous post.
The rest of your post and also the other post of today
is just rediculus, full of mud throwing and insults.
I have *plonked* it.
Best Regards
bart demoen schrieb:
Jan Burse
Jan Burse schrieb:
> So if your hProlog is below the line n, then it will
> currently count as "compiler". And it will be not
> subject to a official comparison with Jekejeke Prolog
> sometime soon, because of the scaling problems I have
If you need a comparison between your hProlog
and Jekejeke Prolog you can serve yourself
and download it from www.jekejeke.ch, and do
what ever you want with it. I will be happy to
receive a copy of your results.
Bye
Jan Burse
> The rest of your post and also the other post of today
> is just rediculus, full of mud throwing and insults.
> I have *plonked* it.
I really hope that we will soon reach a de-escalation
of the matter. I am only responding frankly here
on your rudeness because I am usually following a
tit-for-tat strategy with my counterpart independent
of the status or whatever of the other side.
If you think that you are sitting in another boat
than this is fine for me, but this does not imply
that I will treat you in special manner, and that
you will be allowed to put irrelevant puns in each
and every post you do here.
If you want somebody to fool around, beat your
dog in the garden, but please don't try it on me.
Best Regards
bart demoen
> So I draw the line n somewhere and call everthing below n "compiler" and
> everything above n "interpreters".
You are messing with terminology. Please don't do that.
> The rest of your post and also the other post of today is just
> rediculus, full of mud throwing and insults. I have *plonked* it.
If you perceive it as mud and insults, that is a pity.
I thought that we were actually getting closer to a mutual understanding
of the matter. But I seem mistaken. I might have overestimated you. Sorry
for that.
In another post you wrote
> Jekejeke Prolog, you can serve yourself
> and download it from www.jekejeke.ch,
Really too much paperwork for me: if you want me to do your benchmarking
for you, you should make it easier for me.
BTW, I don't care whether you include hProlog in your benchmarking at all.
But please include YAP and XSB, and compare with compilers, just like
your own system.
In another post (*) you wrote
> So you have a ordering of the Prolog systems
> along their performance:
>
> P1, ..., Pn, Pn+1, ..., Pm
What exactly is your ordering ? How did you measure it ?
My experience is that most often SWI is about 4 times slower than YAP,
but I have a benchmark (with just ordinary "pure" Prolog !) for which
SWI is twice as fast as YAP (benchmark program due to Joachim Schimpf,
thank you Joachim).
Bart Demoen
(*) answering many of your posts in one go, so that I do not increase
my comp.lang.prolog footprint artificially
Jan Burse
> My experience is that most often SWI is about 4 times slower than YAP,
> but I have a benchmark (with just ordinary "pure" Prolog !) for which
> SWI is twice as fast as YAP (benchmark program due to Joachim Schimpf,
> thank you Joachim).
Could you please give some evidence about this benchmark.
A paper reference or a listing here. Otherwise it is just
a claim out of nothing. Vapor.
Bye
Jan Burse
schrieb:
> What exactly is your ordering ? How did you measure it ?
The benchmarks, and thus what I did measure is
all documented on the Jekejeke Prolog web site.
You can find the document here:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/package.html
The Jekejeke Prolog system is still in beta, so
are the benchmarks. They might change in the future.
But current ordering is based on these.
You also find the source code of the benchmark programs
and exact details about the used machine. Currently
I don't do extensive tests on multiple machines, only
one windows box so far.
The benchmarks on facebook are not yet documented,
they will be published in a few weeks together with
the new release 0.9.0.
Interestingly the figures will see kind of a boost,
since the new tests were done with the 64-bit version
of the JDK. Which behaves much better with the code
of the Prolog system:
http://www.facebook.com/photo.php?fbid=181721368563085
The 64-bit JDK has also influence on the ordering:
http://www.facebook.com/photo.php?fbid=177506725651216
But I need more investigation. It could be that a
Concurent Mark Sweep (CMS) is involved, that eventually
some garbage is left when the benchmark finishes.
Have also to check how to measure this and how to
control this. Also for the other Prolog systems.
Currently I don't have a good explanation for this
boost. Still looking around for explanations. One
explanation I did for myself was that most probably
the ALU is no more problem. I have mostly coded the
Prolog ALU with a fast path for ints (32-bit). Here
is a sketch:
mul(int a, int b) {
long res = (long)a * b;
if (Integer.MIN_VALUE <=res && res<=Integer.MAX_VALUE) {
return (int)res;
} else {
return new BigInteger(res);
}
}
The above should work with very few instructions and
mostly in registers with a 64-bit architecture,
since longs in Java are 64-bit. But the facebook figures
also indicate that the GC could be a reason for the
better performance.
But the facebook figures are just for entertainment.
Real new figures will be on the Jekejeke web site in
a few weeks.
Best Regards
Jan Burse
> BTW, I don't care whether you include hProlog in your benchmarking at all.
> But please include YAP and XSB, and compare with compilers, just like
> your own system.
If you insists that my system is a compiler, never
mind. This is accepted. You can call my system a
compiler. I don't care so much about labels. There
is no gain and no loss in putting this label to
my system. I said this already. Putting a label
on my system does not change the figures and
does not help me in development. Its just an
academic exercise.
Also I cannot follow your wish. And I already
explained you the reasons, if only you would
listen.
- Reason I) There is an inherent scaling
problem, it has to do with the GC as well. Short
benchmarks might just not trigger the GC. So
I want to benchmark with comparative GC load.
- Reason II) its a matter of cost, I don't have
time to benchmark a million Prolog compilers
around, because I am not interested in compilers
that produce good static code. I am interest
in Prolog systems that are able to deal
with high-frequency assert/retract of clauses
with body for dynamic predicates. Preferably
thread local. Corresponding benchmarks are in
preparation.
I wrote the two reasons already in previous emails.
But you don't seem to listen at all. I cannot
change these two reasons, so any wish of yours
that will violate these two reasons will not
be my command. Just out of scope.
I am really sorry that I cannot help you. My
work is based on other assumptions than might
be traditionally found for Prolog systems. It
doesn't make sense to fence me into one of
these traditional schemas. I nowhere made a
statement that my goal is to match these
traditional schemas. I am not working in the
line of traditional WAM architectures, with
notions such as emulator, etc..
My work splits off before the WAM, namely at
the PLM, and tries to do something else. So what
is needed is thinking outside the box. Any
reference I have to ISO is only on the language
level but not on the architectural level. Anyway
ISO does not so much define architecture. WAM
does define architecture, but in the traditional
von Neuman sense resp. register machine. But
I already divert from the WAM in the parameter
passing, which I do PLM style.
But goal is not to create a code for a register
machine, when preprocessing a clause. Goal is
to create a web of objects, that serves the
execution of the clause most. Reason is I have
to think this way is because I am going pure Java.
And in Java object pointers are non-orderable,
without some extra ado. So I cannot do the usual
C ptr++ gimmick. As a result a thread in my
Prolog system is just a cloud of objects, no
buffers that resize involved.
Anyway, good luck.
Best Regards
Jan Burse
> von Neuman sense resp. register machine. But
Jan Wielemaker
On 2011-07-23, bart demoen <bart....@cs.kuleuven.be> wrote:
> One additional "fact" the OP might be interested in: some timings
> of the three versions of the predicate you wanted - timings in millisecs
> for 1000 times creating a list of a 1000 consecutive numbers:
>
> setof findall nofrills ala Paulo
> hProlog 2960 2210 150
> SWI 7259 6661 1309
> YAP 2040 1020 400
> SISCtus 4170 3640 850
> XSB 3480 2070 640
> ECLiPse 3840 3690 1470
I was a bit surprised by these numbers. Retrying myself using YAP 6.0
and SWI-Prolog 5.11.25 and the program below, I get this:
findall nofrills
SWI 478 244
YAP 355 095
nf :-
forall(between(1, 1000, _),
numlist(1, 1000, _)).
f :-
forall(between(1, 1000, _),
findall(I, between(1, 1000, I), _)).
numlist(U, U, List) :- !,
List = [U].
numlist(L, U, [L|Ns]) :-
L2 is L+1,
numlist(L2, U, Ns).
This is on AMD64, Ubuntu 11.04, AMD Phenom(tm) 9600B @ 2300Mhz
Now, what is causing these differences? The program? Versions?
OS/Compiler?
Cheers --- Jan
Jan Burse
> BTW, I don't care whether you include hProlog in your benchmarking at all.
> But please include YAP and XSB, and compare with compilers, just like
> your own system.
Here are some compiler results:
Test YAP ECLiPSe Ciao XSB Jekejeke 0.9.0b
nrev 32 82 155 157 746
crypt 78 87 175 281 812
*deriv 78 119 622 354 494
poly 78 108 138 321 625
qsort 62 100 249 255 854
queens 78 107 181 213 883
query 172 258 439 708 1'358
tak 62 114 146 239 941
*perf 156 645 326 250 763
*calc 94 N/A N/A 637 807
Total 890 1'620 2'431 3'415 8'283
Calculator is a DCG example, I could not complete
the test suite for all systems.
ECLiPSe gave me during consult of the DCG example:
uncaught exception in exit_block(-127)
Abort
Ciao gave me during execution of the DCG example:
{ERROR: user:phrase/2 - existence error:
procedure:user:phrase/2 does not exist}
I did not use some modules.
Was not able to retrieve a windows executable for XSB
from the web, so was using previous release.
The results marked with an asterisk (*) are those
where something happens.
Best Regards
System details:
Mainboard: Windows 7, Intel Core i7-2720M @ 2.7GHz, 4MB Ram
Java: JDK 1.6.0_26 (64-bit)
ECLiPSe Version 6.0 #183 (i386_nt)
YAP YAP 6.2.1 (i686-mingw32)
Ciao Ciao 1.14.2-13646
XSB XSB Version 3.2 (Kopi Lewak)
Jekejeke Version: 0.9.0b (temporary variable
experiment), not yet published, will come soon
in a few weeks.
Just noticed that Ciao has also an interpreter
mode, might further look into it.
Bart Demoen
> Could you please give some evidence about this benchmark. A paper
> reference or a listing here. Otherwise it is just a claim out of
> nothing. Vapor.
The program was published by Joachim Schimpf in comp.lang.prolog:
From jsch...@users.sourceforge.net Tue Jun 29 19:52:30 CEST 2010
Subject: Re: shootout
It starts with the words
"It's debatable whether the Haskell program or Mats's eager version"
It is easy to delete the freeze or delay use from it, so that you
can time a query like ?- length(L,10000), pi(L).
I don't feel I can post the program: it is Joachim's and it was
published before.
"Vapor" ... you are pulling off the vapor trick on me, funny :-)