Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!umich!samsung!munnari.oz.au!ditmela!yarra!monu6!minyos!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: Why is bagof so slow? Keywords: bagof, setof Message-ID: <3086@goanna.cs.rmit.oz.au> Date: 28 May 90 02:14:37 GMT References: <2556@randvax.UUCP> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 40 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."