На конференции JBreak я не читал задачки спонсоров специально. Ну, конечно, кроме ада от Excelsior: уж эти ребята всем задали жару. А тут принесли мне листок от СКБ Контур, смотри, мол, посмейся. Я посмеялся: первая задача действительно выглядела настолько наивно сформированной и недоопределённой, что даже не хотелось идти к стенду и убеждать в этом сотрудников компании. Я про это почти забыл, однако тут на Хабре появился авторский разбор этой задачи, не лишённый некоторой глубины. Даже про modCount написали. Выходит, зря я смеялся?

Напомню, задача звучала так:

Упорядочить методы по скорости их работы и вписать номера методов в соответствующую ячейку. Если методы дают незначительно отличающиеся результаты, тогда вписать их в одну ячейку. По каждой задаче написать разъяснение, почему одни методы быстрее других. Предполагается, что код запускается в HotSpot 64-bit VM (JRE 1.8.0_161).

void forEach(List<Integer> values, PrintStream ps) { // 1
    values.forEach(ps::println);
}

void forEach(List<Integer> values, PrintStream ps) { // 2
    values.stream().forEach(ps::println);
}

void forEach(List<Integer> values, PrintStream ps) { // 3
    values.parallelStream().forEach(ps::println);
}

По словам авторов задачи, правильный ответ «зависит от»: 1 или 2 в зависимости от расположения звёзд на небе. При этом бланк для решений не предполагал вписывание такого варианта, да и на объяснение этого места было маловато. Вообще я считаю, что некорректно давать задачу без однозначного правильного ответа. Я не против задач, где однозначно два правильных ответа: 1 и 2 (например, оба всегда и доказуемо одинаково быстрые). Но тут ответ: или так, или эдак в зависимости от обстоятельств. Это некрасивая задача, непродуманная. Такое ощущение, что у авторов правильный ответ был один, но потом (возможно, после общения с участниками конференции) они сами поняли, что были неправы.

Однако самая большая проблема в том, что и третий вариант тоже может быть самым быстрым в зависимости от обстоятельств.

Напомню: довод авторов против варианта с parallelStream в том, что потребитель (PrintStream::println) синхронизирован, а значит процесс потребления данных линеаризован: между потреблением двух любых элементов устанавливается отношение happens-before. Соответственно, от распараллеливания пользы мы не получим, а получим только оверхед на создание потоков и синхронизацию. Тем не менее, не стоит забывать, что стрим состоит не только из потребителя данных, но и из источника. И источник вполне может быть не линеаризован. Если подобрать источник и потребитель так, что источник окажется существенно медленнее, то параллелизм обеспечит прирост сколь угодно близкий к числу процессоров.

По условию задачи источник — какая-то реализация интерфейса List. Дальнейших ограничений задача не вводит, поэтому мы вольны привести любую реализацию, соблюдающую контракт. Мы можем даже ограничиться «достаточно разумными реализациями», которые выглядят логично, без заведомо избыточных задержек.

Давайте сперва ускорим потребителя. Конечно, PrintStream — не финальный класс, и мы могли бы спокойно его расширить, переопределив метод println и убрав синхронизацию вообще. Однако я считаю это читерством: переопределение существующего поведения не должно считаться корректным решением в таких задачах. Тем не менее помним, что PrintStream — это всего лишь обёртка над OutputStream, а тут уже мы в своём праве подсунуть любую реализацию этого абстрактного класса, которая, например, ничего не делает:

private static PrintStream getStream() {
    return new PrintStream(new OutputStream() {
        public void write(int b) {}
        public void write(byte[] b, int off, int len) {}
    });
}

Конечно, это необязательно, а всего лишь для усиления эффекта. Мы можем и для стандартного вывода на консоль сделать источник, который будет существенно медленнее.

Теперь, собственно, источник. Списки, которые выдают элементы медленно, вполне возможны и вполне встречаются в жизни. Такой можно создать, скажем, через Lists.transform из библиотеки Guava, подобрав соответствующую функцию. Вручную его написать тоже несложно: достаточно расширить стандартный AbstractList, определив два метода — get() и size(). Так как наш список будет списком со случайным доступом, мы ещё пометим его маркерным интерфейсом RandomAccess.

Чем же мы займём наш список? Пусть он для каждого элемента с индеком i, например, содержит младший байт хэш-суммы SHA-512 от строкового представления индекса в кодировке UTF-16. Почему нет? Может нам нужна такая псевдослучайная, но стабильная штука:

static List<Integer> getList(int size) {
    class MyList extends AbstractList<Integer> implements RandomAccess {
        @Override
        public Integer get(int index) {
            // Да, появился такой метод в Java 9, очень удобно!
            Objects.checkIndex(index, size);
            try {
                MessageDigest md = MessageDigest.getInstance("SHA-512");
                md.update(String.valueOf(index).getBytes(StandardCharsets.UTF_16));
                return (int) md.digest()[0];
            } catch (NoSuchAlgorithmException e) {
                throw new RuntimeException(e);
            }
        }

        @Override
        public int size() { return size; }
    }
    return new MyList();
}

@BenchmarkMode(Mode.AverageTime)
@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(5)
@State(Scope.Benchmark)
public class ListBenchmark {
    @Param({"100", "10000", "1000000"})
    private int size;

    @Benchmark
    public void testForEach() {
        forEach1(getList(size), getStream());
    }

    @Benchmark
    public void testStreamForEach() {
        forEach2(getList(size), getStream());
    }

    @Benchmark
    public void testParallelStreamForEach() {
        forEach3(getList(size), getStream());
    }

    void forEach1(List<Integer> values, PrintStream ps) { // 1
        values.forEach(ps::println);
    }

    void forEach2(List<Integer> values, PrintStream ps) { // 2
        values.stream().forEach(ps::println);
    }

    void forEach3(List<Integer> values, PrintStream ps) { // 3
        values.parallelStream().forEach(ps::println);
    }

    static PrintStream getStream() {
        return new PrintStream(new OutputStream() {
            public void write(int b) {}
            public void write(byte[] b, int off, int len) {}
        });
    }

    static List<Integer> getList(int size) {
        class MyList extends AbstractList<Integer> implements RandomAccess {
            @Override
            public Integer get(int index) {
                // Да, появился такой метод в Java 9, очень удобно!
                Objects.checkIndex(0, size);
                try {
                    MessageDigest md = MessageDigest.getInstance("SHA-512");
                    md.update(String.valueOf(index).getBytes(StandardCharsets.UTF_16));
                    return (int) md.digest()[0];
                } catch (NoSuchAlgorithmException e) {
                    throw new RuntimeException(e);
                }
            }

            @Override
            public int size() { return size; }
        }
        return new MyList();
    }
}

Теперь погоняем бенчмарк на четырёхядерной машине и увидим такие результаты:

# JMH version: 1.20
# VM version: JDK 9.0.4, VM 9.0.4+11
# VM invoker: C:\Program Files\Java\jdk-9.0.4\bin\java.exe
...
Benchmark                   (size)  Mode  Cnt        Score        Error  Units
testForEach                    100  avgt   50      317,811 ±     48,847  us/op
testForEach                  10000  avgt   50    11944,452 ±    308,630  us/op
testForEach                1000000  avgt   50  1650511,656 ± 489838,860  us/op
testParallelStreamForEach      100  avgt   50       89,836 ±      2,507  us/op
testParallelStreamForEach    10000  avgt   50     9629,607 ±    935,511  us/op
testParallelStreamForEach  1000000  avgt   50   890954,996 ±  64176,572  us/op
testStreamForEach              100  avgt   50      171,991 ±     48,877  us/op
testStreamForEach            10000  avgt   50    22063,496 ±   5965,278  us/op
testStreamForEach          1000000  avgt   50  1646935,273 ± 485037,889  us/op

Результат ForEach и StreamForEach выглядит несколько странно. Например, для списка из 100 элементов стрим побеждает, а для списка из 10000 — наоборот. Однако желанный результат налицо: параллельный стрим везде работает быстрее.

Откуда, кстати, такие колебания? Они могут легко возникнуть, если вы не будете повторять ошибку разработчиков из СКБ Контур: нельзя гонять бенчмарк на одном форке, особенно, если вы подозреваете, что на результат существенно влияет работа JIT-компилятора. JIT-компилятор совершенно недетерминированный: результат компиляции зависит от собранного профиля, но профиль собирается асинхронно, поэтому на момент начала компиляции там могут быть разные цифры и код получится различным. Увеличивать число итераций не имеет смысла, потому что при выходе на стабильное состояние горячий код уже не перекомпилируется. Смотрите, например, вывод для ForEach/size=100:

# Run progress: 0,00% complete, ETA 00:05:37
# Fork: 1 of 5
# Warmup Iteration   1: 585,124 us/op
# Warmup Iteration   2: 390,473 us/op
# Warmup Iteration   3: 388,228 us/op
# Warmup Iteration   4: 387,198 us/op
# Warmup Iteration   5: 384,001 us/op
Iteration   1: 386,163 us/op
Iteration   2: 376,344 us/op
Iteration   3: 374,520 us/op
Iteration   4: 364,211 us/op
Iteration   5: 364,389 us/op
Iteration   6: 363,269 us/op
Iteration   7: 364,266 us/op
Iteration   8: 364,123 us/op
Iteration   9: 363,860 us/op
Iteration  10: 364,035 us/op

# Run progress: 2,22% complete, ETA 00:05:48
# Fork: 2 of 5
# Warmup Iteration   1: 426,376 us/op
# Warmup Iteration   2: 386,556 us/op
# Warmup Iteration   3: 382,808 us/op
# Warmup Iteration   4: 378,838 us/op
# Warmup Iteration   5: 377,987 us/op
Iteration   1: 377,438 us/op
Iteration   2: 374,149 us/op
Iteration   3: 370,854 us/op
Iteration   4: 361,177 us/op
Iteration   5: 362,603 us/op
Iteration   6: 361,055 us/op
Iteration   7: 361,445 us/op
Iteration   8: 361,564 us/op
Iteration   9: 364,283 us/op
Iteration  10: 359,619 us/op

# Run progress: 4,44% complete, ETA 00:05:39
# Fork: 3 of 5
# Warmup Iteration   1: 582,933 us/op
# Warmup Iteration   2: 144,197 us/op
# Warmup Iteration   3: 140,762 us/op
# Warmup Iteration   4: 135,908 us/op
# Warmup Iteration   5: 132,585 us/op
Iteration   1: 132,768 us/op
Iteration   2: 132,491 us/op
Iteration   3: 129,447 us/op
Iteration   4: 119,316 us/op
Iteration   5: 119,427 us/op
Iteration   6: 119,018 us/op
Iteration   7: 119,305 us/op
Iteration   8: 119,361 us/op
Iteration   9: 119,130 us/op
Iteration  10: 119,105 us/op

# Run progress: 6,67% complete, ETA 00:05:31
# Fork: 4 of 5
# Warmup Iteration   1: 569,460 us/op
# Warmup Iteration   2: 389,247 us/op
# Warmup Iteration   3: 385,768 us/op
# Warmup Iteration   4: 381,309 us/op
# Warmup Iteration   5: 379,797 us/op
Iteration   1: 381,618 us/op
Iteration   2: 372,816 us/op
Iteration   3: 371,384 us/op
Iteration   4: 361,205 us/op
Iteration   5: 361,428 us/op
Iteration   6: 361,174 us/op
Iteration   7: 360,579 us/op
Iteration   8: 360,488 us/op
Iteration   9: 359,859 us/op
Iteration  10: 361,365 us/op

# Run progress: 8,89% complete, ETA 00:05:23
# Fork: 5 of 5
# Warmup Iteration   1: 544,560 us/op
# Warmup Iteration   2: 390,766 us/op
# Warmup Iteration   3: 388,537 us/op
# Warmup Iteration   4: 383,953 us/op
# Warmup Iteration   5: 382,270 us/op
Iteration   1: 384,325 us/op
Iteration   2: 377,098 us/op
Iteration   3: 371,531 us/op
Iteration   4: 362,499 us/op
Iteration   5: 362,045 us/op
Iteration   6: 363,345 us/op
Iteration   7: 361,930 us/op
Iteration   8: 362,357 us/op
Iteration   9: 362,452 us/op
Iteration  10: 362,302 us/op

Здесь две отдельных моды в результате: одна около 360 микросекунд, а другая — около 120. При этом в рамках форка результат существенно стабильнее, чем между форками. Вы начинаете ощущать бессмысленность задачи? О какой разнице производительности можно спрашивать, если перезапустив один и тот же код, вы обнаруживаете, что он работает втрое медленнее. Подобные фокусы JIT частенько выкидывает. Неприятно получится, если вы сделаете выводы на основании эксперимента, в котором вам просто повезло и JIT принял удачное решение, которое принимает в одном случае из десяти. Как правило, я не делаю менее трёх форков и если замечаю подозрительную разницу в скорости, то увеличиваю их количество, чтобы изучить явление подробнее.

Тем не менее, изучив вывод, я могу с уверенностью сказать, что даже самый медленный параллельный форк не хуже самого быстрого последовательного. Значит, третий вариант может выиграть, хотя по словам авторов, это «очевидный неправильный ответ».

Внимательный читатель тут возразит: позвольте-позвольте, какая такая Java 9? По условиям была Java 1.8.0_161. Да, замечание верное: я действительно пользуюсь здесь фичей, которая появилась только в девятке: List.spliterator should optimize for RandomAccess lists. В Java 8 реализация сплитератора по умолчанию для списка более глупая, и распараллеливание получается существенно хуже (а нечего устаревшими версиями Java пользоваться!) Поэтому с таким кодом в Java 8 мы почти не получим прироста. Но это не делает наши рассуждения в корне неверными, надо просто написать кода чуть больше. Писать полноценный хороший сплитератор довольно долго, но в некоторых случаях (в том числе здесь) можно схалявить и вместо этого реализовать заново методы stream() и parallelStream():

class MyList extends AbstractList<Integer> implements RandomAccess {
    @Override
    public Integer get(int index) {
        // Модного метода checkIndex нет в Java 8 :-(
        if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
        ... тут дальше всё как было ...
    }

    @Override
    public int size() { return size; }

    @Override
    public Stream<Integer> stream() {
        return IntStream.range(0, size).mapToObj(this::get);
    }

    @Override
    public Stream<Integer> parallelStream() {
        return stream().parallel();
    }
}

Это читерством не считается. Подобным образом реализован, например, стрим для списка, возвращаемого Collections.nCopies. Если я делаю свой список, который планируется использовать как источник параллельного стрима, то, разумеется, я должен позаботиться, чтобы он нормально параллелился.

Результаты вполне ожидаемые:

# JMH version: 1.20
# VM version: JDK 1.8.0_161, VM 25.161-b12
# VM invoker: C:\Program Files\Java\jre1.8.0_161\bin\java.exe
Benchmark                   (size)  Mode  Cnt        Score       Error  Units
testForEach                    100  avgt   50      134,974 ±     2,900  us/op
testForEach                  10000  avgt   50    13075,674 ±   332,211  us/op
testForEach                1000000  avgt   50  1315215,358 ±  9702,119  us/op
testParallelStreamForEach      100  avgt   50      113,029 ±     1,934  us/op
testParallelStreamForEach    10000  avgt   50     9711,281 ±   113,490  us/op
testParallelStreamForEach  1000000  avgt   50  1002479,362 ± 11129,949  us/op
testStreamForEach              100  avgt   50      134,033 ±     2,806  us/op
testStreamForEach            10000  avgt   50    13247,368 ±   273,218  us/op
testStreamForEach          1000000  avgt   50  1320319,189 ± 16277,564  us/op

И тут параллельный стрим побеждает. Кстати, в восьмёрке результаты заметно стабильнее. Вероятно, в девятке что-то сломали в JIT-компиляторе. Интересно, что в Java 10 тоже стабильно и при этом быстрее, чем в Java 8.

Вывод можно сделать следующий. Быстродействие — слишком тонкая область, чтобы в ней сделать надёжную задачку. В крайнем случае, можно формулировать задачу не «что быстрее», а «объясните эффект», как, например, сделал apangin в старом конкурсе (смотрите второй вопрос). А со Stream API вообще всё непросто, тут слишком много свободных переменных и тонких эффектов, чтобы о чём-то говорить определённо. Лучше придумывайте задачки на корректность и семантику, там всё значительно более строго.

С нетерпением жду разбора остальных задач от СКБ Контур!