RFR: 8155043: BitMap set operations assume clear bits beyond unaligned end

[Stefan Karlsson]

Hi Kim,

This looks mostly good to me. I have a few comments inlined:

On 2016-08-05 00:02, Kim Barrett wrote:
> Please review this change to the BitMap set operations to avoid
> depending on or modifying bits beyond the size of the BitMap when the
> size is not word aligned.  This change also adds some unit tests for
> these operations.
>
> In addition:
>
> - Changed set_from to use Copy::disjoint_words.  For other set
> operations, use a consistent iteration idiom for all.
>
> - In the set_xxx_with_result operations, eliminated conditionals in
> the accumulation of the result.

I guess this was done for performance reasons? Have you measured and 
seen any gains with this? The generated code becomes significantly 
larger when using the or/xor combination in your patch.

>
> - Removed unused BitMap::set_intersection_at_offset, rather than
> writing tests for it.
>
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8155043
>
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8155043/webrev.00/

Some minor comments/suggestions that you might want to consider:

==========
http://cr.openjdk.java.net/~kbarrett/8155043/webrev.00/src/share/vm/utilities/bitMap.cpp.frames.html

There are a few places where the tail calculations are slightly 
different compared to the calculations of the aligned part. Would it be 
good to use the same bitwise operations, just to get consistency between 
the two parts?

For example, in BitMap::contains we have

408 bm_word_t value = dest_map[index];
409 if (value != (value | other_map[index])) return false;

vs

414 return (rest == 0) || tail_of_set(~dest_map[limit] & 
other_map[limit], rest) == 0;

We could replace 408-409 with 'if (~dest_map[limit] & other_map[limit]) 
== 0) return false'.

----------
I find that the introduction of the 'bm_word_t orig' variable just makes 
the code extra noisy, and would have preferred the calculations without it.

----------

The new code has a few functions named *_of_set. The terminology "set" 
is previously not used in the BitMap file, so I'm a bit reluctant to 
introduce it. Could we get rid of it by renaming the functions:
   tail_of_set -> tail_of_map
   merge_tail_of_set -> merge_tail_of_map

or maybe:
   tail_of_set -> tail_bits
   merge_tail_of_set -> merge_tail_bits

==========
http://cr.openjdk.java.net/~kbarrett/8155043/webrev.00/test/native/utilities/test_bitMap_setops.cpp.html

The file tests more than the set operations, so maybe the _setops suffix 
should be dropped?

----------
Some of the tests restore the previous bitmap value after all checks, 
but some don't. It would probably be good to make that more consistent.

----------
class BitMapMemory {
...
private:
   idx_t _words;
   bm_word_t* _memory;
};

Most of the classes in the HotSpot have the members at the top of the class.

----------
static bm_word_t make_even_bits() {
   bm_word_t result = 1;
   while (true) {
     bm_word_t next = (result << 2) | 1;
     if (next == result) return result;
     result = next;
   }
}

I'd prefer if you moved down the return statement to a separate line and 
add braces.

----------

Thanks,
StefanK

>
> Testing:
> RBT runtime and gc nightly.
>