Tags

, , , , ,

Whether C++, Java or any other language, we are all familiar with instantiating an object. In those aforementioned languages the operator new happens to do just that. Obviously CPUs don’t have any instruction nearly so high-level as to even approach the meaning of new. So what is it that this operator does? Or that is, what does it truly cost to instantiate an object?

Instantiation

Regardless of the language you are using you will you need to instantiate objects. Even the most strict functional program requires allocating and initializing complex data types. You should therefore know something about what it is doing.

So let’s take a basic example in Java, and see how equivalent code would be written in C (a language without a new operator).

class Point
{
  double x,y;
  Point( double x, double y ) { this->x = x; this->y = y; }
}

To instantiate a point we would write new Point(10,5), using whichever coordinates we want. How would be do the same in C?

struct Point
{
  double x, y;
};

void struct_init( Point * p, double x, double y ) { p->x = x; p->y = y; }

In C, since we don’t have explicit constructors, we simply create a function which takes a pointer to Point and initializes the values. Indeed Java and C++ are doing much the same thing here. The constructors are simply special syntax. Easy enough but we still have to see how C gets it’s memory for the Point instance.

Point * p = (Point*)malloc( sizeof(Point) );
struct_init( p, 10, 5 );

Our simple new operator has certainly saved us some typing. But don’t be fooled, your new operator is doing exactly the above. It first allocates memory (the malloc command here), and then it calls an initializer for that memory location. That initializer, as we see above, simply copies the two values to another location. If we were to profile this simple class we’d find that setting the value of x and y accounts for nearly 0% of CPU time. The rest will be spent in allocating memory.

Polymorphic classes, like in Java and C++ actually do more at construction time. We’ll get into that in another article.

Allocating Memory

Yes, that’s correct, allocating memory has a significant cost overhead. We won’t go too in depth here but you have to understand at least a bit about what happens. When a program requests a chunk of memory, for example with malloc, the runtime library has to find a bit of memory which can be used. Internally it maintains a list of memory blocks that it has available. It must look through its blocks of memory to find one that is large enough for your data. When found it will then divide that block, giving you a pointer to the part you can use, and reserving the rest for a later allocation.

For those of you paying attention to the complexity side of things that sounds like a loop! What you thought was constant time code may actually be linear. Still more, what if the allocator doesn’t have the memory available? Then it has to request the OS for some more memory. In order to do so it must do a context switch (from user space to kernel space). These switches themselves are not free. In turn the kernel has to do some work to get more memory to the program.

How memory is managed is very language and OS dependent however. Short of running a benchmark there is really no easy way to predict the average cost of doing new Point(10,5). Even within one language you will find a lot of variation depending on how many objects are allocated, when you free them, and the size of them.

The previous discussion covers somewhat of a worse case scenario. A benchmark should show that most calls to malloc aren’t nearly so expensive.

The clever stack

The above assumes that we are allocating the object on the heap: global memory. Programs can also allocate objects on the stack. In terms of performance this becomes very interesting. In C, C++, and many other languages stack allocation is free. That is, the compiler does all the work ahead of time and no call to malloc is required! Your only cost is the call to the initializer function itself. For small data objects stack allocation is really a great option.

The Cost of Instantiation

All in all there is a real cost of instantiating an object, not to mention there is also a real cost associated with cleaning up that object. This doesn’t mean you shouldn’t call new, it just means you shouldn’t needlessly call new. Reducing the amount of allocation you have in your program will speed it up. In particular, reducing allocation in key loops in your code could bring substantial improvements. A few calls to new here or there at runtime nobody will notice, yet a call to to new inside a repeated loop will definitely get noticed. So pay attention to to your malloc and new calls and you’ll likely find many ways to improve performance of your code.

Advertisements