Little guidance in memory management

**patishi** · 07-26-2014

Hi all.

I have two questions:

1. As I understand , when creating a local variable inside a function it is created on the stack, and when that specific function exits this variable is gone and the memory is freed (right so far..?).
But what happens when I return that variable from that function and use it somewhere else in the program ? like save it inside a global array for example... Is it still remaining on the stack ??

That means that If I have a very large global array that I use in my program , I should not populate it from variables I return from a function ?

for example , If I hold a very large global array of structs (so I can read from it during the program run):

Code:

struct moveList{
       int moves[7];
       int size;
};

struct moveList arr[900000]; //(is this also allocated on the stack??)

//and this next function doing some processing and returns a struct:

struct moveList getStruct(int x){
    struct movesList mList;
    //doing something...
        return mList;
}


void allocateArray(){
       int i;
       for(int i = 0; i < 900000; i++){
                arr[i] = getStruct(i);
       }
}

2. As a sequel to the previous question, where global variables get allocated ? is it on the stack too ?
If a have a global array (like in the previews example), and it is allocated on the STACK.. but all of it's members are allocated on the HEAP. what does that means ? Is there some kind of "mixing" of STACK and HEAP ? (I get a little confused)

Should I allocate such a big array on the HEAP instead ?

My biggest worry is that memory that is allocated on the heap can be a little slow to read from.. and I need very fast access to that table !! what is your recommendation ?

Thx For all info

**laserlight** · 07-26-2014

Originally Posted by patishi

1. As I understand , when creating a local variable inside a function it is created on the stack, and when that specific function exits this variable is gone and the memory is freed (right so far..?).
But what happens when I return that variable from that function and use it somewhere else in the program ? like save it inside a global array for example... Is it still remaining on the stack ??

You would be returning the value of the variable, so there is no problem. The value would be copied to that element of the array.

The problem comes when you return a pointer to a non-static local variable, not when returning a local variable.

Originally Posted by patishi

2. As a sequel to the previous question, where global variables get allocated ? is it on the stack too ?

Possibly in BSS, but these details (including concerning "stack" and "heap" memory) are implementation defined. From the perspective of C, you need to understand storage duration: local variables that are not declared static have automatic storage duration, i.e., their lifetime is limited to the block in which they are declared. Global variables (and variables declared static, including those that are local) have static storage duration, i.e., their lifetime is that of the entire program when run.

Originally Posted by patishi

Should I allocate such a big array on the HEAP instead ?

My biggest worry is that memory that is allocated on the heap can be a little slow to read from.. and I need very fast access to that table !! what is your recommendation ?

I recommend that you get it to work first. Things like improving the algorithm such that you don't need such a large array, or such that you have more optimal use of the array, will likely see more gains in efficiency than changing from the use of one area in memory to another.

**patishi** · 07-26-2014

Thx for the comment laserlight ,
This array is used as a hash table so I have no better choice.. at least nothing that I am able to think of

so it is ok if I allocate this global array on the stack (or whatever global variables are allocated..) and fill it with pointers to structs that are allocated on the HEAP ? (I assume that holding 900,000 structs on the stack is NOT a good idea

)

**laserlight** · 07-26-2014

Originally Posted by patishi

so it is ok if I allocate this global array on the stack (or whatever global variables are allocated..)

It is unlikely that a global array will be allocated on the stack.

Originally Posted by patishi

and fill it with pointers to structs that are allocated on the HEAP ? (I assume that holding 900,000 structs on the stack is NOT a good idea )

You almost certainly won't have 900000 structs on the stack if the array is global. The thing is, unless you actually are going to use most of these objects, having 900000 of them is likely to just be a waste of space. Having 900000 pointers would then be better since they can be null pointers except when the element is in use, in which case they are likely to be dynamically allocated with say, malloc, and hence most likely to be on the heap. You also need to consider how you are going to handle collisions.

EDIT:
Speaking of hash tables, have you even started on thinking about how you're going to implement it? I would have gone for that first.

**patishi** · 07-26-2014

I will be handling collisions with chaining. each index in the array (hash table) will hold a pointer to a node struct which will be the root of a linked list.
In fact, I need exactly 823,543 (7**7) entries in the table , and for that I will use a table in size 988,251 (20% bigger) or 988271 to make it a prime.

I have no choice but to handle collisions with chaining since I need all those 823,543 entries in memory (this is not a dynamic hash table where I can replace entries).. I need excess to all of them. It will be a "read only" hash table. (it will be initiated at program start)

**laserlight** · 07-26-2014

Originally Posted by patishi

In fact, I need exactly 823,543 (7**7) entries in the table , and for that I will use a table in size 988,251 (20% bigger). I have no choice but to handle collisions with chaining since I need all those 823,543 entries in memory (this is not a dynamic hash table where I can replace entries).. I need excess to all of them. It will be a "read only" hash table.

Then you can have a perfect hash table with no collisions.

**patishi** · 07-26-2014

first of all, thx again for your comments, and sorry for letting this thread slip away a little from the main subject, but this is interesting and important to me (and the main reason that I started this thread in the first place).

I think that perfect hash table will be a little tricky. I will explain:
During the program I will be eccessing the table with unique keys ,and each of those keys will be a 64 bit integer (long long type).
When initiating the table at the start of the program,I am also using 64 bit integers as keys (the same keys that I will use later to find them in the table).
what other way can I determine the right index to store this kind of key in the hash table except (key & sizeOfTable) ?

**laserlight** · 07-26-2014

So, you don't know the keys at compile time?

**patishi** · 07-26-2014

When initiating the table,I have a function that goes through all possible 7**7 combinations , and for each of those combinations it produces a unique 64 bit number.
so In the end, I will have 7**7 keys that I need to store in the table. since those keys are really big numbers (at least some of them) I need compression function that will give me the right index in the table to store them. so I just do (key % sizeOfTable) and store it there.

At program runTime, I will be needing to eccess those keys again (I have a global 64 bit number that is always changing during the program and I use it as a key to access the table).
Of course ,instead of a very large single dimension table I can have :

Code:

struct movesList *list[7][7][7][7][7][7][7];

And maybe I can somehoe find a way to eccess it this way, But it surely will take a few more steps and slower the code (since for the first solution I already have my 64 key ready, and for the second solution I need to do some processing)

**rstanley** · 07-26-2014

It is very difficult for any programmer to handle any multi-dimensional array beyond 3 dimensions. This is clearly not the solution to any problem.

**grumpy** · 07-26-2014

Originally Posted by rstanley

It is very difficult for any programmer to handle any multi-dimensional array beyond 3 dimensions. This is clearly not the solution to any problem.

That's a blanket statement and, like most blanket statements, it is false.

I don't do it every day, but I have used arrays up to five dimensions in production code for a relatively large system. Admittedly, in practice, there are usually better alternatives. And using very large arrays (multidimensional or not) is usually a sign of need for a better algorithm that doesn't require such a large array.

**MutantJohn** · 07-26-2014

Out of curiosity, is *****p slower than *p?

By that I mean,

Code:

void *****p = /* .. */;

// vs.

void *q = /* same data as p but in 1d */

I only ask because with a 5d array, you're dereferencing 5 addresses vs just 1, right? Which means that you're doing 5 reads as well, correct?

**whiteflags** · 07-26-2014

In a 5d array you are actually still using one dimension due to how automatic arrays are actually laid out. If you use pointers to simulate arrays (you actually set up memory for five different dimensions in different locations), then I don't think you have any alternative but to fetch each address until you get the data.

**grumpy** · 07-26-2014

Originally Posted by MutantJohn

Out of curiosity, is *****p slower than *p?

By that I mean,

Code:

void *****p = /* .. */;

// vs.

void *q = /* same data as p but in 1d */

I only ask because with a 5d array, you're dereferencing 5 addresses vs just 1, right? Which means that you're doing 5 reads as well, correct?

Like many things in software development, it depends.

With a true array (as opposed to a pointer that is acting like an array) the compiler can expedite certain operations so, no, there is not necessarily five pointers to be dereferenced.

More generally, however, relative performance depends on what you're doing with the array or pointers obtained from it. If you take the data from an n-dimensional array and map it into a 1D array, you wind up doing bookkeeping (mapping of n indices into 1D) to access elements. Then the relative efficiency comes down to what sequences of operations your code is doing (for example, is it a loop varying one index while holding the rest constant? do inner loops accessing a number of elements that are in a contiguous block? etc etc).

For example, there can be a significant performance difference between multiple-dereferencing a pointer 500 times to do some calculations (retrieve value, modify, write back), and multiple-dereferencing once to retrieve a value, modifying the value obtained 500 times, and then multiple-dereferencing once to write the result back - even though the output results produced are the same. That is what I was alluding to with my comment about choice of algorithm.

Sometimes a compiler can help with poorly written code (whether it works with pointers or arrays or something else) by various techniques, such as hoisting loop-invariant code out of the loop. However, ability of compilers to do that is naturally bounded, and programmers ability to write poor code is unbounded.

**zub** · 07-27-2014

Originally Posted by patishi

During the program I will be eccessing the table with unique keys ,and each of those keys will be a 64 bit integer (long long type).
When initiating the table at the start of the program,I am also using 64 bit integers as keys (the same keys that I will use later to find them in the table).
what other way can I determine the right index to store this kind of key in the hash table except (key & sizeOfTable) ?

Just store keys to array in ascending order and use binary search. It is most simple and robust way, IMHO. For example, you need to create hash array, where keys are 64-bit integers and values are strings.

Code:

1 -> "one"
2 -> "two"
3 -> "three"
10000000000000000000 -> "google"

Array of keys: { 1, 2, 3, 10000000000000000000 };
Array of values: { "one", "two", "three", "google" };

Thread: Little guidance in memory management

Thread Tools

Search Thread

Display

Little guidance in memory management

Similar Threads

Memory management

Memory management

Memory management

Memory management - How/why/when

Memory Management