I read I read the source of ArrayList. I read the JDK source at any rate, so I thought about the unsolved points (4 places). Please replace IntMax in the text with Integer.MAX_VALUE. It was a hassle to write. At first, I wrote intMax, but it has changed to IntMax. what is that.
This is the answer in Part 4.
"LL.760-763 The reason why elementData is purposely set to transient and not written by defaultWriteObject () is to prevent unnecessary writing of the part larger than the size of elementData? !! 』
It's a waste to output null, null, null after size.
But I don't know why I'm doing s.writeInt (size) ;. Where is the compatibility of clone ()! ??
It seems to be to output the serialized fields of javadoc. I knew it for the first time today. Serialized format As for where to fly, there is a link called the serialized format in the related items of the ArrayList class.
(Addition) I misunderstood "here" as "here". Why was it in size but not in elementData? Did you omit it because it is transient? But should I add it because it is serialized with writeObject and readObject? I don't know because I've never added @serial in the first place. unsolved.
"Near the maximum value of int → If it overflows by 1.5 times and becomes a fairly small negative value, it will be misjudged as a> b, but if a-b> 0 (depending on the degree of overflow), it is okay. 』
Even if a * 1.5 overflows and becomes negative, it is within the 32-bit range when considering this as unsigned. Therefore, overflow can be determined by a * 1.5-(IntMax-8)> 0.
Although it is doubled in the ByteArrayOutputStream class, the maximum value immediately before is a = IntMax-8, so a * 2 = 2 * IntMax-16, and it is judged by a * 2- (IntMax-8) = IntMax-8> 0. it can. However, if a = IntMax, 2 * a- (IntMax-8) = IntMax + 8 <0, and the judgment may be missed. However, there may be no problem because the IntMax array cannot be secured with the current Java VM. (See below)
"L.244 I don't know why it is 8. 』
Actually, I wondered if I could secure an array up to IntMax, but the language specification is up to IntMax, but it seems that there are fewer VM implementations than this. For example, in Oracle VM, according to Maximum number of array elements in Java
32bit VM: 0x3fffffff - 3 (= 1,073,741,820)
64bit VM: 0x7fffffff - 2 (= 2,147,483,645)
It seems that it is.
Furthermore, with ByteArrayOutputStream, there is a bug that even a 64-bit VM can only be used up to about 0x3fffffff, and it seems that it has been fixed. In Java SE 8 Update 31, the size limit of ByteArrayOutputStream has been increased Before the correction, it was set to IntMax when it overflowed, but then it becomes OutOfMemory, so it is set to IntMax-8. IntMax-2 is fine considering only the Oracle VM, but it probably won't work with other Java VMs. Since the source is the same as the hugeCapacity of ArrayList, it seems that ArrayList is also fixed at this timing.
Furthermore, according to Cannot allocate array with Integer.MAX_VALUE elements, it was possible to secure up to IntMax in JDK 6, but IntMax in JDK 7 and JDK 8. There is a bug report saying that only up to -2 can be secured (it's a demon). "Closing this bug as will not fix since the current code works as designed." Yes, I will not fix it. It seems that IntMax-headerSize (8byte) is the limit for the convenience of GC. Then why is IntMax-2 OK? whatever.
"Why do you return Integer.MAX_VALUE here while saying Integer.MAX_VALUE --8 in L.244? 』
Certainly funny. Since IntMax-8 is the upper limit, I think it is more natural to throw OutOfMemory if it exceeds this. If you return IntMax, it should be OutOfMemory in Arrays.copyOf after this, but it's a bit strange.
"It is impossible to call minCapcity negative so far. I don't know what kind of case I'm assuming. 』
No, I think there are some negative conditions.
When called from public void ensureCapacity (int minCapacity) {, a negative check is made.
There is no negative check for minCapacity when called from private void ensureCapacityInternal (int minCapacity) {. In other words, when it comes in from add or addAll.
The current elementData.length is 0x60000000, and when multiplied by 1.5, it becomes 0x90000000 and overflows. On the other hand, if you pass a List of 0x60000000 to addAll, minCapacity becomes 0xC0000000 and overflows.
At this time, if (minCapacity - elementData.length > 0) if (newCapacity - minCapacity < 0) if (newCapacity - MAX_ARRAY_SIZE > 0) Are all true and huge Capacity is negative.
Separately if (newCapacity - minCapacity < 0) It is not necessary to set to true, so it is sufficient if it overflows by multiplying by 1.5 and minCapacity overflows. It is the same even if addAll of List of 0x20000000 to elementData.length is 0x60000000.
I wondered why the upper limit of IntMax-8 was, so it was a good opportunity to investigate. Next, ArrayDeque is recommended.
Recommended Posts