oraziorillo/microcrad 源码: https://github.com/oraziorillo/microcrad

microcrad

microcrad 是一个针对 C 语言的小型标量值自动微分引擎，并在其之上构建了一个小型神经网络实现。它是 Andrej Karpathy 的 micrograd (https://github.com/karpathy/micrograd) 在 C 语言中的重新实现，专为想要理解反向传播真正工作原理的人编写。与原始 Python 版本一样，microcrad 操作的是标量而非张量。参与计算的每个数字都是图中的一个节点，每个操作都记录其产生方式，一次反向传播则反向遍历图，以计算输出相对于每个输入的导数。没有向量化，没有 GPU，没有巧妙技巧：只有逐标量应用的链式法则。

在此引擎之上是一个多层感知器，因此你可以用 C 语言构建一个网络，执行前向传播，调用反向传播，并执行梯度下降。这个仓库首先是一个教育性实现。它旨在被阅读、实验和测试。不是一个生产级的自动微分包，不是实用的深度学习框架，也没有针对大数据集或数值鲁棒性进行优化。

整个实现基于两个核心思想：

• Value：计算图中的一个节点。
• 引用计数：microcrad 通过它来知道一个 Value 何时不再属于任何图，从而可以被释放。

下面文档中的几乎所有内容都是这两个思想的结果，因此值得记住它们。

Values 的工作原理

基本类型是 Value。一个 Value 包装一个 double，当它是某个操作的结果时，它会记住计算它所用的操作数：

typedef struct Value {
    uint32_t ref_count;       /* 指向该 Value 的引用数量 */
    uint32_t n_prevs;         /* 产生该 Value 的操作数数量 */
    double data;              /* 该节点持有的标量 */
    double extra_data;        /* 操作参数 (例如 pow 中的指数) */
    struct Value **prev;      /* 操作数 (图中的前驱节点) */
    int32_t op_code;          /* 产生该 Value 的操作 */
    uint32_t magic;           /* 用于检测无效或过期指针的调试守卫值 */
    double grad;              /* dLoss/dThisValue，由反向传播填充 */
} Value;

叶节点 Value（输入、权重、常数）的 n_prevs == 0，没有操作数。由加法等操作产生的 Value 的 n_prevs > 0，并且有一个 prev 数组指向它所依赖的操作数。由于每个操作都会将结果链接回其操作数，所有通过 prev 指针可达的 Value 集合构成一个有向无环图：计算图。

下面是一个最简单的 microcrad 程序，计算一个值及其梯度：

Value *a = value_create_leaf(2.0);
Value *b = value_create_leaf(3.0);
Value *c = value_mul(a, b);               /* c = a * b = 6 */
value_backward(c);                         /* 成功时返回0，并填充每个grad字段 */
printf("c = %f\n", c->data);              /* 6.000000 */
printf("dc/da= %f\n", a->grad);           /* 3.000000 (== b) */
printf("dc/db= %f\n", b->grad);           /* 2.000000 (== a) */
value_release(c);                          /* c被释放；释放其对a和b的持有 */
value_release(a);                          /* a被释放（它的另一个引用是你的） */
value_release(b);                          /* b被释放 */

这个小程序已经展示了要点：

• Value 通过 value_create() 在堆上分配。
• value_mul() 等操作构建连接到图中的新 Value。
• value_backward() 计算其参数相对于它所依赖的每个节点的梯度。
• Value 具有引用计数，释放图的根节点会释放整个图（更多内容见下文）。

创建 Values

Value *value_create(double data, int32_t n_prevs, Value **prev);
Value *value_create_leaf(double data);

value_create_leaf 是叶节点（即输入、权重、偏置或常数）的便捷构造函数：

Value *x = value_create_leaf(42.0);

n_prevs/prev 参数的存在是因为操作函数（value_add 等）在内部使用 value_create 来构建结果节点。大多数用户代码应调用 value_create_leaf，让操作函数完成连接。

新创建的 Value 的引用计数为 1：返回给你的指针就是这1个引用。你需要负责释放它。

操作

Value *value_add(Value *v1, Value *v2);   /* v1 + v2 */
Value *value_mul(Value *v1, Value *v2);   /* v1 * v2 */
Value *value_pow(Value *b, double e);     /* b ** e */
Value *value_exp(Value *v);               /* e ** v */
Value *value_log(Value *v);               /* ln(v) */
Value *value_relu(Value *v);              /* max(0,v) */

除非另有说明，这些函数要求非NULL指针和正确形状的输入。本代码力求保持学习路径清晰；它记录了重要的前提条件，但不会像生产级API那样对每次调用进行严格检查。

每个函数返回一个新的 Value，其 data 是操作结果，prev 数组指向操作数。关键的是，每个操作会保留其操作数：它会增加它们的引用计数，这样结果节点在反向传播过程中需要它们时，它们能够保持存活。这意味着结果节点共同拥有其操作数。你仍然拥有调用前持有的引用，仍然需要负责释放它们：

Value *a = value_create_leaf(2.0);   /* a: ref_count 1 (你的) */
Value *b = value_create_leaf(3.0);   /* b: ref_count 1 (你的) */
Value *c = value_add(a, b);           /* a,b 现在 ref_count 2; c ref_count 1 */
/* ... 使用 c ... */
value_release(c);                     /* c被释放；释放其对a和b的持有 */
value_release(a);                     /* a被释放（它的另一个引用是你的） */
value_release(b);                     /* b被释放 */

注意 value_pow 接受一个普通的 double 指数，而不是 Value：只支持常量指数，指数存储在 extra_data 中。

可用的 op_code 包括加法、乘法、幂运算、指数、自然对数和ReLU。这些正是构建ReLU网络所需的基元，可用于均方误差或负对数似然损失，示例中正是这样做的。减法和除法没有单独的操作：减法是通过对操作数取负再相加实现的（玩具示例中就是这样构建 (prediction - target) 项的），除法是通过乘以倒数实现的，该倒数可以是示例中用于损失缩放而预计算的常量，也可以是 value_pow(x, -1.0)（当除数本身是图中的一个节点时）。

反向传播

int value_backward(Value *v);

value_backward 计算 v 相对于其传递依赖的每个节点的梯度，并将每个结果存储在该节点的 grad 字段中。它的工作方式与 micrograd 完全一样，分为两步：

1. 对以 v 为根的图执行深度优先拓扑排序，使得每个节点出现在它所依赖的所有节点之后。这使用了内部的 Vector 和 SimpleSet 类型（见下文）来记录顺序并避免重复访问共享节点。
2. 将 v->grad 初始化为 1，然后反向遍历排序后的列表，对于每个节点，根据产生它的操作的局部导数（链式法则）将其梯度传递给它的操作数。

成功时返回 0，失败时返回 -1。

前提条件：v 必须非NULL且指向一个有效的计算图根节点。

如果你在循环中进行训练，在调用 value_backward 之前，必须清零你不想累积的任何梯度。因为梯度会在操作数上累积（+=），图中被多次使用的 Value 会正确接收从每条路径回流回来的梯度之和。这就是为什么 value_backward 不会为你重置梯度：如果你在循环中训练，必须在每次反向传播之前自己将 grad 字段清零。两个训练示例都这样做：

for (size_t i = 0; i < parameters->size; i++)
    vector_get(parameters, i)->grad = 0.0;   /* 清零梯度 */
value_backward(loss);                         /* 累积新的梯度 */
for (size_t i = 0; i < parameters->size; i++) {
    Value *p = vector_get(parameters, i);
    p->data -= learning_rate * p->grad;       /* 梯度下降步骤 */
}

内存管理：引用计数

C 语言没有垃圾回收，而计算图是一团共享指针的缠绕：同一个权重 Value 可能是数千个结果节点的操作数，同一个中间结果可能馈送到多个下游操作。手动正确释放这样的图容易出错。microcrad 采用和许多长期运行的 C 程序相同的方式来解决这个问题：引用计数。

void value_retain(Value *v);   /* 获取引用：ref_count++ */
void value_release(Value *v);  /* 释放引用：ref_count-- */

规则很简单：

• 每个 Value 出生时引用计数为 1，归调用创建它的函数的人所有。
• value_retain 记录有新的持有者正在持有该 Value。
• value_release 记录一个持有者已经用完它。当计数降到零时，Value 被释放，并且会首先释放它自己的操作数，这可能导致它们也被释放，依此类推，递归地向下释放图。

递归释放是重要部分：你几乎永远不会逐个节点地释放图。你释放图的根节点（损失、前向传播的输出），然后引用计数向下级联，恰好只释放那些没有其他东西仍在持有的节点。权重（也被网络结构持有）会存活；纯粹的中间结果（仅被你刚刚释放的结果所持有）会被释放。

value_release 可以安全地在 NULL 上调用，因此你不需要对它进行守卫检查。这使得可能中途失败的函数中的清理路径更容易编写：你可以无条件地释放所有内容：

value_release(maybe_null);  /* 如果 maybe_null 是 NULL，则什么都不做 */

关于 magic 字段的说明

每个 Value 携带一个 magic 标记，在节点创建时设置为一个已知常量。value_retain 和 value_release 会检查它，value_release 在递归释放节点之前会毒化它。这是一个调试守卫值，不是正确性保证：它有助于在你实验时捕获一些无效或过期的 Value * 使用，但不能替代正确的所有权推理。如果你看到 microcrad 抱怨某个 Value * 无效或过期，几乎可以肯定你有一个引用计数错误。

这种设计的优缺点

引用计数提供了正确性和组合性，但需要付出代价。

缺点 #1：你必须平衡每一个引用。每个 value_create、value_retain 以及每个操作对其操作数的隐式保留，都必须有一个对应的 value_release。少一个就会泄漏；多一个就会释放仍在使用的内存。examples/ 中的训练示例之所以冗长，正是因为它们在错误路径上对此小心翼翼；这种冗长是避免 C 语言泄漏的代价。

缺点 #2：操作共同拥有它们的操作数，这可能会让你感到惊讶。在 Value *c = value_add(a, b) 之后，即使你释放了你自己对 a 和 b 的引用，c 仍会保持它们存活。这是递归释放得以工作的原因，但意味着你不能孤立地推理单个 Value 的生命周期，必须考虑整个图。

优点 #1：图可以自我释放。释放根节点，任何其他东西都不再引用的整个子图就会在一个调用中消失。不需要编写图遍历代码，不需要记录哪些中间结果需要释放。

优点 #2：共享是免费且正确的。一个在万次乘法中使用的权重，只是被保留了万次；它既不会过早也不会过晚被释放。同样的性质使得 value_backward 能够在共享节点上正确地累积梯度。

神经网络实现

在自动微分引擎之上，microcrad 提供了构建前馈网络所需的三个组件。每个组件都是一个薄结构，其参数是 Value，因此前向传播会自动构建一个你可以进行反向传播的计算图。

Neuron *neuron_create(uint32_t nin);
Value *neuron_forward(Neuron *n, Value **x);
Layer *layer_create(uint32_t nin, uint32_t nout);
Value **layer_forward(Layer *l, Value **x);
MLP *mlp_create(uint32_t nin, uint32_t *nouts, uint32_t n_layers);
Value **mlp_forward(MLP *mlp, Value **x);

这些前向函数假定调用者传入正确长度的数组：neuron_forward 期望 n->nin 个输入，layer_forward 期望构建层时的宽度，mlp_forward 期望模型第一层的宽度。

一个 Neuron 持有 nin 个权重 Value 和一个偏置，全部初始化为小的随机数。其前向传播计算 relu(w·x + b) 并返回单个输出 Value。

一个 Layer 是一个由 nout 个神经元组成的数组，共享相同的输入，其前向传播返回一个包含 nout 个输出 Value 的数组。

一个 MLP 将多个层串联起来，将每一层的输出馈送到下一层。

注意：每个神经元都应用 ReLU，包括输出层中的神经元。这保持了引擎的最小化，但也限制了网络可以表示的内容（其输出始终是非负的），这就是玩具示例针对一个本身非负的函数的原因。这是一个有意的简化，而非疏忽。

要训练模型，你需要网络中每个权重和偏置的扁平列表，以便在单个循环中清零梯度并应用更新。每一层都公开了一个：

Vector *neuron_parameters(Neuron *n);
Vector *layer_parameters(Layer *l);
Vector *mlp_parameters(MLP *mlp);

mlp_parameters 返回一个 Vector，其中包含网络中的每个可训练标量。这是你迭代执行梯度下降的列表，如上面反向传播节所示。

整合在一起

下面是一个完整训练步骤的轮廓，与两个示例使用的形状相同：

uint32_t nouts[] = {8, 1};
MLP *model = mlp_create(2, nouts, 2);      /* 一个 2 -> 8 -> 1 的网络 */
Vector *params = mlp_parameters(model);     /* 所有权重的扁平列表 */

/* 前向：构建图 */
Value *inputs[] = { value_create_leaf(x1), value_create_leaf(x2) };
Value **out = mlp_forward(model, inputs);
/* ... 从 out[...] 构建损失 Value ... */

/* 反向 + 更新 */
for (size_t i = 0; i < params->size; i++)
    vector_get(params, i)->grad = 0.0;
value_backward(loss);
for (size_t i = 0; i < params->size; i++) {
    Value *p = vector_get(params, i);
    p->data -= learning_rate * p->grad;
}

/* 清理 */
value_release(loss);
/* ... 释放 out, inputs ... */
vector_free(params);
mlp_free(model);

examples/ 中的两个示例通过具体的训练循环和数据加载充实了这个轮廓。先阅读 train_on_toy_regression.c：它是仓库中最小的完整程序，创建模型、构建图、反向传播、更新参数并运行推理。

辅助数据结构

引擎依赖于两个小型、自包含的数据结构。你通常不直接与它们交互，但了解它们是有益的。

• Vector (vector.h) 是一个动态增长的 Value 指针数组。它以固定大小的块增长，并参与引用计数：vector_append 会保留它存储的 Value，vector_free 会释放它持有的每个 Value。*_parameters 返回的参数列表就是 Vector。
• SimpleSet (simpleset.h) 是一个基于指针标识（Value 的内存地址）的最小集合。它只支持插入和成员测试，这正是 value_backward 的拓扑排序为避免重复访问共享节点所需要的。

构建和测试

microcrad 除了 C 编译器、C 标准库和用于数学函数的 libm 之外没有其他依赖。一切由 Makefile 驱动。

要构建并运行完整的测试套件：

make test