C Specific question

Member
Posts: 241
Joined: 2008.07
Post: #1
I think I am doing this right but I have a question about something in C specifically.

Does the malloc() function have a void* internally that it uses to point to the memory allocated along with an unsigned int (or whatever) to remember the length of the allocated memory?

I'm wondering, how does it know how much memory to free? The only thing I can figure is it finds the pointer in its list or whatever structure it uses and references it to know how much memory to deallocate.

Here's my code:

Code:
MyObjectiveCClass*** triplePointerBabyYeah;
triplePointerBabyYeah = malloc(numCols * numRows * sizeof(MyObjectiveCClass*));

for(int i=0;i<numCols;i++)
{
     for(int j=0;j<numRows;j++)
     {
          triplePointerBabyYeah[i][j] = [[MyObjectiveCClass alloc] init];
     }
}

The reason I'm doing it like that isn't important. My concern is that all the memory is being deallocated when I'm done. I'm unsure because although I had to tell it how much to allocate, I don't have to tell it how much to deallocate.

Code:
free((void*)triplePointerBabyYeah);

Also, I don't need to dereference it in the free call, do I?

Code:
free((void*)(*triplePointerBabyYeah));

Thanks for any comments! Smile
Quote this message in a reply
Member
Posts: 194
Joined: 2009.02
Post: #2
I believe malloc creates a struct in the memory right before the first address of your newly allocated memory. The struct contains the size of the allocation but no pointer since it knows where it is in relation to the structs memory location. So no, you don't need to specify size to free(), and there's no need to dereference your pointer in the free() call.
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #3
Thank you very much, that's the exact answer I was looking for. Thanks for confirming it for me. You rock! Grin
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #4
How malloc does things is the least of your worries with that code Wink

You can't do foo*** bar = malloc(x*y*sizeof(void*)) and then treat it like a two dimensional array of foo*.

But I guess you already figured that out because it crashed. Rule of thumb is that every indirection (or dimension, or "*") needs its own allocation and initialization, if you want to create a multidimensional array. So in this case, you'd also need to alloc an addition array of size x*sizeof(void*) or y*sizeof(void*), and init them correctly to point to the rows/columns of the big malloc(), before you can do foo[i][j] = baz.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #5
How about just doing:
Code:
MyObjectiveCClass** notATriplePointerBabyYeah;
notATriplePointerBabyYeah = malloc(numCols * numRows * sizeof(MyObjectiveCClass*));

for(int i=0;i<numCols;i++)
{
     for(int j=0;j<numRows;j++)
     {
          notATriplePointerBabyYeah[i*numCols+j] = [[MyObjectiveCClass alloc] init];
     }
}
(I'm assuming you need to use both i & j during initialization on the actual code, otherwise a simple for(int i=0;i<numCols*numRows;i++) would suffice)
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #6
malloc() doesn't necessarily have to allocate the size you requested. It may allocate extra. If you want to find out the actual allocated amount, then you can use malloc_size().

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #7
malloc_size() isn't a standard function, so don't expect it to work on all systems. The actual implementation of malloc() and free() is implementation defined, so there's no one right way to do it. There are a lot of rules it uses internally to make sure you get memory properly aligned for all major data types for your CPU, how it works with virtual memory, etc. As a programmer, though, you shouldn't worry about that, since the OS already handles all that for you. All you have to do is make sure that each malloc() is accompanied by exactly one free(), and you must pass in the exact same pointer as was returned from malloc().

Completely off topic, but I couldn't help that you just hit post 1234, Skorche. Rasp
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #8
Yep, I came back because I realized my folly. I've done this before, but it's the type of thing you just don't do every day.

Basically, what DoG said is what I ended up doing, but I figured it out before I got here. Wink

It's a triple pointer because it's a 2 dimensional array of pointers.

Code:
        Inactive*** tempDoubleArray = malloc(numCols * (numCols-2) * sizeof(Inactive*));
        for(int i=0;i<numCols;i++)
            tempDoubleArray[i] = malloc((numCols-2)*sizeof(Inactive*));

Code:
                    tempDoubleArray[i][j] = [[Inactive alloc] init];

Code:
        for(int i=0;i<numCols;i++)
            for(int j=0;j<numCols-2;j++)
                [tempDoubleArray[i][j] release];
        for(int i=0;i<numCols;i++)
            free(tempDoubleArray[i]);
        free(tempDoubleArray);

That should do it.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #9
You aren't allocating the correct amount of memory. You should be doing:
Code:
Inactive*** tempDoubleArray = malloc(numCols*sizeof(Inactive*));
for (int i = 0; i < numCols; i++)
    tempDoubleArray[i] = malloc(numRows*sizeof(Inactive*));

If each column has the same number of rows, for the most effective use of memory it would be even better to allocate a flat array of size numCols*numRows and index it by [i*numRows + j], since it only requires one allocation. However, that's an optimization and not strictly necessary.
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #10
I understand what you're talking about but how is it an optimization? Is it because the memory would be more contiguous as a single dimensional array but not necessarily so as a 2 dimensional?

The fact that we're talking about an array of pointers here anyway probably makes it not matter much anyway, but maybe. Interesting idea, thanks for the suggestion. I'll think about it.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #11
It's an optimization because you only do one allocation for the entire array instead of 1+numCols allocations (and later, a single free instead of 1+numCols) and also because with an array of arrays you need a second indirection (and a memory access) to get to your object whereas with a single array you skip that step.

Anyway, if you are happy with your structure and find it easier to use, go with it, the performance difference would likely be negligible since any Obj-C call would likely overshadow whatever cost a double indirection may incur. Personally, I wouldn't use an array of arrays to represent a 2D array, I'd only use it if I needed each column/row to be able to contain a different number of rows/columns.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #12
As PowerMacX, two reasons are requiring fewer allocations and one less dereference. Having a contiguous array also helps with cache performance, since you will have fewer cache misses. Another issue is malloc will allocate more memory than you request, since it needs to store information about the allocation and it may also allocate extra memory as padding.

None of these are critical issues, and you should make your code easier to understand before you make sacrifices to optimize for them. However, making a single array and indexing it by i*numRows + j is a relatively simple thing to do, and it has other advantages such as less effort to manage the memory (since you only need to manage 1 malloced pointer) and you only need 1 loop to visit all the elements.
Quote this message in a reply
Member
Posts: 26
Joined: 2010.01
Post: #13
To get back to the original question - how malloc() works internally is pretty implementation-dependent. Some compilers do it differently than others. However, I don't know any that use a struct adjacent to the allocated block, which is quite error-prone in the case of buffer overruns or underruns. Most implementations that I know of use something like a hash table of adresses against a small struct containing allocation size and so on, which is usually placed away from user addresses.

If you're interested, have a look for a code package called dlmalloc, which is a good fast malloc implementation sometimes used in games.
Quote this message in a reply
Post Reply