[m-rev.] for review: generalize the specialization of compare/3 predicates

[Zoltan Somogyi]

On 21-Jan-2002, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> My benchmark results so far show that we should be using the quadratic method
> for all n <= 9, but I do not have benchmark results yet for n >= 10. When I
> do, I will modify the default value of --compare-specialization, the option
> that gives the limit up to which we use the quadratic method.

Here are the extended results:

EXTRA_MCFLAGS = -O2 --compare-specialization 7
GRADE = asm_fast.gc
mercury_compile.01 average of 8 with ignore=0     17.65
mercury_compile.01 average of 8 with ignore=1     17.53
mercury_compile.01 average of 8 with ignore=2     17.52
EXTRA_MCFLAGS = -O2 --compare-specialization 8
GRADE = asm_fast.gc
mercury_compile.02 average of 8 with ignore=0     17.69
mercury_compile.02 average of 8 with ignore=1     17.48
mercury_compile.02 average of 8 with ignore=2     17.48
EXTRA_MCFLAGS = -O2 --compare-specialization 9
GRADE = asm_fast.gc
mercury_compile.03 average of 8 with ignore=0     17.43
mercury_compile.03 average of 8 with ignore=1     17.22
mercury_compile.03 average of 8 with ignore=2     17.22
EXTRA_MCFLAGS = -O2 --compare-specialization 10
GRADE = asm_fast.gc
mercury_compile.04 average of 8 with ignore=0     17.41
mercury_compile.04 average of 8 with ignore=1     17.18
mercury_compile.04 average of 8 with ignore=2     17.17
EXTRA_MCFLAGS = -O2 --compare-specialization 11
GRADE = asm_fast.gc
mercury_compile.05 average of 8 with ignore=0     17.41
mercury_compile.05 average of 8 with ignore=1     17.19
mercury_compile.05 average of 8 with ignore=2     17.19
EXTRA_MCFLAGS = -O2 --compare-specialization 12
GRADE = asm_fast.gc
mercury_compile.06 average of 8 with ignore=0     17.35
mercury_compile.06 average of 8 with ignore=1     17.12
mercury_compile.06 average of 8 with ignore=2     17.13
EXTRA_MCFLAGS = -O2 --compare-specialization 13
GRADE = asm_fast.gc
mercury_compile.07 average of 8 with ignore=0     17.33
mercury_compile.07 average of 8 with ignore=1     17.11
mercury_compile.07 average of 8 with ignore=2     17.11
EXTRA_MCFLAGS = -O2 --compare-specialization 14
GRADE = asm_fast.gc
mercury_compile.08 average of 8 with ignore=0     17.38
mercury_compile.08 average of 8 with ignore=1     17.16
mercury_compile.08 average of 8 with ignore=2     17.16
EXTRA_MCFLAGS = -O2 --compare-specialization 7
GRADE = hlc.gc
mercury_compile.09 average of 8 with ignore=0     21.22
mercury_compile.09 average of 8 with ignore=1     21.04
mercury_compile.09 average of 8 with ignore=2     21.05
EXTRA_MCFLAGS = -O2 --compare-specialization 8
GRADE = hlc.gc
mercury_compile.10 average of 8 with ignore=0     21.17
mercury_compile.10 average of 8 with ignore=1     21.00
mercury_compile.10 average of 8 with ignore=2     21.00
EXTRA_MCFLAGS = -O2 --compare-specialization 9
GRADE = hlc.gc
mercury_compile.11 average of 8 with ignore=0     21.02
mercury_compile.11 average of 8 with ignore=1     20.87
mercury_compile.11 average of 8 with ignore=2     20.87
EXTRA_MCFLAGS = -O2 --compare-specialization 10
GRADE = hlc.gc
mercury_compile.12 average of 8 with ignore=0     21.38
mercury_compile.12 average of 8 with ignore=1     21.21
mercury_compile.12 average of 8 with ignore=2     21.20
EXTRA_MCFLAGS = -O2 --compare-specialization 11
GRADE = hlc.gc
mercury_compile.13 average of 8 with ignore=0     21.35
mercury_compile.13 average of 8 with ignore=1     21.20
mercury_compile.13 average of 8 with ignore=2     21.20
EXTRA_MCFLAGS = -O2 --compare-specialization 12
GRADE = hlc.gc
mercury_compile.14 average of 8 with ignore=0     21.41
mercury_compile.14 average of 8 with ignore=1     21.25
mercury_compile.14 average of 8 with ignore=2     21.25
EXTRA_MCFLAGS = -O2 --compare-specialization 13
GRADE = hlc.gc
mercury_compile.15 average of 8 with ignore=0     21.35
mercury_compile.15 average of 8 with ignore=1     21.18
mercury_compile.15 average of 8 with ignore=2     21.19
EXTRA_MCFLAGS = -O2 --compare-specialization 14
GRADE = hlc.gc
mercury_compile.16 average of 8 with ignore=0     20.92
mercury_compile.16 average of 8 with ignore=1     20.74
mercury_compile.16 average of 8 with ignore=2     20.74

6316627	 105028	  70680	6492335	 6310af	compspec2.01 asm_fast.gc,  7
6315267	 106052	  70680	6491999	 630f5f	compspec2.02 asm_fast.gc,  8
6312019	 108452	  70680	6491151	 630c0f	compspec2.03 asm_fast.gc,  9
6311091	 110148	  70680	6491919	 630f0f	compspec2.04 asm_fast.gc, 10
6310947	 110692	  70680	6492319	 63109f	compspec2.05 asm_fast.gc, 11
6309491	 112548	  70680	6492719	 63122f	compspec2.06 asm_fast.gc, 12
6308483	 113636	  70680	6492799	 63127f	compspec2.07 asm_fast.gc, 13
6308131	 114756	  70680	6493567	 63157f	compspec2.08 asm_fast.gc, 14
4358726	   3864	  70776	4433366	 43a5d6	compspec2.09 hlc.gc,  7
4359142	   3864	  70776	4433782	 43a776	compspec2.10 hlc.gc,  8
4360022	   3864	  70776	4434662	 43aae6	compspec2.11 hlc.gc,  9
4361318	   3864	  70776	4435958	 43aff6	compspec2.12 hlc.gc, 10
4362150	   3864	  70776	4436790	 43b336	compspec2.13 hlc.gc, 11
4363526	   3864	  70776	4438166	 43b896	compspec2.14 hlc.gc, 12
4364518	   3864	  70776	4439158	 43bc76	compspec2.15 hlc.gc, 13
4365990	   3864	  70776	4440630	 43c236	compspec2.16 hlc.gc, 14

The minimum times are at 13 for asm_fast.gc and 14 for hlc.gc. For asm_fast.gc,
increasing the value of --compare-specialization reduces code size even at 14,
while for hlc.gc the code size starts to go up even before 7, but the effect
is very small; the difference between 7 and 14 is only a sixth of a percent.

I therefore propose the following diff (together with the updated log message)
to add to the one in my original mail.

Zoltan.

We have two ways to generate comparison predicates for du types. Suppose the
type has n function symbols. The quadratic method has n^2 clauses, one for each
combination of the bindings of the two arguments. The linear method creates an
index predicate for the type, calls it on each argument, and returns
immediately if the index values indicate a difference. If the index values
say the two arguments are bound to the same function symbol, the linear method
then has n cases, each comparing the arguments of a function symbol.

The quadratic method can be expected to be faster since it avoids function
calls and does fewer tests on the function symbol bound to each argument.
For small values of n, it can also be smaller, mainly due to the absence
of the index predicate. This change allows the user to select the use of
the quadratic method for all types whose value of n is up to a given limit,
whereas before there was a hardcoded limit requiring n <= 3.

compiler/unify_proc.m:
	Generalize the code that generates comparison procedures that
	explicitly compare each function symbol with every other, to
	handle types with any number of function symbols. Rename some
	predicates to make clearer the distinction between these predicates,
	which generate comparison predicates whose size is quadratic in the
	the number of function symbols in the type, from the predicates
	which generate comparison predicates whose size is linear in the
	the number of function symbols in the type.

compiler/handle_options.m:
	Delete the code that limited the exploited value of the
	--compare-specialization option, since the change to unify_proc.m
	has removed the cause of the limitation.

	Add code to set the value of --compare-specialization depending on the
	back end if the user has not given a value.

compiler/options.m:
	Make handle_options.m decide the default value of
	--compare-specialization.

	Move a misplaced comment.

cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/handle_options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.126
diff -u -b -r1.126 handle_options.m
--- compiler/handle_options.m	2002/01/24 02:27:22	1.126
+++ compiler/handle_options.m	2002/02/05 02:48:44
@@ -847,6 +838,23 @@
 	->
 		globals__io_set_option(backend_foreign_languages,
 			accumulating(BackendForeignLanguages))
+	;
+		[]
+	),
+
+	globals__io_lookup_int_option(compare_specialization, CompareSpec),
+	( { CompareSpec < 0 } ->
+		% This indicates that the option was not set by the user;
+		% we should set the option to the default value. This value
+		% may be back end specific, since different back ends have
+		% different performance tradeoffs.
+		(
+			{ HighLevel = no },
+			globals__io_set_option(compare_specialization, int(13))
+		;
+			{ HighLevel = yes },
+			globals__io_set_option(compare_specialization, int(14))
+		)
 	;
 		[]
 	),
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.350
diff -u -b -r1.350 options.m
--- compiler/options.m	2001/12/16 08:11:09	1.350
+++ compiler/options.m	2002/02/05 02:38:52
@@ -771,8 +771,11 @@
 					% at configuration time
 	pic			-	bool(no),
 	max_jump_table_size	-	int(0),
-	compare_specialization	-	int(4),
 					% 0 indicates any size.
+	compare_specialization	-	int(-1),
+					% -1 asks handle_options.m to give
+					% the value, which may be grade
+					% dependent.
 	fact_table_max_array_size -	int(1024),
 	fact_table_hash_percent_full - 	int(90),
 	gcc_local_labels	-	bool(no),
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------