很好的问题。
这个斐波那契函数的多线程实现并不比单线程版本更快。该函数仅作为博客文章中新线程功能的玩具示例,强调它允许在不同的函数中生成许多线程,并且调度程序将找出最佳工作负载。
问题在于@spawn
有一个非平凡的开销约为1µs
,因此如果你生成一个线程来执行少于1µs
的任务,你可能会降低性能。递归定义的fib(n)
的时间复杂度是指数级的,阶数为1.6180^n
[1],因此当你调用fib(43)
时,你生成了大约1.6180^43
数量级的线程。如果每个线程花费1µs
来生成,仅生成和调度所需的线程就需要大约16分钟,甚至还没有考虑执行实际计算和重新合并/同步线程所需的时间。
像这样为计算的每个步骤生成一个线程只有在每个计算步骤相对于@spawn
开销需要较长时间时才有意义。
请注意,有关减少@spawn
开销的工作正在进行中,但由于多核硅芯片的物理特性,我怀疑它永远无法足够快地处理上述fib
实现。
如果你想知道如何修改线程化的fib
函数以使其真正受益,最简单的方法是仅在我们认为运行时间显着长于1µs
时才生成一个fib
线程。在我的机器上(运行在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在评论中问道:似乎使用16个核心可以加速2倍。是否可能获得更接近16倍的加速?
是的,可以。上述函数的问题在于函数体比F
大得多,有许多条件语句、函数/线程生成等。我邀请您比较@code_llvm F(10)
和@code_llvm fib(10)
。这意味着fib
对julia来说更难优化。对于小的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] BenchmarkTools.jl中的BenchmarkTools @btime
宏将运行函数多次,跳过编译时间并平均结果。
fib
对于 Julia 来说比F
更难优化,因此我们只需在n<23
时使用F
而不是fib
。我已经编辑了我的答案,并提供了更详细的解释和示例。 - MasonThreads.nthreads()
输出是什么?我怀疑你可能只使用了单个线程来运行Julia。 - Mason