功能并行的编程语言:F#vs Haskell

Question

功能并行的编程语言:F#vs Haskell

pad*_*pad 28 parallel-processing f# haskell functional-programming

功能编程具有不可变的数据结构,并且没有副作用,这些本质上适用于并行编程.我研究了如何在函数式语言中利用多核计算,并针对某些数值应用程序设定生产代码.

F#背后有微软,它的并行结构如PLINQ,TPL,Async Workflow已被充分记录并显示出一些潜力.然而,关于Haskell中的并行性的研究目前非常活跃,并且它具有许多F#尚未支持的优秀特性:

我的问题是我应该选择哪种语言进行功能并行？如果选择了F#,是否有任何指针可以构建他们目前在Haskell中拥有的内容？

更新:

我选择了Simon的答案,因为它带来了关于垃圾收集器,内存分配和缓存未命中的一些很好的讨论.我会坚持使用F#,我认为这些答案对我学习功能并行是有帮助的.

Answer 1

Sim*_*low 51

如果您考虑的代码类型大量分配内存,那么您可能会发现GHC垃圾收集器比.NET垃圾收集器更好地扩展.有一些anedcodal证据表明,当多个线程大量分配时,.NET GC会成为瓶颈,这也是大多数Java收集器中的一个棘手问题.另一方面,我们已经非常注意在GHC垃圾收集器中实现良好的局部性和可伸缩性 - 主要是因为我们别无选择,大多数惯用的Haskell代码无论如何都会分配很多.我有基准,分配像疯了一样,并保持超过24核心的扩展.

在Haskell中请注意,您可以从类型系统中获得确定性的保证,而F#中没有这种确定性.

你提到了Data Parallel Haskell:这里是一个警示性的注释,虽然DPH团队期望即将发布的GHC 7.2.1版本具有稳定的DPH实现,但目前还没有为生产使用做好准备.

@Jon避免分配不是"解决方案".如果您的语言实现强制您避免分配以获得并行加速,那么这是一个严重的限制.也许你应该考虑另一种语言:-) (11认同)
@SimonMarlow:降低绝对性能不是一个"解决方案".如果您的语言实现迫使您牺牲性能以获得并行加速,那么这是一个严重的限制. (9认同)
实际上,如果你牺牲足够的性能使你的串行版本足够慢,那么获得良好的并行加速是非常微不足道的. (8认同)
您已经指出了并行编程的一个非常重要的方面.我在这里看到类似的.NET GC问题http://stackoverflow.com/questions/2311154/how-can-i-improve-garbage-collector-performance-of-net-4-0-in-highly-并发/ 2311171#2311171.我认为垃圾收集在功能并行的背景下是至关重要的,其中内存分配分散在程序上.从开发人员的角度来看,您有什么建议来避免这些问题？ (3认同)
@Jon:就地变异只能解决问题.正如您提到的缓存无关数据结构,数组和矩阵的情况非常清楚,但您如何在内存中组织递归数据结构(树)以减少缓存未命中？ (3认同)
@pad:我将推迟对缓存遗忘树的大量工作.最先进的技术是采用van Emde Boas布局,但还有其他类型的缓存遗忘树和其他基于树的缓存遗忘数据结构,如漏斗堆.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.2955&rep=rep1&type=pdf http://www.mpi-inf.mpg.de/departments/d1/teaching/ws10/models_of_computation /FunnelHeapTalk.pdf http://supertech.csail.mit.edu/cacheObliviousBTree.html (2认同)

Answer 2

Tom*_*cek 22

首先,我同意其他人没有客观的答案.

但是,我认为功能并行的想法有点高估了.当然,您可以轻松地在程序中找到数据依赖项,如果您正在处理大量数据,则可以使用一些数据并行库来轻松安全地并行化它.但是,即使在C#(使用TPL和PLINQ)中也可以这样做,如果你对你所写的内容有点小心的话.

问题是,大多数程序不需要并行化,因为它们根本没有做足够的CPU密集型工作.例如,F#async解决了(我认为)启用异步I/O的更重要问题,这是连接应用程序中大多数"挂起"的原因.我认为Node.js的受欢迎程度非常好地证明了这一重要性.

函数式语言的真正价值在于语言的表达性 - 您可以轻松定义问题的抽象,以更简洁的方式编写代码,更容易理解,推理和测试.你可以在F#和Haskell中得到这个.

回答关于并行性的具体问题 - 我相信F#中并行性支持的状态更稳定(但是,我是F#人).您可以选择async,TPL和(Erlang-inspired)F#代理(它们都是非常稳定的库).在Haskell方面,仍然有很多进化.在最近的工作仅仅是几个星期了.我还发现在具有明确指定评估模型的语言中使用并行性更容易,但这可能仅仅是我个人的偏好.

我认为你在这里低估了它的价值.在函数式语言中,你更有可能从一个惯用的程序开始并将其并行化,而不会过多地修改代码,或者等效地说你可以编写一个与惯用语序不太相似的并行程序.此外,你更有可能做到正确(绊倒你的危险更少).这不是关于绝对性能:它是关于性能,工作量,可维护性和稳健性之间的权衡. (12认同)
F#虽然没有STM,对吗？在编写某些类型的并发代码时,这是大脑的主要负担. (6认同)
作为一个使用你的F#书(这是迄今为止优秀的BTW)的完全新手,我想补充一点,功能语言(F#,Haskell)中的解决方案的优雅是必不可少的. (3认同)
@Jon,我不是说STM是我链接问题中问题的最佳解决方案.STM命中域的一个很好的例子是你想要一个可以并行更新的大型平衡树.无论如何,当你了解闭包时,你的论点让人联想到新手程序员."好吧,但我从来没有想过它们,我也看不出它们会如何有用." 这是一个*新的抽象*,你必须熟悉并熟悉它,然后才开始跳出来. (3认同)
我怀疑在一种普遍存在突变的语言中,STM有点低级 - 你要么锁定所有东西,要么只能直接同步少量事物.在大多数事物都是不可变的语言中,问题就更少了 - TVars和TChans提供了更高级别的界面. (2认同)
@luqui:我引用的一些工作给出了并发平衡树的性能结果,并且在所有情况下它们都不能扩展,因为即使非本地更新最终也会争用根目录附近的节点.所以它要复杂得多,但并不比序列化更好.相反,并发哈希表和跳过列表提供相同的功能和更好的性能. (2认同)

Answer 3

Jon*_*rsi 21

我会为此投降,但让我成为一个吝啬鬼.

功能语言很棒.它们改变了你对分解问题的看法,并且非常好地映射到某些类型的问题.每个程序员都应该熟悉至少一种函数式编程语言.但是"函数式语言对于并行编程本质上是有益的"可能不是原因所在.

值得注意的是,无疑是有史以来最成功的并行函数语言,Erlang使用完全标准的消息传递来实现其并行性,并且其功能性和并行性之间的联系最多是间接的.

二十五年前,功能语言得到了极大的推动,因为这个论点看起来非常引人注目 - 功能语言似乎很适合当时日益平行的架构.由于语言的副作用自由,编译器和运行时将自动实现并行性. SISAL,甚至可以编译成共享和分布式内存(!)可执行文件,此时开发,就像Haskell一样,也是ML,它是Objective CAML的前身和ML系列中的其他语言.

这只是提供了一些历史观点.对于字面上四分之一个世纪,功能语言倡导者,包括该领域一些最聪明的人,一直在说功能语言在阳光下的日子即将到来,并且它将适用于并行性这是杀手级的应用程序.然而,我们在这里,甚至没有人听说过SISAL; 而且我猜这篇文章的大多数读者都认为Haskell是一种热门的新语言.

当然,很可能现在有了多核考虑因素,事情终于变得非常紧迫,功能语言真的会大放异彩,或者今年将是有一些突破的一年,我甚至无法想象哪一个彻底改变了景观.今年可能与前25年的每一年都不同.但它也可能不会.

现在存在的庞大,绝大多数并行和并发代码,以及可预见的未来,都不是用函数式语言编写的.如果您正在寻求了解并行性,请务必探索F#,Haskell等中可用的机制; 但是不要局限于那些,我只是说.

函数式语言的杀手论证不是并行性,它是代码大小减少4到10倍的因素.过去停止函数式语言的事情是他们无法编译成有效的代码.那不再是真的. (11认同)
只是为了澄清,Erlang是并发编程的语言,而不是并行(即并行加速不是焦点) (9认同)
西蒙·佩顿·琼斯(Simon Peyton Jones)在他最近的函数编程交换中谈到了这一点,[管理并行性:拥抱多样性,但控制副作用](http://skillsmatter.com/podcast/scala/talk-by-haskell-expert -simon-佩顿 - 琼斯/ JS-1434). (8认同)
@SimonMarlow:Simon Peyton-Jones的演讲有两个主要缺陷.首先,他将并行性语境中的函数式编程描述为"明显"更好,因为并行编程环境中的大规模性能下降并不明显.其次,他没有提出将并行Haskell代码与生产质量命令代码进行比较的单一基准,这是方法论的一个根本缺陷. (8认同)
好吧,最终是程序员决定一种语言是什么,谷歌搜索"erlang""可伸缩性"给出400k +点击率; 所以很多人都在使用它,因为它能够利用大量的处理器.(例如,弱缩放,与强缩放相比 - 但仍然是并行性能).并且性能对于Erlang来说非常重要 - 实时电信公司的东西_does_要求有效利用任何可用的硬件.因此,虽然我同意你所做的区别,但我不确定Erlang是"for"并发和并行编程. (2认同)

Answer 4

ild*_*arn 12

简单的答案是,因为两种语言都支持并行性和并发性,所以这不应该成为决定使用哪种语言的因素.也就是说,有一个更大的因素需要考虑这样的决定.

就像"程序员有多便宜"一样 (11认同)

Answer 5

Jon*_*rop 10

功能编程具有不可变的数据结构,并且没有副作用,这些本质上适用于并行编程.

这是一种常见的误解.并行性完全取决于性能和纯度会降低性能.如果你的目标是获得不错的表现,那么纯功能编程并不是一个好的起点.一般而言,纯度意味着更多的分配和更糟糕的局部性.特别是,纯粹的功能数据结构用树替换数组,并且会导致更多的分配并给垃圾收集器带来更多的负担.

例如,在Haskell中测量优雅的纯函数"quicksort"的性能.最后我检查过,它比我机器上的传统命令解决方案慢了几千倍.

此外,没有人设法在Haskell中实现有效的字典数据结构(纯粹或不纯)或高效的纯函数排序,没有人想出如何编写渐近有效的持久不相交集数据结构,并且没有已知的方法来实现其他基本数据结构,如纯函数弱字典!

此外,虽然理论上可以在Haskell中编写不纯的代码,但GC会以牺牲突变性能为代价对纯代码进行大量优化.例如,GHC的哈希表仍然比.NET慢26倍.从历史上看,突变的性能在Haskell中被认为是如此不重要,以至于写一个指向数组的指针是GHC中的O(n)操作已有五年了.

我研究了如何在函数式语言中利用多核计算,并针对某些数值应用程序设定生产代码.

我找到的最好的方法是学习如何在命令式样式(特别是研究Cilk)中编写适合多核的并行程序,然后使用一流函数和尾部调用消除将代码分解为不纯的函数样式.

这意味着缓存不经意的数据结构和算法.在Haskell中没有人这样做过.事实上,迄今为止在并行Haskell上发表的研究都没有提到缓存复杂性的基本概念.此外,尽管众所周知非严格(即懒惰)评估使得空间消耗不可预测,但是尚未普遍认识到同样的问题使得可扩展性在多核上变得非常不可预测.

F#背后有微软,它的并行结构如PLINQ,TPL,Async Workflow已被充分记录并显示出一些潜力.

它们远远超出潜力.成千上万的商业应用建立在这些工业强度基础之上.

然而,关于Haskell中的并行性的研究目前非常活跃,并且它具有许多尚未被F#支持的优秀特性:

为什么你认为它们是"很好的功能"？

我建议阅读Simon Marlow的最新论文:

"...实践经验和调查的结合使我们得出结论,这种方法并非没有缺点.简而言之,问题是:实现并行性par要求程序员理解最多的语言的操作属性实施 - 定义(最糟糕的是未定义).这使得par难以使用,并且陷阱很多 - 新用户的失败率很高......"

我的问题是我应该选择哪种语言进行功能并行？

我建议不要使用并行的纯功能代码进行生产,因为它是一个完整的外卡.假设你很高兴为了获得竞争性的表现而牺牲一些纯度,我会使用并推荐F#.

@Jon我没有进入这个问题的技术方面,只评论答案中使用的修辞方式,以及如何改进.我不能认真地采取这样一种语调的答案,它极大地分散了最初提出的关于纯粹功能并行的问题. (14认同)
这篇文章以多种方式播下了混乱.我只会解决第一段.首先 - 某些算法的渐近最优持久版本确实是开放式问题.但是,Haskell完全能够在需要时使用可变状态.更重要的是,纯度通常会降低性能.副作用的划分以及使用不可变数据结构*作为默认*改进了算法的推理和清晰度,包括并行算法.必要时可以进行变异. (13认同)
部分引用并没有灌输信心:Marlow接着指出,使用预定义的抽象并不会分享这个难度.在任何情况下,即使一个人不喜欢策略方法,你引用的论文也会引入另一种方法.暗示使用Haskell的人不会发送代码而只是写论文会降低这个答案的质量. (10认同)
当你谈到"写障碍"时,你的意思是一般的世代垃圾收集者常见的吗？你也错误地描述了最近GHC阵列的变化,这是令人惊讶的,因为你花了数年时间抱怨它们 - 一直以来,显然不明白问题是什么.写入总是O(1) - 问题是数组的变异导致整个事物在GC上遍历.虽然这很糟糕而且非常值得修复,但它只会在退化情况下引起O(n)行为. (8认同)
@ScottWest:"我没有进入这个问题的技术方面".而且我没有涉及这个问题的非技术方面.我已经提供了参考资料,并且由读者自己决定. (6认同)
"副作用的划分,以及默认使用不可变数据结构改进了算法的推理和清晰度,包括并行算法".显然有许多算法纯度会降低清晰度,但更重要的是,为了清晰起见而破坏优化的性能显然是毫无意义的.Quicksort就是一个很好的例子:12行强制性F#对2行优雅的Haskell,两者都很平行,但F#在8个核心上获得5倍的速度,而纯Haskell则为2.4倍,而F#6,000×比Haskell快. (3认同)
@sclv:这是写屏障,是的.旧的写屏障在一般情况下引起O(n)不必要的操作,而不是退化情况.通过弄脏整个阵列为GC间接地这样做的事实是无关紧要的.关键是单次写入的成本是O(*n*).新的写屏障实际上仍然是O(*n*),但是恒定的前因子足够小,以至于很难在今天的机器上检测到.错误报告甚至拼写出来:"这并没有真正解决问题,它只会降低常数因素"http://hackage.haskell.org/trac/ghc/ticket/650 (3认同)
@sclv:"Haskell完全有能力在需要时使用可变状态".现在**是一个误导性陈述.GHC的GC拦截程序写入的每一个指针,并使其速度极慢,因为它是以纯代码为基础进行优化而牺牲了突变.这就是为什么GHC的哈希表仍然比.NET慢了**26倍.实际上,GHC中的变异是如此之慢,即使是纯功能树也可能比哈希表更快!所以,是的,Haskell在理论上能够通过任何合理的定义进行突变但不具备"完全能力". (2认同)
哦,我忘了提到在Haskell中突变被认为是如此不重要,直到最近,GHC的写入障碍实际上使得将单个指针写入一个数组O(*n*)操作而不是O(1)操作.在几年的用户抱怨之后,这个性能错误已得到修复,但即使是固定版本也比生产质量的GC(如JVM或.NET)慢. (2认同)

Answer 6

Don*_*art 8

没有客观的答案.对于Haskell来说,有大量积极的工作,没有"一刀切"的方法.相反,在Haskell中,提供了许多用于实现并行性的不同工具.Haskell中多核编程的现状如何？

Answer 7

Pau*_*son 6

Haskell的纯度意味着它在并行处理和并发之间做出了明确的区分.

如果您希望通过在多个内核上分配工作来加速大数据处理应用程序,那么您需要并行处理,这意味着"par"及其衍生产品.通过仔细使用这些结构,您可以让您的CPU密集型纯函数在N个内核上运行N倍,同时确保您没有更改原始代码的含义或在程序中引入非确定性.
另一方面,如果您希望您的程序与外部世界中的多个实体交互,交错来自不同实体的通信但仍然具有一定程度的共享资源,那么您需要并发,这意味着使用"fork"和STM的某些组合和TVars.STM为您提供了很好的事务语义,这对于消除竞争条件和其他并发性恶作剧有很大帮助.您需要注意碰撞频率和重试率.

是的,这些术语存在很多混淆.Don Syme最近指出,同时获取URL(例如使用`Async.Parallel`)是并行性而不是并发性,尽管它不受CPU限制.并发垃圾收集是并发但不必(必然)并行的CPU绑定应用程序的示例.我特别喜欢DMBarbour在他的博客上纠正Simon Marlow的声明,该声明列举了一些确定性的并发形式,例如: (6认同)
时态逻辑编程,功能反应式编程,未来通过单个赋值变量,Kahn过程网络,并发约束编程.我喜欢他对并行性的定义是"一个实现属性,表示许多计算同时发生",而并发性是"一种语义属性,表示许多行为同时发生". (5认同)
@Jon,这个答案准确地反映了Haskell社区中这两个术语的公认定义.其他社区的定义是否不同？ (2认同)

归档时间：	14 年，11 月前
查看次数：	7255 次
最近记录：	13 年，4 月前