Pull to refresh

Вычисление факториала или мощь Stream API

Reading time 4 min
Views 32K
На днях появилась статья 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 многие ругают, но за параллелизмом всё же будущее.
Tags:
Hubs:
+20
Comments 44
Comments Comments 44

Articles