Почему instanceof и повторение одного списка быстрее, чем нескольких специализированных списков?

Question

Я предполагал, что разделение объектов, которые реализуют различные интерфейсы, в несколько списков и последующая итерация этих списков будет быстрее, чем выгрузка всех объектов в один список с последующим переключением через instanceof. Например. это:

ArrayList<Visible> visibles = new ArrayList<>();
ArrayList<Highlightable> highlightables = new ArrayList<>();
ArrayList<Selectable> selectables = new ArrayList<>();

// populate the lists
// Visible is an interface, Highlightable is also interface (extends Visible),
// Selectable extends Highlightable
// All interfaces have 3 concrete subclasses each,
// to test situations when JVM is not able to optimize too much due to small number of classes

for (Visible e : visibles) {
    vsum += e.visibleValue();
}
for (Highlightable e : highlightables) {
    vsum += e.visibleValue();
    hsum += e.highlightableValue();
}
for (Selectable e : selectables) {
    vsum += e.visibleValue();
    hsum += e.highlightableValue();
    ssum += e.selectableValue();
}

должно быть быстрее, чем

ArrayList<Visible> visibles = new ArrayList<>();

// populate the list

for (Visible e : visibles) {
    if (e instanceof Selectable) {
        vsum += e.visibleValue();
        hsum += ((Selectable) e).highlightableValue();
        ssum += ((Selectable) e).selectableValue();
    } else if (e instanceof Highlightable) {
        vsum += e.visibleValue();
        hsum += ((Highlightable) e).highlightableValue();
    } else {
        vsum += e.visibleValue();
    }
}

Однако, похоже, это не так:

Main.separateLists             thrpt   30     1546.898 ±     32.312   ops/s
Main.singleListAndInstanceof   thrpt   30     1673.733 ±     29.804   ops/s

Я добавил полный исходный код для теста ниже.

Что может быть причиной ускорения версии instanceof? Даже если мы предположим, что инструкция isntanceof бесплатна, то обе версии должны как минимум быть одинаковыми по производительности (поскольку они по-прежнему добавляют элементы в список и повторяют их).

package test;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Warmup;

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }

    @Benchmark
    @Warmup(iterations = 5, time = 1)
    @Measurement(iterations = 15, time = 1)
    @Fork(value = 2)
    public static long separateLists() {
        ArrayList<Visible> visibles = new ArrayList<>(3_500);
        ArrayList<Highlightable> highlightables = new ArrayList<>(3_500);
        ArrayList<Selectable> selectables = new ArrayList<>(3_500);

        Random random = new Random();
        for (int i = 0; i < 10_000; i++) {
            switch (random.nextInt(9)) {
                case 0:
                    visibles.add(new Visible1(i));
                    break;
                case 1:
                    highlightables.add(new Highlightable1(i));
                    break;
                case 2:
                    selectables.add(new Selectable1(i));
                    break;

                case 3:
                    visibles.add(new Visible2(i));
                    break;
                case 4:
                    highlightables.add(new Highlightable2(i));
                    break;
                case 5:
                    selectables.add(new Selectable2(i));
                    break;

                case 6:
                    visibles.add(new Visible3(i));
                    break;
                case 7:
                    highlightables.add(new Highlightable3(i));
                    break;
                case 8:
                    selectables.add(new Selectable3(i));
                    break;
            }
        }

        long listSize = visibles.size() + highlightables.size() + selectables.size();

        long vsum = 0;
        long hsum = 0;
        long ssum = 0;
        for (Visible e : visibles) {
            vsum += e.visibleValue();
        }
        for (Highlightable e : highlightables) {
            vsum += e.visibleValue();
            hsum += e.highlightableValue();
        }
        for (Selectable e : selectables) {
            vsum += e.visibleValue();
            hsum += e.highlightableValue();
            ssum += e.selectableValue();
        }

        return listSize + vsum * hsum * ssum;
    }

    @Benchmark
    @Warmup(iterations = 5, time = 1)
    @Measurement(iterations = 15, time = 1)
    @Fork(value = 2)
    public static long singleListAndInstanceof() {
        ArrayList<Visible> visibles = new ArrayList<>(10_000);

        Random random = new Random();
        for (int i = 0; i < 10_000; i++) {
            switch (random.nextInt(9)) {
                case 0:
                    visibles.add(new Visible1(i));
                    break;
                case 1:
                    visibles.add(new Highlightable1(i));
                    break;
                case 2:
                    visibles.add(new Selectable1(i));
                    break;

                case 3:
                    visibles.add(new Visible2(i));
                    break;
                case 4:
                    visibles.add(new Highlightable2(i));
                    break;
                case 5:
                    visibles.add(new Selectable2(i));
                    break;

                case 6:
                    visibles.add(new Visible3(i));
                    break;
                case 7:
                    visibles.add(new Highlightable3(i));
                    break;
                case 8:
                    visibles.add(new Selectable3(i));
                    break;
            }
        }

        long listSize = visibles.size();

        long vsum = 0;
        long hsum = 0;
        long ssum = 0;
        for (Visible e : visibles) {
            if (e instanceof Selectable) {
                vsum += e.visibleValue();
                hsum += ((Selectable) e).highlightableValue();
                ssum += ((Selectable) e).selectableValue();
            } else if (e instanceof Highlightable) {
                vsum += e.visibleValue();
                hsum += ((Highlightable) e).highlightableValue();
            } else {
                vsum += e.visibleValue();
            }
        }

        return listSize + vsum * hsum * ssum;
    }
}

abstract class Visible {
    abstract int visibleValue();
}
abstract class Highlightable extends Visible {
    abstract int highlightableValue();
}
abstract class Selectable extends Highlightable {
    abstract int selectableValue();
}

class Visible1 extends Visible {
    private int v;
    Visible1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v; }
}
class Highlightable1 extends Highlightable {
    private int v;
    Highlightable1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*2; }
    @Override int highlightableValue() { return v*3; }
}
class Selectable1 extends Selectable {
    private int v;
    Selectable1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*4; }
    @Override int highlightableValue() { return v*5; }
    @Override int selectableValue() { return v*6; }
}

class Visible2 extends Visible {
    private int v;
    Visible2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*7; }
}
class Highlightable2 extends Highlightable {
    private int v;
    Highlightable2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*8; }
    @Override int highlightableValue() { return v*9; }
}
class Selectable2 extends Selectable {
    private int v;
    Selectable2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*10; }
    @Override int highlightableValue() { return v*11; }
    @Override int selectableValue() { return v*12; }
}


class Visible3 extends Visible {
    private int v;
    Visible3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*13; }
}
class Highlightable3 extends Highlightable {
    private int v;
    Highlightable3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*14; }
    @Override int highlightableValue() { return v*15; }
}
class Selectable3 extends Selectable {
    private int v;
    Selectable3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*16; }
    @Override int highlightableValue() { return v*17; }
    @Override int selectableValue() { return v*18; }
}

Результат теста:

Main.separateLists                                             thrpt  600     1690.522 ±    6.570   ops/s
Main.singleListAndInstanceof                                   thrpt  600     1751.375 ±    4.368   ops/s
Main.separateLists:L1-dcache-load-misses:u                     thrpt    2     2298.258               #/op
Main.singleListAndInstanceof:L1-dcache-load-misses:u           thrpt    2      627.451               #/op
Main.separateLists:L1-dcache-loads:u                           thrpt    2  1217756.290               #/op
Main.singleListAndInstanceof:L1-dcache-loads:u                 thrpt    2  1135982.650               #/op
Main.separateLists:L1-icache-load-misses:u                     thrpt    2      113.599               #/op
Main.singleListAndInstanceof:L1-icache-load-misses:u           thrpt    2       99.896               #/op
Main.separateLists:L1-icache-loads:u                           thrpt    2   656048.382               #/op
Main.singleListAndInstanceof:L1-icache-loads:u                 thrpt    2   694074.004               #/op
Main.separateLists:LLC-load-misses:u                           thrpt    2      872.681               #/op
Main.singleListAndInstanceof:LLC-load-misses:u                 thrpt    2      355.666               #/op
Main.separateLists:LLC-loads:u                                 thrpt    2    12036.496               #/op
Main.singleListAndInstanceof:LLC-loads:u                       thrpt    2     7445.434               #/op
Main.separateLists:LLC-stores:u                                thrpt    2    15277.223               #/op
Main.singleListAndInstanceof:LLC-stores:u                      thrpt    2    10649.517               #/op
Main.separateLists:branch-misses:u                             thrpt    2    22463.763               #/op
Main.singleListAndInstanceof:branch-misses:u                   thrpt    2    29940.958               #/op
Main.separateLists:branches:u                                  thrpt    2   254018.586               #/op
Main.singleListAndInstanceof:branches:u                        thrpt    2   275450.951               #/op
Main.separateLists:cycles:u                                    thrpt    2  1988517.839               #/op
Main.singleListAndInstanceof:cycles:u                          thrpt    2  1921584.057               #/op
Main.separateLists:dTLB-load-misses:u                          thrpt    2       66.212               #/op
Main.singleListAndInstanceof:dTLB-load-misses:u                thrpt    2       64.442               #/op
Main.separateLists:dTLB-loads:u                                thrpt    2  1217929.340               #/op
Main.singleListAndInstanceof:dTLB-loads:u                      thrpt    2  1135799.981               #/op
Main.separateLists:iTLB-load-misses:u                          thrpt    2        4.179               #/op
Main.singleListAndInstanceof:iTLB-load-misses:u                thrpt    2        3.876               #/op
Main.separateLists:iTLB-loads:u                                thrpt    2   656595.175               #/op
Main.singleListAndInstanceof:iTLB-loads:u                      thrpt    2   693913.010               #/op
Main.separateLists:instructions:u                              thrpt    2  2273646.245               #/op
Main.singleListAndInstanceof:instructions:u                    thrpt    2  2045332.939               #/op
Main.separateLists:stalled-cycles-backend:u                    thrpt    2   773671.154               #/op
Main.singleListAndInstanceof:stalled-cycles-backend:u          thrpt    2   619477.824               #/op
Main.separateLists:stalled-cycles-frontend:u                   thrpt    2   184604.485               #/op
Main.singleListAndInstanceof:stalled-cycles-frontend:u         thrpt    2   271938.450               #/op
Main.separateLists:·gc.alloc.rate                              thrpt  600      217.266 ±    0.846  MB/sec
Main.singleListAndInstanceof:·gc.alloc.rate                    thrpt  600      222.747 ±    0.556  MB/sec
Main.separateLists:·gc.alloc.rate.norm                         thrpt  600   202181.035 ±    2.986    B/op
Main.singleListAndInstanceof:·gc.alloc.rate.norm               thrpt  600   200083.395 ±    4.720    B/op
Main.separateLists:·gc.churn.PS_Eden_Space                     thrpt  600      217.792 ±    3.841  MB/sec
Main.singleListAndInstanceof:·gc.churn.PS_Eden_Space           thrpt  600      223.528 ±    4.973  MB/sec
Main.separateLists:·gc.churn.PS_Eden_Space.norm                thrpt  600   202704.197 ± 3508.997    B/op
Main.singleListAndInstanceof:·gc.churn.PS_Eden_Space.norm      thrpt  600   200804.794 ± 4414.457    B/op
Main.separateLists:·gc.churn.PS_Survivor_Space                 thrpt  600        0.095 ±    0.008  MB/sec
Main.singleListAndInstanceof:·gc.churn.PS_Survivor_Space       thrpt  600        0.091 ±    0.008  MB/sec
Main.separateLists:·gc.churn.PS_Survivor_Space.norm            thrpt  600       88.896 ±    7.778    B/op
Main.singleListAndInstanceof:·gc.churn.PS_Survivor_Space.norm  thrpt  600       81.693 ±    7.269    B/op
Main.separateLists:·gc.count                                   thrpt  600     2440.000             counts
Main.singleListAndInstanceof:·gc.count                         thrpt  600     2289.000             counts
Main.separateLists:·gc.time                                    thrpt  600     4501.000                 ms
Main.singleListAndInstanceof:·gc.time                          thrpt  600     4236.000                 ms

ОБНОВЛЕНИЕ: Ниже приведен код теста и результаты с кодом настройки массива, выделенным в отдельные методы и удаленным из измерения. instanceof медленнее для этого случая, как и ожидалось - вышеуказанные различия, вероятно, связаны с проблемами прогнозирования ветвлений в настройке списка. (хотя они тоже интересны, они, вероятно, должны перейти к отдельному вопросу)

package test;

import org.openjdk.jmh.annotations.*;

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }

    @State(Scope.Thread)
    public static class SeparateListsState {
        public ArrayList<Visible> visibles;
        public ArrayList<Highlightable> highlightables;
        public ArrayList<Selectable> selectables;

        @Setup(Level.Invocation)
        public void doSetup() {
            visibles = new ArrayList<>();
            highlightables = new ArrayList<>();
            selectables = new ArrayList<>();

            Random random = new Random(9698426994L + 8879);
            for (int i = 0; i < 10_000; i++) {
                switch (random.nextInt(9)) {
                    case 0:
                        visibles.add(new Visible1(i));
                        break;
                    case 1:
                        highlightables.add(new Highlightable1(i));
                        break;
                    case 2:
                        selectables.add(new Selectable1(i));
                        break;

                    case 3:
                        visibles.add(new Visible2(i));
                        break;
                    case 4:
                        highlightables.add(new Highlightable2(i));
                        break;
                    case 5:
                        selectables.add(new Selectable2(i));
                        break;

                    case 6:
                        visibles.add(new Visible3(i));
                        break;
                    case 7:
                        highlightables.add(new Highlightable3(i));
                        break;
                    case 8:
                        selectables.add(new Selectable3(i));
                        break;
                }
            }
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5, time = 1)
    @Measurement(iterations = 150, time = 1)
    @Fork(value = 2)
    public static long separateLists(SeparateListsState state) {
        long vsum = 0;
        long hsum = 0;
        long ssum = 0;
        for (Visible e : state.visibles) {
            vsum += e.visibleValue();
        }
        for (Highlightable e : state.highlightables) {
            vsum += e.visibleValue();
            hsum += e.highlightableValue();
        }
        for (Selectable e : state.selectables) {
            vsum += e.visibleValue();
            hsum += e.highlightableValue();
            ssum += e.selectableValue();
        }

        return vsum * hsum * ssum;
    }

    @State(Scope.Thread)
    public static class SingleListAndInstanceofState {
        public ArrayList<Visible> visibles;

        @Setup(Level.Invocation)
        public void doSetup() {
            visibles = new ArrayList<>();

            Random random = new Random(9698426994L + 8879);
            for (int i = 0; i < 10_000; i++) {
                switch (random.nextInt(9)) {
                    case 0:
                        visibles.add(new Visible1(i));
                        break;
                    case 1:
                        visibles.add(new Highlightable1(i));
                        break;
                    case 2:
                        visibles.add(new Selectable1(i));
                        break;

                    case 3:
                        visibles.add(new Visible2(i));
                        break;
                    case 4:
                        visibles.add(new Highlightable2(i));
                        break;
                    case 5:
                        visibles.add(new Selectable2(i));
                        break;

                    case 6:
                        visibles.add(new Visible3(i));
                        break;
                    case 7:
                        visibles.add(new Highlightable3(i));
                        break;
                    case 8:
                        visibles.add(new Selectable3(i));
                        break;
                }
            }
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5, time = 1)
    @Measurement(iterations = 150, time = 1)
    @Fork(value = 2)
    public static long singleListAndInstanceof(SingleListAndInstanceofState state) {
        long vsum = 0;
        long hsum = 0;
        long ssum = 0;
        for (Visible e : state.visibles) {
            if (e instanceof Selectable) {
                vsum += e.visibleValue();
                hsum += ((Selectable) e).highlightableValue();
                ssum += ((Selectable) e).selectableValue();
            } else if (e instanceof Highlightable) {
                vsum += e.visibleValue();
                hsum += ((Highlightable) e).highlightableValue();
            } else {
                vsum += e.visibleValue();
            }
        }

        return vsum * hsum * ssum;
    }
}

abstract class Visible {
    abstract int visibleValue();
}
abstract class Highlightable extends Visible {
    abstract int highlightableValue();
}
abstract class Selectable extends Highlightable {
    abstract int selectableValue();
}

class Visible1 extends Visible {
    private int v;
    Visible1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v; }
}
class Highlightable1 extends Highlightable {
    private int v;
    Highlightable1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*2; }
    @Override int highlightableValue() { return v*3; }
}
class Selectable1 extends Selectable {
    private int v;
    Selectable1(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*4; }
    @Override int highlightableValue() { return v*5; }
    @Override int selectableValue() { return v*6; }
}

class Visible2 extends Visible {
    private int v;
    Visible2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*7; }
}
class Highlightable2 extends Highlightable {
    private int v;
    Highlightable2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*8; }
    @Override int highlightableValue() { return v*9; }
}
class Selectable2 extends Selectable {
    private int v;
    Selectable2(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*10; }
    @Override int highlightableValue() { return v*11; }
    @Override int selectableValue() { return v*12; }
}


class Visible3 extends Visible {
    private int v;
    Visible3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*13; }
}
class Highlightable3 extends Highlightable {
    private int v;
    Highlightable3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*14; }
    @Override int highlightableValue() { return v*15; }
}
class Selectable3 extends Selectable {
    private int v;
    Selectable3(int v) {
        this.v = v;
    }
    @Override int visibleValue() { return v*16; }
    @Override int highlightableValue() { return v*17; }
    @Override int selectableValue() { return v*18; }
}

И результаты:

Main.separateLists                                             thrpt  300     4211.552 ±    23.791   ops/s
Main.singleListAndInstanceof                                   thrpt  300     3920.251 ±    15.478   ops/s
Main.separateLists:L1-dcache-load-misses:u                     thrpt    2     3046.033                #/op
Main.singleListAndInstanceof:L1-dcache-load-misses:u           thrpt    2     1089.122                #/op
Main.separateLists:L1-dcache-loads:u                           thrpt    2  1090745.006                #/op
Main.singleListAndInstanceof:L1-dcache-loads:u                 thrpt    2  1125243.609                #/op
Main.separateLists:L1-icache-load-misses:u                     thrpt    2      150.542                #/op
Main.singleListAndInstanceof:L1-icache-load-misses:u           thrpt    2      143.304                #/op
Main.separateLists:L1-icache-loads:u                           thrpt    2   600852.620                #/op
Main.singleListAndInstanceof:L1-icache-loads:u                 thrpt    2   700771.042                #/op
Main.separateLists:LLC-load-misses:u                           thrpt    2     1299.520                #/op
Main.singleListAndInstanceof:LLC-load-misses:u                 thrpt    2      636.764                #/op
Main.separateLists:LLC-loads:u                                 thrpt    2    14408.815                #/op
Main.singleListAndInstanceof:LLC-loads:u                       thrpt    2    10429.768                #/op
Main.separateLists:LLC-stores:u                                thrpt    2    18999.178                #/op
Main.singleListAndInstanceof:LLC-stores:u                      thrpt    2    15370.582                #/op
Main.separateLists:branch-misses:u                             thrpt    2    22578.062                #/op
Main.singleListAndInstanceof:branch-misses:u                   thrpt    2    29257.959                #/op
Main.separateLists:branches:u                                  thrpt    2   258026.890                #/op
Main.singleListAndInstanceof:branches:u                        thrpt    2   284911.889                #/op
Main.separateLists:cycles:u                                    thrpt    2  1915774.770                #/op
Main.singleListAndInstanceof:cycles:u                          thrpt    2  1974841.023                #/op
Main.separateLists:dTLB-load-misses:u                          thrpt    2      101.573                #/op
Main.singleListAndInstanceof:dTLB-load-misses:u                thrpt    2       99.982                #/op
Main.separateLists:dTLB-loads:u                                thrpt    2  1090174.103                #/op
Main.singleListAndInstanceof:dTLB-loads:u                      thrpt    2  1129185.929                #/op
Main.separateLists:iTLB-load-misses:u                          thrpt    2        4.432                #/op
Main.singleListAndInstanceof:iTLB-load-misses:u                thrpt    2        3.955                #/op
Main.separateLists:iTLB-loads:u                                thrpt    2   600301.665                #/op
Main.singleListAndInstanceof:iTLB-loads:u                      thrpt    2   703339.482                #/op
Main.separateLists:instructions:u                              thrpt    2  1974603.052                #/op
Main.singleListAndInstanceof:instructions:u                    thrpt    2  2040460.093                #/op
Main.separateLists:stalled-cycles-backend:u                    thrpt    2   808914.974                #/op
Main.singleListAndInstanceof:stalled-cycles-backend:u          thrpt    2   685615.056                #/op
Main.separateLists:stalled-cycles-frontend:u                   thrpt    2   186013.216                #/op
Main.singleListAndInstanceof:stalled-cycles-frontend:u         thrpt    2   272207.204                #/op
Main.separateLists:·gc.alloc.rate                              thrpt  300      346.891 ±     1.166  MB/sec
Main.singleListAndInstanceof:·gc.alloc.rate                    thrpt  300      358.297 ±     0.614  MB/sec
Main.separateLists:·gc.alloc.rate.norm                         thrpt  300   310744.294 ±     0.107    B/op
Main.singleListAndInstanceof:·gc.alloc.rate.norm               thrpt  300   328992.302 ±     0.110    B/op
Main.separateLists:·gc.churn.PS_Eden_Space                     thrpt  300      349.387 ±    14.305  MB/sec
Main.singleListAndInstanceof:·gc.churn.PS_Eden_Space           thrpt  300      360.039 ±     9.075  MB/sec
Main.separateLists:·gc.churn.PS_Eden_Space.norm                thrpt  300   313154.953 ± 13018.012    B/op
Main.singleListAndInstanceof:·gc.churn.PS_Eden_Space.norm      thrpt  300   330629.833 ±  8345.712    B/op
Main.separateLists:·gc.churn.PS_Survivor_Space                 thrpt  300        0.092 ±     0.012  MB/sec
Main.singleListAndInstanceof:·gc.churn.PS_Survivor_Space       thrpt  300        0.094 ±     0.011  MB/sec
Main.separateLists:·gc.churn.PS_Survivor_Space.norm            thrpt  300       82.348 ±    10.661    B/op
Main.singleListAndInstanceof:·gc.churn.PS_Survivor_Space.norm  thrpt  300       86.465 ±    10.417    B/op
Main.separateLists:·gc.count                                   thrpt  300     1196.000              counts
Main.singleListAndInstanceof:·gc.count                         thrpt  300     1235.000              counts
Main.separateLists:·gc.time                                    thrpt  300     2178.000                  ms
Main.singleListAndInstanceof:·gc.time                          thrpt  300     2355.000                  ms

Answer 1

Как показывает NoDataFound в комментариях, вы не просто сравниваете производительность итерации по списку, но также сравниваете методы заполнения списка. Вам нужно перетащить эту часть своего кода в метод установки - в противном случае на вас могут повлиять операции изменения размера ваших трех ArrayList экземпляров (среди прочего).

Вам также следует либо отказаться от использования Random для заполнения списка, либо, по крайней мере, создать его экземпляр с одинаковым начальным числом в обеих реализациях, иначе вы не создадите повторяющийся порядок элементов в обеих реализациях.

Answer 2

Суть в том, что ваши измерения ошибочны.Мало того, что первая версия вашего вопроса измеряла разные «вещи», но даже у обновленного вопроса есть одна большая проблема, (слишком низкий) размер выборки 10_000!

Это просто неразумный размер выборки.По крайней мере, не один.Вы должны проверить то, что вы видите для итераций 10K, 50K, 100K, 1 миллион, ... цикл.

Видите ли, вы делаете ошибку, которую многие люди делают с Java: они предполагают, что та или иная конструкция на стороне исходного кода определяет производительность.

И это только частично верно.Видите ли, реальные пики производительности происходят из бесчисленных оптимизаций, которые JIT-компилятор в JVM будет выполнять во время выполнения, на основе собранной им информации профилирования.

Я думаю, по умолчаниюпорог, по которому JIT запускает и преобразует байт-код в высокооптимизированный машинный код, подобен вызовам метода / итерации цикла (90 КБ?)более того, JIT даже не считает ваш код «стоящим для оптимизации».Но тогда это начнется, и это может оказать существенное влияние на общую производительность.И потом, то, что вы положили в свой исходный код ... может больше не иметь значения.

Таким образом, нет ни одного измерения, которое бы указывало на то, что является «лучшим» решением.Это скорее зависит от количества итераций, которые вы проходите.

Таким образом, реальный ответ таков: бенчмаркинг производительности Java сложен, и вы должны быть предельно внимательны к тому, что вы делаете, и к выводам, которые вы делаете из своих результатов.

Помимо этого,настоящий реальный ответ: производительность - это проблема роскоши.Конечно, следует избегать глупых ошибок, которые бесполезно сжигают циклы процессора.Но кроме того, ваша основная цель всегда состоит в написании простого кода, который легко читать и понимать.И затем, когда вы замечаете, что «это кажется вялым» или «это не соответствует нашим SLA», тогда вы тщательно определяете эксперименты, чтобы измерить, что происходит, чтобы идентифицировать тот фрагмент кода, который вызывает проблему с производительностью.И просто для справки: вы знаете, какой код JIT может оптимизировать лучше всего ... сюрприз: простой прямой код, который выглядит как код 90% хороших Java-кодеров имеют тенденцию писать.