[m-dev.] for review: fix inst performance problem

[Fergus Henderson]

On 22-Feb-2000, Tyson Dowd <trd at cs.mu.OZ.AU> wrote:
> On 22-Feb-2000, Thomas Charles CONWAY <conway at cs.mu.OZ.AU> wrote:
> > Should we put something in the tests for this? It shouldn't
> > be too hard to test, since the performance problem was exponential.
> 
> I think this is an excellent idea.  Actually automatically testing the
> performance might not be necessary, but certainly the test case should
> be kept.

Finding an appropriate test case was quite a lot of work,
because the original test case was part of a complicated
multi-module program, and it was quite difficult to extract
a simple test case from it that still demonstrated the problem.

However, it turned out to be a good thing to do, because in the
process I discovered a different performance bug which this
change does not fix.

Anyway, here's an updated log message, and diffs for the new test cases.
As well as adding some test cases, this also fixes a mistake in the last
paragraph of my original log message, which was referring to
inst_contains_instname when it should have been talking about
mode_list_contains_inst_var.

I'll go ahead and commit this now (on both the main branch
and the version-0_9_x branch).

--------------------

Estimated hours taken: 10

Fix a performance problem reported by Tom Conway,
that caused the compiler to take forever when compiling
very simple test cases making use of user-defined insts.

compiler/inst_match.m:
compiler/inst_util.m:
	In the implementation of the procedures that traverse insts, e.g.
	inst_matches_initial, inst_matches_final, inst_is_ground, etc., ensure
	that we thread the set of already processed inst names through the
	code, i.e. pass it both in and out, rather than just passing it in.
	This ensures that we don't traverse the same inst name more than once
	for each call to one of those top-level procedures.
	The previous algorithm lead to an exponential performance
	blow-out.

	Also change mode_list_contains_inst_var so that it does not
	expand modes or defined_insts, but instead just returns the
	inst_vars that the mode list contains directly.

tests/valid/Mmakefile:
tests/valid/inst_perf_bug_1.m:
tests/valid/inst_perf_bug_2.m:
	Add a couple of regression tests, one for the performance bug
	that this change fixes, one for a similar performance bug that
	still remains even after this change.  For now only the first
	one is enabled.

cvs diff -N tests/valid/Mmakefile tests/valid/inst_perf_bug_1.m tests/valid/inst_perf_bug_2.m
Index: tests/valid/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/valid/Mmakefile,v
retrieving revision 1.56
diff -u -d -r1.56 Mmakefile
--- tests/valid/Mmakefile	2000/02/22 08:59:58	1.56
+++ tests/valid/Mmakefile	2000/02/22 10:36:45
@@ -62,6 +62,7 @@
 	indexing.m \
 	inhibit_warn_test.m \
 	inlining_bug.m \
+	inst_perf_bug_1.m \
 	int64.m \
 	intermod_impure.m \
 	intermod_lambda.m \
@@ -139,6 +140,7 @@
 #	assoc_list.m
 #	determinism.m
 #	mode_merge_insts.m
+#	inst_perf_bug_2.m
 
 
 # Base grades `jump' and `fast'
Index: tests/valid/inst_perf_bug_1.m
===================================================================
RCS file: inst_perf_bug_1.m
diff -N inst_perf_bug_1.m
--- /dev/null	Wed May  6 06:32:27 1998
+++ inst_perf_bug_1.m	Tue Feb 22 21:10:02 2000
@@ -0,0 +1,47 @@
+:- module inst_perf_bug_1.
+:- interface.
+
+:- type t1 ---> f(t2, t2) ; g(t2, t2).
+:- inst t1 ---> f(t2, t2) ; g(t2, t2).
+
+:- type t2 ---> f(t3, t3) ; g(t3, t3).
+:- inst t2 ---> f(t3, t3) ; g(t3, t3).
+
+:- type t3 ---> f(t4, t4) ; g(t4, t4).
+:- inst t3 ---> f(t4, t4) ; g(t4, t4).
+
+:- type t4 ---> f(t5, t5) ; g(t5, t5).
+:- inst t4 ---> f(t5, t5) ; g(t5, t5).
+
+:- type t5 ---> f(t6, t6) ; g(t6, t6).
+:- inst t5 ---> f(t6, t6) ; g(t6, t6).
+
+:- type t6 ---> f(t7, t7) ; g(t7, t7).
+:- inst t6 ---> f(t7, t7) ; g(t7, t7).
+
+:- type t7 ---> f(t8, t8) ; g(t8, t8).
+:- inst t7 ---> f(t8, t8) ; g(t8, t8).
+
+:- type t8 ---> f(t9, t9) ; g(t9, t9).
+:- inst t8 ---> f(t9, t9) ; g(t9, t9).
+
+:- type t9 ---> f(t10, t10) ; g(t10, t10).
+:- inst t9 ---> f(t10, t10) ; g(t10, t10).
+
+:- type t10 ---> f(t11, t11) ; g(t11, t11).
+:- inst t10 ---> f(t11, t11) ; g(t11, t11).
+
+:- type t11 ---> f(t12, t12) ; g(t12, t12).
+:- inst t11 ---> f(t12, t12) ; g(t12, t12).
+
+:- type t12 ---> f(t13, t13) ; g(t13, t13).
+:- inst t12 ---> f(t13, t13) ; g(t13, t13).
+
+:- type t13 ---> f ; g ; h.
+:- inst t13 ---> f ; g.
+
+:- pred p(t1::in(t1)) is det.
+
+:- implementation.
+
+:- external(p/1).
Index: tests/valid/inst_perf_bug_2.m
===================================================================
RCS file: inst_perf_bug_2.m
diff -N inst_perf_bug_2.m
--- /dev/null	Wed May  6 06:32:27 1998
+++ inst_perf_bug_2.m	Tue Feb 22 21:12:14 2000
@@ -0,0 +1,48 @@
+:- module inst_perf_bug_2.
+:- interface.
+
+:- type t1 ---> f(t2, t2) ; g(t2, t2).
+:- inst t1 ---> f(t2, t2) ; g(t2, t2).
+
+:- type t2 ---> f(t3, t3) ; g(t3, t3).
+:- inst t2 ---> f(t3, t3) ; g(t3, t3).
+
+:- type t3 ---> f(t4, t4) ; g(t4, t4).
+:- inst t3 ---> f(t4, t4) ; g(t4, t4).
+
+:- type t4 ---> f(t5, t5) ; g(t5, t5).
+:- inst t4 ---> f(t5, t5) ; g(t5, t5).
+
+:- type t5 ---> f(t6, t6) ; g(t6, t6).
+:- inst t5 ---> f(t6, t6) ; g(t6, t6).
+
+:- type t6 ---> f(t7, t7) ; g(t7, t7).
+:- inst t6 ---> f(t7, t7) ; g(t7, t7).
+
+:- type t7 ---> f(t8, t8) ; g(t8, t8).
+:- inst t7 ---> f(t8, t8) ; g(t8, t8).
+
+:- type t8 ---> f(t9, t9) ; g(t9, t9).
+:- inst t8 ---> f(t9, t9) ; g(t9, t9).
+
+:- type t9 ---> f(t10, t10) ; g(t10, t10).
+:- inst t9 ---> f(t10, t10) ; g(t10, t10).
+
+:- type t10 ---> f(t11, t11) ; g(t11, t11).
+:- inst t10 ---> f(t11, t11) ; g(t11, t11).
+
+:- type t11 ---> f(t12, t12) ; g(t12, t12).
+:- inst t11 ---> f(t12, t12) ; g(t12, t12).
+
+:- type t12 ---> f(t13, t13) ; g(t13, t13).
+:- inst t12 ---> f(t13, t13) ; g(t13, t13).
+
+:- type t13 ---> f ; g ; h.
+:- inst t13 ---> f ; g.
+
+:- pred p(t1::in(t1), t1::out(t1)) is det.
+
+:- implementation.
+
+p(f(X, Y), f(Y, X)).
+p(g(X, Y), g(Y, X)).
-- 
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.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------