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: [phone] |
| E-mail: nb******@cyf-kr.edu.pl |
*-------------------------------------------------------------------*
| Interested in Computational Electrochemistry? |
| Visit my web site: http://www.cyf-kr.edu.pl/~nbbienia |
*-------------------------------------------------------------------*

[Nils O. Selåsdal]

Leslaw Bieniasz wrote:

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]

""Nils O. Selåsdal"" <NO*@Utel.no> wrote in message
news:KW******************@news4.e.nsc.no...

Leslaw Bieniasz wrote:

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 ?

.... 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]

Leslaw Bieniasz wrote:

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>

--
Karl Heinz Buchegger
kb******@gascad.at

[Rolf Magnus]

Leslaw Bieniasz wrote:

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]

"Leslaw Bieniasz" <nb******@cyf-kr.edu.pl> wrote in message
news:Pi*******************************@kinga.cyf-kr.edu.pl...

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]

Leslaw Bieniasz wrote:

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::occupied=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.


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[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]

Rolf Magnus wrote:

Leslaw Bieniasz wrote:

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.

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.

--
Lionel B

[Karl Heinz Buchegger]

Lionel B wrote:

Rolf Magnus wrote:

Leslaw Bieniasz wrote:

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.

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.
--
Karl Heinz Buchegger
kb******@gascad.at

[Rolf Magnus]

Karl Heinz Buchegger wrote:

Lionel B wrote:

Rolf Magnus wrote:

> Leslaw Bieniasz wrote:
>
> > 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.

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.

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]

Rolf Magnus wrote:

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

http://www23.brinkster.com/noicys

[Ioannis Vranos]

John Harrison wrote:

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);
}


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[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

Leslaw Bieniasz <nb******@cyf-kr.edu.pl> wrote in message news:<Pi*******************************@kinga.cyf-kr.edu.pl>...

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: [phone] |
| E-mail: nb******@cyf-kr.edu.pl |
*-------------------------------------------------------------------*
| Interested in Computational Electrochemistry? |
| Visit my web site: http://www.cyf-kr.edu.pl/~nbbienia |
*-------------------------------------------------------------------*

[Tom Widmer]

On Thu, 28 Oct 2004 11:20:28 +0200, Leslaw Bieniasz
<nb******@cyf-kr.edu.pl> wrote:

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]

Siemel Naran wrote:

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::occupied. which should be a pointer, point to 'p'.

Yes, yes whatever. :-)

std::size_t SomeClass::occupied=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.

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?

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).


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Arijit]

Ioannis Vranos <iv*@guesswh.at.grad.com> wrote in message news:<1098980489.287591@athnrd02>...

John Harrison wrote:

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?

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]

Leslaw Bieniasz <nb******@cyf-kr.edu.pl> wrote in message news:<Pi*******************************@kinga.cyf-kr.edu.pl>...

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Leslaw Bieniasz]

Cracow, 2.11.2004

Hello,

On Thu, 28 Oct 2004, Niels Dybdahl wrote:

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

How exactly can I do this? Examples please.
Let's assume my class is
class A
{
public:
A(const int n){V = new double [n]; N=n;}
~A(void){delete [] V;}

private:
double *V;
int N;
};
How can I force it's construction on the stack, instead of on the heap?
(by the way, I seem to have read somewhere that in the case of 32
bit Windows that I use, there is no difference between the stack and the
heap; it's the same memory pool. Isn't this true?)

By the way, the above class is a simple implementation of a vector
class. My question has been motivated by the observation that apparently
the allocation of the conventional "C-type" vector:

int n;
double *a = new double [n];

takes visibly less time that the allocation of the equivalent "OO" vector:

int n;
A *a = new A(n);

Thus, I am afraid nobody can convince me that OOP need not be slower that
"C" programming. Whatever we do, the indirection involved in the OOP
cannot be overcome. But, I am open to any helpful suggestions.

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: [phone] |
| E-mail: nb******@cyf-kr.edu.pl |
*-------------------------------------------------------------------*
| Interested in Computational Electrochemistry? |
| Visit my web site: http://www.cyf-kr.edu.pl/~nbbienia |
*-------------------------------------------------------------------*