Разница между последовательным и параллельным выполнением с параллелизмом = 1

Question

Не могли бы вы дать мне ссылку, почему существует существенная разница во времени выполнения между следующими 2 факториальными реализациями, использующими Java Stream API:

1. Последовательная реализация
2. Параллельная реализация (использование Stream.parallel ()), выполняемого в пользовательском пуле объединения вилок с параллелизмом, установленным на 1

Мои ожидания заключались в том, чтобы иметь близкое время выполнения, однако параллельная версия имеет ускорение в 2 раза.Я не запускал никаких специализированных тестов, однако время выполнения не должно сильно отличаться даже при холодном запуске jvm.Ниже я прикрепляю исходный код двух реализаций:

• Параллельно

public class FastFactorialSupplier implements FactorialSupplier {
  private final ExecutorService executorService;

  public FastFactorialSupplier(ExecutorService executorService) {
      this.executorService = executorService;
  }

  @Override
  public BigInteger get(long k) {
      try {
          return executorService
                  .submit(
                          () -> LongStream.range(2, k + 1)
                                  .parallel()
                                  .mapToObj(BigInteger::valueOf)
                                  .reduce(BigInteger.ONE, (current, factSoFar) -> factSoFar.multiply(current))
                  )
                  .get();
      } catch (InterruptedException | ExecutionException e) {
          e.printStackTrace();
      }

      return BigInteger.ZERO;
  }
}

• Последовательный

public class MathUtils {

  public static BigInteger factorial(long k) {
      return LongStream.range(2, k + 1)
              .mapToObj(BigInteger::valueOf)
              .reduce(BigInteger.ONE, (current, factSoFar) -> factSoFar.multiply(current));
  }
}

Вот тестовые примеры с приложенным временем выполнения примера в виде комментариев, основанных на том, что показал бегунок intellij junit.

    @Test
    public void testWithoutParallel() {
        //2s 403
        runTest(new DummyFactorialSupplier()); // uses MathUtils.factorial
    }

    @Test
    public void testParallelismWorkStealing1() {
        //1s 43
        runTest(new FastFactorialSupplier(Executors.newWorkStealingPool(1)));
    }

    @Test
    public void testParallelismForkJoin1() {
        // 711ms
        runTest(new FastFactorialSupplier(new ForkJoinPool(1)));
    }

    @Test
    public void testExecutorForkJoin() {
        //85ms
        runTest(new FastFactorialSupplier(new ForkJoinPool()));
    }

    private void runTest(FactorialSupplier factorialSupplier) {
        BigInteger result = factorialSupplier.get(100000);
        assertNotNull(result);
//        assertEquals(456574, result.toString().length());
    }

Тесты были выполнены с использованием java 11, так какбыла проблема в java 8 с пользовательскими пулами объединения вилок - https://bugs.openjdk.java.net/browse/JDK-8190974

Может ли быть оптимизация, связанная с псевдопараллельной обработкой и с тем, как запланировано выполнение, тогда как такого нет, если выполнение чисто последовательное?

Редактировать:

Я также запускаю микробенчмарк, используя jmh

Параллельно:

public class FastFactorialSupplierP1Test {

    @Benchmark
    @BenchmarkMode({Mode.AverageTime, Mode.SampleTime, Mode.SingleShotTime, Mode.Throughput, Mode.All})
    @Fork(value = 1, warmups = 1)
    public void measure() {
        runTest(new FastFactorialSupplier(new ForkJoinPool(1)));
    }

    private void runTest(FactorialSupplier factorialSupplier) {
        BigInteger result = factorialSupplier.get(100000);
        assertNotNull(result);
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

Серийный номер:

public class SerialFactorialSupplierTest {
    @Benchmark
    @BenchmarkMode({Mode.AverageTime, Mode.SampleTime, Mode.SingleShotTime, Mode.Throughput, Mode.All})
    @Fork(value = 1, warmups = 1)
    public void measure() {
        runTest(new DummyFactorialSupplier());
    }

    private void runTest(FactorialSupplier factorialSupplier) {
        BigInteger result = factorialSupplier.get(100000);
        assertNotNull(result);
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

public class IterativeFactorialTest {
    @Benchmark
    @BenchmarkMode({Mode.AverageTime, Mode.SampleTime, Mode.SingleShotTime, Mode.Throughput, Mode.All})
    @Fork(value = 1, warmups = 1)
    public void measure() {
        runTest(new IterativeFact());
    }

    private void runTest(FactorialSupplier factorialSupplier) {
        BigInteger result = factorialSupplier.get(100000);
        assertNotNull(result);
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }

    class IterativeFact implements FactorialSupplier {

        @Override
        public BigInteger get(long k) {
            BigInteger result = BigInteger.ONE;

            while (k-- != 0) {
                result = result.multiply(BigInteger.valueOf(k));
            }

            return result;
        }
    }
}

Результаты:

FastFactorialSupplierP1Test.measure                    avgt    5  0.437 ± 0.006   s/op
IterativeFactorialTest.measure                         avgt    5  2.643 ± 0.383   s/op
SerialFactorialSupplierTest.measure                    avgt    5  2.226 ± 0.044   s/op

Answer 1

Вы выбрали операцию, выполнение которой зависит от порядка оценки.Просто учтите, что производительность BigInteger.multiply зависит от величины двух факторов.Затем выполнение последовательности BigInteger экземпляров с накапливающимся значением в качестве коэффициента для следующего умножения сделает операцию более дорогой, чем дальше вы получите.

Напротив, когда вы разделяете диапазонзначений в меньшие диапазоны, выполняйте умножение индивидуально для каждого диапазона и умножая результаты диапазонов, вы получаете преимущество в производительности, даже если эти поддиапазоны не оцениваются одновременно.

Таким образом, когда параллельный поток разделяетсяработа в чанках, которые потенциально могут быть захвачены другими рабочими потоками, но в итоге оценивают их в том же потоке, вы все равно получаете улучшение производительности в этой конкретной настройке благодаря измененному порядку оценки.

Мы можем проверить это, удалив все артефакты, связанные с потоком и пулом потоков:

public static BigInteger multiplyAll(long from, long to, int split) {
    if(split < 1 || to - from < 2) return serial(from, to);
    split--;
    long middle = (from + to) >>> 1;
    return multiplyAll(from, middle, split).multiply(multiplyAll(middle, to, split));
}

private static BigInteger serial(long l1, long l2) {
    BigInteger bi = BigInteger.valueOf(l1++);
    for(; l1 < l2; l1++) {
        bi = bi.multiply(BigInteger.valueOf(l1));
    }
    return bi;
}

У меня нет под рукой установки JMH, чтобы публиковать стрессовые результаты, но простой запуск показалчто порядок соответствует вашим результатам, просто один разуже примерно вдвое сокращает время оценки, а более высокие числа все еще улучшают производительность, хотя кривая становится более плоской.

Как объяснено в ForkJoinTask.html#getSurplusQueuedTaskCount(), разумной стратегией является разделение работы таким образом, чтобынесколько дополнительных задач на одного работника, которые потенциально могут быть подхвачены другими потоками, что может компенсировать несбалансированные рабочие нагрузки, например, если некоторые элементы дешевле обрабатывать, чем другие.По-видимому, параллельные потоки не имеют специального кода для обработки случая, когда нет дополнительных рабочих потоков, следовательно, вы наблюдаете эффекты разделения работы, даже когда есть только один поток для ее обработки.