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

[Stefan Karlsson]

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