realloc throws error after a particular index size in resizing array

Question

So I am making a resizing array using realloc and repeated doubling and my array works fine till its size is 134217728 but as soon as I push the 134217729th element i.e I call the resize function for 134217728*2 the realloc returns 0.

I think my memory is all full but I have 8 Gbs of Ram and I am using windows 10 MinGW 32 bit compiler on Vs code how can further increase the size of my array if I want to. is this a problem with Windows or am doing something wrong?

#include<iostream>
#include<string.h>
#include <ctime>
using namespace std;
template<class X>
class ArrayStack{
    X* a =(int*) malloc(1 * sizeof(int));;
    int top=0;
    int length=1;

    void resize(int size){
        cout<<"resizing to "<<size<<endl;
        X* temp=(X*) realloc (a, size * sizeof(X));
        if(temp==0){
            cout<<"No continous memory left for the stack ";
        }
        length=size;
        a=temp;                
    }

public:
    void push(X item){
        if(top==length){
            resize(length*2);
        }
        a[top++]=item;
    }

    X pop(){
        if(top<=length/4){
            resize(length/2);
        }
        return a[--top];
    }

    bool IsEmpty(){
        return top==0;
    }        
};

int main(){
    ArrayStack <int> newStack;
    for(unsigned long long int i=0;i<134217729 ;i++){
        // In case of int the max size of array stack i can make is of length 134217728 using repeated doubling and realloc
        int r  = rand()%1000;
        newStack.push(r);
    }  
    while(!newStack.IsEmpty()){
        newStack.pop();
    }
}

realloc returns 0.

Answer 1

32 bit programs have maximun of 4 GB address space. Real address space allowed might be half of that depending on environment. And that includes also program code, static data, libraries, stack etc!

Resizing allocation (always with delete/new, often with realloc too) requires creating new allocation before deleting the old.

So consider total byte size (element count times sizeof element type) of both previous and new allocation. Does it approach or exceed 2 GB?

If it does, you are running out of memory available to your application.

Two solutions: process data in smaller chunks (not easy, not fun, bad performance), or switch to 64 bit compiler (do this).

There is a 64 bit version of MinGW available.

Answer 2

Since this appears homework related, let's start with the basics and you can draw from them and incorporate them in your reallocation scheme. First, as noted above, do not mix new/delete with malloc/calloc/realloc. While they perform similar allocation functions, their implementations are entirely different.

That said, there is nothing that prevents you from writing a short reallocation function (say reallocNew) that will use new and delete to perform the reallocation. Since above you discussed doubling the size of the currently allocation when you reallocate, you simply need to create a new array of type T with twice the current memory. You then copy from your old array to your new (using memcpy) and then delete[] your old array returning your newly reallocated block to the caller for assignment to the original pointer.

A short example of a reallocNew function that takes a pointer to the original block of memory along with a pointer to the current number of elements (to be updated within the function and made available to the caller though the pointer) could be as follows:

template<class T>
T *reallocNew (const T *ptr, size_t *nelem)
{
    /* make new allocated array with 2X the number of elements */
    T *tmp = new T[2 * *nelem];

    /* copy old elements to new block of mem */
    std::memcpy (tmp, ptr, *nelem * sizeof *ptr);
    delete[] ptr;       /* delete the old block of memory */
    *nelem *= 2;        /* update the number of element counter */

    return tmp;         /* return pointer to reallocated block of memory */
}

A short example program making use of the reallocation function to initially start with an allocated block to hold 2-int and then reallocNew at 2, 4 & 8 elements to store the 10-int values added to the array. The complete example could be:

#include <iostream>
#include <cstring>

template<class T>
T *reallocNew (const T *ptr, size_t *nelem)
{
    /* make new allocated array with 2X the number of elements */
    T *tmp = new T[2 * *nelem];

    /* copy old elements to new block of mem */
    std::memcpy (tmp, ptr, *nelem * sizeof *ptr);
    delete[] ptr;       /* delete the old block of memory */
    *nelem *= 2;        /* update the number of element counter */

    return tmp;         /* return pointer to reallocated block of memory */
}

int main (void) {

    size_t  nelem = 2,                  /* no of elements alloced */
            used = 0;                   /* no. of element counter */
    int *arr = new int[nelem];          /* allocate initial elements */

    for (; used < 10; used++) {             /* loop adding to array */
        if (used == nelem)                  /* is realloc needed? */
            arr = reallocNew (arr, &nelem); /* call reallocNew function */
        arr[used] = used + 1;               /* add value to array */
    }

    for (size_t i = 0; i < used; i++)  /* loop over stored values outputting */
        std::cout << "arr[" << i << "] : " << arr[i] << '\n';

    delete[] arr;   /* don't forget to free what you allocated */
}

note: the reallocation scheme is the same above as you find anywhere. You want to avoid reallocating for every addition, so you pick some reasonable scheme like adding some fixed number of elements, multiplying the current by some fraction greater than one, or a common one that provides reasonable trade-off is to just double the current allocation each time a reallocation is needed. That allows the addition of 10 elements above with only 3 reallocation (you could add up to 16 elements without having to reallocate again).

(while the memory will be freed on program exit, a delete[] for allocated memory nested within your code will prevent memory leaks)

Example Use/Output

$ ./bin/newdelrealloc
arr[0] : 1
arr[1] : 2
arr[2] : 3
arr[3] : 4
arr[4] : 5
arr[5] : 6
arr[6] : 7
arr[7] : 8
arr[8] : 9
arr[9] : 10

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/newdelrealloc
==32331== Memcheck, a memory error detector
==32331== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==32331== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==32331== Command: ./bin/newdelrealloc
==32331==
arr[0] : 1
arr[1] : 2
arr[2] : 3
arr[3] : 4
arr[4] : 5
arr[5] : 6
arr[6] : 7
arr[7] : 8
arr[8] : 9
arr[9] : 10
==32331==
==32331== HEAP SUMMARY:
==32331==     in use at exit: 0 bytes in 0 blocks
==32331==   total heap usage: 5 allocs, 5 frees, 72,824 bytes allocated
==32331==
==32331== All heap blocks were freed -- no leaks are possible
==32331==
==32331== For counts of detected and suppressed errors, rerun with: -v
==32331== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Look things over and let me know if you have questions.

Answer 3

i just changed the code to this according to suggestions from above to mix realloc/malloc/calloc etc with new and templated classes but it still has that error. I am still guessing its that i don't have enough space as is also suggested by the people above and thanks guys for being supportive its really hard to come from a language like python and JS to C++ and there are small things that cause a lot of problems and thanks for explaining with patience I got made fun of asking this at class thanks for your time and if you any others methods to get around it shorter to using vectors please suggest.

its an assignment for making something similar to vector I was just going write a wrapper over this which takes all the array fragments I can get using this and link them using a superclass/array/hash and then divide the incoming requests by distributing them according to the index the requests want and which one of the subarrays will have that particular index

#include<iostream>
#include<string.h>
#include <ctime>
using namespace std;
template<class X>
class ArrayStack{
X* a =new X[1];
unsigned long long int top=0;
unsigned long long int length=1;
void resize(unsigned long long int size){
    X* temp=new X[size];
    length=size;
    for(unsigned long long int i=0;i<size/2;i++){
        temp[i]=a[i];
    }
    delete []a;
    a=temp;                
}
public:
void push(X item){
    if(top==length){
        resize(length*2);
    }
    a[top++]=item;
}
X pop(){
    if(top<=length/4){
        resize(length/2);
    }
    return a[--top];
}
bool IsEmpty(){
    return top==0;
}        
};

int main(){
ArrayStack <int> newStack;
for(unsigned long long int i=0;i<134217728 ;i++){
    // In case of int the max size of array stack i can make is of length 134217728 using repeated doubling and realloc
    int r  = rand()%1000;
    newStack.push(r);
}  
while(!newStack.IsEmpty()){
    newStack.pop();
}
}