#4 Matching performance is too slow to be usable.
Graph matching seems to be extremely slow. I've added
some performance tests for matching to the
TestPerformance/GraphPerformance tests in the branches
area (revision 39). The new tests consist of a toy
knowledgeBase of a few simple statements and a series
of query graphs which each contains one of these
statements.
// A boy ate cake.
// [boy] <- (Agent) <- [ate] -> (Theme) -> [cake]
//
// A boy ate ice cream.
// [boy] <- (Agent) <- [ate] -> (Theme) -> [cream]
-> (Attr) -> [ice]
//
// A boy and a girl ate ice cream.
// [boy] <- (Agent) <- [ate] -> (Theme) -> [cream]
-> (Attr) -> [ice]
// [girl] <- (Agent) <-
//
// A boy and a girl played a game.
// [boy] <- (Agent) <- [played] -> (Theme) -> [game]
// [girl] <- (Agent) <-
//
// The cat chased a mouse.
// [cat] <- (Agent) <- [chased] -> (Theme) -> [mouse]
The queries are performed in the order in which the
sentences are listed. Performance numbers that I have
observed:
Match test 01: 270 clock cycles or 0.00027 seconds
Match test 02: 3010000 clock cycles or 3.01 seconds
Match test 03: 334780000 clock cycles or 334.78 seconds
Match test 04: 4610000 clock cycles or 4.61 seconds
Match test 05: 80000 clock cycles or 0.08 seconds
These numbers are for ONE instance of a match test.
For such a small toy, I would argue that only test 01
is acceptable. Test 03 is obviously extremely
disappointing.
I suspect that some of the performance issues are
likely to be related to a fix to a previous bug
(#1509444) that I committed. This fix involves
enabling backtracking. It is suspicious that the worst
performant matches are those that involve the most
repeat graph nodes. Also revealing, is that test 05 is
second in performance only to test 01. Test 05 only
has the Agent and Theme relations which are repeat nodes.
