На днях появилась статья 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 многие ругают, но за параллелизмом всё же будущее.
Автор: lany
