sketch_freq_directions_vs_topnorm_bench.nx source
↩ module page · 223 lines · 6369 B
1// sketch_freq_directions_vs_topnorm_bench.nx -- paired bench, FD vs naive top-norm.
2//
3// CLAIM TO VALIDATE:
4// Frequent Directions reconstructs the true covariance matrix
5// A^T A more accurately than a naive "keep top-l rows by norm"
6// baseline at the same sketch size. Liberty's headline 2013
7// theorem: ||A^T A - B^T B||_F <= ||A - A_k||_F^2 / (l - k).
8// The naive baseline has no such guarantee -- it discards
9// correlation information.
10//
11// SHARED WORKLOAD:
12// - 50 random rows in d=4 dimensions, Q14 fixed-point in [0, 1)
13// - Both sketches at l = 3 rows
14// - Deterministic LCG generator seeded identically
15//
16// MEASUREMENT:
17// true: G_true = A^T A (4x4 Gram matrix)
18// FD est: G_fd = B_fd^T B_fd (4x4)
19// naive est: G_naive = B_naive^T B_naive (where B_naive = top 3
20// rows of A by L2 norm)
21//
22// Scalar error metric (Frobenius):
23// fd_err = sum_{i,j} (G_true[i,j] - G_fd[i,j])^2
24// naive_err = sum_{i,j} (G_true[i,j] - G_naive[i,j])^2
25// Smaller wins.
26//
27// Reuses nx_cmp_memory(our, theirs, tol) as the "scalar smaller-wins"
28// comparator (the function does NOT care that the inputs are
29// covariance-error rather than literal bytes; smaller-wins is the
30// axis semantics).
31//
32// HARD-WIN GATE:
33// verdict == BEATS with delta_ppm > 10000 (1% improvement).
34
35import "syscalls.nx"
36import "sketch_freq_directions.nx"
37import "sketch_comparator.nx"
38import "sketch_types.nx"
39
40const NX_FDB_Q14: i64 = 16384
41const NX_FDB_D: i64 = 4
42const NX_FDB_L: i64 = 3
43const NX_FDB_N: i64 = 50
44
45const NX_FDB_LCG_A: i64 = 1103515245
46const NX_FDB_LCG_C: i64 = 12345
47const NX_FDB_LCG_MOD: i64 = 0x7FFFFFFF
48
49func nx_fdb_row_norm_sq(row: *i64, d: i64) -> i64 {
50 var s: i64 = 0
51 var c: i64 = 0
52 while c < d {
53 s = s + (row[c] * row[c]) / NX_FDB_Q14
54 c = c + 1
55 }
56 return s
57}
58
59func nx_fdb_outer_accumulate(G: *i64, row: *i64, d: i64) -> i64 {
60 var i: i64 = 0
61 while i < d {
62 var j: i64 = 0
63 while j < d {
64 G[i * d + j] = G[i * d + j] + (row[i] * row[j]) / NX_FDB_Q14
65 j = j + 1
66 }
67 i = i + 1
68 }
69 return 0
70}
71
72func nx_fdb_frob_sq_diff(A: *i64, B: *i64, n: i64) -> i64 {
73 var s: i64 = 0
74 var i: i64 = 0
75 while i < n {
76 let d: i64 = A[i] - B[i]
77 s = s + (d * d) / NX_FDB_Q14
78 i = i + 1
79 }
80 return s
81}
82
83func main() -> i64 {
84 let d: i64 = NX_FDB_D
85 let l: i64 = NX_FDB_L
86 let n: i64 = NX_FDB_N
87
88 let fd: *FreqDir = nx_fd_alloc(l, d)
89
90 // Naive baseline: store l rows + their squared norms.
91 let naive_rows_raw: *u8 = sys_mmap(l * d * 8)
92 let naive_rows: *i64 = naive_rows_raw as *i64
93 let naive_norms_raw: *u8 = sys_mmap(l * 8)
94 let naive_norms: *i64 = naive_norms_raw as *i64
95 var z: i64 = 0
96 while z < l * d {
97 naive_rows[z] = 0
98 z = z + 1
99 }
100 z = 0
101 while z < l {
102 naive_norms[z] = 0
103 z = z + 1
104 }
105
106 // True covariance accumulator G_true (d x d).
107 let g_true_raw: *u8 = sys_mmap(d * d * 8)
108 let G_true: *i64 = g_true_raw as *i64
109 z = 0
110 while z < d * d {
111 G_true[z] = 0
112 z = z + 1
113 }
114
115 // Input row buffer.
116 let row_raw: *u8 = sys_mmap(d * 8)
117 let row: *i64 = row_raw as *i64
118
119 // ---- Stream ----
120 var sim_state: i64 = 42
121 var step: i64 = 0
122 while step < n {
123 // Generate row (uniform-ish in [0, Q14)).
124 var c: i64 = 0
125 while c < d {
126 sim_state = ((sim_state * NX_FDB_LCG_A) + NX_FDB_LCG_C) & NX_FDB_LCG_MOD
127 row[c] = sim_state & (NX_FDB_Q14 - 1)
128 c = c + 1
129 }
130 // Accumulate G_true.
131 nx_fdb_outer_accumulate(G_true, row, d)
132 // FD update.
133 nx_fd_add_row(fd, row, d)
134 // Naive update: replace smallest-norm row if new is larger.
135 let nrm: i64 = nx_fdb_row_norm_sq(row, d)
136 var min_idx: i64 = 0
137 var min_n: i64 = naive_norms[0]
138 var k: i64 = 1
139 while k < l {
140 if naive_norms[k] < min_n {
141 min_n = naive_norms[k]
142 min_idx = k
143 }
144 k = k + 1
145 }
146 if nrm > min_n {
147 c = 0
148 while c < d {
149 naive_rows[min_idx * d + c] = row[c]
150 c = c + 1
151 }
152 naive_norms[min_idx] = nrm
153 }
154 step = step + 1
155 }
156
157 // ---- Reconstruct G_fd = B_fd^T B_fd ----
158 let g_fd_raw: *u8 = sys_mmap(d * d * 8)
159 let G_fd: *i64 = g_fd_raw as *i64
160 z = 0
161 while z < d * d {
162 G_fd[z] = 0
163 z = z + 1
164 }
165 var r: i64 = 0
166 while r < l {
167 // Build a row buffer from B_fd[r,:].
168 var c: i64 = 0
169 while c < d {
170 row[c] = nx_fd_b_get(fd, r, c)
171 c = c + 1
172 }
173 nx_fdb_outer_accumulate(G_fd, row, d)
174 r = r + 1
175 }
176
177 // ---- Reconstruct G_naive ----
178 let g_naive_raw: *u8 = sys_mmap(d * d * 8)
179 let G_naive: *i64 = g_naive_raw as *i64
180 z = 0
181 while z < d * d {
182 G_naive[z] = 0
183 z = z + 1
184 }
185 r = 0
186 while r < l {
187 var c: i64 = 0
188 while c < d {
189 row[c] = naive_rows[r * d + c]
190 c = c + 1
191 }
192 nx_fdb_outer_accumulate(G_naive, row, d)
193 r = r + 1
194 }
195
196 // ---- Compute Frobenius errors ----
197 let fd_err: i64 = nx_fdb_frob_sq_diff(G_true, G_fd, d * d)
198 let naive_err: i64 = nx_fdb_frob_sq_diff(G_true, G_naive, d * d)
199
200 // ---- Sanity: both errors positive ----
201 if fd_err <= 0 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
202 if naive_err <= 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
203
204 // ---- "Smaller scalar wins" via memory comparator ----
205 // delta_ppm = (naive_err - fd_err) * 1e6 / naive_err
206 // positive = fd has smaller error = FD wins
207 let err_cmp: *ComparisonResult = nx_cmp_memory(fd_err, naive_err, 10000)
208
209 // ---- HARD-WIN GATE ----
210 if err_cmp.verdict != NX_CMP_VERDICT_BEATS {
211 return __syscall(93, 10, 0, 0, 0, 0, 0)
212 }
213 if err_cmp.delta_ppm < 10000 {
214 return __syscall(93, 11, 0, 0, 0, 0, 0)
215 }
216
217 // ---- Sanity: FD sketch must have non-trivial total_rows count ----
218 if nx_fd_total_rows(fd) != n {
219 return __syscall(93, 20, 0, 0, 0, 0, 0)
220 }
221
222 return 0
223}