Pull to refresh

Comments 44

Я правильно понимаю, что без распараллеливания «быстрый» алгоритм оказался лишь незначительно быстрее наивного?
Нераспараллеленный поток не является «быстрым» алгоритмом, потому что он выполняется слева направо без всяких хитростей. А вот если распараллеленный ограничить одним ядром (например, используя свойство java.util.concurrent.ForkJoinPool.common.parallelism), он будет жрать одно ядро, но выполнится быстрее последовательного потока.
Я бы не назвал ваш алгоритм наивным. Он по сути ближе к древовидному, просто вы устанавливаете фиксированную глубину дерева. Пусть он называется fourBlocks :-) Если уж сравнивать, интересно ещё проверить версию с отдельным подсчётом степеней двойки (причём в параллельном и в последовательном варианте).

Изменённый код бенчмарка
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 {
    private static final BigInteger ONE = BigInteger.valueOf(1);

    @Param({"10", "100", "1000", "10000", "50000"})
    private int n;

    public static BigInteger naive(int n) {
        BigInteger r = ONE;
        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 ONE;
        return IntStream.rangeClosed(2, n).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
    }
    
    public static BigInteger streamedParallel(int n) {
        if(n < 2) return ONE;
        return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
    }

    public static BigInteger fourBlocks(int n) {
        if(n < 2) return ONE;
        BigInteger r1 = ONE, r2 = ONE, r3 = ONE, r4 = ONE;
        int i;
        for (i = n; i > 4; i -= 4)
        {
            r1 = r1.multiply(BigInteger.valueOf(i));
            r2 = r2.multiply(BigInteger.valueOf(i - 1));
            r3 = r3.multiply(BigInteger.valueOf(i - 2));
            r4 = r4.multiply(BigInteger.valueOf(i - 3));
        }
        int mult = i == 4 ? 24 : i == 3 ? 6 : i == 2 ? 2 : 1;
        return r1.multiply(r2).multiply(r3.multiply(r4)).multiply(BigInteger.valueOf(mult));
    }
    
    public static BigInteger streamedShift(int n) {
        if(n < 2) return ONE;
        int p = 0, c = 0;
        while ((n >> p) > 1) {
            p++;
            c += n >> p;
        }
        return IntStream.rangeClosed(2, n).map(i -> i >> Integer.numberOfTrailingZeros(i))
                .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c);
    }

    public static BigInteger streamedParallelShift(int n) {
        if(n < 2) return ONE;
        int p = 0, c = 0;
        while ((n >> p) > 1) {
            p++;
            c += n >> p;
        }
        return IntStream.rangeClosed(2, n).parallel().map(i -> i >> Integer.numberOfTrailingZeros(i))
                .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c);
    }

    @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));
    }

    @Benchmark    
    public void testFourBlocks(Blackhole bh) {
        bh.consume(fourBlocks(n));
    }
    
    @Benchmark    
    public void testStreamedShift(Blackhole bh) {
        bh.consume(streamedShift(n));
    }
    
    @Benchmark    
    public void testStreamedParallelShift(Blackhole bh) {
        bh.consume(streamedParallelShift(n));
    }
}

Результаты будут чуть позже.
Вот результаты:

Benchmark                              (n)  Mode  Cnt       Score       Error  Units
Factorial.testFourBlocks                10  avgt   20       0.409 ±     0.027  us/op
Factorial.testFourBlocks               100  avgt   20       4.752 ±     0.147  us/op
Factorial.testFourBlocks              1000  avgt   20     113.801 ±     7.159  us/op
Factorial.testFourBlocks             10000  avgt   20   10626.187 ±    54.785  us/op
Factorial.testFourBlocks             50000  avgt   20  281522.808 ± 13619.674  us/op
Factorial.testNaive                     10  avgt   20       0.297 ±     0.002  us/op
Factorial.testNaive                    100  avgt   20       5.060 ±     0.036  us/op
Factorial.testNaive                   1000  avgt   20     277.902 ±     1.311  us/op
Factorial.testNaive                  10000  avgt   20   32471.921 ±  1092.640  us/op
Factorial.testNaive                  50000  avgt   20  970355.227 ± 64386.653  us/op
Factorial.testStreamed                  10  avgt   20       0.326 ±     0.002  us/op
Factorial.testStreamed                 100  avgt   20       5.393 ±     0.190  us/op
Factorial.testStreamed                1000  avgt   20     265.550 ±     1.772  us/op
Factorial.testStreamed               10000  avgt   20   29871.366 ±   234.457  us/op
Factorial.testStreamed               50000  avgt   20  894549.237 ±  5453.425  us/op
Factorial.testStreamedParallel          10  avgt   20       6.114 ±     0.500  us/op
Factorial.testStreamedParallel         100  avgt   20      10.719 ±     0.786  us/op
Factorial.testStreamedParallel        1000  avgt   20      72.225 ±     0.509  us/op
Factorial.testStreamedParallel       10000  avgt   20    2811.977 ±    14.599  us/op
Factorial.testStreamedParallel       50000  avgt   20   49501.716 ±   729.646  us/op
Factorial.testStreamedParallelShift     10  avgt   20       6.684 ±     0.549  us/op
Factorial.testStreamedParallelShift    100  avgt   20      11.176 ±     0.779  us/op
Factorial.testStreamedParallelShift   1000  avgt   20      71.056 ±     3.918  us/op
Factorial.testStreamedParallelShift  10000  avgt   20    2641.108 ±   142.571  us/op
Factorial.testStreamedParallelShift  50000  avgt   20   46480.544 ±   405.648  us/op
Factorial.testStreamedShift             10  avgt   20       0.402 ±     0.006  us/op
Factorial.testStreamedShift            100  avgt   20       5.086 ±     0.039  us/op
Factorial.testStreamedShift           1000  avgt   20     237.279 ±     1.566  us/op
Factorial.testStreamedShift          10000  avgt   20   27572.709 ±   135.489  us/op
Factorial.testStreamedShift          50000  avgt   20  874699.213 ± 53645.087  us/op

fourBlocks сравним с наивным при n = 100 и даёт существенный выигрыш уже на 1000. Думаю, внутри 18-кратного увеличения производительности параллельного метода выигрыш от параллелизма максимум четырёхкратный (всё же 4 ядра HT — это не 8 ядер), а остальное — от правильного разбиения данных, так как параллельный алгоритм выигрывает у вашего всего в 5.7 раз при n = 50000. Битовый сдвиг вопреки ожиданиям большого прироста не дал. Вероятно, внутри себя BigInteger сам хорошо с этим справляется и незначительную экономию мы видим лишь за счёт уменьшения потребляемой памяти и облегчения работы сборщику мусора.
Спасибо, интересные результаты. Жалко на шарпе не могу проверить — не нашел пока бенчмарков, поддерживающих многопоток. Существующие только запускают на неактивном ядре все тесты, чтобы от переключения контекста на «виндовых» ядрах не менялись результаты тестирования. Тем более, стандартная библиотека по каким-то эвристикам не всегда параллелит на все ядра, типа если задача не тяжелая… Хотя очевидно, что выигрыш мог бы быть достигнут этим.
Где-нибудь можно посмотреть исходники этих реализаций? *зачёркнуто* Чукча не читатель
У меня получилось вот так:

Naive
2,214s
Tree
1,118s
OptimizedThreading
0,273s

Время — среднее за 10 проходов, каких-то исключительных пиков не наблюдалось в отдельных методах
Система — Core i5 2500, Win7 x64

Другими словами — мне дописывать статью, или уже бессмысленно? :)

Я не знаю, о чём вы собрались писать статью :-) Моя была о том, что Java Stream API исключительно круто сочетается с алгоритмами вида «разделяй и властвуй». Если вы хотите о чём-то другом написать, пожалуйста, пишите :-)
Эх, аналог на шарпе ускоряет максимум в 2 раза, увы… Даже не знаю, кого винить, оригинальную имплементацию BigInteger или кривой TPL…

static BigInteger StreamedParallel(int n)
{
    return n < 2 ? 1 : Enumerable.Range(2, n - 1).AsParallel().Aggregate(BigInteger.One, (acc, elm) => acc * elm, (i, j) => i * j, i => i);
}


Особенно печально, что у вас StreamedParallel выполняется за 700 микросекунд, в то время как на шарпе это 700 миллисекунд. Ну и ускорение относительно naive только в 2 раза, как я уже сказал… Всегда считал, что шарп быстрее джавы во всем. Серьезный удар.
Честно говоря, даже не верится, что на джаве такие результаты. Вон, человек скидывал тестирование на GMP, даже на плюсах получается 23мс, что в 4 раза больше testStreamed 5,5 мс, в которой нет никакой параллелизации, на которую можно было бы списать такой прирост.
Вы путаете что-то. В колонке (n) число, от которого брали факториал. Вас должны интересовать строки с n = 50000. А результата 700 микросекунд я вообще не вижу.
Блин, я осел, всё это время смотрел на колонку СКО, а не на результаты измерений. Тогда всё в порядке, извиняюсь за ложную тревогу.

Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
x19 от простого мультитридинга быть не может. В идеальном варианте только ускорение в N раз, где N — число физических ядер. Там ещё что-то происходит.

Мне на await/async удалось получить ускорение порядка 3.5 раза на 4х ядрах, но там есть пара извращений.
Если использовать целочисленные вектора размерности 3 или 4 то можно еще быстрее посчитать?
Не понимаю, о чём вы. Приведите код, иллюстрирующий вашу идею.
Я про OpenGL www.opengl.org/wiki/Data_Type_(GLSL)#Vectors

Если правильно понял идею, то формируя входной буфер из целочисленных векторов int4(x,y,z,w) и скармливая шейдеру, который для каждого вектора посчитает произведение его координат, шейдер вернет новый буфер в 4 раза короче исходного, его снова отдаем на вычисление тому же шейдеру и тд, пока не останется буфер из одного числа. Таким образом используя ядра GPU, можно достигнуть большей степени параллелизации. Единственное ограничение 32-битный int, так мы быстро упремся.
У меня очень маленький опыт программирования шейдеров. Тут основная проблема в том, что нужно перемножать числа длиной в тысячи и десятки тысяч цифр. Умножение длинных чисел весьма нетривиальная процедура. В Java BigInteger используется три алгоритма в зависимости от длины чисел — наивный, алгоритм Карацубы и алгоритм Тума—Кука. GPU не заточены напрямую под длинную арифметику, вам потребуется библиотека. Не знаю, насколько хорошо с этим в GLSL.
Факториал 12 уже не влезает в int32, соответственно 24! не влезет уже в лонги, поэтому на видюхе вряд ли что удастся посчитать. Если изобрести собственный Biginteger, чтобы считать на видео/SSE, манипулируя только байтами-вордами да интами, то тогда наверное можно.
Вангую, что в Open CL на крайний случай есть 64-bit и вектора длиной до 16. Вполне вероятно, что и аналогичные алгоритмы тоже могут иметь место.
Гм. А как значения из таблицы перевести в среднее время? Подскажите для не знакомых с этим фреймворком.
Колонка Score — это и есть среднее время в микросекундах.
Score = время работы в микросекундах. Там в последнем столбце единицы измерения указаны.
А как этот фреймворк параллелит длинное умножение? Мне просто интересно, откуда 20ти кратный прирост, что я упустил
И не смогли бы вы запустить на вашей машине оригинальный код?
Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
Каждое отдельное умножение не параллелится, разумеется. Параллелятся ветки дерева умножений. Не сказал бы, что это фреймворк — это стандартная библиотека Java. Фреймворк JMH использовался только для замера производительности, а сама реализация факториала (в самом верху поста) не требует ничего кроме Java SE 1.8.

Сравнивать напрямую Java и C# может быть не очень уместно. Не факт, что реализация BigInteger в них похожа. И представлять в памяти, и умножать длинные целые можно кучей способов.

А что требуется установить, чтобы скомпилировать ваш код? Я с шарпами как-то не работаю. Лучше вы мой код у себя запустите ;-)
Я пытался параллелить только корень, но это уже даёт 100% загрузку процессора. В идеале, распаралеливание, на 4 потока может дать только 4х кратный прирост.
Узким местом, впрочем, оказалось умножение последнего элемента — при любая финальной комбинация вызывается за 0.54 секунды

Собственно вот (однократная проверка, быстродействие, по наблюдениям, плавает в пределах 5%):

2-25000: 00:00:00.2458574 // thread 1
25001-50000: 00:00:00.3246583 // thread 2
finalizing: 00:00:00.5395141
total: 00:00:00.8882113

C# использует алгоритм Карацубы для умножения длинных чисел.
Но умножение, как мне показалось, реализовано крайне неэффективно. Собственно, тот же битовый сдвиг даёт прирост скорости почти в 2 раза для финальной операции. Собственно большенство плясок там именно вокруг этого.

Для того, чтобы скомпилировать код можно обойтись одним .NET Framework'ом, но лучше — какую-нибудь Visual Studio с поддержкой C#. Скинуть код смогу только этак в 22:00 МСК
В Java для таких больших чисел уже Тоом—Кук используется. Ну очевидно, что у Java получается гораздо быстрее сделать последнее умножение. Я добавил отладочный вывод, получилось, что задача разбивается на 16 последовательных подзадач 2..3125, 3126..6250 и т. д. до 46876..50000, а потом результаты перемножаются древовидным способом, но по факту всё равно получается, что последнее умножение — это произведение результатов 2..25000 и 25001..50000. В перемножаемых числах 329183 и 379175 бит. Возможно, в Java реализация умножения действительно сделана лучше. Либо вам всё же стоит разогреть свой код.
Вряд ли в С# Карацуба, я больше склоняюсь к тому что там немного оптимизированный квадрат
Я тоже руководствовался этим ответом, но надо бы декомпилировать System.Numerics. Я этого не сделал из-за того, что рефлектор с первого раза неймспейс не подцепил :)
Существует таинство открытых исходников .Net, известное только посвященным. Для просмотра исходников не нужен рефлектор, можно даже увидеть их с комментариями, оригинальными названиями переменных и директивами условной компиляции (чего декомпилятор не умеет и не будет уметь никогда)
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigInteger.cs,1543
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigIntegerBuilder.cs,609
Лень — она такая, искать посвящённых тоже не хотелось, хотелось кодить :)
Вот здесь пишут что квадрат. Я не специалист в дотнете, проверить сам не могу. Но асимптотика у него довольно странная, это да.
Спасибо за интересную статью. Хотелось бы ещё в тесте увидеть такую реализацию факториала:
public static BigInteger recursiveFactorial(int i) {
BigInteger r = BigInteger.valueOf(1);
    if (i == 1) {
	return r;
    }
    r = BigInteger.valueOf(i);
    return r.multiply(factorial(i - 1));
}
Нет, не хочется :)

А если серьезно, то имхо, стек сдохнет. Сколько каждый BigInteger занимает памяти, умножаем на по крайней мере 50000 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.

Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
Java-компилятор не может развернуть хвостовой вызов.
Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
В clojure есть специальная форма (recur ...), которая позволяет сделать вид, что выполняется tail recursive вызов.

В scala есть автоматическая оптимизация tail rec с ограничениями (proper tail call). Т. е. оптимизируется только в случае возможности переиспользования stack frame. Плюс есть аннотация @tailrec, гарантирующая, что при невозможности этой оптимизации будет compile-time error. Причём, в случае scala для применения оптимизации необходимо гарантировать, что метод не будет переопределён (private или final). См. tech.pro/blog/2112/scala-tail-recursion-optimisation-and-comparison-to-java
Я всё это знаю. Я говорил конкретно про Java. В Java хвостовая рекурсия, насколько я понимаю, не может быть реализована без нарушения JLS.
А она не отдана просто на откуп JIT'у? Т. е. unspecified? На SO видел что-то в этом роде, но пруфлинки на сайт ibm уже к тому моменту протухли.
В .Net также есть директива хвостового вызова (вернее опкод tail. — 0xFE 0x14). Да и в джаве появится, раз пошли функциональные эти приколы.
Не похоже, чтобы это было в приоритете. На JPoint ничего про это не говорили.
Sign up to leave a comment.

Articles