Comments 44
Я правильно понимаю, что без распараллеливания «быстрый» алгоритм оказался лишь незначительно быстрее наивного?
0
Нераспараллеленный поток не является «быстрым» алгоритмом, потому что он выполняется слева направо без всяких хитростей. А вот если распараллеленный ограничить одним ядром (например, используя свойство java.util.concurrent.ForkJoinPool.common.parallelism), он будет жрать одно ядро, но выполнится быстрее последовательного потока.
+2
Добавьте, пожалуйста, улучшенный наивный алгоритм в сравнение, интересно, сколько получится
+1
Я бы не назвал ваш алгоритм наивным. Он по сути ближе к древовидному, просто вы устанавливаете фиксированную глубину дерева. Пусть он называется 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));
}
}
Результаты будут чуть позже.
0
Вот результаты:
fourBlocks сравним с наивным при n = 100 и даёт существенный выигрыш уже на 1000. Думаю, внутри 18-кратного увеличения производительности параллельного метода выигрыш от параллелизма максимум четырёхкратный (всё же 4 ядра HT — это не 8 ядер), а остальное — от правильного разбиения данных, так как параллельный алгоритм выигрывает у вашего всего в 5.7 раз при n = 50000. Битовый сдвиг вопреки ожиданиям большого прироста не дал. Вероятно, внутри себя BigInteger сам хорошо с этим справляется и незначительную экономию мы видим лишь за счёт уменьшения потребляемой памяти и облегчения работы сборщику мусора.
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 сам хорошо с этим справляется и незначительную экономию мы видим лишь за счёт уменьшения потребляемой памяти и облегчения работы сборщику мусора.
0
Спасибо, интересные результаты. Жалко на шарпе не могу проверить — не нашел пока бенчмарков, поддерживающих многопоток. Существующие только запускают на неактивном ядре все тесты, чтобы от переключения контекста на «виндовых» ядрах не менялись результаты тестирования. Тем более, стандартная библиотека по каким-то эвристикам не всегда параллелит на все ядра, типа если задача не тяжелая… Хотя очевидно, что выигрыш мог бы быть достигнут этим.
0
Где-нибудь можно посмотреть исходники этих реализаций? *зачёркнуто* Чукча не читатель
У меня получилось вот так:
Naive
2,214s
Tree
1,118s
OptimizedThreading
0,273s
Время — среднее за 10 проходов, каких-то исключительных пиков не наблюдалось в отдельных методах
Система — Core i5 2500, Win7 x64
Другими словами — мне дописывать статью, или уже бессмысленно? :)
У меня получилось вот так:
Naive
2,214s
Tree
1,118s
OptimizedThreading
0,273s
Время — среднее за 10 проходов, каких-то исключительных пиков не наблюдалось в отдельных методах
Система — Core i5 2500, Win7 x64
Другими словами — мне дописывать статью, или уже бессмысленно? :)
+1
Я не знаю, о чём вы собрались писать статью :-) Моя была о том, что Java Stream API исключительно круто сочетается с алгоритмами вида «разделяй и властвуй». Если вы хотите о чём-то другом написать, пожалуйста, пишите :-)
+1
Эх, аналог на шарпе ускоряет максимум в 2 раза, увы… Даже не знаю, кого винить, оригинальную имплементацию BigInteger или кривой TPL…
Особенно печально, что у вас StreamedParallel выполняется за 700 микросекунд, в то время как на шарпе это 700 миллисекунд. Ну и ускорение относительно naive только в 2 раза, как я уже сказал… Всегда считал, что шарп быстрее джавы во всем. Серьезный удар.
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 раза, как я уже сказал… Всегда считал, что шарп быстрее джавы во всем. Серьезный удар.
0
Честно говоря, даже не верится, что на джаве такие результаты. Вон, человек скидывал тестирование на GMP, даже на плюсах получается 23мс, что в 4 раза больше testStreamed 5,5 мс, в которой нет никакой параллелизации, на которую можно было бы списать такой прирост.
0
Вы путаете что-то. В колонке (n) число, от которого брали факториал. Вас должны интересовать строки с n = 50000. А результата 700 микросекунд я вообще не вижу.
0
Блин, я осел, всё это время смотрел на колонку СКО, а не на результаты измерений. Тогда всё в порядке, извиняюсь за ложную тревогу.
Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
+1
А я правильно понимаю, что таким же образом можно распараллелить и посчитать на GPU?
0
В принципе можно, но с помощью Java и в одну строчку — вряд ли. Ждём результатов проекта Sumatra.
+1
Если использовать целочисленные вектора размерности 3 или 4 то можно еще быстрее посчитать?
0
Не понимаю, о чём вы. Приведите код, иллюстрирующий вашу идею.
0
Я про OpenGL www.opengl.org/wiki/Data_Type_(GLSL)#Vectors
Если правильно понял идею, то формируя входной буфер из целочисленных векторов int4(x,y,z,w) и скармливая шейдеру, который для каждого вектора посчитает произведение его координат, шейдер вернет новый буфер в 4 раза короче исходного, его снова отдаем на вычисление тому же шейдеру и тд, пока не останется буфер из одного числа. Таким образом используя ядра GPU, можно достигнуть большей степени параллелизации. Единственное ограничение 32-битный int, так мы быстро упремся.
Если правильно понял идею, то формируя входной буфер из целочисленных векторов int4(x,y,z,w) и скармливая шейдеру, который для каждого вектора посчитает произведение его координат, шейдер вернет новый буфер в 4 раза короче исходного, его снова отдаем на вычисление тому же шейдеру и тд, пока не останется буфер из одного числа. Таким образом используя ядра GPU, можно достигнуть большей степени параллелизации. Единственное ограничение 32-битный int, так мы быстро упремся.
0
У меня очень маленький опыт программирования шейдеров. Тут основная проблема в том, что нужно перемножать числа длиной в тысячи и десятки тысяч цифр. Умножение длинных чисел весьма нетривиальная процедура. В Java BigInteger используется три алгоритма в зависимости от длины чисел — наивный, алгоритм Карацубы и алгоритм Тума—Кука. GPU не заточены напрямую под длинную арифметику, вам потребуется библиотека. Не знаю, насколько хорошо с этим в GLSL.
0
Факториал 12 уже не влезает в int32, соответственно 24! не влезет уже в лонги, поэтому на видюхе вряд ли что удастся посчитать. Если изобрести собственный Biginteger, чтобы считать на видео/SSE, манипулируя только байтами-вордами да интами, то тогда наверное можно.
0
Вангую, что в Open CL на крайний случай есть 64-bit и вектора длиной до 16. Вполне вероятно, что и аналогичные алгоритмы тоже могут иметь место.
0
Гм. А как значения из таблицы перевести в среднее время? Подскажите для не знакомых с этим фреймворком.
0
А как этот фреймворк параллелит длинное умножение? Мне просто интересно, откуда 20ти кратный прирост, что я упустил
И не смогли бы вы запустить на вашей машине оригинальный код?
Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
И не смогли бы вы запустить на вашей машине оригинальный код?
Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
0
Каждое отдельное умножение не параллелится, разумеется. Параллелятся ветки дерева умножений. Не сказал бы, что это фреймворк — это стандартная библиотека Java. Фреймворк JMH использовался только для замера производительности, а сама реализация факториала (в самом верху поста) не требует ничего кроме Java SE 1.8.
Сравнивать напрямую Java и C# может быть не очень уместно. Не факт, что реализация BigInteger в них похожа. И представлять в памяти, и умножать длинные целые можно кучей способов.
А что требуется установить, чтобы скомпилировать ваш код? Я с шарпами как-то не работаю. Лучше вы мой код у себя запустите ;-)
Сравнивать напрямую Java и C# может быть не очень уместно. Не факт, что реализация BigInteger в них похожа. И представлять в памяти, и умножать длинные целые можно кучей способов.
А что требуется установить, чтобы скомпилировать ваш код? Я с шарпами как-то не работаю. Лучше вы мой код у себя запустите ;-)
0
Я пытался параллелить только корень, но это уже даёт 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 МСК
Узким местом, впрочем, оказалось умножение последнего элемента — при любая финальной комбинация вызывается за 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 МСК
0
В Java для таких больших чисел уже Тоом—Кук используется. Ну очевидно, что у Java получается гораздо быстрее сделать последнее умножение. Я добавил отладочный вывод, получилось, что задача разбивается на 16 последовательных подзадач 2..3125, 3126..6250 и т. д. до 46876..50000, а потом результаты перемножаются древовидным способом, но по факту всё равно получается, что последнее умножение — это произведение результатов 2..25000 и 25001..50000. В перемножаемых числах 329183 и 379175 бит. Возможно, в Java реализация умножения действительно сделана лучше. Либо вам всё же стоит разогреть свой код.
0
Вряд ли в С# Карацуба, я больше склоняюсь к тому что там немного оптимизированный квадрат
0
System.Numerics.BigInteger uses the Karatsuba algorithm or standard schoolbook multiplication, depending on the size of
stackoverflow.com/a/3066062/2559709
0
Я тоже руководствовался этим ответом, но надо бы декомпилировать System.Numerics. Я этого не сделал из-за того, что рефлектор с первого раза неймспейс не подцепил :)
0
Существует таинство открытых исходников .Net, известное только посвященным. Для просмотра исходников не нужен рефлектор, можно даже увидеть их с комментариями, оригинальными названиями переменных и директивами условной компиляции (чего декомпилятор не умеет и не будет уметь никогда)
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigInteger.cs,1543
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigIntegerBuilder.cs,609
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigInteger.cs,1543
http://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigIntegerBuilder.cs,609
+1
Спасибо за интересную статью. Хотелось бы ещё в тесте увидеть такую реализацию факториала:
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));
}
-1
Нет, не хочется :)
А если серьезно, то имхо, стек сдохнет. Сколько каждый BigInteger занимает памяти, умножаем на по крайней мере 50000 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.
Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
А если серьезно, то имхо, стек сдохнет. Сколько каждый BigInteger занимает памяти, умножаем на по крайней мере 50000 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.
Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
0
Java-компилятор не может развернуть хвостовой вызов.
Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
+2
В clojure есть специальная форма (recur ...), которая позволяет сделать вид, что выполняется tail recursive вызов.
В scala есть автоматическая оптимизация tail rec с ограничениями (proper tail call). Т. е. оптимизируется только в случае возможности переиспользования stack frame. Плюс есть аннотация
В 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-java0
Я всё это знаю. Я говорил конкретно про Java. В Java хвостовая рекурсия, насколько я понимаю, не может быть реализована без нарушения JLS.
+1
В .Net также есть директива хвостового вызова (вернее опкод tail. — 0xFE 0x14). Да и в джаве появится, раз пошли функциональные эти приколы.
0
А мне бы не хотелось её видеть :-)
+1
Sign up to leave a comment.
Вычисление факториала или мощь Stream API