String search anomaly (https://github.com/si14/java-string-search-bench)

bench_anomaly.md

The code (full version here):

// ...
        unsortedArray = new String[arraySize];
        System.arraycopy(allStrings, 0, unsortedArray, 0, arraySize);
        toSearchIdx = arraySize / 2;

// ...

    private int linearSearchInterned(String s) {
        for (int i = 0; i < unsortedArray.length; i++) {
            if (unsortedArray[i] == s) {
                return i;
            }
        }
        return -1;
    }

Part of the benchmark results:

i.g.s.s.InternedBench.benchInterned                   1   avgt        20        2.274        0.024    ns/op
i.g.s.s.InternedBench.benchInterned                   2   avgt        20        3.552        0.207    ns/op
i.g.s.s.InternedBench.benchInterned                   3   avgt        20        3.336        0.122    ns/op
i.g.s.s.InternedBench.benchInterned                   5   avgt        20        4.113        0.192    ns/op
i.g.s.s.InternedBench.benchInterned                   8   avgt        20       13.902        1.605    ns/op     // WAT
i.g.s.s.InternedBench.benchInterned                  13   avgt        20        7.404        0.483    ns/op     // WAT
i.g.s.s.InternedBench.benchInterned                  21   avgt        20        8.995        0.154    ns/op     
i.g.s.s.InternedBench.benchInterned                  33   avgt        20       11.811        0.025    ns/op