- Forum
- General C++ Programming
- How is this memory allocated?
How is this memory allocated?
Hi, I am writing an Array template class for a project. I was writing a push function when I wondered something. What actually happens if I increase an array in size, without allocating that space before? I think I should just show you what I mean.
m_array is the array created, m_size is the size of that array.
When I set the m_size+=1, what is happening? Could that overwrite something that was currently at that position in memory? I originally had a push function which placed an element at a specified position and kept the order of the structure, which was O(N), I created a temp array and copied it and changed the size etc. Then I thought of this, which would be no contest if my data got huge.
Is it legal to do the above? Would it also be the same if I was shortening the array? (m_size-=1) or would that lock the memory that it previously owned?
Thanks.
|
|
m_array is the array created, m_size is the size of that array.
When I set the m_size+=1, what is happening? Could that overwrite something that was currently at that position in memory? I originally had a push function which placed an element at a specified position and kept the order of the structure, which was O(N), I created a temp array and copied it and changed the size etc. Then I thought of this, which would be no contest if my data got huge.
Is it legal to do the above? Would it also be the same if I was shortening the array? (m_size-=1) or would that lock the memory that it previously owned?
Thanks.
Once you've created the array, presumably with something like:
changing m_size doesn't affect the size of the array at all. The array has already been allocated.
If the array is of size m_size, then this:
is already writing off the end of the array into memory that could be anything. The last element is
If you write off the end of the array, you'll be writing into memory that wasn't allocated and could be in use by something else. If you need to make the array bigger, you'll have to do it manually by allocating more memory and copying elements and so forth, or you could use realloc.
The memory is not locked. If you want to, you can write over any piece of memory that you can address. If you do this, expect to trash your data and spark a segfault.
int* m_array = new int[m_size];changing m_size doesn't affect the size of the array at all. The array has already been allocated.
If the array is of size m_size, then this:
m_array[m_size] = ...is already writing off the end of the array into memory that could be anything. The last element is
m_array[m_size-1]If you write off the end of the array, you'll be writing into memory that wasn't allocated and could be in use by something else. If you need to make the array bigger, you'll have to do it manually by allocating more memory and copying elements and so forth, or you could use realloc.
| would that lock the memory that it previously owned? |
The memory is not locked. If you want to, you can write over any piece of memory that you can address. If you do this, expect to trash your data and spark a segfault.
Last edited on
But how come if I do this:
It works as it should? How is it creating a place in memory to store a[3] and a[4] if it is not changing size?
|
|
It works as it should? How is it creating a place in memory to store a[3] and a[4] if it is not changing size?
Array<int>
is not an array. It looks like a container class that behaves similarly to an array, but also is capable of taking care of its own size without trashing everything. It increases its own size without you having to worry about it.
As a general rule of thumb, if you can use a C++ container class to do what you want, use it. There will be a hit to take on speed and memory, but if you don't care about that (and it won't be a lot) then use the container class.
is not an array. It looks like a container class that behaves similarly to an array, but also is capable of taking care of its own size without trashing everything. It increases its own size without you having to worry about it.
As a general rule of thumb, if you can use a C++ container class to do what you want, use it. There will be a hit to take on speed and memory, but if you don't care about that (and it won't be a lot) then use the container class.
Last edited on
Ye Its my own data structure I am making, just calling it an array because we are modelling it on the array class.
Last edited on
| ...the array class. |
An array is not a class, but aside from that, up to you; realloc would mean you don't have to worry about copying the old array over into the new expanded array yourself, and it would also free the old memory. Of course, realloc likes you to have used malloc rather than new when you first allocated the memory space.
I suspect that if this is for some kind of academic course, you should manually handle all the memory yourself with new and delete.
Last edited on
My first question was about memory, will increasing/decreasing the size overwrite anything etc. Because I am not re-allocating memory. If I wasn't just basically starting c++, yes, I could probably know what exactly happens when the code I posted first runs. But I am testing each new function I make, and trying to understand exactly what happens, If I am asking the wrong questions then sorry, but I basically need to know if anything I have done so far will cause a memory leak I suppose
@reply to your post above this, My specs were to make it as robust as possible, and try to make it as memory efficient as possible. I didn't think sorting through an entire array, inputting the specified element and shifting everything up would bode too well for say 1000x more data. Which is why I decided to try the smaller approach, and find out if it was a legitimate thing to do.
@reply to your post above this, My specs were to make it as robust as possible, and try to make it as memory efficient as possible. I didn't think sorting through an entire array, inputting the specified element and shifting everything up would bode too well for say 1000x more data. Which is why I decided to try the smaller approach, and find out if it was a legitimate thing to do.
Last edited on
If you do not allocate any more memory, and then write to a position in the array that you never actually allocated, then yes, you will overwrite something.
You will have a memory leak if, when you create a whole new bigger array to copy everything into and then add the new element on the end, you forget to delete the original.
Looks to me like you are deleting the original, so no memory leaks here. You could double-check by running your code under valgrind. It will present you with a nice easy summary of any memory leaks.
You will have a memory leak if, when you create a whole new bigger array to copy everything into and then add the new element on the end, you forget to delete the original.
delete[] m_array;Looks to me like you are deleting the original, so no memory leaks here. You could double-check by running your code under valgrind. It will present you with a nice easy summary of any memory leaks.
So, would malloc and realloc me better suited to this? So I can realloc as much memory as I need instead of using new? So, could I for example, realloc enough memory for 4bytes when the push function is called, so the array can grow by that 4 bytes? Is that how it works?
Generally speaking a program fragment like this:
will work. It may crash sometimes, or crash in debug builds, but it will work in most cases in release builds. Still, the program containing the fragment will usually fail. It may work by chance, but generally you should expect that it fails. So, this is a bug.
To summarize, the rule that you need to allocate the proper amount of memory is not because the particular program fragment will crash if it tries to write something outside of its bounds, but because the program as a whole will misbehave. And this is what makes it so hard to debug. You will get the error where you least expect it - far from where the cause is.
Sometimes illegal access will crash the program. In hosted environments, i.e. those with OS installed, there is usually virtual memory management in place. What this means is that the programs access one big data container instead of the physical memory itself, but they are not aware of that. It seems as if the code accesses the actual memory, but in fact the instructions lead to accessing some data structure that the CPU itself maintains. One consequence is, that if you have not declared your intention of storing something in particular memory range, then the CPU will signal the OS that something wrong is happening and the OS will terminate your program (or other stuff, but let's keep it simple.) It does not happen every time, because the CPU structure is not fine grained - it splits the address space in 4K blocks or smth like that. So illegal modification inside some 4K block that the program already uses will probably corrupt data, but will not trigger the CPU alarm.
There are freestanding environments, like those used for software in cars, washing machines and such. The memory access is direct (..lets assume). What this means is that no one cares what the program accesses, because the device is running just one program. Then it becomes internal issue for your code to coordinate its activities, so that two program fragments do not step on each other's feet. The library routines like malloc and free help you to do exactly that. Using malloc tells the run-time - give me some memory range that I can use to store information and don't let others use it for different purpose until I free it. Of course, your code has to coordinate with the memory management routines and behave properly, or the trick wont work.
Regarding realloc. The proper way to allocate memory in C++ is to use new, new[], delete, delete[]. This guarantees that the initialization code in object constructors is always executed before the storage is used and the clean-up code in object destructors is always executed before the storage is released. If you work with fundamental types (char, int...) or with POD types (C-like structures) that is not an issue, but you should try to be consistent. However, for some systems realloc provides faster alternative then allocating new memory block and copying the data from the old one. First, realloc can use free space after the current block to make it grow. The old contents are preserved. However, there is no guarantee that such trailing free space is available, and realloc may have to find large enough spot to place the new enlarged block, and also copy the contents of the old one. So, you can not expect that the location of the data will be preserved. You have to update all pointers and references to the new location after realloc. Still, realloc can perform better than manually doing malloc and copying in some OSes. This has to do with the virtual memory management I mentioned before.
In summary: realloc will provide block of memory with the size you request. The old data will be preserved, but is likely that the location will change. realloc returns the new location. You should not use realloc to grow buffers by small amounts, because it is generally not a cheap operation. realloc should be used in preference to malloc and memcpy.
Regards
|
|
To summarize, the rule that you need to allocate the proper amount of memory is not because the particular program fragment will crash if it tries to write something outside of its bounds, but because the program as a whole will misbehave. And this is what makes it so hard to debug. You will get the error where you least expect it - far from where the cause is.
Sometimes illegal access will crash the program. In hosted environments, i.e. those with OS installed, there is usually virtual memory management in place. What this means is that the programs access one big data container instead of the physical memory itself, but they are not aware of that. It seems as if the code accesses the actual memory, but in fact the instructions lead to accessing some data structure that the CPU itself maintains. One consequence is, that if you have not declared your intention of storing something in particular memory range, then the CPU will signal the OS that something wrong is happening and the OS will terminate your program (or other stuff, but let's keep it simple.) It does not happen every time, because the CPU structure is not fine grained - it splits the address space in 4K blocks or smth like that. So illegal modification inside some 4K block that the program already uses will probably corrupt data, but will not trigger the CPU alarm.
There are freestanding environments, like those used for software in cars, washing machines and such. The memory access is direct (..lets assume). What this means is that no one cares what the program accesses, because the device is running just one program. Then it becomes internal issue for your code to coordinate its activities, so that two program fragments do not step on each other's feet. The library routines like malloc and free help you to do exactly that. Using malloc tells the run-time - give me some memory range that I can use to store information and don't let others use it for different purpose until I free it. Of course, your code has to coordinate with the memory management routines and behave properly, or the trick wont work.
Regarding realloc. The proper way to allocate memory in C++ is to use new, new[], delete, delete[]. This guarantees that the initialization code in object constructors is always executed before the storage is used and the clean-up code in object destructors is always executed before the storage is released. If you work with fundamental types (char, int...) or with POD types (C-like structures) that is not an issue, but you should try to be consistent. However, for some systems realloc provides faster alternative then allocating new memory block and copying the data from the old one. First, realloc can use free space after the current block to make it grow. The old contents are preserved. However, there is no guarantee that such trailing free space is available, and realloc may have to find large enough spot to place the new enlarged block, and also copy the contents of the old one. So, you can not expect that the location of the data will be preserved. You have to update all pointers and references to the new location after realloc. Still, realloc can perform better than manually doing malloc and copying in some OSes. This has to do with the virtual memory management I mentioned before.
In summary: realloc will provide block of memory with the size you request. The old data will be preserved, but is likely that the location will change. realloc returns the new location. You should not use realloc to grow buffers by small amounts, because it is generally not a cheap operation. realloc should be used in preference to malloc and memcpy.
Regards
Hi there,
I know this thread's a bit old but I didn't see an answer that I thought really answered what you were asking so I thought I'd just add. First, I'm assuming this a template class. The focus of the question is on m_array.
Well if m_size is the size of the currently allocated array, as far as I can tell it's an error to try and access m_array[m_size], because the array indexes go from 0 to m_size-1, if this is covered elsewhere in your code then ok. Like Moschops said, the element that would be at m_array[m_size] is off the end.
But also I noticed how your test code was:
Array<int> a(2);
a.Push(30,1);
a.Push(40,1);
a.Push(24,2);
for(int i=0;i<a.Size();i++)
{
std::cout<<"a["<<i<<"] = "<<a[i]<<std::endl;
}
Does this initially allocate an array with 2 elements in your template? If so, how does it resize the array to add the 3rd element on line #6? I haven't seen a standard container class with the name 'Array'. Unless there is? Anyone? :)
From what I've seen, you would normally have some rule to resize the array (like to reallocate to a new double size array and copy the elements when it hits MAX (while it's below 100), and then to add 50 each time it hits MAX over 100 - or something of the like). As long as you're only accessing an element within the current size (with a standard C (and C++) array this would be indexes from 0 to array_size-1), any value in that range is legal. If you try to access a value outside that, it's illegal.
So assuming that your function calls expand the array you're using (or reallocate as required) as you add another element that takes it beyond it's current size, you're safe.
Hope this helps
I know this thread's a bit old but I didn't see an answer that I thought really answered what you were asking so I thought I'd just add. First, I'm assuming this a template class. The focus of the question is on m_array.
Well if m_size is the size of the currently allocated array, as far as I can tell it's an error to try and access m_array[m_size], because the array indexes go from 0 to m_size-1, if this is covered elsewhere in your code then ok. Like Moschops said, the element that would be at m_array[m_size] is off the end.
But also I noticed how your test code was:
Array<int> a(2);
a.Push(30,1);
a.Push(40,1);
a.Push(24,2);
for(int i=0;i<a.Size();i++)
{
std::cout<<"a["<<i<<"] = "<<a[i]<<std::endl;
}
Does this initially allocate an array with 2 elements in your template? If so, how does it resize the array to add the 3rd element on line #6? I haven't seen a standard container class with the name 'Array'. Unless there is? Anyone? :)
From what I've seen, you would normally have some rule to resize the array (like to reallocate to a new double size array and copy the elements when it hits MAX (while it's below 100), and then to add 50 each time it hits MAX over 100 - or something of the like). As long as you're only accessing an element within the current size (with a standard C (and C++) array this would be indexes from 0 to array_size-1), any value in that range is legal. If you try to access a value outside that, it's illegal.
So assuming that your function calls expand the array you're using (or reallocate as required) as you add another element that takes it beyond it's current size, you're safe.
Hope this helps
Topic archived. No new replies allowed.