Quantcast

10 RFR: 8169039: Add unit tests for BitMap search operations

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

10 RFR: 8169039: Add unit tests for BitMap search operations

Kim Barrett
Please review this change to add a native unit test for BitMap search
operations, e.g. get_next_{zero,one}_offset and variants.

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

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

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

Re: 10 RFR: 8169039: Add unit tests for BitMap search operations

Kim Barrett
Looking for reviewers.

> On Feb 18, 2017, at 12:58 AM, Kim Barrett <[hidden email]> wrote:
>
> Please review this change to add a native unit test for BitMap search
> operations, e.g. get_next_{zero,one}_offset and variants.
>
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8169039
>
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.00/


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

Re: 10 RFR: 8169039: Add unit tests for BitMap search operations

Kim Barrett
> On Mar 3, 2017, at 5:00 AM, Kim Barrett <[hidden email]> wrote:
>
> Looking for reviewers.

Still looking for reviewers.

>> On Feb 18, 2017, at 12:58 AM, Kim Barrett <[hidden email]> wrote:
>>
>> Please review this change to add a native unit test for BitMap search
>> operations, e.g. get_next_{zero,one}_offset and variants.
>>
>> CR:
>> https://bugs.openjdk.java.net/browse/JDK-8169039
>>
>> Webrev:
>> http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.00/


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

Re: 10 RFR: 8169039: Add unit tests for BitMap search operations

David Holmes
Hi Kim,

On 14/03/2017 11:09 PM, Kim Barrett wrote:
>> On Mar 3, 2017, at 5:00 AM, Kim Barrett <[hidden email]> wrote:
>>
>> Looking for reviewers.
>
> Still looking for reviewers.

Maybe expand to hotspot-dev. Not sure who may be familiar with the code
being tested - I'm not. Nor do I know enough to follow exactly what the
test is doing.

Sorry.
David

>>> On Feb 18, 2017, at 12:58 AM, Kim Barrett <[hidden email]> wrote:
>>>
>>> Please review this change to add a native unit test for BitMap search
>>> operations, e.g. get_next_{zero,one}_offset and variants.
>>>
>>> CR:
>>> https://bugs.openjdk.java.net/browse/JDK-8169039
>>>
>>> Webrev:
>>> http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.00/
>
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 10 RFR: 8169039: Add unit tests for BitMap search operations

Stefan Karlsson
In reply to this post by Kim Barrett
Hi Kim,

On 2017-02-18 06:58, Kim Barrett wrote:
> Please review this change to add a native unit test for BitMap search
> operations, e.g. get_next_{zero,one}_offset and variants.
>
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8169039
>
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.00/
>

StefanJ and I reviewed this patch.

There seems to be a bug in the fourth nested for-loop in test_search_ranges:

   if (end + 2 * search_chunk_size < right) {
     c_end = search_nchunks;
     break;
   }

If we understand the code correctly this is supposed to limit the end
part of the [start, end) range that we test. This is similar to section
for the start part:

   if (left + 2 * search_chunk_size < start) {
     c_start = search_nchunks;
     break;
   }

The latter code snippet limits 'start' to the values [0, left + 2
search_chunk_size], which seems reasonable.

The former code snippet seems to be expected to limit 'end' to values
[right - 2 * search_chunk_size, MAX_SIZE_T]. However, this doesn't work
when 'right' is "large", say 15.

What happens is that the first iteration of the loop will find that
'end' is a low value, that's not in the range [right - 2 *
search_chunk_size, MAX_SIZE_T] so the two innermost for-loops are broken
out of, without proceeding to the higher 'end' values.

We think that the appropriate fix is to remove the setting of c_end:

   if (end + 2 * search_chunk_size < right) {
     // c_end = search_nchunks; <-- Remove this
     break;
   }

to allow the code to try the next chunk for c_end.

==========

Style comments:

Could you add a comment describing what the two snippets above is
intended to do? From what we could infer, this is only an optimization
to limit the search space?

----------

Can you add braces and new lines to the one-liner if-statements. For
example:

   if (start > left) expected = right;

----------

This code:

   idx_t expected = left;
   if (start > left) expected = right;
   if (start > right) expected = end;
   if (expected > end) expected = end;

and:

   idx_t start2 = expected + 1;
   if (start2 > end) start2 = end;
   expected = right;
   if (start2 > right) expected = end;
   if (expected > end) expected = end;

was non-obvious to us. Could it be rewritten using functions with
describing names? For example:

   // 'end' indicates no match.
   idx_t expected = end;

   if (is_within_range(left, start, end)) {
     expected = left;
   } else if (is_within_range(right, start, end)) {
     expected = right;
   }

or at least add some comments describing that piece of code?

----------

Other than that, this looks good. Thanks for writing these tests!

StefanK & StefanJ
Loading...