Dynamic Memory Allocation (maps)

[ajtgarber]

http://pastebin.com/XQEpni3d DynamicTileArray.h
http://pastebin.com/0Z1zTnN0 DynamicTileArray.cpp

(allocation & deallocation are being done with malloc() and free())

Okay, recently I've been trying to make a map class that allows you to make a dynamically sized map (rather than locking you into some maximum). When I run the program my main creates a new Map object, and sets every tile in the map to a "null tile". When I tell the program to make a map 32x32, it gets to (0, 10) before it needs to allocate more memory (the map defaults at 10x10), as it allocates more memory it copies the values from the original array into the new array. When it gets to (1, 0) the program crashes with these messages:

*** glibc detected *** ./Editor: free(): corrupted unsorted chunks: 0x000000000136f430 ***
======= Backtrace: =========
/lib/libc.so.6(+0x775b6)[0x7fd8b1bdd5b6]
/lib/libc.so.6(cfree+0x73)[0x7fd8b1be3e83]
/usr/lib/libSDL-1.2.so.0(+0x106b9)[0x7fd8b2aca6b9]
/usr/lib/libSDL-1.2.so.0(SDL_WaitThread+0x31)[0x7fd8b2aca701]
/usr/lib/libSDL-1.2.so.0(+0x586a1)[0x7fd8b2b126a1]
/usr/lib/libSDL-1.2.so.0(+0x10f85)[0x7fd8b2acaf85]
/usr/lib/libSDL-1.2.so.0(SDL_QuitSubSystem+0x75)[0x7fd8b2ac1815]
/usr/lib/libSDL-1.2.so.0(SDL_Quit+0xe)[0x7fd8b2ac187e]
/usr/lib/libSDL-1.2.so.0(+0x810f)[0x7fd8b2ac210f]
/lib/libc.so.6(+0x33af0)[0x7fd8b1b99af0]
./Editor[0x4026f6]
./Editor[0x402a2b]
./Editor[0x4055a0]
./Editor[0x403f70]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7fd8b1b84c4d]
./Editor[0x401f19]
======= Memory map: ========
00400000-0040b000 r-xp 00000000 08:02 21234031 /home/ajtgarber/Desktop/Editor_Broken/Editor
0060a000-0060b000 r--p 0000a000 08:02 21234031 /home/ajtgarber/Desktop/Editor_Broken/Editor
0060b000-0060c000 rw-p 0000b000 08:02 21234031 /home/ajtgarber/Desktop/Editor_Broken/Editor
012f8000-0139d000 rw-p 00000000 00:00 0 [heap]
7fd8a4000000-7fd8a4021000 rw-p 00000000 00:00 0
7fd8a4021000-7fd8a8000000 ---p 00000000 00:00 0
7fd8a8310000-7fd8a8311000 ---p 00000000 00:00 0
7fd8a8311000-7fd8a8b11000 rw-p 00000000 00:00 0
7fd8ac9e4000-7fd8ac9e6000 rw-p 00000000 00:00 0
7fd8ac9e6000-7fd8acb12000 rw-s 00000000 00:04 230326304 /SYSV00000000 (deleted)
7fd8acb12000-7fd8acb17000 r-xp 00000000 08:02 3936358 /usr/lib/alsa-lib/libasound_module_pcm_pulse.so
7fd8acb17000-7fd8acd16000 ---p 00005000 08:02 3936358 /usr/lib/alsa-lib/libasound_module_pcm_pulse.so
7fd8acd16000-7fd8acd17000 r--p 00004000 08:02 3936358 /usr/lib/alsa-lib/libasound_module_pcm_pulse.so
7fd8acd17000-7fd8acd18000 rw-p 00005000 08:02 3936358 /usr/lib/alsa-lib/libasound_module_pcm_pulse.so
7fd8acd18000-7fd8acd1e000 r-xp 00000000 08:02 3935738 /usr/lib/libogg.so.0.6.0
7fd8acd1e000-7fd8acf1d000 ---p 00006000 08:02 3935738 /usr/lib/libogg.so.0.6.0
7fd8acf1d000-7fd8acf1e000 r--p 00005000 08:02 3935738 /usr/lib/libogg.so.0.6.0
7fd8acf1e000-7fd8acf1f000 rw-p 00006000 08:02 3935738 /usr/lib/libogg.so.0.6.0
7fd8acf1f000-7fd8acf4b000 r-xp 00000000 08:02 3935979 /usr/lib/libvorbis.so.0.4.3
7fd8acf4b000-7fd8ad14a000 ---p 0002c000 08:02 3935979 /usr/lib/libvorbis.so.0.4.3
7fd8ad14a000-7fd8ad14b000 r--p 0002b000 08:02 3935979 /usr/lib/libvorbis.so.0.4.3
7fd8ad14b000-7fd8ad14c000 rw-p 0002c000 08:02 3935979 /usr/lib/libvorbis.so.0.4.3
7fd8ad14c000-7fd8ad30f000 r-xp 00000000 08:02 3935981 /usr/lib/libvorbisenc.so.2.0.6
7fd8ad30f000-7fd8ad50f000 ---p 001c3000 08:02 3935981 /usr/lib/libvorbisenc.so.2.0.6
7fd8ad50f000-7fd8ad526000 r--p 001c3000 08:02 3935981 /usr/lib/libvorbisenc.so.2.0.6
7fd8ad526000-7fd8ad527000 rw-p 001da000 08:02 3935981 /usr/lib/libvorbisenc.so.2.0.6
7fd8ad527000-7fd8ad570000 r-xp 00000000 08:02 3934964 /usr/lib/libFLAC.so.8.2.0
7fd8ad570000-7fd8ad770000 ---p 00049000 08:02 3934964 /usr/lib/libFLAC.so.8.2.0
7fd8ad770000-7fd8ad771000 r--p 00049000 08:02 3934964 /usr/lib/libFLAC.so.8.2.0
7fd8ad771000-7fd8ad772000 rw-p 0004a000 08:02 3934964 /usr/lib/libFLAC.so.8.2.0
7fd8ad772000-7fd8ad789000 r-xp 00000000 08:02 19136617 /lib/libnsl-2.11.1.soAborted

I've narrowed the crash down to line 46 in DynamicTileArray.cpp but I'm not sure whats causing it. The memory seems to have been allocated just fine, and I believe I have my array setup properly.
Can someone help me figure out what I'm doing wrong?

[bnpph]

First off, change:

Code: Select all

DynamicTileArray();
DynamicTileArray(int width, int height);

To

Code: Select all

DynamicTileArray(int width = 10, int height = 10);

This is wrong:

Code: Select all

(Tile*)malloc(sizeof(Tile*)*10);

sizeof(Tile*) is the size of a pointer - which will be 4 bytes on x86. You want sizeof(Tile) instead.
Also, sizeof(Tile**) should be sizeof(Tile*)

Code: Select all

        //copy over existing tiles from the previous array
        for(int i = 0; i < width; i++) {
                for(int j = 0; j < height; j++) {
                        cout << "DynamicTileArray::allocateSpace copying: " << i << ", " << j << endl;
                        //it dies here (t1 and t2 are just here to see what is broken) 
                        Tile t1 = myArray[i][j];
                        cout << "DynamicTileArray::allocateSpace test2" << endl;
                        Tile t2 = tiles[i][j];
                        myArray[i][j] = tiles[i][j];
                }
        }

Use memcpy. The compilers can optimize it much better, and it is much shorter.

There are a lot of other little problems, but those are some that stand out.


Also, you should rethink your design. First off, why does it need to be resizable? You can get much better performance if you make it a set size from when it is constructed. Second, do you really want to combine too many features into functions? For example, your setTile function can call the allocateSpace function, when really it should throw an error or be undefined when passing values into it that are out of bounds - have a "isInBounds(int, int)" function and let the programmer decide what to do when he uses it.

[Falco Girgis]

Yeah, you are going to be getting SEVERE performance penalties for using a map in your design. This is absolutely the WORST data structure for the task at hand...

What's wrong with a static array? It's going to be 1000x faster and faster.

[ajtgarber]

I've changed the sizeof(Tile**)'s to sizeof(Tile*) and the sizeof(Tile*) (from before) to sizeof(Tile). Its still crashing at the same point, this time instead of the whole mess of messages,
its giving me the "Segmentation Fault". I wanted to have the dynamic memory in the map so that if someone only wanted a small map they could do so without it taking more resources than it needed, and if they
wanted an obscenely large map they could do so. Would it be better if I made this dynamic map something large in the beginning (like you would with the static array) and after they pass that point start allocating
more memory? Or should I just drop the dynamic memory all together? (I'm partially doing this for the reasons above, and also to get more familiar with it)

As for the methods doing more than one thing at once, I'll be working on that later this evening. Thanks for pointing it out

[Falco Girgis]

EDIT:

Oops! I don't know what the fuck I was thinking... I thought you said you were using a std::map to store your map... nevermind what I said. It's not going to be a billion times slower. Make sure to use memcpy, as bnpph said.

My bad.

[bnpph]

I've changed the sizeof(Tile**)'s to sizeof(Tile*) and the sizeof(Tile*) (from before) to sizeof(Tile). Its still crashing at the same point, this time instead of the whole mess of messages,
its giving me the "Segmentation Fault".

Hm, that is strange. Are you sure your malloc calls are returning an actual pointer? Does your Tile class have any copy constructors? Also, try replacing malloc with realloc in your resize method.

I wanted to have the dynamic memory in the map so that if someone only wanted a small map they could do so without it taking more resources than it needed, and if they
wanted an obscenely large map they could do so. Would it be better if I made this dynamic map something large in the beginning (like you would with the static array) and after they pass that point start allocating
more memory? Or should I just drop the dynamic memory all together? (I'm partially doing this for the reasons above, and also to get more familiar with it)

Anything that uses new/malloc (or other variants) is dynamic memory - it is fine to only have it in the constructor, and not make it resizable. You need to decide what uses of the class need to run at their fastest If the use of resizing it is done infrequently and does not need to run fast, then you can change the layout of the memory to get faster access speed, but slower resize speed.

[ajtgarber]

My malloc calls are returning pointers (my last run gave me: 0xba2940, 0xbfa310. Not that thats helpful or anything). My Tile class currently does not have a copy constructor, if I'm using memcpy would I need it?
Is there any way to check if my program has access to a pointer?

EDIT:

Oops! I don't know what the fuck I was thinking... I thought you said you were using a std::map to store your map... nevermind what I said. It's not going to be a billion times slower. Make sure to use memcpy, as bnpph said.

My bad.

Sorry about that, I guess I wasn't very clear when I originally posted. Hooray it won't have fail performance (well.. hopefully anyway )!

[short]

Your program has access to any pointer malloc returns. If you try to get a specific memory address, (based on obscure rules of your OS) I think the OS will come in and bitch slap you. You could look it up though.

if I'm using memcpy would I need it?

memcpy is a C function, there's absolutely no need for a copy constructor.

The header for memcpy is so:

Code: Select all

void * memcpy ( void * destination, const void * source, size_t num );

so just pass it two addresses and the size of what the memory is your copying.