#7 CLIPS optimization: retracting a fact hashed it a second time

[Batch Job 1]

Retracting a fact hashed it a second time

What was slow. RemoveHashedFact in clips_core_source_642/core/facthsh.c found the bucket to take the fact out of by hashing the fact again:

   hashValue = HashFact(theFact);
   hashValue = (hashValue % FactData(theEnv)->FactHashTableSize);

HashFact walks the deftemplate name and then every field of every slot, and a multislot is walked field by field through HashMultifield. The assertion that put the fact in the table had already done that walk, and had already saved the answer: HashFact's last act is theFact->hashValue = (unsigned long) count;.

So every retraction repeated the whole of the work its own assertion had done, and the wider the fact's slots the more there was to repeat.

What was measured. Two thousand facts of a sixty-field multislot, asserted and then retracted, five times over, timing the retractions alone:

	time
hashing the fact again	0.0223 s
reading the stored value	0.0148 s

A third of the time of the retractions went on recomputing a number the fact was already carrying.

The change. The bucket comes from the stored value.

   hashValue = (size_t) theFact->hashValue;
   hashValue = (hashValue % FactData(theEnv)->FactHashTableSize);

What it rests on. That the stored value agrees with the fact's contents is not an assumption this introduces. ResizeFactHashTable, ninety lines further down the same file, relocates every entry in the table by exactly that value:

          newLocation = theEntry->theFact->hashValue % newSize;

If the stored value could disagree with the fact, a resize would already put entries in buckets where nothing would find them. So the invariant is one the hash table depends on throughout, and using it for removal as well as for relocation is consistent rather than new.

The ordering that keeps it true is in RetractDriver, which calls RemoveHashedFact before ReplaceFact writes any new slot value. unsigned long and size_t are both eight bytes here, so the stored field holds the whole of what HashFact returned.

The answers are the same answers. tests/duplicates-across-retraction.clp gives output identical to unmodified 6.4.2, line for line.

What the hash decides is whether an assert is a duplicate, so that is what the tests ask. A retraction that chose the wrong bucket would leave the entry behind, and the next assert of the same fact would then be let through as something new — which is what a wrong bucket would look like from the outside, and what every case here would catch.

It covers: a sixteen-field multislot asserted twice, retracted, and asserted twice again; two hundred rounds of assert, assert again, retract, counting both the duplicates recognised and the facts left behind; a thousand distinct facts through four stages of assert, retract, assert and assert again; a modify, which retracts and re-asserts under the same index, after which the modified value must be recognised as a duplicate and the value it held before must be accepted as new; and an ordered fact, where the whole of the fact is one multifield slot and HashMultifield recurses into it.