sketch_varopt_vs_reservoir_biased_bench.nx source
↩ module page · 111 lines · 3694 B
1// sketch_varopt_vs_reservoir_biased_bench.nx -- weighted sampling capability.
2//
3// CLAIM TO VALIDATE:
4// VarOpt sketch (Efraimidis-Spirakis A-ExpJ, Cohen et al. weighted-
5// sampling) selects items with probability proportional to weight.
6// Uniform Reservoir (Vitter 1985) samples uniformly regardless of
7// weight. On a stream with one heavy-weighted item among many
8// light-weighted items, VarOpt consistently retains the heavy item;
9// Reservoir nearly always loses it.
10//
11// CAPABILITY EXCEED: weighted streaming sampling. DS ships Vitter
12// reservoir but NOT VarOpt/A-ExpJ. Substrate offers both.
13//
14// WORKLOAD:
15// - 1 HEAVY item (id=99999) with weight 1000
16// - 50 medium items (ids 100..149) with weight 100
17// - 5000 noise items (ids 1000..5999) with weight 1
18// - Total: 5051 items, 11000 total weight
19//
20// Run with 10 different seeds. Tally how often the heavy item
21// appears in each sketch's sample. VarOpt should retain >=9/10.
22// Reservoir should retain <=4/10.
23//
24// MEMORY:
25// VarOpt k=100, entries 24 bytes each -> 2400 + header
26// Reservoir cap=300, 8 bytes each -> 2400 + header
27// Matched ~2400 bytes by construction.
28
29import "syscalls.nx"
30import "sketch_varopt.nx"
31import "sketch_reservoir.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35const NX_VOB_HEAVY_ID: i64 = 99999
36
37func main() -> i64 {
38 let varopt_k: i64 = 100
39 let res_cap: i64 = 300 // matched-memory: 300 × 8 = 2400 ≈ 100 × 24
40
41 var seed: i64 = 1
42 var varopt_hits: i64 = 0
43 var res_hits: i64 = 0
44
45 while seed <= 10 {
46 let vo: *VarOpt = nx_varopt_alloc(varopt_k, seed)
47 let rs: *Reservoir = nx_reservoir_alloc(res_cap, seed)
48 if vo == (0 as *VarOpt) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
49 if rs == (0 as *Reservoir) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
50
51 // ---- Stream ----
52 // Heavy item
53 nx_varopt_add(vo, NX_VOB_HEAVY_ID, 1000)
54 nx_reservoir_add(rs, NX_VOB_HEAVY_ID)
55 // Medium items
56 var m: i64 = 0
57 while m < 50 {
58 nx_varopt_add(vo, 100 + m, 100)
59 nx_reservoir_add(rs, 100 + m)
60 m = m + 1
61 }
62 // Noise
63 var i: i64 = 0
64 while i < 5000 {
65 nx_varopt_add(vo, 1000 + i, 1)
66 nx_reservoir_add(rs, 1000 + i)
67 i = i + 1
68 }
69
70 // ---- Check: is heavy item in VarOpt sample? ----
71 var vo_found: i64 = 0
72 let vo_n: i64 = nx_varopt_n_items(vo)
73 var k: i64 = 0
74 while k < vo_n {
75 let e: *VoptEntry = nx_varopt_entry_at(vo, k)
76 if e.item == NX_VOB_HEAVY_ID { vo_found = 1 }
77 k = k + 1
78 }
79 if vo_found == 1 { varopt_hits = varopt_hits + 1 }
80
81 // ---- Check: is heavy item in Reservoir sample? ----
82 var rs_found: i64 = 0
83 k = 0
84 while k < rs.n_items {
85 if rs.items[k] == NX_VOB_HEAVY_ID { rs_found = 1 }
86 k = k + 1
87 }
88 if rs_found == 1 { res_hits = res_hits + 1 }
89
90 seed = seed + 1
91 }
92
93 // ---- HARD-WIN GATE ----
94 // VarOpt should retain the heavy item in nearly every run.
95 if varopt_hits < 9 {
96 return __syscall(93, 10, 0, 0, 0, 0, 0)
97 }
98 // Reservoir's expected rate: cap=300 / 5051 = ~6% -> 0-1 out of 10
99 // Allow up to 4/10 for variance.
100 if res_hits > 4 {
101 return __syscall(93, 20, 0, 0, 0, 0, 0)
102 }
103
104 // ---- VarOpt edge in capability ----
105 let acc: *ComparisonResult = nx_cmp_accuracy(varopt_hits, res_hits, 10, 100000)
106 if acc.verdict != NX_CMP_VERDICT_BEATS {
107 return __syscall(93, 30, 0, 0, 0, 0, 0)
108 }
109
110 return 0
111}