#18 Inefficient interpattern tests

[Aneil Mallavarapu]

Hi Dave,

I've noticed a severe slow-down when a network processes an interpattern test involving large number of objects. It seems the problem lies in the functions test-against-left-memory and test-against-right-memory. Interpattern bindings such as in
(defrule r1 () (x (a ?v)) (y (b ?v)) => ...)
do not take advantage of a hash-based optimization whereby a matching token for ?v in the left memory is found by a hash-lookup based on that value in the right memory.

This can be seen by modifying make-inter-pattern-test with some tracing code (in attached file), then evaling this:

(defclass x () (a))
(defclass y () (b))
(clear)
(reset)
(defrule xdet () (x (a ?a)) (y (b ?a)) => (format t "HELLO: ~S~%" ?a))
;; add 3 x instances:
(assert (x (a 1)))
(assert (x (a 2)))
(assert (x (a 3)))
;; add 4 y instances:
(assert (y (b 1)))
(assert (y (b 2)))
(assert (y (b 3)))
(assert (y (b 4)))

This results in 3*4 = 12 EQUAL tests being run. In principle, this could be cut down to 3+4=7 hash lookups. Not a big difference when we have a small set of objects like this, but I'm building systems which require tests between 10s of thousands of right and left memory elements, so this ends up being a difference between 10s of thousands of hash lookups compared to 100s of millions of equal tests.

I spelunked the code a bit and couldn't really see how to implement a hash-based lookup given the current data structures. Do you have an idea whether this is possible?

[Aneil Mallavarapu]

traces calls to the inter-pattern-test function

[Aneil Mallavarapu]

Contains a patch which implements efficient inter-pattern-tests

[Aneil Mallavarapu]

Logged In: YES
user_id=870521
Originator: YES

I've created a patch that fixes this problem (attached). I've tested it with the monkeys and bananas example (misc/mab.lisp). The behavior and the (WATCH :ALL) traces are identical.

In a simple test where 1000 instances are matched to each other:

(in-package :lisa-user)

(defclass x () ((a :initarg :a)))
(defclass y () ((b :initarg :b)))
(defrule match () (x (a ?v)) (y (b ?v)) => (format t "+"))
(defun test (n)
"Times the matching of n instances"
(reset)
(dotimes (i n)
(assert-instance (make-instance 'x :a i))
(assert-instance (make-instance 'y :b i)))
(run))

(TEST N) computes performs an inter-pattern slot match across 1000 instances of 2 classes. LISA RELEASE_3_2 takes 8.36 seconds; the patch drops this down to .734 seconds. The attached zip file contains a graph which compares performance as N is varied.

The patch contains a new file: src/rete/reference/inter-pattern-test.lisp and changes to lisa.asd, join-node.lisp, node-tests.lisp and node2.lisp.

I've also attached dribbles of the mab.lisp output.

File Added: lisa-with-inter-pattern-filter.zip