Are multiple realloc more expensive than a huge malloc?
arrays, c, malloc, realloc
Solution
If you can spare the memory to make the large up-front allocation, and it gives a worthwhile performance increase, then by all means do it.
If you stick with `realloc`, then you might find that doubling the size every time instead of increasing by a fixed amount can give a good trade-off between performance and efficient memory usage.
Problem
I am using a dynamic array to represent a min-heap. There is a loop that removes minimum, and add random elements to the min-heap until some condition occur. Although I don't know how the length of the heap will change during run-time (there is a lot of randomness), I know the upper bound, which is 10 million. I have two options: 1) Declare a small array using malloc, then call realloc when there number of elements in the heap exceeds the length. 2) Declare a 10 million entry array using malloc. This avoids ever calling realloc. Question Is option 2 more efficient than option 1? I tested this with my code and there seems to be significant (20%) run-time reduction from using 2. This is estimated because of the randomness in the code. Is there any drawback to declaring a large 10-50 million entry array with malloc up front?