Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC830713); site edai.UUCP
Path: utzoo!watmath!clyde!floyd!vax135!ukc!edcaad!edee!edai!ok
From: ok@edai.UUCP (Richard O'Keefe)
Newsgroups: net.lang.prolog
Subject: Why I think partitions are faster than tagging.
Message-ID: <4096@edai.UUCP>
Date: Sat, 31-Mar-84 17:18:13 EST
Article-I.D.: edai.4096
Posted: Sat Mar 31 17:18:13 1984
Date-Received: Fri, 30-Mar-84 02:37:27 EST
Organization: Art.Intelligence,Edin.Univ.
Lines: 28


     I've been asked to justify my contention that Prolog interpreters
using tags are likely to be slower than Prolog interpreters which like
C-Prolog use a few partitions for their type tests.  C Prolog in fact
can do almost all its type testing by comparing against two boundaries
(which can be kept in registers a lot of the time) and against 0.

     The basis of my claim is that I've looked at the code produced by
the C compiler in both kinds of interpreters, and I've tried to hand-
code unification routines in assembler.  There is a very important loop
that crops up all over the place in a Prolog interpreter:

	a = <a pointer>;
	while (a <is a bound reference>) a = <contents of a>;

This is generally followed by a switch with

	case <a is unbound> : ...
	case <a is atomic>  : ...
	case <a is compound>:

which takes two comparisons or their equivalent in either case.
I can get this loop down to 4 instructions using C-Prolog's data
representation, but with *byte* tags I can only get it down to
5 whichever end I put the tag.  The VAX code is 11 bytes -vs- 19.
The number of instructions would be the same on an M68000.

     Of course the skill of the programmar is a greater factor.