<p>In Java, the size of arrays are immutable. However, to my understanding, they are still allocated on the heap, because Java allocates almost everything on the heap. Even then, Java arrays are still unchanging in size. My question is, if at any point a language implementation (e.g., the Java Virtual Machine) could simply call <code>realloc()</code> or the equivalent, why do they still not support resizing an array without creating a new one?</p>
<p>Another example is in C++, there are <code>new</code>/<code>delete</code> which are equivalent to <code>malloc()</code>/<code>free()</code>, but there is no corresponding equivalent of <code>realloc()</code>. At the same time, both languages have standard library classes that behave as arrays that can be resized (<code>java.util.ArrayList</code> and <code>std::vector</code>). Is there a reason a language would bar the programmer from manually performing reallocations/resizes?</p>

<arrays><c++><memory-management><java>
Why might a language avoid reallocation?
CC BY-SA 4.0
2023-07-11T19:45:36.247Z
It might be worth noting that `realloc` is, essentially, a fancy wrapper around `free` and `malloc` with some corner cases. While it might resize in-place in favorable conditions, it gives no guarantees. Java and C++ still allow you to do the same thing manually, which is what `ArrayList` and `std::vector` do.
abel1502
CC BY-SA 4.0
2023-07-12T09:20:47.220Z
It could also be said that those corner cases are the reason why realloc exists.
ojs
<p>There is potentially unknown number of variables pointing to (&quot;referencing&quot;) the same Java array. It cannot be &quot;reallocated&quot; because these references may end up pointing to nothing if it is moved in the memory. A wrapper object is required that is not reallocated so references to it remain valid. This wrapper object can then manage the internal array to what only it has access to.</p>
<p>With C++, it is still possible to get this wrong by creating and retaining pointers into internal values inside the vector: you add one more element, the vector grows and using your pointers is now undefined behavior. However you mostly just need to be aware.</p>
<p>And, yes, C++ does have <a href="https://en.cppreference.com/w/cpp/memory/c/realloc" rel="noreferrer">std::realloc</a> that you may use if find reasonable, even if there are restrictions how to allocate the region, see comment below.</p>

CC BY-SA 4.0
2023-07-11T18:57:58.947Z
2023-07-13T07:32:40.370Z
2023-07-13T07:32:40.370Z
Audrius Meškauskas
CC BY-SA 4.0
2023-07-12T10:40:07.197Z
C++ `std::realloc` is for use with what was `std::malloc`ed (or `std::calloc`ed), it's incompatible with `new`.
Ruslan
CC BY-SA 4.0
2023-07-14T14:56:52.627Z
Note that a stop-the-world garbage collector can reallocate storage for objects and update all references to them, and in fact that is how many such collectors work.  Such reallocation can only occur during a stop-the-world event, however, and not at other times.
supercat
CC BY-SA 4.0
2023-07-23T18:50:00.203Z
@supercat - yes, but running a stop-the-world collection generally takes multiple milliseconds or even tens of milliseconds in typical applications.  And a hypothetical Java `Arrays.resize` would need to run one every time it was called, which is likely to be substantially less efficient than just copying the array's contents into a new one, thus the entire point of `realloc` existing (that in some unusual circumstances it's faster, and isn't ever noticeably slower than making a new copy) is essentially negated.
occipita
CC BY-SA 4.0
2023-07-23T19:17:26.467Z
@occipita: Agreed that stop-the-world GC systems that globally update direct references can't accommodate operations that might require expanding objects in place.  Such a system could allow objects to be shrunk, however, with the proviso that storage wouldn't become available until the next GC cycle.  That's not really a problem, though, since nobody would care whether the memory was available before the next GC cycle.
supercat
<p>In C, the memory location of the object affected by calling <code>realloc</code> may change, meaning you have to update your pointers to the object after calling it.  The canonical way of using it is:</p>
<pre><code>ptr = realloc(ptr, newSize);
</code></pre>
<p>If there are other copies of the pointer, you need to make sure they're updated too. In reality, almost all code that uses <code>realloc</code> works on pointers that only have one copy.</p>
<p>In a language with garbage collection, copying the contents and updating the references will cause the original object to be deleted.  This means that the Java code:</p>
<pre><code>array = Arrays.copyOf (array, newSize)
</code></pre>
<p>is actually directly equivalent in the case where there is no other reference to <code>array</code>.  Unfortunately, we cannot directly modify the allocation because in most implementations there is no way of telling that <code>array</code> is the only copy of the reference: the garbage collector can only find out when there are no copies, but not identify how many copies there are.  A reference counting GC may be able to achieve this, but Java was not designed with using such a GC in mind.</p>

CC BY-SA 4.0
2023-07-15T16:01:36.480Z
2023-07-15T16:01:36.480Z
occipita
CC BY-SA 4.0
2023-07-18T09:16:28.837Z
I wouldn't call that the "canonical" way to use `realloc()`.  A common _wrong_ way, perhaps...
Toby Speight
CC BY-SA 4.0
2023-07-24T04:50:00.697Z
@TobySpeight they're just omitting the error checking for brevity here. The important point is that you have to reassign the original pointer.
Barmar
CC BY-SA 4.0
2023-07-27T07:22:29.107Z
I hope so @Barmar.  Unfortunately, I've seen almost exactly that line in real code, so it bears mention that we mustn't reassign `ptr` when `realloc()` has failed and left the existing memory block untouched.
Toby Speight
<p>Java couldn't allow this because of how its memory is laid out. There are four pools, each of increasing size. Every time an object is created, it is added to the smallest pool, in a contiguous manner. Objects that go out of scope don't immediately get deallocated, instead waiting for the next GC cycle. When that pool is full, all objects in the pool are checked for aliveness. If they are, they move to the next larger pool. The pool is then cleared at the end of the GC cycle. This happens for each larger pool, until the largest, which requires the most work to clean up, but rarely ever does. As such, a reallocation would require all members of the pool to potentially move to make space, or the object would have to be placed at the end of the pool, and everything else would move, and it may even trigger an early GC cycle in that pool if there's insufficient space.</p>
<p>C++ has a different memory layout, but the ideas are kind of the same. Memory is allocated contiguously, so increasing the size almost always requires a move operation. However, since we don't control the pointer, only references, and since multiple references can exist (which is also true for Java), that means that the language would have to specify that references are also updated automatically. This could be a major performance problem. One way to work around this problem is by using smart pointers. Your code would only ever interact with a pointer that is guaranteed to not be reallocated, and that pointer would point to the data that can move. This way, you maintain just one reference to the object, which improves performance.</p>
<p>Other strategies are possible, such as intentionally leaving space after every object, but this would trade the risk of movement in exchange for wasted memory usage. The language could also just keep track of the references in some kind of list, and therefore know how to update the references. Either way, such languages would likely be wasteful with memory or processing time. The fastest way to access data is direct access, and that typically means limiting what you can do with that memory once allocated.</p>

CC BY-SA 4.0
2023-07-13T15:00:19.200Z
2023-07-13T15:00:19.200Z
phyrfox
CC BY-SA 4.0
2023-07-16T10:02:44.570Z
I'm not that much into current Java GC strategy, but if I recall correctly, they moved away from having fixed pools and all survining GC strategies are mark&copy anyway. But I could be mistaken.
feldentm
CC BY-SA 4.0
2023-07-16T13:46:13.013Z
@feldentm This answer is intentionally written as more abstract, rather than being overly technical. You are correct that some details have changed wrt exactly how pools are allocated and cleared, but these differences don't matter at a high level. There's still young and old generations, promotion still occurs, etc. It's been incremental changes, like concurrent cleanup, aggressive optimization of the memory maps used, and so on, that make GC more efficient these days.
phyrfox
CC BY-SA 4.0
2023-07-17T16:57:38.683Z
An essential feature of Java is that as long as any reference exists and isn't null, it will identify an object of the same type and size.  Reallocating arrays with different sizes would break this.
supercat
# Why might a language avoid reallocation?
Posted by: username_0 on 2023-07-11
In Java, the size of arrays are immutable. However, to my understanding, they are still allocated on the heap, because Java allocates almost everything on the heap. Even then, Java arrays are still unchanging in size. My question is, if at any point a language implementation (e.g., the Java Virtual Machine) could simply call `realloc()` or the equivalent, why do they still not support resizing an array without creating a new one?

Another example is in C++, there are `new`/`delete` which are equivalent to `malloc()`/`free()`, but there is no corresponding equivalent of `realloc()`. At the same time, both languages have standard library classes that behave as arrays that can be resized (`java.util.ArrayList` and `std::vector`). Is there a reason a language would bar the programmer from manually performing reallocations/resizes?
**Tags:** arrays c++ memory-management java
> **Comments:**
> **username_1**: It might be worth noting that `realloc` is, essentially, a fancy wrapper around `free` and `malloc` with some corner cases. While it might resize in-place in favorable conditions, it gives no guarantees. Java and C++ still allow you to do the same thing manually, which is what `ArrayList` and `std::vector` do.  
> **username_2**: It could also be said that those corner cases are the reason why realloc exists.  
---
## 3 answers
### Answer by username_3 on 2023-07-11. Score: 14
There is potentially unknown number of variables pointing to ("referencing") the same Java array. It cannot be "reallocated" because these references may end up pointing to nothing if it is moved in the memory. A wrapper object is required that is not reallocated so references to it remain valid. This wrapper object can then manage the internal array to what only it has access to.

With C++, it is still possible to get this wrong by creating and retaining pointers into internal values inside the vector: you add one more element, the vector grows and using your pointers is now undefined behavior. However you mostly just need to be aware.

And, yes, C++ does have [std::realloc](https://en.cppreference.com/w/cpp/memory/c/realloc) that you may use if find reasonable, even if there are restrictions how to allocate the region, see comment below.
> **Comments:**
> **username_4** (2023-07-12): C++ `std::realloc` is for use with what was `std::malloc`ed (or `std::calloc`ed), it's incompatible with `new`.  
> **username_5** (2023-07-14): Note that a stop-the-world garbage collector can reallocate storage for objects and update all references to them, and in fact that is how many such collectors work.  Such reallocation can only occur during a stop-the-world event, however, and not at other times.  
> **username_6** (2023-07-23): @supercat - yes, but running a stop-the-world collection generally takes multiple milliseconds or even tens of milliseconds in typical applications.  And a hypothetical Java `Arrays.resize` would need to run one every time it was called, which is likely to be substantially less efficient than just copying the array's contents into a new one, thus the entire point of `realloc` existing (that in some unusual circumstances it's faster, and isn't ever noticeably slower than making a new copy) is essentially negated.  
> **username_5** (2023-07-23): @occipita: Agreed that stop-the-world GC systems that globally update direct references can't accommodate operations that might require expanding objects in place.  Such a system could allow objects to be shrunk, however, with the proviso that storage wouldn't become available until the next GC cycle.  That's not really a problem, though, since nobody would care whether the memory was available before the next GC cycle.  
---
### Answer by username_9 on 2023-07-13. Score: 8
Java couldn't allow this because of how its memory is laid out. There are four pools, each of increasing size. Every time an object is created, it is added to the smallest pool, in a contiguous manner. Objects that go out of scope don't immediately get deallocated, instead waiting for the next GC cycle. When that pool is full, all objects in the pool are checked for aliveness. If they are, they move to the next larger pool. The pool is then cleared at the end of the GC cycle. This happens for each larger pool, until the largest, which requires the most work to clean up, but rarely ever does. As such, a reallocation would require all members of the pool to potentially move to make space, or the object would have to be placed at the end of the pool, and everything else would move, and it may even trigger an early GC cycle in that pool if there's insufficient space.

C++ has a different memory layout, but the ideas are kind of the same. Memory is allocated contiguously, so increasing the size almost always requires a move operation. However, since we don't control the pointer, only references, and since multiple references can exist (which is also true for Java), that means that the language would have to specify that references are also updated automatically. This could be a major performance problem. One way to work around this problem is by using smart pointers. Your code would only ever interact with a pointer that is guaranteed to not be reallocated, and that pointer would point to the data that can move. This way, you maintain just one reference to the object, which improves performance.

Other strategies are possible, such as intentionally leaving space after every object, but this would trade the risk of movement in exchange for wasted memory usage. The language could also just keep track of the references in some kind of list, and therefore know how to update the references. Either way, such languages would likely be wasteful with memory or processing time. The fastest way to access data is direct access, and that typically means limiting what you can do with that memory once allocated.
> **Comments:**
> **username_10** (2023-07-16): I'm not that much into current Java GC strategy, but if I recall correctly, they moved away from having fixed pools and all survining GC strategies are mark&copy anyway. But I could be mistaken.  
> **username_9** (2023-07-16): @feldentm This answer is intentionally written as more abstract, rather than being overly technical. You are correct that some details have changed wrt exactly how pools are allocated and cleared, but these differences don't matter at a high level. There's still young and old generations, promotion still occurs, etc. It's been incremental changes, like concurrent cleanup, aggressive optimization of the memory maps used, and so on, that make GC more efficient these days.  
> **username_5** (2023-07-17): An essential feature of Java is that as long as any reference exists and isn't null, it will identify an object of the same type and size.  Reallocating arrays with different sizes would break this.  
---
### Answer by username_6 on 2023-07-15. Score: 5
In C, the memory location of the object affected by calling realloc may change, meaning you have to update your pointers to the object after calling it.  The canonical way of using it is:
ptr = realloc(ptr, newSize);

If there are other copies of the pointer, you need to make sure they're updated too. In reality, almost all code that uses realloc works on pointers that only have one copy.
In a language with garbage collection, copying the contents and updating the references will cause the original object to be deleted.  This means that the Java code:
array = Arrays.copyOf (array, newSize)

is actually directly equivalent in the case where there is no other reference to array.  Unfortunately, we cannot directly modify the allocation because in most implementations there is no way of telling that array is the only copy of the reference: the garbage collector can only find out when there are no copies, but not identify how many copies there are.  A reference counting GC may be able to achieve this, but Java was not designed with using such a GC in mind.
> **Comments:**
> **username_7** (2023-07-18): I wouldn't call that the "canonical" way to use `realloc()`.  A common _wrong_ way, perhaps...  
> **username_8** (2023-07-24): @TobySpeight they're just omitting the error checking for brevity here. The important point is that you have to reassign the original pointer.  
> **username_7** (2023-07-27): I hope so @Barmar.  Unfortunately, I've seen almost exactly that line in real code, so it bears mention that we mustn't reassign `ptr` when `realloc()` has failed and left the existing memory block untouched.  
---
