2

I know you can make a dynamically sized array using malloc, but I'm interested in doing the same thing using new, partly because malloc is considered bad practice in C++ and mostly out of curiosity.

Say I'm writing a program that will receive an input of bytes that could be as many as MAX_INPUT_SIZE, which is so large that allocating an array of that size could potentially impede the ability of other programs to run on the same RAM. However, all input sizes [0, MAX_INPUT_SIZE] are equally as likely to be received. Is there a way to write the program in such a way that memory allocation on the heap is proportional to the input size so that performance of other programs are not affected unless a large enough input is received? Assume these restrictions:

  • Cannot use malloc
  • Cannot use vector or other wrappers (let's say we are looking for extremely fast performance)
  • The algorithm to interpret the data MUST have all data available in one array (for performance reasons, and so that small inputs will still be processed very fast)
  • Program should allocate memory approximately equal to input size

These restrictions are unrealistically tight but it's just hypothetical. Here is a potential solution:

char *data;
long long int data_size;
/* receive input size */

if( data_size <= 1000 )
    data = new char[1000];

else if( data_size <= 10000 )
    data = new char[10000];
...
else if( data_size <= MAX_INPUT_SIZE / 10 )
    data = new char[MAX_INPUT_SIZE / 10];

else if( data_size <= MAX_INPUT_SIZE )
    data = new char[MAX_INPUT_SIZE];

My question is, does the above code actually only allocate new memory when its line of code is run, or does it prepare memory for all those new calls, and just assign the pointer to the one requested?

Essentially, would this program run on computer where MAX_INPUT_SIZE exceeds the available RAM, but the actual data_size does not?

If the answer is, yes it would run, then why does new force you to have an array size that resolves at compile time? Surely it's possible for the C++ compiler could make new allocate dynamically then? If so then is it simply a design choice, and what would be the reasons for disallowing dynamic array size allocation?

If the answer is, no it wouldn't run, is there an alternate solution given the restrictions?

danronmoon
  • 3,814
  • 5
  • 34
  • 56
Jedediah Heal
  • 133
  • 7
  • 8
    You asked: *why does new force you to have an array size that resolves at compile time* … but it ***doesn't***! – Adrian Mole Dec 05 '19 at 21:19
  • 1
    What you are looking for is associative containers, like `std::set`, `std::unordered_set`, or perhaps `std::map` or `std::unordered_map`. This is what you're looking for. Please see your C++ book for a full explanation. – Sam Varshavchik Dec 05 '19 at 21:23
  • 2
    You also asked: *Surely it's possible for the C++ compiler could make new allocate dynamically then?* - but it ***does***! – Adrian Mole Dec 05 '19 at 21:23
  • 3
    `if( data_size <= 1000 ) data = new char[1000]; else if( data_size <= 10000 ) data = new char[10000];` ?? why not `new char[data_size]` ? – KamilCuk Dec 05 '19 at 21:23
  • 3
    *Cannot use vector or other wrappers (let's say we are looking for extremely fast performance)* -- Please measure. Let's see the proof that using `vector` will be slower than whatever you come up with. – PaulMcKenzie Dec 05 '19 at 21:26
  • It seems I'm mistaken. Does anyone know what language/senario am I thinking of where you can't have an array length that isn't known at runtime? – Jedediah Heal Dec 05 '19 at 21:28
  • BTW, `new` is [also](https://isocpp.org/wiki/faq/freestore-mgmt#memory-leaks) considered bad practice. Re: array size, you must be thinking of array objects, as in `char x[1000];`. See [Static array vs. dynamic array in C++](https://stackoverflow.com/questions/2672085/static-array-vs-dynamic-array-in-c) – rustyx Dec 05 '19 at 21:29
  • Just use a `std::vector`. It is just as fast as using `new` as long as you use it right and you turn on optimizations. – NathanOliver Dec 05 '19 at 21:52

3 Answers3

4

does the above code actually only allocate new memory when it's line of code is run, or does it prepare memory for all those new calls, and just assign the pointer to the one requested?

The memory is not allocated until new is actually called at runtime.

Essentially, would this program run on computer where MAX_INPUT_SIZE exceeds the available RAM, but the actual data_size does not?

Yes.

why does new force you to have an array size that resolves at compile time?

It doesn't. Wherever did you get that idea? Only static arrays need to have their size specified at compile-time. Dynamic arrays do not. One of the main benefits of using new[] is that you can supply it with a value that is not known until run-time. For example:

char *data;
long long int data_size;
/* receive input size */

data = new char[data_size];
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • Yes this is probably what I'm thinking of. What if I rephrased my question to ask about array declaration with dynamic sizing? Although it would make no sense, would my solution work to mimic dynamic sizing? – Jedediah Heal Dec 05 '19 at 21:40
  • "*array declaration with dynamic sizing*" - that would be a so-called **variable length array** (VLA), which is **non-standard**, only supported as an extension in few compilers. The *standard* way to use dynamic length arrays is to use `new[]`, preferably `std::vector` instead. "*Although it would make no sense, would my solution work to mimic dynamic sizing?*" - I don't understand what you are asking. – Remy Lebeau Dec 05 '19 at 22:10
1

I believe you mixed array declaration with new allocation.

With arrays:

#define this_has_to_be_compile_time_constant  50
// or: const int this_has_to_be_compile_time_constant = 50;
char array[this_has_to_be_compile_time_constant];

But with new:

int this_can_be_a_variable = some_function();
char *array = new char[this_can_be_a_variable];
KamilCuk
  • 120,984
  • 8
  • 59
  • 111
  • Yes this is probably what I'm thinking of. What if I rephrased my question to ask about array declaration with dynamic sizing? Although it would make no sense, would my solution work to mimic dynamic sizing? – Jedediah Heal Dec 05 '19 at 21:39
  • About what exactly? What is an "array declaration with dynamic sizing"? – KamilCuk Dec 05 '19 at 21:40
0
  • Cannot use vector or other wrappers (let's say we are looking for extremely fast performance)

Just use a vector.

The following snippet is from running code.

  • The size of gameboard object is not known at compile time.

  • In my practice, gameboard is created empty, which takes no time at all.

    // create game-board - with a vector of cells

    CellVec_t gameBoard;

So one line does the allocation effort after the size is determined. Options include default value, cmd line override, display max size, etc.

from en.cppreference.com/w/cpp/container/vector:

"Reallocations are usually costly operations in terms of performance. The reserve() function can be used to eliminate reallocations if the number of elements is known beforehand. "

Thus

gameBoard.reserve (static_cast<long unsigned int>(aMaxRow * aMaxCol));

GOLUtil_t  gBrd(aMaxRow, aMaxCol, gameBoard, *ansiTerm);

...

Size of gameboard.size() is 0 when reserve is called, and capacity is fully allocated after.

2785528
  • 5,438
  • 2
  • 18
  • 20