From jan@swi.psy.uva.nl  Tue Jan  2 21:12:17 2001
Received: from gollem.swi.psy.uva.nl (gollem [145.18.152.30])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id VAA24290;
	Tue, 2 Jan 2001 21:12:16 +0100 (MET)
Received: (from jan@localhost)
	by gollem.swi.psy.uva.nl (8.9.3/8.9.3/SuSE Linux 8.9.3-0.1) id VAA31317;
	Tue, 2 Jan 2001 21:12:54 +0100
Date: Tue, 2 Jan 2001 21:12:54 +0100
Message-Id: <200101022012.VAA31317@gollem.swi.psy.uva.nl>
From: Jan Wielemaker <jan@swi.psy.uva.nl>
Subject: Re: performance of index/1 'd calls
To: Lourens van der Meij <lourens@cs.vu.nl>
In-Reply-To: Lourens van der Meij's message of Mon, 1 Jan 2001 11:12:02 +0100 (CET)
Phone: +31 - 20 - 525 6121
Cc: prolog@gollem.swi.psy.uva.nl

> I tried to replace my own simple multi-indexing lookup based on explicit
> hashing on the combination of all index parameters by the built-in 
> index/1 feature in SWI-Prolog. 
> 
> In my program performance got worse.
> 
> I just wrote a simple test: Indeed multi-indexing does offer constant time
> lookup if all indexed arguments are ground as I would like.

Actually only one or more of the indexed arguments needs to be provided.

> But multi indexed lookup in the test seems to be 50 times slower than
> non multi indexed lookup.

There is a little bug in your program that causes the 1-st argument
indexed version to fail (argument order in the assert).  With this fixed
the difference is still 10 times.

> 
> See the test below.
> 
> Could you comment please?

[ The test accesses a predicate mapping random integers to 11, 2000 clauses.
  The `indexed' version is indexed on both arguments
]

So, what happens?  How does SWI-Prolog select the (first) clause?  If no
:- index directive is given, the system decides at the first call whether
to do no indexing, `key-based' (see below) or hashed indexing.  If the
predicate is dynamic it will reconsider when the predicate reaches 25
clauses.  Using an :- index directive it will always do `key-based'.

If it looks for the first clause, it also looks for the next.  If none
is found the goal is deterministic, otherwise the other clause is
registered in the choice-point.

Using hashed access, the system deduces the hash-key from the 1-st arg
of the goal and does a hash-lookup that will generally return a very
short list of candicate clauses.

Using key-based indexing, the system deduces a key and a mask from the
goal and each clause has been assigned a key and mask (the mask maskes
variables at the specified location).  A simple masking and compare
operation tells the system that a clause is a candidate for unification
or not.

As said, the system also looks for the next clause and here is the pain.
there is no next clause in your case, but it will only find out after
searching the entire clauselist.

For short, a 1-st argument hashed predicate has more or less constant
low time selecting a clause (rehashing is performed automatically if
the table becomes too populated).  Key-based indexing is relatively
fast, but degrades linear with the number of clauses.  Not indexed
at all is slow in selecting the next clause, but the first clause
is relatively fast as the scan for the next clause simply succeeds
if this is not the last clause of the predicate.

	Regards --- Jan

