[rules-dev] Loop detection

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