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 многие ругают, но за параллелизмом всё же будущее.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий