Thread: Little guidance in memory management

Thank you all for the usefull comments. Zub , I afraid that binary search will be a little on the slow side (although the idea itself is nice) , I think I prefer using chaining search..but maybe I am wrong here

Unfortunately , I am still a little bit confused.
I got my hash table to work fine, although Not in perfect hashing..but I'm working on it.

I am declaring and defining the array as global (above main() ) in size of 900000 + . It is array of pointers to struct (all set to null at first) . And each of these node structs contains an array of int values.
Because I don't know the exact size of this array (the ints array..not the actual table) in advance (each one is different size) it is a pointer to int and not fixed sized.
I allocate memory for it during the table initialization function.

So if the table array is fixed sized and allocated wherever global variables are allocated (and i still don't know where it is exactly) but it's content is allocated by me on the heap... what does this means??

And second thing:
What if I want to allocate all those structs on the stack instead.. how can I do this ? Rememer that I dont know the exact size in advance..that's why I use malloc.
(I can set the content of the structs to be fixed size but I don't want to waste space for nothing)
I would appreciate if you guys can help me figuring this out.

Thx again.

Originally Posted by patishi

I afraid that binary search will be a little on the slow side (although the idea itself is nice) , I think I prefer using chaining search..but maybe I am wrong here

You can measure with typical test data to see what kind of difference does it make in probable practice.

Originally Posted by patishi

So if the table array is fixed sized and allocated wherever global variables are allocated (and i still don't know where it is exactly) but it's content is allocated by me on the heap... what does this means??

Err... this means what you wrote.

Originally Posted by patishi

What if I want to allocate all those structs on the stack instead.. how can I do this ?

Why do you want to do this?

Anyway, in practice, the answer is probably: you cannot as the space required will probably be too large, and to make it worse you do not know how much memory to allocate at compile time so you will have to allocate the maximum needed.

Originally Posted by patishi

There is one more thing I don't understand.. if I store 823,543 structs. Each of those structs contains an array of 7 long long (64 bit) type , another 64 bit for the key, and another int (32 bit).
Thats about 68 bytes (!)
If I multiply 68 in 823,543 I get 56,000,924, dividing in 1000 I get 56,000. That means 56,000 mega and that's about 56 Gig !!

No: 56000924 B = 54688.4 KB = 53.41 MB = 0.05216 GB (where = is used to denote "approximately")

Originally Posted by patishi

My computer have only 4 Gb of RAM .

Note that it is possible for there to be more virtual memory than the amount of RAM available.

Originally Posted by patishi

Is there a difference in performance when doing operations with 64 bit variables vs 32 types ?

In general, yes.

The nature of that difference, however, depends on hardware implementation (registers, operations on them, etc) and software (e.g. do some operations need to be emulated in software) so it is not a slam-dunk that one always has greater or lesser performance than the other - by whatever measure is used for performance. The only exception is memory usage: a given number of 64-bit variables, by definition, use more memory than the same number of 32-bit variables.

Possibilities include;
1) Hardware natively supports 32-bit, and 64-bit variables/operations are emulated in software. In this case, 64-bit operations will almost invariably exhibit lower performance than than 32-bit.
2) Hardware supports 64-bit natively, but 32-bit variables/operations are emulated in software (32-bit variable copied to 64 bit register, operation performed, result truncated and copied back to a 32-bit variable). In this case, 32-bit operations will almost invariably exhibit lower performance than 64-bit.
3) Hardware supports both 32-bit and 64-bit variables/registers/operations. In this case, relative performance depends on the hardware and microcode design, and whether the design is optimised more for performance of 32-bit or 64-bit.

There are real-world hardware and software combinations that do each of the above .... and other possibilities too. Of course, compiler optimisation can skew performance results too, depending on how much knowledge of the target hardware is used to inform compiler design.

I afraid that binary search will be a little on the slow side

Is there a difference in performance when doing operations with 64 bit variables vs 32 types ?

Premature optimization is the root of all evil (or at least most of it) in programming.