JDK-8165313 : Inserting freed regions during Free Collection Set serial phase takes very long on huge heaps
  • Type: Bug
  • Component: hotspot
  • Sub-Component: gc
  • Affected Version: 9
  • Priority: P2
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2016-09-02
  • Updated: 2018-06-21
  • Resolved: 2016-09-12
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 9
9 b138Fixed
Related Reports
Relates :  
JDK-8165443 - Free Collection Set serial phase takes very long on large heaps
Relates :  
JDK-8034842 - Parallelize the Free CSet phase in G1
Description
The serial part to free the collection set on huge heaps with a very large collection set is very slow.

E.g.

Free collection Set: 430.7ms
  Free collection set serial:  421.2ms
  Young Free collection set: ... Avg. 4.2 ... Workers: 213
  Non-young free collection set: skipped

Heap size: 1.5TB (49152 total regions), eden size: 11793->0, survivor size: 5007->5007, old 871 -> 871, humongous: 16 -> 16

The problem is that inserting free regions in the free list without any ordering takes very long due to being and O(n^2) operation.
Comments
I changed the type of this issue to a bug: this change has originally been part of changes promised (actually performance requirements) to some customers with JDK-8034842. Due to some error, it has been left out.
07-09-2016
With that patch applied, free collection set serial goes down to ~40ms again on like ~1 TB young gens. It is still significant, and unneeded, but more work. I created JDK-8165443 after some analysis.
07-09-2016
Attached fix reduces free collection set serial time to ~20% of before. The remaining time could be investigated a little bit further though, maybe there are similar low-hanging fruit - potentially in another CR.
02-09-2016
The issue is insertion of free regions from the collection set into the free list. The collection set is most often not in any way sorted (actually it is typically sorted in descending heap region order), so the insertion (which is optimized for inserting elements that are in ascending order), is very slow. One fix is to sort the collection set indices in ascending order once before iterating over it. Tests that inserted the collection set region in reverse (relying on the fact that the collection set regions are mostly in descending heap region order), decreased the free collection set serial time to 1/4th. A perfectly ascending ordering of the collection set before insertion will make this operation O(n + m) + O(n * log n) from O(n^2).
02-09-2016
Basically the length of the free collection set serial phase has been underestimated a lot while fixing JDK-8034842. Internal tests showed it being a much smaller part of the pause at most, considered negligible.
02-09-2016
Can be reproduced with gcbasher with the following options: -Xmx20G -Xms20G -XX:G1HeapRegionSize=1m -XX:G1NewSizePercent=70 -XX:G1MaxNewSizePercent=85, resulting in ~80-100ms of free collection set serial time.
02-09-2016