code wiki / _hdl_build / nx_clbg_fannkuch.nx
`nx_clbg_fannkuch.nx` source

↩ module page · 150 lines · 5292 B
1// nx_clbg_fannkuch.nx -- struct-free, pure-integer fannkuch-redux(N).
2//
3// Canonical Computer Language Benchmarks Game integer hot loop. Enumerates all
4// N! permutations of {0..N-1} via the "rotations" odometer (NOT lexicographic),
5// reversing the perm[0]+1 prefix until perm[0]==0 (counting flips) for each.
6//
7// Outputs (written into a caller-owned 2-slot i64 buffer):
8//   out[0] = checksum  (sum of flips with alternating sign +,-,+,- in gen order)
9//   out[1] = maxflips  (max flip count over all permutations)
10//
11// Golden (verified vs gcc -O2 C ref, 2026-06-13):
12//   N=7  -> checksum 228   maxflips 16
13//   N=10 -> checksum 73196 maxflips 38   (X-PERF-003a fixed N)
14//   N=11 -> checksum 556355 maxflips 51
15//
16// Sovereign-compiled (nx_cc_sovereign -> nxasm_x86_main, NO gcc); this is the
17// runtime measured by _xperf003a_gate. spec: knowledge/specs/2026-06-13-clbg-fannkuch-throughput.md
18// genealogy_id: clbg_fannkuch_redux
19// lineage_id: function
20
21import "nx_clock.nx"
22import "nx_itoa_lib.nx"   // shared MSB-first emitter (zero-alloc)
23
24const FK_MAXN: i64 = 32          // perm arrays sized for N up to 32 (golden uses 10)
25const FK_INTSZ: i64 = 8          // i64 per array slot
26const FK_DEFAULT_N: i64 = 10     // X-PERF-003a fixed N (golden checksum 73196 / maxflips 38)
27const FK_REPEAT: i64 = 5         // run the enumeration this many times -> stable timing floor
28
29// fannkuch_redux(n, out): runs the full N! enumeration.
30// out is a caller-mmapped i64[2]; on return out[0]=checksum, out[1]=maxflips.
31// Returns 0 on success, -1 if n is out of the supported [1,FK_MAXN] range.
32func fannkuch_redux(n: i64, out: *i64) -> i64 {
33    if n < 1 { return 0 - 1 }
34    if n > FK_MAXN { return 0 - 1 }
35
36    let perm:  *i64 = sys_mmap(FK_MAXN * FK_INTSZ) as *i64
37    let perm1: *i64 = sys_mmap(FK_MAXN * FK_INTSZ) as *i64
38    let count: *i64 = sys_mmap(FK_MAXN * FK_INTSZ) as *i64
39
40    var i: i64 = 0
41    while i < n {
42        perm1[i] = i
43        i = i + 1
44    }
45
46    var checksum: i64 = 0
47    var maxflips: i64 = 0
48    var sign: i64 = 1
49    var r: i64 = n
50
51    var done: i64 = 0
52    while done == 0 {
53        // refill the odometer to the right of position r
54        while r != 1 {
55            count[r - 1] = r
56            r = r - 1
57        }
58
59        // copy perm1 -> perm
60        var c: i64 = 0
61        while c < n {
62            perm[c] = perm1[c]
63            c = c + 1
64        }
65
66        // flip loop: reverse the perm[0]+1 prefix until perm[0]==0
67        var flips: i64 = 0
68        var k: i64 = perm[0]
69        while k != 0 {
70            var lo: i64 = 0
71            var hi: i64 = k
72            while lo < hi {
73                let t: i64 = perm[lo]
74                perm[lo] = perm[hi]
75                perm[hi] = t
76                lo = lo + 1
77                hi = hi - 1
78            }
79            flips = flips + 1
80            k = perm[0]
81        }
82
83        if flips > maxflips { maxflips = flips }
84        if sign > 0 { checksum = checksum + flips }
85        if sign < 0 { checksum = checksum - flips }
86        sign = 0 - sign
87
88        // advance odometer: left-rotate growing prefixes of perm1
89        var adv: i64 = 0
90        while adv == 0 {
91            if r == n {
92                out[0] = checksum
93                out[1] = maxflips
94                return 0
95            }
96            let perm0: i64 = perm1[0]
97            var m: i64 = 0
98            while m < r {
99                perm1[m] = perm1[m + 1]
100                m = m + 1
101            }
102            perm1[r] = perm0
103            count[r] = count[r] - 1
104            if count[r] > 0 { adv = 1 }
105            if adv == 0 { r = r + 1 }
106        }
107    }
108    out[0] = checksum
109    out[1] = maxflips
110    return 0
111}
112
113// --- standalone smoke / sovereign timing harness ---
114// Brackets the sovereign permutation hot loop with nx_clock_monotonic_ns() and
115// prints a single machine-parseable line the gate reads back:
116//   FANNKUCH_SOV n=<N> checksum=<..> maxflips=<..> sov_us=<..> reps=<..>
117// sov_us = wall time of FK_REPEAT enumerations / FK_REPEAT (per-run floor).
118
119func fk_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
120// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
121// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
122// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
123// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
124func fk_putn(v: i64) -> i64 { nxi_out(v); return 0 }
125
126func main() -> i64 {
127    let out: *i64 = sys_mmap(2 * FK_INTSZ) as *i64
128    out[0] = 0
129    out[1] = 0
130
131    // SOVEREIGN HOT LOOP -- bracketed by the monotonic clock.
132    let t0: i64 = nx_clock_monotonic_ns()
133    var rep: i64 = 0
134    while rep < FK_REPEAT {
135        fannkuch_redux(FK_DEFAULT_N, out)
136        rep = rep + 1
137    }
138    let t1: i64 = nx_clock_monotonic_ns()
139
140    let total_us: i64 = (t1 - t0) / 1000
141    let sov_us: i64 = total_us / FK_REPEAT
142
143    fk_puts("FANNKUCH_SOV n=" as *u8); fk_putn(FK_DEFAULT_N)
144    fk_puts(" checksum=" as *u8); fk_putn(out[0])
145    fk_puts(" maxflips=" as *u8); fk_putn(out[1])
146    fk_puts(" sov_us=" as *u8); fk_putn(sov_us)
147    fk_puts(" reps=" as *u8); fk_putn(FK_REPEAT)
148    fk_puts("\n" as *u8)
149    return 0
150}
nx_clbg_fannkuch.nx source

`nx_clbg_fannkuch.nx` source
