RFR: 6735527: Bitmap - speed up searches

Kim Barrett kim.barrett at oracle.com
Sat Oct 27 00:18:23 UTC 2018


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

Testing:
mach5 tier1-5
New gtest-based "microbenchmark".



More information about the hotspot-dev mailing list