nx_sketch_sliding_window.nx source
↩ module page · 187 lines · 5310 B
1// sketch_sliding_window.nx -- last-W-samples rolling aggregator.
2//
3// Circular buffer of size W with running sum + lazy min/max tracking.
4// Useful for "last 5 minutes / last 100 events" rolling computations
5// when the EXACT window is required (vs EWMA's exponential decay).
6//
7// AGGREGATES MAINTAINED:
8// sum -- running sum (O(1) update)
9// count -- min(window_size, observations) — useful at warm-up
10// min -- minimum (lazy: recompute via full scan when displaced)
11// max -- maximum (lazy: same)
12//
13// USE CASES:
14// - SRE: last-5-minute p99 latency window
15// - finance: 20-period moving average
16// - sensor: rolling-window anomaly thresholds
17// - rate-limiting: requests per fixed window
18//
19// MIN/MAX LAZY STRATEGY: cheaper than monotonic-deque for typical W.
20// Cached min/max valid until the displaced sample equaled the cached
21// value; then we rescan the buffer. Worst-case O(W) on eviction, O(1)
22// amortized for "no extremum eviction." For deterministic O(1)-per-op
23// monotonic-deque variant, swap in v2.
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
29// verdict: NOT_YET_EVALUATED
30
31import "nx_syscalls.nx"
32import "nx_sketch_types.nx"
33
34const NX_SW_MIN_W: i64 = 2
35const NX_SW_MAX_W: i64 = 1000000
36
37struct SlidingWindow {
38 buffer: *i64, // circular ring of W slots
39 window: i64, // capacity W
40 count: i64, // # samples (capped at W)
41 head: i64, // next write position
42 sum: i64,
43 cached_min: i64,
44 cached_max: i64,
45 cache_valid: i64, // 1 if cached_min/cached_max valid
46}
47
48// === construction =================================================
49
50func nx_sw_alloc(window: i64) -> *SlidingWindow {
51 if window < NX_SW_MIN_W { return 0 as *SlidingWindow }
52 if window > NX_SW_MAX_W { return 0 as *SlidingWindow }
53 let raw: *u8 = sys_mmap(72)
54 let s: *SlidingWindow = raw as *SlidingWindow
55 s.buffer = sys_mmap(window * 8) as *i64
56 var i: i64 = 0
57 while i < window {
58 s.buffer[i] = 0
59 i = i + 1
60 }
61 s.window = window
62 s.count = 0
63 s.head = 0
64 s.sum = 0
65 s.cached_min = 0
66 s.cached_max = 0
67 s.cache_valid = 0
68 return s
69}
70
71// === recompute min/max via full scan ============================
72
73func nx_sw_recompute_extrema(s: *SlidingWindow) -> i64 {
74 if s.count == 0 {
75 s.cached_min = 0
76 s.cached_max = 0
77 s.cache_valid = 0
78 return 0
79 }
80 var mn: i64 = s.buffer[0]
81 var mx: i64 = s.buffer[0]
82 var i: i64 = 1
83 while i < s.count {
84 let v: i64 = s.buffer[i]
85 if v < mn { mn = v }
86 if v > mx { mx = v }
87 i = i + 1
88 }
89 s.cached_min = mn
90 s.cached_max = mx
91 s.cache_valid = 1
92 return 0
93}
94
95// === push ==========================================================
96
97func nx_sw_push(s: *SlidingWindow, value: i64) -> i64 {
98 var evicted: i64 = 0
99 var has_evicted: i64 = 0
100 if s.count >= s.window {
101 evicted = s.buffer[s.head]
102 has_evicted = 1
103 s.sum = s.sum - evicted
104 }
105 if s.count < s.window {
106 s.count = s.count + 1
107 }
108 s.buffer[s.head] = value
109 s.sum = s.sum + value
110 s.head = (s.head + 1) % s.window
111
112 // Invalidate cached extrema only if the evicted value was an extremum.
113 if has_evicted == 1 {
114 if s.cache_valid == 1 {
115 if evicted == s.cached_min { s.cache_valid = 0 }
116 if evicted == s.cached_max { s.cache_valid = 0 }
117 }
118 }
119 // Track new value against cache (cheap).
120 if s.cache_valid == 1 {
121 if value < s.cached_min { s.cached_min = value }
122 if value > s.cached_max { s.cached_max = value }
123 }
124 return 0
125}
126
127// === queries =====================================================
128
129func nx_sw_sum(s: *SlidingWindow) -> i64 {
130 return s.sum
131}
132
133func nx_sw_mean(s: *SlidingWindow) -> i64 {
134 if s.count == 0 { return 0 }
135 return s.sum / s.count
136}
137
138func nx_sw_count(s: *SlidingWindow) -> i64 {
139 return s.count
140}
141
142func nx_sw_min(s: *SlidingWindow) -> i64 {
143 if s.count == 0 { return 0 }
144 if s.cache_valid == 0 {
145 nx_sw_recompute_extrema(s)
146 }
147 return s.cached_min
148}
149
150func nx_sw_max(s: *SlidingWindow) -> i64 {
151 if s.count == 0 { return 0 }
152 if s.cache_valid == 0 {
153 nx_sw_recompute_extrema(s)
154 }
155 return s.cached_max
156}
157
158func nx_sw_range(s: *SlidingWindow) -> i64 {
159 return nx_sw_max(s) - nx_sw_min(s)
160}
161
162// === typed envelope ==============================================
163//
164// All aggregates are EXACT integer computations. Production tier.
165
166func nx_sw_query_mean(s: *SlidingWindow) -> *ApproxI64 {
167 let m: i64 = nx_sw_mean(s)
168 return nx_approx_new(m, NX_ENV_ABS, 0, 1000000000,
169 NX_MATURITY_PRODUCTION,
170 NX_ADV_HONEST)
171}
172
173// === introspection ================================================
174
175func nx_sw_memory_bytes(s: *SlidingWindow) -> i64 {
176 return 72 + s.window * 8
177}
178
179func nx_sw_clear(s: *SlidingWindow) -> i64 {
180 s.count = 0
181 s.head = 0
182 s.sum = 0
183 s.cached_min = 0
184 s.cached_max = 0
185 s.cache_valid = 0
186 return 0
187}