narain@randvax.UUCP (Sanjai Narain) (05/27/90)
In the following program, there is one fact about f, namely f(1). Running times of two queries, each run a thousand times, are compared: f(X). bagof(X,f(X),S). The first takes about 25ms, whereas the second about 1200ms. Why a 40-fold difference in speed? Are there ways to speed up computation of sets? Timings are for Quintus Prolog on a SPARC station, running UNIX, with 16mb of main memory. Thanks for any response. Sanjai Narain time_b(T):-statistics(runtime,_),test_b(1000),statistics(runtime,[_,T]). time_c(T):-statistics(runtime,_),test_c(1000),statistics(runtime,[_,T]). test_b(0). test_b(N):-bagof(U,f(U),S),N1 is N-1, test_b(N1). test_c(0). test_c(N):-f(X),N1 is N-1,test_c(N1). f(1).
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/27/90)
In article <2556@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes: > In the following program, there is one fact about f, namely f(1). > Running times of two queries ... are compared: > f(X). % 25 micro-seconds each > bagof(X, f(X), S). % 1200 micro-seconds each > Why a 40-fold difference in speed? bagof/3 has to put the answers *somewhere*. Some Prologs have a special 'setof stack' or a "bubble" in the heap. Quintus Prolog basically does a special cheap assert and a special cheap retract, so it's faster than what you could write directly, but it's still an assert and a retract, and the old rule of thumb "1 data base change per millisecond" still holds good. The cost is likely to go down, but for large solution sets the cost of sorting to find solutions with the same bindings for free variables (or of sorting to eliminate duplicate solutions if you use setof/3, which is almost always the right thing to do) is O(NlgN) and is going to swamp O(N), and for small solution sets the cost of finding the answers usually dominates. I can imagine a 4-fold speed-up for this bagof/3 call (relative to other operations) with the aid of a special "setof stack" and special support code. Is this a very big problem? How many more copies of Quintus Prolog could be sold for each x% speedup of bagof/3? > Are there ways to speed up computation of sets? Depends on what the computation is doing. Tell me more about your real problem. -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/27/90)
In article <2556@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes: > In the following program, there is one fact about f, namely f(1). > Running times of two queries ... are compared: > f(X). % 25 micro-seconds each > bagof(X, f(X), S). % 1200 micro-seconds each > Why a 40-fold difference in speed? For the record, the ratio in NU Prolog 1.5#18 is 160. (This was on an Encore Multimax running "4.3BSD", essentially unloaded.) -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/28/90)
In article <2556@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes: > In the following program, there is one fact about f, namely f(1). ... > Why a 40-fold difference in [f(X) -vs- bagof(X, f(X), L)]? It's worth pointing out that the ratio depends on the cost of doing f/1. Letting there be N facts f(1). ... f(N), and letting R be the ratio (time to form a bag of all solutions) R = ------------------------------------- (time just to find all the solutions) I obtained the following results in NU Prolog 1.5#18 on Goanna: N = 1, R = 160 N = 10, R = 65 N = 100, R = 55 Remember that bagof/3 and setof/3 have a non-trivial startup cost: they have to scan the goal to find free variables, and they have to call the goal. Going through a dynamic call costs something. So for a generator with a *single* solution you're going to be measuring the full overhead and comparing it with the cheapest possible goal. From the NU Prolog figures, the marginal cost per solution for bagof is about 54 times slower than finding a solution by looking it up in a table. If the overhead/margin ratio were the same for Quintus Prolog, the marginal cost per solution of bagof would be about 14 times slower than finding a solution by looking it up in a table, not 40. (Quintus Prolog doesn't run on NS32532s, and my Sun-3/50's disc is being repaired, so I can't quote QP times.) There is, of course, no reason to believe that the overhead/margin ratio _is_ the same in Quintus Prolog, so the marginal cost per solution might be 10 times or 20 times or what have you. The only way I can think of to get a _less_ meaningful comparison than bagof/3 -vs- f(1) would be bagof/3 -vs- 'true'. -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
alain@kulcs.uucp (Alain Callebaut) (05/28/90)
In article <2556@randvax.UUCP> Sanjai Narain writes : > In the following program, there is one fact about f, namely f(1). > Running times of two queries, each run a thousand times, are compared: > > f(X). > bagof(X,f(X),S). > > The first takes about 25ms, whereas the second about 1200ms. Why a > 40-fold difference in speed? Are there ways to speed up computation > of sets? Timings are for Quintus Prolog on a SPARC station, running > UNIX, with 16mb of main memory. If you don't need the full flexibility of bagof, you could use findall instead : that's much faster. I did the same timings, on a SPARCstation 1, with 16 MB, for BIM_Prolog 2.5. The f(X) took 10ms, the bagof 330ms and a findall 150ms. Alain Callebaut
narain@randvax.UUCP (Sanjai Narain) (05/30/90)
I thank Alain Callebaut and Richard O'Keefe for quite useful answers to my query about bagof. The problem arose in the implementation of a simulation technique in Prolog. A model consists of causality rules, roughly of the form: A causes B if C Given that an event E has occurred, one needs to compute the set of all F such that E causes F. It turns out that in important cases the use of setof (or bagof) can be eliminated. This has yielded a speedup of 20 for our current model. Regards. Sanjai
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/31/90)
In article <2559@randvax.UUCP>, narain@randvax.UUCP (Sanjai Narain) writes: > I thank Alain Callebaut and Richard O'Keefe for quite useful answers to my > query about bagof. [...] > It turns out that in important cases the use of setof (or bagof) can > be eliminated. This has yielded a speedup of 20 for our current model. I think it would be a good idea for you to describe your original problem, how you coded it using bagof/3, and how you transformed it to eliminate the calls to bagof/3. There are few of us who would not welcome such speedups... -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
lang@PRC.Unisys.COM (Francois-Michel Lang) (05/31/90)
This is indirectly related to the speed of bagof/3: Do any (current or former) implementors out there have any thoughts about the possibility of providing built-in versions of bagof/setof that return a difference list? E.g., given f(1). f(2). f(3). f(4). we could do | ?- bagof_dl(X, f(X), List, Tail). X = _495, List = [1,2,3,4|Tail], Tail = _542 | ?- I isn't hard to write a version of *findall* that returns a difference list (after writing one myself I discovered one in the library...), but I haven't tried doing the same thing with bagof/setof. Another problem is that anything user-defined would have to use the ``expensive'' versions of assert/retract instead of the ``special cheap'' versions (presumably not accessible to users), and therefore be much slower. Any thoughts about this? ---------------------------------------------------------------------------- Francois-Michel Lang (215) 648-2536 Unisys Center for Advanced Information Technology lang@prc.unisys.com Dept of Comp & Info Science, U of PA lang@linc.cis.upenn.edu
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/01/90)
In article <14004@burdvax.PRC.Unisys.COM>, lang@PRC.Unisys.COM (Francois-Michel Lang) writes: > Do any (current or former) implementors out there > have any thoughts about the possibility of providing > built-in versions of bagof/setof that return a difference list? Sure it's possible. I'm the one that put findall/4 in the library. However, it's worth pointing out that in setof(Template, Generator, Set), append(Set, OldSet, NewList) you _don't_ get a set out the other end, just a NewList with no special properties. The analogue of findall/4 would be setof(Template, Generator, Set), ord_union(Set, OldSet, NewSet) which isn't the kind of thing you can do with difference lists. And in the case of bagof/3, the cost of doing an extra append/3 afterwards is typically a small fraction of the cost of the bagof/3 (10%, say). It's better to put the effort into better sorting routines. -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."