Отличный вопрос
Эта многопоточная реализация функции Фибоначчи не быстрее однопоточной версии. Эта функция была показана только в посте блога как игрушечный пример того, как работают новые возможности потоков, подчеркнув, что она позволяет создавать множество потоков в различных функциях, и планировщик определит оптимальную рабочую нагрузку.
Проблема в том, что @spawn
нетривиальные накладные расходы 1µs
, поэтому, если вы создаете поток для выполнения задачи, которая занимает меньше 1µs
, вы, вероятно, повредите своей производительности. Рекурсивное определение fib(n)
имеет экспоненциальную временную сложность порядка 1.6180^n
[1], поэтому при вызове fib(43)
вы создаете что-то из 1.6180^43
потоков порядка . Если каждому из них требуется 1µs
порождение, потребуется около 16 минут, чтобы порождать и планировать необходимые потоки, и это даже не учитывает время, которое требуется для выполнения фактических вычислений и повторного объединения / синхронизации потоков, что занимает даже больше времени.
Подобные вещи, когда вы создаете поток для каждого шага вычисления, имеют смысл, только если каждый шаг вычисления занимает больше времени по сравнению с @spawn
накладными расходами.
Обратите внимание, что есть работа по уменьшению накладных расходов @spawn
, но из-за самой физики многоядерных силиконовых чипов я сомневаюсь, что это когда-нибудь может быть достаточно быстрым для вышеуказанной fib
реализации.
Если вам интересно, как мы могли бы изменить многопоточную fib
функцию, чтобы она была полезной, проще всего было бы создать fib
поток, только если мы думаем, что это займет значительно больше времени, чем 1µs
выполнение. На моей машине (работающей на 16 физических ядрах) я получаю
function F(n)
if n < 2
return n
else
return F(n-1)+F(n-2)
end
end
julia> @btime F(23);
122.920 μs (0 allocations: 0 bytes)
так что это на два порядка больше стоимости порождения нити. Это похоже на хорошее сокращение для использования:
function fib(n::Int)
if n < 2
return n
elseif n > 23
t = @spawn fib(n - 2)
return fib(n - 1) + fetch(t)
else
return fib(n-1) + fib(n-2)
end
end
Теперь, если я буду следовать правильной методологии тестирования BenchmarkTools.jl [2], я найду
julia> using BenchmarkTools
julia> @btime fib(43)
971.842 ms (1496518 allocations: 33.64 MiB)
433494437
julia> @btime F(43)
1.866 s (0 allocations: 0 bytes)
433494437
@Anush спрашивает в комментариях: это в 2 раза быстрее при использовании 16 ядер, что кажется. Можно ли приблизить что-то ближе к 16-кратному ускорению?
Да, это так. Проблема с вышеприведенной функцией заключается в том, что тело функции больше, чем у F
, с большим количеством условных выражений, порождением функции / потока и всем этим. Я приглашаю вас сравнить @code_llvm F(10)
@code_llvm fib(10)
. Это значит, что fib
Юлии гораздо сложнее оптимизировать. Эти дополнительные накладные расходы имеют огромное значение для небольших n
случаев.
julia> @btime F(20);
28.844 μs (0 allocations: 0 bytes)
julia> @btime fib(20);
242.208 μs (20 allocations: 320 bytes)
о нет! весь этот дополнительный код, который никогда не затрагивается, n < 23
замедляет нас на порядок! Хотя есть простое решение: когда n < 23
не возвращаться к fib
, а вызывать однопоточное F
.
function fib(n::Int)
if n > 23
t = @spawn fib(n - 2)
return fib(n - 1) + fetch(t)
else
return F(n)
end
end
julia> @btime fib(43)
138.876 ms (185594 allocations: 13.64 MiB)
433494437
что дает результат ближе к тому, что мы ожидаем для стольких потоков.
[1] https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/
[2] @btime
Макрос BenchmarkTools из BenchmarkTools.jl будет запускать функции несколько раз, пропуская время компиляции и усредненные результаты.
fib
это труднее Джулию оптимизируют чемF
, поэтому мы просто использоватьF
вместоfib
дляn< 23
. Я отредактировал свой ответ с более глубоким объяснением и примером.Threads.nthreads()
для вас? Я подозреваю, что у вас может быть Джулия, работающая только с одним потоком.@Anush
В качестве примера использования запоминания и многопоточности вручную
Но ускорение произошло из-за запоминания, а не из-за многопоточности. Урок здесь заключается в том, что мы должны лучше продумать алгоритмы перед многопоточностью.
источник