Take the 2-minute tour ×

In some C++ project I'm dealing with objects that represents graphs of various nature. They all implement a common, abstract, interface, which I'll reduce to one function for this post:

class graph {
   // Create an iterator over the successors of v
   virtual succ_iterator* succ(const vertex* v) const = 0;

The succ_iterator class is also an abstract class that makes it possible to iterate over the successors vertices of v:

class succ_iterator {
   virtual void first() = 0;               // reset the iterator
   virtual void next() = 0;                // move to next successor
   virtual bool done() const = 0;          // no more successor left?
   virtual const vertex* dest() const = 0; // destination vertex

So a loop over all the successors of v in graph g would look like this:

succ_iterator* i = g->succ(v);
   // use i->dest()
delete i;

I use such a loop very often to implement graph algorithms. Profiling the code reveal that its spending a lot of time allocating memory for these tiny iterator instances, so I'd like to hear about ideas to improve this.

Unfortunately, my graphs can be have very different implementations, so each graph may have its own implementation of the succ_iterator interface. Essentially, each class in the graph hierarchy has a corresponding class in the succ_iterator hierarchy. For instance one graph may be implemented using std::vector to store adjacency lists explicitly (in that case the succ_iterator is a simple wrapper above std::vector::const_iterator), while another graph might be computed on-the-fly (in that case its succ_iterator instance will actually compute the successors as it progresses). I don't know the nature of the graphs at compile time, so this rules out a template-based implementation à la STL.

I have thought about allowing each graph to handle a pool of succ_iterator. This seems to require an extra graph::succ_release(succ_iterator*) method to return the iterator to the pool instead of deleting it. Most pools I have seen are done at the memory level: i.e., when you release an object, its destructor is called, but the occupied memory is retained so that the next object will be created (with an in-place constructor) in the same block. It seems this still wastes time as the in-place constructor will have to setup a virtual-table pointer that is the same as that of the previous object. I think in such a pool I should replace delete+new by a recycle() method that has the same prototype as the constructor. As the code base is quite large, and this requires an interface change, I'd like to hear about other design ideas or possible improvements before I implement this.

Edit: I don't use threads.

share|improve this question
Step 1: try changing your implementation of malloc. Most new implementations are barebone calls to malloc under the hood, so switching to jemalloc or tcmalloc which were optimized for speed could yield the necessary boost without even touching your program. –  Matthieu M. Jul 4 '12 at 9:39
Thanks for these pointers. I'll look into these. So far I haven't found any benchmark comparing jemalloc, tcmalloc, and glibc's malloc for single-threaded application. Do you know of any? –  adl Jul 4 '12 at 20:52
unfortunately no. However one of the highlight of the Redis 2.4 release was switching from glibc to jemalloc; and Redis is single-threaded (mostly). –  Matthieu M. Jul 5 '12 at 6:11

1 Answer 1

You could cache the succ_iterators per graph instance and lookup and reuse them when needed?

//static or member:
std::map<graph*,succ_iterator*> graph_iterator_cache;

But I don't know if you have threadsafety issues.

share|improve this answer
I don't use any thread (at least for now). I'm not sure I understand you suggestion: the above map would associate only one iterator to each graph. I need to be able to use several iterators. Typically, a DFS can be implemented using a stack of iterators (each iterator representing an edge in the set of outgoing edges of a vertex). Sometimes I even need two iterators on the successors of the same vertex but looking at different edges (this rules out an implementation were all iterators would be preallocated for each vertex). –  adl Jul 4 '12 at 20:15

Your Answer


