How to design a class appropriate for millions of allocations?

Question

If I want to allocate millions of objects of a class Foo, and I want to be memory- and time-efficient, how should I design the Foo class?

Obviously, Foo should not contain much member data.

Also, I guess, it should not use virtual functions?

And how costly is it for Foo to derive from a Base class? And from several Base classes?

Are there any other tips for making millions of Foo objects very efficient?

Answer 1

I don't think there's much to say about designing your class for millions of allocations. Yes, there's the obvious memory limit, so if you have a fix amount of memory this might be a real concern for you, otherwise you will always risk running out of memory. A pointer to the virtual table is just that, a pointer (4 or 8 bytes on 32 or 64 bit architecture), not sure this is the case in multiple inheritance. Calling virtual functions has the overhead of the virtual lookup (and extra cache miss, if you didn't use it recently), but only for virtual functions, and they may never be inlined.

If there's a lot of repeated values, you might want to look into having a separate data structure as well (flyweight pattern). And for efficiency, make sure you have a light-weight (inlined) constructor and assignment operators, especially if you intend to use stl vectors and similar.

These are all pretty straightforward stuff, so now for my real suggestion:

What's really going to kill your memory management is if you get fragmentation, where you might all of a sudden have a bunch of memory, but still nowhere to put your objects (not enough contiguous space). If you have a lot of interleaved allocation, this might turn to be a real problem so you might want to look into allocating large blocks of objects, keep them in a pool and reuse. Or use a custom allocator (new-operator), where you preallocate a block of memory which is a multiple of your object size, and use that for your objects.

Answer 2

Have a look at the Flyweight pattern. The GoF book does a much better job than Wikipedia at explaining the pattern, though.

Answer 3

The main thing is to minimize use of new and delete by keeping used objects in a pool and re-using them. Don't worry about virtual functions. The overhead of calling them is usually trivial relative to whatever else is going on in your program.