RFR: 8079136: Accessing a nested sublist leads to StackOverflowError (original) (raw)

Ivan Gerasimov ivan.gerasimov at oracle.com
Thu May 7 16🔞35 UTC 2015

Hi Martin!

I'm afraid of these changes - they are hard to review. Can't we fix the SOE with a relatively small change to ArrayList.SubList methods that recursively invoke parent methods to use iteration instead, i.e. can't you implement updateSizeAndModCount in the existing SubList class? Well. Another minor goal I had was to possibly unify two implementations of sublists in AbstractList.java and ArrayList.java. Let me do another try in that direction. What if sublist classes are made static inner classes, will it look better?

Please see the updated webrev: WEBREV: http://cr.openjdk.java.net/~igerasim/8079136/03/webrev/

---

I would make modCount an argument to updateSizeAndModCount. I did that initially, but later realized that this argument should never be different from root.modCount.

---

Separate out hot and cold code in subListRangeCheck (although pre-existing code had the same problem) + static void subListRangeCheck(int fromIndex, int toIndex, int size) { + if (fromIndex < 0)_ _+ throw new IndexOutOfBoundsException("fromIndex = " +_ _fromIndex);_ _+ if (toIndex > size) + throw new IndexOutOfBoundsException("toIndex = " + toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex(" + fromIndex + + ") > toIndex(" + toIndex + ")"); + } + if ((fromIndex < 0) | (toIndex > size) | (fromIndex > toIndex)) slowpath(); Recently, I investigated this possible way of optimization, and I was surprised to discover that javac generates more compact code for logical operators, comparing to bitwise operators for booleans.

I've just tried it again to refresh my memory and here are results for a simple function:

This >>> void f(int index) { if (index < 0 || index >= size) throw new Error(); } <<< compiles into 20 bytecode commads. This >>> void f(int index) { if (index < 0 | index >= size) throw new Error(); } <<< produces 34 commads.

This is because the bitwise or operator really operates on integers. So, javac first conditionally initializes an auxiliary integer variables to either 0 or 1, then ORs them, and then checks the result. As the result, we have 3 branches in the code above.

Another approach would be to do something like this: void f(int index) { int x = index | (size - 1 - index); if (x < 0) throw new Error(); } The code length (23) is still a bit greater, comparing to the first version, but on the other hand it's got only one branch. It's still not clear though, if this going to be more efficient or not.

I recommend to leave this code as is for now, and investigate the ways to optimize it in a different CR.

--- java style consensus has been converging on: java source files should have exactly one top-level class. It seems like you changed inner class SubList to be a top-level class - why? Until now, SubList and RandomAccessSubList were top-level classes in AbstractList.java. ArrayList.SubList was an inner class.

Wanting to make their implementations similar, I either had to make all of them inner classes (webrev #1), or top-level classes (like in webrev #2).

In my last attempt I made them inner static classes. Number of changes is relatively small, so it might be easier to review. Would you please take a look? http://cr.openjdk.java.net/~igerasim/8079136/03/webrev/

Sincerely yours, Ivan

More information about the core-libs-dev mailing list