Array Memory Question..I think!

[Akill10]

Hi, I am writing this template Array class. I am trying out some different functions, anything I can think of to implement. I have written an Add function as follows:

/**Add function - adds an element at the top of the stack**/
    //creates new Array 1 larger
    //sets position of element(p_item) to top of the array "stack"
void Add(DataType p_item)
    {
           int m_newSize = m_size+1;
            DataType* tempArr = new DataType[m_newSize];
            for(int i=0;i<m_size;i++)
            tempArr[i] = m_array[i];

            tempArr[m_size] = p_item;
            m_size = m_newSize;
             if(m_array!=0)
             delete[] m_array;

             m_array = tempArr;
             tempArr = 0;


    }

Now this works as i expected. The question lies with what I thought of when trying to think of more efficient ways. Here it is:

void Add(DataType p_item)
    {
         if(m_array!=0)
        {
            m_size += 1;
            m_array[m_size-1] = p_item;
        }

    }

Ok, obviously this function cares less about memory allocation than my old aunt josie, but why does it work once?
This is my main function:

int main()
{
    Array<int> a(5);
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;
    a[4] = 4;
    a.Add(12);//if I only call this function 1 time ,it works. Why is this?
    std::cout<<"A is now "<<a.Size()<<std::endl;
  /*   a.Add(8);
    std::cout<<"A is now "<<a.Size()<<std::endl;*/


    return 0;
}

If I just call the 'bad' Add method once, it works fine. Why? What exactly would be going wrong?

[Rimojenkins]

I'm not absolutely positive, but there isn't a Loop in the "bad" code...

[Akill10]

I'm not absolutely positive, but there isn't a Loop in the "bad" code...

I can't see how that would do anything buddy, plus, it wasn't the question I asked :) I suppose I should have added that m_size is the size of the original array and m_array is the array

[Rimojenkins]

Whoops, my bad. I really did misunderstand what you were asking.
I'll edit this post once I figure it out. Sorry my friend

edit:
I'm sorry for wasting your time. I really thought I could help. I'll open my book and try to find classes (I haven't gotten there yet)...
Sorry again! GL

[Red Goose]

I don't understand this:

if (my_array != 0)

What exactly are you checking for, and for what purpose?

[Akill10]

I don't understand this:

if (my_array != 0)

What exactly are you checking for, and for what purpose?

checking that m_array is not a null pointer, if this is true then I know I can change the size.
I probably should have added that m_size is the size passed into the constructor for the Array. m_array is the array created.

[Akill10]

Am I asking a stupid question here or something? I don't really want to continue this until I properly understand how the array is being constructed in memory.

[Mr. K]

This might solve your problem.Why msize +=1?

void Add(DataType p_item)
    {
         if(m_array != 0)
        {
            m_array[m_size] = p_item;
        }
    }

[pseudorandom21]

void Add(DataType p_item)
{
int m_newSize = m_size+1;
DataType* tempArr = new DataType[m_newSize];
for(int i=0;i<m_size;i++)
tempArr[i] = m_array[i];
tempArr[m_size] = p_item;
m_size = m_newSize;
if(m_array!=0)
delete[] m_array;
m_array = tempArr;
tempArr = 0;
}

Well there are some serious problems with this. I expected your class to be something similar to a vector, meaning it will allocate a large block of memory and then allow access to a certain part of it. Reallocation can be time-consuming and the best way to avoid frequent re-allocation is to allocate N*2 elements (usually).

So if you have 512 bytes reserved for use by the container and it needs more memory, one would allocate 1024 bytes, and the next realloc would be 2048.

My question is, why are you allocating a new array and copying every time you add a new element? Wouldn't it be better to allocate a chunk of memory, and allow access to it as needed?

[Akill10]

void Add(DataType p_item)
{
int m_newSize = m_size+1;
DataType* tempArr = new DataType[m_newSize];
for(int i=0;i<m_size;i++)
tempArr[i] = m_array[i];
tempArr[m_size] = p_item;
m_size = m_newSize;
if(m_array!=0)
delete[] m_array;
m_array = tempArr;
tempArr = 0;
}

Well there are some serious problems with this. I expected your class to be something similar to a vector, meaning it will allocate a large block of memory and then allow access to a certain part of it. Reallocation can be time-consuming and the best way to avoid frequent re-allocation is to allocate N*2 elements (usually).

So if you have 512 bytes reserved for use by the container and it needs more memory, one would allocate 1024 bytes, and the next realloc would be 2048.

My question is, why are you allocating a new array and copying every time you add a new element? Wouldn't it be better to allocate a chunk of memory, and allow access to it as needed?

I suppose it would(I don't know), I have basically just started c++ coming from java. There is a lot I do not know about memory management etc. But, going by what you say, wouldn't that mean there will always be 'extra' memory I am not using, if I reserve it? Using my way, I only use the extra memory for the duration of the function, and then delete it don't I? Please advise if I am way off the mark here. Taking memory management into account is probably one of the most fundamental practices in C++ I would assume, So I need to understand it fully.

Now I do ofcourse understand that, the more amount of data in my array, the longer this will take to compute each time. Which is why I tried to just increase the size by 1 and insert it at the end.

[pseudorandom21]

Yes it does waste at most (N/2)-1 units of memory, I'm not an expert at memory management, I'm a college student--that's just something I picked up on reading a random website a year or two ago. The website was basically some guy ranting about how crappy his memory management was, then the perfect solution was to allocate N*2--like it was a magical formula made by god. Kind of funny, actually.

and yes you do delete it, my bad.

[rxlim]

The reason your code might work is because there are two levels of memory
allocators in C++. The operating system does the actual allocation
of the physical memory and maps it into the process memory space
called heap (known page allocation). Normally this memory is not freed until the
process terminates. The process is free to write to any location
in this allocated memory area (heap). However unused parts of this
memory may be swapped out to disc (to a swap file / page file).

Then there is new/delete and malloc and free. These user space
functions do not really allocate anything by them selves.
They keep track of the already allocated heap memory and request more heap
memory from the OS if needed. This is done in Linux/Unix via a system
call, called brk which can be accessed via the library function sbrk.

So lets say that we allocate 1 MB of memory on the heap with new. This will
increase the heap size with more than 1 MB. The new operator will, behind the
scenes, also allocate space for a block header that keeps information
about the allocated block, such as size. This header might be something around 8-20
bytes depending on the system. This is how delete and free know how
much memory to free without being told explicitly (because the header is
placed right before the address returned from new/malloc).

When delete is called on the previously allocated memory, that block
will be saved to a linked list called a free list. This free list
contains free blocks that can be reused. If two consecutive blocks
are freed they will be merged into one big block. This does not mean
that we cannot access this memory! Actually we can, BUT if we do we
might corrupt the linked list.

If there is a block with size 35 bytes (not including the block header)
and we want to allocate 30 bytes we might actually get the entire
35 byte memory block since if new/malloc would split this block into two blocks only
5 bytes would remain which will not even hold a block header. So
that might be one reason why your code works without using an extra new.
There are also a couple of other reasons for which new might
return a block bigger than requested like speed optimization reasons.

One other thing that might be good to know is that most cpus
divide memory (virtual memory) into pages, with a fixed size.
On a x86 cpu this size is normally 4KB. So when requesting a
new heap size to the brk system call the operating system will
make that an even number of pages (without telling us).

Here is an example application that allocates 1MB without
using new or delete.

int main()
{
  // Get the address of the heap (currently 0 bytes)
  int* startOfHeap = (int*)sbrk(0);

  // Increase heap size with 1MB
  sbrk(1*1024*1024);

  // Write to a random position within this MB
  startOfHeap[342] = 23;

  // Read from the same location
  cout << startOfHeap[342] << endl;

  return 0;
}

In Windows I belive the function is called HeapAlloc,
but it might work differently.

This is how a new operator / malloc function might look like

void* malloc(int size)
{
  while (true) {
    // Find an existing free block from the free list
    void* freeBlock = findFreeBlock(size);
    if (freeBlock != NULL) return freeBlock;

    // No free block found, allocate a new block (increase heap)
    void* newBlock = sbrk(size + HEADERSIZE);
    if (newBlock == (void*)-1) return NULL;
    initHeader(newBlock, size);  
    freeListAdd(newBlock);  
  }
}

The following application illustrates that the heap (in most cases) is
a multiple of 4KB blocks even if we only request for example 2 bytes.

int main()
{
  int* startOfHeap = (int*)sbrk(0);
  cout << "Heap starts at " << hex << sbrk(0) << endl;

  // On most computers this will actually allocate
  // 4KB of heap memory
  cout << "Requesting 2 bytes" << endl;
  sbrk(2);

  // This might work since sbrk would have allocated
  // an entire page (4KB)
  cout << "Writing to " << &startOfHeap[342] << endl;
  startOfHeap[342] = 23;
  cout << dec << startOfHeap[342] << endl;

  // Trying to write just outside this 4096 byte block
  // This will most likely result in a segmentation fault.
  cout << "Writing to " << &startOfHeap[1026] << endl;
  startOfHeap[1026] = 24;
  cout << dec << startOfHeap[1026] << endl;

  return 0;
}

By replacing sbrk(2) with new char[2], depending on the
implementation of new, it might happen that more than
one page gets allocated and even the second assignment
might work (startOfHeap[1026] = 24).

[Akill10]

The reason your code might work is because there are two levels of memory
allocators in C++. The operating system does the actual allocation
of the physical memory and maps it into the process memory space
called heap (known page allocation). Normally this memory is not freed until the
process terminates. The process is free to write to any location
in this allocated memory area (heap). However unused parts of this
memory may be swapped out to disc (to a swap file / page file).

Then there is new/delete and malloc and free. These user space
functions do not really allocate anything by them selves.
They keep track of the already allocated heap memory and request more heap
memory from the OS if needed. This is done in Linux/Unix via a system
call, called brk which can be accessed via the library function sbrk.

So lets say that we allocate 1 MB of memory on the heap with new. This will
increase the heap size with more than 1 MB. The new operator will, behind the
scenes, also allocate space for a block header that keeps information
about the allocated block, such as size. This header might be something around 8-20
bytes depending on the system. This is how delete and free know how
much memory to free without being told explicitly (because the header is
placed right before the address returned from new/malloc).

When delete is called on the previously allocated memory, that block
will be saved to a linked list called a free list. This free list
contains free blocks that can be reused. If two consecutive blocks
are freed they will be merged into one big block. This does not mean
that we cannot access this memory! Actually we can, BUT if we do we
might corrupt the linked list.

If there is a block with size 35 bytes (not including the block header)
and we want to allocate 30 bytes we might actually get the entire
35 byte memory block since if new/malloc would split this block into two blocks only
5 bytes would remain which will not even hold a block header. So
that might be one reason why your code works without using an extra new.
There are also a couple of other reasons for which new might
return a block bigger than requested like speed optimization reasons.

One other thing that might be good to know is that most cpus
divide memory (virtual memory) into pages, with a fixed size.
On a x86 cpu this size is normally 4KB. So when requesting a
new heap size to the brk system call the operating system will
make that an even number of pages (without telling us).

Here is an example application that allocates 1MB without
using new or delete.

int main()
{
  // Get the address of the heap (currently 0 bytes)
  int* startOfHeap = (int*)sbrk(0);

  // Increase heap size with 1MB
  sbrk(1*1024*1024);

  // Write to a random position within this MB
  startOfHeap[342] = 23;

  // Read from the same location
  cout << startOfHeap[342] << endl;

  return 0;
}

In Windows I belive the function is called HeapAlloc,
but it might work differently.

This is how a new operator / malloc function might look like

void* malloc(int size)
{
  while (true) {
    // Find an existing free block from the free list
    void* freeBlock = findFreeBlock(size);
    if (freeBlock != NULL) return freeBlock;

    // No free block found, allocate a new block (increase heap)
    void* newBlock = sbrk(size + HEADERSIZE);
    if (newBlock == (void*)-1) return NULL;
    initHeader(newBlock, size);  
    freeListAdd(newBlock);  
  }
}

The following application illustrates that the heap (in most cases) is
a multiple of 4KB blocks even if we only request for example 2 bytes.

int main()
{
  int* startOfHeap = (int*)sbrk(0);
  cout << "Heap starts at " << hex << sbrk(0) << endl;

  // On most computers this will actually allocate
  // 4KB of heap memory
  cout << "Requesting 2 bytes" << endl;
  sbrk(2);

  // This might work since sbrk would have allocated
  // an entire page (4KB)
  cout << "Writing to " << &startOfHeap[342] << endl;
  startOfHeap[342] = 23;
  cout << dec << startOfHeap[342] << endl;

  // Trying to write just outside this 4096 byte block
  // This will most likely result in a segmentation fault.
  cout << "Writing to " << &startOfHeap[1026] << endl;
  startOfHeap[1026] = 24;
  cout << dec << startOfHeap[1026] << endl;

  return 0;
}

By replacing sbrk(2) with new char[2], depending on the
implementation of new, it might happen that more than
one page gets allocated and even the second assignment
might work (startOfHeap[1026] = 24).

Thanks, but I already knew most of this. My only problem was wondering if reducing the size of the array will "lock" memory in the last index which was removed. Which it won't really, because an array points to the start of a block of memory that is a specific size, So If I reduce the size, it will point to that block of memory but is 1 less in size.

It will be a good read for anyone stumbling in here though.