11
\$\begingroup\$

I'm currently attempting to learn some basic JVM optimization techniques using JMH.

I created the following bench to compare mid-index insertion performance between ArrayList and LinkedList.

How exactly do I measure score vs error in the final results?

The documentation states:

Your benchmarks should be peer-reviewed

I'm not quite sure how to validate the results, so I'm asking for a review of the following implementation to determine whether my workflow is correct. Any advice would be appreciated as I don't have much experience in performance evaluation techniques.

public class ListBench {

    static List<Integer> arrayList = new ArrayList<>();

    static List<Integer> linkedList = new LinkedList<>();

    private static int COUNT = 100;

    static {
        arrayList.add( 0 );
        linkedList.add( 0 );
    }

    @Benchmark
    @BenchmarkMode( Mode.Throughput )
    public static void arrayListBench() {

        for(int i = 0; i < COUNT; i++) {
            arrayList.add( mid( arrayList.size() ), i + 1 );
        }

    }

    @Benchmark
    @BenchmarkMode( Mode.Throughput )
    public static void linkedListBench() {

        for(int i = 0; i < COUNT; i++) {
            linkedList.add( mid( linkedList.size() ), i + 1 );
        }
    }

    public static int mid( int n ) {
        return n / 2;
    }

    public static void main( String[] args ) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include( ListBench.class.getSimpleName() )
            .warmupIterations( 10)
            .measurementIterations( 10 )
            .forks( 1 )
            .build();

        new Runner( opt ).run();
    }

}    

Init Params java -jar target/benchmarks.jar ListBench -wi 10 -i 10 -f 1

Results

# JMH 1.10-SNAPSHOT (released today)
# VM invoker: c:\Java\jdk_8\jre\bin\java.exe
# VM options: <none>
# Warmup: 10 iterations, 1 s each
# Measurement: 10 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: com.beckett.ListBench.arrayListBench

# Run progress: 0.00% complete, ETA 00:00:40
# Fork: 1 of 1
# Warmup Iteration   1: 1578.361 ops/s
# Warmup Iteration   2: 609.785 ops/s
# Warmup Iteration   3: 431.937 ops/s
# Warmup Iteration   4: 354.311 ops/s
# Warmup Iteration   5: 290.205 ops/s
# Warmup Iteration   6: 286.704 ops/s
# Warmup Iteration   7: 273.980 ops/s
# Warmup Iteration   8: 256.947 ops/s
# Warmup Iteration   9: 241.936 ops/s
# Warmup Iteration  10: 216.881 ops/s
Iteration   1: 218.604 ops/s
Iteration   2: 208.873 ops/s
Iteration   3: 200.316 ops/s
Iteration   4: 192.754 ops/s
Iteration   5: 167.496 ops/s
Iteration   6: 173.361 ops/s
Iteration   7: 167.943 ops/s
Iteration   8: 163.542 ops/s
Iteration   9: 158.993 ops/s
Iteration  10: 144.436 ops/s


Result "arrayListBench":
  179.632 ±(99.9%) 36.413 ops/s [Average]
  (min, avg, max) = (144.436, 179.632, 218.604), stdev = 24.085
  CI (99.9%): [143.219, 216.044] (assumes normal distribution)


# JMH 1.10-SNAPSHOT (released today)
# VM invoker: c:\Java\jdk_8\jre\bin\java.exe
# VM options: <none>
# Warmup: 10 iterations, 1 s each
# Measurement: 10 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: com.beckett.ListBench.linkedListBench

# Run progress: 50.00% complete, ETA 00:00:20
# Fork: 1 of 1
# Warmup Iteration   1: 446.279 ops/s
# Warmup Iteration   2: 183.674 ops/s
# Warmup Iteration   3: 140.986 ops/s
# Warmup Iteration   4: 118.704 ops/s
# Warmup Iteration   5: 100.247 ops/s
# Warmup Iteration   6: 94.524 ops/s
# Warmup Iteration   7: 86.703 ops/s
# Warmup Iteration   8: 80.523 ops/s
# Warmup Iteration   9: 75.306 ops/s
# Warmup Iteration  10: 68.613 ops/s
Iteration   1: 67.402 ops/s
Iteration   2: 64.286 ops/s
Iteration   3: 61.578 ops/s
Iteration   4: 58.948 ops/s
Iteration   5: 54.654 ops/s
Iteration   6: 55.136 ops/s
Iteration   7: 53.127 ops/s
Iteration   8: 51.460 ops/s
Iteration   9: 50.100 ops/s
Iteration  10: 46.219 ops/s


Result "linkedListBench":
  56.291 ±(99.9%) 10.073 ops/s [Average]
  (min, avg, max) = (46.219, 56.291, 67.402), stdev = 6.663
  CI (99.9%): [46.218, 66.364] (assumes normal distribution)


# Run complete. Total time: 00:00:40

Benchmark                   Mode  Cnt    Score    Error  Units
ListBench.arrayListBench   thrpt   10  179.632 ± 36.413  ops/s
ListBench.linkedListBench  thrpt   10   56.291 ± 10.073  ops/s
\$\endgroup\$
7
\$\begingroup\$

Important things:

  1. Have you read JMH Samples?

  2. Your benchmark does not have steady state. You can actually see that with diminishing performance iteration-to-iteration, and a large score error at the end. Measuring non-steady state benchmarks is a tricky business.

  3. Looping in benchmarks is generally discouraged, because loop unrolling optimizations, and subsequent code transformations may affect the benchmarks in unpredictable ways. See JMHSample_11_Loops and JMHSample_34_SafeLooping.

  4. Single fork is almost never enough. Run-to-run variance is a very frequent contender in performance results.

  5. The last, but not the least, you have to analyze benchmarks, not just running them. Use profilers to understand what is going on, wriggle experimental setup to see if it reacts to changes similar to your mental model, etc.

Stylistic things (or, things that make JMH tests more idiomatic, and therefore quickly understandable):

  1. static-s are not handy for storing states, especially if the next thing you try is testing with multiple threads. Use @Setup methods instead. See JMHSample_05_StateFixtures.

  2. static constants are bad substitutes for @Param. See JMHSample_27_Params.

  3. You don't need main() method to run benchmarks. In fact, running with uberjar is more reliable, as every sample links the caveats from JMH page:

    Running benchmarks from the IDE is generally not recommended due to generally uncontrolled environment in which the benchmarks run.

  4. You don't also need to build JMH to make benchmark runs (I see you are using 1.10-SNAPSHOT). All recent artifacts are available from Maven Central, and JMH page has a one-liner to generate the benchmark project from the archetype.

\$\endgroup\$
  • \$\begingroup\$ Thanks Aleksey ~ I developed my implementation after a cursory review of the JMH Samples and came to a similar conclusion as you stated in item 3... However, I'm still a bit uncertain how to refactor my bench to work correctly for this use case.... I'll spend more time going through the samples. \$\endgroup\$ – Eddie B May 20 '15 at 3:30
5
\$\begingroup\$

By using both to be measured classes

static List<Integer> arrayList = new ArrayList<>();

static List<Integer> linkedList = new LinkedList<>();

you're preventing Class Hierarchy Analysis (CHA). If the JVM could determine that there's just a single implementation of List, it could devirtualize all calls to List methods(*). As both ArrayList and LinkedList are used a lot, you're safe to ignore this problem, but with other classes it's very important. So you should rewrite the initialization to instantiate only the relevant class. As a bonus, you'd need a single @Benchmark only.


Benchmark                   Mode  Cnt    Score    Error  Units
ListBench.arrayListBench   thrpt   10  179.632 ± 36.413  ops/s
ListBench.linkedListBench  thrpt   10   56.291 ± 10.073  ops/s

The score 56±10 has a nearly 20% error, which is a lot. No idea what could be done to improve it (except for increasing the number of iterations which helps a bit, but costs a lot of time).

However, the results are sufficiently clear: LinkedList is the loser as it should be(**). Because of 56+10 being (much) less than 180-36 and because of the high confidence level 99.9% you can be pretty sure.

(*) If later another implementation gets loaded, all methods using CHA have to be deoptimized (and recompiled again). But all class loading happens at safepoints, so there's no runtime cost for this check.

(**) Joshua Bloch admitted that it was a mistake to include it in the JVM 20 years ago. With deeper memory hierarchies, it's becoming more and more unusable.

\$\endgroup\$
  • \$\begingroup\$ Can you provide a reference to the Joshua Bloch comment? (I believe it, but I think it is a good idea to add a secondary reference.) \$\endgroup\$ – kevinarpe Aug 22 '16 at 10:07
  • 1
    \$\begingroup\$ @kevinarpe I could find just a tweet saying "Does anyone actually use LinkedList? I wrote it, and I never use it.". \$\endgroup\$ – maaartinus Aug 22 '16 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.