better new delete

[cppquester]

Hi Folks,

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though):

class A
{
std::vector< int> someData;

static std::stack used;

public:
static void * operator new (size_t size);
static void operator delete (void *p, size_t size);
};

void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();
used.pop();
return res;
}

return ::new( sz);
}

void A:perator delete (void *p, size_t sz)
{
someData.clear();
used.push( p);
}

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?
Of course it is obvious that there is a certain memory overhead (for
the stack and as all As are never freed), but it looks to me that this
is a very easy way to gain a lot of performance potentially. Am I
missing something?

 

[Alf P. Steinbach]

* (e-mail address removed):

Hi Folks,

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though):

class A
{
std::vector< int> someData;

static std::stack used;

public:
static void * operator new (size_t size);
static void operator delete (void *p, size_t size);
};

void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();
used.pop();
return res;
}

return ::new( sz);
}

void A:perator delete (void *p, size_t sz)
{
someData.clear();
used.push( p);
}

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?
Of course it is obvious that there is a certain memory overhead (for
the stack and as all As are never freed), but it looks to me that this
is a very easy way to gain a lot of performance potentially. Am I
missing something?

The general idea is called a free-list or, with more sophisticated
management, a cache. And what you're missing is, first, that std::stack
itself uses dynamic allocation, and second, that in operator delete you
don't have access to instance member data (the instance has already been
destroyed), and third, that a free-list is based on a certain usage
pattern (otherwise it just adds overhead), and fourth, that defining
operator new and operator delete is very costly in that it prohibits
other possibly more important usages of that mechanism, and fifth, that
it's generally not a good idea to do micro-optimization. In short don't
do it, or at least, don't do it yet (for optimization, first measure!).

Cheers, & hth.,

- Alf

 

[Victor Bazarov]

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though):

class A
{
std::vector< int> someData;

static std::stack used;

public:
static void * operator new (size_t size);
static void operator delete (void *p, size_t size);
};

void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();
used.pop();
return res;
}

return ::new( sz);
}

void A:perator delete (void *p, size_t sz)
{
someData.clear();
used.push( p);
}

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?
Of course it is obvious that there is a certain memory overhead (for
the stack and as all As are never freed), but it looks to me that this
is a very easy way to gain a lot of performance potentially. Am I
missing something?

The idea, as I understand it, is not to deallocate the last "freed"
instance but to reuse it. Seems nice to have the freeing delayed,
and that's essentially what Boost's pooled memory manager does. Their
idea is not to deallocate and not to reuse, but instead just keep
giving you new pieces and deallocate them all at once at the end, when
you don't need any of them any more.

V

 

[cppquester]

I just had the following idea for opertor new and delete

(I am sure I am not the first one, haven't seen it
so far though): [code snipped]
void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();

Don't you mean used.top()?
yes.

used.pop();
return res;
}

[code snipped]

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?

One obvious thing that you should gain is the protection from memory
fragmentation (which is really a big performance gain), the same method can
be (and is) implemented using placement new

So my suggestions will lead to fragmentation? But still better than
standard new, isn't it?
Do you have a link to a aolution with placement new?

 

[Joe Greer]

(e-mail address removed) wrote in @r29g2000hsg.googlegroups.com:

Hi Folks,

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though):

class A
{
std::vector< int> someData;

static std::stack used;

You need to give a type here.

public:
static void * operator new (size_t size);
static void operator delete (void *p, size_t size);
};

void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();
used.pop();
return res;
}

return ::new( sz);
}

void A:perator delete (void *p, size_t sz)
{
someData.clear();
used.push( p);
}

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?
Of course it is obvious that there is a certain memory overhead (for
the stack and as all As are never freed), but it looks to me that this
is a very easy way to gain a lot of performance potentially. Am I
missing something?

At first I didn't understand the point of someData, but now I think I
do. What you really want to do with your delete operator is:

void A:perator delete(void *p, size_t sz)
{
static_cast<A*>(p)->~A();
used.push(p);
}


The difference is that you invoke the class' destructor instead of
trying to hand code everything.

The problem with this approach is thread safety. If you are writing a
multi-threaded application, you will need to protect the queuing
operations and that will give you back your OS hit.

This kind of allocator will help you if you have objects which will have
lots of creations a deletes (thousands) in the lifetime of the
application. In that particular case, this type of allocator will help
with memory fragmentation issues and may help in speed. Most of my
programming is multi-threaded, so I don't really see a performance
improvement except for as a whole because the memory isn't quite so
fragmented.

In order to see a performance increase, you will want to be sure that
most of the time, a previously deleted object will be waiting for reuse.
If your program is truly single threaded, you might consider just
reusing the existing object instead of going through a reallocation
cycle.

Hope my observations help in some way,
joe

 

[Alf P. Steinbach]

* Joe Greer:

(e-mail address removed) wrote in @r29g2000hsg.googlegroups.com:


You need to give a type here.


At first I didn't understand the point of someData, but now I think I
do. What you really want to do with your delete operator is:

void A:perator delete(void *p, size_t sz)
{
static_cast<A*>(p)->~A();
used.push(p);
}

Considering that original code would not compile, it isn't necessarily
bad to introduce additional undefined behavior.

However, the OP and other readers may get the impression that the above
would be a good idea.

So, to correct that impression: it's just Undefined Behavior, the object
has already been destroyed.

Cheers, & hth.,

- Alf

 

[cppquester]

Thanks for your reply (same to all other repliers as well!)

The general idea is called a free-list or, with more sophisticated
management, a cache. And what you're missing is, first, that std::stack
itself uses dynamic allocation,

so what?
For me only performance gain is what counts.
(plus I might use a std::vetor with reserve() in the end)

and second, that in operator delete you
don't have access to instance member data (the instance has already been
destroyed),
Ok.

and third, that a free-list is based on a certain usage
pattern (otherwise it just adds overhead),

As I said, frequent allocation/deallocation (no persistent objects).

and fourth, that defining
operator new and operator delete is very costly in that it prohibits
other possibly more important usages of that mechanism,

Don't get this one: Better no improvement than a reasonable one just
because there is a possible even better one (which then might never be
done in the end because it is way more complicated)?

and fifth, that
it's generally not a good idea to do micro-optimization. In short don't
do it, or at least, don't do it yet (for optimization, first measure!).

I did some. Much of the time is indeed spend on operator new/delete.
(But before actually implementing my idea I thought it is wise to get
some
advice to maybe even make it better - or let it even be if I will be
conviced that the idea wasn't that good in the end).

 

[cppquester]

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though):

class A
{
std::vector< int> someData;

static std::stack used;

public:
static void * operator new (size_t size);
static void operator delete (void *p, size_t size);
};

void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back();
used.pop();
return res;
}

return ::new( sz);
}

void A:perator delete (void *p, size_t sz)
{
someData.clear();
used.push( p);
}

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?
Of course it is obvious that there is a certain memory overhead (for
the stack and as all As are never freed), but it looks to me that this
is a very easy way to gain a lot of performance potentially. Am I
missing something?

The idea, as I understand it, is not to deallocate the last "freed"
instance but to reuse it. Seems nice to have the freeing delayed,
and that's essentially what Boost's pooled memory manager does. Their
idea is not to deallocate and not to reuse, but instead just keep
giving you new pieces and deallocate them all at once at the end, when
you don't need any of them any more.

I think I cannot use a pool here because I do not know the peak memory
amount used. Some objects might have a very short life span, others
might
exist almost for the whole runtime.

 

[Alf P. Steinbach]

* (e-mail address removed):

Thanks for your reply (same to all other repliers as well!)


so what?
For me only performance gain is what counts.
(plus I might use a std::vetor with reserve() in the end)

Think about it.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Thanks for your reply (same to all other repliers as well!)


so what?
For me only performance gain is what counts.
(plus I might use a std::vetor with reserve() in the end)

Even vector with reserve() is not safe, should you ever over-allocate it
will re-allocate and you're in deep shit, so to speak. To do it
correctly you must allocate raw memory and do the book-keeping yourself.

One way to do it would be to allocate chunks of data sized to be a
multiple of the size of the objects, say 10 to 50. Then you keep track
of how many objects you have in each chunk. When all are full you
allocate a new one and start filling it. The idea is that when you start
deallocating the objects you'll end up with empty chunks which can then
be deallocated.

For some usage patterns this will end up with lots of chunks with one
object in each, but never more chunks than needed to hold the maximum
number of objects used.

 

[Abdo Haji-Ali]

Hi Folks,

I just had the following idea for opertor new and delete
(I am sure I am not the first one, haven't seen it
so far though): [code snipped]
void* A:perator new(size_t sz)
{
void* res;
if( used.size() > 0)
{
res = used.back(); Don't you mean used.top()?
used.pop();
return res;
}

[code snipped]

If there are a lot of instances of A to be allocated and freed all the
time,
could (would) this result in a performance gain compared to
the standard new/delete operator as system calls are avoided in most
cases?

One obvious thing that you should gain is the protection from memory
fragmentation (which is really a big performance gain), the same method can
be (and is) implemented using placement new

Abdo Haji-Ali
Programmer
In|Framez

 

[Abdo Haji-Ali]

So my suggestions will lead to fragmentation? But still better than
standard new, isn't it?
Do you have a link to a aolution with placement new?

On the contrary, what I meant is that the main advantage of a memory pool
(something like what you're doing) IS the *protection* from memory
fragmentation.
For samples, google for "C++ memory pool". This should return a few hundred
of thousands results

Abdo Haji-Ali
In|Framez
Programmer

 

[Joe Greer]

Considering that original code would not compile, it isn't necessarily
bad to introduce additional undefined behavior.

However, the OP and other readers may get the impression that the above
would be a good idea.

So, to correct that impression: it's just Undefined Behavior, the object
has already been destroyed.

Good point, I was focusing too much on the OP's code and not enough on what
was actually happening.

joe