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

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

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
|

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
|

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
|

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
|

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
Reply | Threaded
Open this post in threaded view
|

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

Kim Barrett
> On Mar 22, 2017, at 10:44 AM, Stefan Karlsson <[hidden email]> wrote:
>
> 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.

Thanks for looking at this.

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

Well spotted.

When I added comments to these cutoffs (as requested, and I really
should have done that in the first place), I realized the situation is
even worse than you surmised.  I think I've corrected things now, and
added sufficient comments to help future readers (including me! It's
been a while since I originally wrote this test).

As you surmised, these bits are for limiting the search space, to
speed up the test.  Each of the (now 3) cuttoffs speeds up the test by
roughly a factor of 2; without any the test takes > 1sec on my desktop
machine, with them it takes < 120ms.  It's probably possible to
tighten up the cuttoff heuristics to further improve that, but they
add enough complication already that I'm wondering if they are worth
the trouble.

> This code:
> […]
> was non-obvious to us. Could it be rewritten using functions with describing names? For example:

Added compute_expected() helper.

New webrevs:
full: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01/
incr: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01.inc/

Reply | Threaded
Open this post in threaded view
|

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

Stefan Johansson


On 2017-04-02 00:47, Kim Barrett wrote:

>> On Mar 22, 2017, at 10:44 AM, Stefan Karlsson <[hidden email]> wrote:
>>
>> 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.
> Thanks for looking at this.
>
>> There seems to be a bug in the fourth nested for-loop in test_search_ranges:
> Well spotted.
>
> When I added comments to these cutoffs (as requested, and I really
> should have done that in the first place), I realized the situation is
> even worse than you surmised.  I think I've corrected things now, and
> added sufficient comments to help future readers (including me! It's
> been a while since I originally wrote this test).
I agree, I also think this works now :) Following exactly how the
different cutoffs work is still not obvious, but I have no good simple
idea how to improve it either.

> As you surmised, these bits are for limiting the search space, to
> speed up the test.  Each of the (now 3) cuttoffs speeds up the test by
> roughly a factor of 2; without any the test takes > 1sec on my desktop
> machine, with them it takes < 120ms.  It's probably possible to
> tighten up the cuttoff heuristics to further improve that, but they
> add enough complication already that I'm wondering if they are worth
> the trouble.
>
>> This code:
>> […]
>> was non-obvious to us. Could it be rewritten using functions with describing names? For example:
> Added compute_expected() helper.
>
> New webrevs:
> full: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01/
> incr: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01.inc/
>
Reviewed,
StefanJ
Reply | Threaded
Open this post in threaded view
|

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

Stefan Karlsson
In reply to this post by Kim Barrett
On 2017-04-02 00:47, Kim Barrett wrote:

>> On Mar 22, 2017, at 10:44 AM, Stefan Karlsson <[hidden email]> wrote:
>>
>> 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.
>
> Thanks for looking at this.
>
>> There seems to be a bug in the fourth nested for-loop in test_search_ranges:
>
> Well spotted.
>
> When I added comments to these cutoffs (as requested, and I really
> should have done that in the first place), I realized the situation is
> even worse than you surmised.  I think I've corrected things now, and
> added sufficient comments to help future readers (including me! It's
> been a while since I originally wrote this test).
>

OK

> As you surmised, these bits are for limiting the search space, to
> speed up the test.  Each of the (now 3) cuttoffs speeds up the test by
> roughly a factor of 2; without any the test takes > 1sec on my desktop
> machine, with them it takes < 120ms.  It's probably possible to
> tighten up the cuttoff heuristics to further improve that, but they
> add enough complication already that I'm wondering if they are worth
> the trouble.

The added checks added even more complexity to this already non-trivial
part of the test. So, if we want to tighten this even further I think we
need to think about ways to make it easier to read and understand the
cutoff logic.

>
>> This code:
>> […]
>> was non-obvious to us. Could it be rewritten using functions with describing names? For example:
>
> Added compute_expected() helper.
>

Thanks!

> New webrevs:
> full: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01/
> incr: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01.inc/
>

Reviewed.

StefanK
Reply | Threaded
Open this post in threaded view
|

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

Kim Barrett
In reply to this post by Stefan Johansson
> On Apr 7, 2017, at 8:19 AM, Stefan Johansson <[hidden email]> wrote:
>
>
>
> On 2017-04-02 00:47, Kim Barrett wrote:
>> […]
>> New webrevs:
>> full: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01/
>> incr: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01.inc/
>>
> Reviewed,
> StefanJ

Thanks.

Reply | Threaded
Open this post in threaded view
|

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

Kim Barrett
In reply to this post by Stefan Karlsson
> On Apr 7, 2017, at 8:26 AM, Stefan Karlsson <[hidden email]> wrote:
>
> On 2017-04-02 00:47, Kim Barrett wrote:
>> […]

>> New webrevs:
>> full: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01/
>> incr: http://cr.openjdk.java.net/~kbarrett/8169039/hotspot.01.inc/
>>
>
> Reviewed.
>
> StefanK

Thanks.

Reply | Threaded
Open this post in threaded view
|

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

Kim Barrett
There will be a delay in pushing this new test.  It seems the test
fails in a product build on Mac, due to
https://bugs.openjdk.java.net/browse/JDK-8178348.