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

["Antoine de Maricourt" <antoine.de-maricourt@xxxxxxx>]

> 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).
The underlying list node allocator will probably get a whole bunch of nodes 
every times it needs more nodes (probably the number of nodes that fit in a 
memory page). In your case, the node size seems to be 4096 / 256 = 16 bytes. 
Since you call them "links", I assume you use lists of pointers (i.e. 
list<T*>). The link holds 2 pointers (one for the linked list, the other one 
for your T objects). There is probably another hiden pointer used by the 
memory manager, and alignment makes your link 16 bytes large.

> This leads to my tree occupying about 100 times as much space as it 
> should.
However, a bunch of nodes shall not be tied to a given list, so your 
statement seems to be very odd (if it's true, you'd better use another 
implementation of the STL...).

> 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?
1. Make sure you really use "100 times as much space as it should". One way 
to do this is to trace node allocation (display their address on standard 
output and look at the difference between 2 consecutive allocations)
2. If yes (which would really surprise me), report to the library maintainer 
and / or use another implementation (what implementation are you using?)
3. Otherwise, you might consider:
a- storing objects instead of pointers in the list (use list<T> instead of 
list<T*>). Depending on sizeof(T), that might improve space efficiency
b- write your own allocator, and use it as an extra parameter to the 
template: this way, you can easily improve space efficiency, without 
rewriting the "list" class.
c- rewrite a whole tree class, that does not use lists from the STL

Your choice depends on your perspective. If you're writing experimental code 
and if efficiency is not the bottleneck (provided it remains decent), you'll 
go through steps 1 and 2 (and maybe 3a). If efficiency really matters then 
you might consider step 3c.

Another thought: if you are using list of pointer (list<T*>) don't forget 
that the list will only deallocate its own nodes (i.e. the links), and not 
the objects they point to. Since the objects have not been created by the 
list, they will not be deallocated by the list. Maybe you are experimenting 
memory leaks as well. In other words, if you write:

T* item = new item (...);
list<T*> l;
l.push_front (item);

and if you remove items from the list, and/or destroy the list, then you 
need to deallocate 'item' explicitely.

Antoine 
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/