C/C++ Allocation

Question

Giving a number X and reading X numbers into an uni-dimensional array, which of the following ways is the best(fastest as execution time)?

Please note that X is a number between 1 and 1000000

scanf("%d", &x);
int array[x];
//continue reading X numbers into array

Or

scanf("%d", &x);
int array[1000000];
//continue reading X ...

Or

scanf("%d", &x);
int * array = malloc(x*sizeof(int));
//same as above
free(array);

Or the C++ dynamic allocation method?

Note 1: that I am posting this from a mobile phone, I hope the format for the code above is fine, if not, I ask nicely somebody (<3) to edit it, since it is painfull to indent code from a phone.

Note 2: How could I test what I asked above?

Use a timer to count the time it takes for the three different methods... Although I would definitely ban number 2 `array[1000000]` as if you have only 1 data you loose lots of memory... — Martin Verjans, Mar 30 '16 at 08:34
Do you really care about execution time when using user input?! Will you ever notice any difference? — Adriano Repetti, Mar 30 '16 at 08:38
You should ask yourself if it is really worth optimizing here. What does your program do with the the scanfed data ? — Jabberwocky, Mar 30 '16 at 08:38
Possible duplicate of [C++ memory allocation for arrays](http://stackoverflow.com/questions/24909753/c-memory-allocation-for-arrays) — secretgenes, Mar 30 '16 at 08:42
http://stackoverflow.com/questions/161053/which-is-faster-stack-allocation-or-heap-allocation — secretgenes, Mar 30 '16 at 08:42
@AdrianoRepetti The program that I am currently writing has to have a maximal execution time, basically I want things to load faster at a small cost of CPU. Assuming that I have enoguh memory. — Tudorut Robert, Mar 30 '16 at 08:50
@TudorutRobert if your program has such **strict timing requirements** then stack array allocation (but where array is allocated is implementation defined) is slightly faster (that's why it's what usually done in real-time environments). Note that VLA may be stack allocated too (implementation defined) and they have slightly better performance vs malloc() but they have many other drawbacks. However, in this case, first of all limit answers to C or C++ and describe your specific architecture and requirements. A _general_ answer in this case is just useless. — Adriano Repetti, Mar 30 '16 at 08:55

CodeFuller · Answer 1 · 2016-03-30T08:48:19.967

1

You'll get compilation error for this code:

scanf("%d", &x);
int array[x];

x should be known at compilation time in this case.

When using int array[1000000] you allocate memory on the stack, not in the heap, so it's fundamental difference comparing to malloc or new operator. It would be faster because it takes actually only one CPU command of modifying stack pointer.

If comparing malloc and new, malloc will be faster because new will eventually call malloc inside. But the performance gain will be tiny, It doesn't worth to optimize your c++ program in this way, just use c++ when you need to allocate dynamic memory.

edited Mar 30 '16 at 08:48

answered Mar 30 '16 at 08:37

CodeFuller

30,317
3
63
79

In C++ i tried it with cin>>x; int array[x]; and it compiles just fine.(i assumed that it works the same in C) – Tudorut Robert Mar 30 '16 at 08:39
1

@CodeFuller also in C (starting from C99) it's valid (and it has been a GCC extension as well). Oh, BTW...do you really really think you can measure performance difference between new and malloc? It's slower (true) but because it does something else... – Adriano Repetti Mar 30 '16 at 08:39
1

Well, may be int array[x] could be compiled with gcc, but standard c++ doesn't support this. In VS you'll get error 'error C2133: 'array' : unknown size'. – CodeFuller Mar 30 '16 at 08:46
@TudorutRobert I would avoid VLA. Even if some compilers don't complain. VLA is a standard feature of c99. In c++11 is _[a conditional feature which implementations are not required to support](https://en.wikipedia.org/wiki/Variable-length_array)_ – zdf Mar 30 '16 at 08:53
@CodeFuller as Adriano said, it's valid C (since C99). The fact that C++ doesn't allow this or the fact that the Microsoft compiler gives an error is irrelevant to the fact that variable-length arrays are a valid C language construct. Nonetheless, what I agree with what ZDF says. – rubenvb Mar 30 '16 at 08:55
Since C11 Variable Length Arrays are no longer mandatory for C, see https://en.wikipedia.org/wiki/C11_(C_standard_revision) VS has never had a fully compliant C99 compiler especially with regards to VLA. – Elijan9 Mar 30 '16 at 10:44

score 1 · Accepted Answer · answered Mar 30 '16 at 09:19

Since there appears scanf (and the comments assume that there's another million calls to scanf) any questions regarding the memory allocation in combination with "Which is fastest?" can be universally answered with: "Yes" (read as: irrelevant).

While automatic storage ("stack allocation") is generally faster than freestore, it is entirely insignificant compared to the time you will spend in scanf. That being said, it is usually (not necessarily, but usually) dynamic deallocation which is slow, not allocation.

A couple of points to note in general on that code:

Reading an integer from some external source (file, network, argv, whatever) and doing an allocation based on that number without doing a sanity check first is massively bad karma. This is bound to cause a problem one day, it is how many existing real-world exploits came into being. Do not trust blindly that any number that you got from somewhere is automatically valid. Even if no malice is involved, accident may still provide an invalid number which will cause catastrophic failure.
Allocating a non-constant sized array on the stack will work under recent versions of C and will "work" as an extension even under C++ if you use GCC, but it is normally not allowable in C++ (meaning it will fail to compile).
Allocating a million integers means roughly 4MB of memory, which is pretty harsh towards your maximum stack size (often only 1MB). Expect a stack overflow happening.
Allocating an unknown number of integers (but expecting the number to be up to a million) is similar to (3).
The worst thing re (3) and (4) is that it may actually succeed. Which possibly means your program will unexpectedly crash later (encountering a stack overflow), in an entirely unrelated innocent piece of code. And you will wonder why that happens, since the code that crashes looks like it is perfectly valid (and it is, indeed!).

C/C++ Allocation

2 Answers2