benchmark for trailing & coroutining

[Fergus Henderson]

Hi,

Here's the results of a benchmark of three different versions
of the N-queens problem (for N = 10).

In order simplest to most complicated:
"queens" is the simple "generate & test" solution.
"dqueens" is a coroutining "test & generate" solution using when/block decls.
"vqueens" is a coroutining "test & generate" solution using freeze/2.
"cqueens" is a non-coroutining "interleaved generate-test" solution.

This was on kryten, using `-O6 --intermodule-optimization'.

program grade		user  sys   real    %cpu	slowdown vs asm_fast
------- -----           ---   ---   ----    ----
cqueens	asm_fast	0.01u 0.05s 0:00.10 60.0%	 1.0
queens	asm_fast	0.43u 0.07s 0:00.53 94.3%	 1.0

								cost of GC
cqueens	asm_fast.gc	0.06u 0.21s 0:00.33 81.8%	 3.30	230%
queens	asm_fast.gc	1.43u 0.25s 0:01.73 97.1%	 3.26	226%

								cost of
								GC + trailing
cqueens	asm_fast.gc.tr	0.12u 0.20s 0:00.34 94.1%	 3.40	230% + ~10%
queens	asm_fast.gc.tr	1.58u 0.26s 0:01.92 95.8%	 3.62	226% + 40%
vqueens	asm_fast.gc.tr	0.13u 0.22s 0:00.39 89.7%

							slowdown vs Mercury
cqueens	NU-Prolog	0.18u 0.29s 0:00.52 90.3%	 5.2	asm_fast
							 1.5	asm_fast.gc.tr
queens	NU-Prolog	6.63u 0.33s 0:07.01 99.2%	13.2	asm_fast
							 3.7	asm_fast.gc.tr
dqueens	NU-Prolog	5.32u 0.31s 0:05.73 98.2%	14.7	asm_fast.gc.tr

cqueens	SICSTUS compact	0.16u	0.47s	0:00.67	94.0%	 6.7	asm_fast
							 2.0	asm_fast.gc.tr
queens	SICSTUS compact	4.82u	0.46s	0:05.34	98.8%	10.1	asm_fast
							 2.8	asm_fast.gc.tr
dqueens	SICSTUS compact	4.05u	0.49s	0:04.59	98.9%	11.8	asm_fast.gc.tr

So, interesting things to note:

	* Coroutining seems to cost much less, relatively, for Mercury than
	  for NU-Prolog or SICStus.  For NU-Prolog and SICStus, the
	  coroutining version is an order of magnitude slower than
	  the sequential versions, but for Mercury its efficiency
	  is nearly equal to that of the best sequential version.

	  Note that this is with a version of freeze/2 doesn't check for
	  floundering; adding the check will slow it down a little.

	* Conservative GC costs a lot

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.