Вычисление факториала или мощь Stream API
На днях появилась статья 5nwДва способа быстрого вычисления факториала, в которой приводится идея ускорения подсчёта факториала с помощью группировки перемножаемых чисел в дерево по принципу «разделяй и властвуй». Взглянув на это, я сразу понял, что тут параллельные потоки Java проявят себя во всей красе: ведь они делят задачу на подзадачи с помощью сплитераторов именно таким образом. Получается, что быстрая реализация будет ещё и красивой: public static BigInteger streamedParallel (int n) { if (n < 2) return BigInteger.valueOf(1); return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(); } К сожалению, в статье 5nw нет подробностей замера производительности. Сколько тестов проводилось? Был ли разогрев? Оценивалась ли погрешность замеров времени? Не выкосил ли JIT-компилятор часть вычислений, потому что их результаты не использовались? А если использовались (например, полученное число выводилось в файл), то исключён ли факт использования из подсчёта времени? В этом плане хочу сказать спасибо Алексею Шипилёву, который своей библиотекой JMH, а также многочисленными презентациями и статьями привил какую-никакую культуру бенчмаркинга в Java-сообществе.У меня будет такой код бенчмарка:
import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.annotations.*; import java.util.concurrent.TimeUnit; import java.util.stream.IntStream; import java.math.BigInteger;
@Warmup (iterations=5) @Measurement (iterations=10) @BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @State (Scope.Benchmark) @Fork (2) public class Factorial { @Param ({»10»,»100»,»1000»,»10000»,»50000»}) private int n;
public static BigInteger naive (int n) { BigInteger r = BigInteger.valueOf (1); for (int i = 2; i <= n; ++i) r = r.multiply(BigInteger.valueOf(i)); return r; }
public static BigInteger streamed (int n) { if (n < 2) return BigInteger.valueOf(1); return IntStream.rangeClosed(2, n).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(); } public static BigInteger streamedParallel(int n) { if(n < 2) return BigInteger.valueOf(1); return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get(); }
@Benchmark public void testNaive (Blackhole bh) { bh.consume (naive (n)); } @Benchmark public void testStreamed (Blackhole bh) { bh.consume (streamed (n)); } @Benchmark public void testStreamedParallel (Blackhole bh) { bh.consume (streamedParallel (n)); } } Я сравнил три реализации — наивную, на обычном потоке и на параллельном потоке. Разумно проверить алгоритм для различных значений n — 10, 100, 1000, 10000 и 50000, чтобы представить динамику изменения результатов. Проводится пять итераций разогрева и десять итераций с замером, всё это повторяется дважды (с перезапуском Java-машины), то есть для каждого теста делается 20 замеров. Обратите внимание на чёрную дыру (Blackhole): она нужна, чтобы JIT-компилятор не удалил результат вычислений, решив, что он всё равно не используется.
Протестировал я на ноутбуке с процессором Core i7–4702MQ (8 хардварных тредов). Получаются вот такие результаты:
Benchmark (n) Mode Cnt Score Error Units Factorial.testNaive 10 avgt 20 0.298 ± 0.005 us/op Factorial.testNaive 100 avgt 20 5.113 ± 0.195 us/op Factorial.testNaive 1000 avgt 20 278.601 ± 9.586 us/op Factorial.testNaive 10000 avgt 20 32232.618 ± 889.512 us/op Factorial.testNaive 50000 avgt 20 972369.158 ± 29287.950 us/op Factorial.testStreamed 10 avgt 20 0.339 ± 0.021 us/op Factorial.testStreamed 100 avgt 20 5.432 ± 0.246 us/op Factorial.testStreamed 1000 avgt 20 268.366 ± 4.859 us/op Factorial.testStreamed 10000 avgt 20 30429.526 ± 435.611 us/op Factorial.testStreamed 50000 avgt 20 896719.207 ± 7995.599 us/op Factorial.testStreamedParallel 10 avgt 20 6.470 ± 0.515 us/op Factorial.testStreamedParallel 100 avgt 20 11.280 ± 1.094 us/op Factorial.testStreamedParallel 1000 avgt 20 74.174 ± 2.647 us/op Factorial.testStreamedParallel 10000 avgt 20 2826.643 ± 52.831 us/op Factorial.testStreamedParallel 50000 avgt 20 49196.070 ± 464.634 us/op Наивный тест в целом подтверждает теоретическое предположение о квадратичой сложности алгоритма. Разделим время на n²: n = 10: 0.002980 n = 100: 0.000511 n = 1000: 0.000279 n = 10000: 0.000322 n = 50000: 0.000389 Прирост на больших значениях, вероятно, связан с увеличением расхода памяти и активизацией сборщика мусора.Нераспараллеленный поток для малых n работает ожидаемо несколько большее время (на 13% для n = 10 и на 6% для n = 100): всё же обвязка Stream API что-то съедает. Однако удивительно, что для больших n потоковый вариант работает на 4–8% быстрее, хотя алгоритмически выглядит так же. Очередное подтверждение тому, что о производительности опасно рассуждать теоретически, не проводя замеры. Оптимизации JIT-компилятора, кэширование процессора, предсказание ветвления и прочие факторы очень трудно учесть в теории.
Распараллеленный поток ожидаемо существенно медленнее для очень коротких операций. Однако прирост скорости наблюдается уже при n = 1000, когда полный расчёт занимает около 270 мкс в последовательном режиме и только 75 в параллельном. Это отлично согласуется со Stream Parallel Guidance (спасибо apangin за ссылку), где сказано, что распараллеливать имеет смысл задачи, которые выполняются дольше 100 мкс. При больших же значениях n распараллеленный поток на коне: мы получаем прирост скорости в 18 раз. В целом это согласуется с приростом у 5nw, помноженным на число потоков (1.7/0.8×8 = 17).
У ForkJoinPool очень маленький оверхед, поэтому даже миллисекундная задача получает выигрыш по скорости. При этом алгоритмы вида «разделяй и властвуй» естественным образом перекладываются на параллельные потоки, благодаря чему параллельный поток может оказаться существенно быстрее последовательного. Stream API многие ругают, но за параллелизмом всё же будущее.
