Don’t Fear the Builder

Writing a nontrivial piece of code requires a programmer to make countless tiny decisions, and to produce good quality code quickly, many of these decisions must be made subconciously. But what happens if your instinct is mostly superstitious bullshit? I instinctively avoid allocating objects when I don’t have to, so would not voluntarily resort to using things like EqualsBuilder or HashCodeBuilder from Apache Commons. I feel dismayed whenever I am asked about the relationship between hash code and equals in interviews for contracts. This indicates a lack of mutual respect, but what’s revealing is that enough people passing themselves off as developers don’t know this stuff that it makes the question worth asking. EqualsBuilder and HashCodeBuilder make it so you don’t actually need to know, making it safe to put any object in a HashSet, whoever wrote the class. But should you use these classes just because they protect the naive (and you from the naive)? Is it a runtime tax? Or is any perceived cost magically eradicated by the JVM? It’s time to benchmark my instinct.

Baseline

There are definitely no allocations in the code IntelliJ (or similar) would generate for equals and hashCode automatically. I will use this generated code as the baseline: if I can match or beat this code with EqualsBuilder or HashCodeBuilder respectively, I can dismiss my prejudice. Here’s the baseline class:


public class Baseline {
    
    private final String a;
    private final int b;
    private final String c;
    private final Instant d;

    public Baseline(String a, int b, String c, Instant d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Baseline baseline = (Baseline) o;

        if (b != baseline.b) return false;
        if (!a.equals(baseline.a)) return false;
        if (!c.equals(baseline.c)) return false;
        return d.equals(baseline.d);
    }

    @Override
    public int hashCode() {
        int result = a.hashCode();
        result = 31 * result + b;
        result = 31 * result + c.hashCode();
        result = 31 * result + d.hashCode();
        return result;
    }
}

It’s not pretty and it’s a real pain to keep generated code up to date when adding and removing fields (you can delete it and regenerate it but it creates merge noise) but there’s no obvious way to improve on this code. It’s correct and looks fast. To benchmark alternatives, I want to look at the effect on set membership queries against a HashSet of various sizes.

Builder Implementation

I will contrast this with the following code using code from Apache Commons (incidentally, also generated by IntelliJ):


public class Builder {

    private final String a;
    private final int b;
    private final String c;
    private final Instant d;

    public Builder(String a, int b, String c, Instant d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        Builder builder = (Builder) o;

        return new EqualsBuilder()
                .append(b, builder.b)
                .append(a, builder.a)
                .append(c, builder.c)
                .append(d, builder.d)
                .isEquals();
    }

    @Override
    public int hashCode() {
        return new HashCodeBuilder(17, 37)
                .append(a)
                .append(b)
                .append(c)
                .append(d)
                .toHashCode();
    }
}

This code is a bit neater and easier to maintain, but does it have an observable cost?

HashSet Benchmark

For a parametrised range of HashSet sizes, I measure throughput for calls to contains. This requires that both hashCode and equals are called, the latter potentially several times. There is bias in this benchmark, because the implementation producing the best hash function will minimise the calls to equals, but I am willing to reward the better implementation rather than maniacally isolate any attributable allocation cost.

The code is simple, if a little repetitive. For each implementation, I make some random instances of my class, and make one that I can be sure isn’t in the set. I measure the cost of repeated invocations to the hashCode and equals methods by finding an object, and searching but failing to find an object separately.


@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class HashSetContainsBenchmark {

    @Param({"8", "96", "1024", "8192"})
    int setSize;

    private HashSet<Baseline> baselineSet;
    private Baseline presentBaseline;
    private Baseline missingBaseline;

    private HashSet<Builder> builderSet;
    private Builder presentBuilder;
    private Builder missingBuilder;

    @Setup(Level.Trial)
    public void setup() {
        setupBaselineState();
        setupBuilderState();
    }

    private void setupBaselineState() {
        baselineSet = new HashSet<>();
        for (int i = 0; i < setSize; ++i) {
            while(!baselineSet.add(newBaselineInstance()));
        }
        presentBaseline = baselineSet.iterator().next();
        do {
            missingBaseline = newBaselineInstance();
        } while (baselineSet.contains(missingBaseline));
    }

    private void setupBuilderState() {
        builderSet = new HashSet<>();
        for (int i = 0; i < setSize; ++i) {
            while(!builderSet.add(newBuilderInstance()));
        }
        presentBuilder = builderSet.iterator().next();
        do {
            missingBuilder = newBuilderInstance();
        } while (builderSet.contains(missingBuilder));
    }

    @Benchmark
    public boolean findPresentBaselineInstance() {
        return baselineSet.contains(presentBaseline);
    }

    @Benchmark
    public boolean findMissingBaselineInstance() {
        return baselineSet.contains(missingBaseline);
    }

    @Benchmark
    public boolean findPresentBuilderInstance() {
        return builderSet.contains(presentBuilder);
    }

    @Benchmark
    public boolean findMissingBuilderInstance() {
        return builderSet.contains(missingBuilder);
    }

    private static Baseline newBaselineInstance() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        return new Baseline(UUID.randomUUID().toString(),
                random.nextInt(),
                UUID.randomUUID().toString(),
                Instant.ofEpochMilli(random.nextLong(0, Instant.now().toEpochMilli())));
    }

    private static Builder newBuilderInstance() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        return new Builder(UUID.randomUUID().toString(),
                random.nextInt(),
                UUID.randomUUID().toString(),
                Instant.ofEpochMilli(random.nextLong(0, Instant.now().toEpochMilli())));
    }
}

Running this benchmark with org.apache.commons:commons-lang3:3.7 yields the throughput results below. There is an occasional and slight throughput degradation with the builders, but the builder implementation is sometimes faster in this benchmark, but the difference isn’t large enough to worry about.

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: setSize
findMissingBaselineInstance thrpt 1 10 153.878772 7.993036 ops/us 8
findMissingBaselineInstance thrpt 1 10 135.835085 6.031588 ops/us 96
findMissingBaselineInstance thrpt 1 10 137.716073 25.731562 ops/us 1024
findMissingBaselineInstance thrpt 1 10 123.896741 15.484023 ops/us 8192
findMissingBuilderInstance thrpt 1 10 142.051528 4.177352 ops/us 8
findMissingBuilderInstance thrpt 1 10 132.326909 1.017351 ops/us 96
findMissingBuilderInstance thrpt 1 10 127.220440 8.680761 ops/us 1024
findMissingBuilderInstance thrpt 1 10 140.029701 6.272960 ops/us 8192
findPresentBaselineInstance thrpt 1 10 139.714236 1.626873 ops/us 8
findPresentBaselineInstance thrpt 1 10 140.244864 1.777298 ops/us 96
findPresentBaselineInstance thrpt 1 10 135.273760 7.587937 ops/us 1024
findPresentBaselineInstance thrpt 1 10 133.158555 5.101069 ops/us 8192
findPresentBuilderInstance thrpt 1 10 111.196443 18.804103 ops/us 8
findPresentBuilderInstance thrpt 1 10 124.008441 5.182294 ops/us 96
findPresentBuilderInstance thrpt 1 10 126.729750 4.286002 ops/us 1024
findPresentBuilderInstance thrpt 1 10 124.159285 5.287920 ops/us 8192

Where did the builder go?

It’s worth taking a look at the compiler output to find out what happened. Considering the case where the object isn’t found in the set, we can see that the code gets inlined, and the hash code must be quite good. By enabling the args -XX:+PrintCompilation -XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining it’s clear to see that the entire hash code generation gets inlined into the calling loop, and that equals is never executed (suggesting that there are no collisions to resolve here) .

                              @ 8   java.util.HashSet::contains (9 bytes)   inline (hot)
                                @ 5   java.util.HashMap::containsKey (18 bytes)   inline (hot)
                                 \-> TypeProfile (17571/17571 counts) = java/util/HashMap
                                  @ 2   java.util.HashMap::hash (20 bytes)   inline (hot)
                                    @ 9   com.openkappa.simd.builder.Builder::hashCode (43 bytes)   inline (hot)
                                      @ 8   org.apache.commons.lang3.builder.HashCodeBuilder::<init> (60 bytes)   inline (hot)
                                        @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
                                        @ 26   org.apache.commons.lang3.Validate::isTrue (18 bytes)   unloaded signature classes
                                        @ 46   org.apache.commons.lang3.Validate::isTrue (18 bytes)   unloaded signature classes
                                      @ 15   org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes)   inline (hot)
                                        @ 21   java.lang.Object::getClass (0 bytes)   (intrinsic)
                                        @ 24   java.lang.Class::isArray (0 bytes)   (intrinsic)
                                        @ 49   java.lang.String::hashCode (49 bytes)   inline (hot)
                                          @ 19   java.lang.String::isLatin1 (19 bytes)   inline (hot)
                                          @ 29   java.lang.StringLatin1::hashCode (42 bytes)   inline (hot)
                                      @ 22   org.apache.commons.lang3.builder.HashCodeBuilder::append (17 bytes)   inline (hot)
                                      @ 29   org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes)   inline (hot)
                                        @ 21   java.lang.Object::getClass (0 bytes)   (intrinsic)
                                        @ 24   java.lang.Class::isArray (0 bytes)   (intrinsic)
                                        @ 49   java.lang.String::hashCode (49 bytes)   inline (hot)
                                          @ 19   java.lang.String::isLatin1 (19 bytes)   inline (hot)
                                          @ 29   java.lang.StringLatin1::hashCode (42 bytes)   inline (hot)
                                      @ 36   org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes)   inline (hot)
                                        @ 21   java.lang.Object::getClass (0 bytes)   (intrinsic)
                                        @ 24   java.lang.Class::isArray (0 bytes)   (intrinsic)
                                        @ 49   java.time.Instant::hashCode (22 bytes)   inline (hot)
                                      @ 39   org.apache.commons.lang3.builder.HashCodeBuilder::toHashCode (5 bytes)   accessor
                                  @ 6   java.util.HashMap::getNode (148 bytes)   inline (hot)
                                    @ 59   com.openkappa.simd.builder.Builder::equals (84 bytes)   never executed
                                    @ 126   com.openkappa.simd.builder.Builder::equals (84 bytes)   never executed

So the code is clearly small enough to get inlined. But what about the builder itself, isn’t it allocated? Not if it doesn’t escape. On a debug JVM, it’s possible to observe the removal of the builder’s allocation the JVM args -XX:+PrintEscapeAnalysis -XX:+PrintEliminateAllocations. However, on a production JVM, it can be observed indirectly by measuring the difference when escape analysis is disabled with -XX:-DoEscapeAnalysis.

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: setSize
findMissingBaselineInstance thrpt 1 10 150.972758 5.095163 ops/us 8
findMissingBaselineInstance thrpt 1 10 140.236057 2.222751 ops/us 96
findMissingBaselineInstance thrpt 1 10 132.680494 5.225503 ops/us 1024
findMissingBaselineInstance thrpt 1 10 115.220385 4.232488 ops/us 8192
findMissingBuilderInstance thrpt 1 10 68.869355 4.479944 ops/us 8
findMissingBuilderInstance thrpt 1 10 67.786351 5.980353 ops/us 96
findMissingBuilderInstance thrpt 1 10 71.113062 3.057181 ops/us 1024
findMissingBuilderInstance thrpt 1 10 75.088839 1.592294 ops/us 8192
findPresentBaselineInstance thrpt 1 10 141.425675 2.630898 ops/us 8
findPresentBaselineInstance thrpt 1 10 142.636359 2.854795 ops/us 96
findPresentBaselineInstance thrpt 1 10 143.939199 0.475918 ops/us 1024
findPresentBaselineInstance thrpt 1 10 142.006635 3.098352 ops/us 8192
findPresentBuilderInstance thrpt 1 10 71.546971 6.152584 ops/us 8
findPresentBuilderInstance thrpt 1 10 62.451705 11.896730 ops/us 96
findPresentBuilderInstance thrpt 1 10 68.903442 3.263955 ops/us 1024
findPresentBuilderInstance thrpt 1 10 69.576038 4.047581 ops/us 8192

Without escape analysis, the baseline code hardly slows down, whereas the change in the builder benchmarks is stark. The difference of differences here isolates the cost of allocating the HashCodeBuilder on the heap, and this is the kind of difference that can be expected from value types coming from Project Valhalla. Escape analysis is enabled by default, and the key point here is that even if the code looks like it might be slower, it might be as good or better – it depends what the JIT does with it.

Eliminating Bounds Checks with Intrinsics in Java 9

Open source projects are starting to capitalise on fast new intrinsics available in Java 9. For instance, Lucene is already experimenting with Arrays.mismatch, which I wrote about a few months ago, and Objects.checkIndex, which I didn’t know existed. A quick google search returned nothing on this method except the javadoc and a Baeldung blog post, which reiterates the javadoc. The intent behind these methods is obvious, and their signatures are simple enough to use blind, but why bother? What do you get, and when do you get it? This post analyses the range and index check methods to illustrate why it would be worthwhile for a project like Lucene, known for its performance, potentially supporting two versions of the same code. Edit: Robert Muir from Lucene points out in the comments here that his primary motivation for using these methods is actually consistency and correctness, rather than performance.

Objects.checkIndex, Arrays, and RangeCheckElimination

Suppose you have a double[] and want to perform a summation on the prefix of the array, expressed by a method parameter. You need to check that the parameter actually specifies a prefix of the array, but there also need to be bounds checks accessing the array. You might write code like this:


    @Benchmark
    public double RangePrefixSum_ManualCheck(BoundsCheckState state) {
        double[] data = state.data;
        int limit = state.index;
        if (limit < 0 || limit >= data.length) {
            throw new ArrayIndexOutOfBoundsException(limit + " >= " + data.length);
        }
        double result = 0D;
        for (int i = 0; i <= limit; ++i) {
            result += data[i];
        }
        return result;
    }

Or you could use Objects.checkIndex which takes an index and a length and will throw an ArrayIndexOutOfBoundsException if the index is not less than the length. The idea behind using it is that the JIT compiler can fuse this bounds check with any checks after the call, resulting in their elimination. You can see that this intrinsic functions as a “hint” rather than a handle to an assembly snippet in the source code. Using the new API you could write:


    @Benchmark
    public double PrefixRangeSum_CheckIndex(BoundsCheckState state) {
        double[] data = state.data;
        int limit = Objects.checkIndex(state.index, data.length);
        double result = 0D;
        for (int i = 0; i <= limit; ++i) {
            result += data[i];
        }
        return result;
    }

But does it make any difference? Or will both loops profit from RangeCheckElimination anyway, rendering any difference moot? As a point of comparison, I benchmark against the same code without any kind of precondition check so we can isolate the cost of performing the actual check.


    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public double RangePrefixSum_NoCheck(BoundsCheckState state) {
        double[] data = state.data;
        int limit = state.index;
        double result = 0D;
        for (int i = 0; i <= limit; ++i) {
            result += data[i];
        }
        return result;
    }

Running the benchmark, it turns out there is virtually no difference for shorter arrays, but there may be a small benefit when the arrays get longer. The assembly emitted is identical for each loop in any case. In short, bounds checks are probably being optimised away anyway; it is RangeCheckElimination, not Objects.checkIndex, taking effect here.

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
PrefixRangeSum_CheckIndex thrpt 1 10 8040.641837 371.264782 ops/ms 100
PrefixRangeSum_CheckIndex thrpt 1 10 716.093965 35.701464 ops/ms 1000
PrefixRangeSum_CheckIndex thrpt 1 10 73.321275 2.693158 ops/ms 10000
RangePrefixSum_ManualCheck thrpt 1 10 10433.584914 429.149725 ops/ms 100
RangePrefixSum_ManualCheck thrpt 1 10 676.266935 43.792141 ops/ms 1000
RangePrefixSum_ManualCheck thrpt 1 10 69.937342 5.215848 ops/ms 10000
RangePrefixSum_NoCheck thrpt 1 10 8754.536246 548.945401 ops/ms 100
RangePrefixSum_NoCheck thrpt 1 10 687.851103 37.487361 ops/ms 1000
RangePrefixSum_NoCheck thrpt 1 10 69.145729 2.783780 ops/ms 10000

For reference, here is the assembly used by the “naive” code:

com/openkappa/simd/boundscheck/CheckIndex.RangePrefixSum_ManualCheck(Lcom/openkappa/simd/boundscheck/BoundsCheckState;)D  [0x00000293bb8abe20, 0x00000293bb8abf38]  280 bytes
Argument 0 is unknown.RIP: 0x293bb8abe20 Code size: 0x00000118
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000293d0b32228} 'RangePrefixSum_ManualCheck' '(Lcom/openkappa/simd/boundscheck/BoundsCheckState;)D' in 'com/openkappa/simd/boundscheck/CheckIndex'
  0x00000293bb8abe20: int3                      ;...cc

  0x00000293bb8abe21: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x00000293bb8abe2c: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

  0x00000293bb8abe30: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x00000293bb8abe37: push    rbp               ;...55

  0x00000293bb8abe38: sub     rsp,50h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...50

  0x00000293bb8abe3c: mov     r14,qword ptr [rdx+20h]  ;...4c
                                                ;...8b
                                                ;...72
                                                ;...20

  0x00000293bb8abe40: mov     ebx,dword ptr [rdx+18h]  ;...8b
                                                ;...5a
                                                ;...18

  0x00000293bb8abe43: mov     r13d,dword ptr [rdx]  ;...44
                                                ;...8b
                                                ;...2a

  0x00000293bb8abe46: vmovsd  xmm0,qword ptr [rdx+8h]  ;...c5
                                                ;...fb
                                                ;...10
                                                ;...42
                                                ;...08

  0x00000293bb8abe4b: vmovq   rbp,xmm0          ;...c4
                                                ;...e1
                                                ;...f9
                                                ;...7e
                                                ;...c5

  0x00000293bb8abe50: mov     rcx,rdx           ;...48
                                                ;...8b
                                                ;...ca

  0x00000293bb8abe53: mov     r10,5b517c90h     ;...49
                                                ;...ba
                                                ;...90
                                                ;...7c
                                                ;...51
                                                ;...5b
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x00000293bb8abe5d: call indirect r10         ;...41
                                                ;...ff
                                                ;...d2

  0x00000293bb8abe60: test    r14,r14           ;...4d
                                                ;...85
                                                ;...f6

  0x00000293bb8abe63: je      293bb8abecdh      ;...74
                                                ;...68

  0x00000293bb8abe65: mov     r11d,dword ptr [r14+8h]  ;...45
                                                ;...8b
                                                ;...5e
                                                ;...08

  0x00000293bb8abe69: cmp     r11d,0f80000b9h   ;...41
                                                ;...81
                                                ;...fb
                                                ;...b9
                                                ;...00
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array double})}
  0x00000293bb8abe70: jne     293bb8abef1h      ;...0f
                                                ;...85
                                                ;...7b
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@42 (line 22)

  0x00000293bb8abe76: cmp     r13d,ebx          ;...44
                                                ;...3b
                                                ;...eb

  0x00000293bb8abe79: jnle    293bb8abec6h      ;...7f
                                                ;...4b
                                                ;*if_icmpgt {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@45 (line 22)

  0x00000293bb8abe7b: mov     r11d,dword ptr [r14+0ch]
                                                ;...45
                                                ;...8b
                                                ;...5e
                                                ;...0c
                                                ;*daload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@53 (line 23)
                                                ; implicit exception: dispatches to 0x00000293bb8abf0d
  0x00000293bb8abe7f: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x00000293bb8abe82: jnb     293bb8abed7h      ;...73
                                                ;...53

  0x00000293bb8abe84: vmovq   xmm0,rbp          ;...c4
                                                ;...e1
                                                ;...f9
                                                ;...6e
                                                ;...c5

  0x00000293bb8abe89: vaddsd  xmm0,xmm0,mmword ptr [r14+r13*8+10h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...ee
                                                ;...10
                                                ;*dadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@54 (line 23)

  0x00000293bb8abe90: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@57 (line 22)

  0x00000293bb8abe93: cmp     r13d,ebx          ;...44
                                                ;...3b
                                                ;...eb

  0x00000293bb8abe96: jnle    293bb8abebah      ;...7f
                                                ;...22
                                                ;*if_icmpgt {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@45 (line 22)

  0x00000293bb8abe98: nop     dword ptr [rax+rax+0h]  ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*daload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@53 (line 23)

  0x00000293bb8abea0: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x00000293bb8abea3: jnb     293bb8abed2h      ;...73
                                                ;...2d

  0x00000293bb8abea5: vaddsd  xmm0,xmm0,mmword ptr [r14+r13*8+10h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...ee
                                                ;...10
                                                ;*dadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@54 (line 23)

  0x00000293bb8abeac: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ; ImmutableOopMap{r14=Oop }
                                                ;*goto {reexecute=1 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@60 (line 22)

  0x00000293bb8abeaf: test    dword ptr [293a7e50000h],eax
                                                ;...85
                                                ;...05
                                                ;...4b
                                                ;...41
                                                ;...5a
                                                ;...ec
                                                ;*goto {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@60 (line 22)
                                                ;   {poll}
  0x00000293bb8abeb5: cmp     r13d,ebx          ;...44
                                                ;...3b
                                                ;...eb

  0x00000293bb8abeb8: jle     293bb8abea0h      ;...7e
                                                ;...e6
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::RangePrefixSum_ManualCheck@42 (line 22)

  0x00000293bb8abeba: add     rsp,50h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...50

  0x00000293bb8abebe: pop     rbp               ;...5d

  0x00000293bb8abebf: test    dword ptr [293a7e50000h],eax
                                                ;...85
                                                ;...05
                                                ;...3b
                                                ;...41
                                                ;...5a
                                                ;...ec
                                                ;   {poll_return}
  0x00000293bb8abec5: ret                       ;...c3

And using Objects.checkIndex we see essentially the same thing.

com/openkappa/simd/boundscheck/CheckIndex.PrefixRangeSum_CheckIndex(Lcom/openkappa/simd/boundscheck/BoundsCheckState;)D  [0x0000028c1a51d4a0, 0x0000028c1a51d5f8]  344 bytes
Argument 0 is unknown.RIP: 0x28c1a51d4a0 Code size: 0x00000158
[Entry Point]
[Constants]
  # {method} {0x0000028c2f7a1dd0} 'PrefixRangeSum_CheckIndex' '(Lcom/openkappa/simd/boundscheck/BoundsCheckState;)D' in 'com/openkappa/simd/boundscheck/CheckIndex'
  # this:     rdx:rdx   = 'com/openkappa/simd/boundscheck/CheckIndex'
  # parm0:    r8:r8     = 'com/openkappa/simd/boundscheck/BoundsCheckState'
  #           [sp+0x30]  (sp of caller)
  0x0000028c1a51d4a0: mov     r10d,dword ptr [rdx+8h]  ;...44
                                                ;...8b
                                                ;...52
                                                ;...08

  0x0000028c1a51d4a4: shl     r10,3h            ;...49
                                                ;...c1
                                                ;...e2
                                                ;...03

  0x0000028c1a51d4a8: cmp     rax,r10           ;...49
                                                ;...3b
                                                ;...c2

  0x0000028c1a51d4ab: jne     28c12a7c200h      ;...0f
                                                ;...85
                                                ;...4f
                                                ;...ed
                                                ;...55
                                                ;...f8
                                                ;   {runtime_call ic_miss_stub}
  0x0000028c1a51d4b1: nop                       ;...66
                                                ;...66
                                                ;...90

  0x0000028c1a51d4b4: nop     dword ptr [rax+rax+0h]  ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x0000028c1a51d4bc: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

[Verified Entry Point]
  0x0000028c1a51d4c0: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d4c7: push    rbp               ;...55

  0x0000028c1a51d4c8: sub     rsp,20h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...20
                                                ;*synchronization entry
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@-1 (line 43)

  0x0000028c1a51d4cc: mov     r10d,dword ptr [r8+14h]  ;...45
                                                ;...8b
                                                ;...50
                                                ;...14
                                                ;*getfield data {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@1 (line 43)
                                                ; implicit exception: dispatches to 0x0000028c1a51d5bd
  0x0000028c1a51d4d0: mov     r11d,dword ptr [r12+r10*8+0ch]
                                                ;...47
                                                ;...8b
                                                ;...5c
                                                ;...d4
                                                ;...0c
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@10 (line 44)
                                                ; implicit exception: dispatches to 0x0000028c1a51d5c9
  0x0000028c1a51d4d5: mov     ebp,dword ptr [r8+10h]  ;...41
                                                ;...8b
                                                ;...68
                                                ;...10
                                                ;*getfield index {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@6 (line 44)

  0x0000028c1a51d4d9: cmp     ebp,r11d          ;...41
                                                ;...3b
                                                ;...eb

  0x0000028c1a51d4dc: jnb     28c1a51d587h      ;...0f
                                                ;...83
                                                ;...a5
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*invokestatic checkIndex {reexecute=0 rethrow=0 return_oop=0}
                                                ; - java.util.Objects::checkIndex@3 (line 372)
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@11 (line 44)

  0x0000028c1a51d4e2: test    r11d,r11d         ;...45
                                                ;...85
                                                ;...db

  0x0000028c1a51d4e5: jbe     28c1a51d59dh      ;...0f
                                                ;...86
                                                ;...b2
                                                ;...00
                                                ;...00
                                                ;...00

  0x0000028c1a51d4eb: movsxd  r11,r11d          ;...4d
                                                ;...63
                                                ;...db

  0x0000028c1a51d4ee: mov     r8d,ebp           ;...44
                                                ;...8b
                                                ;...c5

  0x0000028c1a51d4f1: inc     r8d               ;...41
                                                ;...ff
                                                ;...c0

  0x0000028c1a51d4f4: movsxd  r9,r8d            ;...4d
                                                ;...63
                                                ;...c8

  0x0000028c1a51d4f7: dec     r9                ;...49
                                                ;...ff
                                                ;...c9

  0x0000028c1a51d4fa: cmp     r9,r11            ;...4d
                                                ;...3b
                                                ;...cb

  0x0000028c1a51d4fd: jnb     28c1a51d59dh      ;...0f
                                                ;...83
                                                ;...9a
                                                ;...00
                                                ;...00
                                                ;...00

  0x0000028c1a51d503: cmp     ebp,7ffffffeh     ;...81
                                                ;...fd
                                                ;...fe
                                                ;...ff
                                                ;...ff
                                                ;...7f

  0x0000028c1a51d509: jnle    28c1a51d5adh      ;...0f
                                                ;...8f
                                                ;...9e
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)

  0x0000028c1a51d50f: add     ebp,0fffffffeh    ;...83
                                                ;...c5
                                                ;...fe

  0x0000028c1a51d512: lea     r11,[r12+r10*8]   ;...4f
                                                ;...8d
                                                ;...1c
                                                ;...d4

  0x0000028c1a51d516: vxorpd  xmm0,xmm0,xmm0    ;...c5
                                                ;...f9
                                                ;...57
                                                ;...c0

  0x0000028c1a51d51a: vaddsd  xmm0,xmm0,mmword ptr [r12+r10*8+10h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...d4
                                                ;...10
                                                ;*dadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@33 (line 47)

  0x0000028c1a51d521: mov     r9d,80000000h     ;...41
                                                ;...b9
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...80

  0x0000028c1a51d527: cmp     r8d,ebp           ;...44
                                                ;...3b
                                                ;...c5

  0x0000028c1a51d52a: cmovl   ebp,r9d           ;...41
                                                ;...0f
                                                ;...4c
                                                ;...e9

  0x0000028c1a51d52e: mov     r9d,1h            ;...41
                                                ;...b9
                                                ;...01
                                                ;...00
                                                ;...00
                                                ;...00

  0x0000028c1a51d534: cmp     ebp,1h            ;...83
                                                ;...fd
                                                ;...01

  0x0000028c1a51d537: jle     28c1a51d565h      ;...7e
                                                ;...2c

  0x0000028c1a51d539: nop     dword ptr [rax+0h]  ;...0f
                                                ;...1f
                                                ;...80
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)

  0x0000028c1a51d540: vaddsd  xmm0,xmm0,mmword ptr [r11+r9*8+10h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...cb
                                                ;...10

  0x0000028c1a51d547: vaddsd  xmm0,xmm0,mmword ptr [r11+r9*8+18h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...cb
                                                ;...18

  0x0000028c1a51d54e: vaddsd  xmm0,xmm0,mmword ptr [r11+r9*8+20h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...cb
                                                ;...20

  0x0000028c1a51d555: vaddsd  xmm0,xmm0,mmword ptr [r11+r9*8+28h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...cb
                                                ;...28
                                                ;*dadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@33 (line 47)

  0x0000028c1a51d55c: add     r9d,4h            ;...41
                                                ;...83
                                                ;...c1
                                                ;...04
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@36 (line 46)

  0x0000028c1a51d560: cmp     r9d,ebp           ;...44
                                                ;...3b
                                                ;...cd

  0x0000028c1a51d563: jl      28c1a51d540h      ;...7c
                                                ;...db
                                                ;*if_icmpgt {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@24 (line 46)

  0x0000028c1a51d565: cmp     r9d,r8d           ;...45
                                                ;...3b
                                                ;...c8

  0x0000028c1a51d568: jnl     28c1a51d57bh      ;...7d
                                                ;...11

  0x0000028c1a51d56a: nop                       ;...66
                                                ;...90
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)

  0x0000028c1a51d56c: vaddsd  xmm0,xmm0,mmword ptr [r11+r9*8+10h]
                                                ;...c4
                                                ;...81
                                                ;...7b
                                                ;...58
                                                ;...44
                                                ;...cb
                                                ;...10
                                                ;*dadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@33 (line 47)

  0x0000028c1a51d573: inc     r9d               ;...41
                                                ;...ff
                                                ;...c1
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@36 (line 46)

  0x0000028c1a51d576: cmp     r9d,r8d           ;...45
                                                ;...3b
                                                ;...c8

  0x0000028c1a51d579: jl      28c1a51d56ch      ;...7c
                                                ;...f1
                                                ;*if_icmpgt {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@24 (line 46)

  0x0000028c1a51d57b: add     rsp,20h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...20

  0x0000028c1a51d57f: pop     rbp               ;...5d

  0x0000028c1a51d580: test    dword ptr [28c08310000h],eax
                                                ;...85
                                                ;...05
                                                ;...7a
                                                ;...2a
                                                ;...df
                                                ;...ed
                                                ;   {poll_return}
  0x0000028c1a51d586: ret                       ;...c3

  0x0000028c1a51d587: mov     edx,0ffffffe4h    ;...ba
                                                ;...e4
                                                ;...ff
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d58c: mov     dword ptr [rsp],r10d  ;...44
                                                ;...89
                                                ;...14
                                                ;...24

  0x0000028c1a51d590: mov     dword ptr [rsp+4h],r11d  ;...44
                                                ;...89
                                                ;...5c
                                                ;...24
                                                ;...04

  0x0000028c1a51d595: nop                       ;...66
                                                ;...90

  0x0000028c1a51d597: call    28c12a7de80h      ;...e8
                                                ;...e4
                                                ;...08
                                                ;...56
                                                ;...f8
                                                ; ImmutableOopMap{[0]=NarrowOop }
                                                ;*invokestatic checkIndex {reexecute=0 rethrow=0 return_oop=0}
                                                ; - java.util.Objects::checkIndex@3 (line 372)
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@11 (line 44)
                                                ;   {runtime_call UncommonTrapBlob}
  0x0000028c1a51d59c: int3                      ;...cc
                                                ;*invokestatic checkIndex {reexecute=0 rethrow=0 return_oop=0}
                                                ; - java.util.Objects::checkIndex@3 (line 372)
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@11 (line 44)

  0x0000028c1a51d59d: mov     edx,0ffffff86h    ;...ba
                                                ;...86
                                                ;...ff
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d5a2: mov     dword ptr [rsp],r10d  ;...44
                                                ;...89
                                                ;...14
                                                ;...24

  0x0000028c1a51d5a6: nop                       ;...90

  0x0000028c1a51d5a7: call    28c12a7de80h      ;...e8
                                                ;...d4
                                                ;...08
                                                ;...56
                                                ;...f8
                                                ; ImmutableOopMap{[0]=NarrowOop }
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)
                                                ;   {runtime_call UncommonTrapBlob}
  0x0000028c1a51d5ac: int3                      ;...cc

  0x0000028c1a51d5ad: mov     edx,0ffffff7eh    ;...ba
                                                ;...7e
                                                ;...ff
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d5b2: mov     dword ptr [rsp],r10d  ;...44
                                                ;...89
                                                ;...14
                                                ;...24

  0x0000028c1a51d5b6: nop                       ;...90

  0x0000028c1a51d5b7: call    28c12a7de80h      ;...e8
                                                ;...c4
                                                ;...08
                                                ;...56
                                                ;...f8
                                                ; ImmutableOopMap{[0]=NarrowOop }
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)
                                                ;   {runtime_call UncommonTrapBlob}
  0x0000028c1a51d5bc: int3                      ;...cc
                                                ;*dload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@27 (line 47)

  0x0000028c1a51d5bd: mov     edx,0fffffff6h    ;...ba
                                                ;...f6
                                                ;...ff
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d5c2: nop                       ;...90

  0x0000028c1a51d5c3: call    28c12a7de80h      ;...e8
                                                ;...b8
                                                ;...08
                                                ;...56
                                                ;...f8
                                                ; ImmutableOopMap{}
                                                ;*getfield data {reexecute=1 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@1 (line 43)
                                                ;   {runtime_call UncommonTrapBlob}
  0x0000028c1a51d5c8: int3                      ;...cc
                                                ;*getfield data {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@1 (line 43)

  0x0000028c1a51d5c9: mov     edx,0fffffff6h    ;...ba
                                                ;...f6
                                                ;...ff
                                                ;...ff
                                                ;...ff

  0x0000028c1a51d5ce: nop                       ;...90

  0x0000028c1a51d5cf: call    28c12a7de80h      ;...e8
                                                ;...ac
                                                ;...08
                                                ;...56
                                                ;...f8
                                                ; ImmutableOopMap{}
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@10 (line 44)
                                                ;   {runtime_call UncommonTrapBlob}
  0x0000028c1a51d5d4: int3                      ;...cc
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.boundscheck.CheckIndex::PrefixRangeSum_CheckIndex@10 (line 44)

  0x0000028c1a51d5d5: hlt                       ;...f4

  0x0000028c1a51d5d6: hlt                       ;...f4

  0x0000028c1a51d5d7: hlt                       ;...f4

  0x0000028c1a51d5d8: hlt                       ;...f4

  0x0000028c1a51d5d9: hlt                       ;...f4

  0x0000028c1a51d5da: hlt                       ;...f4

  0x0000028c1a51d5db: hlt                       ;...f4

  0x0000028c1a51d5dc: hlt                       ;...f4

  0x0000028c1a51d5dd: hlt                       ;...f4

  0x0000028c1a51d5de: hlt                       ;...f4

  0x0000028c1a51d5df: hlt                       ;...f4

Point Access Range Check Elimination

If there’s no gain rolling up an array, because the optimisations applied to loops over arrays are so good, what if you need to provide random access to some kind of collection? You need to perform checks. We can put it to the test by comparing these two pieces of code:


    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public double PointAccess_ManualCheck(BoundsCheckState state) {
        double[] data = state.data;
        int index = state.index;
        if (index < 0 || index >= data.length) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + data.length);
        }
        return data[index];
    }

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public double PointAccess_CheckIndex(BoundsCheckState state) {
        double[] data = state.data;
        int index = Objects.checkIndex(state.index, data.length);
        return data[index];
    }

Again, disappointingly, there’s virtually no difference, and this time it’s in the naive approach’s favour.

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
PointAccess_CheckIndex thrpt 1 10 79259.682293 10737.451258 ops/ms 100
PointAccess_CheckIndex thrpt 1 10 59719.861827 15039.268226 ops/ms 1000
PointAccess_CheckIndex thrpt 1 10 25541.582169 18540.720843 ops/ms 10000
PointAccess_ManualCheck thrpt 1 10 81280.935102 7639.676934 ops/ms 100
PointAccess_ManualCheck thrpt 1 10 61888.048023 19194.480590 ops/ms 1000
PointAccess_ManualCheck thrpt 1 10 27379.437571 17218.454466 ops/ms 10000

The nice thing about not using the intrinsic is you can control the error message, and while I’m hesitant to make negative proclamations (perhaps my benchmark code is flawed), I am in no rush to use this method.

How much Algebra does C2 Know? Part 2: Distributivity

In part one of this series of posts, I looked at how important associativity and independence are for fast loops. C2 seems to utilise these properties to generate unrolled and pipelined machine code for loops, achieving higher throughput even in cases where the kernel of the loop is 3x slower according to vendor advertised instruction throughputs. C2 has a weird and wonderful relationship with distributivity, and hints from the programmer can both and help hinder the generation of good quality machine code.

Viability and Correctness

Distributivity is the simple notion of factoring out brackets. Is this, in general, a viable loop rewrite strategy? This can be utilised to transform the method Scale into FactoredScale, both of which perform floating point arithmetic:


    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public double Scale(DoubleData state) {
        double value = 0D;
        double[] data = state.data1;
        for (int i = 0; i < data.length; ++i) {
            value += 3.14159 * data[i];
        }
        return value;
    }

    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public double FactoredScale(DoubleData state) {
        double value = 0D;
        double[] data = state.data1;
        for (int i = 0; i < data.length; ++i) {
            value += data[i];
        }
        return 3.14159 * value;
    }

Running the project at github with the argument --include .*scale.*, there may be a performance gain to be had from this rewrite, but it isn’t clear cut:

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
FactoredScale thrpt 1 10 7.011606 0.274742 ops/ms 100000
FactoredScale thrpt 1 10 0.621515 0.026853 ops/ms 1000000
Scale thrpt 1 10 6.962434 0.240180 ops/ms 100000
Scale thrpt 1 10 0.671042 0.011686 ops/ms 1000000

With the real numbers it would be completely valid, but floating point arithmetic is not associative. Joseph Darcy explains why in this deep dive on floating point semantics. Broken associativity of addition entails broken distributivity of any operation over it, so the two loops are not equivalent, and they give different outputs (e.g. 15662.513298516365 vs 15662.51329851632 for one sample input). The rewrite isn’t correct even for floating point data, so it isn’t an optimisation that could be applied in good faith, except in a very small number of cases. You have to rewrite the loop yourself and figure out if the small but inevitable differences are acceptable.

Counterintuitive Performance

Integer multiplication is distributive over addition, and we can check if C2 does this rewrite by running the same code with 32 bit integer values, for now fixing a scale factor of 10 (which seems like an innocuous value, no?)


    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public int Scale_Int(IntData state) {
        int value = 0;
        int[] data = state.data1;
        for (int i = 0; i < data.length; ++i) {
            value += 10 * data[i];
        }
        return value;
    }

    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public int FactoredScale_Int(IntData state) {
        int value = 0;
        int[] data = state.data1;
        for (int i = 0; i < data.length; ++i) {
            value += data[i];
        }
        return 10 * value;
    }

The results are fascinating:

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
FactoredScale_Int thrpt 1 10 28.339699 0.608075 ops/ms 100000
FactoredScale_Int thrpt 1 10 2.392579 0.506413 ops/ms 1000000
Scale_Int thrpt 1 10 33.335721 0.295334 ops/ms 100000
Scale_Int thrpt 1 10 2.838242 0.448213 ops/ms 1000000

The code is doing thousands more multiplications in less time when the multiplication is not factored out of the loop. So what the devil is going on? Inspecting the assembly for the faster loop is revealing

com/openkappa/simd/scale/Scale.Scale_Int(Lcom/openkappa/simd/state/IntData;)I  [0x000001c89e499320, 0x000001c89e4996f8]  984 bytes
Argument 0 is unknown.RIP: 0x1c89e499320 Code size: 0x000003d8
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000001c8b3701b10} 'Scale_Int' '(Lcom/openkappa/simd/state/IntData;)I' in 'com/openkappa/simd/scale/Scale'
  0x000001c89e499320: int3                      ;...cc

  0x000001c89e499321: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e49932c: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

  0x000001c89e499330: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x000001c89e499337: push    rbp               ;...55

  0x000001c89e499338: sub     rsp,40h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...40

  0x000001c89e49933c: mov     rbp,qword ptr [rdx+8h]  ;...48
                                                ;...8b
                                                ;...6a
                                                ;...08

  0x000001c89e499340: mov     ebx,dword ptr [rdx+10h]  ;...8b
                                                ;...5a
                                                ;...10

  0x000001c89e499343: mov     r13d,dword ptr [rdx]  ;...44
                                                ;...8b
                                                ;...2a

  0x000001c89e499346: mov     rcx,rdx           ;...48
                                                ;...8b
                                                ;...ca

  0x000001c89e499349: vzeroupper                ;...c5
                                                ;...f8
                                                ;...77

  0x000001c89e49934c: mov     r10,51da8d20h     ;...49
                                                ;...ba
                                                ;...20
                                                ;...8d
                                                ;...da
                                                ;...51
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e499356: call indirect r10         ;...41
                                                ;...ff
                                                ;...d2

  0x000001c89e499359: mov     r11d,dword ptr [rbp+8h]  ;...44
                                                ;...8b
                                                ;...5d
                                                ;...08
                                                ; implicit exception: dispatches to 0x000001c89e4996c1
  0x000001c89e49935d: cmp     r11d,0f800016dh   ;...41
                                                ;...81
                                                ;...fb
                                                ;...6d
                                                ;...01
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array int})}
  0x000001c89e499364: jne     1c89e4996a9h      ;...0f
                                                ;...85
                                                ;...3f
                                                ;...03
                                                ;...00
                                                ;...00
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@10 (line 41)

  0x000001c89e49936a: mov     edi,dword ptr [rbp+0ch]  ;...8b
                                                ;...7d
                                                ;...0c
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@13 (line 41)

  0x000001c89e49936d: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e499370: jnl     1c89e49967ah      ;...0f
                                                ;...8d
                                                ;...04
                                                ;...03
                                                ;...00
                                                ;...00
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@14 (line 41)

  0x000001c89e499376: mov     r10d,ebp          ;...44
                                                ;...8b
                                                ;...d5

  0x000001c89e499379: mov     r8d,r13d          ;...45
                                                ;...8b
                                                ;...c5

  0x000001c89e49937c: inc     r8d               ;...41
                                                ;...ff
                                                ;...c0

  0x000001c89e49937f: shr     r10d,2h           ;...41
                                                ;...c1
                                                ;...ea
                                                ;...02

  0x000001c89e499383: and     r10d,7h           ;...41
                                                ;...83
                                                ;...e2
                                                ;...07

  0x000001c89e499387: xor     r9d,r9d           ;...45
                                                ;...33
                                                ;...c9

  0x000001c89e49938a: cmp     r8d,r9d           ;...45
                                                ;...3b
                                                ;...c1

  0x000001c89e49938d: cmovl   r8d,r9d           ;...45
                                                ;...0f
                                                ;...4c
                                                ;...c1

  0x000001c89e499391: cmp     r8d,edi           ;...44
                                                ;...3b
                                                ;...c7

  0x000001c89e499394: cmovnle r8d,edi           ;...44
                                                ;...0f
                                                ;...4f
                                                ;...c7

  0x000001c89e499398: add     r10d,r8d          ;...45
                                                ;...03
                                                ;...d0

  0x000001c89e49939b: mov     r11d,4h           ;...41
                                                ;...bb
                                                ;...04
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e4993a1: sub     r11d,r10d         ;...45
                                                ;...2b
                                                ;...da

  0x000001c89e4993a4: and     r11d,7h           ;...41
                                                ;...83
                                                ;...e3
                                                ;...07

  0x000001c89e4993a8: add     r11d,r8d          ;...45
                                                ;...03
                                                ;...d8

  0x000001c89e4993ab: cmp     r11d,edi          ;...44
                                                ;...3b
                                                ;...df

  0x000001c89e4993ae: cmovnle r11d,edi          ;...44
                                                ;...0f
                                                ;...4f
                                                ;...df

  0x000001c89e4993b2: nop                       ;...66
                                                ;...90

  0x000001c89e4993b4: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e4993b7: jnb     1c89e49968bh      ;...0f
                                                ;...83
                                                ;...ce
                                                ;...02
                                                ;...00
                                                ;...00

  0x000001c89e4993bd: mov     r10d,dword ptr [rbp+r13*4+10h]
                                                ;...46
                                                ;...8b
                                                ;...54
                                                ;...ad
                                                ;...10
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@23 (line 42)

  0x000001c89e4993c2: mov     r9d,r10d          ;...45
                                                ;...8b
                                                ;...ca

  0x000001c89e4993c5: shl     r9d,3h            ;...41
                                                ;...c1
                                                ;...e1
                                                ;...03

  0x000001c89e4993c9: shl     r10d,1h           ;...41
                                                ;...d1
                                                ;...e2

  0x000001c89e4993cc: add     r9d,r10d          ;...45
                                                ;...03
                                                ;...ca

  0x000001c89e4993cf: add     ebx,r9d           ;...41
                                                ;...03
                                                ;...d9
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@25 (line 42)

  0x000001c89e4993d2: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@27 (line 41)

  0x000001c89e4993d5: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x000001c89e4993d8: jl      1c89e4993b4h      ;...7c
                                                ;...da
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@14 (line 41)

  0x000001c89e4993da: mov     r8d,edi           ;...44
                                                ;...8b
                                                ;...c7

  0x000001c89e4993dd: add     r8d,0ffffffc1h    ;...41
                                                ;...83
                                                ;...c0
                                                ;...c1

  0x000001c89e4993e1: mov     ecx,80000000h     ;...b9
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...80

  0x000001c89e4993e6: cmp     edi,r8d           ;...41
                                                ;...3b
                                                ;...f8

  0x000001c89e4993e9: cmovl   r8d,ecx           ;...44
                                                ;...0f
                                                ;...4c
                                                ;...c1

  0x000001c89e4993ed: cmp     r13d,r8d          ;...45
                                                ;...3b
                                                ;...e8

  0x000001c89e4993f0: jnl     1c89e499651h      ;...0f
                                                ;...8d
                                                ;...5b
                                                ;...02
                                                ;...00
                                                ;...00

  0x000001c89e4993f6: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e499400: vmovdqu ymm8,ymmword ptr [rbp+r13*4+10h]
                                                ;...c4
                                                ;...21
                                                ;...7e
                                                ;...6f
                                                ;...44
                                                ;...ad
                                                ;...10

  0x000001c89e499407: movsxd  r10,r13d          ;...4d
                                                ;...63
                                                ;...d5

  0x000001c89e49940a: vmovdqu ymm9,ymmword ptr [rbp+r10*4+30h]
                                                ;...c4
                                                ;...21
                                                ;...7e
                                                ;...6f
                                                ;...4c
                                                ;...95
                                                ;...30

  0x000001c89e499411: vmovdqu ymm13,ymmword ptr [rbp+r10*4+0f0h]
                                                ;...c4
                                                ;...21
                                                ;...7e
                                                ;...6f
                                                ;...ac
                                                ;...95
                                                ;...f0
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e49941b: vmovdqu ymm12,ymmword ptr [rbp+r10*4+50h]
                                                ;...c4
                                                ;...21
                                                ;...7e
                                                ;...6f
                                                ;...64
                                                ;...95
                                                ;...50

  0x000001c89e499422: vmovdqu ymm4,ymmword ptr [rbp+r10*4+70h]
                                                ;...c4
                                                ;...a1
                                                ;...7e
                                                ;...6f
                                                ;...64
                                                ;...95
                                                ;...70

  0x000001c89e499429: vmovdqu ymm3,ymmword ptr [rbp+r10*4+90h]
                                                ;...c4
                                                ;...a1
                                                ;...7e
                                                ;...6f
                                                ;...9c
                                                ;...95
                                                ;...90
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e499433: vmovdqu ymm2,ymmword ptr [rbp+r10*4+0b0h]
                                                ;...c4
                                                ;...a1
                                                ;...7e
                                                ;...6f
                                                ;...94
                                                ;...95
                                                ;...b0
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c89e49943d: vmovdqu ymm0,ymmword ptr [rbp+r10*4+0d0h]
                                                ;...c4
                                                ;...a1
                                                ;...7e
                                                ;...6f
                                                ;...84
                                                ;...95
                                                ;...d0
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@23 (line 42)

  0x000001c89e499447: vpslld  ymm11,ymm8,1h     ;...c4
                                                ;...c1
                                                ;...25
                                                ;...72
                                                ;...f0
                                                ;...01

  0x000001c89e49944d: vpslld  ymm1,ymm0,1h      ;...c5
                                                ;...f5
                                                ;...72
                                                ;...f0
                                                ;...01

  0x000001c89e499452: vpslld  ymm0,ymm0,3h      ;...c5
                                                ;...fd
                                                ;...72
                                                ;...f0
                                                ;...03

  0x000001c89e499457: vpaddd  ymm5,ymm0,ymm1    ;...c5
                                                ;...fd
                                                ;...fe
                                                ;...e9

  0x000001c89e49945b: vpslld  ymm0,ymm2,3h      ;...c5
                                                ;...fd
                                                ;...72
                                                ;...f2
                                                ;...03

  0x000001c89e499460: vpslld  ymm7,ymm3,3h      ;...c5
                                                ;...c5
                                                ;...72
                                                ;...f3
                                                ;...03

  0x000001c89e499465: vpslld  ymm10,ymm4,3h     ;...c5
                                                ;...ad
                                                ;...72
                                                ;...f4
                                                ;...03

  0x000001c89e49946a: vpslld  ymm15,ymm12,3h    ;...c4
                                                ;...c1
                                                ;...05
                                                ;...72
                                                ;...f4
                                                ;...03

  0x000001c89e499470: vpslld  ymm14,ymm13,3h    ;...c4
                                                ;...c1
                                                ;...0d
                                                ;...72
                                                ;...f5
                                                ;...03

  0x000001c89e499476: vpslld  ymm1,ymm9,3h      ;...c4
                                                ;...c1
                                                ;...75
                                                ;...72
                                                ;...f1
                                                ;...03

  0x000001c89e49947c: vpslld  ymm2,ymm2,1h      ;...c5
                                                ;...ed
                                                ;...72
                                                ;...f2
                                                ;...01

  0x000001c89e499481: vpaddd  ymm6,ymm0,ymm2    ;...c5
                                                ;...fd
                                                ;...fe
                                                ;...f2

  0x000001c89e499485: vpslld  ymm0,ymm3,1h      ;...c5
                                                ;...fd
                                                ;...72
                                                ;...f3
                                                ;...01

  0x000001c89e49948a: vpaddd  ymm7,ymm7,ymm0    ;...c5
                                                ;...c5
                                                ;...fe
                                                ;...f8

  0x000001c89e49948e: vpslld  ymm0,ymm4,1h      ;...c5
                                                ;...fd
                                                ;...72
                                                ;...f4
                                                ;...01

  0x000001c89e499493: vpaddd  ymm10,ymm10,ymm0  ;...c5
                                                ;...2d
                                                ;...fe
                                                ;...d0

  0x000001c89e499497: vpslld  ymm0,ymm12,1h     ;...c4
                                                ;...c1
                                                ;...7d
                                                ;...72
                                                ;...f4
                                                ;...01

  0x000001c89e49949d: vpaddd  ymm12,ymm15,ymm0  ;...c5
                                                ;...05
                                                ;...fe
                                                ;...e0

  0x000001c89e4994a1: vpslld  ymm0,ymm13,1h     ;...c4
                                                ;...c1
                                                ;...7d
                                                ;...72
                                                ;...f5
                                                ;...01

  0x000001c89e4994a7: vpaddd  ymm4,ymm14,ymm0   ;...c5
                                                ;...8d
                                                ;...fe
                                                ;...e0

  0x000001c89e4994ab: vpslld  ymm0,ymm9,1h      ;...c4
                                                ;...c1
                                                ;...7d
                                                ;...72
                                                ;...f1
                                                ;...01

  0x000001c89e4994b1: vpaddd  ymm2,ymm1,ymm0    ;...c5
                                                ;...f5
                                                ;...fe
                                                ;...d0

  0x000001c89e4994b5: vpslld  ymm0,ymm8,3h      ;...c4
                                                ;...c1
                                                ;...7d
                                                ;...72
                                                ;...f0
                                                ;...03

  0x000001c89e4994bb: vpaddd  ymm8,ymm0,ymm11   ;...c4
                                                ;...41
                                                ;...7d
                                                ;...fe
                                                ;...c3

  0x000001c89e4994c0: vphaddd ymm0,ymm8,ymm8    ;...c4
                                                ;...c2
                                                ;...3d
                                                ;...02
                                                ;...c0

  0x000001c89e4994c5: vphaddd ymm0,ymm0,ymm3    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c3

  0x000001c89e4994ca: vextracti128 xmm3,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c3
                                                ;...01

  0x000001c89e4994d0: vpaddd  xmm0,xmm0,xmm3    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c3

  0x000001c89e4994d4: vmovd   xmm3,ebx          ;...c5
                                                ;...f9
                                                ;...6e
                                                ;...db

  0x000001c89e4994d8: vpaddd  xmm3,xmm3,xmm0    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d8

  0x000001c89e4994dc: vmovd   r10d,xmm3         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...da

  0x000001c89e4994e1: vphaddd ymm0,ymm2,ymm2    ;...c4
                                                ;...e2
                                                ;...6d
                                                ;...02
                                                ;...c2

  0x000001c89e4994e6: vphaddd ymm0,ymm0,ymm3    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c3

  0x000001c89e4994eb: vextracti128 xmm3,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c3
                                                ;...01

  0x000001c89e4994f1: vpaddd  xmm0,xmm0,xmm3    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c3

  0x000001c89e4994f5: vmovd   xmm3,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...da

  0x000001c89e4994fa: vpaddd  xmm3,xmm3,xmm0    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d8

  0x000001c89e4994fe: vmovd   r11d,xmm3         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...db

  0x000001c89e499503: vphaddd ymm2,ymm12,ymm12  ;...c4
                                                ;...c2
                                                ;...1d
                                                ;...02
                                                ;...d4

  0x000001c89e499508: vphaddd ymm2,ymm2,ymm0    ;...c4
                                                ;...e2
                                                ;...6d
                                                ;...02
                                                ;...d0

  0x000001c89e49950d: vextracti128 xmm0,ymm2,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d0
                                                ;...01

  0x000001c89e499513: vpaddd  xmm2,xmm2,xmm0    ;...c5
                                                ;...e9
                                                ;...fe
                                                ;...d0

  0x000001c89e499517: vmovd   xmm0,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c3

  0x000001c89e49951c: vpaddd  xmm0,xmm0,xmm2    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c2

  0x000001c89e499520: vmovd   r10d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c2

  0x000001c89e499525: vphaddd ymm0,ymm10,ymm10  ;...c4
                                                ;...c2
                                                ;...2d
                                                ;...02
                                                ;...c2

  0x000001c89e49952a: vphaddd ymm0,ymm0,ymm3    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c3

  0x000001c89e49952f: vextracti128 xmm3,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c3
                                                ;...01

  0x000001c89e499535: vpaddd  xmm0,xmm0,xmm3    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c3

  0x000001c89e499539: vmovd   xmm3,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...da

  0x000001c89e49953e: vpaddd  xmm3,xmm3,xmm0    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d8

  0x000001c89e499542: vmovd   r11d,xmm3         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...db

  0x000001c89e499547: vphaddd ymm2,ymm7,ymm7    ;...c4
                                                ;...e2
                                                ;...45
                                                ;...02
                                                ;...d7

  0x000001c89e49954c: vphaddd ymm2,ymm2,ymm0    ;...c4
                                                ;...e2
                                                ;...6d
                                                ;...02
                                                ;...d0

  0x000001c89e499551: vextracti128 xmm0,ymm2,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d0
                                                ;...01

  0x000001c89e499557: vpaddd  xmm2,xmm2,xmm0    ;...c5
                                                ;...e9
                                                ;...fe
                                                ;...d0

  0x000001c89e49955b: vmovd   xmm0,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c3

  0x000001c89e499560: vpaddd  xmm0,xmm0,xmm2    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c2

  0x000001c89e499564: vmovd   r10d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c2

  0x000001c89e499569: vphaddd ymm0,ymm6,ymm6    ;...c4
                                                ;...e2
                                                ;...4d
                                                ;...02
                                                ;...c6

  0x000001c89e49956e: vphaddd ymm0,ymm0,ymm3    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c3

  0x000001c89e499573: vextracti128 xmm3,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c3
                                                ;...01

  0x000001c89e499579: vpaddd  xmm0,xmm0,xmm3    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c3

  0x000001c89e49957d: vmovd   xmm3,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...da

  0x000001c89e499582: vpaddd  xmm3,xmm3,xmm0    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d8

  0x000001c89e499586: vmovd   r11d,xmm3         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...db

  0x000001c89e49958b: vphaddd ymm2,ymm5,ymm5    ;...c4
                                                ;...e2
                                                ;...55
                                                ;...02
                                                ;...d5

  0x000001c89e499590: vphaddd ymm2,ymm2,ymm0    ;...c4
                                                ;...e2
                                                ;...6d
                                                ;...02
                                                ;...d0

  0x000001c89e499595: vextracti128 xmm0,ymm2,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d0
                                                ;...01

  0x000001c89e49959b: vpaddd  xmm2,xmm2,xmm0    ;...c5
                                                ;...e9
                                                ;...fe
                                                ;...d0

  0x000001c89e49959f: vmovd   xmm0,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c3

  0x000001c89e4995a4: vpaddd  xmm0,xmm0,xmm2    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c2

  0x000001c89e4995a8: vmovd   r10d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c2

  0x000001c89e4995ad: vphaddd ymm2,ymm4,ymm4    ;...c4
                                                ;...e2
                                                ;...5d
                                                ;...02
                                                ;...d4

  0x000001c89e4995b2: vphaddd ymm2,ymm2,ymm1    ;...c4
                                                ;...e2
                                                ;...6d
                                                ;...02
                                                ;...d1

  0x000001c89e4995b7: vextracti128 xmm1,ymm2,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d1
                                                ;...01

  0x000001c89e4995bd: vpaddd  xmm2,xmm2,xmm1    ;...c5
                                                ;...e9
                                                ;...fe
                                                ;...d1

  0x000001c89e4995c1: vmovd   xmm1,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...ca

  0x000001c89e4995c6: vpaddd  xmm1,xmm1,xmm2    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...ca

  0x000001c89e4995ca: vmovd   ebx,xmm1          ;...c5
                                                ;...f9
                                                ;...7e
                                                ;...cb
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@25 (line 42)

  0x000001c89e4995ce: add     r13d,40h          ;...41
                                                ;...83
                                                ;...c5
                                                ;...40
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@27 (line 41)

  0x000001c89e4995d2: cmp     r13d,r8d          ;...45
                                                ;...3b
                                                ;...e8

  0x000001c89e4995d5: jl      1c89e499400h      ;...0f
                                                ;...8c
                                                ;...25
                                                ;...fe
                                                ;...ff
                                                ;...ff
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@14 (line 41)

  0x000001c89e4995db: mov     r10d,edi          ;...44
                                                ;...8b
                                                ;...d7

  0x000001c89e4995de: add     r10d,0fffffff9h   ;...41
                                                ;...83
                                                ;...c2
                                                ;...f9

  0x000001c89e4995e2: cmp     edi,r10d          ;...41
                                                ;...3b
                                                ;...fa

  0x000001c89e4995e5: cmovl   r10d,ecx          ;...44
                                                ;...0f
                                                ;...4c
                                                ;...d1

  0x000001c89e4995e9: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000001c89e4995ec: jnl     1c89e49962eh      ;...7d
                                                ;...40

  0x000001c89e4995ee: nop                       ;...66
                                                ;...90

  0x000001c89e4995f0: vmovdqu ymm0,ymmword ptr [rbp+r13*4+10h]
                                                ;...c4
                                                ;...a1
                                                ;...7e
                                                ;...6f
                                                ;...44
                                                ;...ad
                                                ;...10
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@23 (line 42)

  0x000001c89e4995f7: vpslld  ymm1,ymm0,3h      ;...c5
                                                ;...f5
                                                ;...72
                                                ;...f0
                                                ;...03

  0x000001c89e4995fc: vpslld  ymm0,ymm0,1h      ;...c5
                                                ;...fd
                                                ;...72
                                                ;...f0
                                                ;...01

  0x000001c89e499601: vpaddd  ymm0,ymm1,ymm0    ;...c5
                                                ;...f5
                                                ;...fe
                                                ;...c0

  0x000001c89e499605: vphaddd ymm3,ymm0,ymm0    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...d8

  0x000001c89e49960a: vphaddd ymm3,ymm3,ymm1    ;...c4
                                                ;...e2
                                                ;...65
                                                ;...02
                                                ;...d9

  0x000001c89e49960f: vextracti128 xmm1,ymm3,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d9
                                                ;...01

  0x000001c89e499615: vpaddd  xmm3,xmm3,xmm1    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d9

  0x000001c89e499619: vmovd   xmm1,ebx          ;...c5
                                                ;...f9
                                                ;...6e
                                                ;...cb

  0x000001c89e49961d: vpaddd  xmm1,xmm1,xmm3    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...cb

  0x000001c89e499621: vmovd   ebx,xmm1          ;...c5
                                                ;...f9
                                                ;...7e
                                                ;...cb
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@25 (line 42)

  0x000001c89e499625: add     r13d,8h           ;...41
                                                ;...83
                                                ;...c5
                                                ;...08
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@27 (line 41)

  0x000001c89e499629: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000001c89e49962c: jl      1c89e4995f0h      ;...7c
                                                ;...c2
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@14 (line 41)

  0x000001c89e49962e: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e499631: jnl     1c89e499651h      ;...7d
                                                ;...1e

  0x000001c89e499633: nop                       ;...90

  0x000001c89e499634: mov     r11d,dword ptr [rbp+r13*4+10h]
                                                ;...46
                                                ;...8b
                                                ;...5c
                                                ;...ad
                                                ;...10
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@23 (line 42)

  0x000001c89e499639: mov     r10d,r11d         ;...45
                                                ;...8b
                                                ;...d3

  0x000001c89e49963c: shl     r10d,3h           ;...41
                                                ;...c1
                                                ;...e2
                                                ;...03

  0x000001c89e499640: shl     r11d,1h           ;...41
                                                ;...d1
                                                ;...e3

  0x000001c89e499643: add     r10d,r11d         ;...45
                                                ;...03
                                                ;...d3

  0x000001c89e499646: add     ebx,r10d          ;...41
                                                ;...03
                                                ;...da
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@25 (line 42)

  0x000001c89e499649: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@27 (line 41)

  0x000001c89e49964c: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e49964f: jl      1c89e499634h      ;...7c
                                                ;...e3
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@14 (line 41)

  0x000001c89e499651: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e499654: jnl     1c89e49967ah      ;...7d
                                                ;...24

  0x000001c89e499656: nop                       ;...66
                                                ;...90

  0x000001c89e499658: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e49965b: jnb     1c89e499691h      ;...73
                                                ;...34

  0x000001c89e49965d: mov     r11d,dword ptr [rbp+r13*4+10h]
                                                ;...46
                                                ;...8b
                                                ;...5c
                                                ;...ad
                                                ;...10
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@23 (line 42)

  0x000001c89e499662: mov     r10d,r11d         ;...45
                                                ;...8b
                                                ;...d3

  0x000001c89e499665: shl     r10d,3h           ;...41
                                                ;...c1
                                                ;...e2
                                                ;...03

  0x000001c89e499669: shl     r11d,1h           ;...41
                                                ;...d1
                                                ;...e3

  0x000001c89e49966c: add     r10d,r11d         ;...45
                                                ;...03
                                                ;...d3

  0x000001c89e49966f: add     ebx,r10d          ;...41
                                                ;...03
                                                ;...da
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@25 (line 42)

  0x000001c89e499672: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@27 (line 41)

  0x000001c89e499675: cmp     r13d,edi          ;...44
                                                ;...3b
                                                ;...ef

  0x000001c89e499678: jl      1c89e499658h      ;...7c
                                                ;...de
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int@10 (line 41)

  0x000001c89e49967a: mov     eax,ebx           ;...8b
                                                ;...c3

  0x000001c89e49967c: vzeroupper                ;...c5
                                                ;...f8
                                                ;...77

  0x000001c89e49967f: add     rsp,40h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...40

  0x000001c89e499683: pop     rbp               ;...5d

  0x000001c89e499684: test    dword ptr [1c88a9e0000h],eax
                                                ;...85
                                                ;...05
                                                ;...76
                                                ;...69
                                                ;...54
                                                ;...ec
                                                ;   {poll_return}
  0x000001c89e49968a: ret 

The loop is aggressively unrolled, pipelined, and vectorised. Moreover, the multiplication by ten results not in a multiplication but two left shifts (see VPSLLD) and an addition. Note that x << 1 + x << 3 = x * 10 and C2 seems to know it; this rewrite can be applied because it can be proven statically that the factor is always 10. The “optimised” loop doesn’t vectorise at all (and I have no idea why not – isn’t this a bug? Yes it is.)

com/openkappa/simd/scale/Scale.FactoredScale_Int(Lcom/openkappa/simd/state/IntData;)I  [0x000002bbebeda320, 0x000002bbebeda4b8]  408 bytes
Argument 0 is unknown.RIP: 0x2bbebeda320 Code size: 0x00000198
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000002bb81241148} 'FactoredScale_Int' '(Lcom/openkappa/simd/state/IntData;)I' in 'com/openkappa/simd/scale/Scale'
  0x000002bbebeda320: int3                      ;...cc

  0x000002bbebeda321: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000002bbebeda32c: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

  0x000002bbebeda330: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x000002bbebeda337: push    rbp               ;...55

  0x000002bbebeda338: sub     rsp,40h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...40

  0x000002bbebeda33c: mov     rbp,qword ptr [rdx+8h]  ;...48
                                                ;...8b
                                                ;...6a
                                                ;...08

  0x000002bbebeda340: mov     ebx,dword ptr [rdx+10h]  ;...8b
                                                ;...5a
                                                ;...10

  0x000002bbebeda343: mov     r13d,dword ptr [rdx]  ;...44
                                                ;...8b
                                                ;...2a

  0x000002bbebeda346: mov     rcx,rdx           ;...48
                                                ;...8b
                                                ;...ca

  0x000002bbebeda349: mov     r10,51da8d20h     ;...49
                                                ;...ba
                                                ;...20
                                                ;...8d
                                                ;...da
                                                ;...51
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000002bbebeda353: call indirect r10         ;...41
                                                ;...ff
                                                ;...d2

  0x000002bbebeda356: mov     r10d,dword ptr [rbp+8h]  ;...44
                                                ;...8b
                                                ;...55
                                                ;...08
                                                ; implicit exception: dispatches to 0x000002bbebeda46d
  0x000002bbebeda35a: cmp     r10d,0f800016dh   ;...41
                                                ;...81
                                                ;...fa
                                                ;...6d
                                                ;...01
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array int})}
  0x000002bbebeda361: jne     2bbebeda459h      ;...0f
                                                ;...85
                                                ;...f2
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@10 (line 52)

  0x000002bbebeda367: mov     r10d,dword ptr [rbp+0ch]
                                                ;...44
                                                ;...8b
                                                ;...55
                                                ;...0c
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@13 (line 52)

  0x000002bbebeda36b: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda36e: jnl     2bbebeda422h      ;...0f
                                                ;...8d
                                                ;...ae
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@14 (line 52)

  0x000002bbebeda374: mov     r11d,r13d         ;...45
                                                ;...8b
                                                ;...dd

  0x000002bbebeda377: inc     r11d              ;...41
                                                ;...ff
                                                ;...c3

  0x000002bbebeda37a: xor     r8d,r8d           ;...45
                                                ;...33
                                                ;...c0

  0x000002bbebeda37d: cmp     r11d,r8d          ;...45
                                                ;...3b
                                                ;...d8

  0x000002bbebeda380: cmovl   r11d,r8d          ;...45
                                                ;...0f
                                                ;...4c
                                                ;...d8

  0x000002bbebeda384: cmp     r11d,r10d         ;...45
                                                ;...3b
                                                ;...da

  0x000002bbebeda387: cmovnle r11d,r10d         ;...45
                                                ;...0f
                                                ;...4f
                                                ;...da

  0x000002bbebeda38b: nop                       ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@21 (line 53)

  0x000002bbebeda38c: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda38f: jnb     2bbebeda43ch      ;...0f
                                                ;...83
                                                ;...a7
                                                ;...00
                                                ;...00
                                                ;...00

  0x000002bbebeda395: add     ebx,dword ptr [rbp+r13*4+10h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...ad
                                                ;...10
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@22 (line 53)

  0x000002bbebeda39a: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@24 (line 52)

  0x000002bbebeda39d: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x000002bbebeda3a0: jl      2bbebeda38ch      ;...7c
                                                ;...ea
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@14 (line 52)

  0x000002bbebeda3a2: mov     r11d,r10d         ;...45
                                                ;...8b
                                                ;...da

  0x000002bbebeda3a5: add     r11d,0fffffff9h   ;...41
                                                ;...83
                                                ;...c3
                                                ;...f9

  0x000002bbebeda3a9: mov     r8d,80000000h     ;...41
                                                ;...b8
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...80

  0x000002bbebeda3af: cmp     r10d,r11d         ;...45
                                                ;...3b
                                                ;...d3

  0x000002bbebeda3b2: cmovl   r11d,r8d          ;...45
                                                ;...0f
                                                ;...4c
                                                ;...d8

  0x000002bbebeda3b6: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x000002bbebeda3b9: jnl     2bbebeda409h      ;...7d
                                                ;...4e

  0x000002bbebeda3bb: nop     dword ptr [rax+rax+0h]  ;...0f
                                                ;...1f
                                                ;...44
                                                ;...00
                                                ;...00
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@21 (line 53)

  0x000002bbebeda3c0: add     ebx,dword ptr [rbp+r13*4+10h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...ad
                                                ;...10

  0x000002bbebeda3c5: movsxd  r8,r13d           ;...4d
                                                ;...63
                                                ;...c5

  0x000002bbebeda3c8: add     ebx,dword ptr [rbp+r8*4+14h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...14

  0x000002bbebeda3cd: add     ebx,dword ptr [rbp+r8*4+18h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...18

  0x000002bbebeda3d2: add     ebx,dword ptr [rbp+r8*4+1ch]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...1c

  0x000002bbebeda3d7: add     ebx,dword ptr [rbp+r8*4+20h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...20

  0x000002bbebeda3dc: add     ebx,dword ptr [rbp+r8*4+24h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...24

  0x000002bbebeda3e1: add     ebx,dword ptr [rbp+r8*4+28h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...28

  0x000002bbebeda3e6: add     ebx,dword ptr [rbp+r8*4+2ch]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...85
                                                ;...2c
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@22 (line 53)

  0x000002bbebeda3eb: add     r13d,8h           ;...41
                                                ;...83
                                                ;...c5
                                                ;...08
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@24 (line 52)

  0x000002bbebeda3ef: cmp     r13d,r11d         ;...45
                                                ;...3b
                                                ;...eb

  0x000002bbebeda3f2: jl      2bbebeda3c0h      ;...7c
                                                ;...cc
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@14 (line 52)

  0x000002bbebeda3f4: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda3f7: jnl     2bbebeda409h      ;...7d
                                                ;...10

  0x000002bbebeda3f9: nop                       ;...66
                                                ;...66
                                                ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@21 (line 53)

  0x000002bbebeda3fc: add     ebx,dword ptr [rbp+r13*4+10h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...ad
                                                ;...10
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@22 (line 53)

  0x000002bbebeda401: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@24 (line 52)

  0x000002bbebeda404: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda407: jl      2bbebeda3fch      ;...7c
                                                ;...f3
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@14 (line 52)

  0x000002bbebeda409: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda40c: jnl     2bbebeda422h      ;...7d
                                                ;...14

  0x000002bbebeda40e: nop                       ;...66
                                                ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@21 (line 53)

  0x000002bbebeda410: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda413: jnb     2bbebeda442h      ;...73
                                                ;...2d

  0x000002bbebeda415: add     ebx,dword ptr [rbp+r13*4+10h]
                                                ;...42
                                                ;...03
                                                ;...5c
                                                ;...ad
                                                ;...10
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@22 (line 53)

  0x000002bbebeda41a: inc     r13d              ;...41
                                                ;...ff
                                                ;...c5
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@24 (line 52)

  0x000002bbebeda41d: cmp     r13d,r10d         ;...45
                                                ;...3b
                                                ;...ea

  0x000002bbebeda420: jl      2bbebeda410h      ;...7c
                                                ;...ee
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@10 (line 52)

  0x000002bbebeda422: mov     r11d,ebx          ;...44
                                                ;...8b
                                                ;...db

  0x000002bbebeda425: shl     r11d,3h           ;...41
                                                ;...c1
                                                ;...e3
                                                ;...03

  0x000002bbebeda429: shl     ebx,1h            ;...d1
                                                ;...e3

  0x000002bbebeda42b: add     ebx,r11d          ;...41
                                                ;...03
                                                ;...db
                                                ;*imul {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::FactoredScale_Int@33 (line 55)

  0x000002bbebeda42e: mov     eax,ebx           ;...8b
                                                ;...c3

  0x000002bbebeda430: add     rsp,40h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...40

  0x000002bbebeda434: pop     rbp               ;...5d

  0x000002bbebeda435: test    dword ptr [2bbd8590000h],eax
                                                ;...85
                                                ;...05
                                                ;...c5
                                                ;...5b
                                                ;...6b
                                                ;...ec
                                                ;   {poll_return}
  0x000002bbebeda43b: ret                       ;...c3

This is a special case: data is usually dynamic and variable, so the loop cannot always be proven to be equivalent to a linear combination of bit shifts. The routine is compiled for all possible parameters, not just statically contrived cases like the one above, so you may never see this assembly in the wild. However, even with random factors, the slow looking loop is aggressively optimised in a way the hand “optimised” code is not:


    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public int Scale_Int_Dynamic(ScaleState state) {
        int value = 0;
        int[] data = state.data;
        int factor = state.randomFactor();
        for (int i = 0; i < data.length; ++i) {
            value += factor * data[i];
        }
        return value;
    }

    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    @Benchmark
    public int FactoredScale_Int_Dynamic(ScaleState state) {
        int value = 0;
        int[] data = state.data;
        int factor = state.randomFactor();
        for (int i = 0; i < data.length; ++i) {
            value += data[i];
        }
        return factor * value;
    }

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
FactoredScale_Int_Dynamic thrpt 1 10 26.100439 0.340069 ops/ms 100000
FactoredScale_Int_Dynamic thrpt 1 10 1.918011 0.297925 ops/ms 1000000
Scale_Int_Dynamic thrpt 1 10 30.219809 2.977389 ops/ms 100000
Scale_Int_Dynamic thrpt 1 10 2.314159 0.378442 ops/ms 1000000

Far from seeking to exploit distributivity to reduce the number of multiplication instructions, it seems to almost embrace the extraneous operations as metadata to drive optimisations. The assembly for Scale_Int_Dynamic confirms this (it shows vectorised multiplication, not shifts, within the loop):

com/openkappa/simd/scale/Scale.Scale_Int_Dynamic(Lcom/openkappa/simd/scale/ScaleState;)I  [0x000001f5ca2fa120, 0x000001f5ca2fa498]  888 bytes
Argument 0 is unknown.RIP: 0x1f5ca2fa120 Code size: 0x00000378
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000001f5df561a20} 'Scale_Int_Dynamic' '(Lcom/openkappa/simd/scale/ScaleState;)I' in 'com/openkappa/simd/scale/Scale'
  0x000001f5ca2fa120: int3                      ;...cc

  0x000001f5ca2fa121: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa12c: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

  0x000001f5ca2fa130: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x000001f5ca2fa137: push    rbp               ;...55

  0x000001f5ca2fa138: sub     rsp,50h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...50

  0x000001f5ca2fa13c: mov     r13,qword ptr [rdx+10h]  ;...4c
                                                ;...8b
                                                ;...6a
                                                ;...10

  0x000001f5ca2fa140: mov     ebx,dword ptr [rdx+18h]  ;...8b
                                                ;...5a
                                                ;...18

  0x000001f5ca2fa143: mov     ebp,dword ptr [rdx+8h]  ;...8b
                                                ;...6a
                                                ;...08

  0x000001f5ca2fa146: mov     r14d,dword ptr [rdx]  ;...44
                                                ;...8b
                                                ;...32

  0x000001f5ca2fa149: mov     rcx,rdx           ;...48
                                                ;...8b
                                                ;...ca

  0x000001f5ca2fa14c: vzeroupper                ;...c5
                                                ;...f8
                                                ;...77

  0x000001f5ca2fa14f: mov     r10,51da8d20h     ;...49
                                                ;...ba
                                                ;...20
                                                ;...8d
                                                ;...da
                                                ;...51
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa159: call indirect r10         ;...41
                                                ;...ff
                                                ;...d2

  0x000001f5ca2fa15c: mov     r10d,dword ptr [r13+8h]  ;...45
                                                ;...8b
                                                ;...55
                                                ;...08
                                                ; implicit exception: dispatches to 0x000001f5ca2fa461
  0x000001f5ca2fa160: cmp     r10d,0f800016dh   ;...41
                                                ;...81
                                                ;...fa
                                                ;...6d
                                                ;...01
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array int})}
  0x000001f5ca2fa167: jne     1f5ca2fa445h      ;...0f
                                                ;...85
                                                ;...d8
                                                ;...02
                                                ;...00
                                                ;...00
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@16 (line 64)

  0x000001f5ca2fa16d: mov     edi,dword ptr [r13+0ch]  ;...41
                                                ;...8b
                                                ;...7d
                                                ;...0c
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@19 (line 64)

  0x000001f5ca2fa171: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa174: jnl     1f5ca2fa411h      ;...0f
                                                ;...8d
                                                ;...97
                                                ;...02
                                                ;...00
                                                ;...00
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@20 (line 64)

  0x000001f5ca2fa17a: mov     r11d,r13d         ;...45
                                                ;...8b
                                                ;...dd

  0x000001f5ca2fa17d: mov     r10d,r14d         ;...45
                                                ;...8b
                                                ;...d6

  0x000001f5ca2fa180: inc     r10d              ;...41
                                                ;...ff
                                                ;...c2

  0x000001f5ca2fa183: shr     r11d,2h           ;...41
                                                ;...c1
                                                ;...eb
                                                ;...02

  0x000001f5ca2fa187: and     r11d,7h           ;...41
                                                ;...83
                                                ;...e3
                                                ;...07

  0x000001f5ca2fa18b: xor     r8d,r8d           ;...45
                                                ;...33
                                                ;...c0

  0x000001f5ca2fa18e: cmp     r10d,r8d          ;...45
                                                ;...3b
                                                ;...d0

  0x000001f5ca2fa191: cmovl   r10d,r8d          ;...45
                                                ;...0f
                                                ;...4c
                                                ;...d0

  0x000001f5ca2fa195: cmp     r10d,edi          ;...44
                                                ;...3b
                                                ;...d7

  0x000001f5ca2fa198: cmovnle r10d,edi          ;...44
                                                ;...0f
                                                ;...4f
                                                ;...d7

  0x000001f5ca2fa19c: add     r11d,r10d         ;...45
                                                ;...03
                                                ;...da

  0x000001f5ca2fa19f: mov     r9d,4h            ;...41
                                                ;...b9
                                                ;...04
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa1a5: sub     r9d,r11d          ;...45
                                                ;...2b
                                                ;...cb

  0x000001f5ca2fa1a8: and     r9d,7h            ;...41
                                                ;...83
                                                ;...e1
                                                ;...07

  0x000001f5ca2fa1ac: add     r9d,r10d          ;...45
                                                ;...03
                                                ;...ca

  0x000001f5ca2fa1af: cmp     r9d,edi           ;...44
                                                ;...3b
                                                ;...cf

  0x000001f5ca2fa1b2: cmovnle r9d,edi           ;...44
                                                ;...0f
                                                ;...4f
                                                ;...cf
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@29 (line 65)

  0x000001f5ca2fa1b6: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa1b9: jnb     1f5ca2fa422h      ;...0f
                                                ;...83
                                                ;...63
                                                ;...02
                                                ;...00
                                                ;...00

  0x000001f5ca2fa1bf: mov     r11d,ebp          ;...44
                                                ;...8b
                                                ;...dd

  0x000001f5ca2fa1c2: imul    r11d,dword ptr [r13+r14*4+10h]
                                                ;...47
                                                ;...0f
                                                ;...af
                                                ;...5c
                                                ;...b5
                                                ;...10

  0x000001f5ca2fa1c8: add     ebx,r11d          ;...41
                                                ;...03
                                                ;...db
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@31 (line 65)

  0x000001f5ca2fa1cb: inc     r14d              ;...41
                                                ;...ff
                                                ;...c6
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@33 (line 64)

  0x000001f5ca2fa1ce: cmp     r14d,r9d          ;...45
                                                ;...3b
                                                ;...f1

  0x000001f5ca2fa1d1: jl      1f5ca2fa1b6h      ;...7c
                                                ;...e3
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@20 (line 64)

  0x000001f5ca2fa1d3: mov     r9d,edi           ;...44
                                                ;...8b
                                                ;...cf

  0x000001f5ca2fa1d6: add     r9d,0ffffffc1h    ;...41
                                                ;...83
                                                ;...c1
                                                ;...c1

  0x000001f5ca2fa1da: mov     r8d,80000000h     ;...41
                                                ;...b8
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...80

  0x000001f5ca2fa1e0: cmp     edi,r9d           ;...41
                                                ;...3b
                                                ;...f9

  0x000001f5ca2fa1e3: cmovl   r9d,r8d           ;...45
                                                ;...0f
                                                ;...4c
                                                ;...c8

  0x000001f5ca2fa1e7: cmp     r14d,r9d          ;...45
                                                ;...3b
                                                ;...f1

  0x000001f5ca2fa1ea: jnl     1f5ca2fa3f0h      ;...0f
                                                ;...8d
                                                ;...00
                                                ;...02
                                                ;...00
                                                ;...00

  0x000001f5ca2fa1f0: vmovd   xmm2,ebp          ;...c5
                                                ;...f9
                                                ;...6e
                                                ;...d5

  0x000001f5ca2fa1f4: vpshufd xmm2,xmm2,0h      ;...c5
                                                ;...f9
                                                ;...70
                                                ;...d2
                                                ;...00

  0x000001f5ca2fa1f9: vinserti128 ymm2,ymm2,xmm2,1h  ;...c4
                                                ;...e3
                                                ;...6d
                                                ;...38
                                                ;...d2
                                                ;...01

  0x000001f5ca2fa1ff: nop                       ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@29 (line 65)

  0x000001f5ca2fa200: vmovdqu ymm0,ymmword ptr [r13+r14*4+10h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...44
                                                ;...b5
                                                ;...10

  0x000001f5ca2fa207: vpmulld ymm11,ymm0,ymm2   ;...c4
                                                ;...62
                                                ;...7d
                                                ;...40
                                                ;...da

  0x000001f5ca2fa20c: movsxd  r10,r14d          ;...4d
                                                ;...63
                                                ;...d6

  0x000001f5ca2fa20f: vmovdqu ymm0,ymmword ptr [r13+r10*4+30h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...44
                                                ;...95
                                                ;...30

  0x000001f5ca2fa216: vmovdqu ymm1,ymmword ptr [r13+r10*4+0f0h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...8c
                                                ;...95
                                                ;...f0
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa220: vmovdqu ymm3,ymmword ptr [r13+r10*4+50h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...5c
                                                ;...95
                                                ;...50

  0x000001f5ca2fa227: vmovdqu ymm7,ymmword ptr [r13+r10*4+70h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...7c
                                                ;...95
                                                ;...70

  0x000001f5ca2fa22e: vmovdqu ymm6,ymmword ptr [r13+r10*4+90h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...b4
                                                ;...95
                                                ;...90
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa238: vmovdqu ymm5,ymmword ptr [r13+r10*4+0b0h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...ac
                                                ;...95
                                                ;...b0
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa242: vmovdqu ymm4,ymmword ptr [r13+r10*4+0d0h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...a4
                                                ;...95
                                                ;...d0
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001f5ca2fa24c: vpmulld ymm9,ymm0,ymm2    ;...c4
                                                ;...62
                                                ;...7d
                                                ;...40
                                                ;...ca

  0x000001f5ca2fa251: vpmulld ymm4,ymm4,ymm2    ;...c4
                                                ;...e2
                                                ;...5d
                                                ;...40
                                                ;...e2

  0x000001f5ca2fa256: vpmulld ymm5,ymm5,ymm2    ;...c4
                                                ;...e2
                                                ;...55
                                                ;...40
                                                ;...ea

  0x000001f5ca2fa25b: vpmulld ymm6,ymm6,ymm2    ;...c4
                                                ;...e2
                                                ;...4d
                                                ;...40
                                                ;...f2

  0x000001f5ca2fa260: vpmulld ymm8,ymm7,ymm2    ;...c4
                                                ;...62
                                                ;...45
                                                ;...40
                                                ;...c2

  0x000001f5ca2fa265: vpmulld ymm10,ymm3,ymm2   ;...c4
                                                ;...62
                                                ;...65
                                                ;...40
                                                ;...d2

  0x000001f5ca2fa26a: vpmulld ymm3,ymm1,ymm2    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...40
                                                ;...da

  0x000001f5ca2fa26f: vphaddd ymm1,ymm11,ymm11  ;...c4
                                                ;...c2
                                                ;...25
                                                ;...02
                                                ;...cb

  0x000001f5ca2fa274: vphaddd ymm1,ymm1,ymm0    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...c8

  0x000001f5ca2fa279: vextracti128 xmm0,ymm1,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c8
                                                ;...01

  0x000001f5ca2fa27f: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa283: vmovd   xmm0,ebx          ;...c5
                                                ;...f9
                                                ;...6e
                                                ;...c3

  0x000001f5ca2fa287: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa28b: vmovd   r10d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c2

  0x000001f5ca2fa290: vphaddd ymm1,ymm9,ymm9    ;...c4
                                                ;...c2
                                                ;...35
                                                ;...02
                                                ;...c9

  0x000001f5ca2fa295: vphaddd ymm1,ymm1,ymm0    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...c8

  0x000001f5ca2fa29a: vextracti128 xmm0,ymm1,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c8
                                                ;...01

  0x000001f5ca2fa2a0: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa2a4: vmovd   xmm0,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c2

  0x000001f5ca2fa2a9: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa2ad: vmovd   r11d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c3

  0x000001f5ca2fa2b2: vphaddd ymm0,ymm10,ymm10  ;...c4
                                                ;...c2
                                                ;...2d
                                                ;...02
                                                ;...c2

  0x000001f5ca2fa2b7: vphaddd ymm0,ymm0,ymm1    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c1

  0x000001f5ca2fa2bc: vextracti128 xmm1,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c1
                                                ;...01

  0x000001f5ca2fa2c2: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa2c6: vmovd   xmm1,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...cb

  0x000001f5ca2fa2cb: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa2cf: vmovd   r10d,xmm1         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...ca

  0x000001f5ca2fa2d4: vphaddd ymm1,ymm8,ymm8    ;...c4
                                                ;...c2
                                                ;...3d
                                                ;...02
                                                ;...c8

  0x000001f5ca2fa2d9: vphaddd ymm1,ymm1,ymm0    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...c8

  0x000001f5ca2fa2de: vextracti128 xmm0,ymm1,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c8
                                                ;...01

  0x000001f5ca2fa2e4: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa2e8: vmovd   xmm0,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c2

  0x000001f5ca2fa2ed: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa2f1: vmovd   r11d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c3

  0x000001f5ca2fa2f6: vphaddd ymm0,ymm6,ymm6    ;...c4
                                                ;...e2
                                                ;...4d
                                                ;...02
                                                ;...c6

  0x000001f5ca2fa2fb: vphaddd ymm0,ymm0,ymm1    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c1

  0x000001f5ca2fa300: vextracti128 xmm1,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c1
                                                ;...01

  0x000001f5ca2fa306: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa30a: vmovd   xmm1,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...cb

  0x000001f5ca2fa30f: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa313: vmovd   r10d,xmm1         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...ca

  0x000001f5ca2fa318: vphaddd ymm1,ymm5,ymm5    ;...c4
                                                ;...e2
                                                ;...55
                                                ;...02
                                                ;...cd

  0x000001f5ca2fa31d: vphaddd ymm1,ymm1,ymm0    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...c8

  0x000001f5ca2fa322: vextracti128 xmm0,ymm1,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c8
                                                ;...01

  0x000001f5ca2fa328: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa32c: vmovd   xmm0,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...c2

  0x000001f5ca2fa331: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa335: vmovd   r11d,xmm0         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...c3

  0x000001f5ca2fa33a: vphaddd ymm0,ymm4,ymm4    ;...c4
                                                ;...e2
                                                ;...5d
                                                ;...02
                                                ;...c4

  0x000001f5ca2fa33f: vphaddd ymm0,ymm0,ymm1    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...02
                                                ;...c1

  0x000001f5ca2fa344: vextracti128 xmm1,ymm0,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...c1
                                                ;...01

  0x000001f5ca2fa34a: vpaddd  xmm0,xmm0,xmm1    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c1

  0x000001f5ca2fa34e: vmovd   xmm1,r11d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...cb

  0x000001f5ca2fa353: vpaddd  xmm1,xmm1,xmm0    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...c8

  0x000001f5ca2fa357: vmovd   r10d,xmm1         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...7e
                                                ;...ca

  0x000001f5ca2fa35c: vphaddd ymm1,ymm3,ymm3    ;...c4
                                                ;...e2
                                                ;...65
                                                ;...02
                                                ;...cb

  0x000001f5ca2fa361: vphaddd ymm1,ymm1,ymm7    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...cf

  0x000001f5ca2fa366: vextracti128 xmm7,ymm1,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...cf
                                                ;...01

  0x000001f5ca2fa36c: vpaddd  xmm1,xmm1,xmm7    ;...c5
                                                ;...f1
                                                ;...fe
                                                ;...cf

  0x000001f5ca2fa370: vmovd   xmm7,r10d         ;...c4
                                                ;...c1
                                                ;...79
                                                ;...6e
                                                ;...fa

  0x000001f5ca2fa375: vpaddd  xmm7,xmm7,xmm1    ;...c5
                                                ;...c1
                                                ;...fe
                                                ;...f9

  0x000001f5ca2fa379: vmovd   ebx,xmm7          ;...c5
                                                ;...f9
                                                ;...7e
                                                ;...fb
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@31 (line 65)

  0x000001f5ca2fa37d: add     r14d,40h          ;...41
                                                ;...83
                                                ;...c6
                                                ;...40
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@33 (line 64)

  0x000001f5ca2fa381: cmp     r14d,r9d          ;...45
                                                ;...3b
                                                ;...f1

  0x000001f5ca2fa384: jl      1f5ca2fa200h      ;...0f
                                                ;...8c
                                                ;...76
                                                ;...fe
                                                ;...ff
                                                ;...ff
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@20 (line 64)

  0x000001f5ca2fa38a: mov     r11d,edi          ;...44
                                                ;...8b
                                                ;...df

  0x000001f5ca2fa38d: add     r11d,0fffffff9h   ;...41
                                                ;...83
                                                ;...c3
                                                ;...f9

  0x000001f5ca2fa391: cmp     edi,r11d          ;...41
                                                ;...3b
                                                ;...fb

  0x000001f5ca2fa394: cmovl   r11d,r8d          ;...45
                                                ;...0f
                                                ;...4c
                                                ;...d8

  0x000001f5ca2fa398: cmp     r14d,r11d         ;...45
                                                ;...3b
                                                ;...f3

  0x000001f5ca2fa39b: jnl     1f5ca2fa3d5h      ;...7d
                                                ;...38

  0x000001f5ca2fa39d: nop                       ;...66
                                                ;...66
                                                ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@29 (line 65)

  0x000001f5ca2fa3a0: vmovdqu ymm0,ymmword ptr [r13+r14*4+10h]
                                                ;...c4
                                                ;...81
                                                ;...7e
                                                ;...6f
                                                ;...44
                                                ;...b5
                                                ;...10

  0x000001f5ca2fa3a7: vpmulld ymm1,ymm0,ymm2    ;...c4
                                                ;...e2
                                                ;...7d
                                                ;...40
                                                ;...ca

  0x000001f5ca2fa3ac: vphaddd ymm3,ymm1,ymm1    ;...c4
                                                ;...e2
                                                ;...75
                                                ;...02
                                                ;...d9

  0x000001f5ca2fa3b1: vphaddd ymm3,ymm3,ymm0    ;...c4
                                                ;...e2
                                                ;...65
                                                ;...02
                                                ;...d8

  0x000001f5ca2fa3b6: vextracti128 xmm0,ymm3,1h  ;...c4
                                                ;...e3
                                                ;...7d
                                                ;...39
                                                ;...d8
                                                ;...01

  0x000001f5ca2fa3bc: vpaddd  xmm3,xmm3,xmm0    ;...c5
                                                ;...e1
                                                ;...fe
                                                ;...d8

  0x000001f5ca2fa3c0: vmovd   xmm0,ebx          ;...c5
                                                ;...f9
                                                ;...6e
                                                ;...c3

  0x000001f5ca2fa3c4: vpaddd  xmm0,xmm0,xmm3    ;...c5
                                                ;...f9
                                                ;...fe
                                                ;...c3

  0x000001f5ca2fa3c8: vmovd   ebx,xmm0          ;...c5
                                                ;...f9
                                                ;...7e
                                                ;...c3
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@31 (line 65)

  0x000001f5ca2fa3cc: add     r14d,8h           ;...41
                                                ;...83
                                                ;...c6
                                                ;...08
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@33 (line 64)

  0x000001f5ca2fa3d0: cmp     r14d,r11d         ;...45
                                                ;...3b
                                                ;...f3

  0x000001f5ca2fa3d3: jl      1f5ca2fa3a0h      ;...7c
                                                ;...cb
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@20 (line 64)

  0x000001f5ca2fa3d5: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa3d8: jnl     1f5ca2fa3f0h      ;...7d
                                                ;...16

  0x000001f5ca2fa3da: nop                       ;...66
                                                ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@29 (line 65)

  0x000001f5ca2fa3dc: mov     r10d,ebp          ;...44
                                                ;...8b
                                                ;...d5

  0x000001f5ca2fa3df: imul    r10d,dword ptr [r13+r14*4+10h]
                                                ;...47
                                                ;...0f
                                                ;...af
                                                ;...54
                                                ;...b5
                                                ;...10

  0x000001f5ca2fa3e5: add     ebx,r10d          ;...41
                                                ;...03
                                                ;...da
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@31 (line 65)

  0x000001f5ca2fa3e8: inc     r14d              ;...41
                                                ;...ff
                                                ;...c6
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@33 (line 64)

  0x000001f5ca2fa3eb: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa3ee: jl      1f5ca2fa3dch      ;...7c
                                                ;...ec
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@20 (line 64)

  0x000001f5ca2fa3f0: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa3f3: jnl     1f5ca2fa411h      ;...7d
                                                ;...1c

  0x000001f5ca2fa3f5: nop                       ;...66
                                                ;...66
                                                ;...90
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@29 (line 65)

  0x000001f5ca2fa3f8: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa3fb: jnb     1f5ca2fa428h      ;...73
                                                ;...2b

  0x000001f5ca2fa3fd: mov     r11d,ebp          ;...44
                                                ;...8b
                                                ;...dd

  0x000001f5ca2fa400: imul    r11d,dword ptr [r13+r14*4+10h]
                                                ;...47
                                                ;...0f
                                                ;...af
                                                ;...5c
                                                ;...b5
                                                ;...10

  0x000001f5ca2fa406: add     ebx,r11d          ;...41
                                                ;...03
                                                ;...db
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@31 (line 65)

  0x000001f5ca2fa409: inc     r14d              ;...41
                                                ;...ff
                                                ;...c6
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@33 (line 64)

  0x000001f5ca2fa40c: cmp     r14d,edi          ;...44
                                                ;...3b
                                                ;...f7

  0x000001f5ca2fa40f: jl      1f5ca2fa3f8h      ;...7c
                                                ;...e7
                                                ;*iload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.scale.Scale::Scale_Int_Dynamic@16 (line 64)

  0x000001f5ca2fa411: mov     eax,ebx           ;...8b
                                                ;...c3

  0x000001f5ca2fa413: vzeroupper                ;...c5
                                                ;...f8
                                                ;...77

  0x000001f5ca2fa416: add     rsp,50h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...50

  0x000001f5ca2fa41a: pop     rbp               ;...5d

  0x000001f5ca2fa41b: test    dword ptr [1f5b68c0000h],eax
                                                ;...85
                                                ;...05
                                                ;...df
                                                ;...5b
                                                ;...5c
                                                ;...ec
                                                ;   {poll_return}
  0x000001f5ca2fa421: ret                       ;...c3

There are two lessons to be learnt here. The first is that what you see is not what you get. The second is about the correctness of asymptotic analysis. If hierarchical cache renders asymptotic analysis bullshit (linear time but cache friendly algorithms can, and do, outperform logarithmic algorithms with cache misses), optimising compilers render the field practically irrelevant.

Confusing Sets and Lists

Optimisation is rarely free: often point improvements incur costs elsewhere. Sometimes we try to optimise away the constraints we observe, without questioning our underlying assumptions. I have often seen the roles of lists and sets confused. An application can be brought to its knees – that is, cease to deliver commercial value – if List.contains is called frequently enough on big enough lists. And then there is the workaround…

When I moved over to Java from C++ several years ago, it seemed utterly crazy that there was even a Collection interface – exactly what Scott Meier’s Effective STL said not to do. I still think it’s crazy. Sets and lists cannot be substituted, and when you add up the marginal costs, as well as the costs of any compensatory workarounds, confusing them is responsible for a lot of performance bugs. As an application developer, it is part of your job to choose. Here are a few simple examples of when to use each collection type.

Contains

Is an element in the collection?

Never ever do this with a List. This operation is often referred to as being O(n). Which means in your worst case will touch every element in the list (technically, at least once). You have a choice between HashSet and a TreeSet, and both have costs and benefits.

If you choose a HashSet, your best case is O(1): you evaluate a hash code, take its modulus with respect to the size of an array, and look up a bucket containing only one element. The worst case occurs with a degenerate hash code which maps all elements to the same bucket. This is again O(n): you probe a linked list testing each element for equality. On average you get something between these two cases and it depends on the uniformity of your hash code implementation.

If you choose a TreeSet you get a worst case O(log n): this is effectively just a binary search through the nodes in a red black tree. Performance is limited by the cost of the comparator, and suffers systematically from cache misses for large sets (like any kind of pointer chasing, branch prediction and prefetching is difficult if not impossible).

If you’re working with numbers, and small to medium collections, a sorted primitive array may be the best approach, so long as it fits in cache. If you’re working with integers, you can do this in constant time in the worst case by using a BitSet.

Select

What is the value of the element at a given index with respect to a sort order?

This is an obvious use case for a List: it’s O(1) – this is just a lookup at an array offset.

You couldn’t even write the code with a HashSet without copying the data into an intermediate ordered structure, at which point you would probably think again. You see this sort of thing done in code written by inexpensive programmers at large outsourcing consultancies, who were perhaps just under unreasonable pressure to deliver to arbitrary deadlines.

SortedSet, and anything conceptually similar, is the wrong data structure for this operation. The only way to compute this is O(n): you iterate through the set incrementing a counter until you reach the index, and then return the element you’ve iterated to. If you reach the end of the set, you throw. If you do this a lot, you’ll notice.

Rank

How many predecessors does an element have with respect to a sort order?

Another classic operation for List, so long as you keep it sorted. Use Collections.binarySearch to find the index of the element in the collection with complexity O(log n). This is its rank. If you can get away with it, primitive arrays will be much better here, especially if they are small enough to fit in cache.

Once again, there are creativity points available for the solution involving a HashSet, and they do exist in the wild, but a clean looking solution is at least possible with a SortedSet. However, it involves an iteration with another check against an incrementing counter. It’s O(n) and if you do it a lot, you’ll blow your performance profile, so use a sorted list instead.

What if you had the source code?

Is this fundamental or just a limitation of the Collections framework? Maybe if you had the source code you could just make these data structures optimal for every use case, without having to choose the right one? Not without creating a Frankenstein, and not without a lot of memory. Optimisation isn’t free.

How much Algebra does C2 Know? Part 1: Associativity

Making loops execute faster is firmly rooted in algebra, but how much does C2 know or care about? When building a highly optimised query engine, a critical concern is the quality of assembly code generated for loops. There is a lot more to JIT compilation than loop optimisation; inlining, class hierarchy analysis, escape analysis to name but a few. Moreover, everything it does has to be fast since it shares resources with the application itself; it can’t spend time unless it brings a net benefit. Being such a generalist, does C2, the JIT compiler used in server applications, know high school algebra?

Specific knowledge of maths is not always worthwhile to program execution, even when it leads to high performance gains. As a motivating example, there is no way to refer directly to the natural numbers in any programming language I have ever used. For instance, the sum of the first n natural numbers is ((n+1) * n)/2, and most high school students know it. This expression is intuitively much faster to evaluate than the equivalent algorithm:


int sum(int n) {
    int total = 0;
    for (int i = 0; i <= n; ++i) {
        total += i;
    }
    return total;
}

But would this loop rewrite be a worthwhile optimisation? The expression takes about 3.5ns to compute the sum of the first million natural numbers, whereas the loop takes 350µs, so we can conclude that C2 does not know this formula and prefers brute force. I would be aghast if time had been spent on optimisations like this: unless your application spends a lot of time adding up contiguous ranges of natural numbers, the marginal benefit is negligible. If this is what your application does most, you should do it yourself. The possibility of an optimisation doesn’t imply its viability: there needs to be a benefit when considering engineering effort, speed improvement, reliability and ubiquity. While this optimisation fails miserably on the grounds of ubiquity, there’s useful schoolboy maths that C2 does seem to know.

Associativity and Dependencies

Each x86 instruction has a throughput – the number of cycles it takes to complete – and a latency – the number of cycles it takes before the result is available to the next instruction in a chain. These numbers are produced by processor vendors, but there are independent numbers like these from Agner Fog, which also includes more detailed definitions of terms like latency. At first, the latency number feels a bit like a scam: what use is an advertised throughput if we can’t use the result immediately? This is where pipelining comes in: independent instructions can be interleaved. If a loop operation is associative and there are no dependencies between iterations, then it can be unrolled, which enables pipelining. If a loop operation is also commutative, then out of order execution is permitted. Evidence of an unrolled loop suggests that the compiler has realised that an operation is at least associative.

To see this in action it’s necessary to find an associative loop reduction that the compiler can’t vectorise. I took an example from the RoaringBitmap library – computing the cardinality of a bitmap container – which is a perfect example to capture this behaviour, because bit counts cannot be vectorised in Java.


  /**
   * Recomputes the cardinality of the bitmap.
   */
  protected void computeCardinality() {
    this.cardinality = 0;
    for (int k = 0; k < this.bitmap.length; k++) {
      this.cardinality += Long.bitCount(this.bitmap[k]);
    }
  }

we can see evidence of loop unrolling and out of order execution when looking at the assembly code emitted. The popcnt instructions are executed on the array out of order, and do not wait for the addition to the accumulator.

popcnt  r9,qword ptr [rbx+r13*8+10h]

movsxd  r8,r13d

popcnt  r10,qword ptr [rbx+r8*8+28h]

popcnt  r11,qword ptr [rbx+r8*8+18h]

popcnt  rdx,qword ptr [rbx+r8*8+20h]
 
movsxd  r8,r9d

add     r8,rbp

movsxd  r9,edx

To generate this assembly code you can run the project at github with the arguments

--include .*popcnt.* 
--print-assembly

The compiler does a very good job in this case: you can try unrolling the loop yourself, but you can only match performance if you guess the loop stride correctly. It’s impossible to prove a negative proposition, but it’s likely you’ll only make it worse if you try. C2 graduates with flying colours here: it definitely understands associativity and dependence.

The catch with pipelining is that an instruction must always wait for its operands. While the operation is associative, there is no way to reorder the code below.


    private int[] prefixSum(int[] data) {
        int[] result = new int[data.length];
        for (int i = 1; i < result.length; ++i) {
            result[i] = result[i - 1] + data[i];
        }
        return result;
    }

What happens with a prefix sum? There’s no unrolling: you can see the loop control statements have not been removed (look for commands like cmp ebx, inc ebx). The loop is also executed in order because it is sequentially dependent.

com/openkappa/simd/prefix/PrefixSum.impl([I)[I  [0x000001c21215bb20, 0x000001c21215bd78]  600 bytes
Argument 0 is unknown.RIP: 0x1c21215bb20 Code size: 0x00000258
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000001c2244379d0} 'impl' '([I)[I' in 'com/openkappa/simd/prefix/PrefixSum'
  0x000001c21215bb20: int3                      ;...cc

  0x000001c21215bb21: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c21215bb2c: nop                       ;...66
                                                ;...66
                                                ;...66
                                                ;...90

  0x000001c21215bb30: mov     dword ptr [rsp+0ffffffffffff9000h],eax
                                                ;...89
                                                ;...84
                                                ;...24
                                                ;...00
                                                ;...90
                                                ;...ff
                                                ;...ff

  0x000001c21215bb37: push    rbp               ;...55

  0x000001c21215bb38: sub     rsp,60h           ;...48
                                                ;...83
                                                ;...ec
                                                ;...60

  0x000001c21215bb3c: mov     rbp,qword ptr [rdx+10h]  ;...48
                                                ;...8b
                                                ;...6a
                                                ;...10

  0x000001c21215bb40: mov     r13,qword ptr [rdx+8h]  ;...4c
                                                ;...8b
                                                ;...6a
                                                ;...08

  0x000001c21215bb44: mov     ebx,dword ptr [rdx]  ;...8b
                                                ;...1a

  0x000001c21215bb46: mov     rcx,rdx           ;...48
                                                ;...8b
                                                ;...ca

  0x000001c21215bb49: mov     r10,51da8d20h     ;...49
                                                ;...ba
                                                ;...20
                                                ;...8d
                                                ;...da
                                                ;...51
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c21215bb53: call indirect r10         ;...41
                                                ;...ff
                                                ;...d2

  0x000001c21215bb56: test    rbp,rbp           ;...48
                                                ;...85
                                                ;...ed

  0x000001c21215bb59: je      1c21215bcb9h      ;...0f
                                                ;...84
                                                ;...5a
                                                ;...01
                                                ;...00
                                                ;...00

  0x000001c21215bb5f: mov     r10d,dword ptr [rbp+8h]  ;...44
                                                ;...8b
                                                ;...55
                                                ;...08

  0x000001c21215bb63: cmp     r10d,0f800016dh   ;...41
                                                ;...81
                                                ;...fa
                                                ;...6d
                                                ;...01
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array int})}
  0x000001c21215bb6a: jne     1c21215bd1dh      ;...0f
                                                ;...85
                                                ;...ad
                                                ;...01
                                                ;...00
                                                ;...00

  0x000001c21215bb70: mov     r8,rbp            ;...4c
                                                ;...8b
                                                ;...c5

  0x000001c21215bb73: mov     r10d,dword ptr [r13+8h]  ;...45
                                                ;...8b
                                                ;...55
                                                ;...08
                                                ; implicit exception: dispatches to 0x000001c21215bd41
  0x000001c21215bb77: cmp     r10d,0f800016dh   ;...41
                                                ;...81
                                                ;...fa
                                                ;...6d
                                                ;...01
                                                ;...00
                                                ;...f8
                                                ;   {metadata({type array int})}
  0x000001c21215bb7e: jne     1c21215bd1dh      ;...0f
                                                ;...85
                                                ;...99
                                                ;...01
                                                ;...00
                                                ;...00
                                                ;*iload_3 {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@7 (line 21)

  0x000001c21215bb84: mov     edi,dword ptr [r13+0ch]  ;...41
                                                ;...8b
                                                ;...7d
                                                ;...0c
                                                ;*arraylength {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@9 (line 21)

  0x000001c21215bb88: cmp     ebx,edi           ;...3b
                                                ;...df

  0x000001c21215bb8a: jnl     1c21215bcaah      ;...0f
                                                ;...8d
                                                ;...1a
                                                ;...01
                                                ;...00
                                                ;...00
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@10 (line 21)

  0x000001c21215bb90: mov     r11d,ebx          ;...44
                                                ;...8b
                                                ;...db

  0x000001c21215bb93: inc     r11d              ;...41
                                                ;...ff
                                                ;...c3

  0x000001c21215bb96: xor     r9d,r9d           ;...45
                                                ;...33
                                                ;...c9

  0x000001c21215bb99: mov     ecx,1h            ;...b9
                                                ;...01
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c21215bb9e: cmp     r11d,ecx          ;...44
                                                ;...3b
                                                ;...d9

  0x000001c21215bba1: cmovl   r11d,ecx          ;...44
                                                ;...0f
                                                ;...4c
                                                ;...d9

  0x000001c21215bba5: cmp     r11d,edi          ;...44
                                                ;...3b
                                                ;...df

  0x000001c21215bba8: cmovnle r11d,edi          ;...44
                                                ;...0f
                                                ;...4f
                                                ;...df

  0x000001c21215bbac: cmp     r11d,r9d          ;...45
                                                ;...3b
                                                ;...d9

  0x000001c21215bbaf: cmovl   r11d,r9d          ;...45
                                                ;...0f
                                                ;...4c
                                                ;...d9

  0x000001c21215bbb3: cmp     r11d,edi          ;...44
                                                ;...3b
                                                ;...df

  0x000001c21215bbb6: cmovnle r11d,edi          ;...44
                                                ;...0f
                                                ;...4f
                                                ;...df

  0x000001c21215bbba: nop                       ;...66
                                                ;...90
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bbbc: mov     ebp,ebx           ;...8b
                                                ;...eb

  0x000001c21215bbbe: dec     ebp               ;...ff
                                                ;...cd
                                                ;*isub {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@18 (line 22)

  0x000001c21215bbc0: cmp     ebp,edi           ;...3b
                                                ;...ef

  0x000001c21215bbc2: jnb     1c21215bcc1h      ;...0f
                                                ;...83
                                                ;...f9
                                                ;...00
                                                ;...00
                                                ;...00

  0x000001c21215bbc8: mov     r9d,dword ptr [r8+0ch]  ;...45
                                                ;...8b
                                                ;...48
                                                ;...0c
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@22 (line 22)
                                                ; implicit exception: dispatches to 0x000001c21215bd31
  0x000001c21215bbcc: mov     ebp,dword ptr [r13+rbx*4+0ch]
                                                ;...41
                                                ;...8b
                                                ;...6c
                                                ;...9d
                                                ;...0c
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@19 (line 22)

  0x000001c21215bbd1: cmp     ebx,r9d           ;...41
                                                ;...3b
                                                ;...d9

  0x000001c21215bbd4: jnb     1c21215bce1h      ;...0f
                                                ;...83
                                                ;...07
                                                ;...01
                                                ;...00
                                                ;...00

  0x000001c21215bbda: add     ebp,dword ptr [r8+rbx*4+10h]
                                                ;...41
                                                ;...03
                                                ;...6c
                                                ;...98
                                                ;...10
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bbdf: cmp     ebx,edi           ;...3b
                                                ;...df

  0x000001c21215bbe1: jnb     1c21215bd01h      ;...0f
                                                ;...83
                                                ;...1a
                                                ;...01
                                                ;...00
                                                ;...00

  0x000001c21215bbe7: mov     dword ptr [r13+rbx*4+10h],ebp
                                                ;...41
                                                ;...89
                                                ;...6c
                                                ;...9d
                                                ;...10
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bbec: inc     ebx               ;...ff
                                                ;...c3
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@25 (line 21)

  0x000001c21215bbee: cmp     ebx,r11d          ;...41
                                                ;...3b
                                                ;...db

  0x000001c21215bbf1: jl      1c21215bbbch      ;...7c
                                                ;...c9
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@10 (line 21)

  0x000001c21215bbf3: cmp     edi,r9d           ;...41
                                                ;...3b
                                                ;...f9

  0x000001c21215bbf6: mov     r11d,edi          ;...44
                                                ;...8b
                                                ;...df

  0x000001c21215bbf9: cmovnle r11d,r9d          ;...45
                                                ;...0f
                                                ;...4f
                                                ;...d9

  0x000001c21215bbfd: mov     r10d,r11d         ;...45
                                                ;...8b
                                                ;...d3

  0x000001c21215bc00: add     r10d,0fffffff9h   ;...41
                                                ;...83
                                                ;...c2
                                                ;...f9

  0x000001c21215bc04: mov     ecx,80000000h     ;...b9
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...80

  0x000001c21215bc09: cmp     r11d,r10d         ;...45
                                                ;...3b
                                                ;...da

  0x000001c21215bc0c: cmovl   r10d,ecx          ;...44
                                                ;...0f
                                                ;...4c
                                                ;...d1

  0x000001c21215bc10: cmp     ebx,r10d          ;...41
                                                ;...3b
                                                ;...da

  0x000001c21215bc13: jnl     1c21215bc80h      ;...7d
                                                ;...6b

  0x000001c21215bc15: nop     word ptr [rax+rax+0h]  ;...66
                                                ;...66
                                                ;...66
                                                ;...0f
                                                ;...1f
                                                ;...84
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;...00
                                                ;*isub {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@18 (line 22)

  0x000001c21215bc20: mov     ecx,dword ptr [r8+rbx*4+10h]
                                                ;...41
                                                ;...8b
                                                ;...4c
                                                ;...98
                                                ;...10

  0x000001c21215bc25: add     ecx,dword ptr [r13+rbx*4+0ch]
                                                ;...41
                                                ;...03
                                                ;...4c
                                                ;...9d
                                                ;...0c
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc2a: mov     dword ptr [r13+rbx*4+10h],ecx
                                                ;...41
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...10
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc2f: movsxd  r11,ebx           ;...4c
                                                ;...63
                                                ;...db

  0x000001c21215bc32: add     ecx,dword ptr [r8+r11*4+14h]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...14
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc37: mov     dword ptr [r13+r11*4+14h],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...14
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc3c: add     ecx,dword ptr [r8+r11*4+18h]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...18
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc41: mov     dword ptr [r13+r11*4+18h],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...18
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc46: add     ecx,dword ptr [r8+r11*4+1ch]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...1c
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc4b: mov     dword ptr [r13+r11*4+1ch],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...1c
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc50: add     ecx,dword ptr [r8+r11*4+20h]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...20
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc55: mov     dword ptr [r13+r11*4+20h],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...20
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc5a: add     ecx,dword ptr [r8+r11*4+24h]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...24
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc5f: mov     dword ptr [r13+r11*4+24h],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...24
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc64: add     ecx,dword ptr [r8+r11*4+28h]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...28
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc69: mov     dword ptr [r13+r11*4+28h],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...28

  0x000001c21215bc6e: add     ecx,dword ptr [r8+r11*4+2ch]
                                                ;...43
                                                ;...03
                                                ;...4c
                                                ;...98
                                                ;...2c

  0x000001c21215bc73: mov     dword ptr [r13+r11*4+2ch],ecx
                                                ;...43
                                                ;...89
                                                ;...4c
                                                ;...9d
                                                ;...2c
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc78: add     ebx,8h            ;...83
                                                ;...c3
                                                ;...08
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@25 (line 21)

  0x000001c21215bc7b: cmp     ebx,r10d          ;...41
                                                ;...3b
                                                ;...da

  0x000001c21215bc7e: jl      1c21215bc20h      ;...7c
                                                ;...a0
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@10 (line 21)

  0x000001c21215bc80: cmp     ebx,edi           ;...3b
                                                ;...df

  0x000001c21215bc82: jnl     1c21215bcaah      ;...7d
                                                ;...26
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bc84: mov     ebp,ebx           ;...8b
                                                ;...eb

  0x000001c21215bc86: dec     ebp               ;...ff
                                                ;...cd
                                                ;*isub {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@18 (line 22)

  0x000001c21215bc88: cmp     ebp,edi           ;...3b
                                                ;...ef

  0x000001c21215bc8a: jnb     1c21215bcc1h      ;...73
                                                ;...35

  0x000001c21215bc8c: mov     ebp,dword ptr [r13+rbx*4+0ch]
                                                ;...41
                                                ;...8b
                                                ;...6c
                                                ;...9d
                                                ;...0c
                                                ;*iaload {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@19 (line 22)

  0x000001c21215bc91: cmp     ebx,r9d           ;...41
                                                ;...3b
                                                ;...d9

  0x000001c21215bc94: jnb     1c21215bce1h      ;...73
                                                ;...4b

  0x000001c21215bc96: add     ebp,dword ptr [r8+rbx*4+10h]
                                                ;...41
                                                ;...03
                                                ;...6c
                                                ;...98
                                                ;...10
                                                ;*iadd {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@23 (line 22)

  0x000001c21215bc9b: cmp     ebx,edi           ;...3b
                                                ;...df

  0x000001c21215bc9d: jnb     1c21215bd01h      ;...73
                                                ;...62

  0x000001c21215bc9f: mov     dword ptr [r13+rbx*4+10h],ebp
                                                ;...41
                                                ;...89
                                                ;...6c
                                                ;...9d
                                                ;...10
                                                ;*iastore {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@24 (line 22)

  0x000001c21215bca4: inc     ebx               ;...ff
                                                ;...c3
                                                ;*iinc {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@25 (line 21)

  0x000001c21215bca6: cmp     ebx,edi           ;...3b
                                                ;...df

  0x000001c21215bca8: jl      1c21215bc84h      ;...7c
                                                ;...da
                                                ;*if_icmpge {reexecute=0 rethrow=0 return_oop=0}
                                                ; - com.openkappa.simd.prefix.PrefixSum::impl@10 (line 21)

  0x000001c21215bcaa: mov     rax,r13           ;...49
                                                ;...8b
                                                ;...c5

  0x000001c21215bcad: add     rsp,60h           ;...48
                                                ;...83
                                                ;...c4
                                                ;...60

  0x000001c21215bcb1: pop     rbp               ;...5d

  0x000001c21215bcb2: test    dword ptr [1c27b720000h],eax
                                                ;...85
                                                ;...05
                                                ;...48
                                                ;...43
                                                ;...5c
                                                ;...69
                                                ;   {poll_return}
  0x000001c21215bcb8: ret                       ;...c3

Does this harm performance? add takes 0.33 cycles, whereas popcnt takes 1 cycle per instruction. Shouldn’t a prefix sum be faster to calculate than a population count, on the same length of array and same width of integer? They can be compared head to head (implementing prefix sum for long[] to keep word width constant)

--include .*prefix.PrefixSum.PrefixSumLong|.*popcnt.PopCount.PopCount$

Far from having 3x throughput, the prefix sum is much worse. This is entirely because there is no loop unrolling and no pipelining. When possible, C2 applies aggressive unrolling optimisations unavailable to the programmer. For vectorisable operations (requiring linear independence and countability), loop unrolling further marks the loop as a candidate for auto-vectorisation.

Benchmark Mode Threads Samples Score Score Error (99.9%) Unit Param: size
PopCount thrpt 1 10 9.174499 0.394487 ops/ms 100000
PopCount thrpt 1 10 1.217521 0.513734 ops/ms 1000000
PrefixSumLong thrpt 1 10 6.807279 0.925282 ops/ms 100000
PrefixSumLong thrpt 1 10 0.443974 0.053544 ops/ms 1000000

If the dependencies need to fetch data from RAM the latency can be much higher than loading from registers or from prefetched cache. Even when fetching from RAM, the worst case scenario, during this delay independent instructions can complete, unless they have a false dependency.

Targeting SIMD in Java

Vectorised instruction execution can be targeted directly in C++ but with Java there are extra layers of abstraction to go through. Folklore aside, when does vectorisation or SIMD execution actually happen in Java? Skeptical of old wives’ tales, I investigate when SIMD instructions are actually used in Java 9, and how to disable it by programming badly.

Building a Benchmark Harness

I use JMH to write benchmarks. For the uninitiated, it is the standard Java micro-benchmarking framework and handles various pitfalls, the most salient of which being that it ensures that your code actually executes, and ensures measurement is performed against a monotonic measure of time. Benchmarks produced without JMH are unlikely to be correct and should arouse suspicion, especially if used during a sales process.

Averages always lie, so minimisation of 99.9th percentile execution time is a better objective to have in mind. As a general performance indicator I measure throughput in operations per time unit, which is useful to correlate with JVM compilation events.

To tune performance, before even worrying about achieving SIMD execution, we need to be aware of recompilation and failures to inline. These features are enabled by the arguments below and my simple harness has a specific mode to support these diagnostics:

-XX:+PrintCompilation 
-XX:+UnlockDiagnosticVMOptions 
-XX:+PrintInlining

The proof that code is actually being vectorised is to observe the emission of AVX instructions. To prove this has happened (and if it does, it will be correlated with astonishing performance statistics), we need to see the assembly code so I run the benchmark in a mode that will print out the generated assembly via the arguments:

-XX:+UnlockDiagnosticVMOptions
-XX:+PrintAssembly
-XX:PrintAssemblyOptions=hsdis-print-bytes 
-XX:CompileCommand=print

However, SIMD execution only happens when SuperWord parallelism is enabled (and by default, it is) so we won’t even need to look at the assembly unless we see a clear difference when running the benchmark without the UseSuperWord option:

-XX:-UseSuperWord

What Gains Can Be Expected?

Is vectorised code execution a panacea? Assuming we can force the JVM to use SIMD, how much performance can be expected? It turns out that java.util.Arrays.fill can be vectorised, so we can get a taste of the difference it makes. We can observe its impact by benchmarking throughput with and without SuperWord instruction level parallelism.


    private void benchmark(String... jvmArgs) throws RunnerException {
            Options opt = new OptionsBuilder()
                    .include(this.getClass().getName() + ",*")
                    .mode(Mode.Throughput)
                    .timeUnit(TimeUnit.MILLISECONDS)
                    .warmupIterations(5)
                    .measurementIterations(5)
                    .forks(1)
                    .shouldFailOnError(true)
                    .shouldDoGC(true)
                    .operationsPerInvocation(1_000_000)
                    .jvmArgs(jvmArgs)
                    .build();
            new Runner(opt).run();
    }

    @Benchmark
    public void fillArray(Blackhole bh)  {
        double[] array = new double[1 << 10];
        for(int i = 0; i << 1_000_000; ++i) {
            Arrays.fill(array, i);
            bh.consume(array);
        }
    }

# VM version: JDK 9-ea, VM 9-ea+166
...
# VM options: -XX:-UseSuperWord
...

Benchmark                 Mode  Cnt    Score     Error   Units
TestBenchmark.fillArray  thrpt    5  966.947 ± 596.705  ops/ms

# VM version: JDK 9-ea, VM 9-ea+166
...
# VM options: -XX:+UseSuperWord
...

Benchmark                 Mode  Cnt     Score      Error   Units
TestBenchmark.fillArray  thrpt    5  4230.802 ± 5311.001  ops/ms

The difference in throughput is palpable and astonishing.

Intrinsics

Various intrinsics, such as Arrays.fill above, compile down to vectorised instructions. When SuperWord parallelism is enabled, they will always run faster. The JIT compiler will also target simple hand-written code, but intrinsics are a safer bet.

Adding Arrays Together

Addition of arrays will either use SIMD or not; it depends how you go about writing your code. If your code is too complicated then you will not achieve vectorised execution. I will start from a method which does not vectorise, transform it to one that does by a process of simplification, and then break it again by trying to be too clever. The code which does vectorise is the same naive code I would have written in C++ as a student, ignorant of JVM internals. All of the code is available at github.

To start off with I created a highly contrived class called BadCode which is actually inspired, albeit seriously exacerbated, by a generic function in an API I have seen in a professional setting. The so called object oriented (sic) API seeks to be able to operate on any type of primitive array, so takes the lowest common denominator (java.lang.Object) as parameters and performs instanceof checks to get the correctly typed array instance. While the code is bloated, this provides as much flexibility as possible, which suits the supplier of the API – which has many clients with disparate use cases – but not necessarily the performance constrained caller.

The code is too bloated to include here but can be seen on github. It has two major performance bugs which will be addressed in turn:

  1. It’s verbose enough not to inline
  2. It has more than one exit point

Because the method supports so many use cases, the code size is very large (2765 bytes). By default, any method with a code size of greater than 2000 bytes will fail to inline. Inlining is at the very base of our hierarchy of performance needs. We can see that the JIT compiler has failed to inline the method by printing inlining and compilation:

   2193  715 %     4       com.openkappa.simd.generated.TestBenchmark_badClass_jmhTest::badClass_thrpt_jmhStub @ 13 (55 bytes)
                              @ 19   com.openkappa.simd.TestBenchmark::badClass (9 bytes)   force inline by CompileCommand
                                @ 2   com.openkappa.simd.TestBenchmark$BadClassState::compute (16 bytes)   inline (hot)
                                  @ 12   com.openkappa.simd.BadCode::bigMethod (2765 bytes)   hot method too big

Taking a look at our throughput, we can see there is a problem. The code isn’t getting any faster, so clearly no optimisations are being applied.
# Run progress: 0.00% complete, ETA 00:00:40
# Fork: 1 of 1
# Warmup Iteration   1: 0.193 ops/us
# Warmup Iteration   2: 0.176 ops/us
# Warmup Iteration   3: 0.216 ops/us
# Warmup Iteration   4: 0.183 ops/us
# Warmup Iteration   5: 0.294 ops/us
Iteration   1: 0.260 ops/us
Iteration   2: 0.224 ops/us
Iteration   3: 0.170 ops/us
Iteration   4: 0.169 ops/us
Iteration   5: 0.169 ops/us

Our three nines is terrible, taking up to six microseconds to add two arrays:
TestBenchmark.badClass:badClass·p0.999         sample       6.296           us/op

Regardless of the large code size, the approach taken in the API has enforced multiple exit points in the method, which will always disable SIMD execution. Running with SuperWord disabled does not worsen performance, implying our code is not getting vectorised.

Smaller Code

Having noticed that the method is not getting inlined, let alone compiling to AVX instructions, we need to make the code smaller first. In this scenario our values are always double[] so the API provider effectively forces us to pay for the disparate use cases they must support, and this taxation without representation harms performance. We can rewrite it to be smaller, targeting our own specific use case. The code is concise enough to include here, and is the code any student would write to perform element-wise addition of two arrays. Notice the loop condition.


public class SmallerCode {

    public double[] smallMethod(double[] left, double[] right) {
        double[] result = new double[left.length];
        for(int i = 0; i < left.length && i < right.length; ++i) {
            result[i] = left[i] + right[i];
        }
        return result;
    }
}

Let’s benchmark SmallerCode, where the same code has a size of 43B. The method is indeed inlined.

   1374  647       3       com.openkappa.simd.TestBenchmark$SmallerCodeState::compute (16 bytes)   made not entrant
                              @ 12   com.openkappa.simd.SmallerCode::smallMethod (43 bytes)   inline (hot)

Throughput is doubled and we see evidence of dynamic optimisation.
# Run progress: 25.00% complete, ETA 00:02:42
# Fork: 1 of 1
# Warmup Iteration   1: 0.372 ops/us
# Warmup Iteration   2: 0.340 ops/us
# Warmup Iteration   3: 0.432 ops/us
# Warmup Iteration   4: 0.497 ops/us
# Warmup Iteration   5: 0.499 ops/us
Iteration   1: 0.398 ops/us
Iteration   2: 0.364 ops/us
Iteration   3: 0.408 ops/us
Iteration   4: 0.544 ops/us
Iteration   5: 0.401 ops/us

This code is twice as fast, and our three nines is better, just by virtue of keeping the code simple.
TestBenchmark.smallerCode:smallerCode·p0.999             sample       2.164          us/op

But are we getting SIMD execution? Possibly – disabling SuperWord yields noticeably worse results.
# Run progress: 25.00% complete, ETA 00:02:22
# Fork: 1 of 1
# Warmup Iteration   1: 0.261 ops/us
# Warmup Iteration   2: 0.343 ops/us
# Warmup Iteration   3: 0.294 ops/us
# Warmup Iteration   4: 0.320 ops/us
# Warmup Iteration   5: 0.316 ops/us
Iteration   1: 0.293 ops/us
Iteration   2: 0.276 ops/us
Iteration   3: 0.304 ops/us
Iteration   4: 0.291 ops/us
Iteration   5: 0.279 ops/us

It’s worth inspecting the assembly to see if we can observe the emission of AVX instructions once we reenable UseSuperWord. Assembly is easier to read if inlining is disabled, this can be controlled in JMH with this annotation: @CompilerControl(CompilerControl.Mode.DONT_INLINE). Applying the annotation, the assembly is printed using the appropriate JVM args:
-XX:+UnlockDiagnosticVMOptions 
-XX:+PrintAssembly
-XX:PrintAssemblyOptions=hsdis-print-bytes 
-XX:CompileCommand=print

0x00000154edb691e0: vmovdqu ymm0,ymmword ptr [rbp+r10*8+10h]

0x00000154edb691e7: vaddpd  ymm0,ymm0,ymmword ptr [rdx+r10*8+10h]

0x00000154edb691ee: vmovdqu ymmword ptr [r8+r10*8+10h],ymm0

0x00000154edb691f5: add     r10d,4h           

0x00000154edb691f9: cmp     r10d,ebx          

0x00000154edb691fc: jl      154edb691e0h      

It’s true – this code is indeed vectorised – see the AVX instructions in bold!

Ruining It

Having witnessed vectorisation when adding arrays together, let’s try and break it. There are a few patterns we can apply to break our vectorised code:

  • Putting an OR condition as the loop condition
  • Putting a non-inlined method inside the loop
  • Putting an arbitrary method as the loop condition
  • Manually unrolling the loop
  • Using a long as the loop variable
  • Multiple exit points

The list goes on but now let’s really fuck it up. We were using double[] so let’s see what happens if we use a DirectByteBuffer as the backing for a homegrown vector construct instead. Instead of returning a new heap allocated array, we will write our doubles into a byte buffer, and use an offset and length to delineate the arrays. For instance, the code below will write the sum of two arrays stored in a byte buffer back into the same byte buffer. We can abstract vectors by creating small on-heap objects for each array which know the offset and length of each array in the buffer.


public int add(ByteBuffer byteBuffer,
               int leftOffset, int leftLength,
               int rightOffset, int rightLength,
               int resultOffset) {
        int resultIndex = resultOffset;
        for(int l = leftOffset, r = rightOffset;
            l < leftOffset + leftLength && r < rightOffset + rightLength;
            l += 8, r += 8, resultIndex += 8) {
            byteBuffer.putDouble(resultIndex, byteBuffer.getDouble(l) + byteBuffer.getDouble(r));
        }
        return resultIndex;
    }

Is this clever? We’ve beaten the garbage collector. It certainly feels like a clever engineering story. No, performance wise, we are back to where we were with the remarkably convoluted and conflated catch all function. Entertainingly, had we only ever benchmarked against BadCode::bigMethod we may not have noticed this performance regression.

# Run progress: 0.00% complete, ETA 00:00:40
# Fork: 1 of 1
# Warmup Iteration   1: 0.156 ops/us
# Warmup Iteration   2: 0.160 ops/us
# Warmup Iteration   3: 0.198 ops/us
# Warmup Iteration   4: 0.190 ops/us
# Warmup Iteration   5: 0.272 ops/us
Iteration   1: 0.220 ops/us
Iteration   2: 0.242 ops/us
Iteration   3: 0.216 ops/us
Iteration   4: 0.248 ops/us
Iteration   5: 0.351 ops/us

TestBenchmark.byteBuffer:byteBuffer·p0.999     sample       6.552           us/op

The obvious indicator that this is not being vectorised is that performance does not degrade when setting
-XX:-UseSuperWord

And to be sure we can inspect the assembly code emitted (without disabling UseSuperWord!).
  0x000001869216cb67: mov     edx,ecx

  0x000001869216cb69: add     edx,r9d

  0x000001869216cb6c: cmp     ecx,edx

  0x000001869216cb6e: jnl     1869216cb1dh

  0x000001869216cb70: mov     r13d,dword ptr [r12+r11*8+8h]
                                                
  0x000001869216cb75: cmp     r13d,0f8007ed8h
                                      
  0x000001869216cb7c: jne     1869216d015h

  0x000001869216cb82: lea     r13,[r12+r11*8]

  0x000001869216cb86: movzx   eax,byte ptr [r13+29h]

  0x000001869216cb8b: test    eax,eax

  0x000001869216cb8d: je      1869216d015h    

The reality is that whenever sun.misc.Unsafe is used, directly or indirectly, we lose access to SIMD. The bottom line is if you want to exploit instruction level parallelism, then be prepared to write code even a beginner could understand instantly. Bizarre off-heap data structures and vectorised execution? Unlikely.

TCP Congestion Control and Spark Back Pressure

Bandwidth in the Internet is a rivalrous resource; consumption by any consumer grants utility and inhibits consumption by other consumers. Unless consumers sometimes relent in their pursuit of bandwidth, buffers on routers would spend most of their time discarding of excess packets making point-to-point connections unsustainable. Stopping the Internet from collapsing requires a distributed algorithm along the lines of the old adage “do as you would be done by”. Such algorithms have existed for decades, are well understood, and have some interesting properties that can be applied to throughput problems in application development.

Congestion Control

In 1986 the throughput on the campus network at UC Berkeley, consisting of three links, fell from 32Kbps to 40bps without explanation. Van Jacobson realised that this was caused by buffer overload at routers, leading to an excessive fraction of network packets being dropped, preventing establishment and sustenance of TCP connections. In order to optimise aggregate bandwidth, utilisation should be controlled at a level where packet loss at routers is minimised. One solution to the problem would be to grant all bandwidth to a single consumer – with obvious drawbacks – any allocation should be fair and stable.  A centralised mediator, such as a government, is computationally infeasible so the algorithm must be decentralised.

Jacobson’s Algorithm

Van Jacobson devised an algorithm in TCP clients which use packet loss (manifested in corruption or timeouts) as a congestion indicator. Each client maintains a congestion window which limits the number of unacknowledged packets at any point in time. When congestion is detected, the client backs off. The algorithm splits the lifecycle of a  TCP connection into two phases: Slow Start and Congestion Avoidance.

  1. Slow Start occurs when a connection is created or after a packet times out:
    1. Initialise the congestion window (cwnd) to a number of packets called the maximum segment size (MSS).
    2. For each acknowledged packet, increase cwnd by one until the slow start threshold (ssthresh) is reached or a packet is lost. This is more or less exponential increase (and favours short connections).
    3. When a loss event occurs, set ssthresh to half its current value and resume slow start
  2. Congestion avoidance starts when the slow start threshold is reached.
    1. Every time cwnd packets are acknowledged, add the MSS to cwnd. This is linear increase.
    2. When a loss event occurs, set ssthresh to half its current value, halve cwnd and resume linear increase.

The algorithm aims to spend as much time as possible in congestion avoidance to maintain stability, and aims to find a fair value of the slow start threshold with respect to all consumers. The time series of cwnd during a TCP connection makes a saw tooth after an initial exponential increase.

This algorithm prevents congestions collapse and can be shown to be stable at an aggregate level. However there are some issues with it. For instance, the algorithm favours short connections (those with short round trip times) both during slow start and congestion avoidance. Given the choice of a short oversubscribed route and a long undersubscribed route, the algorithm will choose the short oversubscribed route. Particularly, the linear increase during congestion avoidance is too slow and means that too much time is spent away from the optimal bandwidth.

Since Jacobson’s algorithm was devised, many variations on its theme have been proposed and some implemented, all aiming to maximise the time spent at a pareto-optimal per connection bandwidth. For instance, the BIC (Binary Increase Congestion) algorithm, which replaces the linear CA phase with a binary search. CUBIC, which replaces the linear phase with a cubic function (the inflection point set at the level of the cwnd at the last congestion), event was the default algorithm in the Linux kernel from 2.6.19. CUBIC was replaced as the default by Proportional Rate Reduction, devised by Google, which does not wait for the acknowledgement of outstanding packet before retransmission, from 3.2 onwards.

400px-bic_cubic_growth_functions

Spark Back-Pressure

When Spark back pressure is enabled and a queue of micro-batches builds up, Spark will automatically resize the batch to make it smaller. The upstream system can either block or hold onto the unconsumed messages for a bit longer. When the backlog has cleared, Spark starts increasing the batch size. I haven’t yet figured out whether Spark is explicitly optimising for minimal queue length, minimal queued bytes, maximal throughput or minimal latency but the act of varying the batch size is a search for an optimum.

Though the feature works well, decreases are often more aggressive than necessary and increases slower than feasible. Sometimes queues build up for intrinsic reasons; the job is too slow to service the batch size at the desired polling frequency, but sometimes the build up is caused extrinsically, for instance by temporary cluster overload. If the back-pressure is too aggressive and the cause extrinsic, then unless the algorithm aggressively probes recovery rate will be delayed.  It would be interesting to vary the batch sizing algorithm along the lines of variations on Jacobson’s algorithm, like replacing linear increase with binary recovery/probing, and assess the optimality (choose one or many of maximise throughput/minimise latency/minimise risk of OOM) and stability (for what proportion of time does the batch size stay at the optimal level?)