RFR: 8185757: QuickSort array size should be size_t

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RFR: 8185757: QuickSort array size should be size_t

Kim Barrett
Please review this change of the type of QuickSort::sort size
parameter from int to size_t, and propogating this change throughout
the QuickSort implementation (using size_t rather than int sizes and
indices) and tests.

Since I was touching the QuickSort code anyway, I made a couple of
additional changes.

- Re-ordered the internal template parameters, moving "idempotent" to
the front and allowing the array element type and the comparator type
to be deduced.

- Changed the handling of the result of calling the comparator, only
requiring it to return negative, zero, or positive, rather than
exactly -1, 0, or +1. This makes it consistent with the standard
library function qsort.

Also updated a couple of callers:

- In G1CollectionSet::finalize_old_part, removed no longer needed cast
of (size_t) size to int.

- In Method::sort_methods, removed unnecessary explicit template
argument, allowing it to be deduced.  I didn't change the length from
int to size_t here, because that had more fanout, and there are other
issues around its type.  For example, it is being passed to other
functions that expect a u2 value.

CR:
https://bugs.openjdk.java.net/browse/JDK-8185757

Webrev:
http://cr.openjdk.java.net/~kbarrett/8185757/hotspot.00/

Testing:
JPRT. In addition to unit testing, sorting gets exercised by G1 and by
class file parsing (sort_methods).

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Thomas Schatzl
Hi Kim,

On Wed, 2017-08-02 at 19:29 -0400, Kim Barrett wrote:

> Please review this change of the type of QuickSort::sort size
> parameter from int to size_t, and propogating this change throughout
> the QuickSort implementation (using size_t rather than int sizes and
> indices) and tests.
>
> Since I was touching the QuickSort code anyway, I made a couple of
> additional changes.
>
> - Re-ordered the internal template parameters, moving "idempotent" to
> the front and allowing the array element type and the comparator type
> to be deduced.
>
> - Changed the handling of the result of calling the comparator, only
> requiring it to return negative, zero, or positive, rather than
> exactly -1, 0, or +1. This makes it consistent with the standard
> library function qsort.

Not sure if the change of the do-while to the for-loops improves
readability that much.
However, please put the closing brackets of these into extra lines
(quicksort.hpp:76,77) to avoid the casual reader to overlook them.

> Also updated a couple of callers:
>
> - In G1CollectionSet::finalize_old_part, removed no longer needed
> cast of (size_t) size to int.

Yes :)

>
> - In Method::sort_methods, removed unnecessary explicit template
> argument, allowing it to be deduced.  I didn't change the length from
> int to size_t here, because that had more fanout, and there are other
> issues around its type.  For example, it is being passed to other
> functions that expect a u2 value.

Fine with me. Please consider filing a CR for that.

> CR:
> https://bugs.openjdk.java.net/browse/JDK-8185757
>
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8185757/hotspot.00/
> JPRT. In addition to unit testing, sorting gets exercised by G1 and
> by class file parsing (sort_methods).

One (potential) pre-existing issue with the test: it uses random() to
create tests - however this decreases reproducability...

Thanks,
  Thomas

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Thomas Schatzl
Hi again,

On Thu, 2017-08-03 at 14:32 +0200, Thomas Schatzl wrote:

> Hi Kim,
>
> On Wed, 2017-08-02 at 19:29 -0400, Kim Barrett wrote:
> >
> > Please review this change of the type of QuickSort::sort size
> > parameter from int to size_t, and propogating this change
> > throughoutthe QuickSort implementation (using size_t rather than
> > int sizes and indices) and tests.
> >
> > Since I was touching the QuickSort code anyway, I made a couple of
> > additional changes.
> >
> > - Re-ordered the internal template parameters, moving "idempotent"
> > to the front and allowing the array element type and the comparator
> > type to be deduced.
> >
> > - Changed the handling of the result of calling the comparator,
> > only
> > requiring it to return negative, zero, or positive, rather than
> > exactly -1, 0, or +1. This makes it consistent with the standard
> > library function qsort.
> Not sure if the change of the do-while to the for-loops improves
> readability that much.
> However, please put the closing brackets of these into extra lines
> (quicksort.hpp:76,77) to avoid the casual reader to overlook them.

 forgot to mention: looks good apart from that. Do not need a re-review
for changing this.

Thanks,
  Thomas

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Kim Barrett
In reply to this post by Thomas Schatzl
> On Aug 3, 2017, at 8:32 AM, Thomas Schatzl <[hidden email]> wrote:
> On Wed, 2017-08-02 at 19:29 -0400, Kim Barrett wrote:
>> - Changed the handling of the result of calling the comparator, only
>> requiring it to return negative, zero, or positive, rather than
>> exactly -1, 0, or +1. This makes it consistent with the standard
>> library function qsort.
>
> Not sure if the change of the do-while to the for-loops improves
> readability that much.

I guess it wasn’t obvious that the change away from do-while was
necessitated by the change from int to size_t.  The left/right_index
variables were initialized to beyond the end, and always pre-inc/dec
in the do-while loops.  But in that scheme, left_index was initially -1.

While it would have worked to change the types to size_t and still
initialize left_index to (converted) -1, and left the do-while untouched
so that it incremented left_index to (overflowed) zero in the first
iteration, that seemed rather obscure to me, and also at some risk of
compiler / static analyzer warnings.

> However, please put the closing brackets of these into extra lines
> (quicksort.hpp:76,77) to avoid the casual reader to overlook them.

Sorry, but that just looks horrible.  As a casual reader, I wouldn’t
even look for them, since if they aren’t there then the code is
badly mis-indented.

>> - In Method::sort_methods, removed unnecessary explicit template
>> argument, allowing it to be deduced.  I didn't change the length from
>> int to size_t here, because that had more fanout, and there are other
>> issues around its type.  For example, it is being passed to other
>> functions that expect a u2 value.
>
> Fine with me. Please consider filing a CR for that.

I was thinking I should probably do that.

>> CR:
>> https://bugs.openjdk.java.net/browse/JDK-8185757
>>
>> Webrev:
>> http://cr.openjdk.java.net/~kbarrett/8185757/hotspot.00/
>> JPRT. In addition to unit testing, sorting gets exercised by G1 and
>> by class file parsing (sort_methods).
>
> One (potential) pre-existing issue with the test: it uses random() to
> create tests - however this decreases reproducability…

Which has both good and bad aspects.  Printing the first random value
might help, so long as this remains a non-TEST_VM test; once the
VM is initialized there could be other concurrent callers of random()
that would alter the test’s sequence.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Thomas Schatzl
Hi,

On Thu, 2017-08-03 at 14:06 -0400, Kim Barrett wrote:

> >
> > On Aug 3, 2017, at 8:32 AM, Thomas Schatzl <[hidden email]
> > om> wrote:
> > On Wed, 2017-08-02 at 19:29 -0400, Kim Barrett wrote:
> > >
> > > - Changed the handling of the result of calling the comparator,
> > > only
> > > requiring it to return negative, zero, or positive, rather than
> > > exactly -1, 0, or +1. This makes it consistent with the standard
> > > library function qsort.
> > Not sure if the change of the do-while to the for-loops improves
> > readability that much.
> I guess it wasn’t obvious that the change away from do-while was
> necessitated by the change from int to size_t.  The left/right_index
> variables were initialized to beyond the end, and always pre-inc/dec
> in the do-while loops.  But in that scheme, left_index was initially
> -1.
>
> While it would have worked to change the types to size_t and still
> initialize left_index to (converted) -1, and left the do-while
> untouched
> so that it incremented left_index to (overflowed) zero in the first
> iteration, that seemed rather obscure to me, and also at some risk of
> compiler / static analyzer warnings.

Okay.

> > However, please put the closing brackets of these into extra lines
> > (quicksort.hpp:76,77) to avoid the casual reader to overlook them.
> Sorry, but that just looks horrible.  As a casual reader, I wouldn’t
> even look for them, since if they aren’t there then the code is
> badly mis-indented.

Actually I was already at writing about an issue with indentation when
I noticed the brackets :)

Not insisting on changing this.

> > >
> > > CR:
> > > https://bugs.openjdk.java.net/browse/JDK-8185757
> > >
> > > Webrev:
> > > http://cr.openjdk.java.net/~kbarrett/8185757/hotspot.00/
> > > JPRT. In addition to unit testing, sorting gets exercised by G1
> > > and
> > > by class file parsing (sort_methods).
> > One (potential) pre-existing issue with the test: it uses random()
> > to
> > create tests - however this decreases reproducability…
> Which has both good and bad aspects.  Printing the first random value
> might help, so long as this remains a non-TEST_VM test; once the
> VM is initialized there could be other concurrent callers of random()
> that would alter the test’s sequence.

Just commenting when I read over it. Yes, multiple tests running at the
same time another aspect.

Thanks,
  Thomas
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Kim Barrett
> On Aug 3, 2017, at 3:05 PM, Thomas Schatzl <[hidden email]> wrote:
>
> Hi,
>
> On Thu, 2017-08-03 at 14:06 -0400, Kim Barrett wrote:
>>>
>>> On Aug 3, 2017, at 8:32 AM, Thomas Schatzl <[hidden email]
>>> om> wrote:
>>> However, please put the closing brackets of these into extra lines
>>> (quicksort.hpp:76,77) to avoid the casual reader to overlook them.
>> Sorry, but that just looks horrible.  As a casual reader, I wouldn’t
>> even look for them, since if they aren’t there then the code is
>> badly mis-indented.
>
> Actually I was already at writing about an issue with indentation when
> I noticed the brackets :)
>
> Not insisting on changing this.

I added a couple of asserts to check for buffer overruns due to a bad comparator:

diff -r 6b62ed03a6a6 -r 7616ceb92653 src/share/vm/utilities/quickSort.hpp
--- a/src/share/vm/utilities/quickSort.hpp Fri Aug 04 18:02:51 2017 -0400
+++ b/src/share/vm/utilities/quickSort.hpp Fri Aug 04 19:17:36 2017 -0400
@@ -73,8 +73,12 @@
     T pivot_val = array[pivot];
 
     for ( ; true; ++left_index, --right_index) {
-      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {}
-      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {}
+      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
+        assert(left_index < length, "reached end of partition");
+      }
+      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {
+        assert(right_index > 0, "reached start of partition");
+      }
 
       if (left_index < right_index) {
         if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Thomas Schatzl
Hi,

On Fri, 2017-08-04 at 19:20 -0400, Kim Barrett wrote:
> >
> >
> > > > [...]

> > > > However, please put the closing brackets of these into extra
> > > > lines
> > > > (quicksort.hpp:76,77) to avoid the casual reader to overlook
> > > > them.
> > > Sorry, but that just looks horrible.  As a casual reader, I
> > > wouldn’t even look for them, since if they aren’t there then the
> > > code is badly mis-indented.
> > Actually I was already at writing about an issue with indentation
> > when I noticed the brackets :)
> >
> > Not insisting on changing this.
> I added a couple of asserts to check for buffer overruns due to a bad
> comparator:
>
> diff -r 6b62ed03a6a6 -r 7616ceb92653
> src/share/vm/utilities/quickSort.hpp
> --- a/src/share/vm/utilities/quickSort.hpp Fri Aug 04 18:02:51
> 2017 -0400
> +++ b/src/share/vm/utilities/quickSort.hpp Fri Aug 04 19:17:36
> 2017 -0400
> @@ -73,8 +73,12 @@
>      T pivot_val = array[pivot];
>  
>      for ( ; true; ++left_index, --right_index) {
> -      for ( ; comparator(array[left_index], pivot_val) < 0;
> ++left_index) {}
> -      for ( ; comparator(array[right_index], pivot_val) > 0; --
> right_index) {}
> +      for ( ; comparator(array[left_index], pivot_val) < 0;
> ++left_index) {
> +        assert(left_index < length, "reached end of partition");
> +      }
> +      for ( ; comparator(array[right_index], pivot_val) > 0; --
> right_index) {
> +        assert(right_index > 0, "reached start of partition");
> +      }
>  
>        if (left_index < right_index) {
>          if (!idempotent || comparator(array[left_index],
> array[right_index]) != 0) {
>

  looks good.

Thanks a lot.

Thomas

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

coleen.phillimore
In reply to this post by Kim Barrett


This looks good.  I don't think we'll change the methods->length()
because it's limited to u2 and used to set method_idnum() which is a
u2.  Odd that the compiler doesn't complain about narrowing an int into
a u2 though.

Coleen

On 8/4/17 7:20 PM, Kim Barrett wrote:

>> On Aug 3, 2017, at 3:05 PM, Thomas Schatzl <[hidden email]> wrote:
>>
>> Hi,
>>
>> On Thu, 2017-08-03 at 14:06 -0400, Kim Barrett wrote:
>>>> On Aug 3, 2017, at 8:32 AM, Thomas Schatzl <[hidden email]
>>>> om> wrote:
>>>> However, please put the closing brackets of these into extra lines
>>>> (quicksort.hpp:76,77) to avoid the casual reader to overlook them.
>>> Sorry, but that just looks horrible.  As a casual reader, I wouldn’t
>>> even look for them, since if they aren’t there then the code is
>>> badly mis-indented.
>> Actually I was already at writing about an issue with indentation when
>> I noticed the brackets :)
>>
>> Not insisting on changing this.
> I added a couple of asserts to check for buffer overruns due to a bad comparator:
>
> diff -r 6b62ed03a6a6 -r 7616ceb92653 src/share/vm/utilities/quickSort.hpp
> --- a/src/share/vm/utilities/quickSort.hpp Fri Aug 04 18:02:51 2017 -0400
> +++ b/src/share/vm/utilities/quickSort.hpp Fri Aug 04 19:17:36 2017 -0400
> @@ -73,8 +73,12 @@
>       T pivot_val = array[pivot];
>  
>       for ( ; true; ++left_index, --right_index) {
> -      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {}
> -      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {}
> +      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
> +        assert(left_index < length, "reached end of partition");
> +      }
> +      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {
> +        assert(right_index > 0, "reached start of partition");
> +      }
>  
>         if (left_index < right_index) {
>           if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
>
>

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Kim Barrett
In reply to this post by Thomas Schatzl
> On Aug 7, 2017, at 5:42 AM, Thomas Schatzl <[hidden email]> wrote:
>
> Hi,
>
> On Fri, 2017-08-04 at 19:20 -0400, Kim Barrett wrote:
>>>
>>>
>>>>> [...]
>
>>>>> However, please put the closing brackets of these into extra
>>>>> lines
>>>>> (quicksort.hpp:76,77) to avoid the casual reader to overlook
>>>>> them.
>>>> Sorry, but that just looks horrible.  As a casual reader, I
>>>> wouldn’t even look for them, since if they aren’t there then the
>>>> code is badly mis-indented.
>>> Actually I was already at writing about an issue with indentation
>>> when I noticed the brackets :)
>>>
>>> Not insisting on changing this.
>> I added a couple of asserts to check for buffer overruns due to a bad
>> comparator:
>>
>> diff -r 6b62ed03a6a6 -r 7616ceb92653
>> src/share/vm/utilities/quickSort.hpp
>> --- a/src/share/vm/utilities/quickSort.hpp Fri Aug 04 18:02:51
>> 2017 -0400
>> +++ b/src/share/vm/utilities/quickSort.hpp Fri Aug 04 19:17:36
>> 2017 -0400
>> @@ -73,8 +73,12 @@
>>      T pivot_val = array[pivot];
>>  
>>      for ( ; true; ++left_index, --right_index) {
>> -      for ( ; comparator(array[left_index], pivot_val) < 0;
>> ++left_index) {}
>> -      for ( ; comparator(array[right_index], pivot_val) > 0; --
>> right_index) {}
>> +      for ( ; comparator(array[left_index], pivot_val) < 0;
>> ++left_index) {
>> +        assert(left_index < length, "reached end of partition");
>> +      }
>> +      for ( ; comparator(array[right_index], pivot_val) > 0; --
>> right_index) {
>> +        assert(right_index > 0, "reached start of partition");
>> +      }
>>  
>>        if (left_index < right_index) {
>>          if (!idempotent || comparator(array[left_index],
>> array[right_index]) != 0) {
>>
>
>   looks good.
>
> Thanks a lot.
>
> Thomas

Thanks.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: RFR: 8185757: QuickSort array size should be size_t

Kim Barrett
In reply to this post by coleen.phillimore
> On Aug 7, 2017, at 8:22 PM, [hidden email] wrote:
>
>
>
> This looks good.

Thanks.

>  I don't think we'll change the methods->length() because it's limited to u2 and used to set method_idnum() which is a u2.  Odd that the compiler doesn't complain about narrowing an int into a u2 though.
>
> Coleen
>
> On 8/4/17 7:20 PM, Kim Barrett wrote:
>>> On Aug 3, 2017, at 3:05 PM, Thomas Schatzl <[hidden email]> wrote:
>>>
>>> Hi,
>>>
>>> On Thu, 2017-08-03 at 14:06 -0400, Kim Barrett wrote:
>>>>> On Aug 3, 2017, at 8:32 AM, Thomas Schatzl <[hidden email]
>>>>> om> wrote:
>>>>> However, please put the closing brackets of these into extra lines
>>>>> (quicksort.hpp:76,77) to avoid the casual reader to overlook them.
>>>> Sorry, but that just looks horrible.  As a casual reader, I wouldn’t
>>>> even look for them, since if they aren’t there then the code is
>>>> badly mis-indented.
>>> Actually I was already at writing about an issue with indentation when
>>> I noticed the brackets :)
>>>
>>> Not insisting on changing this.
>> I added a couple of asserts to check for buffer overruns due to a bad comparator:
>>
>> diff -r 6b62ed03a6a6 -r 7616ceb92653 src/share/vm/utilities/quickSort.hpp
>> --- a/src/share/vm/utilities/quickSort.hpp Fri Aug 04 18:02:51 2017 -0400
>> +++ b/src/share/vm/utilities/quickSort.hpp Fri Aug 04 19:17:36 2017 -0400
>> @@ -73,8 +73,12 @@
>>      T pivot_val = array[pivot];
>>        for ( ; true; ++left_index, --right_index) {
>> -      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {}
>> -      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {}
>> +      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
>> +        assert(left_index < length, "reached end of partition");
>> +      }
>> +      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {
>> +        assert(right_index > 0, "reached start of partition");
>> +      }
>>          if (left_index < right_index) {
>>          if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {


Loading...