sketch_histogram.nx source
↩ module page · 211 lines · 7393 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
31import "syscalls.nx"
32import "sketch_types.nx"
33
34const NX_HIST_BUCKETS_MIN: i64 = 2
35const NX_HIST_BUCKETS_MAX: i64 = 100000
36
37struct Histogram {
38 buckets: *i64, // n_buckets entries
39 n_buckets: i64,
40 min_val: i64,
41 max_val: i64, // exclusive upper bound
42 range: i64, // max_val - min_val
43 under_count: i64, // count of values < min_val
44 over_count: i64, // count of values >= max_val
45 total: i64, // sum of all counts (in-range + over + under)
46}
47
48// === construction =================================================
49
50func nx_hist_alloc(min_val: i64, max_val: i64, n_buckets: i64) -> *Histogram {
51 if n_buckets < NX_HIST_BUCKETS_MIN { return 0 as *Histogram }
52 if n_buckets > NX_HIST_BUCKETS_MAX { return 0 as *Histogram }
53 if max_val <= min_val { return 0 as *Histogram }
54 let raw: *u8 = sys_mmap(80)
55 let h: *Histogram = raw as *Histogram
56 let bytes: i64 = n_buckets * 8
57 let buckets_raw: *u8 = sys_mmap(bytes)
58 h.buckets = buckets_raw as *i64
59 var i: i64 = 0
60 while i < n_buckets {
61 h.buckets[i] = 0
62 i = i + 1
63 }
64 h.n_buckets = n_buckets
65 h.min_val = min_val
66 h.max_val = max_val
67 h.range = max_val - min_val
68 h.under_count = 0
69 h.over_count = 0
70 h.total = 0
71 return h
72}
73
74// === bucket index =================================================
75//
76// idx = (value - min) * n_buckets / range
77// Bounded by [0, n_buckets - 1] for in-range values.
78
79func nx_hist_bucket(h: *Histogram, value: i64) -> i64 {
80 let offset: i64 = value - h.min_val
81 let idx: i64 = (offset * h.n_buckets) / h.range
82 return idx
83}
84
85// === add ==========================================================
86
87func nx_hist_add(h: *Histogram, value: i64) -> i64 {
88 h.total = h.total + 1
89 if value < h.min_val {
90 h.under_count = h.under_count + 1
91 return 0
92 }
93 if value >= h.max_val {
94 h.over_count = h.over_count + 1
95 return 0
96 }
97 let idx: i64 = nx_hist_bucket(h, value)
98 h.buckets[idx] = h.buckets[idx] + 1
99 return 0
100}
101
102func nx_hist_add_n(h: *Histogram, value: i64, count: i64) -> i64 {
103 if count <= 0 { return 0 }
104 h.total = h.total + count
105 if value < h.min_val {
106 h.under_count = h.under_count + count
107 return 0
108 }
109 if value >= h.max_val {
110 h.over_count = h.over_count + count
111 return 0
112 }
113 let idx: i64 = nx_hist_bucket(h, value)
114 h.buckets[idx] = h.buckets[idx] + count
115 return 0
116}
117
118// === queries ======================================================
119
120func nx_hist_count_at(h: *Histogram, idx: i64) -> i64 {
121 if idx < 0 { return 0 }
122 if idx >= h.n_buckets { return 0 }
123 return h.buckets[idx]
124}
125
126// Count of values in bucket containing `value`. Returns 0 for OOR.
127func nx_hist_count_for_value(h: *Histogram, value: i64) -> i64 {
128 if value < h.min_val { return 0 }
129 if value >= h.max_val { return 0 }
130 return h.buckets[nx_hist_bucket(h, value)]
131}
132
133// p_milli in [0, 1000]. Walk cumulative counts (under -> buckets ->
134// over) to find the quantile. Returns the bucket-midpoint value.
135func nx_hist_quantile(h: *Histogram, p_milli: i64) -> i64 {
136 if h.total == 0 { return 0 }
137 let target: i64 = (p_milli * h.total) / 1000
138 var cum: i64 = h.under_count
139 if cum >= target { return h.min_val }
140 var i: i64 = 0
141 while i < h.n_buckets {
142 cum = cum + h.buckets[i]
143 if cum >= target {
144 // Return midpoint of this bucket.
145 let bucket_lo: i64 = h.min_val + (i * h.range) / h.n_buckets
146 let bucket_hi: i64 = h.min_val + ((i + 1) * h.range) / h.n_buckets
147 return (bucket_lo + bucket_hi) / 2
148 }
149 i = i + 1
150 }
151 return h.max_val
152}
153
154// === typed queries ================================================
155
156func nx_hist_query_count_for_value(h: *Histogram, value: i64) -> *ApproxI64 {
157 let c: i64 = nx_hist_count_for_value(h, value)
158 return nx_approx_new(c, NX_ENV_ABS, 0, 1000000000,
159 NX_MATURITY_PRODUCTION,
160 NX_ADV_HONEST)
161}
162
163// Quantile envelope: rank error = bucket resolution in ppb-of-range.
164// For n_buckets=100, resolution = 1% = 10_000_000 ppb.
165func nx_hist_quantile_resolution_ppb(h: *Histogram) -> i64 {
166 return 1000000000 / h.n_buckets
167}
168
169func nx_hist_query_quantile(h: *Histogram, p_milli: i64) -> *ApproxI64 {
170 let v: i64 = nx_hist_quantile(h, p_milli)
171 return nx_approx_new(v, NX_ENV_RANK_ERROR,
172 nx_hist_quantile_resolution_ppb(h),
173 1000000000, // deterministic
174 NX_MATURITY_PRODUCTION,
175 NX_ADV_HONEST)
176}
177
178// === merge ========================================================
179//
180// Element-wise count addition across matched ranges. Refused if
181// ranges don't match.
182
183func nx_hist_merge(a: *Histogram, b: *Histogram) -> *Histogram {
184 if a.n_buckets != b.n_buckets { return 0 as *Histogram }
185 if a.min_val != b.min_val { return 0 as *Histogram }
186 if a.max_val != b.max_val { return 0 as *Histogram }
187 let out: *Histogram = nx_hist_alloc(a.min_val, a.max_val, a.n_buckets)
188 var i: i64 = 0
189 while i < a.n_buckets {
190 out.buckets[i] = a.buckets[i] + b.buckets[i]
191 i = i + 1
192 }
193 out.under_count = a.under_count + b.under_count
194 out.over_count = a.over_count + b.over_count
195 out.total = a.total + b.total
196 return out
197}
198
199// === introspection ================================================
200
201func nx_hist_total(h: *Histogram) -> i64 {
202 return h.total
203}
204
205func nx_hist_in_range(h: *Histogram) -> i64 {
206 return h.total - h.under_count - h.over_count
207}
208
209func nx_hist_memory_bytes(h: *Histogram) -> i64 {
210 return 80 + h.n_buckets * 8
211}