#6 CLIPS optimization: a fact index was looked up by walking the whole fact list

[Batch Job 1]

A fact index was looked up by walking the whole fact list

What was slow. FindIndexedFact in clips_core_source_642/core/factmngr.c started at the first fact and compared indices until it matched or the list ran out:

   for (theFact = GetNextFact(theEnv,NULL);
        theFact != NULL;
        theFact = GetNextFact(theEnv,theFact))
     {
      if (theFact->factIndex == factIndexSought)
        { return(theFact); }
     }

It is reached by retract, fact-existp, fact-relation, fact-slot-value and the other fact-access functions given an index rather than an address, from argacces.c, factfun.c and factcom.c.

So the cost of reaching a fact grew with how far into the list it was, and the cost of an index that is not there was a walk of the whole list. The newest fact — which (modify N), (duplicate N) and reading back a fact just asserted all name — was the furthest away.

What was measured. Two thousand reads of one slot of the newest fact:

facts held	before	after
500	0.0033 s	0.00011 s
4000	0.0235 s	0.00010 s

The column on the left grows with the number of facts. The column on the right does not: the same two thousand reads cost the same whether five hundred facts are held or four thousand. At four thousand facts that is two hundred and twenty times faster.

Retracting by ascending index was already fast and stays so — each retraction takes the fact at the head — and retracting by descending index was the slow direction and is now the fast one.

The change. The walk starts at whichever end of the list is nearer and stops as soon as it passes the index sought. An index outside the two ends is answered without any walk, and an index at either end in one step.

   if (factIndexSought < firstFact->factIndex) return NULL;
   if (factIndexSought > lastFact->factIndex) return NULL;

   if ((factIndexSought - firstFact->factIndex) <=
       (lastFact->factIndex - factIndexSought))
     { … walk forward from firstFact, stopping when the index passes … }

   … otherwise walk backward from lastFact, stopping when the index passes …

What it rests on. Three things CLIPS already maintains, rather than anything new:

The fact list ascends by index. A fact asserted with a fresh index goes after LastFact, which holds the highest one. A fact asserted with an index it is reusing goes back to the position the previous fact held — that is what the factListPosition argument of AssertDriver is for, and why (modify 1 …) leaves fact 1 at the head of (facts) rather than moving it to the end.

Both ends are kept. FactData(theEnv)->FactList and ->LastFact are maintained by the same code that links and unlinks.

Nothing reachable through the list is garbage. RetractDriver unlinks the fact from FactList before marking it garbage, so the garbage test inside GetNextFact cannot fire during a walk of the list, and a walk in either direction visits the same facts.

The two subtractions are inside long long because the tests above them have already established that the index sought lies between the two ends.

The answers are the same answers. tests/lookup-by-index.clp gives output identical to unmodified 6.4.2, line for line.

What it covers: the indices themselves and the order of the fact list, before and after a modify that reuses an index and a duplicate that allocates one; reading a slot by index at the front, the back and the middle, and a multislot; fact-relation and fact-existp by index; an index below the first, above the last, a long way above the last, and negative, all of which must be refused without finding anything; both ends of the integer type, which argument checking refuses before the lookup is reached and which therefore raise ARGACCES2; two retractions that leave gaps, with lookups either side of a gap, at the newest and at the oldest; and two hundred facts retracted by index oldest first and another two hundred newest first, so both walk directions are exercised.