nx_vecexec.nx source
↩ module page · 169 lines · 6767 B
1// nx_vecexec.nx -- VECTORIZED EXECUTION (vectorized-exec, F-vec). The DuckDB model, single-core: operators
2// consume/produce COLUMN VECTORS (batches of VX_VEC values) over the zero-copy nx_colframe, instead of a
3// tuple-at-a-time pipeline that pays operator-dispatch overhead per row. A filter emits a SELECTION VECTOR;
4// downstream operators gather over it. Batch loops are branch-lean and cache-resident (and the shape a
5// SIMD backend auto-vectorises). NOT threading -- this is the batch/columnar execution model, provably
6// single-core. Composes nx_colframe (reads columns as zero-copy views). license_tier: ORIGINAL No hw writes.
7import "nx_syscalls.nx"
8import "nx_colframe.nx"
9const VX_MAGIC_12345: i64 = 12345
10const VX_MAGIC_1103515245: i64 = 1103515245
11const VX_MAGIC_4000000: i64 = 4000000
12
13const VX_VEC: i64 = 1024 // vector (batch) width -- the granularity operators process
14const VX_OUT: i64 = 4096
15const VX_ZERO: i64 = 48
16
17// ---- vectorized operators over a colframe (all batch-structured) --------------------------------
18// vectorized SUM of a whole column
19func vx_sum(frame: *u8, ci: i64) -> i64 {
20 let n: i64 = cf_nrows(frame)
21 let col: *i64 = cf_col(frame, ci)
22 var acc: i64 = 0
23 var base: i64 = 0
24 while base < n {
25 var lim: i64 = base + VX_VEC
26 if lim > n { lim = n }
27 var r: i64 = base
28 while r < lim { acc = acc + col[r]; r = r + 1 }
29 base = lim
30 }
31 return acc
32}
33// vectorized FILTER col >= thr -> selection vector of row indices; returns nsel
34func vx_filter_ge(frame: *u8, ci: i64, thr: i64, sel: *i64) -> i64 {
35 let n: i64 = cf_nrows(frame)
36 let col: *i64 = cf_col(frame, ci)
37 var ns: i64 = 0
38 var base: i64 = 0
39 while base < n {
40 var lim: i64 = base + VX_VEC
41 if lim > n { lim = n }
42 var r: i64 = base
43 while r < lim { if col[r] >= thr { sel[ns] = r; ns = ns + 1 } r = r + 1 }
44 base = lim
45 }
46 return ns
47}
48// GATHER-sum a column over a selection vector (the downstream operator consuming the filter's output)
49func vx_sum_sel(frame: *u8, ci: i64, sel: *i64, nsel: i64) -> i64 {
50 let col: *i64 = cf_col(frame, ci)
51 var acc: i64 = 0
52 var i: i64 = 0
53 while i < nsel { acc = acc + col[sel[i]]; i = i + 1 }
54 return acc
55}
56// vectorized COUNT col >= thr (no materialised selection -- a pure batch scan)
57func vx_count_ge(frame: *u8, ci: i64, thr: i64) -> i64 {
58 let n: i64 = cf_nrows(frame)
59 let col: *i64 = cf_col(frame, ci)
60 var c: i64 = 0
61 var base: i64 = 0
62 while base < n {
63 var lim: i64 = base + VX_VEC
64 if lim > n { lim = n }
65 var r: i64 = base
66 while r < lim { if col[r] >= thr { c = c + 1 } r = r + 1 }
67 base = lim
68 }
69 return c
70}
71// THE COMPOSED VECTORIZED QUERY: SUM(sumcol) WHERE filtcol >= thr, filter->select->gather.
72func vx_sum_where_ge(frame: *u8, sumci: i64, filtci: i64, thr: i64, sel: *i64) -> i64 {
73 let ns: i64 = vx_filter_ge(frame, filtci, thr, sel)
74 return vx_sum_sel(frame, sumci, sel, ns)
75}
76
77// ---- scalar TUPLE-AT-A-TIME reference: a predicate call per row (the architecture we beat) --------
78func vx_pred_ge(v: i64, thr: i64) -> i64 { if v >= thr { return 1 } return 0 }
79func vx_scalar_sum_where_ge(frame: *u8, sumci: i64, filtci: i64, thr: i64) -> i64 {
80 let n: i64 = cf_nrows(frame)
81 let fcol: *i64 = cf_col(frame, filtci)
82 let scol: *i64 = cf_col(frame, sumci)
83 var acc: i64 = 0
84 var r: i64 = 0
85 while r < n { if vx_pred_ge(fcol[r], thr) == 1 { acc = acc + scol[r] } r = r + 1 }
86 return acc
87}
88
89// ---- bench: MEASURE scalar vs vectorized over a large frame, report real microseconds -------------
90func vx_raw(out: *u8, o: i64, s: *u8) -> i64 { var i: i64 = 0; while s[i] != (0 as u8) { out[o] = s[i]; o = o + 1; i = i + 1 } return o }
91func vx_num(out: *u8, o: i64, v: i64) -> i64 {
92 var oo: i64 = o
93 var m: i64 = v
94 if m < 0 { out[oo] = 45 as u8; oo = oo + 1; m = 0 - m }
95 let t: *u8 = sys_mmap(24)
96 var k: i64 = 0
97 if m == 0 { t[0] = VX_ZERO as u8; k = 1 }
98 while m > 0 { t[k] = (VX_ZERO + (m % 10)) as u8; m = m / 10; k = k + 1 }
99 var i: i64 = k - 1
100 while i >= 0 { out[oo] = t[i]; oo = oo + 1; i = i - 1 }
101 return oo
102}
103func vx_atoi(s: *u8) -> i64 { var v: i64 = 0; var i: i64 = 0; var go: i64 = 1; while go == 1 { let c: i64 = s[i] as i64; if c < 48 { go = 0 } else { if c > 57 { go = 0 } else { v = v * 10 + (c - 48); i = i + 1 } } } return v }
104
105func vx_bench(nrows: i64, out: *u8) -> i64 {
106 // build a 2-column frame (val, key) in a colframe
107 let val: *i64 = sys_mmap(8 * nrows) as *i64
108 let key: *i64 = sys_mmap(8 * nrows) as *i64
109 var s: i64 = VX_MAGIC_12345
110 var i: i64 = 0
111 while i < nrows {
112 s = (s * VX_MAGIC_1103515245 + VX_MAGIC_12345) & 0x7fffffff
113 key[i] = s % 200
114 val[i] = s % 1000
115 i = i + 1
116 }
117 let cols: *i64 = sys_mmap(8 * 2) as *i64
118 let names: *i64 = sys_mmap(8 * 2) as *i64
119 cols[0] = val as i64
120 cols[1] = key as i64
121 names[0] = "val" as *u8 as i64
122 names[1] = "key" as *u8 as i64
123 let tot: i64 = cf_encoded_bytes(names, 2, nrows)
124 let frame: *u8 = sys_mmap(tot + 64)
125 cf_encode(cols, names, 2, nrows, frame)
126 let sel: *i64 = sys_mmap(8 * nrows) as *i64
127
128 // scalar timing
129 let t0: i64 = sys_now_us()
130 let rs: i64 = vx_scalar_sum_where_ge(frame, 0, 1, 100)
131 let t1: i64 = sys_now_us()
132 // vectorized timing
133 let rv: i64 = vx_sum_where_ge(frame, 0, 1, 100, sel)
134 let t2: i64 = sys_now_us()
135
136 let us_s: i64 = t1 - t0
137 let us_v: i64 = t2 - t1
138 var ratio_milli: i64 = 0
139 if us_v > 0 { ratio_milli = us_s * 1000 / us_v }
140
141 var o: i64 = 0
142 o = vx_raw(out, o, "{\"tool\":\"nx_vecexec\",\"verb\":\"bench\",\"rows\":" as *u8)
143 o = vx_num(out, o, nrows)
144 o = vx_raw(out, o, ",\"query\":\"SUM(val) WHERE key>=100\",\"scalar_result\":" as *u8)
145 o = vx_num(out, o, rs)
146 o = vx_raw(out, o, ",\"vectorized_result\":" as *u8)
147 o = vx_num(out, o, rv)
148 o = vx_raw(out, o, ",\"results_agree\":" as *u8)
149 if rs == rv { o = vx_raw(out, o, "true" as *u8) } else { o = vx_raw(out, o, "false" as *u8) }
150 o = vx_raw(out, o, ",\"scalar_us\":" as *u8)
151 o = vx_num(out, o, us_s)
152 o = vx_raw(out, o, ",\"vectorized_us\":" as *u8)
153 o = vx_num(out, o, us_v)
154 o = vx_raw(out, o, ",\"speedup_x1000\":" as *u8)
155 o = vx_num(out, o, ratio_milli)
156 o = vx_raw(out, o, "}\n" as *u8)
157 out[o] = 0 as u8
158 return o
159}
160
161func main(argc: i64, argv: *i64) -> i64 {
162 let out: *u8 = sys_mmap(VX_OUT)
163 var nrows: i64 = VX_MAGIC_4000000
164 if argc >= 2 { nrows = vx_atoi(argv[1] as *u8) }
165 if nrows < 1 { nrows = VX_MAGIC_4000000 }
166 let n: i64 = vx_bench(nrows, out)
167 sys_write(1, out, n)
168 return 0
169}