C++ 是否被视为冯诺依曼编程语言?

Is C++ considered a Von Neumann programming language?

字词Von Neumann languages is applied to programming languages whose computational model is based on the Von Neumann computer architecture

TL:DR: C++ 抽象机是 PRAM (Parallel Random Access Machine).

的一种类型

来自您链接的 Von Neumann Languages 维基百科文章:

Many widely used programming languages such as C, C++ and Java have ceased to be strictly von Neumann by adding support for parallel processing, in the form of threads.

Cease 描述了从 being 到 not-being 的转变。所以是的,在 C++11 添加线程之前,根据维基百科,C++ 严格地 是一种冯诺依曼语言。 (之后它基本上仍然是一种 VN 语言;让多个线程共享同一个 address-space 并不会从根本上改变 C++ 的工作方式。)

在此上下文中成为冯·诺依曼架构的有趣部分:

  • 完全具有可寻址 RAM,允许随时高效访问(模缓存/分页)任何对象
  • 将程序存储在 RAM 中:函数指针是可行且高效的,不需要解释器
  • 有一个程序计数器,逐步执行存储程序中的指令:自然模型是一种一次只做一件事的命令式编程语言。这是非常基础的,很容易忘记它不是唯一的模型! (相对于 FPGA 或 ASIC 或所有门都可能在每个时钟周期并行执行某些操作的东西。或者 MIMD GPU,其中您编写的计算 "kernel" 对所有数据可能是 运行 可能并行,没有每个元素的处理顺序的隐式排序。或者 Computational RAM:将 ALU 放入内存芯片中以绕过 Von Neumann 瓶颈)

IDK 为什么 wiki 文章提到 self-modifying 代码;像大多数语言一样,ISO C++ 没有对其进行标准化,并且完全兼容 ahead-of-time 对 split-bus / split-address-space Harvard architecture. (No eval or anything else that would require an interpreter or JIT.) Or on a normal CPU (Von Neumann 的编译),严格的 W^X 内存保护并且从不使用 mprotect 更改页面权限可写入可执行文件。

当然,大多数真正的 C++ 实现 do 提供 well-defined 将 machine-code 写入缓冲区并转换为函数指针的方法,作为扩展。 (例如 GNU C/C++ 的 __builtin___clear_cache(start, end) 被命名为 I-cache sync,但定义是为了确保将数据作为函数调用是安全的。dead-store 消除优化同样,因此即使在具有连贯 I-caches 的 x86 上,代码也可能在没有它的情况下中断。)因此 实现可以扩展 ISO C++ 以利用冯诺依曼架构的这一特性; ISO C++ 有意限制了范围,以允许操作系统和类似东西之间存在差异。

请注意,作为冯·诺依曼 而不是 严格地暗示支持间接寻址模式。一些早期的 CPU 没有,self-modifying 代码(重写指令中的地址 hard-coded)对于实现我们现在使用间接寻址的东西是必要的。

另请注意,约翰·冯·诺依曼是一个非常有名的人,他的名字与许多基本事物相关联。冯·诺依曼架构(与哈佛相反)的某些内涵并非在所有情况下都真正相关。例如"Von Neumann language" 术语不太关心冯诺依曼与哈佛;它关心 stored-program 与程序计数器与元胞自动机或图灵机(带有真实磁带) 之类的东西。通过使用单独的总线(或只是拆分缓存)来获取指令(哈佛)来获得额外的带宽只是一种性能优化,而不是根本性的改变。


什么是抽象机器模型/计算模型?

首先,有一些 models of computation that are weaker than Turing machines, like Finite State Machines. There are also non-sequential models of computation, for example Cellular Automata (Conway's Game of Life),其中多个事件在每个 "step".

并行发生

如我们所知"strong"的Turing machine is the most widely-known (and mathematically simple) sequential abstract machine。没有任何类型的绝对内存寻址,只是磁带上的相对移动,它自然提供了无限的存储空间。这很重要,并且在某些方面使得所有其他类型的抽象机器与真实的 CPU 非常不同。请记住,这些计算模型用于 理论 计算机科学,而不是工程。有限内存或性能等问题与可计算的内容无关在理论上,仅在实践中。

如果你可以在图灵机上计算某些东西,你可以在任何其他 Turing-complete 计算模型(根据定义)上计算它,也许使用更简单的程序,也可能不使用。图灵机不是很好编程,或者至少与任何真正的 CPU 的汇编语言不同。最值得注意的是,内存不是 random-access。而且他们无法轻松地对并行计算/算法进行建模。 (如果你想抽象地证明关于算法的事情,为某种抽象机器实现它可能是一件好事。)

证明抽象机需要具备哪些功能才能成为图灵完备也可能很有趣,因此这是开发更多抽象机的另一个动机。

还有许多其他在可计算性方面是等效的。 RAM machine model 最像 real-world CPU 有内存数组。但作为一个简单的抽象机器,它不会理会寄存器。事实上,只是为了让事情更混乱,它称其存储单元为 寄存器数组 。 RAM 机器支持间接寻址,因此与现实世界 CPUs 的正确类比肯定是内存,而不是 CPU 寄存器。 (并且有无限数量的寄存器,每个寄存器的大小都是无限的。地址永远存在,每个 "register" 都需要能够保存一个指针。)RAM 机器可以是哈佛:程序存储在一个单独的 finite-state 部分机器。将其想象成一台具有 memory-indirect 寻址模式的机器,因此您可以将 "variables" 保存在已知位置,并将其中一些用作指向 unbounded-size 数据结构的指针。

The program for an abstract RAM machine 看起来像汇编语言,带有 load/add/jnz 和您希望它具有的任何其他指令选择。操作数可以是立即数或寄存器数(普通人称之为绝对地址)。或者,如果模型有一个蓄能器,那么你有一台带蓄能器的 load/store 机器,更像一个真正的 CPU.

如果您想知道为什么像 MIPS 这样的“3 地址”机器被称为“3 地址”机器而不是 3 操作数,它可能是 1。因为指令编码需要空间/I-fetch 带宽通过冯·诺依曼瓶颈对于 3 explicit 操作数位置(寄存器编号)和 2。因为在 RAM 抽象机中,操作数是内存地址 = 寄存器编号。


C++ 不能是图灵完备的:指针的大小是有限的。

当然,C++ 与 CS 抽象机器模型有 巨大 差异:C++ 要求每个类型都有一个 compile-time-constant 有限 sizeof,所以如果包含 infinite-storage 要求 ,C++ 不能 Turing-complete。 Is C actually Turing-complete? on cs.SE applies to C++, too: the requirement that types have a fixed width is a showstopper for infinite storage. See also https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded

中的所有内容

所以计算机科学抽象机很傻,那 C++ 抽象机呢?

它们当然有它们的目的,但是关于 C++ 我们可以说很多有趣的东西,如果我们稍微 不那么抽象 以及它假定的机器类型谈谈机器可以高效做什么。一旦我们谈论有限机器和性能,这些差异就变得相关了。

首先,完全 运行 C++,其次,运行 没有巨大的 and/or 不可接受的性能开销。 (例如,硬件将需要相当直接地支持指针,可能不需要 self-modifying 代码将指针值存储到使用它的每个 load/store 指令中。这在 C++11 中不起作用线程是语言的一部分:相同的代码可以同时对 2 个不同的指针进行操作。)

我们可以更详细地了解 ISO C++ 标准假定的计算模型,该标准根据抽象机上发生的事情描述了该语言的工作方式。真正的实现需要 运行 在真实硬件上编码,运行 s "as-if" 抽象机正在执行 C++ 源代码,重现 any/all 可观察到的行为(可被程序的其他部分观察到)不调用 UB)。

C/C++有内存和指针,所以它绝对是一种RAM机器。

或者最近,a Parallel random-access machine,将共享内存添加到 RAM 模型,并为每个线程提供自己的程序计数器。鉴于 std::atomic<> release-sequences 使 所有 之前的操作对其他线程可见,"establishing a happens-before relationship" 同步模型基于 coherent共享内存。在需要手动触发同步/刷新的东西之上模拟它对性能来说是可怕的。 (非常聪明的优化可能会证明什么时候可以延迟,所以不是每个 release-store 都必须受到影响,但是 seq-cst 可能会很糟糕。seq-cst 必须建立所有线程的全局操作顺序同意;这很难,除非商店同时对所有其他线程可见。)

但请注意,在 C++ 中,除非您使用 atomic<T>,否则实际同时访问是 UB。这个allows the optimizer to freely use CPU registers for locals, temporaries, and even globals without exposing registers as a language feature. UB allows optimization一般;这就是为什么现代 C/C++ 实现是 而不是 可移植汇编语言的原因。

C/C++ 中的历史关键字 register 表示变量不能获取其地址,因此即使是 non-optimizing 编译器也可以将其保留在CPU 寄存器,而不是内存。 我们谈论的是 CPU 寄存器,而不是计算机科学 RAM 机器 "register = addressable memory location"。 (就像 x86 上的 rax..rsp/r8..r15,或 MIPS 上的 r0..r31)。现代编译器会进行逃逸分析,并自然地将局部变量正常保存在寄存器中,除非它们必须溢出它们。其他类型的 CPU 寄存器也是可能的,例如a register-stack 像 x87 FP 寄存器。 反正register关键字的存在就是为了优化这类机器但是不排除运行在没有寄存器的机器上,只有memory-memory说明。

C++ 旨在 运行 在冯eumann 机器 CPU 寄存器 ,但是 C++ 抽象机(标准用来定义语言)不允许将数据作为代码执行,或者说任何关于寄​​存器的事情。不过,每个 C++ 线程确实有自己的执行上下文,并且对 PRAM threads/cores 进行建模,每个线程都有自己的程序计数器和调用堆栈(或任何用于自动存储的实现,以及用于确定 return 的位置) .) 在具有 CPU 寄存器的真实机器中,它们对每个线程都是私有的。

所有 real-world CPU 都是 Random Access Machines,并且 CPU 寄存器与可寻址/可索引 RAM 分开。即使 CPUs 只能用一个累加器寄存器进行计算,通常至少有一个指针或索引寄存器,至少允许一些有限的数组索引。至少所有 CPU 作为 C 编译器目标运行良好。

如果没有寄存器,每条机器指令编码都需要所有操作数的绝对内存地址。 (可能像 6502,其中 "zero page",内存的低 256 字节,是特殊的,并且有使用零页中的字作为索引或指针的寻址模式,以允许 16 位指针没有任何16 位体系结构寄存器。或类似的东西。)参见 Why do C to Z80 compilers produce poor code? on RetroComputing.SE for some interesting stuff about real-world 8-bit CPUs where a fully compliant C implementation (supporting recursion and reentrancy) is quite expensive to implement. A lot of of the slowness is that 6502 / Z80 systems were too small to host an optimizing compiler. But even a hypothetical modern optimizing cross-compiler (like a gcc or LLVM back-end) would have a hard time with some things. See also a recent answer on 对 6502 zero-page 索引寻址模式的一个很好的解释:来自内存中绝对 8 位地址的 16 位指针 + 8 位注册。

没有 间接寻址的机器 不能轻松支持数组索引、链表,而且绝对不能支持指针变量作为first-class 对象。 (反正效率不高)


真正的机器上什么是高效的 -> 什么习语是自然的

C 的大部分早期历史都在 PDP-11 上,这是一个普通的 mem + 寄存器机器,其中任何寄存器都可以用作指针。自动存储映射到寄存器,或在需要溢出时映射到调用堆栈上的 space。内存是平面字节数组(或 char 的块),没有分段。

数组索引只是根据指针算法定义的,而不是它自己的东西,这也许是因为 PDP-11 可以有效地做到这一点:任何寄存器都可以保存一个地址并被取消引用。 (相对于一些只有几个指针宽度的特殊寄存器的机器,其余的更窄。这在 8 位机器上很常见,但早期的 16 位机器如 PDP-11 的 RAM 不足以让一个 16 位寄存器一个地址就够了)。

查看 Dennis Ritchie 的文章 The Development of the C Language 了解更多历史; C 在 PDP-7 Unix 上由 B 衍生而来。 (第一个 Unix 是用 PDP-7 asm 编写的)。我不太了解 PDP-7,但显然 BCPL 和 B 也使用只是整数的指针,数组基于 pointer-arithmetic.

PDP-7 is an 18-bit word-addressable ISA。这可能就是 B 没有 char 类型的原因。但是它的寄存器足够宽以容纳指针,所以它自然支持 B 和 C 的指针模型(指针并不是很特别,你可以复制它们并取消引用它们,你可以获取任何东西的地址)。如此平坦的内存模型,没有 "special" 内存区域,就像您在分段机器或一些零页的 8 位微处理器上找到的那样。

诸如 C99 VLA(和无限大小的局部变量)和无限重入和递归之类的东西意味着函数 local-variable 上下文的调用堆栈或其他分配机制(也就是使用堆栈指针的普通机器上的堆栈帧。 )

我认为尝试将 C++(或大多数其他语言)固定到单一体系结构模型是最困难的。让我们考虑一下 C++ 98/03。正如问题所说,它们符合冯诺依曼模型。哦,等等——它们也同样适合(如果不是更好的话)哈佛建筑。

就此而言,哈佛建筑实际上更像是一个模型家族,而不是一个模型。特别是,如果 CPU 具有单独的代码和数据缓存,通常会被视为使用哈佛架构——即使它类似于 x86,硬件会尽力隐藏代码中的拆分(例如,您可以编写自修改代码,修改代码后,您执行的将是新代码——尽管可能会有很大的损失,因为指令缓存未针对处理修改进行优化) .

但是 "Harvard Architecture" 也可以用来描述一些 DSP,它们有两个(或三个)完全独立的内存总线连接到物理上独立的内存:

适应这一点的语言规则实际上相当微妙——以至于除非您正在寻找它们,否则很容易完全错过它们。例如,C 和 C++ 将指向函数的指针定义为独立于指向数据的指针。他们也非常小心地避免对诸如地址之类的事情给予任何保证,除非在相当有限的情况下(例如,在 C++ 中,你不会保证任何关于比较地址的事情。数据地址的函数)。

然而,自从 C++11 标准以来,情况发生了一些变化。虽然核心语言保留了一些按指定顺序执行的指令流的基本特征,但该库增加了创建可以并行执行的多个线程的能力。它们可以通过共享内存进行通信,但是您必须使用原子变量或内存栅栏来保证任何程度的成功。这允许在任何地方的机器上实现,从极度紧密耦合到相当松散耦合,其中(例如)看起来像共享内存的通信实际上可能涉及通过网络连接之类的东西发送数据,并发送信号告诉远端何时 t 运行任务完成。

因此,再次说明,该语言的规范并没有真正绑定到通常被视为硬件级别的单一体系结构。相反,虽然它可能更适用于通常被认为是相当紧密耦合的机器,但我相信它可以在相当松散耦合的机器上实现,例如完全独立、不同的机器集群。您通常需要(或至少想要)更改您编写代码的方式,但至少在理论上您可以编写可移植的 C++ 代码 运行。

C++是一种用英文写成的规范标准。请参阅 n3337 - C++11 的最新草案。

正如 and 所解释的,官方模型是并行随机机。

但是您通常使用编译器和 运行 您的程序(除非您编写嵌入式系统)在 Linux 上的某些 operating system (e.g. Windows or Linux; read also this). Many OSes provide dynamic loading facilities (e.g. dlopen(3) 下编写 C++ 代码,并且大多数计算机都可以使用 C++编译器。

然后您实际上 可以在运行时生成 C++ 代码,将生成的 C++ 代码编译为 plugin, then dlopen that generated plugin. And on Linux you can do that many times (e.g. have dozen of thousands of such generated plugins, see my bismon and manydl.c 程序。

您还可以找到几个 JIT 编译 C++ 库,例如 libgccjit or LLVM

实际上,C++ 程序可以在运行时生成代码然后使用它(即使那不在 C++ 标准之内)。这就是冯·诺依曼机器的特征。