G1 GC consuming all CPU time

[Jon Masamitsu]

Forwarding this for Peter Harvey because I don't know what
happened to it (while it was waiting to be moderated).

==============================================

Hi,

I've constructed a more practical microbenchmark that demonstrates the 
previously-described issue in the G1 collector. The code at the end of 
this email will repeatedly prepend a million randomly-valued nodes to a 
doubly-linked list, and then apply a simple merge sort to that list. The 
merge sort manipulates many reference values, resulting in the same 
issues as described earlier.

Using just -XX:+UseG1GC with no other options, the VM will seemingly try 
to balance the number of concurrent refinement threads. But no matter 
how many threads it chooses to use, performance is significantly 
degraded when compare to the CMS collector.

When using the CMS collector my microbenchmark has output like:

Took 752 to prepend 1000000 and then sort all 1000000
Took 2114 to prepend 1000000 and then sort all 2000000
Took 2672 to prepend 1000000 and then sort all 3000000
Took 2752 to prepend 1000000 and then sort all 4000000
Took 2056 to prepend 1000000 and then sort all 5000000

When using the G1 collector my microbenchmark has output like:

Took 1693 to prepend 1000000 and then sort all 1000000
Took 5774 to prepend 1000000 and then sort all 2000000
Took 9546 to prepend 1000000 and then sort all 3000000
Took 15480 to prepend 1000000 and then sort all 4000000
Took 20235 to prepend 1000000 and then sort all 5000000

With the -XX:+UnlockDiagnosticVMOptions -XX:+G1SummarizeRSetStats 
-XX:G1SummarizeRSetStatsPeriod=1 options enabled I get diagnostic output 
like:

  Concurrent RS processed 29981518 cards
   Of 117869 completed buffers:
         18647 ( 15.8%) by conc RS threads.
         99222 ( 84.2%) by mutator threads.

  Concurrent RS processed 68819227 cards
   Of 273465 completed buffers:
        164272 ( 60.1%) by conc RS threads.
        109193 ( 39.9%) by mutator threads.


My original code was an extreme corner case of graph manipulation 
(though yes, we do ship a commercial product with that kind of code in 
it). I hope that 'merge sort on a linked list of random data' can serve 
as a more useful example of where the G1 collector will not perform 
well. From what I understand, any algorithm that modifies a large number 
of references connecting many small objects will bring out this 
behaviour in the G1 collector. For example, I would suspect that large 
reference-based heap structures (where inserted nodes have random 
values) may also cause issues for the G1 collector.

Regards,
Peter.

----

package linkedlist;

import java.util.Random;

public class List {
// Node in the linked list
public final static class Node {
Node prev;

Node next;

double value;
}

// Random number generator
private final Random random = new Random(12);

// Dummy node for the head
private final Node head = new Node();

// Split the list at the given node, and sort the right-hand side
private static Node splitAndSort(Node node, boolean ascending) {
// Split the list at the given node
if (node.prev != null)
node.prev.next = null;
node.prev = null;

// Ensure we have at LEAST two elements
if (node.next == null)
return node;

// Find the midpoint to split the list
Node mid = node.next;
Node end = node.next;
do {
end = end.next;
if (end != null) {
end = end.next;
mid = mid.next;
}
} while (end != null);

// Sort the two sides
Node list2 = splitAndSort(mid, ascending);
Node list1 = splitAndSort(node, ascending);

// Merge the two lists (setting prev only)
node = null;
while (true) {

if (list1 == null) {
list2.prev = node;
node = list2;
break;
} else if (list2 == null) {
list1.prev = node;
node = list1;
break;
} else if (ascending == (list1.value < list2.value)) {
list2.prev = node;
node = list2;
list2 = list2.next;
} else {
list1.prev = node;
node = list1;
list1 = list1.next;
}
}

// Fix all the nexts (based on the prevs)
while (node.prev != null) {
node.prev.next = node;
node = node.prev;
}

return node;
}

// Sort the nodes in ascending order
public void sortNodes() {
if (head.next != null) {
head.next = splitAndSort(head.next, true);
head.next.prev = head;
}
}

// Prepend a number of nodes with random values
public void prependNodes(int count) {
for (int i = 0; i < count; i++) {
Node node = new Node();
if (head.next != null) {
node.next = head.next;
head.next.prev = node;
}
node.value = random.nextDouble();
node.prev = head;
head.next = node;
}
}

public static void main(String[] args) {
List list = new List();
int count = 0;
long start = System.currentTimeMillis();
while (true) {
// Append a million random entries
list.prependNodes(1000000);
count += 1000000;

// Sort the entire list
list.sortNodes();

// Print the time taken for this pass
long end = System.currentTimeMillis();
System.out.println("Took " + (end - start) + " to prepend 1000000 and 
then sort all " + count);
start = end;
}
}
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/hotspot-gc-dev/attachments/20140605/f9434b4b/attachment.htm>