How to benchmark '&' vs '%' cost correctly, using JMH

Question

So here is the simple thing I am trying to test, what is faster a mod operation or a AND one (assuming power of two) - this is what hashMap does internally. Is this a correctly spelled "test"? I have to admit that the internals of jmh and getting to write a correct micro benchmark after going through all the samples (for the 3-rd time I think) is quite a challenge. :)

   @State(Scope.Thread)
@BenchmarkMode(org.openjdk.jmh.annotations.Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MeasureSpeedModuleVsAnd {

    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
                .include(MeasureSpeedModuleVsAnd.class.getSimpleName())
                .forks(1)
                .warmupIterations(1)
                .measurementIterations(5)
                .warmupTime(TimeValue.seconds(2))
                .build();

        new Runner(opt).run();

    }

    @Param({ "16", "32", "256", "1048576" /* 2 power of 10 */ })
    public int number_of_buckets;

    @Param({ "345984", "123456", "111", "98653" })
    public int hashcode;

    @Benchmark
    public int benchamark_modulo() {
        return hashcode % number_of_buckets;
    }

    @Benchmark
    public int benchmark_and() {
        return (number_of_buckets - 1) & hashcode;
    }
}

Answer 1

This is covered in detail in this blog post: http://psy-lob-saw.blogspot.co.za/2014/11/the-mythical-modulo-mask.html

Your benchmark is broken (comparing what seems like irrelevant quantities) because you are comparing (non_final_field & constant) with (constant % non_final_field). Replace with (non_final_field1 % non_final_field2) and (non_final_field1 & (non_final_field2-1)) where non_final_field2 is a power of 2.

In the context of HashMap the value is used to read from an array and the blog post covers the implications of that side as well.