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));
}
}Результаты будут чуть позже.
Вот результаты:
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/opfourBlocks сравним с наивным при 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
Другими словами — мне дописывать статью, или уже бессмысленно? :)
У меня получилось вот так:
Naive
2,214s
Tree
1,118s
OptimizedThreading
0,273s
Время — среднее за 10 проходов, каких-то исключительных пиков не наблюдалось в отдельных методах
Система — Core i5 2500, Win7 x64
Другими словами — мне дописывать статью, или уже бессмысленно? :)
Я не знаю, о чём вы собрались писать статью :-) Моя была о том, что Java Stream API исключительно круто сочетается с алгоритмами вида «разделяй и властвуй». Если вы хотите о чём-то другом написать, пожалуйста, пишите :-)
Эх, аналог на шарпе ускоряет максимум в 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 раза, как я уже сказал… Всегда считал, что шарп быстрее джавы во всем. Серьезный удар.
Честно говоря, даже не верится, что на джаве такие результаты. Вон, человек скидывал тестирование на GMP, даже на плюсах получается 23мс, что в 4 раза больше testStreamed 5,5 мс, в которой нет никакой параллелизации, на которую можно было бы списать такой прирост.
Вы путаете что-то. В колонке (n) число, от которого брали факториал. Вас должны интересовать строки с n = 50000. А результата 700 микросекунд я вообще не вижу.
Блин, я осел, всё это время смотрел на колонку СКО, а не на результаты измерений. Тогда всё в порядке, извиняюсь за ложную тревогу.
Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
А я правильно понимаю, что таким же образом можно распараллелить и посчитать на GPU?
В принципе можно, но с помощью Java и в одну строчку — вряд ли. Ждём результатов проекта Sumatra.
Если использовать целочисленные вектора размерности 3 или 4 то можно еще быстрее посчитать?
Не понимаю, о чём вы. Приведите код, иллюстрирующий вашу идею.
Я про 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, так мы быстро упремся.
У меня очень маленький опыт программирования шейдеров. Тут основная проблема в том, что нужно перемножать числа длиной в тысячи и десятки тысяч цифр. Умножение длинных чисел весьма нетривиальная процедура. В Java BigInteger используется три алгоритма в зависимости от длины чисел — наивный, алгоритм Карацубы и алгоритм Тума—Кука. GPU не заточены напрямую под длинную арифметику, вам потребуется библиотека. Не знаю, насколько хорошо с этим в GLSL.
Факториал 12 уже не влезает в int32, соответственно 24! не влезет уже в лонги, поэтому на видюхе вряд ли что удастся посчитать. Если изобрести собственный Biginteger, чтобы считать на видео/SSE, манипулируя только байтами-вордами да интами, то тогда наверное можно.
Вангую, что в Open CL на крайний случай есть 64-bit и вектора длиной до 16. Вполне вероятно, что и аналогичные алгоритмы тоже могут иметь место.
Гм. А как значения из таблицы перевести в среднее время? Подскажите для не знакомых с этим фреймворком.
А как этот фреймворк параллелит длинное умножение? Мне просто интересно, откуда 20ти кратный прирост, что я упустил
И не смогли бы вы запустить на вашей машине оригинальный код?
Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
И не смогли бы вы запустить на вашей машине оригинальный код?
Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
Каждое отдельное умножение не параллелится, разумеется. Параллелятся ветки дерева умножений. Не сказал бы, что это фреймворк — это стандартная библиотека Java. Фреймворк JMH использовался только для замера производительности, а сама реализация факториала (в самом верху поста) не требует ничего кроме Java SE 1.8.
Сравнивать напрямую Java и C# может быть не очень уместно. Не факт, что реализация BigInteger в них похожа. И представлять в памяти, и умножать длинные целые можно кучей способов.
А что требуется установить, чтобы скомпилировать ваш код? Я с шарпами как-то не работаю. Лучше вы мой код у себя запустите ;-)
Сравнивать напрямую 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 МСК
Узким местом, впрочем, оказалось умножение последнего элемента — при любая финальной комбинация вызывается за 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.BigInteger uses the Karatsuba algorithm or standard schoolbook multiplication, depending on the size of
stackoverflow.com/a/3066062/2559709
Я тоже руководствовался этим ответом, но надо бы декомпилировать 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
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 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.
Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
А если серьезно, то имхо, стек сдохнет. Сколько каждый BigInteger занимает памяти, умножаем на по крайней мере 50000 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.
Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
Java-компилятор не может развернуть хвостовой вызов.
Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
В 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-javaА мне бы не хотелось её видеть :-)
Sign up to leave a comment.
Вычисление факториала или мощь Stream API