I was just reviewing a half dozen papers on solvers and proof engines this
week.
I believe exhaustive solvers need all cross products. In one of the papers
it proposed an incremental approach to validating a knowledgebase of rules
and facts. If I remember correctly, it used backward chaining techniques to
progressively execute queries.
peter
On 12/15/06, Mark Proctor <[EMAIL PROTECTED]> wrote:
Peter,
do you know if t he behaviour of a solver results in unused cross
products? i.e. you know how in Rete it will attempt to join all cross
products, but only 1 or a few of those join attempts might be executed -
which is what leaps takes advantage of. Do solvers benefit from that, or do
they need all cross products?
Mark
Peter Van Weert wrote:
I checked with Jon, and he has been tweaking the Jess program and has
now timings of 10-30 times slower. I must admit that JCHR does not
perform that well on this particular benchmark, since my join orderer is
not that good yet. Also, I must admit 10-30 is better then I was
anticipating, so I might have to some more tests later (but, as I said
before, the RETE-Leaps thing doesn't matter that much here, so that is
probably an important factor).
Obvious things, well:
- we do not use RETE, but something that is closer to Leaps (i.e. only
make those joins you need). There is the claim Leaps is asymptotically
better then RETE, but I must admit I have never seen it proved.
- we compile to host-language code (for JCHR this is Java), whereas (I
think) most rule engines are more interpreters. The generated code will
be quite specialized towards the particular rule it is part of, the join
that has to be made, etc.
- we use high performance hash indexes to do the lookups, but I guess
everyone does that
- we perform quite some static analysis. Many of them are tuned to our
operational semantics and would not apply to Drools
There are many papers and at least two PhD theses were written
entirely over the compilation of CHR. Most can be found online.
Basically, we sacrifice flexibility (no runtime addition of rules,
limited conflict resolution, ...) for speed. The core language is really
fast now after several years of optimizing the compilers. Since CHR is
originally designed to specify constraint solvers, this has always been
an important factor. Lately CHR is becoming more and more (ab)used as a
general purpose language, and we are looking into adding things like
negation as absence, aggregates and flexible rule priorities, but this
is still in a very early stage.
Cheers,
Peter
Mark Proctor wrote:
Interesting that you say its 30-100 times slower, I don't believe we
would be much faster than jess - I'm now very intrigued to look at the
JCHR engine :) with local search leaps wouldn't help as you want to know
all cross products as part of the query. I should have some time early
next year to look over this - are there any obvious things you can say
now? Btw I have taken this conversation to the dev mailing list.
Mark
Peter Van Weert wrote:
Mark Proctor wrote:
Peter,
I believe it is possible to do full prolog style backward chaining,
integrated with standard rules - see
http://wiki.jboss.org/wiki/Wiki.jsp?page=BackwardChaining.
Of course it is possible. Almost every major Prolog distribution (SWI,
XSB, B-Prolog, SICStus 4, YAP, hProlog) includes a port of our CHR
system. These seemingly combine Prolog's backward chaining with CHR's
forward chaining.
I agree that what you are describing on the above wiki page seems to be
a form of backward chaining, something I cannot always say about the
backwards chaining features of other rule engines (Clips, Jess, ...).
I'm interested to see what you mean about performance, with tuning there
should be no reason for our system to be less performant. See email on
dev. I'm willing to apply anything to core that will make this possible.
Geoff when running your examples set the following settings "-Xmx512M
-Xms512M -server", I also believe there is a setting for more
aggressive OO optimisations.
Maybe I should check again. The last time I compared with Drools, it
was
still called Drools. We recently did a comparison Jess versus
CHR(hProlog) though, and Jess turned out to be between 30-100 times
slower. This was for one of our benchmarks where the RETE versus Leaps
thing would not even be much of an issue. I suspect that for many other
benchmarks RETE will perform far worse.
Now, let's read the mail on dev. Well, the thing is, if you can still
make improvements of 50%, I think you are not yet there where we are
with CHR. It is becoming more and more difficult to gain more then a few
percents with our highly optimizing compilers (not talking about JCHR
here, because I don't have all optimizations yet). But maybe yes, once
you do more aggressive optimizations and analysis, things could converge.
What's this 'traveling tournament lvl10 use case'? If it is not to big
of a program, I am very interested to port it and see how (J)CHR
performs on it...
Would be truly great if we can work together on a unified system - see
http://markproctor.blogspot.com/2006/11/declarative-behavioural-modelling-dbm.html
Of to bed as I'm shattered, I'll email tomorrow about getting together
online.
Mark
CHeeRs,
Peter
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
---------------------------------------------------------------------
To unsubscribe from this list please visit:
http://xircles.codehaus.org/manage_email
