<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
<br>
Coleen, <br>
<br>
Thanks for the review!<br>
<br>
On 2011-06-23 03:46, Coleen Phillimore wrote:
<blockquote cite="mid:4E029B13.7030308@oracle.com" type="cite">
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<title></title>
<span class="Apple-style-span" style="border-collapse: separate;
color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style:
normal; font-variant: normal; font-weight: normal;
letter-spacing: normal; line-height: normal; orphans: 2;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; font-size: medium;">
<pre><a moz-do-not-send="true" href="http://cr.openjdk.java.net/%7Ebrutisso/7016112/webrev.01/src/share/vm/utilities/quicksort.cpp.html">http://cr.openjdk.java.net/~brutisso/7016112/webrev.01/src/share/vm/utilities/quicksort.cpp.html</a>
46 bool aIsOdd = a % 2 == 1;
47 bool bIsOdd = b % 2 == 1;
</pre>
</span>Can you add () around the bit operations? Since the order
precedence of these operators is always surprising (at least to
me).<br>
</blockquote>
<br>
Yes, I'll do that.<br>
<br>
<blockquote cite="mid:4E029B13.7030308@oracle.com" type="cite"> I
like the way you set the pattern for the internal testing
framework. Thanks for getting this started.<br>
</blockquote>
<br>
Thanks, it was really useful to have the unit tests when I made this
fix.<br>
<br>
<blockquote cite="mid:4E029B13.7030308@oracle.com" type="cite"> When
we move these methodOops out of permgen, we might want to go back
to stdlib::quicksort. It would be less code for us to
maintain. Otherwise, this looks pretty straightforward and I like
this fix.<br>
</blockquote>
<br>
I agree that we should get back to stdlib::quicksort when it is safe
to use it again.<br>
<br>
Thanks,<br>
Bengt<br>
<br>
<blockquote cite="mid:4E029B13.7030308@oracle.com" type="cite"> <br>
Thanks,<br>
Coleen<br class="Apple-interchange-newline">
<br>
<br>
On 6/21/2011 5:32 PM, Bengt Rutisson wrote:
<blockquote cite="mid:4E010DEB.3030104@oracle.com" type="cite"> <br>
Hi again, <br>
<br>
For completeness. Here is the graph for sorting maximum length
arrays on Linux x64 (run on my laptop). These runs show that my
implementation takes twice as long as the stdlib version. I am
not happy about that, but I don't know how much effort it is
worth to optimize for this case. <br>
<br>
Bengt <br>
<br>
<br>
On 2011-06-21 14:50, Bengt Rutisson wrote: <br>
<blockquote type="cite"> <br>
Hi Runtime and GC, <br>
<br>
Sending this review request to both groups. I fixed a GC bug,
but the changes are in runtime code. <br>
<br>
The bug that I fixed is this one: <br>
7016112 CMS: crash during promotion testing <br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="http://monaco.sfbay.sun.com/detail.jsf?cr=7016112">http://monaco.sfbay.sun.com/detail.jsf?cr=7016112</a>
<br>
<br>
And here is the webrev: <br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="http://cr.openjdk.java.net/%7Ebrutisso/7016112/webrev.01/">http://cr.openjdk.java.net/~brutisso/7016112/webrev.01/</a>
<br>
<br>
The investigation to find the root of the crashes reported in
7016112 was quite lengthy. It is not that easy to read the CR
and figure out what is going on, so here is some background: <br>
<br>
When we load classes we store references to the methods of a
class in an object array. When we have loaded all methods we
sort the object array to allow binary search within the array.
To do this sort we use stdlib::qsort(), which is the standard
library quicksort implementation. <br>
<br>
If we are using CMS we might be doing concurrent marking while
we are sorting the object array. The object array can be found
by the concurrent marking code and it may start iterating over
the array while we are sorting it. The problem is that on
Windows the stdlib::qsort() is not implemented to do atomic
updates of elements in the array that it sorts. Instead it
does a byte-by-byte swap when it needs to swap two values.
That is an easy way to implement different element widths, but
it means that at some point in time one element may contain a
few bytes from the element above or below. If this happens at
the same time as the marking code is trying to read that
element, we will be marking some random address and not the
method that was supposed to be marked. <br>
<br>
On Solaris and Linux the stdlib::qsort() implementations try
to swap as wide data types as possible so this issue should
not occur there. On the other hand we have no guarantees that
this will always be how stdlib::qsort() is implemented. <br>
<br>
After some discussions about different ways of solving this we
came to the conclusion that the simplest way is to implement
our own quicksort that operates on the correct pointer width
(oop or narrowOop). <br>
<br>
So, this is what I have done to fix this bug. <br>
<br>
Also, it is likely that this problem will go away when the
perm gen removal project is finished. Right now it looks like
we will not be tracing and marking methods at all after that
change. <br>
<br>
* Questions * <br>
<br>
- Should we keep the bubble sort that is done before calling
quicksort in methodOopDesc::sort_methods() ? <br>
<br>
- Should we keep the idempotent option or should we try to
always use idempotent sorting (see performance test below)? <br>
<br>
- What is the best way to handle unit tests? I added a flag
called ExecuteInternalVMTests to run unit tests. This is in
line with the existing ErrorHandlerTest flag. My thought is
that we can use this same flag for other unit tests than just
the quicksort tests. Would be good if we could get these tests
executed by JPRT as well. I simply run these with "java
-XX:+ExecuteInternalVMTests -version". <br>
<br>
<br>
* Testing * <br>
<br>
Did the obvious testing: Ran JPRT with the changes in the
webrev and ran the failing nsk test from the bug
(nsk/sysdict/vm/stress/jck12a/sysdictj12a008) repeatedly for
sevaral days without failing. <br>
<br>
I created some unit tests for the quicksort implementation and
they all pass. <br>
<br>
I also made a build that sorts both with my own quicksort and
with stdlib::qsort and then compares that the arrays have the
same sort order. Ran this through JPRT and it seems to work on
all platforms. That run also included the unit tests. If
anybody wants to see how this testing was done, there is a
separate webrev for that build. The interesting code is in
methodOop.cpp: <br>
<br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="http://cr.openjdk.java.net/%7Ebrutisso/7016112/webrev-verify-sorting/">http://cr.openjdk.java.net/~brutisso/7016112/webrev-verify-sorting/</a>
<br>
<br>
* Performance * <br>
<br>
I am a bit unsure how to get any relevant performance data for
this change. What I have done so far is to create a class that
has 65535 methods (which is the maximum - the length of the
method array is u2) and I have measured how long it takes to
sort this method array. The methods have random names but
every hundredth method has 4 overloaded version. This makes
sure that there are some duplicates in the array. <br>
<br>
For now I have run this on my Windows x64 work station with 4
cpus and on a Solaris Sparc machine with 2 cpus (uname says:
SunOS sthsparc24 5.10 Generic_139555-08 sun4us sparc
FJSV,GPUZC-M Solaris). <br>
<br>
I am attaching graphs for the results. The Y-axis has time in
nano seconds. Judging by this my quicksort is a bit faster on
Windows and a bit slower on Solaris. But the interesting thing
is that the idempotent version is faster than the default
behavior on Windows and on par with the default on Solaris. I
assume that this is due to the fact that some stores can be
avoided if we don't do swap of duplicates. This means that (at
least on Windows) swap is more expensive than compare. If this
is true we should probably remove the special treatment of
idempotent. <br>
<br>
I could run this on more machines, but I am not sure how
relevant this type of data is. Most method arrays will be much
shorter and compared to reading the class from a file the sort
will be in the noise. <br>
<br>
Long email...I hope I covered most of the issues here. Let me
know if you have any questions. <br>
<br>
Thanks, <br>
Bengt <br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>