Allocation behavior of STL containers.

[roberts]

There is only two places in my code that I do any memory allocation and the list of those allocated blocks are kept in a main class that iterates through the lists to delete them when the dtor is called.

When I process a 3D object, I do so a span(when scanning the geometry) and line(when reading or writing to/from a file) at a time and nothing I do in my code allocates any new memory blocks beyond what I do above, but if I process the same file, scaled larger, my computer bogs down pretty bad. I also watched the process monitor and saw my program was using a little over 1/2G of memory.

It's the same number of base vertices and triangles, the only things I allocate memory for. The only thing that increases in quantity is the number of span blocks, which are stored in a local list, and spans which which are returned from a locally declared list to another locally declared list.

I do make heavy use of lists, but they are local and still my machine and program slows down big time.

How is memory allocated and freed in locally declared lists? Do I need to pop lists to free memory or can I just let them pass out of scope and assume the underlying list container handles destruction?

[JLBorges]

> can I just let them pass out of scope and assume the underlying list container handles destruction?

Yes. The container will take care of releasing memory for its value_type when it is destroyed.

If the value_type is a pointer (and the elements point to an object with dynamic storage duration), the container will release memory for the pointer (and not for the pointed object).

{
    std::list<A> seq1 ; // safe, the container takes care of the objects

    std::list< std::unique_ptr<A> > seq2 ; // safe, the container takes care of the smart pointers;
    // the destructor of the smart pointer will take care of the object of type A
    std::list< std::shared_ptr<A> > seq3 ; // same as above

    std::list<A*> seq4 ; // it is the programmers responsibility to delete dynamically allocated 
    // objects of type A. This - a container holding raw pointers to obects 
    // which must be destroyed along with the container - is a canonical anti-pattern 
} 

> I do make heavy use of lists, but they are local and still my machine and program slows down big time.

Consider if you can use std::vector<> instead. It is the default sequence container of choice. In particular, use a std::list<> only if either insert/erase into the middle of the sequence is a frequent operation or if you actually need its 'strong guarantee' of exception safety.

[roberts]

    std::list<A*> seq4 ; // it is the programmers responsibility to delete dynamically allocated 
    // objects of type A. This - a container holding raw pointers to obects 
    // which must be destroyed along with the container - is a canonical anti-pattern  

This is what I use as the main lists, but some of my other lists will contain pointers to allocated memory contained in the main lists:

class Geometry
{
private:
	list<Vector *> vertex_list;
	list<Triangle *> triangle_list;
	
	Vector boundingbox[2];

class Triangle
{
private:
	Vector *vertex_ref[3];
	Vector normal;
	Triangle *triangle_ref[3];				// pointer reference to the triangles that share an edge with this one.
	double d;

struct Span_block
{
	double t;						// 0.0 <= t <= 1.0. Used for sorting
	int blocking;					// Determines if this block represents a START or END block.
	Vector p;
	Triangle *triangle;				// The triangle this span block references. Used at end to resolve partial hits.
	Point point[4];					// Individual point information, including whether the point
	Span_block() {}
	Span_block( const Span_block & );
	Span_block &operator=(const Span_block &);

	void invalidate();
};

Geometry is the class the holds all the allocated blocks. All other pointers are simply used to reference into Geometry's list of triangles and vertices.

I'm not sure I understand fully the concept of pattern/anti-pattern. I'll see what some googling turns up and come back with questions.

I'll convert the other lists to vectors and see if that helps. They probably all can be vectors as there is no middle insertions going on. Everything is simply pushed and I do a linear lookup for resolving references.

[JLBorges]

> This is what I use as the main lists, but some of my other lists will contain pointers to allocated
> memory contained in the main lists: ... Geometry is the class the holds all the allocated blocks.
> All other pointers are simply used to reference into Geometry's list of triangles and vertices.

I presume that: The Geometry object is a long-lived object, and it has a destructor that takes care of destroying the vertices and triangles. The list of Span_blocks is a short lived object which hold objects of type Span_block by value; with each Span_block containing non-owning pointers to objects held in the Geometry object.

The temporary lists of Span_block objects are of the type std::list<Span_block> - that is the Span_block objects are not dynamically allocated. In this case, there is no issue - you can just let the list pass out of scope and the underlying list container will take care of the clean up.

If these temporary lists are of type std::list<Span_block*>, with each Span_block being allocated dynamically, the list destructor of the list will not destroy the Span_block objects. In this case, you will have to write java-like spaghett:

{
    std::list< Span_block* > seq ;
    try
    {
         // ...
         seq.push_back( new Span_block( /* ... */ ) ) ;
        // ...
        // do thing with list
        // ...
    }
    catch( ... ) // simulated finally
    {
          for( Span_block* p : lst ) delete p ;
          throw ;
    }

     for( Span_block* p : lst ) delete p ;
}

Writing error handling code in places where you do not know how to handle errors is an anti-pattern in C++. C++ has first class language support for RAII; it is by design that C++ does not have a try-finally construct.

The idiomatic way to do this would be:

{
    std::list< std::unique_ptr<Span_block> > seq ;
    // ...
    seq.emplace_back( new Span_block( /* ... */ ) ) ;
    // ...
    // do thing with list
    // ...
}

[roberts]

If these temporary lists are of type std::list<Span_block*>, with each Span_block being allocated
dynamically, the list destructor of the list will not destroy the Span_block objects. In this case,
you will have to write java-like spaghett:

No, I was very precise. There is only two places where memory is allocated and the block are ultimately stored in the same place. It helps with freeing up resources and controlling memory leaks, at least for me. It's a practice I've always used.

[JLBorges]

Ok, that is fine then.

There are two possible ways which come to mind for improving memory related performance:

1. Consider replacing the std::list<Span_block> with std::vector<Span_block>

2. If that is not possible, use a custom pool allocator. Boost has a ready made one: http://www.boost.org/doc/libs/1_49_0/libs/pool/doc/html/boost_pool/pool/interfaces.html#pool_allocator

[roberts]

1. Consider replacing the std::list<Span_block> with std::vector<Span_block>

Already done. Everything has been converted to vectors. I don't see much of a change in the memory footprint, but my computer is not suffering anymore.

I'll look into boost again, but to be honest, I am having trouble with the obfuscation. I tried to use program_options and I am simply unable to grasp the methodology of that thing. It also doesn't help that at least one of their tutorial examples throws a compiler error and I'm not sure how to go about making it work and it happens to be the one I need to look at most.

[JLBorges]

> I'll look into boost again

No, unless you want to reduce the memory footprint for some reason.

If the performance with std::vector<> / std::allocator<> is good enough, let it be.