Java 8 вложенных циклов с потоками и производительностью

Чтобы тренировать потоки Java 8, я попытался преобразовать следующий вложенный цикл в API потока Java 8. Он вычисляет наибольшую сумму суммы a ^ b (a, b < 100) и принимает ~ 0.135s на моем Core i5 760.

public static int digitSum(BigInteger x)
{
    int sum = 0;
    for(char c: x.toString().toCharArray()) {sum+=Integer.valueOf(c+"");}
    return sum;
}

@Test public void solve()
    {
        int max = 0;
        for(int i=1;i<100;i++)
            for(int j=1;j<100;j++)
                max = Math.max(max,digitSum(BigInteger.valueOf(i).pow(j)));
        System.out.println(max);
    }

Мое решение, которое я ожидал быстрее из-за паралеллизма, на самом деле заняло 0,25 с (0,19 с без parallel()):

int max =   IntStream.range(1,100).parallel()
            .map(i -> IntStream.range(1, 100)
            .map(j->digitSum(BigInteger.valueOf(i).pow(j)))
            .max().getAsInt()).max().getAsInt();

Мои вопросы

  • Я сделал правильное преобразование или есть лучший способ конвертировать вложенные циклы в потоковые вычисления?
  • почему вариант потока намного медленнее старого?
  • почему оператор parallel() фактически увеличил время от 0,19 до 0,25 с?

Я знаю, что microbenchmarks хрупкие, а parallelism стоит только для больших проблем, но для CPU, даже 0.1s - это вечность, правильно?

Обновление

Я измеряю фреймворком Junit 4 в Eclipse Kepler (он показывает время, затраченное на выполнение теста).

Мои результаты для a, b < 1000 вместо 100:

  • традиционный цикл 186s
  • последовательный поток 193s
  • параллельный поток 55s

Обновление 2 Заменив sum+=Integer.valueOf(c+""); на sum+= c - '0'; (спасибо Peter!), Сбрил 10 целых секунд параллельного метода, доведя его до 45 секунд. Не ожидал такого большого эффекта!

Кроме того, сокращение числа parallelism до количества ядер процессора (4 в моем случае) не помогло, так как оно сократило время до 44,8 с (да, оно добавляет a и b = 0, но я думаю, что это не сильно повлияет на производительность):

int max = IntStream.range(0, 3).parallel().
          .map(m -> IntStream.range(0,250)
          .map(i -> IntStream.range(1, 1000)
          .map(j->.digitSum(BigInteger.valueOf(250*m+i).pow(j)))
          .max().getAsInt()).max().getAsInt()).max().getAsInt();

Ответы

Ответ 1

Я создал быстрый и грязный микро-тест, основанный на вашем коде. Результаты:

: 3192
lambda: 3140
лямбда-параллель: 868

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

public static void main(String[] args) {
    int sum = 0;

    //warmup
    for (int i = 0; i < 100; i++) {
        solve();
        solveLambda();
        solveLambdaParallel();
    }

    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solve();
        }
        long end = System.nanoTime();
        System.out.println("loop: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambda();
        }
        long end = System.nanoTime();
        System.out.println("lambda: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambdaParallel();
        }
        long end = System.nanoTime();
        System.out.println("lambda parallel : " + (end - start) / 1_000_000);
    }
    System.out.println(sum);
}

public static int digitSum(BigInteger x) {
    int sum = 0;
    for (char c : x.toString().toCharArray()) {
        sum += Integer.valueOf(c + "");
    }
    return sum;
}

public static int solve() {
    int max = 0;
    for (int i = 1; i < 100; i++) {
        for (int j = 1; j < 100; j++) {
            max = Math.max(max, digitSum(BigInteger.valueOf(i).pow(j)));
        }
    }
    return max;
}

public static int solveLambda() {
    return  IntStream.range(1, 100)
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

public static int solveLambdaParallel() {
    return  IntStream.range(1, 100)
            .parallel()
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

Я также запускаю его с помощью jmh, который более надежен, чем ручные тесты. Результаты согласуются с выше (микросекунды за звонок):

Benchmark                                Mode   Mean        Units
c.a.p.SO21968918.solve                   avgt   32367.592   us/op
c.a.p.SO21968918.solveLambda             avgt   31423.123   us/op
c.a.p.SO21968918.solveLambdaParallel     avgt   8125.600    us/op

Ответ 2

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

Одна большая разница в вашем коде цикла, вы работаете набор очень мал. Вы рассматриваете только одну максимальную цифровую сумму за раз. Это означает, что код кэширован и у вас очень короткие объекты. В случае stream() вы создаете коллекции, для которых в любой момент времени есть больше в рабочем наборе, используя больше кеша, с большим объемом служебных данных. Я ожидал бы, что ваши времена GC будут длиннее и/или более частыми, а также.

почему вариант потока намного медленнее старого?

Петли довольно хорошо оптимизированы, так как до разработки Java. Их можно очень эффективно сопоставить с оборудованием. Потоки являются довольно новыми и не так сильно оптимизированы.

почему оператор parallel() фактически увеличил время от 0,19 до 0,25 с?

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