🚀 go-pugleaf

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