Any way to speed up "new"?

[Leslaw Bieniasz]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

Sincerely,

L.B.

*-------------------------------------------------------------------*
| Dr. Leslaw Bieniasz, |
| Institute of Physical Chemistry of the Polish Academy of Sciences,|
| Department of Electrochemical Oxidation of Gaseous Fuels, |
| ul. Zagrody 13, 30-318 Cracow, Poland. |
| tel./fax: +48 (12) 266-03-41 |
| E-mail: (e-mail address removed) |
*-------------------------------------------------------------------*
| Interested in Computational Electrochemistry? |
| Visit my web site: http://www.cyf-kr.edu.pl/~nbbienia |
*-------------------------------------------------------------------*

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

First question is, do you really need to "new" all thost small
objects ?

 

[Catalin Pitis]

First question is, do you really need to "new" all thost small
objects ?

.... and if yes, try to minimize the number of allocations with new. I know
that the containers in STL do this by allocating in advance more memory than
needed, to prevent memory fragmentation and to minimize the number of
allocations (and the time needed for them).

Catalin

 

[Karl Heinz Buchegger]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator.

Get a copy of
Effective C++
Scott Meyers

Item 10 ("Write operator delete if you write operator new")
discusses a solution for that.

<Quote>
Let's step back for a moment and return to fundamentals. Why would anybody want to write their
own version of operator new or operator delete in the first place?

More often than not, the answer is efficiency. The default versions of operator new and
operator delete are perfectly adequate for general-purpose use, but their flexibility
inevitably leaves room for improvements in their performance in a more circumscribed
context. This is especially true for applications that dynamically allocate a large number
of small objects.

....
</Quote>

 

[Rolf Magnus]

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming.

So using new is slower than using malloc? That sounds strange to me. But if
that is really the case, you might try to use malloc in your C++ program
too instead of new. It depends on what your objects exactly are.

The question is:
are there any techniques to speed up this memory allocation?

You can try to do your own, managing things differently than the built-in
one, but there is no magic make_new_fast() function or something

 

[John Harrison]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

Sincerely,

L.B.

Andrei Alexandrescu discusses a small object allocator in his book Modern
C++ Design. The minimal testing that I did with it on my platform suggested
that it did indeed speed things up when you had to allocate a large number
of small objects. Maybe you should get hold of the book, or just download
the code, it's part of the Loki library.

Also on my platform new and malloc are the same thing, operator new just
calls malloc. Have you actually checked what operator new does on your
platform?

Also can you just get rid of some of the allocations? Certainly I see newbie
code where too many allocations are performed for no good reason. There is
absolutely no reason that object oriented code need be slower than
procedural code (I think this is what you meant by functional code). Object
orientated code could just be thought of as a way of organising procedural
code better. Perhaps you could post an outline of the classes you are using
and their relationships.

john

 

[Ioannis Vranos]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

You can define your own version of new either as a global function or as
a member function of your class (the second is better in your case),
both called implicitly. Check this dummy example of mine:




#include <cstddef>

// Contains std::bad_alloc
#include <new>

#include <iostream>


class SomeClass
{
static std::size_t occupied;
static unsigned char *buffer;
static const std::size_t MAX_SIZE=5*1024;

public:

~SomeClass() { std::cout<<"Destructor called!\n"; }

void *operator new(std::size_t size)
{
using namespace std;

cout<<"Class member operator new was called!\n";

if(occupied+size>MAX_SIZE)
throw bad_alloc();

occupied+=size;

return buffer+occupied-size;
}

void operator delete(void *p)
{
std::cout<<"Class member operator delete was called!\n";

occupied-=sizeof(SomeClass);
}
};

std::size_t SomeClass:ccupied=0;
unsigned char *SomeClass::buffer=new unsigned char[MAX_SIZE];


int main()
{
SomeClass *p=new SomeClass;

delete p;
}



This is for demonstration only, does not always work well in reality.

 

[Niels Dybdahl]

The question is:

are there any techniques to speed up this memory allocation?

If you can place the objects on the stack instead of the heap, then you will
gain some speed.

Niels Dybdahl

 

[Lionel B]

So using new is slower than using malloc? That sounds strange to me.

To me too (I think on my system operator new simply calls malloc)...
but he doesn't actually say that his C code used malloc. Maybe he was
allocating on the stack. Which begs the question as to why his C++
implementation should use new.

 

[Karl Heinz Buchegger]

To me too (I think on my system operator new simply calls malloc)...
but he doesn't actually say that his C code used malloc. Maybe he was
allocating on the stack. Which begs the question as to why his C++
implementation should use new.

If we are exact, then the OP didn't say that malloc() was faster then new.
All he said, is that an implementation the C way is faster then his C++
implementation. There are plenty of pitfalls why this could be so. Eg.
constantly passing per value instead of per reference comes to my mind
immediatly.

 

[Rolf Magnus]

If we are exact, then the OP didn't say that malloc() was faster then new.

That's right. I just assumed that with 'equivalent code wriiten using pure
"C" functional programming', he meant that he allocates the data
dynamically in both cases, which would mean malloc (or calloc or realloc)
in C.

All he said, is that an implementation the C way is faster then his C++
implementation. There are plenty of pitfalls why this could be so. Eg.
constantly passing per value instead of per reference comes to my mind
immediatly.

Why would that be slower in C++ than in C?

 

[Ioannis Vranos]

So using new is slower than using malloc? That sounds strange to me. But if
that is really the case, you might try to use malloc in your C++ program
too instead of new. It depends on what your objects exactly are.

It looks like you are missing the fact that constructors and destructors
are not called when using the malloc()/free() family.

 

[Ioannis Vranos]

Also on my platform new and malloc are the same thing, operator new just
calls malloc. Have you actually checked what operator new does on your
platform?

Does the following display any messages in your platform?


#include <cstdlib>
#include <iostream>


class SomeClass
{
public:
SomeClass() { std::cout<<"Constructor called!\n"; }
~SomeClass() { std::cout<<"Destructor called!\n"; }
};



int main()
{
using namespace std;

SomeClass *p= static_cast<SomeClass *>( malloc(sizeof(*p)) );

free(p);
}

 

[Arijit]

What I gather from your post is that for creating an object a number
of calls to new is necessary. In your C code, you are using only 1 call
to malloc instead (Its possible because no constructors are involved,
like in C++ case.) If thats the case, I think using placement form of new
for all your objects will speed up the memory allocation considerably.

If on the other hand in your C code you were using the same number of
malloc calls as calls to new in C++ code, then the C code should not
run any faster than the C++ code.

-Arijit

 

[Siemel Naran]

class SomeClass
{
static std::size_t occupied;
static unsigned char *buffer;
static const std::size_t MAX_SIZE=5*1024;

public:

~SomeClass() { std::cout<<"Destructor called!\n"; }

void *operator new(std::size_t size)
{
using namespace std;

cout<<"Class member operator new was called!\n";

if(occupied+size>MAX_SIZE)
throw bad_alloc();

occupied+=size;

return buffer+occupied-size;
}

void operator delete(void *p)
{
std::cout<<"Class member operator delete was called!\n";

occupied-=sizeof(SomeClass);
}
};

Right idea, but your operator delete does not make use of 'p', and instead
always releases the memory of the last element allocated, so SomeClass * s1
= new SomeClass(); SomeClass * s2 = new SomeClass(); delete s1 actually
releases the memory of s2.

One idea is to ensure that sizeof(SomeClass) >= sizeof(void*), which is
usually the case anyway. Then make the 'p' passed to class operator delete
point to the next available slot. And have the static member
SomeClass:ccupied. which should be a pointer, point to 'p'.

std::size_t SomeClass:ccupied=0;
unsigned char *SomeClass::buffer=new unsigned char[MAX_SIZE];

Who deletes SomeClass::buffer? There is a memory leak.

This is for demonstration only, does not always work well in reality.

OK, so apart from the simplicity of your operator new and delete for
demonstration, what do you mean that it does not always work? What can go
wrong?

 

[Karl Heinz Buchegger]

That's right. I just assumed that with 'equivalent code wriiten using pure
"C" functional programming', he meant that he allocates the data
dynamically in both cases, which would mean malloc (or calloc or realloc)
in C.


Why would that be slower in C++ than in C?

May bad. Should have talked a little bit more about what I mean.
A lot of newbies pass class objects around per value. Surprisingly
they don't do the same in C (with struct objects). In C they always
pass pointers while in C++ they go through the burden of creating
a lot of temporaries because they don't recognize the temporaries.
So it may be that the C++ way is more expensive and he sees more
time spent in memory allocations because the program simply
creates and destoyes lots of temporaries. But without code
it is hard to tell.

Just my thoughts on the OP's problem, because I am with you
that new shouldn't be that much slower then malloc().

 

[Tom Widmer]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

The first thing to do is to remove any pointers you don't need,
replacing them with values. e.g.

class Foo
{
SubFoo* subpart;
};

can often be replaced with:
class Foo
{
SubFoo subpart;
};

Obviously, this isn't possible if polymorphism is required.

Next, make sure your functions use values rather than pointers. e.g.
NOT
void f()
{
Foo* f = new Foo();
//....
delete f;
}

but instead:
void f()
{
Foo f;
//use f
}

If that doesn't give you the required speed up, you'll have to look at
object copying - eliminate any unnecessary object copying, using
reference counting if necessary, and passing values by reference where
appropriate.

If your code is now looking tight, but is *still* too slow, the final
optimization is to optimize the allocations themselves. Take a look at
the boost pool library (www.boost.org), which allows massive
optimization of small object allocations.

Finally, read a book on writing modern, efficient C++ - well written
C++ programs tends to perform just as well as the equivalent well
written C program - efficiency losses in some areas tend to be
compensated by gains in others.

Tom

 

[Ioannis Vranos]

Right idea, but your operator delete does not make use of 'p',

Yes, I could have made the signature

void operator delete(void *)
{
// ...
}


in that example. However this is unimportant.

and instead
always releases the memory of the last element allocated, so SomeClass * s1
= new SomeClass(); SomeClass * s2 = new SomeClass(); delete s1 actually
releases the memory of s2.

One idea is to ensure that sizeof(SomeClass) >= sizeof(void*), which is
usually the case anyway.

What's the purpose of this? Keep in mind that the specified operators
are members of the class SomeClass and are called only when dealing with
such objects. So the void * passed in the member operator delete() is a
SomeClass * always.

Then make the 'p' passed to class operator delete
point to the next available slot. And have the static member
SomeClass:ccupied. which should be a pointer, point to 'p'.

Yes, yes whatever.

std::size_t SomeClass:ccupied=0;
unsigned char *SomeClass::buffer=new unsigned char[MAX_SIZE];

Who deletes SomeClass::buffer? There is a memory leak.

Presumably the rest of the program.

OK, so apart from the simplicity of your operator new and delete for
demonstration, what do you mean that it does not always work? What can go
wrong?

The simplicity you are talking about. As the implementation is given,
as you said if you do two subsequent calls to new and then a delete to
the first object, the code does not work properly (the destructor of s1
is called and the space of s2 is cleaned).

 

[Arijit]

Operator new and new operator are two different things. So operator new
needs only to allocate memory, not call constructor. The same thing
happens when you overload operator new for your class. Your operator
new only has to allocate memory, not call constructor on that allocated
memory. So its perfectly ok to implement operator new with malloc. And
in fact, usually thats how its done. The global new usually calls malloc
Thats why on most platforms you can get away with allocating something with
new and deleting with free and vice versa.

Does the following display any messages in your platform?


#include <cstdlib>
#include <iostream>


class SomeClass
{
public:
SomeClass() { std::cout<<"Constructor called!\n"; }
~SomeClass() { std::cout<<"Destructor called!\n"; }
};



int main()
{
using namespace std;

SomeClass *p= static_cast<SomeClass *>( malloc(sizeof(*p)) );

free(p);
}

I hope you are being sarcastic .

-Arijit

 

[Jerry Coffin]

Cracow, 28.10.2004

Hello,

I have a program that intensively allocates and deletes lots
of relatively small objects, using "new" operator. The objects
themselves are composed of smaller objects, again allocated using "new".
From my tests I deduce that a considerable part of the computational
time is spent on the memory allocation, which makes the program
substantially slower compared to the equivalent code written using
pure "C" functional programming. The question is:
are there any techniques to speed up this memory allocation?
(I use Borland C++ Builder 4.0 pro, if this plays any role).

There are all kinds of ways. The first thing to do is to use a
profiler to get a better assurance that this is really what's causing
the slow-down. Since you haven't shown either piece of code, it's
impossible to say with any certainty what's going on, but there's no
particularly good reason new should be substantially slower than
malloc, as far as the memory allocation itself goes.

Using new, however, doesn't just allocate memory -- it creates an
object in that memory. If your ctor is slow, using new will be slow
even though the memory allocation itself hasn't slowed down at all.

If it really IS the memory allocator that's causing the problem, the
usual cure is to overload operator new for the class(es) in question.
The advantage here is that you only have to provide for allocating one
specific size of chunk of memory, instead of providing for all
different sizes like the global operator new does. One common
implementation is to allocate a chunk of memory big enough to hold a
number of objects, and with it create a list of the addresses of
unused chunks of memory, each the right size to hold an object. When
you receive a request for a chunk, you just pop the first address off
the list and return it. When you need to free an object, you push its
address back onto the list, and you're done. This can save lots of
work in trying to find a chunk of (roughly) the right size, and if
there isn't one, creating it from a bigger chunk (and then coalescing
chunks when they're freed).

I'll reiterate, however, that there's normally no reason new should be
a lot slower at allocating memory than malloc, so if you're seeing a
large slowdown, the first thing to do is be sure where the time is
going. When/if you confirm that it really IS the memory allocation,
working on the allocator is likely to do some good.