(C++) Looking for tips to reduce memory usage

Question

I've got a problem with a really tight and tough memory limit. I'm a CPP geek and I want to reduce my memory usage. Please give me some tips.

---

One of my friends recommended to take functions inside my structs out of them. for example instead of using:

struct node{
   int f()
   {}
}

he recommended me to use:

int f(node x)
{}

does this really help?

Note: I have lots of copies of my struct.

---

here's some more information:

I'm coding some sort of segment tree for a practice problem on an online judge. I get tree nodes in a struct. my struct has these variables:

  int start;
  int end;
  bool flag;
  node* left;
  node* right;

The memory limit is 16 MB and I'm using 16.38 MB.

Answer 1

I'm guessing by the subtext of your question that the majority of your memory usage is data, not code. Here are a couple of tips:

• If your data ranges are limited, take advantage of it. If the range of an integer is -128 to 127, use char instead of int, or unsigned char if it's 0 to 255. Likewise use int16_t or uint16_t for ranges of -32768..32767 and 0..65535.
• Rearrange the structure elements so the larger items come first, so that data alignment doesn't leave dead space in the middle of the structure. You can also usually control padding via compiler options, but it's better just to make the layout optimal in the first place.
• Use containers that don't have a lot of overhead. Use vector instead of list, for example. Use boost::ptr_vector instead of std::vector containing shared_ptr.
• Avoid virtual methods. The first virtual method you add to a struct or class adds a hidden pointer to a vtable.

Answer 2

No, regular member functions don't make the class or struct larger. Introducing a virtual function might (on many platforms) add a vtable pointer to the class. On x86 that would increase the size by four bytes. No more memory will be required as you add virtual functions, though -- one pointer is sufficient. The size of a class or struct type is never zero (regardless of whether it has any member variables or virtual functions). This is to make sure that each instance occupies its own memory space (source, section 9.0.3).

Answer 3

In my opinion, the best way to reduce memory is to consider your algorithmic space compexity instead of justing doing fine code optimizations. Reconsider things like dynamic programming tables, unnecessary copies, generally any thing that is questionable in terms of memory efficiency. Also, try to free memory resources early whenever they are not needed anymore.

Answer 4

For your final example (the tree), you can use a clever hack with XOR to replace the two node pointers with a single node pointer, as described here. This only works if you traverse the tree in the right order, however. Obviously this hurts code readability, so should be something of a last resort.

Answer 5

You could use compilation flags to do some optimization. If you are using g++ you could test with: -O2

There are great threads about the subject:

C++ Optimization Techniques

Should we still be optimizing "in the small"?

Constants and compiler optimization in C++

What are the known C/C++ optimizations for GCC

Answer 6

The two possibilities are not at all equivalent:

• In the first, f() is a member function of node.
• In the second, f() is a free (or namespace-scope) function. (Note also that the signature of two f() are different.)

Now note that, in the first style, f() is an inline member function. Defining a member function inside the class body makes it inline. Although inlining is not guranteed, it is just a hint to the compiler. For functions with small bodies, it may be good to inline them, as it would avoid function call over head. However, I have never seen that to be a make-or-break factor.

If you do not want or if f() does not qualifiy for inlining, you should define it outside the class body (probably in a .cpp file) as:

 int node::f() { /* stuff here */ }

If memory usage is a problem in your code, then most probably the above topics are not relevant. Exploring the following might give you some hint

• Find the sizes of all classes in your program. Use sizeof to find this information, e.g. sizeof( node)
• Find what is the maximum number of objects of each class that your program is creating.

• Using the above two series of information, estimate worst case memory usage by your program

  Worst case memory usage = n1 * sizeof( node1 ) + n2 * sizeof( node2 ) + ...

If the above number is too high, then you have the following choices:

• Reducing the number of maximum instances of classes. This probably won't be possible because this depends on the input to the program, and that is beyond your control
• Reduce the size of each classes. This is in your control though.

How to reduce the size of the classes? Try packing the class members compactly to avoid packing.

Answer 7

As others have said, having methods doesn't increase the size of the struct unless one of them is virtual.

You can use bitfields to effectively compress the data (this is especially effective with your boolean...). Also, you can use indices instead of pointers, to save some bytes.

Remember to allocate your nodes in big chunks rather than individually (e.g., using new[] once, not regular new many times) to avoid memory management overhead.

If you don't need the full flexibility your node pointers provide, you may be able to reduce or eliminate them. For example, heapsort always has a near-full binary tree, so the standard implementation uses an implicit tree, which doesn't need any pointers at all.

Above all, finding a different algorithm may change the game completely...