[JAVA] I read the source of ArrayList I read

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.

But why is elementData transient? → Unsolved

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 ()! ??

L.139 why is javadoc comment @serial here? → Unsolved

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.

The capacity adjustment area is full of mysteries and 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.

LL.264-270 I don't understand the meaning of this method. → Unsolved

"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.

at the end

I wondered why the upper limit of IntMax-8 was, so it was a good opportunity to investigate. Next, ArrayDeque is recommended.

Recommended Posts

I read the source of ArrayList I read
I read the source of Integer
I read the source of Long
I read the source of Short
I read the source of Byte
I read the source of String
I read the Kotlin startbook
Is drainTo of LinkedBlockingQueue safe? I followed the source
05. I tried to stub the source of Spring Boot
I investigated the internal processing of Retrofit
[day: 5] I summarized the basics of Java
Read the Perelman treatise of Poincare conjecture
I want to output the day of the week
I checked the place of concern of java.net.URL # getPath
I understood the very basics of character input
I compared the characteristics of Java and .NET
I want to var_dump the contents of the intent
I touched on the new features of Java 15
I tried using the profiler of IntelliJ IDEA
I checked the number of taxis with Ruby
Try the free version of Progate [Java I]
[Java] How to get the URL of the transition source
ArrayList and the role of the interface seen from List
I examined the life cycle of the extension of JUnit Jupiter
The world of clara-rules (2)
I was addicted to the record of the associated model
I tried to summarize the state transition of docker
I saw the list view of Android development collectively
I tried to reduce the capacity of Spring Boot
Judgment of the calendar
I tried the new feature profiler of IntelliJ IDEA 2019.2.
The world of clara-rules (4)
I want to know the answer of the rock-paper-scissors app
Image processing: The basic structure of the image read by the program
I want to display the name of the poster of the comment
I summarized the display format of the JSON response of Rails
The world of clara-rules (1)
The world of clara-rules (3)
Read Java HashMap source
I read the "Object-Oriented Practical Guide", so a memorandum
Source of cellular objects
Read the Rails Guide (Overview of Action Controller) again
[Java] When writing the source ... A memorandum of understanding ①
I wrote a sequence diagram of the j.u.c.Flow sample
The world of clara-rules (5)
I summarized the types and basics of Java exceptions
The idea of quicksort
[WIP] I tried the configuration of Docker + Streama + NFS
I am keenly aware of the convenience of graphql-code-generator, part 2
I can't get out of the Rails dbconsole screen
I learned about the existence of a gemspec file
I want to be aware of the contents of variables!
I want to return the scroll position of UITableView!
The idea of jQuery
I made the server side of an online card game ①
I didn't understand the behavior of Java Scanner and .nextLine ().
I took a peek at the contents of Java's HashMap
[Java] ArrayList → Should I specify the size in array conversion?
I tried to summarize the basics of kotlin and java
Now, I understand the coordinate transformation method of UIView (Swift)
[Android] Exit the activity of the transition source at the time of screen transition