views:

188

answers:

13

Hei community,

I've got a small question concerning the deletion of pointers.

I am working with pointer-to-pointer matrices of Dimension 1024x1024. Since I am creating them dynamically, I delete the allocated space for them at the end of the program. But doing this in the usual loop costs quite a lot of time - I measured about 2sec using the clockrate of the processor. And 2 Seconds is HUGE when the program runs only 15 seconds - plus: the function using these allocated pointers is called more than only once... .

Here is the measured time-critical piece of code including the measurement:

time=clock();
for(i=0;i<xSize;i++){            //xSize is dynamic, but 1024 for the measurement
    delete [] inDaten[i];
    delete [] inDaten2[i];
    delete [] copy[i];
}
delete inDaten; delete inDaten2; delete copy;
time=clock()-time;
     time/=CLOCKS_PER_SEC;

Is deleting pointers ALWAYS that long? Or am I just doing things the wrong way?

I hope someone here can help me out with that. Since I am optimizing a quite complex programm to run faster, I can't use those 2sec-piece of code. It is just way TOO slow compared to all the other parts. But still I need to be able to implement this code dynamically. SmartPointers could be helpful, but if I understand correctly, they also need the time to delete themselves - just at a different time...

Thanks for your answers!

Baradrist

EDIT: I just found out, that measuring these delete-computations is quite slow because I didn't compile it in release-mode. Since the debugger comes into play, I measured these (in the end unreal) numbers that got me a headache. The final program optimizes automatically enough so that there is nearly no time involved in the deletion any more.

Anyways: thanks for all the helpful answers! They got me a lot of extra-knowledge and things to think about!!!!

A: 

Cant you just use

delete [] yourpointer;
ckv
How is this applicable here?
sharptooth
+3  A: 

delete[] will also call destructors for each element of the array which adds time unless the destructor is trivial.

Other than that - yes, dynamic memory allocation is relatively costly. If you can't tolerate it - try to allocate less blocks of larger size or go without dynamic allocation in time-critical stuff.

Smart pointers won't help much - they will do the same deallocation inside. They are not for speedup, but for design convenience.

sharptooth
+1  A: 

If you delete them at the end of the program and it doesn't matter wheter destructors are run, simply leave out the deletion—the memory will be deallocated by the OS. Otherwise, try to use single indirections, i.e., no pointer-to-pointer arrays. Apart from reducing deletion time, this will also improve locality of reference.

Philipp
There is no guarantee that the OS will free any memory at all.
Yacoby
@Yacoby: unless the OS itself gives such a guarantee. Which any modern (desktop) OS does.
jalf
Regardless of whether or not the OS cleans up the process memory at exit, it's still bad practice to rely on such a crutch. Better to use an allocator that is better suited for fast deallocation, and/or redesign the code to minimize deallocation (without introducing leaks, of course).
Void
@Void: AFAIK all modern garbage-collected runtime environments rely on this behavior, and they are designed to introduce leaks if it increases performance.
Philipp
+2  A: 

Here is an interesting thread "Memory Allocation/Deallocation Bottleneck?"

Allocation and deallocation take a long time and thus are one of the most common costly operations you have. This is because the heap management has to take care of a bunch of things. Usually there are also more checks on the memory blocks in debug mode. If you have the same time in release configuration I would be surprised, usually there is a factor in between of at least 2. With a private heap you can increase the things dramatically. If you allocate always objects of the same size then a memory pool could be the best alternative.

jdehaan
A: 

Try creating your own memory allocation methods so that you can reduce the destruction time.

For example request a block of memory from Os and allocate the array to it so that you can free the entire block in a single operatin.

Prav
A: 

It looks like the problem is in the structure of your data. Why do you need so many dynamic allocations? What can be done to reduce the number of allocations?

If freeing the pointers takes 2 seconds, it likely takes at least as much to allocate them.

Freeing them can be avoided just by exiting the program early. C++ makes no guarantees about what will happen with the allocated memory then, but your OS probably does, so in practical terms, it might be an easy way to shave 2 seconds off the execution time.

But that still leaves the > 2 seconds for the allocations.

Your best bet is to try to structure the data better, I think. Can you show us how the matrix is structured currently?

jalf
Using 1-dim matrices saves the time! You are right concerning the structure. The matrices contain greyscales of pinctures (so 1024x1024 etc).But still: the allocation is way faster than the deallocation (measured-wise)
Baradrist
A: 

Thanks a LOT for all the fast answers!!! It's nice to see that there is someone out there helping =). Still for my problem it seems like I have to deal with this loss of time, since I need the dynamic arrays as temporary-matrices in smaller sub-programs that are not performed at the end.

Anyways: again THANKS!! And have a nice day!

Baradrist

Baradrist
Using one-dimensional matrices should do the trick - thanks!
Baradrist
A: 

If the objects pointed to in your arrays have non-trivial destructors there is not much you can do to significantly improve runtime without addressing that first. Otherwise:

Instead of making inDaten, inDaten2 and copy arrays of size isize of pointers to arrays of size isize why not make them arrays of size isize*isize and instead of addressing individual items with : array[i][j] address them with array[i*isize+j]. That way you can clean up with one call to delete [].

jilles de wit
+1  A: 

Shouldn't this be:

delete [] inDaten; delete [] inDaten2; delete [] copy;

because as used, they are obviously arrays. (At least they appear too be, you didn't provide quite enough context).

xcramps
Yes, it should be - already changed it, but it doesnt change the time-numbers =).
Baradrist
A: 

An optimization for this is to allocate memory in chunks, allocate individual pointers with placement new and upon deletion just delete the whole chunk.

You will have to be careful though, as this option implicitely does not call the destructor for each object allocated with placement new.

utnapistim
A: 

You don't say how large the objects in the arrays are, but if they're sufficiently large, it's possible that part of the memory got swapped out and needed to be swapped back in (or possibly just remapped back into process space), and that's causing the time you're seeing.

Mark B
A: 

If you've determined the memory allocations/deallocations to be the bottleneck and want this to be faster, the first obvious solution is to use a contiguous buffer for your arrays. You can still provide a matrix interface which accesses them like two-dimensional arrays.

// Rudimentary Implementation
template <class T>
class SquareMatrix
{
public:
    explicit SquareMatrix(int i_size): 
        size(i_size), mat(new T[i_size * i_size]) {}

    ~SquareMatrix()
    {
        delete[] mat;
    }

    // could also be column depending on row-major/col-major
    T* operator[](unsigned int row)
    {
        return mat + row * size;
    }

    // could also be column depending on row-major/col-major
    const T* operator[](unsigned int row) const
    {
        return mat + row * size;
    }

private:
    unsigned int size;
    T* mat;
};

The second obvious thing to do is, instead of three matrices, have one matrix composed of a structure which has all the data you need. This is assuming that one matrix of tuples will suffice which seems to be the case with the code you posted.

If you really want to go hardcore and require multiple matrices, then write your own memory allocator for this. You could allocate memory for multiple matrices at once and simply construct them using placement new. Some further reading and study is required if you want to do this as writing memory allocators is not a trivial task: you need to consider issues like alignment, but that's the fastest way to go.

I recommend that you still grab a profiler rather than relying on timing tests and do a proper call graph analysis of your code. This will tell you exactly how much time is being spent where. It could be that the construction/destruction of the objects in your matrices is not as cheap as it could be, for example.

Short of obvious algorithmic inefficiencies, even extremely knowledgeable programmers are often incorrect about the bottlenecks in their code. The profiler is your best friend if efficiency is a major concern.

A: 

If all the objects referenced by the pointers in your matrix are the same type (or at least the same size), you could allocate one large chunk of memory to hold them all and initialize them in-place.

Jen