nx_sketch_ddsketch.nx source
↩ module page · 208 lines · 6513 B
1// sketch_ddsketch.nx -- DDSketch (Masson et al, PVLDB 2019).
2//
3// Multiplicative-error quantile sketch. Different error model than
4// KLL (additive rank) and T-Digest (scale-function tail-tight):
5//
6// For query rank q, returned value v satisfies:
7// true_value(q) ∈ [v · (1-α), v · (1+α)]
8//
9// I.e., the returned VALUE is within α-relative-error of the true.
10// Perfect for log-distributed metrics (latency, sizes, durations).
11//
12// CAPABILITY: heavy-tail observability. Latency p99=100ms vs p99=1000ms
13// both reported with ±1% multiplicative error, regardless of magnitude.
14//
15// ALGORITHM:
16// bucket(x) = ⌈log_γ(x)⌉ where γ = (1+α)/(1-α)
17// For our integer implementation:
18// octave = bitlen(x) - 1 (floor log2)
19// mantissa = x - (1 << octave)
20// sub_bucket = mantissa * BPO / (1 << octave)
21// bucket_index = octave * BPO + sub_bucket
22//
23// BPO = buckets-per-octave; relative error ≈ 1/BPO.
24// BPO=64 -> ~1.5% multiplicative error
25// BPO=128 -> ~0.8%
26//
27// MEMORY: 64 * BPO * 8 bytes (~32KB for BPO=64, 64KB for BPO=128).
28// MERGE: count-wise addition; matching BPO required.
29//
30// LOSSLESS-LANGUAGE DISCIPLINE:
31// nx_dd_query_quantile returns NX_ENV_REL_STDDEV with param_a = 1/BPO
32// in PPB. Conf = 1e9 (deterministic). MaturityClass = ReferenceImpl.
33
34// nx_safety_envelope:
35// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
36// sil_target: SIL1
37// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
38// verdict: NOT_YET_EVALUATED
39
40import "nx_syscalls.nx"
41import "nx_sketch_types.nx"
42
43const NX_DD_BPO_MIN: i64 = 16
44const NX_DD_BPO_MAX: i64 = 1024
45const NX_DD_MAX_OCTAVE: i64 = 62 // covers x up to 2^62
46
47struct DDSketch {
48 buckets: *i64, // size = (MAX_OCTAVE+1) * BPO
49 bpo: i64,
50 total: i64,
51 zero_count: i64, // x == 0 lands here
52 neg_count: i64, // x < 0 lands here (raw count; no neg buckets v1)
53}
54
55// === construction =================================================
56
57func nx_dd_alloc(bpo: i64) -> *DDSketch {
58 if bpo < NX_DD_BPO_MIN { return 0 as *DDSketch }
59 if bpo > NX_DD_BPO_MAX { return 0 as *DDSketch }
60 let raw: *u8 = sys_mmap(48)
61 let d: *DDSketch = raw as *DDSketch
62 let n_buckets: i64 = (NX_DD_MAX_OCTAVE + 1) * bpo
63 let buckets_raw: *u8 = sys_mmap(n_buckets * 8)
64 d.buckets = buckets_raw as *i64
65 var i: i64 = 0
66 while i < n_buckets {
67 d.buckets[i] = 0
68 i = i + 1
69 }
70 d.bpo = bpo
71 d.total = 0
72 d.zero_count = 0
73 d.neg_count = 0
74 return d
75}
76
77// === bit-length helper ============================================
78
79func nx_dd_bitlen(x: i64) -> i64 {
80 if x <= 0 { return 0 }
81 var n: i64 = 0
82 var t: i64 = x
83 while t > 0 {
84 t = t >> 1
85 n = n + 1
86 }
87 return n
88}
89
90// === bucket index =================================================
91//
92// For x > 0:
93// octave = bitlen(x) - 1
94// mantissa = x - (1 << octave)
95// sub_bucket = mantissa * bpo / (1 << octave)
96// bucket = octave * bpo + sub_bucket
97
98func nx_dd_bucket(d: *DDSketch, x: i64) -> i64 {
99 if x <= 0 { return 0 } // caller responsibility to not pass <= 0
100 let lg: i64 = nx_dd_bitlen(x)
101 let octave: i64 = lg - 1
102 if octave > NX_DD_MAX_OCTAVE { return (NX_DD_MAX_OCTAVE + 1) * d.bpo - 1 }
103 let base: i64 = 1 << octave
104 let mantissa: i64 = x - base
105 var sub: i64 = (mantissa * d.bpo) / base
106 if sub < 0 { sub = 0 }
107 if sub >= d.bpo { sub = d.bpo - 1 }
108 return octave * d.bpo + sub
109}
110
111// === inverse: bucket -> representative value ======================
112//
113// For bucket index b in octave o, sub s:
114// o = b / bpo; s = b % bpo
115// value = (1 << o) + s * (1 << o) / bpo
116// = (1 << o) * (bpo + s) / bpo
117
118func nx_dd_value_at_bucket(d: *DDSketch, b: i64) -> i64 {
119 let octave: i64 = b / d.bpo
120 let sub: i64 = b - octave * d.bpo
121 let base: i64 = 1 << octave
122 return (base * (d.bpo + sub)) / d.bpo
123}
124
125// === add ==========================================================
126
127func nx_dd_add(d: *DDSketch, x: i64) -> i64 {
128 d.total = d.total + 1
129 if x == 0 {
130 d.zero_count = d.zero_count + 1
131 return 0
132 }
133 if x < 0 {
134 d.neg_count = d.neg_count + 1
135 return 0
136 }
137 let b: i64 = nx_dd_bucket(d, x)
138 d.buckets[b] = d.buckets[b] + 1
139 return 0
140}
141
142// === quantile =====================================================
143//
144// Walk buckets accumulating count; return value-at-bucket for the
145// bucket containing the p·total rank.
146
147func nx_dd_quantile(d: *DDSketch, p_milli: i64) -> i64 {
148 if d.total == 0 { return 0 }
149 let target: i64 = (p_milli * d.total) / 1000
150 var cum: i64 = d.neg_count + d.zero_count
151 if cum >= target {
152 if target <= d.neg_count { return -1 } // negative quantile sentinel
153 return 0
154 }
155 let n_buckets: i64 = (NX_DD_MAX_OCTAVE + 1) * d.bpo
156 var i: i64 = 0
157 while i < n_buckets {
158 let c: i64 = d.buckets[i]
159 if c > 0 {
160 cum = cum + c
161 if cum >= target {
162 return nx_dd_value_at_bucket(d, i)
163 }
164 }
165 i = i + 1
166 }
167 return 0
168}
169
170// === typed envelope ===============================================
171//
172// Relative error = 1/BPO. For BPO=64: 1.56% = 15_600_000 ppb.
173
174func nx_dd_query_quantile(d: *DDSketch, p_milli: i64) -> *ApproxI64 {
175 let v: i64 = nx_dd_quantile(d, p_milli)
176 let err_ppb: i64 = 1000000000 / d.bpo
177 return nx_approx_new(v, NX_ENV_REL_STDDEV, err_ppb,
178 1000000000,
179 NX_MATURITY_REFERENCE_IMPL,
180 NX_ADV_HONEST)
181}
182
183// === merge ========================================================
184
185func nx_dd_merge(a: *DDSketch, b: *DDSketch) -> *DDSketch {
186 if a.bpo != b.bpo { return 0 as *DDSketch }
187 let out: *DDSketch = nx_dd_alloc(a.bpo)
188 let n_buckets: i64 = (NX_DD_MAX_OCTAVE + 1) * a.bpo
189 var i: i64 = 0
190 while i < n_buckets {
191 out.buckets[i] = a.buckets[i] + b.buckets[i]
192 i = i + 1
193 }
194 out.total = a.total + b.total
195 out.zero_count = a.zero_count + b.zero_count
196 out.neg_count = a.neg_count + b.neg_count
197 return out
198}
199
200// === introspection ================================================
201
202func nx_dd_memory_bytes(d: *DDSketch) -> i64 {
203 return 48 + (NX_DD_MAX_OCTAVE + 1) * d.bpo * 8
204}
205
206func nx_dd_total(d: *DDSketch) -> i64 {
207 return d.total
208}