I'm working on a project in SBCL 1.0.17 on OS X 10.5.3 that requires
allocating a very large number of objects (CLOS instances, structs and
double-floats, mostly), and have been running into issues where I
exhaust the heap and get kicked into the SBCL low-level debugger. I
would like to reduce the amount of memory my program uses to keep this
from happening, but don't really have a clear sense of how big the
objects that I'm allocating are. I can use ROOM and TIME to get some
idea, but was hoping there might be something I could use to determine
how large *individual* objects are.
I know that this stuff is all implementation specific, but haven't
been finding much luck getting started with this. Any hints on good
starting places would be greatly appreciated.
Many thanks,
Matt Pillsbury
Pillsy <·········@gmail.com> writes:
> I know that this stuff is all implementation specific, but haven't
^^^^^^^^^^^^^^^^^^^^^^^
> been finding much luck getting started with this. Any hints on good
> starting places would be greatly appreciated.
^^^^^^^^^^^^^^^
I guess the sources of your implementation would be a good starting place.
But really, if your program is too slow, do you first ask a good
starting place to know how much time each operator takes? Or do you
do some time complexity analysis of your algorithm and try to replace
a polynomial algorithm into a logarithmic one?
It's exactly the same for space complexity. You don't care the exact
value of the constant space factor, because it won't change
significantly the limit before which your program will crash out of
memory. What matters is to replace your algorithms that take
polynomial or exponential space into algorithms that take logaritmic
or polynomial space.
> allocating a very large number of objects (CLOS instances, structs and
> double-floats, mostly), and have been running into issues where I
Ok. So here is the space needed by these data:
clos instances: O(number of slots)
structs: O(number of fields)
double-float O(1)
Now, do your own (time and SPACE) complexity analysis!
--
__Pascal Bourguignon__
On Jun 9, 4:19 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> But really, if your program is too slow, do you first ask a good
> starting place to know how much time each operator takes? Or do you
> do some time complexity analysis of your algorithm and try to replace
> a polynomial algorithm into a logarithmic one?
>
> It's exactly the same for space complexity. You don't care the exact
> value of the constant space factor, because it won't change
> significantly the limit before which your program will crash out of
> memory. What matters is to replace your algorithms that take
> polynomial or exponential space into algorithms that take logaritmic
> or polynomial space.
...
> Now, do your own (time and SPACE) complexity analysis!
I think this is a little misguided. Complexity analysis is really
useful for reasoning about how _algorithm_ performance scales with
respect to input size, which is why we don't "care" about constant
factors. We do care though, if those constants are huge.
We're talking here about performance issues with a specific language
implementation, so more concrete measurements are needed.
For example, heap exhaustion can sometimes be averted by manually
initiating garbage-collection at opportune moments (e.g. after you've
created and are done with 10,000 objects which have just gone out of
scope) in languages with a GC.
Got a profiler?
Ois�n Mac Fheara� <···········@gmail.com> writes:
> On Jun 9, 4:19�pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> But really, if your program is too slow, do you first ask a good
>> starting place to know how much time each operator takes? �Or do you
>> do some time complexity analysis of your algorithm and try to replace
>> a polynomial algorithm into a logarithmic one?
>>
>> It's exactly the same for space complexity. �You don't care the exact
>> value of the constant space factor, because it won't change
>> significantly the limit before which your program will crash out of
>> memory. �What matters is to replace your algorithms that take
>> polynomial or exponential space into algorithms that take logaritmic
>> or polynomial space.
> ...
>> Now, do your own (time and SPACE) complexity analysis!
>
> I think this is a little misguided. Complexity analysis is really
> useful for reasoning about how _algorithm_ performance scales with
> respect to input size, which is why we don't "care" about constant
> factors. We do care though, if those constants are huge.
So you think that (make-instance 'some-class) will use on the order of 1GB
rather than (dotimes (i 1e8) (make-instance 'some-class)) giving 100
million objects of 100 bytes?
You're thinking that constants analysis will give you a better answer
than asymptotic analysis in the mentionned by the OP?
> We're talking here about performance issues with a specific language
> implementation, so more concrete measurements are needed.
> For example, heap exhaustion can sometimes be averted by manually
> initiating garbage-collection at opportune moments (e.g. after you've
> created and are done with 10,000 objects which have just gone out of
> scope) in languages with a GC.
>
> Got a profiler?
--
__Pascal Bourguignon__
On Jun 10, 1:24 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> So you think that (make-instance 'some-class) will use on the order of 1GB
> rather than (dotimes (i 1e8) (make-instance 'some-class)) giving 100
> million objects of 100 bytes?
>
> You're thinking that constants analysis will give you a better answer
> than asymptotic analysis in the mentionned by the OP?
No, of course not, and I didn't mean to say that your approach was
somehow irrelevant or useless. Apologies if it came across that way.
It's very important to look at algorithmic complexity to see if
there's some silly loop-in-a-loop-in-a-loop creating objects.
But this is a case where we are interested in learning about constant
factors involved in time and (especially) space performance.
For example, looking at the computer language shootout (which I'm sure
has been discussed to death before: http://shootout.alioth.debian.org/)
shows that Lisp (SBCL) fares quite badly in terms of memory use,
compared with other implementations of the same algorithm in different
languages.
So algorithmic complexity analysis won't help us there, unless we
start looking deeper under the hood of the compiler. Thus, it's
helpful to investigate other more concrete analyses.
Ois�n Mac Fheara� <···········@gmail.com> writes:
> On Jun 10, 1:24�pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> So you think that (make-instance 'some-class) will use on the order of 1GB
>> rather than (dotimes (i 1e8) (make-instance 'some-class)) giving 100
>> million objects of 100 bytes?
>>
>> You're thinking that constants analysis will give you a better answer
>> than asymptotic analysis in the mentionned by the OP?
>
> No, of course not, and I didn't mean to say that your approach was
> somehow irrelevant or useless. Apologies if it came across that way.
> It's very important to look at algorithmic complexity to see if
> there's some silly loop-in-a-loop-in-a-loop creating objects.
> But this is a case where we are interested in learning about constant
> factors involved in time and (especially) space performance.
>
> For example, looking at the computer language shootout (which I'm sure
> has been discussed to death before: http://shootout.alioth.debian.org/)
> shows that Lisp (SBCL) fares quite badly in terms of memory use,
> compared with other implementations of the same algorithm in different
> languages.
> So algorithmic complexity analysis won't help us there, unless we
> start looking deeper under the hood of the compiler. Thus, it's
> helpful to investigate other more concrete analyses.
Ok, we agree. I only had the impression that since the OP was
filling the memory that it would be more efficient to search for a
better algorithm, space-wise, that to try to optimize the constants.
--
__Pascal Bourguignon__
On Jun 10, 5:48 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Ok, we agree. I only had the impression that since the OP was
> filling the memory that it would be more efficient to search for a
> better algorithm, space-wise, that to try to optimize the constants.
That makes sense; even if those constants are large, they're probably
not so large that they'd cause a good algorithm to run out of heap on
modern machines with lotsaRAM.
In Java programming, when I've run out of heap it's usually been
indicative of generating and destroying not-lightweight-enough objects
in a loop tight enough to cause problems before the GC kicks in
(although the JVM may grab quite a small heap without being asked to
make a bigger one, which gives it even less room to manoeuvre - does
the Lisp code get a big heap?).
This is one of the downsides of OO programming, especially if you
initialise big objects (e.g. buffers) in constructors rather than
lazily. Whenever something like this happens, I wonder if a totally
functional version would be easy to write and would avoid the
problems. Then I come up with some hack (like calling the GC before
allocating more objects, or making stuff lazy, or sharing/staticing
some objects instead of recreating them repeatedly) and forget about
it for a while...
On Jun 9, 5:05 pm, Pillsy <·········@gmail.com> wrote:
> I'm working on a project in SBCL 1.0.17 on OS X 10.5.3 that requires
> allocating a very large number of objects (CLOS instances, structs and
> double-floats, mostly), and have been running into issues where I
> exhaust the heap and get kicked into the SBCL low-level debugger. I
> would like to reduce the amount of memory my program uses to keep this
> from happening, but don't really have a clear sense of how big the
> objects that I'm allocating are. I can use ROOM and TIME to get some
> idea, but was hoping there might be something I could use to determine
> how large *individual* objects are.
See src/code/room.lisp.
You might, for example, like SB-VM:INSTANCE-USAGE.
On Jun 10, 3:05 am, Pillsy <·········@gmail.com> wrote:
> I'm working on a project in SBCL 1.0.17 on OS X 10.5.3 that requires
> allocating a very large number of objects (CLOS instances, structs and
> double-floats, mostly), and have been running into issues where I
> exhaust the heap and get kicked into the SBCL low-level debugger. I
> would like to reduce the amount of memory my program uses to keep this
[[...]]
Apart from all the other suggestions in this thread, on a coarser
level, you can also use the built-in profiler. sb-profile:report (I
think) output will look something like:
measuring PROFILE overhead..done
seconds | consed | calls | sec/call | name
27.636 | 1,141,809,360 | 3 | 9.211999 | ENDO-REPLACE
7.278 | 246,245,000 | 1 | 7.277973 | EXECUTE
3.990 | 90,240,456 | 5 | 0.797999 | MATCH
0.015 | 883,960 | 5 | 0.002999 | PATTERN
0.000 | 24,576 | 5 | 0.000000 | TEMPLATE
So although we normally associate time usage with profilers, the SBCL
one also gives you a rough idea on how much space each function
consed. Maybe this could help.
Cheers.