So, after a fairly long haul, I'm satisfied that the program I'm
working on does the right thing. However, it does the right thing very
slowly. This isn't unexpected, because I wasn't trying hard to make it
go fast as I wrote it. However, now that I have it working, I really do
need it to be quite a bit faster than it is.
I've been profiling it (using SBCL's built-in exact profiler) and
trying to figure out how to speed up the slow parts. I know that
declaring types of variables and functions can really speed things up,
so I've been trying to figure out the way to do them properly. If my
shaky understanding of the profiler's output is correct, I'm boxing and
unboxing a lot of double-floats, and I'd like to not be doing that.
However:
1) I find that a lot of the time, when I'm done declaring types, my
code *looks* really ugly. Maybe that's unavoidable, but maybe it isn't.
I don't know.
2) I don't understand how declarations interact with CLOS/generic
functions. For instance, if I add the :type keyword to a slot
definition, does that do anything? I'd just declaim types for my
accessors, but I can't really figure out what's up with declamations of
generic functions. If I declaim the function type somewhere, and add a
method (for an entirely unrelated class---one's a standard-class and
the other's a condition) the declamation seems to be overridden
entirely.
I've tried reading the CLHS sections on types and classes, but haven't
found it terribly helpful---I may just be dense. The other books I've
looked at (mostly PCL and PAIP) don't spend much time talking about
declarations. If anyone has any pointers, I'd be very grateful.
Thanks,
Matt
Pillsy wrote:
> So, after a fairly long haul, I'm satisfied that the program I'm
> working on does the right thing. However, it does the right thing very
> slowly. This isn't unexpected, because I wasn't trying hard to make it
> go fast as I wrote it. However, now that I have it working, I really do
> need it to be quite a bit faster than it is.
>
> I've been profiling it (using SBCL's built-in exact profiler) and
> trying to figure out how to speed up the slow parts. I know that
> declaring types of variables and functions can really speed things up,
The most dangerous gun in the world is one you know to be unloaded.
Maybe you said this elsewhere, but unless this is an intensive numerical
algorithm your problem may lie elsewhere. Such as in the algorithm
itself. I am especially suspicious because you mention CLOS, not usually
central to intensive numerics.
Is the code short and shareable enough to, well, share?
> 2) I don't understand how declarations interact with CLOS/generic
> functions. For instance, if I add the :type keyword to a slot
> definition, does that do anything?
Not necessarily. Impleementation-dependent.
> I've tried reading the CLHS sections on types and classes, but haven't
> found it terribly helpful---I may just be dense. The other books I've
> looked at (mostly PCL and PAIP) don't spend much time talking about
> declarations. If anyone has any pointers, I'd be very grateful.
Start over on this thread. Change the subject to "Lisp Sucks! Molasses
is faster!!" and post the code and some timings and the whole community
will be working for you for free.
hth, kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> Pillsy wrote:
> > So, after a fairly long haul, I'm satisfied that the program I'm
> > working on does the right thing. However, it does the right thing very
> > slowly. This isn't unexpected, because I wasn't trying hard to make it
> > go fast as I wrote it. However, now that I have it working, I really do
> > need it to be quite a bit faster than it is.
> > I've been profiling it (using SBCL's built-in exact profiler) and
> > trying to figure out how to speed up the slow parts. I know that
> > declaring types of variables and functions can really speed things up,
> The most dangerous gun in the world is one you know to be unloaded.
> Maybe you said this elsewhere, but unless this is an intensive numerical
> algorithm your problem may lie elsewhere.
There's a lot of numerics, but that's not the slow part ATM. It's a
Monte Carlo simulation, which has a bunch of moves which it makes
randomly, and having each move be its own CLOS class was so
natural-seeming that I did it that way. AIUI, this sort of thing is
what OO was invented for....
> Such as in the algorithm itself.
I *think* the algorithm is OK, because it's a widely used one, although
it's possible I've bungled my implementation.
> Is the code short and shareable enough to, well, share?
No, it's pretty long.
[...]
> > I've tried reading the CLHS sections on types and classes, but haven't
> > found it terribly helpful---I may just be dense. The other books I've
> > looked at (mostly PCL and PAIP) don't spend much time talking about
> > declarations. If anyone has any pointers, I'd be very grateful.
> Start over on this thread. Change the subject to "Lisp Sucks! Molasses
> is faster!!" and post the code and some timings and the whole community
> will be working for you for free.
LOL.
Thanks!
Matt
Pillsy wrote:
> Ken Tilton wrote:
>
>
>>Pillsy wrote:
>
>
>>>So, after a fairly long haul, I'm satisfied that the program I'm
>>>working on does the right thing. However, it does the right thing very
>>>slowly. This isn't unexpected, because I wasn't trying hard to make it
>>>go fast as I wrote it. However, now that I have it working, I really do
>>>need it to be quite a bit faster than it is.
>
>
>>>I've been profiling it (using SBCL's built-in exact profiler) and
>>>trying to figure out how to speed up the slow parts. I know that
>>>declaring types of variables and functions can really speed things up,
>
>
>>The most dangerous gun in the world is one you know to be unloaded.
>
>
>>Maybe you said this elsewhere, but unless this is an intensive numerical
>>algorithm your problem may lie elsewhere.
>
>
> There's a lot of numerics, but that's not the slow part ATM. It's a
> Monte Carlo simulation, which has a bunch of moves which it makes
> randomly, and having each move be its own CLOS class was so
> natural-seeming that I did it that way. AIUI, this sort of thing is
> what OO was invented for....
er, um... no. OO is about managing huge wadges of code in huge systems
that will be spending most of their lives waiting on disk I/O so WTF
cares about OO overhead, we need to manage these huge codebases!!! ie,
OO is for lazy-ass mo-fos who cannot be bothered to toss of a few dozen
lines of code and reinvent "objects" in a fashion screamingly optimized
for their application.
I will be honest here, I am just a humble application programmer, and as
an American I barely know where Monte Carlo is because we only need to
know where is Las Vegas. But I will guarantee you this: you
so-ab-so-lute-ly do not want to use CLOS. That is a massively general
solution to abstraction. Your monte carlo deal needs to scream, so it
needs to abstract only what it needs to abstract. In the spirit of "make
it right before you make it fast", I believe you have passed "make it
right" and now are ready for make it fast.
Eliminate CLOS and use defstruct if necessary. eliminate GFs and use
defuns. Find Graham's (or was it Norvig?) who toss off OO in a few dozen
lines, emulate that.
>
>
>>Such as in the algorithm itself.
>
>
> I *think* the algorithm is OK, because it's a widely used one, although
> it's possible I've bungled my implementation.
Right. Was CLOS overkill? Did you need multiple inheritance and
everything else the AMOP offers? update-insatnce-for-changed-class?
anything?
This is the multi-paradigm aka big-ball-of-mud thing: Just Solve Your
Problem. One constraint on monte carlo is cycles, so your mistake was
using a too general solution (which burns cycles) in a context where
(minimizing) cycle count was a functional requirement.
bzzzzzt!
so why is this an issue with Lisp and not C++? C++ works things out at
compile time so you can get away with using it in compute-intensive
situations. Lisp lets you define a subclass before defining the
superclass. And then redefine either. While the app is running.
Different cultures, and the difference is where methinks you be stuck.
Recast what you now have without CLOS. If the code gets nasty, now you
know why we love macros (and why you need to d/l "On Lisp").
hth, kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> Pillsy wrote:
[...]
> > There's a lot of numerics, but that's not the slow part ATM. It's a
> > Monte Carlo simulation, which has a bunch of moves which it makes
> > randomly, and having each move be its own CLOS class was so
> > natural-seeming that I did it that way. AIUI, this sort of thing is
> > what OO was invented for....
> er, um... no.
Simula 67? (I'm sure it's also helpful for managing huge globs of
code.)
[...]
> But I will guarantee you this: you so-ab-so-lute-ly do not want to use CLOS.
> That is a massively general solution to abstraction.
This was a very helpful suggestion, though. Replacing one of the
defgenerics
with a defun + a typecase really sped the program's major bottlenecks
(so it's
not the major bottleneck anymore). I'm still looking for other, similar
bottlenecks
to see if the same trick will help there.
[...]
> > I *think* the algorithm is OK, because it's a widely used one, although
> > it's possible I've bungled my implementation.
> Right. Was CLOS overkill? Did you need multiple inheritance and
> everything else the AMOP offers?
Multiple inheritance and the method combinations were actually pretty
useful;
the rest not so much.
So far, replacing the defgenerics with typecases in the few places I've
done it
hasn't made things any uglier; if that changes, I can probably do
something like
the Norvig book's "case"-based OO in macros.
Thanks again for the help.
Pillsy wrote:
> Ken Tilton wrote:
> > Pillsy wrote:
> [...]
> > > There's a lot of numerics, but that's not the slow part ATM. It's a
> > > Monte Carlo simulation, which has a bunch of moves which it makes
> > > randomly, and having each move be its own CLOS class was so
> > > natural-seeming that I did it that way. AIUI, this sort of thing is
> > > what OO was invented for....
>
> > er, um... no.
>
> Simula 67? (I'm sure it's also helpful for managing huge globs of
> code.)
> [...]
> > But I will guarantee you this: you so-ab-so-lute-ly do not want to use CLOS.
> > That is a massively general solution to abstraction.
>
> This was a very helpful suggestion, though. Replacing one of the
> defgenerics
> with a defun + a typecase really sped the program's major bottlenecks
> (so it's
> not the major bottleneck anymore). I'm still looking for other, similar
> bottlenecks
> to see if the same trick will help there.
This implies that the program is doing a great number of function
calls, and that performing function calls is a significant proportion
of runtime. Generally this shouldn't be the case for a simulation
program, a large proportion of the work should preferably be in a
single routine. (This normally isn't possible for software in general
but is easier for simulation software). That said I wrote a simulation
program (in C) once that suffered this same problem.
"Pillsy" <·········@gmail.com> writes:
> 1) I find that a lot of the time, when I'm done declaring types, my
> code *looks* really ugly. Maybe that's unavoidable, but maybe it isn't.
> I don't know.
Don't declare types yourself!
Write a type inference engine for CL, and let it add the type
declarations automatically for you. ;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
Pascal Bourguignon wrote:
> "Pillsy" <·········@gmail.com> writes:
> > 1) I find that a lot of the time, when I'm done declaring types, my
> > code *looks* really ugly. Maybe that's unavoidable, but maybe it isn't.
> > I don't know.
>
> Don't declare types yourself!
>
> Write a type inference engine for CL, and let it add the type
> declarations automatically for you. ;-)
There's already an extensive and clever one inside SBCL. Declarations
in SBCL just make it work a bit better.
(message (Hello 'Pillsy)
(you :wrote :on '(9 Nov 2006 15:39:49 -0800))
(
P> 1) I find that a lot of the time, when I'm done declaring types, my
P> code *looks* really ugly. Maybe that's unavoidable, but maybe it isn't.
P> I don't know.
it appears that type inference doesn't work as well in Lisp as it works in
ML and Haskell. i suspect it's because Lisp is too dynamic, so it can do
inference only when it's able to do inlining. (however, it works much better
than in Python :).
P> 2) I don't understand how declarations interact with CLOS/generic
P> functions.
as Kenny suggests, try to eliminate CLOS/generics -- they are even more
'dynamic' than usual functions, so it's hard to optimize.
if you're not building large system with many modules and many programmers,
standard CLOS does not helps much -- you can achieve same effect with few
functions and macros.
P> For instance, if I add the :type keyword to a slot definition, does
P> that do anything?
well, it's up to you to check that :)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")