函数式编程是否会降低Von Neumann的瓶颈？

Question

我相信(从一些阅读中)读取/写入总线上从CPU缓存到主存储器的数据对计算任务(需要通过总线移动数据)的完成速度产生了相当大的限制--Von Neumann瓶颈.

到目前为止,我已经遇到过一些文章,其中提到函数式编程比其他范式(例如命令式方法)更具性能.OO(在某些计算模型中).

有人可以解释纯功能编程可以减少这个瓶颈的一些方法吗？即.发现(一般)以下任何一点是真的吗？

1. 使用不可变数据结构意味着通常较少的数据在该总线上移动 - 更少的写入？

2. 使用不可变数据结构意味着数据可能更容易在CPU缓存中闲置 - 因为对现有状态的更少更少意味着缓存中的对象刷新更少？

3. 是否有可能使用不可变的数据结构意味着,我们可能会经常甚至从来没有读取数据从主内存回来,因为我们在计算过程中创建对象并使其在本地缓存中,然后在相同的时间片创建一个新的不可变对象关闭它(如果需要更新),那么我们永远不会使用原始对象,即.我们正在使用位于本地缓存中的对象进行更多工作.

Answer 1

哦,伙计,这是经典之作. 约翰巴克斯的1977年ACM图灵奖讲座就是这样:"编程能否从冯诺依曼风格中解放出来？功能风格及其程序代数." (论文"Lambda:The Ultimate Goto"在同一会议上发表.)

我猜你或者提出这个问题的人都记得那个讲座.Backus所谓的"冯·诺伊曼瓶颈"是"一个连接管,它可以在CPU和商店之间传输一个单词(并向商店发送一个地址)."

CPU仍然有数据总线,但在现代计算机中,它通常足以容纳一个单词矢量.我们也没有摆脱我们需要存储和查找大量地址的问题,例如链接到列表和树的子节点.

但巴克斯不只是谈论物理架构(强调增加):

这个管不仅是问题数据流量的字面瓶颈,而且更重要的是,它是一个知识瓶颈,它使我们与一次一字一词的思维联系在一起,而不是鼓励我们根据问题进行思考.手头任务的更大概念单位.因此,编程基本上是通过冯·诺伊曼瓶颈来规划和详细说明话语的巨大流量,而且大部分流量都不涉及重要的数据本身,而是在哪里找到它.

从这个意义上说,函数式编程在很大程度上成功地让人们编写更高级别的函数,例如地图和缩减,而不是"一次一字一词地思考",例如forC 的循环.如果你试图执行今天对C中的大量数据进行操作,就像1977年一样,你需要把它写成一个顺序循环.潜在地,循环的每次迭代都可以对数组的任何元素或任何其他程序状态执行任何操作,甚至可以使用循环变量本身进行任何操作,并且任何指针都可能对这些变量中的任何变量进行别名.当时DO,Backus的第一个高级语言Fortran 的循环也是如此,除了关于指针别名的部分.为了在今天获得良好的性能,你试图帮助编译器弄清楚,不,循环并不真正需要按照你指定的顺序运行:这是一个可以并行化的操作,比如一些减少或转换其他数组或单独的循环索引的纯函数.

但这已不再适合现代计算机的物理架构,现代计算机都是矢量化对称多处理器 - 就像70年代后期的Cray超级计算机一样,但更快.

事实上,标准模板库现在有上是完全独立的实施细则或数据的内部表示容器算法和Backus的自己的创作,Fortran语言,加入FORALL并PURE于1995年.

当你看到今天的大数据问题时,你会发现我们用来解决它们的工具类似于功能习语,而不是Backus在50年代和60年代设计的命令式语言.你不会for在2018年写一堆循环去做机器学习; 你可以像Tensorflow那样定义一个模型并对其进行评估.如果您想同时使用大量处理器来处理大数据,那么知道您的操作是关联的非常有用,因此可以按任何顺序进行分组然后组合,从而实现自动并行化和矢量化.或者数据结构可以是无锁且无等待的,因为它是不可变的.或者,矢量上的变换是可以使用另一个矢量上的SIMD指令实现的映射.

例子

去年,我用几种不同语言编写了几个短程序来解决一个问题,即找到最小化三次多项式的系数.C11中的蛮力方法在相关部分看起来像这样:

      static variable_t ys[MOST_COEFFS];

//      #pragma omp simd safelen(MOST_COEFFS)
      for ( size_t j = 0; j < n; ++j )
        ys[j] = ((a3s[j]*t + a2s[j])*t + a1s[j])*t + a0s[j];

      variable_t result = ys[0];

//      #pragma omp simd reduction(min:y)
      for ( size_t j = 1; j < n; ++j ) {
        const variable_t y = ys[j];
        if (y < result)
          result = y;
      } // end for j

C++ 14版本的相应部分如下所示:

  const variable_t result =
    (((a3s*t + a2s)*t + a1s)*t + a0s).min();

在这种情况下,系数向量是std::valarray对象,STL中的一种特殊类型的对象,它们的组件如何被别名化,并且其成员操作受到限制,并且对操作矢量化安全的操作有很多限制很像纯函数的限制.允许减少,像名单.min()在最后,是不是巧合,类似instances的Data.Semigroup.如果你仔细研究<algorithm>STL,你会看到类似的故事.

现在,我不会声称C++已成为一种功能语言.事实上,我让程序中的所有对象都不可变并由RIIA自动收集,但这只是因为我已经有很多功能编程,这就是我现在喜欢的代码.语言本身不会强加诸如不变性,垃圾收集或没有副作用之类的东西.但是,当我们看看Backus在1977年所说的真正的冯·诺伊曼瓶颈时,"一个知识瓶颈让我们一直在思考,而不是鼓励我们用更大的概念单位来思考手头的任务,"这适用于C++版本吗？这些操作是系数向量的线性代数,而不是一次一个字.而C++借用的想法 - 表达模板背后的想法更是如此 - 主要是功能概念.(将该片段与它在K&R C中的表现进行比较,以及Backus如何在1977年的图灵奖演讲的第5.2节中定义了计算内部产品的功能程序.)

我还在Haskell中编写了一个版本,但我不认为它是逃避那种冯诺依曼瓶颈的一个很好的例子.

完全可以编写满足Backus对冯诺依曼瓶颈的所有描述的功能代码.回想一下我本周写的代码,我自己就完成了.构建列表的折叠或遍历？他们是高层次的抽象,但他们也被定义为或字在一次一个操作序列,而一半以上的瓶颈,当您创建和遍历一个单向链表传递的数据是地址其他数据!它们是通过von Neumann瓶颈放置数据的有效方式,这就是我为什么这样做的原因:它们是编程冯·诺依曼机器的伟大模式.

但是,如果我们对以不同方式编码感兴趣,那么函数式编程为我们提供了工具.(我不会要求它是做的唯一的事情.)快速下降的foldMap,其应用到正确的载体,和monoidal操作的关联性可以让你分裂问题成任何大小,你的块希望并在以后合并这些作品.map在除单链表之外的数据结构上进行操作而不是折叠,并且可以自动并行化或向量化.或者以产生相同结果的其他方式进行转换,因为我们已经在更高的抽象级别上表达了结果,而不是一次一个字的特定操作序列.

到目前为止我的例子都是关于并行编程的,但我确信量子计算会从根本上改变程序的外观.