Originally Posted by
ali.franco95
After dynamically allocating my arrays, I think I have seen some speed gains in my code down from 13sec to 11sec. Am I imagining this (could be that I am not listening to music as I am executing the program) or there is something to it. I just noticed it, was not looking to optimise my code.
Here's something I learned recently here; it is specifically to do with the linux kernel, but it might apply in some way to all modern operating systems since it has to do with fundamental issues.
11-13 seconds is a long time and implies the total size of these arrays is very large. What happens when you do this:
Code:
int *array_x = malloc(10000*sizeof(int));
Is that the kernel assigns the program enough virtual address space to cover the array. This is not actual memory. There are a few reasons to do that:
1) So that the OS can juggle numerous large applications simultaneously, that, when considered together, might exhaust all of the real physical memory.
2) So that the OS can provide contiguous addresses (the C standard, eg, requires such for arrays) possibly using small, non-contiguous blocks if there is not actually such a large single chunk available.
If you now examine the uninitialized contents of array_x, it is all zeros. WRT linux at least, these are fake. A read on uninitialized heap memory still does not involve any real physical memory.
Physical memory (actual RAM) comes into play when you write something into the array. At that point, the kernel finds enough physical memory to cover the part written into. That's all. Ie, if the first thing you do is this:
Code:
array_x[1001] = 666;
array_x[7123] = 3000000;
The kernel will come up with 2 page sized blocks of RAM. A page is the smallest unit of memory the kernel will deal with (4096 bytes is common). At this point, presuming sizeof(int) == 4, array_x represents 40000 bytes of virtual address space, but only 8192 bytes of real memory.
Every time a new page is needed to cover a write, there is some processor overhead. I believe this is why traditionally malloc is considered an expensive call; traditionally, this would all happen at once (which would probably be more efficient time-wise, but would be very inefficient, RAM usage wise). Instead, it happens a page at a time when allocated space is written into for the first time.
Part of the cost here is that if the write does not cover the entire page, the kernel actually zeros out the rest of it.* Ie, calloc() calls are meaningless on linux (and I believe other modern OS's) because malloc'd memory is zero'd out anyway. One reason for that is security; if the memory were left in the state it was last used, you could get access to all kinds of information you maybe should not have access to just by allocating large chunks of memory and then reading the uninitialized data.
So this might be your issue. There are ways to determine that and to alleviate the problem but they will be platform specific.
* it could be that this happens when the previous user frees it.
