RFR: 6735527: Bitmap - speed up searches

[Thomas Schatzl]

Hi,

On Fri, 2018-10-26 at 20:18 -0400, Kim Barrett wrote:
> Please review this improvement to the performance of BitMap searches.
> 
> The functions BitMap::get_next_one_offset and friends now use
> count_trailing_zeros to find the position of a 1 bit in a word,
> rather
> than using a loop.
> 
> That set of functions is also now implemented using a parameterized
> helper, eliminating a bunch of code (near) duplication.
> 
> There is a new gtest-based "microbenchmark" included in the change:
> test_bitMap_search_perf.cpp. It fills a 64KB bitmap to some specified
> "density", and then counts the bits in the bitmap by iteration over
> get_next_one_offset.  Repeat for various densities.
> 
> With the webrev is an OpenDocument spreadsheet comparing running the
> microbenchmark before and after the change.  Comparisons were made on
> a Xeon E5-2630 @ 2.6GHz running Ubuntu 16.04, code compiled with
> gcc7.3.0.  It shows that across the entire range of densities the new
> code is no worse than the old, and for some ranges is significantly
> better.  It's nice that the ranges with improvements are likely
> relevant to GC.
> 
> Question for reviewers: Should the microbenchmark be checked in?  It
> doesn't really test anything, just executes some code and prints some
> timing information.
> 
> CR:
> https://bugs.openjdk.java.net/browse/JDK-6735527
> 
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/6735527/open.00/
> http://cr.openjdk.java.net/~kbarrett/6735527/comparison.ods

  the change looks good to me.

The microbenchmark unfortunately does not seem to not fit anywhere in
the rest of the repo at this time. Maybe somebody else has an idea
where to put it.

Thanks,
  Thomas