nx_sketch_histogram.nx source
↩ module page · 217 lines · 7439 B
1// sketch_histogram.nx -- fixed-bin histogram with quantile + merge.
2//
3// Linear-bin histogram over a CALLER-DECLARED range [min, max). Each
4// of N buckets holds an exact count. Out-of-range values land in
5// under_count or over_count.
6//
7// COMPLEMENTS the quantile sketches:
8// - sketch_kll: provable uniform rank-error; small footprint
9// - sketch_tdigest: tail-tight; small footprint
10// - sketch_histogram: EXACT bucket counts within declared range;
11// memory = N * 8 bytes (no compression)
12// Caller picks: histogram for known bounded ranges with audit-grade
13// counts, sketches for unbounded streams with bounded error.
14//
15// USE CASES:
16// - HTTP status code distribution (range [200, 600), 1 bucket per code)
17// - Latency distribution with known SLA (range [0, 1000ms))
18// - Score distribution (range [0, 100))
19//
20// MERGE: count-wise addition across matched ranges. Refused if ranges
21// differ.
22//
23// LOSSLESS-LANGUAGE DISCIPLINE:
24// nx_hist_query_count(value): NX_ENV_ABS with param_a = 0 if in-range,
25// meaning exact count. For out-of-range we report the under/over
26// counts honestly.
27// nx_hist_query_quantile(p): NX_ENV_RANK_ERROR with param_a = bucket
28// resolution = (max - min) / N expressed in ppb relative to range.
29// MaturityClass = Production (exact within budget).
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38import "nx_sketch_types.nx"
39
40const NX_HIST_BUCKETS_MIN: i64 = 2
41const NX_HIST_BUCKETS_MAX: i64 = 100000
42
43struct Histogram {
44 buckets: *i64, // n_buckets entries
45 n_buckets: i64,
46 min_val: i64,
47 max_val: i64, // exclusive upper bound
48 range: i64, // max_val - min_val
49 under_count: i64, // count of values < min_val
50 over_count: i64, // count of values >= max_val
51 total: i64, // sum of all counts (in-range + over + under)
52}
53
54// === construction =================================================
55
56func nx_hist_alloc(min_val: i64, max_val: i64, n_buckets: i64) -> *Histogram {
57 if n_buckets < NX_HIST_BUCKETS_MIN { return 0 as *Histogram }
58 if n_buckets > NX_HIST_BUCKETS_MAX { return 0 as *Histogram }
59 if max_val <= min_val { return 0 as *Histogram }
60 let raw: *u8 = sys_mmap(80)
61 let h: *Histogram = raw as *Histogram
62 let bytes: i64 = n_buckets * 8
63 let buckets_raw: *u8 = sys_mmap(bytes)
64 h.buckets = buckets_raw as *i64
65 var i: i64 = 0
66 while i < n_buckets {
67 h.buckets[i] = 0
68 i = i + 1
69 }
70 h.n_buckets = n_buckets
71 h.min_val = min_val
72 h.max_val = max_val
73 h.range = max_val - min_val
74 h.under_count = 0
75 h.over_count = 0
76 h.total = 0
77 return h
78}
79
80// === bucket index =================================================
81//
82// idx = (value - min) * n_buckets / range
83// Bounded by [0, n_buckets - 1] for in-range values.
84
85func nx_hist_bucket(h: *Histogram, value: i64) -> i64 {
86 let offset: i64 = value - h.min_val
87 let idx: i64 = (offset * h.n_buckets) / h.range
88 return idx
89}
90
91// === add ==========================================================
92
93func nx_hist_add(h: *Histogram, value: i64) -> i64 {
94 h.total = h.total + 1
95 if value < h.min_val {
96 h.under_count = h.under_count + 1
97 return 0
98 }
99 if value >= h.max_val {
100 h.over_count = h.over_count + 1
101 return 0
102 }
103 let idx: i64 = nx_hist_bucket(h, value)
104 h.buckets[idx] = h.buckets[idx] + 1
105 return 0
106}
107
108func nx_hist_add_n(h: *Histogram, value: i64, count: i64) -> i64 {
109 if count <= 0 { return 0 }
110 h.total = h.total + count
111 if value < h.min_val {
112 h.under_count = h.under_count + count
113 return 0
114 }
115 if value >= h.max_val {
116 h.over_count = h.over_count + count
117 return 0
118 }
119 let idx: i64 = nx_hist_bucket(h, value)
120 h.buckets[idx] = h.buckets[idx] + count
121 return 0
122}
123
124// === queries ======================================================
125
126func nx_hist_count_at(h: *Histogram, idx: i64) -> i64 {
127 if idx < 0 { return 0 }
128 if idx >= h.n_buckets { return 0 }
129 return h.buckets[idx]
130}
131
132// Count of values in bucket containing `value`. Returns 0 for OOR.
133func nx_hist_count_for_value(h: *Histogram, value: i64) -> i64 {
134 if value < h.min_val { return 0 }
135 if value >= h.max_val { return 0 }
136 return h.buckets[nx_hist_bucket(h, value)]
137}
138
139// p_milli in [0, 1000]. Walk cumulative counts (under -> buckets ->
140// over) to find the quantile. Returns the bucket-midpoint value.
141func nx_hist_quantile(h: *Histogram, p_milli: i64) -> i64 {
142 if h.total == 0 { return 0 }
143 let target: i64 = (p_milli * h.total) / 1000
144 var cum: i64 = h.under_count
145 if cum >= target { return h.min_val }
146 var i: i64 = 0
147 while i < h.n_buckets {
148 cum = cum + h.buckets[i]
149 if cum >= target {
150 // Return midpoint of this bucket.
151 let bucket_lo: i64 = h.min_val + (i * h.range) / h.n_buckets
152 let bucket_hi: i64 = h.min_val + ((i + 1) * h.range) / h.n_buckets
153 return (bucket_lo + bucket_hi) / 2
154 }
155 i = i + 1
156 }
157 return h.max_val
158}
159
160// === typed queries ================================================
161
162func nx_hist_query_count_for_value(h: *Histogram, value: i64) -> *ApproxI64 {
163 let c: i64 = nx_hist_count_for_value(h, value)
164 return nx_approx_new(c, NX_ENV_ABS, 0, 1000000000,
165 NX_MATURITY_PRODUCTION,
166 NX_ADV_HONEST)
167}
168
169// Quantile envelope: rank error = bucket resolution in ppb-of-range.
170// For n_buckets=100, resolution = 1% = 10_000_000 ppb.
171func nx_hist_quantile_resolution_ppb(h: *Histogram) -> i64 {
172 return 1000000000 / h.n_buckets
173}
174
175func nx_hist_query_quantile(h: *Histogram, p_milli: i64) -> *ApproxI64 {
176 let v: i64 = nx_hist_quantile(h, p_milli)
177 return nx_approx_new(v, NX_ENV_RANK_ERROR,
178 nx_hist_quantile_resolution_ppb(h),
179 1000000000, // deterministic
180 NX_MATURITY_PRODUCTION,
181 NX_ADV_HONEST)
182}
183
184// === merge ========================================================
185//
186// Element-wise count addition across matched ranges. Refused if
187// ranges don't match.
188
189func nx_hist_merge(a: *Histogram, b: *Histogram) -> *Histogram {
190 if a.n_buckets != b.n_buckets { return 0 as *Histogram }
191 if a.min_val != b.min_val { return 0 as *Histogram }
192 if a.max_val != b.max_val { return 0 as *Histogram }
193 let out: *Histogram = nx_hist_alloc(a.min_val, a.max_val, a.n_buckets)
194 var i: i64 = 0
195 while i < a.n_buckets {
196 out.buckets[i] = a.buckets[i] + b.buckets[i]
197 i = i + 1
198 }
199 out.under_count = a.under_count + b.under_count
200 out.over_count = a.over_count + b.over_count
201 out.total = a.total + b.total
202 return out
203}
204
205// === introspection ================================================
206
207func nx_hist_total(h: *Histogram) -> i64 {
208 return h.total
209}
210
211func nx_hist_in_range(h: *Histogram) -> i64 {
212 return h.total - h.under_count - h.over_count
213}
214
215func nx_hist_memory_bytes(h: *Histogram) -> i64 {
216 return 80 + h.n_buckets * 8
217}