Re: [computer-go] space efficiency in C++

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Sun, Apr 24, 2005 at 01:58:16AM +0100, Tom Cooper wrote:
>    I've got a problem with efficiency in memory use that I thought someone 
> here might be able to help me with.
> 
> I'm using C++, and I have a class: tree, that contains a member object 
> list<tree *> children.  I think I do want a list here, because I do a lot 
> of deleting individual elements.  My tree objects are very big, in fact 
> their size is the main performance limiting factor in my 
> programme.  However, the lists of children are typically quite short, often 
> one or two elements.  My implementation of the Standard C++ Library seems 
> to allocate space for each list in batches of 256 links (which I suspect is 
> typical).  This leads to my tree occupying about 100 times as much space as 
> it should.

I hope that's not typical, though I haven't used C++ with any
seriousness for years, so for all I know it might be.
 
> Has anyone else come across this problem  Does anyone have an idea for a 
> work-around?  Do I have to abandon the standard library for this 
> application?

If "abandon the standard library for this application" means not using
the library anywhere in your go-playing program, I'd say no, unless
this problem is just one of many specific symptoms of the library's
implementation being generally horrible, or unless you have a
comparably expressive but better-implemented library to replace it
with.

If "abandon ... for this application" means use another list<>
implementation for this hotspot, I'd say yes. It's not uncommon with
libraries in general to find that one's own usage pattern is handled
inefficiently by the library, enough to justify overriding it, and in
my experience usually the right thing is just to override the library
in the measured hotspot, not throw out the library. (Throwing out
libraries can be justified, but in my experience usually because of
reliability problems, not performance problems. On the other hand,
this pattern of the library wanting 100x too much space for short
lists seems more extreme than usual...)

Lists are about as simple as data structures can be, so it should be
easy to write a special-purpose replacement once you find a bottleneck
like this. If you were already familiar with C++ templates and STL
house style, or if you found an open-source library to borrow from,
writing a mysmalllist<T*> with the performance characteristics you
want and with plug-compatible support for the STL operations that you
use for that slot might be a matter of a day.

By the way, I think you'll increase your chance of getting useful
feedback on questions about implementation issues if you make a habit
of saying what the implementation is. If you can say "in
DarkMachineSoul STLBang 3.4 running on my Trolltoothware laptop,
list<T*> preallocates 256 list elements" then responses aren't limited
to vague opinions like mine, but can be very specific: "oh yeah,
*that* problem, you too, huh? See http://foo..."; with a cut and dried
workaround, or a recommendation for a generally better replacement
library with detailed justification of why it's generally better, or
whatever.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
Ubi saeva indignatio ulterius cor lacerare nequit. -- Jonathan Swift's epitaph
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/