Automatic Versus Dynamic

[mike.m.schmidt]

Hello,

I've been trying to optimize a piece of code that executes in 6
milliseconds. From what I have read, dynamically managing memory with
new/malloc and delete/free is less efficient than using the stack to
store variables. Part of my 6 ms code calls delete on class pointers
more than 20000 times. I changed the code to store the class
instances on the stack instead of the heap, so the class's destructor
is called but not delete. Unfortunately, the execution time is still
6 ms.

Does anyone know what is happening? Is automatic storage really more
efficient than dynamic storage?

Any help would be greatly appreciated.

Thanks,
Mike

 

[Gianni Mariani]

Hello,

I've been trying to optimize a piece of code that executes in 6
milliseconds. From what I have read, dynamically managing memory with
new/malloc and delete/free is less efficient than using the stack to
store variables. Part of my 6 ms code calls delete on class pointers
more than 20000 times. I changed the code to store the class
instances on the stack instead of the heap, so the class's destructor
is called but not delete. Unfortunately, the execution time is still
6 ms.

Stack based objects get deleted automatically as they go out of scope.
I think you're still "deleting" everything.

Does anyone know what is happening? Is automatic storage really more
efficient than dynamic storage?

Any help would be greatly appreciated.

Memory allocators are quite zippy nowadays.

Have you run a profiler on your code?

 

[Michael DOUBEZ]

(e-mail address removed) a écrit :

Hello,

I've been trying to optimize a piece of code that executes in 6
milliseconds. From what I have read, dynamically managing memory with
new/malloc and delete/free is less efficient than using the stack to
store variables.

There is an overhead in requesting memory from the system and object are
more likely to be in the cache when on the stack.

Part of my 6 ms code calls delete on class pointers
more than 20000 times.

Do you mean you call delete on members of a class ? If that's the case,
putting the objects on the stack won't change anything.

I changed the code to store the class
instances on the stack instead of the heap, so the class's destructor
is called but not delete.

The delete is called automatically when the object goes out of scope.

Unfortunately, the execution time is still 6 ms.

If you really need object allocated dynamically inside your class, you
could try to reuse the memory or using a pool allocator (IIRC boost
provides one and there is a gnu extension).

Does anyone know what is happening?

Without seeing your code and without profiling: no. Perhaps the
allocation is not the bottleneck.

Is automatic storage really more efficient than dynamic storage?

Yes but perhaps it doesn't modify your program's performances. Profile
it to be sure.

 

[mike.m.schmidt]

Do you mean you call delete on members of a class ? If that's the case,
putting the objects on the stack won't change anything.

I should have added that object allocation is not included in the
timing. I was calling delete, but now the class member is
automatically allocated.

Used to have:
class foo
{
....
bar *b;
};

foo::~foo()
{
delete b;
}

Now I have:
class foo
{
....
bar b;
};

foo::~foo()
{
}

In both cases, bar's destructor is called, but the underlying memory
management is different.

The delete is called automatically when the object goes out of scope.

'delete' is not called when an automatically allocated object goes out
of scope; the object's destructor is called.

I need to know exactly what happens when the delete operator runs on a
dynamically allocated object. I've read that the memory is pushed
onto the free list and adjacent free blocks are coalesced into one
larger block. On the other hand, when an object on the stack is
destroyed, the stack pointer is simply adjusted. Therefore, objects
on the stack should take less time to clean up, but that is not
reflected in my timing values. I'd like to know why.

Thanks,
Mike

 

[Andre Kostur]

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

I need to know exactly what happens when the delete operator runs on a
dynamically allocated object. I've read that the memory is pushed
onto the free list and adjacent free blocks are coalesced into one
larger block. On the other hand, when an object on the stack is
destroyed, the stack pointer is simply adjusted. Therefore, objects
on the stack should take less time to clean up, but that is not
reflected in my timing values. I'd like to know why.

Magic. What happens when delete is called is magic. Assuming the standard
new and delete, all you can say is that after delete, the memory that was
deleted has been returned to the free store. Precisely how the free store
is managed is an implementation detail, and you'll have to consult your
compiler/OSes documentation.

 

[Michael DOUBEZ]

(e-mail address removed) a écrit :

I should have added that object allocation is not included in the
timing. I was calling delete, but now the class member is
automatically allocated.

Used to have:
class foo
{
...
bar *b;
};

foo::~foo()
{
delete b;
}

Now I have:
class foo
{
...
bar b;
};

foo::~foo()
{
}

In both cases, bar's destructor is called, but the underlying memory
management is different.

Yes, b is allocated on the stack then.

'delete' is not called when an automatically allocated object goes out
of scope; the object's destructor is called.

Yes. That is what I meant.

I need to know exactly what happens when the delete operator runs on a
dynamically allocated object. I've read that the memory is pushed
onto the free list and adjacent free blocks are coalesced into one
larger block. On the other hand, when an object on the stack is
destroyed, the stack pointer is simply adjusted. Therefore, objects
on the stack should take less time to clean up, but that is not
reflected in my timing values.

It is expect but ...

I'd like to know why.

.... perhaps it is not significant for your program.
Profile your program to see where it is spending time.

 

[Puppet_Sock]

I've been trying to optimize a piece of code that executes in 6
milliseconds.  From what I have read, dynamically managing memory with
new/malloc and delete/free is less efficient than using the stack to
store variables.  Part of my 6 ms code calls delete on class pointers
more than 20000 times.  I changed the code to store the class
instances on the stack instead of the heap, so the class's destructor
is called but not delete.  Unfortunately, the execution time is still
6 ms.

Does anyone know what is happening?  Is automatic storage really more
efficient than dynamic storage?

Any help would be greatly appreciated.

Gonna be a bit snarky here first. It is so frequent that
people want things faster, but they don't really have a
good reason for it, that it's worth badgering you with
the "have you checked the power cord is plugged in" questions.

Ok, ask a prior question here. Is this 6 ms code actually
worth worrying about? As somebody else asked, have you
profiled your code to see that this 6 ms actually is
where your code is spending a signficiant amount of time?
Or should you be worrying about the other parts of your
app that may be using the time?

Presuming all those come up with "yes I need optimiizing"
then go forward.

20,000 calls to delete in 6 ms? Are you sure there is any
room for "optimizing?" That's like 0.3 micro seconds per
delete, not including any actual work for the code.

Ok, you need to optimize. How fast would be fast enough?
If you don't have any spec for that, what are you doing?
"I want it faster" isn't a spec. It's a plea for that
pony you never had as a kid.

Maybe what you need is a petting zoo?

Ok, you are still here wanting to optimize.

First, consider whether a tweak of algorithm isn't
the best way to go. Maybe you can reduce the number
of objects you really allocate/deallocate? Maybe
you can cut depth of some tree or something?

Before you make your algorithm really complicated
to make it faster, revisit those "is this optimization
really necessary" questions. If you decide a more
complicated algorithm is the right path, make sure
you document it clearly so you will be able to
understand what is going on in six months or a year
when you come back to this code.

And make sure you time it before you switch.

There are ways to manage memory other than grabbing
and giving back objects. What is the maximum number
of objects you need at one time? Is it 20,000? If it
is some much smaller number, consider what the level
of effort of the ctor and dtor of each object is.

If the actual construction work is not very large,
maybe you can do something like so:
- Allocate a bunch of objects. Maybe in a vector.
- Construct them as required. Look up the "named
constructor idiom" for guidance.
- Destruct them as needed.
- Do not deallocate the memory until you are done.
- When you stop needing a particular object, keep
track that it has become available. When you need
a new one, select it from the available ones.
What scheme you use to do this will depend on
the order you acquire and give back objects.
- When you are finished, use normal dtor procedures
to give back all the resources associated.

But! Be sure to time this scheme with representative
sample data before you adopt it. It is quite possible
it will be slower than the usual thing, especially
if the construction effort for each object is large.

If you really need 20,000 objects all at once, maybe
what you want is to allocate all the objects at once.
Again, maybe in a vector. Then you can access them
with just an integer. Possibly (though again, time it
before you switch) allocating a block of 20,000 objects
will be faster than allocating 20,000 individual
objects one at a time. Again, you may need the "named
constructor idiom."
Socks

 

[James Kanze]

[..]
I need to know exactly what happens when the delete operator
runs on a dynamically allocated object. I've read that the
memory is pushed onto the free list and adjacent free blocks
are coalesced into one larger block. On the other hand,
when an object on the stack is destroyed, the stack pointer
is simply adjusted. Therefore, objects on the stack should
take less time to clean up, but that is not reflected in my
timing values. I'd like to know why.

There is a function called 'deallocation function', which the
what the global operator delete is usually called, I think.
The statement with the 'delete' operator for a single object
(not an array) has two steps, it calls the object's destructor
and then calls the deallocation function. It's a bit
simplified, for more read the Standard, [expr.delete].

What the deallocation function does under the covers is
implementation-defined. Whether "the memory is pushed", or
"adjacent blocks are coalesced" is not defined by the language
itself. Perhaps you need to see the documentation for your
compiler/library to get a better idea of what's really going
on behind the covers. Of course, you can also redefine the
operators 'new' and 'delete' for your class and the overloaded
'delete' is going to be called instead of the 'deallocation
function' (or, rather, it will be the deallocation function in
that case).

You seem to be saying that you see no difference if the object
is dynamic or automatic. Perhaps your timing mechanism needs
to have higher resolution?

Or perhaps the cost of dynamic allocation is negligible compared
to other things he's doing. (A single allocation and free are
certainly negligible compared to 6ms.) Or perhaps he's just
encountered a case where allocation is particularly
fast---allocating and freeing the same block over and over, with
no intervening allocations or frees, can be very cheap in some
allocators.