Sometimes constraints are questionable

[Stuart Marks]

Hi Jim,

This was mentioned previously in this thread but not discussed very much. I 
suggest you take a look at jdk.internal.util.ArraysSupport.newLength(). Ivan 
Gerasimov and I worked this over fairly closely last year, and I'm pretty sure 
it does what Martin is saying, which I also think is the right thing.

The intent is that it be used for things that have growable arrays, where the 
array might have a larger capacity than the logical number of elements currently 
stored. Sometimes the array needs to be grown to accommodate an immediate need 
(minGrowth) but it's desired to grow larger (prefGrowth) in anticipation of 
future needs. If minGrowth can't be accommodated, it throws OOME, but if 
prefGrowth can't be accommodated, it might be acceptable to provide a smaller 
amount of growth.

(Of course, all this assumes that there is sufficient memory available to 
allocate the actual array. ArraysSupport.newLength doesn't attempt to ascertain 
that.)

One issue is integer wraparound (overflow). This is the primary value that 
ArraysSupport.newLength provides. It would be good to centralize these 
computations instead of having them be spread all over.

Another issue is the one that MAX_ARRAY_LENGTH (also called MAX_ARRAY_SIZE) is 
trying to address. This is sort-of a misnomer. It's not the actual maximum array 
size (which in fact isn't known the the library). It's actually the maximum 
array size that the library is fairly confident the VM can provide, assuming 
that enough memory is actually available. What the heck does that mean?

The theoretical maximum array size is Integer.MAX_VALUE, since the JLS and JVMS 
don't allow anything larger. However, actual VM implementations will refuse to 
allocate an array above a certain amount slightly smaller than that, even if 
there is enough memory available. In practice, I believe the values for current 
Hotspot are Integer.MAX_VALUE-3 or Integer.MAX_VALUE-2, depending on whether 
compressed OOPS are in use.

Why is this significant? Consider the following case, where the capacity of 
something is currently Integer.MAX_VALUE-100, and it's filled with elements. The 
application performs some operation that requires 50 elements (minGrowth) be 
added. A new array could certainly be allocated with size Integer.MAX_VALUE-50, 
but typical growth policies for these kinds of containers want to increase the 
current capacity by 1.5x or 2x (prefGrowth). Doing this multiplication would 
exceed Integer.MAX_VALUE, so that won't work. Clearly, we need to clamp the 
capacity somewhere.

We don't want to clamp the capacity at Integer.MAX_VALUE, because this 
allocation would fail on every JVM I'm aware of, even if enough memory is 
available. So we don't do that. Instead, we clamp the preferred growth at some 
fairly arbitrary value smaller than Integer.MAX_VALUE, which is here called 
MAX_ARRAY_LENGTH, and increase the capacity to that instead. This allows the 
container's requested allocation to proceed: it satisfies minGrowth, but it 
doesn't satisfy prefGrowth. Instead, it returns a capacity value that's 
reasonably likely to succeed, given an unknown JVM implementation limit.

Recall that the container now has Integer.MAX_VALUE-50 elements and the capacity 
is MAX_ARRAY_SIZE, which is currently defined somewhat arbitrarily at 
Integer.MAX_VALUE-8. Suppose the application now wants to add 43 elements. What 
should happen?

We could say, this exceeds MAX_ARRAY_LENGTH, so refuse the request and throw 
OOME. This is reasonable and consistent in some sense, but perhaps not in 
another. Suppose there is sufficient memory, and the JVM does allow arrays of 
Integer.MAX_VALUE-7 to be created. Shouldn't we even try?

That's what hugeLength() does -- it returns a value that attempts an allocation 
beyond the max preferential growth, and leaves it up to the JVM to grant or 
refuse the request based on its own implementation limits.

Anyway, this is all quite subtle, and maybe comments in ArraysSupport don't 
describe this adequately. But the code that implements this kind of policy has 
been copied to different locations around the JDK, and it uses somewhat 
different terminology, and it might have slightly different bugs, but they're 
all essentially trying to implement this policy.

**

Several questions could be asked:

1) Is this the right policy for implementing growable arrays?

2) In cases where a class needs a growable array, can and should it be 
refactored to use ArraysSupport.newLength()?

3) Does ArraysSupport.newLength() need to be modified to accommodate needs of 
additional call sites?

4) We might want to consider refactoring PriorityBlockingQueue and ArrayDeque to 
use ArraysSupport.newLength, in order to provide a consistent policy for 
collections. Other growable-array-based collections (Vector, ArrayList, 
PriorityQueue) do already.

s'marks





On 6/1/20 4:47 AM, Jim Laskey wrote:
> Thanks David will run with that,
> 
> 
>> On May 31, 2020, at 8:34 PM, David Holmes <david.holmes at oracle.com> wrote:
>>
>> On 31/05/2020 12:29 am, Jim Laskey wrote:
>>> I'm working through https://bugs.openjdk.java.net/browse/JDK-8230744 <https://bugs.openjdk.java.net/browse/JDK-8230744> Several classes throw OutOfMemoryError without message .
>>> I'm wondering why hugeCapacity in src/jdk.zipfs/share/classes/jdk/nio/zipfs/ByteArrayChannel.java is defined as
>>>      /**
>>>       * The maximum size of array to allocate.
>>>       * Some VMs reserve some header words in an array.
>>>       * Attempts to allocate larger arrays may result in
>>>       * OutOfMemoryError: Requested array size exceeds VM limit
>>>       */
>>>      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
>>>      /**
>>>       * Increases the capacity to ensure that it can hold at least the
>>>       * number of elements specified by the minimum capacity argument.
>>>       *
>>>       * @param minCapacity the desired minimum capacity
>>>       */
>>>      private void grow(int minCapacity) {
>>>          // overflow-conscious code
>>>          int oldCapacity = buf.length;
>>>          int newCapacity = oldCapacity << 1;
>>>          if (newCapacity - minCapacity < 0)
>>>              newCapacity = minCapacity;
>>>          if (newCapacity - MAX_ARRAY_SIZE > 0)
>>>              newCapacity = hugeCapacity(minCapacity);
>>>          buf = Arrays.copyOf(buf, newCapacity);
>>>      }
>>>      private static int hugeCapacity(int minCapacity) {
>>>          if (minCapacity < 0) // overflow
>>>              throw new OutOfMemoryError();
>>
>> Not sure how we could have minCapacity < 0 at this point. It should have been checked before the call to grow, and grow will not make it negative.
>>
>>>          return (minCapacity > MAX_ARRAY_SIZE) ?
>>>              Integer.MAX_VALUE :
>>>              MAX_ARRAY_SIZE;
>>
>> That's a bug plain and simple. It should never report a size > MAX_ARRAY_SIZE.
>>
>>>      }
>>> It just seems that it's pushing the inevitable off to Arrays.copyOf.  Shouldn't it be:
>>>      private static int hugeCapacity(int minCapacity) {
>>>          if (minCapacity < 0 || minCapacity > MAX_ARRAY_SIZE) {
>>>              throw
>>>                  new OutOfMemoryError("ByteArrayChannel exceeds maximum size: " +
>>>                                        MAX_ARRAY_SIZE);
>>>          }
>>>                   return MAX_ARRAY_SIZE;
>>>      }
>>
>> That seems more appropriate to me - modulo the question mark over minCapacity being negative.
>>
>>> Real question: is there some hidden purpose behind this kind of logic?
>>
>> The basic strategy is to double the current capacity unless that will trigger an unnecessary exception, in which case just use the requested capacity, but again watch for the implementation limits.
>>
>> Cheers,
>> David
>> -----
>>
>>> Cheers,
>>> -- Jim
>