为什么我们没有通过 PSeq 获得性能提升?
Why do we not get a performance improvement with PSeq?
问题
我们认为并行处理每个 "tail permutation" 会减少该算法的实际 运行 时间。为什么不呢?如果我们完全可以配置 PSeq 来改善 运行 时间,我们会怎样?
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else ([], permute xs.Tail)
// Why do we not get a performance
// improvement when we use PSeq here
// relative to using Seq?
||> PSeq.fold (fun acc ps ->
(insertAtEach xs.Head ps)@acc)
permute ["A";"B";"C"] |> ignore
我们认为排列工作将按如下方式拆分,并且算法的 insertAtEach
阶段将并行工作。
[C]
[BC] [CB]
[ABC] [BCA] [BCA] [ACB] [CAB] [CBA]
CPU01 CPU02
即使我们使用 permute [0..9]
这样的大初始列表,它实际上在并行时更慢。我们还没有弄清楚 withDegreeOfParallelism
和相关的 PSeq 选项是否有帮助。
一边
下面是代码清单的其余部分:
let put a q xs =
([], xs)
||> Seq.fold (fun acc x ->
if x = q then a::x::acc
else x::acc)
|> List.rev
// Insert x at each possible location in xs
let insertAtEach a xs =
([a::xs], xs)
||> Seq.fold (fun acc x ->
(put a x xs)::acc)
第一部分:“为什么不是吗?”
因为每次转换(转换)从SEQ -- -- --
process-execution调度到PAR -- || ||
需要做一些努力,这证明它们确实明显物化了 [TIME]
-domain 和 [SPACE]
-domain setup + termination overhead costs.
有关详细信息,请查看 re-formulated Amdahl's Law, particularly the naive-form Fig.1 与 部分:批评 以及后来得出的 overhead-strict re-formulation法律。
没有办法避免纳税和 overhead-costs 被支付...
在 parallel-computing 中,在 just-concurrent 计算环境中稍微不那么密集,确实很容易付出比接受 多的方式作为交换。
此外,在 Whosebug 上,使用搜索标签 parallelism-amdahl,您可以在此处找到 大量示例 和惊喜 post,您可以看到很多具有基准 overhead-costs 的示例(如果用户保持 open-minded 并且足够系统地确实 运行 他们并记录和 post 现实的 [TIME]
域成本) .
第二部分:“如何 如果我们可以......改善运行宁时间?“
没有人可以逃避 overhead-strict,atomic-processing 意识到 re-formulated 阿姆达尔定律。
没有人可以。
然而,如果在初始产品规划期间使用此工具,它还具有 design-side 优势。
产生的净处理开销受资源池大小、强制性 data-transfers、(未)避免共享 and/or 其他形式 mutual-dependencies、结果大小的影响在 {
并发 |
并行 }
处理终止时返回 -- 所有这些 add-on 成本都可以系统地进行基准测试 ,以便很好地理解这样做的成本,包括内存分配成本、垃圾收集或类似的现实操作方法释放开销。
给定一个已知的部署生态系统,在进入pure-serial/分布式/并行流程执行时,没有人被禁止使用基准数据进行系统costs-benefits评估。
鉴于此 fine-grained 知识已进行基准测试,
它可以作为解决困境的公平指标:
即 - PAR -- ||||
部分的最小大小是多少,以便它至少支付自己的 un-avoidable { setup + termination }
-overhead-add-on-成本?
这两个都没有做过,人们会感到惊讶,re-factoring 的过程与 直接 "negative" 或worse-than-expected 处理性能改进的一种方式。
总是:基准,基准,基准。
下一个:干脆不要选择更贵的方式
PSeq.fold
并不像您想象的那样。 PSeq.fold
实际上根本不是平行的。它是连续的。
您不能只是在算法中间的某个地方丢出 "parallel" 这个词并希望获得最好的结果。这不是并行化的工作方式。你必须真正理解发生了什么,什么是并行发生的,什么是顺序的,什么原则上可以并行,什么不能。
以fold
为例:它将提供的折叠函数应用于序列的每个元素和上一次调用的结果。由于每个下一个调用都必须有上一个调用的结果才能执行,所以很明显 fold
根本不能并行执行。必须是顺序的。事实上,如果您查看其 source code,这就是 PSeq.fold
实际执行的操作。因此,每次转换为 ParallelSequence
都会产生一些开销,但没有任何收获。
现在,如果您仔细查看您的算法,您可以梳理出可并行化的部分。你的算法是做什么的:
- 递归计算尾部排列。
- 对于这些排列中的每一个,通过在每个索引处插入头部来分解它。
- 连接第 2 步的所有结果。
当你这样说时,很容易看出第 2 步除了它本身之外并不真正依赖于任何东西。每个尾部排列都与其他所有排列完全分开处理。
当然,仅查看您的源代码并不能证明这一点,因为您已将步骤 2 和步骤 3 组合在一个表达式中 (insertAtEach xs.Head ps)@acc
,但使用以下通用标识很容易区分:
xs |> fold (fun a x -> g a (f x))
===
xs |> map f |> fold (fun a x -> g a x)
也就是说,不是将函数 f
应用于 fold
期间的每个元素 x
,而是可以使用 map
将它应用于每个元素 "in advance" ].
将这个想法应用到你的算法中,你会得到:
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else permute xs.Tail
|> Seq.map (insertAtEach xs.Head)
|> Seq.fold (fun acc ps -> ps@acc) []
现在很容易看出 Seq.map
步骤是可并行化的步骤:map
独立于其他元素将函数应用于每个元素,因此它 可以 原则上并行工作。只需将 Seq
替换为 PSeq
即可获得并行版本:
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else permute xs.Tail
|> PSeq.map (insertAtEach xs.Head)
|> PSeq.fold (fun acc ps -> ps@acc) []
PSeq
是否确实并行执行 map
是另一回事,但这应该很容易根据经验验证。
事实上,在我的机器上,对于 7 到 10 个元素的列表(11 个元素的列表导致 OOM),并行版本始终优于顺序版本。
P.S。请记住,在测量时间时,您需要首先强制生成序列(例如,将其转换为列表或采用 Seq.last
)。否则,您所测量的只是并行化开销成本。
问题
我们认为并行处理每个 "tail permutation" 会减少该算法的实际 运行 时间。为什么不呢?如果我们完全可以配置 PSeq 来改善 运行 时间,我们会怎样?
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else ([], permute xs.Tail)
// Why do we not get a performance
// improvement when we use PSeq here
// relative to using Seq?
||> PSeq.fold (fun acc ps ->
(insertAtEach xs.Head ps)@acc)
permute ["A";"B";"C"] |> ignore
我们认为排列工作将按如下方式拆分,并且算法的 insertAtEach
阶段将并行工作。
[C]
[BC] [CB]
[ABC] [BCA] [BCA] [ACB] [CAB] [CBA]
CPU01 CPU02
即使我们使用 permute [0..9]
这样的大初始列表,它实际上在并行时更慢。我们还没有弄清楚 withDegreeOfParallelism
和相关的 PSeq 选项是否有帮助。
一边
下面是代码清单的其余部分:
let put a q xs =
([], xs)
||> Seq.fold (fun acc x ->
if x = q then a::x::acc
else x::acc)
|> List.rev
// Insert x at each possible location in xs
let insertAtEach a xs =
([a::xs], xs)
||> Seq.fold (fun acc x ->
(put a x xs)::acc)
第一部分:“为什么不是吗?”
因为每次转换(转换)从SEQ -- -- --
process-execution调度到PAR -- || ||
需要做一些努力,这证明它们确实明显物化了 [TIME]
-domain 和 [SPACE]
-domain setup + termination overhead costs.
有关详细信息,请查看 re-formulated Amdahl's Law, particularly the naive-form Fig.1 与 部分:批评 以及后来得出的 overhead-strict re-formulation法律。
没有办法避免纳税和 overhead-costs 被支付...
在 parallel-computing 中,在 just-concurrent 计算环境中稍微不那么密集,确实很容易付出比接受 多的方式作为交换。
此外,在 Whosebug 上,使用搜索标签 parallelism-amdahl,您可以在此处找到 大量示例 和惊喜 post,您可以看到很多具有基准 overhead-costs 的示例(如果用户保持 open-minded 并且足够系统地确实 运行 他们并记录和 post 现实的 [TIME]
域成本) .
第二部分:“如何 如果我们可以......改善运行宁时间?“
没有人可以逃避 overhead-strict,atomic-processing 意识到 re-formulated 阿姆达尔定律。
没有人可以。
然而,如果在初始产品规划期间使用此工具,它还具有 design-side 优势。
产生的净处理开销受资源池大小、强制性 data-transfers、(未)避免共享 and/or 其他形式 mutual-dependencies、结果大小的影响在 {
并发 |
并行 }
处理终止时返回 -- 所有这些 add-on 成本都可以系统地进行基准测试 ,以便很好地理解这样做的成本,包括内存分配成本、垃圾收集或类似的现实操作方法释放开销。
给定一个已知的部署生态系统,在进入pure-serial/分布式/并行流程执行时,没有人被禁止使用基准数据进行系统costs-benefits评估。
鉴于此 fine-grained 知识已进行基准测试,
它可以作为解决困境的公平指标:
即 - PAR -- ||||
部分的最小大小是多少,以便它至少支付自己的 un-avoidable { setup + termination }
-overhead-add-on-成本?
这两个都没有做过,人们会感到惊讶,re-factoring 的过程与 直接 "negative" 或worse-than-expected 处理性能改进的一种方式。
总是:基准,基准,基准。
下一个:干脆不要选择更贵的方式
PSeq.fold
并不像您想象的那样。 PSeq.fold
实际上根本不是平行的。它是连续的。
您不能只是在算法中间的某个地方丢出 "parallel" 这个词并希望获得最好的结果。这不是并行化的工作方式。你必须真正理解发生了什么,什么是并行发生的,什么是顺序的,什么原则上可以并行,什么不能。
以fold
为例:它将提供的折叠函数应用于序列的每个元素和上一次调用的结果。由于每个下一个调用都必须有上一个调用的结果才能执行,所以很明显 fold
根本不能并行执行。必须是顺序的。事实上,如果您查看其 source code,这就是 PSeq.fold
实际执行的操作。因此,每次转换为 ParallelSequence
都会产生一些开销,但没有任何收获。
现在,如果您仔细查看您的算法,您可以梳理出可并行化的部分。你的算法是做什么的:
- 递归计算尾部排列。
- 对于这些排列中的每一个,通过在每个索引处插入头部来分解它。
- 连接第 2 步的所有结果。
当你这样说时,很容易看出第 2 步除了它本身之外并不真正依赖于任何东西。每个尾部排列都与其他所有排列完全分开处理。
当然,仅查看您的源代码并不能证明这一点,因为您已将步骤 2 和步骤 3 组合在一个表达式中 (insertAtEach xs.Head ps)@acc
,但使用以下通用标识很容易区分:
xs |> fold (fun a x -> g a (f x))
===
xs |> map f |> fold (fun a x -> g a x)
也就是说,不是将函数 f
应用于 fold
期间的每个元素 x
,而是可以使用 map
将它应用于每个元素 "in advance" ].
将这个想法应用到你的算法中,你会得到:
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else permute xs.Tail
|> Seq.map (insertAtEach xs.Head)
|> Seq.fold (fun acc ps -> ps@acc) []
现在很容易看出 Seq.map
步骤是可并行化的步骤:map
独立于其他元素将函数应用于每个元素,因此它 可以 原则上并行工作。只需将 Seq
替换为 PSeq
即可获得并行版本:
let rec permute (xs:'t list) =
if xs.Length = 1 then [xs]
else permute xs.Tail
|> PSeq.map (insertAtEach xs.Head)
|> PSeq.fold (fun acc ps -> ps@acc) []
PSeq
是否确实并行执行 map
是另一回事,但这应该很容易根据经验验证。
事实上,在我的机器上,对于 7 到 10 个元素的列表(11 个元素的列表导致 OOM),并行版本始终优于顺序版本。
P.S。请记住,在测量时间时,您需要首先强制生成序列(例如,将其转换为列表或采用 Seq.last
)。否则,您所测量的只是并行化开销成本。