scala - 函数式编程是否可以减少冯·诺依曼瓶颈？

我相信(通过一些读取)，跨总线从CPU缓存到主存储器的数据读写将对计算任务(需要跨总线移动数据)完成的速度施加很大的限制-冯·诺依曼瓶颈。

到目前为止，我已经看过几篇文章，其中提到函数式编程比诸如命令式方法之类的其他范例更具性能。 OO(在某些计算模型中)。

有人可以解释一些纯粹的函数式编程可以减少此瓶颈的方法吗？即。以下几点在总体上是否正确？

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

使用不可变的数据结构意味着数据更有可能在CPU高速缓存中徘徊-因为对现有状态的较少更新意味着较少从高速缓存清除对象？

是否有可能使用不可变数据结构，这意味着我们经常可能甚至永远都不会从主存储器读取数据，因为我们可能在计算过程中创建对象并将其保存在本地缓存中，然后在同一时间片上创建一个新的不可变对象(immutable对象)它(如果需要更新)，则我们永远不会使用原始对象，即。我们正在处理坐在本地缓存中的对象。

最佳答案

哦，老兄，那是经典。 John Backus’ 1977 ACM Turing Award lecture is all about that: “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs.”(在同一 session 上发表了论文“Lambda:The Ultimate Goto”。)

我想您或提出这个问题的人都会想到这次演讲。 Backus所说的“冯·诺依曼瓶颈”是“一个连接管，可以在CPU和存储之间传输单个字(并向存储发送地址)。”

CPU仍然具有数据总线，尽管在现代计算机中，它通常足够宽以容纳单词 vector 。我们也没有摆脱需要存储和查找许多地址的问题，例如到列表和树的子节点的链接。

但是Backus不仅在谈论物理体系结构(重点已添加):

这个管不仅是问题的数据流量的字面瓶颈，而且更重要的是，它是一种智力瓶颈，使我们一直不停地思考一次单词思考而不是鼓励我们用术语思考即将完成的任务的较大概念单元。因此，编程基本上是在规划和详细说明通过冯·诺依曼瓶颈的巨大单词流量，其中大部分流量与重要数据本身无关，而与在何处查找有关。

从这种意义上说，函数式编程在使人们编写更高级别的功能(例如映射和归约)方面取得了很大的成功，而不是像C语言的for循环这样的“一次单词思考”功能。今天，要对C中的大量数据执行运算，然后就像1977年一样，您需要将其编写为顺序循环。潜在的是，循环的每次迭代都可能对数组的任何元素，任何其他程序状态甚至循环变量本身产生任何影响，并且任何指针都可能对这些变量中的任何一个进行别名。当时，Backus的第一种高级语言Fortran的DO循环也是如此，除了可能涉及指针别名的部分。为了今天获得良好的性能，您尝试帮助编译器弄清楚，不，循环实际上并不需要按照您实际指定的顺序运行:这是一个可以并行化的操作，例如对某些对象的简化或转换其他数组或仅循环索引的纯函数。

但这已不再适合现代计算机的物理体系结构，因为它们都是 vector 化对称多处理器，例如70年代后期的Cray super 计算机，但速度更快。

确实，C++标准模板库现在在容器上具有完全独立于实现细节或数据内部表示的算法，而Backus自己的创造Fortran在1995年添加了FORALL和PURE。

当您查看当今的大数据问题时，您会发现我们用来解决这些问题的工具比起功能性习语，比Backus在50年代和60年代设计的命令性语言要大得多。您不会在2018年编写一堆for循环来进行机器学习；您可以在Tensorflow之类的模型中定义模型并进行评估。如果您想一次使用带有多个处理器的大数据，知道您的操作是关联的，因此可以按任何顺序分组然后合并，这非常有帮助，从而可以进行自动并行化和 vector 化。或者，因为数据结构是不可变的，所以它可以是无锁的和无等待的。或者 vector 上的变换是可以用另一 vector 上的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();

在这种情况下，系数 vector 是std::valarray对象，它是STL中的一种特殊类型的对象，它对如何别名其组件，其成员操作受到限制以及对可以安全地 vector 化哪些操作有很多限制听起来很像是对纯函数的限制。允许减少的列表(如结尾的.min())为not coincidentally，类似于instances的Data.Semigroup。如果您仔细阅读STL中的<algorithm>，就会发现类似的故事。

现在，我不会断言C++已成为一种功能语言。碰巧的是，我使程序中的所有对象变得不可变，并由RIIA自动收集，但这只是因为我对函数式编程有很多了解，所以我现在喜欢编码。该语言本身不会强加诸如不变性，垃圾回收或没有副作用之类的东西。但是当我们看到巴库斯(Backus)在1977年所说的是真正的冯·诺依曼瓶颈时，“一个知识性瓶颈使我们只能一次思考一个单词，而不是鼓励我们以更大的概念单元来思考。任务”，这是否适用于C++版本？这些运算是系数 vector 上的线性代数，而不是一次字。 C++借以做到这一点的想法以及表达式模板背后的想法在很大程度上都是功能性概念。 (将该片段与在K＆R C中的外观进行比较，以及Backus在1977年他的图灵奖演讲的5.2节中如何定义一个功能程序来计算内部乘积。)

我还用Haskell编写了一个版本，但我认为这并不是摆脱von Neumann瓶颈的一个很好的例子。

完全有可能编写符合Backus关于von Neumann瓶颈的所有描述的功能代码。回顾我本周编写的代码，我自己做了。折叠或遍历可建立列表？它们是高级抽象，但它们也被定义为一次单词操作的序列，当您创建和遍历单链接列表时，通过瓶颈的一半或更多数据是地址其他数据!它们是通过von Neumann瓶颈处理数据的有效方法，这基本上就是我这样做的原因:它们是对von Neumann机器编程的绝佳模式。

但是，如果我们有兴趣以其他方式编码，函数式编程可以为我们提供实现此目的的工具。 (我不会声称这是唯一的方法。)将简化表达为foldMap，将其应用到正确的 vector 上，单面运算的关联性可让您将问题分解为任意大小的块您想要并在以后合并各个部分。在除单链列表以外的数据结构上，将操作设为map而不是折叠，即可自动对其进行并行化或 vector 化处理。或以其他方式转换以产生相同的结果，因为我们已将结果表示为更高的抽象水平，而不是特定的一次单词操作序列。

到目前为止，我的示例是关于并行编程的，但是我敢肯定，量子计算将从根本上改变程序的外观。

关于scala - 函数式编程是否可以减少冯·诺依曼瓶颈？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48674498/