<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Forwarding this for Peter Harvey because I don't know what<br>
happened to it (while it was waiting to be moderated).<br>
<br>
==============================================<br>
<br>
<div>Hi,</div>
<div><br>
</div>
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.
<div>
<br>
</div>
<div>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.</div>
<div><br>
</div>
<div>
<div>When using the CMS collector my microbenchmark has output
like:</div>
<div><br>
</div>
<div>
<div>Took 752 to prepend 1000000 and then sort all 1000000</div>
<div>Took 2114 to prepend 1000000 and then sort all 2000000</div>
<div>Took 2672 to prepend 1000000 and then sort all 3000000</div>
<div>Took 2752 to prepend 1000000 and then sort all 4000000</div>
<div>Took 2056 to prepend 1000000 and then sort all 5000000</div>
</div>
</div>
<div><br>
</div>
<div>
<div>
<div>When using the G1 collector my microbenchmark has output
like:</div>
</div>
<div><br>
</div>
<div>
<div>Took 1693 to prepend 1000000 and then sort all 1000000</div>
<div>Took 5774 to prepend 1000000 and then sort all 2000000</div>
<div>Took 9546 to prepend 1000000 and then sort all 3000000</div>
<div>Took 15480 to prepend 1000000 and then sort all 4000000</div>
<div>Took 20235 to prepend 1000000 and then sort all 5000000</div>
</div>
</div>
<div><br>
</div>
<div>With the -XX:+UnlockDiagnosticVMOptions
-XX:+G1SummarizeRSetStats -XX:G1SummarizeRSetStatsPeriod=1 options
enabled I get diagnostic output like:<br>
</div>
<div>
<div><br>
</div>
<div>
<div> Concurrent RS processed 29981518 cards</div>
<div> Of 117869 completed buffers:</div>
<div> 18647 ( 15.8%) by conc RS threads.</div>
<div> 99222 ( 84.2%) by mutator threads.</div>
</div>
<div><br>
</div>
<div> Concurrent RS processed 68819227 cards</div>
<div>
Of 273465 completed buffers:</div>
<div> 164272 ( 60.1%) by conc RS threads.</div>
<div> 109193 ( 39.9%) by mutator threads.</div>
</div>
<div><br>
</div>
<div><br>
</div>
<div>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.<br>
</div>
<div><br>
</div>
<div>Regards,</div>
<div>Peter.</div>
<div><br>
</div>
----<br>
<div><br>
</div>
<div>
<div>package linkedlist;</div>
<div><br>
</div>
<div>import java.util.Random;</div>
<div><br>
</div>
<div>public class List {</div>
<div><span class="" style="white-space:pre"> </span>// Node in
the linked list</div>
<div><span class="" style="white-space:pre"> </span>public final
static class Node {</div>
<div><span class="" style="white-space:pre"> </span>Node prev;</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>Node next;</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>double value;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Random
number generator</div>
<div><span class="" style="white-space:pre"> </span>private final
Random random = new Random(12);</div>
<div><br>
</div>
<div>
<span class="" style="white-space:pre"> </span>// Dummy node
for the head</div>
<div><span class="" style="white-space:pre"> </span>private final
Node head = new Node();</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Split the
list at the given node, and sort the right-hand side</div>
<div><span class="" style="white-space:pre"> </span>private
static Node splitAndSort(Node node, boolean ascending) {</div>
<div><span class="" style="white-space:pre"> </span></div>
<div><span class="" style="white-space:pre"> </span>// Split the
list at the given node</div>
<div><span class="" style="white-space:pre"> </span>if (node.prev
!= null)</div>
<div><span class="" style="white-space:pre"> </span>node.prev.next
= null;</div>
<div><span class="" style="white-space:pre"> </span>node.prev =
null;</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Ensure we
have at LEAST two elements</div>
<div><span class="" style="white-space:pre"> </span>if (node.next
== null)</div>
<div><span class="" style="white-space:pre"> </span>return node;</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Find the
midpoint to split the list</div>
<div><span class="" style="white-space:pre"> </span>Node mid =
node.next;</div>
<div><span class="" style="white-space:pre"> </span>Node end =
node.next;</div>
<div><span class="" style="white-space:pre"> </span>do {</div>
<div><span class="" style="white-space:pre"> </span>end =
end.next;</div>
<div><span class="" style="white-space:pre"> </span>if (end !=
null) {</div>
<div>
<span class="" style="white-space:pre"> </span>end = end.next;</div>
<div><span class="" style="white-space:pre"> </span>mid =
mid.next;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>} while (end
!= null);</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Sort the
two sides</div>
<div><span class="" style="white-space:pre"> </span>Node list2 =
splitAndSort(mid, ascending);</div>
<div><span class="" style="white-space:pre"> </span>Node list1 =
splitAndSort(node, ascending);</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Merge the
two lists (setting prev only)</div>
<div><span class="" style="white-space:pre"> </span>node = null;</div>
<div><span class="" style="white-space:pre"> </span>while (true)
{</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>if (list1 ==
null) {</div>
<div><span class="" style="white-space:pre"> </span>list2.prev =
node;</div>
<div><span class="" style="white-space:pre"> </span>node = list2;</div>
<div><span class="" style="white-space:pre"> </span>break;</div>
<div><span class="" style="white-space:pre"> </span>} else if
(list2 == null) {</div>
<div><span class="" style="white-space:pre"> </span>list1.prev =
node;</div>
<div><span class="" style="white-space:pre"> </span>node = list1;</div>
<div><span class="" style="white-space:pre"> </span>break;</div>
<div><span class="" style="white-space:pre"> </span>} else if
(ascending == (list1.value < list2.value)) {</div>
<div><span class="" style="white-space:pre"> </span>list2.prev =
node;</div>
<div><span class="" style="white-space:pre"> </span>node = list2;</div>
<div><span class="" style="white-space:pre"> </span>list2 =
list2.next;</div>
<div><span class="" style="white-space:pre"> </span>} else {</div>
<div><span class="" style="white-space:pre"> </span>list1.prev =
node;</div>
<div><span class="" style="white-space:pre"> </span>node = list1;</div>
<div><span class="" style="white-space:pre"> </span>list1 =
list1.next;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div>
<span class="" style="white-space:pre"> </span>// Fix all the
nexts (based on the prevs)</div>
<div><span class="" style="white-space:pre"> </span>while
(node.prev != null) {</div>
<div><span class="" style="white-space:pre"> </span>node.prev.next
= node;</div>
<div><span class="" style="white-space:pre"> </span>node =
node.prev;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>return node;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Sort the
nodes in ascending order</div>
<div><span class="" style="white-space:pre"> </span>public void
sortNodes() {</div>
<div><span class="" style="white-space:pre"> </span>if (head.next
!= null) {</div>
<div><span class="" style="white-space:pre"> </span>head.next =
splitAndSort(head.next, true);</div>
<div><span class="" style="white-space:pre"> </span>head.next.prev
= head;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Prepend a
number of nodes with random values</div>
<div><span class="" style="white-space:pre"> </span>public void
prependNodes(int count) {</div>
<div><span class="" style="white-space:pre"> </span>for (int i =
0; i < count; i++) {</div>
<div><span class="" style="white-space:pre"> </span>Node node =
new Node();</div>
<div><span class="" style="white-space:pre"> </span>if (head.next
!= null) {</div>
<div><span class="" style="white-space:pre"> </span>node.next =
head.next;</div>
<div><span class="" style="white-space:pre"> </span>head.next.prev
= node;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>node.value =
random.nextDouble();</div>
<div><span class="" style="white-space:pre"> </span>node.prev =
head;</div>
<div><span class="" style="white-space:pre"> </span>head.next =
node;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>public static
void main(String[] args) {</div>
<div><span class="" style="white-space:pre"> </span>List list =
new List();</div>
<div><span class="" style="white-space:pre"> </span>int count =
0;</div>
<div><span class="" style="white-space:pre"> </span></div>
<div><span class="" style="white-space:pre"> </span>long start =
System.currentTimeMillis();</div>
<div><span class="" style="white-space:pre"> </span>while (true)
{</div>
<div><span class="" style="white-space:pre"> </span></div>
<div><span class="" style="white-space:pre"> </span>// Append a
million random entries</div>
<div><span class="" style="white-space:pre"> </span>list.prependNodes(1000000);</div>
<div><span class="" style="white-space:pre"> </span>count +=
1000000;</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Sort the
entire list</div>
<div><span class="" style="white-space:pre"> </span>list.sortNodes();</div>
<div><br>
</div>
<div><span class="" style="white-space:pre"> </span>// Print the
time taken for this pass</div>
<div><span class="" style="white-space:pre"> </span>long end =
System.currentTimeMillis();</div>
<div><span class="" style="white-space:pre"> </span>System.out.println("Took
" + (end - start) + " to prepend 1000000 and then sort all " +
count);</div>
<div><span class="" style="white-space:pre"> </span>start = end;</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div><span class="" style="white-space:pre"> </span>}</div>
<div>}</div>
</div>
</body>
</html>