Greetings. I've been doing some performance optimisations on LISA
(http://lisa.sourceforge.net) and could use some advice.
First, some background. To get a rough idea of performance vis-a-vis
similar implementations, I've run versions of the "monkey and bananas"
planning problem on LISA, Xanalys' KnowledgeWorks and JESS. LISA
actually does quite well against KnowledgeWorks, with execution times
within a few tens of seconds on a 1000-iteration test (LISA being the
slower). I'm pleased with this initial result, but would like to improve
things; LISA is still alpha software and there are many upcoming
features.
Before the comparison with KW, I did some profiling and adressed a
number of bottlenecks; I am now considering aspects of LISA's
architecture itself. LISA makes extensive use of CLOS, particularly
within the Rete network. Each node is implemented as a class, slot
access is via methods, network traversal is via methods, etc. In my
travels I have read that structs "might be" a more efficient choice over
classes (sometimes). In the case of LISA, I am considering replacing the
Rete node classes with structs; however, it is not clear to me how much
of a "win" (if any) this would be. It seems the only potential
bottleneck structs would adress would be slot access; generic functions
would still form the core LISA architecture, so that "overhead" would
still exist. Hmm; and perhaps struct instance creation would also be
more efficient? LISA creates a lot of instances as facts are asserted
and run through the network.
In any event, I could use some help. Converting the Rete nodes to
structs is a significant undertaking; I don't want to proceed unless the
payoff is worth the effort. I am aware that there are many performance
variables that can affect production-rule systems, and that the MAB
might not be a true reflection of "real-world" rulebases. However, it's
all I have right now; and, perhaps I can address some commonly-known
issues that would improve LISA's performance regardless.
Incidentally, JESS on the IBM Java VM (Redhat Linux) is consistently
four times faster than LISA and KW. However, JESS "cheats", in a manner
of speaking, by making many critical member variables "package visible"
and avoiding the overhead of Java method calls. LISA doesn't (can't?) do
this.
I appreciate your time and advice.
Regards,
--
-----------------------------------------------------------------
David E. Young
Fujitsu Network Communications (defun real-language? (lang)
(········@computer.org) (eq lang 'LISP))
"But all the world understands my language."
-- Franz Joseph Haydn (1732-1809)
In article <·················@nc.rr.com>, ·······@nc.rr.com wrote:
>Greetings. I've been doing some performance optimisations on LISA
>(http://lisa.sourceforge.net) and could use some advice.
i checked out your work when you first announced its existence and
was mighty impressed. keep up the good work!
>In my
>travels I have read that structs "might be" a more efficient choice over
>classes (sometimes). In the case of LISA, I am considering replacing the
>Rete node classes with structs; however, it is not clear to me how much
>of a "win" (if any) this would be. It seems the only potential
>bottleneck structs would adress would be slot access; generic functions
>would still form the core LISA architecture, so that "overhead" would
>still exist. Hmm; and perhaps struct instance creation would also be
>more efficient? LISA creates a lot of instances as facts are asserted
>and run through the network.
some thoughts:
(1) why bother making this optimization now? it trades flexibility
for speed. why not defer making this trade until performance becomes
unacceptable. you might find uses for the flexibility of classes in
the meantime...
(2) read rob doorenbos's dissertation on efficiently implementing the
rete algorithm (http://www.cs.cmu.edu/People/clamen/reports/1995.html).
this implementation has scaled to tens of thousands of rules (perhaps
even hundreds of thousands) on single workstations circa the mid 1990s.
(3) one way to avoid the hit of instance creation is to cache instances
of tokens that were once part of the network but have been expunged.
when such tokens are needed again, dip into your cache first before
incurring the expense of creating new ones from scratch. caveat: i
don't know how maintaining private resources like this messes with the
assumptions and performance of lisp's gc. when i tried this optimization
in my own system, i only saw performance improvements of 10% or so. i
decided this wasn't worth the complication of the code, and removed it
a bit later.
>In any event, I could use some help. Converting the Rete nodes to
>structs is a significant undertaking; I don't want to proceed unless the
>payoff is worth the effort.
(by the way, by "rete node", you mean "token", right? the nodes are
relatively permanent; it's the tokens that wax and wane and generally
drive overall performance.)
>I am aware that there are many performance
>variables that can affect production-rule systems, and that the MAB
>might not be a true reflection of "real-world" rulebases. However, it's
>all I have right now; and, perhaps I can address some commonly-known
>issues that would improve LISA's performance regardless.
again, look at doorenbos's dissertation for performance hints. my
own experience is that when you scale to large production systems,
new bottlenecks will appear. the main performance factor is the
number of tokens in the network, which (generally) increases with
the number of production rules and especially with the amount of
variable binding being done (and undone). the MAB model is not
very taxing in this regard.
>I appreciate your time and advice.
no problem. i (for one) am quite interested in your project.
sashank varma
From: David E. Young
Subject: Re: Optimisations and classes vs. structs
Date:
Message-ID: <3AC3518F.700EA523@nc.rr.com>
Sashank Varma wrote:
> In article <·················@nc.rr.com>, ·······@nc.rr.com wrote:
>
> >Greetings. I've been doing some performance optimisations on LISA
> >(http://lisa.sourceforge.net) and could use some advice.
>
> i checked out your work when you first announced its existence and
> was mighty impressed. keep up the good work!
>
Hello Sashank; I appreciate that encouragement very much.
> some thoughts:
>
> (1) why bother making this optimization now?
This is actually a fine point. My motivation is to correct any fundamental
inefficiencies in the architecture now, while LISA is still relatively
small. I certainly want to maintain flexibility; one important goal of the
project is to build a CLOS implementation of RETE, and I don't want to vary
from that goal.
I actually did a small experiment yesterday, reimplementing as a struct the
class used for join-node memories. On a 500-iteration run LISA's performance
improved about ten seconds. I'm now considering limiting any changes to the
class that implements FACT (and perhaps TOKEN), since slot accesses to these
instances occur quite frequently during pattern matching.
>
> (2) read rob doorenbos's dissertation on efficiently implementing the
> rete algorithm (http://www.cs.cmu.edu/People/clamen/reports/1995.html).
> this implementation has scaled to tens of thousands of rules (perhaps
> even hundreds of thousands) on single workstations circa the mid 1990s.
>
This is great information! Thanks very much.
>
> (3) one way to avoid the hit of instance creation is to cache instances
> of tokens that were once part of the network but have been expunged...
I thought about this, but as you mention it isn't clear how much of a "win"
it would be. And, it would add complexity perhaps needlessly and violate
another project goal (simplicity wherever possible).
>
> (by the way, by "rete node", you mean "token", right? the nodes are
> relatively permanent; it's the tokens that wax and wane and generally
> drive overall performance.)
>
Apologies; yes, you're correct. Indeed, reading your comment just clarified
something for me. The Rete nodes probably aren't worth changing because they
are less influential on performance than FACTs and TOKENs.
>
> no problem. i (for one) am quite interested in your project.
>
Thanks very much for your time; you've been most helpful. LISA is a very
interesting project (for myself at least), and it's teaching me quite a bit.
Regards,
--
-----------------------------------------------------------------
David E. Young
Fujitsu Network Communications (defun real-language? (lang)
(········@computer.org) (eq lang 'LISP))
"But all the world understands my language."
-- Franz Joseph Haydn (1732-1809)
On Tue, 27 Mar 2001 15:59:07 GMT, "David E. Young" <·······@nc.rr.com>
wrote:
> Greetings. I've been doing some performance optimisations on LISA
> (http://lisa.sourceforge.net) and could use some advice.
[...]
> architecture itself. LISA makes extensive use of CLOS, particularly
The EncyCMUCLopedia includes some documents on the performance of PCL with
CMU CL. Don't bother downloading it, I will upload a new version--with more
documents on this topic--in a couple of days. However, since LISA is
intended to be portable, at this early stage of development you may not
want to deal with system-dependent optimizations yet.
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/