Sign in to follow this  
  • entries
    8
  • comments
    10
  • views
    7451

Busy, busy, busy...or am I?

Sign in to follow this  

232 views

So between work and studying, I haven't had much time to work on my project, now officially dubbed "Essentia." I did manage to sit down for a couple of hours yesterday and get the sprite animations up and running. I'm still polishing up the code, but the base implementation is complete at this point.

In the past I had used sprite sheets, but after some consideration it seems as though using individual images would be simpler to implement, as well as provide faster execution times. The speed increase would be due to fewer calculations and a much smaller buffer index; namely a buffer of image pointers versus multiple buffers containing the RGB values of the images themselves. Based on previous tests to pinpoint speed bottlenecks in the engine, the sole act of indexing into a large buffer seems to consume a lot of processing power. Nonetheless, even if the speed gain were negligible, the ease of implementation, as opposed to calculating the indices for the individual frames, causes the multiple image approach to be much more appealing.

So that's what I'm going to go with.

I was originally using a self-written dynamic array class (appropriately named CDynamicArray) that I had used in the past for less involved applications. Although resizing arrays is considered a costly operation, none of the additions were being made during run time, so I decided to use the structure for my sprite animation buffers. However, upon successful compilation, I immediately began to receive heap corruption errors. Initially, I had no idea what could be going wrong. Based on the debug call stack, it looked as though all of my images were being deleted prematurely. I spent a good half hour stepping through the program before I located the code causing the problem, and I'm still not sure what the source of the issue was, unless my understanding of the c++ delete[] operator is incorrect. I researched the topic, and all the documentation I found seemed to agree with my original understanding, but perhaps I am missing something - I will detail the problem below and hopefully someone here can explain.

So here goes...

My sprite class contains a CDynamicArray of pointers to objects of type CImage, which is my image class. Think of it as an array of pointers. Inside the CDynamicArray class, I had functions to take care of all the resizing and copying of elements that would have to take place each time an element was added or removed. So the InsertItem function code would look something like this:

template
void CDynamicArray::InsertItem( TYPE tItem )
{
// ... Error Checking Omitted ... //

TYPE* pTempList[] = new TYPE[m_iSize];

for( int i = 0; i < m_iSize; i++ )
pTempList = m_pItemList;

delete[] m_pItemList;

m_iSize++;

// ... Resize m_pItemList ... //
// ... Copy Old Items Into m_pItemList ... //
// ... Cleanup ... //
}


I don't have the source anymore (as I am no longer using this method), but the omitted code is irrelevant. The focus here is on the delete[] m_pItemList line in the middle. m_pItemList is an array of CImage pointers that has already been correctly initialized.

So here is where I'm confused: my understanding of the delete[] keyword is that it deletes the memory allocated to store elements, but does not delete the memory allocated to the elements themselves. For full, correct memory management, you actually have to loop through the array, prior to deleting the array itself, and delete all of the array's elements first. So in my example, the array itself should have been deleted, but the pointers should remain intact, and all of the documentation material that I found seemed to agree. If anyone knows the source of the discrepancy, by all means feel free to enlighten me, but I'm stumped at this point.

Oh well. All of this was probably for the best, because it didn't take me long to realize that I could save myself a lot of grief (and probably speed things up in the process) by simply using a std::vector in place of my CDynamicArray class. All hail the STL!

And that, my friends, is where my rambling ends. I replaced all of my previous custom structures with std::vectors, and my code now compiles and executes perfectly, and actually looks a lot cleaner as well. So if there is anything to be learned from this, it is that the standard template library is a standard for a reason, and is not to be trifled with.

I submit.

In other news, I managed to pass the ISCW on Thursday and am now only one exam away from the full CCNP and an end to the socially-decrepit, sleep-deprived life that I have subjected myself to for the last three months. This also means that within the next two weeks or so, I will able to fully devote my time to Essentia, and you fine folks will no longer be forced to listen to my error-induced rambling but will be provided quality, tangible content that should put to rest any concerns as to the validity of the claim that I am "working on it."

Until next time.
Sign in to follow this  


1 Comment


Recommended Comments

If I understand you correctly, you have this:

CDynamicArray<CImage *>


In this case, the memory belonging to the images won't be deleted when you call delete [] on the internal memory array.

The Heap Corruption could be due to other things, such as CDynamicArray not detecting accesses out of bounds, or possibly issues like failing to adhere to the rule of three.


Two efficiency notes on your implementation (you have thrown it away, but its still good to know).

The first is that std::vector<> (along with most dynamic array implementations in various languages) uses amortised growth. This means that it has two "sizes":

- The actual number of items stored.
- The total capacity.

Adding an item doesn't reallocate the internal buffer unless the capacity is reached. When the capacity is reached, the buffer size is increased by a large amount (example: double the current size). This means that adding a large number of objects to a vector won't trigger too many allocations.

The second note is that your algorithm is this:

- allocate temporary buffer
- copy original to temp
- clear original
- allocate bigger array into original
- copy temp to original
- add new item at the end
- clear temp

This can be simplified:

- allocate bigger temporary buffer
- copy original into temp
- add element to the end
- swap temp and original (*)
- delete [] temp

This also makes exception safety a bit easier to implement, because until the marked line we haven't actually modified the internal state. Notice how we save ourself a full allocation, copy, clear cycle.

You can see how std::vector<> does all this (the source is included with your compiler), however it can be difficult to trace the code because there are many oddly named auxiliary functions and interactions with the allocator etc. But it is still instructive.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now