blob: 2eb5f6aaaffb276467ecd78e96e3e1b61bf55fc3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
# Nock Interpreter Implementations
We have three Nock interpreters with different tradeoffs:
## 1. `nock.ml` - Hybrid (Trampoline + Recursion)
**Strategy**: Uses `loop()` trampoline for some tail calls, but still has recursive `nock_on` calls for distribution and op2.
**Pros**:
- Fastest for simple/medium computations
- Uses OCaml's native call stack for performance
**Cons**:
- **Stack overflow on deep computations** (solid pill lifecycle)
- Requires `OCAMLRUNPARAM='l=100M'` for deep recursion
- Not truly constant stack space
**Performance**: ⭐⭐⭐⭐⭐ (best when it works)
**Use case**: Default interpreter for normal operations
---
## 2. `nock_iter.ml` - Fully Iterative (Work/Result Stacks)
**Strategy**: Zero recursion. Uses explicit work and result stacks stored as lists.
**Pros**:
- **Never stack overflows** - O(1) stack space
- No `OCAMLRUNPARAM` needed
- Predictable memory usage
**Cons**:
- Slower than `nock.ml` (list push/pop overhead)
- More complex to understand
**Performance**: ⭐⭐⭐⭐ (solid, consistent)
**Use case**: When you need guaranteed no-overflow (e.g., untrusted inputs)
---
## 3. `nock_tail.ml` - Continuation-Passing Style (CPS)
**Strategy**: Uses explicit continuations as a queue. Each computation knows what to do with its result.
**Pros**:
- **Never stack overflows** - O(1) stack space
- No `OCAMLRUNPARAM` needed
- Elegant functional style
- Easy to add logging/tracing/debugging
**Cons**:
- Slower than `nock.ml` (continuation allocation overhead)
- Larger heap usage (continuations on heap)
**Performance**: ⭐⭐⭐⭐ (solid, elegant)
**Use case**: When you want beautiful code that never overflows
---
## Benchmark Results
### Simple Operations (1000× increment)
```
nock.ml 0.0001s ← Fastest
nock_iter.ml 0.0002s ← 2x slower
nock_tail.ml 0.0002s ← 2x slower
```
### Complex Operations (ivory pill lifecycle)
```
nock.ml Stack overflow! ✗ (without OCAMLRUNPARAM)
nock_iter.ml Works! ✓ (slow but works)
nock_tail.ml Works! ✓ (slow but works)
```
---
## Recommendation
**For production**: Use `nock.ml` with `OCAMLRUNPARAM='l=100M'` for best performance.
**For robustness**: Use `nock_iter.ml` or `nock_tail.ml` when you can't afford stack overflows.
**For learning/hacking**: Study `nock_tail.ml` - it's the clearest implementation of CPS.
---
## Technical Notes
### Why is `nock.ml` faster?
It uses OCaml's native call stack for tail calls, which is highly optimized in the OCaml runtime. The `loop()` pattern compiles to tight machine code.
### Why are `nock_iter` and `nock_tail` slower?
Every step requires:
- List allocation (`::` operator)
- Pattern matching on list head
- List garbage collection
Native call stack operations are just a stack pointer adjustment - orders of magnitude faster.
### The Fundamental Tradeoff
- **Stack-based** = Fast but can overflow
- **Heap-based** = Slower but never overflows
This is a classic CS tradeoff. You can't have both.
---
## Future Work
- **Jets**: Hand-optimized implementations of common Hoon stdlib functions
- **JIT compilation**: Compile hot paths to native code
- **Parallel execution**: Use `nock_parallel.ml` with Domainslib
- **Memory pooling**: Reuse continuation/stack objects instead of allocating new ones
|
