GitHub - oraziorillo/microcrad: A re-implementation of Karpathy's micrograd in C
Pangram verdict · v3.3
We believe that this document is a mix of AI-generated, AI-assisted, and human-written content
AI likelihood · overall
MixedArticle text · 1,672 words · 6 segments analyzed
microcrad is a tiny scalar-valued automatic differentiation engine for C, with a small neural network implementation built on top of it. It is a re-implementation of Andrej Karpathy's micrograd in C, written for people who want to understand how backpropagation really works. Like the Python original, microcrad operates on scalars, not tensors. Every number that takes part in a computation is a node in a graph, every operation records how it was produced, and a single backward pass walks the graph in reverse to compute the derivative of the output with respect to every input. There is no vectorization, no GPU, no clever tricks: just the chain rule applied one scalar at a time. On top of this engine sits a multi-layer perceptron, so you can build a network, run a forward pass, call backward, and do gradient descent, all in C. This repository is first and foremost an educational implementation. It is meant to be read, experimented with, and tested. It is not a production autograd package, not a practical deep-learning framework, and not optimized for large datasets or numerical robustness. The whole thing is built around two ideas:
A Value, which is a single node in the computation graph. Reference counting, which is how microcrad knows when a Value is no longer part of any graph and can be freed.
Almost everything in the documentation below is a consequence of these two ideas, so it is worth keeping them in mind. How Values work The fundamental type is Value. A Value wraps a single double and, when it is the result of an operation, remembers the operands it was computed from: typedef struct Value { uint32_t ref_count; /* How many references point at this Value. */ uint32_t n_prevs; /* How many operands produced this Value. */ double data; /* The scalar this node holds. */ double extra_data; /* Operation parameter (e.g. the exponent in pow). */ struct Value **prev; /* The operands (previous nodes in the graph). */ int32_t op_code; /* Which operation produced this Value. */ uint32_t magic; /* Debug canary for some invalid or stale pointers. */
double grad; /* dLoss/dThisValue, filled in by backward. */ } Value; A leaf Value (an input, a weight, a constant) has n_prevs == 0 and no operands. A Value produced by an operation such as addition has n_prevs > 0 and a prev array pointing at the operands it depends on. Because every operation links its result back to its operands, the set of all Values reachable through prev pointers forms a directed acyclic graph: the computation graph. This is the simplest microcrad program that computes something and its gradient: 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); /* returns 0 on success, and fills every grad field */
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 freed; releases its hold on a and b */ value_release(a); /* a freed (its other reference was yours) */ value_release(b); /* b freed */ This small program already shows the essentials:
Values are heap allocated with value_create(). Operations such as value_mul() build new Values wired into the graph. value_backward() computes the gradient of its argument with respect to every node it depends on. Values are reference counted, and releasing the root of a graph releases the whole graph (more on this below).
Creating Values Value *value_create(double data, int32_t n_prevs, Value **prev); Value *value_create_leaf(double data); value_create_leaf is the convenience constructor for a leaf node, that is, an input, a weight, a bias, or a constant: Value *x = value_create_leaf(42.0); The n_prevs/prev arguments exist because the operation functions (value_add and friends) use value_create internally to build result nodes. Most user code should call value_create_leaf and let the operations do the wiring. A freshly created Value starts with a reference count of 1: the pointer returned to you is that one reference. It is your job to release it. Operations 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) */ Unless stated otherwise, these functions expect non-NULL pointers and correctly shaped inputs. This code aims to keep the learning path clear; it documents important preconditions, but it does not try to harden every call like a production-grade API would. Each of these returns a new Value whose data is the result of the operation and whose prev array points at the operands. Crucially, each operation retains its operands: it bumps their reference count so that the result node keeps them alive for as long as it needs them for the backward pass. This means a result node co-owns its operands.
You still own the references you were holding before the call, and you are still responsible for releasing them: Value *a = value_create_leaf(2.0); /* a: ref_count 1 (yours) */ Value *b = value_create_leaf(3.0); /* b: ref_count 1 (yours) */ Value *c = value_add(a, b); /* a,b now ref_count 2; c ref_count 1 */
/* ... use c ... */
value_release(c); /* c freed; it releases its hold on a and b */ value_release(a); /* a freed (its other reference was yours) */ value_release(b); /* b freed */ Note that value_pow takes a plain double exponent, not a Value: only constant exponents are supported, and the exponent is stored in extra_data. The available op_codes are addition, multiplication, power, exponential, natural logarithm and ReLU. These are exactly the primitives needed to build a ReLU network with a mean-squared-error or negative-log-likelihood loss, which is what the examples do. Subtraction and division are not separate operations: subtraction is addition with a negated operand (the toy example builds its (prediction - target) term this way), and division is multiplication by a reciprocal, either a constant precomputed with value_create as the examples do for their loss scaling, or value_pow(x, -1.0) when the divisor is itself a node in the graph. Backpropagation int value_backward(Value *v); value_backward computes the gradient of v with respect to every node it transitively depends on, storing each result in that node's grad field. It works in two steps, exactly like micrograd:
It performs a depth-first topological sort of the graph rooted at v, so that every node appears after all the nodes it depends on. This uses the internal Vector and SimpleSet types (see below) to record the ordering and to avoid visiting a shared node twice. It seeds v->grad = 1 and walks the sorted list in reverse, and for each node it pushes its gradient onto its operands according to the local derivative of the operation that produced it (the chain rule).
It returns 0 on success and -1 on failure.
Precondition: v must be non-NULL and must point at a valid computation graph root. If you are training in a loop, you must also zero any gradients you do not want to accumulate before calling it. Because gradients accumulate (+=) onto the operands, a Value that is used in more than one place in the graph correctly receives the sum of the gradients flowing back through each path. This is why value_backward does not reset gradients for you: if you are training in a loop, you must zero the grad fields yourself before each backward pass. Both training examples do exactly this: for (size_t i = 0; i < parameters->size; i++) vector_get(parameters, i)->grad = 0.0; /* zero the gradients */
value_backward(loss); /* accumulate new ones */
for (size_t i = 0; i < parameters->size; i++) { Value *p = vector_get(parameters, i); p->data
-= learning_rate * p->grad; /* gradient descent step */ } Memory management: reference counting C has no garbage collector, and a computation graph is a tangle of shared pointers: the same weight Value can be an operand of thousands of result nodes, and the same intermediate result can feed several downstream operations. Freeing such a graph correctly by hand is error prone. microcrad solves this the same way many long-lived C programs do, with reference counting. void value_retain(Value *v); /* take a reference: ref_count++ */ void value_release(Value *v); /* drop a reference: ref_count-- */ The rules are simple:
Every Value is born with a reference count of 1, owned by whoever called the function that created it. value_retain records that someone new is holding the Value. value_release records that a holder is done with it. When the count reaches zero, the Value is freed, and it releases its own operands first, which may in turn free them, and so on recursively down the graph.
The recursive release is the important part: you almost never free a graph node by node. You release the root of the graph (the loss, the output of a forward pass), and the reference counts cascade downward, freeing exactly the nodes that nothing else still holds. Weights, which are also held by the network structure, survive; pure intermediates, which were only held by the result you just released, are freed. value_release is safe to call on NULL, so you do not need to guard against it. This makes cleanup paths in functions that may fail part way through much easier to write, you can release everything unconditionally: value_release(maybe_null); /* does nothing if maybe_null is NULL */ A note on the magic field Every Value carries a magic marker set to a known constant when the node is created. value_retain and value_release check it, and value_release poisons it before recursively freeing the node. This is a debug canary, not a correctness guarantee: it can help catch some invalid or stale Value * usage while you are experimenting, but it is not a substitute for correct ownership reasoning. If you ever see microcrad complaining that a Value * is invalid or stale, you almost certainly have a reference-counting bug.