[rules-dev] Loop detection

[Michael Neale]

For those that are interested, I thought I would try a variation on
the "tortoise and hare" algorithm to detect cycles in rule firing
patterns in order to "guess" that a infinite loop was happening and
stop it (that would work reasonably well for common cases). I was able
to use a version of it (I call it the "crippled tortoise") - and it
seems to work nicely.

The gist of it is to let the rules spin for a while, after N number of
firings, track another N (ie record the names of rules that fire for N
firings). Then run the cycle detector, see if it ends up with a cycle
- compare the cycle length ( divided by the number of rules in cycle)
with Y and then you have a pretty good idea that a loop is happening
(unless its a fib style recursion, perhaps). I have trouble guessing
what N and Y should be (Y needs to be < N) - I wasn't sure if as the
number of rules increase means that a larger sample is needed to
detect for cycles (as we don't want a false positive).

It seems to work well - certainly an opt in thing - I built it in to
the new execution server code to try it out, as it is an ideal place
you would want some protection like this (to stop wasting CPUs/threads
!).

Just thought people would be interested, and perhaps some have other
ideas (as there are lots of things we can mix in to help with this). I
also looked at using the LeftTuple hashcode, which is fine but only
tracks "key" field changes (so you can see the same hashcode over and
over even though the data is changing), so its not really perfect
either.

-- 
Michael D Neale
home: www.michaelneale.net
blog: michaelneale.blogspot.com