Nim 编程语言内存模型研究

2024-06-15 - 乙酉甲辰年庚午庚戌 - 农历五月初十晴，中午短时间小雨

海云青飞翻译

序

这是 Nim 编程语言如何在内存中存储数据的教程，它将解释每个 Nim 程序员都应该知道的基本知识，也将更深入地探讨 Nim 组织其数据结构（如字符串和序列）的方式

Nim 会负责程序的所有内存管理，只要使用语言的安全部分，就几乎不需要使用内存地址或进行显式的内存分配

但是，当 Nim 代码与外部 C 代码或 C 库进行互操作时，这种情况会发生变化——在这种情况下，可能需要知道 Nim 对象在内存中的存储位置和存储方式，以便将其传递给 C，或者需要知道如何访问 C 分配的数据以使 Nim 可以访问它

具有 C 或 C++ 背景的读者会熟悉本文档的第一部分，因为其中很多不是 Nim 语言所独有的。相反，对于动态语言（例如 Python 或 Javascript ）的程序员来说，有些事情可能是新事物，在这些语言中，内存处理更加抽象

本文档的大多数（如果不是全部）适用于 C 和 C++ 代码生成器，因为 Javascript 后端不使用原始内存，而是依赖 Javascript 对象

计算机内存基础

本节并从 CPU 和计算机程序的角度简要介绍了计算机内存

字大小

计算机的主存（RAM）包含许多内存位置，每个内存位置都有唯一地址。取决于 CPU 架构，每个内存位置的大小（“字大小”）通常在一个字节（8位）到八个字节（64位）之间变化，而 CPU 通常也能够以较小的块形式访问较大的字。一些架构可以从任意地址读取和写入内存，而其他架构只能访问字长倍数的地址的内存

CPU 使用特定指令访问内存，这些指令允许它从给定地址读取或写入给定字大小的数据。例如，它可能将值 0x12345 作为 32 位数字存储在地址 0x100000 处。用于执行此操作的低级汇编指令可能如下所示：

mov [0x100000], 0x12345

这是上述指令完成后地址 0x100000 上的存储器的样子，每一列代表一个字节：

            00   01   02   03   04
          +----+----+----+----+----
0x100000  | 00 | 01 | 23 | 45 | ..
          +----+----+----+----+----

字节序

更复杂的是，一个字中字节的实际顺序因 CPU 类型而异——有些 CPU 将最高有效字节放在首位，而其他 CPU 则将最低有效字节放在首位。这称为 CPU 的字节序

如今，大多数 CPU （Intel兼容、x86、amd64、大多数ARM家族）都是小端，整数 0x1234 首先存储最低有效字节，例如：
```
  00   01
+----+----+
| 34 | 12 |
+----+----+
```
海云青飞注：多数 CPU 使用小端字节序，应该是历史原因
飞思卡尔（Freescale）或 OpenRISC 等其他 CPU 都是大端。整数 0x1234 的最高有效字节在前。在网络上发送数据时，大多数网络协议都以大端顺序对数据进行序列化。这就是为什么大端也被称为网络字节序的原因。例如：
```
 00   01
+----+----+
| 12 | 34 |
+----+----+
```
海云青飞注：网络是后来出现的，人类更容易理解大端字节序，所以网络协议多使用大端字节序

最重要的是：如果要编写可移植的代码，则在将二进制数据写入磁盘或通过网络写入时，切勿对计算机的字节序做任何假设，并确保将数据显式转换为适当的字节序

组织内存的两种方式

传统上，C 程序使用两种用于组织计算机内存中对象的常用方法：栈和堆。两种方法都有不同的用途，并且具有不同的特征。 Nim 代码被编译为 C或 C++ 代码，因此 Nim 自然共享这些语言的内存模型

栈

栈是内存的一个区域，总是在其中从一端添加和删除数据。这称为“后进先出”（LIFO）

栈理论，从“栈”到“气”

人类用概念思考，好的概念命名能够提高人类的思维效率，不幸的是很多人不知道这个原理，导致很多概念的名字不能直观反映其含义，计算机术语的栈和堆就是很好的例子。愚笨的人花费很多生命时间去记忆别人给出的知识，智者则总是在创造性地命名概念及改进对概念的命名。现在海云青飞就来尝试改进对“栈”和“堆”的命名

栈，重命名为气
堆，重命名为沉

现在先来说一下什么是气。气，代表轻而上浮。可想而知，沉，表示重而下觉

气，可用气球来辅助理解。你有数量不定的气球，如果气球到处乱飘，这样显然不行，于是你做了一个口朝下的通道，通道只允许一个气球通过，然后你把所有气球放入通道，需要时就从通道底下取气球

由于历史原因，计算机栈通常自上而下工作：将新数据添加到栈底部或从栈底部删除，但这不会更改机制本身

+--------------+ <-- stack top
|              |
|   in use     |
|              |
|              |
+--------------+ <-- stack pointer
|              |
|              | | new data added
:    free      : v on the bottom

下面海云青飞就用气来取代原来的栈，你看到气，就会想起我前面说过的气球的例子，于是你就永远不会忘记气的数据存取特征

气的管理非常简单：程序只需要跟踪指向当前气底部的一个地址，即通常称为气指针的地址。将数据添加到气时，将数据复制到位并减少气指针。从气中删除数据时，会将其复制出来，并再次增加气指针

气实践

在 Nim ，C 和大多数其他编译语言中，气用于两个不同的目的：

首先，它用作存储临时局部变量的地方。这些变量仅在函数处于活动状态（即未返回）时存在
编译器还将气用于其他类型：每次调用函数时，将调用指令之后的下一条指令的地址放在气上——这是返回地址。函数返回时，它将在气上找到该地址，然后跳转到该地址

以上两种机制的组合数据构成一个气帧：这是气的一部分，其中包含当前活动函数的返回地址及其所有局部变量

在程序执行期间，如果程序嵌套了两个函数，则气将是这样：

+----------------+ <-- stack top
| return address |
| variable       | <-- stack frame #1
| variable       |
| ...            |
+----------------+
| return address |
| variable       | <-- stack frame #2
| ...            |
+----------------+ <-- stack pointer
|     free       |
:                :

对数据和返回地址使用气是一个很巧妙的技巧，并且具有为程序中的数据提供自动存储分配和清除的良好副作用

气也可以很好地与线程配合使用：每个线程仅具有自己的气，存储自己的局部变量，并拥有自己的气框架

现在知道了 Nim 在遇到运行时错误或异常时生成气跟踪时从何处获取信息：它将查找气上最里面的函数地址，并打印其名称。然后，它一直在气中进一步查找下一级函数，一直到最上层

堆

气旁边的堆是在计算机程序中存储数据的另一个位置。虽然气通常用于保存局部变量，但堆可以用于动态的存储

堆理论

堆是一个有点像仓库的内存区域。内存区域称为分配区(arena)：

:              : ^ heap can grow at the top
|              | |
|              |
|    free!     | <--- The heap arena
|              |
|              |
+--------------+

当程序要存储数据时，它将首先计算需要多少存储空间。然后它将去仓库职员（内存分配器）并请求一个存储数据的地方。职员有一个分类帐，在其中跟踪仓库中的所有分配，它将找到一个足够大的空位来容纳数据。然后它将在账本(ledger)中输入该地址和大小的区域已被占用，并将该地址返回给程序。该程序现在可以随意从该区域的内存中存储和检索其数据

:              :
|    free      |
|              |
+--------------+
|  allocated   | <--- allocation address
+--------------+

可以重复上述过程，在堆上分配其他大小不同的块：

:              :
|    free      |
+--------------+
|              |
| allocated #3 |
|              |
+--------------+
| allocated #2 |
+--------------+
| allocated #1 |
+--------------+

当不再使用数据块时，程序将告诉内存分配器该块的地址。分配器在账本(ledger)中查找地址，并删除条目。该块现在供后续自由使用。这是释放块＃2时的上图所示：

:              :
|    free      |
+--------------+
|              |
| allocated #3 |
|              |
+--------------+
|    free      | <-- There's a hole in the heap!
+--------------+
| allocated #1 |
+--------------+

如图所示，释放块＃2现在会在堆中留下一个空内存，这可能会在将来导致问题。考虑下一个分配请求：

如果下一个分配的大小小于空内存的大小，则分配器可能会重用空内存中的可用空间；但是由于新的请求较小，因此在新块之后将保留一个新的较小空内存
如果下一个分配的大小大于空内存的大小，则分配器必须在某处找到更大的地方，从而使空内存保持打开状态

有效地重复使用空内存的唯一方法是下一次分配的孔大小是否完全相同

大量使用具有许多不同大小的对象的堆可能会导致称为碎片的现象。这意味着分配器无法有效地使用分配区来满足分配请求，从而实际上浪费了一部分可用内存

堆实践

在 Nim 中，除非明确要求将所有数据存储在堆上，否则所有数据将存储在气上：通常使用 new()、proc 时在堆上为新对象分配内存：

type Thing = object
    a: int

var t = new Thing

上面的代码片段将在堆上分配内存以存储 Thing 类型的对象。新分配的内存块的地址由 new 返回，现在为 ref Thing 类型。 ref 是一种特殊的指针，通常由 Nim 管理。在“跟踪的引用和垃圾收集器”部分中对此进行了详细介绍

Nim 中的内存组织

只要使用语言的安全部分， Nim 就会管理内存分配，这将确保数据存储在适当的位置，并在不再需要时将其释放。如果需要，Nim 也会提供完全控制，可以精确选择存储数据的方式和位置

Nim 提供了一些方便的功能，可检查内存中数据的组织方式。这些将在以下各节的示例中使用，以检查 Nim 如何以及在何处存储数据：

addr(x)

此 proc 返回变量 x 的地址。对于类型T的变量，其地址将具有类型 ptr T
unsafeAddr(x)

此 proc 基本上与 addr() 相同，但是即使 Nim 认为获取对象的地址并不安全，也可以使用它-稍后将对此进行更多介绍
sizeof(x)

返回变量x的大小（以字节为单位）
typeof(x)

返回变量x类型的字符串表示形式

类型 T 的对象上的 addr(x) 和 unsafeAddr(x) 的结果具有 ptr T 类型的结果。Nim 不知道如何打印，因此我们将使用 repr() 格式化输入：

var a: int
echo a.addr.repr
# ptr 0x56274ece0c60 --> 0

使用指针

基本上，指针不过是一种特殊类型的变量，它拥有一个内存地址，即它指向内存中的其他内容。如上所述，在 Nim 中有两种类型的指针：

ptr T 用于未跟踪的引用，也称为指针
ref T 用于跟踪的引用，用于由 Nim 管理的内存

ptr T 指针类型被认为是不安全的。指针指向手动分配的对象或内存中其他地方的对象，作为程序员，任务是确保指针始终指向有效数据

当需要访问指针所指向的内存中的数据时（即带有该数字索引的地址的内容），需要取消引用 dereference（或简称为 deref）指针

在 Nim 中，可以使用空数组下标 [] 来执行此操作，类似于在 C 中使用 * 前缀运算符。下面的代码段显示了如何为int创建别名并更改其值

var a = 20
var p = a.addr
p[] = 30
echo a  # --> 30

在此声明一个普通变量 a 并使用值 20 对其进行初始化
p 是 ptr int 类型的指针，指向 int 的地址 a
[] 运算符用于取消引用指针 p。由于 p 是 ptr int 类型的指针，它指向存储 a 的内存地址，因此取消引用的变量 p [] 也是 int 类型。现在，变量 a 和 p[] 指的是完全相同的内存位置，因此将值分配给 p[] 也将更改 a 的值

对于对象或元组访问， Nim 将执行自动取消引用，普通的 . 访问运算符可以与普通对象一样使用

气：局部变量

局部变量（也称为自动变量）是 Nim 存储变量和数据的默认方法

Nim 将在气上为变量保留空间，并且只要它在范围内，就会一直存在。实际上，这意味着只要声明它的函数不返回，该变量就将存在。一旦函数返回气就会展开，并且变量也消失了

以下是一些将存储在气中变量的示例：

type Thing = object
    a, b: int

var a: int
var b = 14
var c: Thing
var d = Thing(a: 5, b: 18)

跟踪的引用和垃圾收集器

在前面的部分中，我们看到由 addr() 返回的 Nim 中的指针的类型为 ptr T，但是我们看到 new 的返回值为 ref T`

虽然 ptr 和 ref 都是数据指针，但两者之间有一个重要区别：

ptr T 只是一个指针，即持有地址的变量，该地址指向其他地方的数据。作为程序员，有责任确保使用该指针时，它指向有效的内存
ref T 是一个跟踪的引用：这也是指向其他内容的地址，但是 Nim 会跟踪指向的数据，并确保在不再需要它时将其释放

获取 ref T 指针的唯一方法是使用 new() 、proc 分配内存。Nim 将保留内存，还将开始跟踪该数据在代码中的引用位置。当 Nim 运行时看到不再引用该数据时，它便知道丢弃数据是安全的，它将自动释放数据。这就是所谓的垃圾回收，简称 GC

Nim 如何在内存中存储数据

本节将展示一些实验，在这些实验中我们将研究 Nim 如何在内存中存储各种数据类型原始类型

基本或标量类型是“单个”值，例如 int，bool 或 float。标量通常保存在气中，除非它们是容器类型（如对象）的一部分让我们看看 Nim 如何为我们管理原始类型的内存

下面的代码段首先创建一个类型为 int 的变量 a，并打印该变量及其大小。然后，它将创建第二个类型为 ptr int 的变量 b，称为指针，现在保存变量 a 的地址

var a = 9
echo a.repr
echo sizeof(a)

var b = a.addr
echo b.repr
echo sizeof(b)

在我的机器上，我可能会得到以下输出：

9
8
ptr 0x300000 --> 9
8

输出的第一行，这是变量 a 的值
第二行，这是变量的大小，以字节为单位。 8 个字节可生成 64 位，这恰好是计算机上 Nim 中int类型的默认大小。到现在为止还挺好
第三行，表示变量 b 的表示。 b 包含变量 a 的地址，该变量恰好位于地址 0x300000。在 Nim 中，地址称为 ref 或指针
b 本身也是一个变量，它不是 ptr int 类型的。在我的机器上，地址的大小也为 64 位，等于 8 个字节

以上内容可以用下图表示：

           +---------------------------------------+
0x??????:  | 00 | 00 | 00 | 00 | 30 | 00 | 00 | 00 | b: ptr int =
           +---------------------------------------+    0x300000
                               |
                               |
                               v
           +---------------------------------------+
0x300000:  | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 09 | a: int = 9
           +---------------------------------------+

复合类型：对象

让我们将一个更复杂的对象放到气上，看看会发生什么：

type Thing = object
    a: uint32
    b: uint8
    c: uint16

var t: Thing

echo "size t.a ", t.a.sizeof
echo "size t.b ", t.b.sizeof
echo "size t.c ", t.c.sizeof
echo "size t   ", t.sizeof

echo "addr t.a ", t.a.addr.repr
echo "addr t.b ", t.b.addr.repr
echo "addr t.c ", t.c.addr.repr
echo "addr t   ", t.addr.repr

我们的对象类型 Thing 的定义，其中包含各种大小的整数
创建Thing 类型的变量 t
打印t 的大小及其所有字段
打印 t 的地址及其所有字段

在 Nim 中，对象只是将变量分组到一个方便的容器中的一种方法，请确保将变量与 C 一样放置在内存中这是我机器上的输出：

size t.a 4
size t.b 1
size t.c 2
size t   8
addr t   ptr 0x300000 --> [a = 0, b = 0, c = 0]
addr t.a ptr 0x300000 --> 0
addr t.b ptr 0x300004 --> 0
addr t.c ptr 0x300006 --> 0

让我们看一下输出：

首先获取对象字段的大小。 a 被声明为一个 uint32，它是4个字节大，b 是一个 uint8，它是 1 个字节，而 c 是一个 uint16，它是 2 个字节大。校验！
这有点令人惊讶：打印容器对象t的大小，看起来好像是 8 字节大。但这并没有加起来，因为对象的内容只有 4 + 1 + 2 = 7 个字节！在下面将解释细节
让我们获取对象 t 的地址：在我的机器上，它被放置在气上的地址 0x300000
在这里我们可以看到字段 t.a 与对象本身在内存中的位置完全相同：0x300000。t.b 的地址是 0x300004，即 t.a 之后的 4 个字节。这是有道理的，因为 t.a 为四个字节
t.c 的地址是 0x300006，它是 t.b 之后的 2 个字节，但是 t.b 只有一个字节大吗？

因此，让我们来简要了解一下我们从上面学到的知识：

            00   01   02   03   04   05   06   07
        +-------------------+----+----+---------+
0x300000:  | a                 | b  | ?? | c       |
        +-------------------+----+----+---------+
        ^                   ^         ^
        |                   |         |
        address of           addr       addr
        t and t.a           of t.b     of t.c

这就是我们的 Thing 对象在内存中的样子。那么标记为空内存是怎么回事呢？在偏移量 5 处，为什么总大小不是 7 个而是 8 个字节？

这是由编译器执行的操作（称为对齐）引起的，该操作使 CPU 可以更轻松地访问内存中的数据。通过确保对象在内存中以其大小的倍数（或体系结构字大小的倍数）很好地对齐， CPU 可以更有效地访问内存。这通常会导致代码更快，但会浪费一些内存

（可以提示 Nim 编译器不要进行对齐，就是使用 {.packed.} 编译指示将对象的字段连续放置在内存中，有关详细信息，请参阅 Nim 语言手册）

字符串和序列

以上各节介绍了 Nim 如何在内存中管理相对简单的静态对象。本节将介绍更复杂和动态的数据类型的实现，这些数据类型是 Nim 语言的一部分：字符串和序列

在 Nim 中，字符串和序列数据类型密切相关。这些基本上是一排相同类型的对象（字符串为 char，序列为其他任何类型）。这些类型的不同之处在于它们可以动态增加或缩小内存

谈一谈序列

让我们创建一个序列并进行一些实验：

var a = @[ 30, 40, 50 ]

让我们问一下 Nim 变量 a 的类型是什么：

var a = @[ 30, 40, 50 ]
echo typeof(a)   # -> seq[int]

我们看到类型是 seq[int]，与预期一致

现在，让我们添加一些代码来查看 Nim 如何存储数据：

var a = @[ 0x30, 0x40, 0x50 ]
echo a.repr
echo a.len
echo a[0].addr.repr
echo a[1].addr.repr

这是我机器的输出：

ptr 0x300000 --> 0x900000@[0x30, 0x40, 0x50]
3
ptr 0x900010 --> 0x30
ptr 0x900018 --> 0x40

从中可以得出什么？

变量 a 本身放置在气上，该气恰好在我的计算机上的地址 0x300000 上。 a 是某种指针，它指向堆上的地址 0x900000！这就是实际序列的所在
该序列包含3个元素，正如应该的那样
a[0] 是序列的第一个元素。它的值为 0x30，i存储在序列本身之后的地址 0x900010 中
序列中的第二项是 a[1]，它位于地址 0x900018 中。这很合理，因为 int 的大小为 8`个字节，并且序列中的所有 int 都连续放置在内存中

让我们再画一下。我们知道 a 是存在气上的指针，它指向堆上大小为 16 个字节的内容，后跟序列的元素：

             stack
           +---------------------------------------+
0x300000   | 00 | 00 | 00 | 00 | 90 | 00 | 00 | 00 | a: seq[int]
           +---------------------------------------+
                               |
             heap              v
           +---------------------------------------+
0x900000   | ?? | ?? | ?? | ?? | ?? | ?? | ?? | ?? |
           +---------------------------------------+
0x900008   | ?? | ?? | ?? | ?? | ?? | ?? | ?? | ?? |
           +---------------------------------------+
0x900010   | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 30 | a[0] = 0x30
           +---------------------------------------+
0x900018   | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 40 | a[1] = 0x40
           +---------------------------------------+
0x900020   | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 50 | a[2] = 0x50
           +---------------------------------------+

除了块开头的 16 个未知字节之外，这几乎解释了所有序列： Nim 在此区域存储有关序列的内部信息

通常，这些数据对用户是隐藏的，但是可以在 Nim 系统库中简单地找到此头部的实现，如下所示：

type TGenericSeq = object
    len: int
    reserved: int

Nim 使用len字段存储序列的当前长度——即其中有多少个元素
保留字段用于跟踪序列中存储器的实际大小，出于性能原因， Nim 可能会提前保留更大的空间，以避免在需要添加新项目时调整序列的大小

让我们做一个小实验来检查序列标头中的内容：

type TGenericSeq = object
    len, reserved: int

var a = @[10, 20, 30]
var b = cast[ptr TGenericSeq](a)
echo b.repr

原始的 TGenericSeq 对象不是从系统库中导出的，因此这里定义了相同的对象
在这里，变量 a 被强制转换为 TGenericSeq 类型

当我们使用 echo b.repr 打印结果时，输出如下所示：

ptr 0x900000 --> [len = 3, reserved = 3]

我们知道了这些信息：我们的序列大小为 3 ，并且总共为 3 个元素保留了空间。下一节将说明将更多字段添加到序列中时会发生什么

序列增长

下面的代码段以相同的序列开始，然后添加新的元素。每次迭代将打印序列标头：

type TGenericSeq = object
    len, reserved: int
var a = @[10, 20, 30]
for i in 0..4:
    echo cast[ptr TGenericSeq](a).repr
    a.add i

这是输出，看是否可以发现有趣的事情：

ptr 0x900000 --> [len = 3, reserved = 3] <1>
ptr 0x900070 --> [len = 4, reserved = 6] <2>
ptr 0x900070 --> [len = 5, reserved = 6] <3>
ptr 0x900070 --> [len = 6, reserved = 6]
ptr 0x9000d0 --> [len = 7, reserved = 12] <4>

输出的第一行，这是原始的 3 个元素序列：它存储在地址为 0x900000 的堆中，长度为 3 个元素，并且还为3个元素保留了存储空间
第二行，添加了一个元素，并且有一些值得注意的事情：
- len 字段增加到 4，这很有意义，因为序列现在包含 4 个元素
- 保留字段从 3 增加到 6。这是因为 Nim 在进行新分配时会将存储大小增加了一倍——当重复添加数据而不必为每个 add() 调整分配大小时，这样做会更有效率
- 请注意，序列本身的地址也已更改。原因是堆上序列数据的初始内存分配不足以容纳新元素，因此 Nim 必须找到更大的内存块来保存数据。分配器可能已经将序列后面的区域保留给其他区域，因此无法扩大该区域。相反，在堆上其他位置进行了新分配，将序列的旧数据从旧位置复制到了新位置，并添加了新元素
当在上面添加第 4 个元素时， Nim 调整了序列存储的大小，以容纳 6 个元素-这可以增加两个元素，而不必进行更大的分配。现在，序列中放置了 6 个元素，总共保留了 6 个元素的大小
此处再次发生相同的情况：块的大小不足以容纳第7个项目，因此整个序列被移至另一个位置，并且分配规模扩大到可容纳 12 个元素

结论

该文档仅涉及 Nim 处理内存的方式，还有很多要说的。以下是我认为值得一写但还没有写过的主题：

有关垃圾回收以及 Nim 中可用的GC的详细讨论
在没有垃圾收集器的情况下使用 Nim / 具有紧凑内存的嵌入式系统
新 Nim 运行时
闭包、迭代器、异步中的内存使用——局部变量并不总是放在气上
FFI：在 C 和 Nim 之间传递数据的讨论和示例

这是一个还在完善的文档，欢迎评论。可以在github上找到源代码，网址为https://github.com/zevv/nim-memory

海云青飞官方网站