Задача про forEach(ps::println) от СКБ Контур
На конференции JBreak я не читал задачки спонсоров специально. Ну, конечно, кроме ада от Excelsior: уж эти ребята всем задали жару. А тут принесли мне листок от СКБ Контур, смотри, мол, посмейся. Я посмеялся: первая задача действительно выглядела настолько наивно сформированной и недоопределённой, что даже не хотелось идти к стенду и убеждать в этом сотрудников компании. Я про это почти забыл, однако тут на Хабре появился авторский разбор этой задачи, не лишённый некоторой глубины. Даже про modCount написали. Выходит, зря я смеялся?
Напомню, задача звучала так:
Упорядочить методы по скорости их работы и вписать номера методов в соответствующую ячейку. Если методы дают незначительно отличающиеся результаты, тогда вписать их в одну ячейку. По каждой задаче написать разъяснение, почему одни методы быстрее других. Предполагается, что код запускается в HotSpot 64-bit VM (JRE 1.8.0_161).void forEach(Listvalues, PrintStream ps) { // 1 values.forEach(ps::println); } void forEach(List values, PrintStream ps) { // 2 values.stream().forEach(ps::println); } void forEach(List 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 getList(int size) {
class MyList extends AbstractList 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();
} @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 values, PrintStream ps) { // 1
values.forEach(ps::println);
}
void forEach2(List values, PrintStream ps) { // 2
values.stream().forEach(ps::println);
}
void forEach3(List 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 getList(int size) {
class MyList extends AbstractList 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 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 stream() {
return IntStream.range(0, size).mapToObj(this::get);
}
@Override
public Stream 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 вообще всё непросто, тут слишком много свободных переменных и тонких эффектов, чтобы о чём-то говорить определённо. Лучше придумывайте задачки на корректность и семантику, там всё значительно более строго.
С нетерпением жду разбора остальных задач от СКБ Контур!
