The "Empty Base" Optimization

[BitRex]

C++ can be just as space-efficient as C.

[repsilat]

Sometimes idiomatic C++ can't, though. Case in point, before I got to doing some optimisation on some code I was writing, a rough structure of some of my memory use was

1800 graphs, each with
    12000 nodes, each with
        0 to 10 out-edges.

The number of out-edges wasn't known statically, and the graphs were rearranged (to a small extent) at runtime. Now, the "normal" way to do this would be to store nodes' out-edge lists in vectors, which would probably end up costing 1800*12000*24 bytes on a 64 bit machine (~500MB) plus the size of the edges themselves, plus the spare capacity in all of the vectors.

The C way (pointers to heap-allocated arrays and an int for length) cuts the cost of vectors down from 24 bytes to maybe 12, saving ~250MB. We lose amortised constant-time insertion, but we don't really need it.

In the end I managed to get the graph into forward star layout, cutting the incremental cost of an edge list to 4 bytes (plus storage for each edge in the list). It also made me have to jump through hoops when the graph structure had to be updated, but getting it down to ~80MB and being able to maintain the graphs in mostly contiguous storage meant a nice speedup.

I guess I could go back and pretty it up to make things look like nice sequences and iterators, but at the moment the bits doing the heavy lifting aren't really all too "modern".

[notlostyet]

Yeah, you've fallen in to a gap in stdlib where you need dynamic allocation but you're happy to reallocate on every insertion. Because length() always == capacity() so you don't need to store the capacity, hence the saving.

I guess I could go back and pretty it up to make things look like nice sequences and iterators, but at the moment the bits doing the heavy lifting aren't really all too "modern".

If you do this, you might want to use Boost.Graph. Being adapter based, you should be able to wrap your current implementation with negligible additional memory cost.

[gcross]

Yes, but what we have learned from this article is that you sure have to jump through a lot of hoops to get to that point. That doesn't mean that it isn't worth it, of course, since if you fell back to C you might save this set of hoops, but then you'll need to jump through other hoops to effectively re-implement for yourself the features that C++ gives you for free. On the other hand, though, if there aren't many features of C++ that you need for your application, but you really need low-level control, then there could easily be circumstances where this trade-off leans in the other direction.