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

Stefan Karlsson stefan.karlsson at oracle.com
Wed Mar 22 14:44:10 UTC 2017

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;

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;

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

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 

   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;


   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

More information about the hotspot-runtime-dev mailing list