1use xlog_core::{Result, ScalarType, XlogError};
24
25use super::fj_delta::FjDeltaCols;
26use super::{wcoj_kernels, CudaKernelProvider, WCOJ_MODULE};
27use crate::device_runtime::StreamId;
28use crate::launch::LaunchRecorder;
29use crate::CudaBuffer;
30use crate::{LaunchAsync, LaunchConfig};
31
32const BLOCK_SIZE: u32 = 256;
33
34fn require_binary_u32_class(buf: &CudaBuffer, name: &str, ctx: &str) -> Result<()> {
35 if buf.arity() != 2 {
36 return Err(XlogError::Kernel(format!(
37 "{ctx}: {name} must be arity-2, got {}",
38 buf.arity()
39 )));
40 }
41 for idx in 0..2 {
42 match buf.schema().column_type(idx) {
43 Some(ScalarType::U32) | Some(ScalarType::Symbol) => {}
44 other => {
45 return Err(XlogError::Kernel(format!(
46 "{ctx}: {name} column {idx} must be U32/Symbol, got {other:?}"
47 )));
48 }
49 }
50 }
51 Ok(())
52}
53
54impl CudaKernelProvider {
55 pub fn fj_delta_sparse_novel_u32_recorded(
67 &self,
68 delta: &CudaBuffer,
69 edge: &CudaBuffer,
70 full_r: &CudaBuffer,
71 cols: FjDeltaCols,
72 max_table_bytes: u64,
73 launch_stream: StreamId,
74 ) -> Result<Option<CudaBuffer>> {
75 let ctx = "fj_delta_sparse_novel_u32_recorded";
76 let runtime = self.memory().runtime().ok_or_else(|| {
77 XlogError::Kernel(format!(
78 "{ctx} requires a runtime-backed GpuMemoryManager (with_runtime)"
79 ))
80 })?;
81 let cu_stream = runtime
82 .stream_pool()
83 .resolve(launch_stream)
84 .ok_or_else(|| {
85 XlogError::Kernel(format!(
86 "{ctx}: launch_stream StreamId({}) does not resolve",
87 launch_stream.0
88 ))
89 })?;
90
91 require_binary_u32_class(delta, "delta", ctx)?;
92 require_binary_u32_class(edge, "edge", ctx)?;
93 require_binary_u32_class(full_r, "full_r", ctx)?;
94
95 let row_count = |buf: &CudaBuffer| -> Result<u32> {
96 match buf.cached_row_count() {
97 Some(c) => Ok(c),
98 None => self.dtoh_scalar_untracked::<u32>(buf.num_rows_device(), 0),
99 }
100 };
101 let n_delta = row_count(delta)?;
102 let n_edge = row_count(edge)?;
103 let n_r = row_count(full_r)?;
104
105 let out_schema = full_r.schema().clone();
106 if n_delta == 0 || n_edge == 0 {
107 return Ok(Some(self.create_empty_buffer(out_schema)?));
108 }
109
110 let delta_x = delta.column(cols.delta_carry).ok_or_else(|| {
111 XlogError::Kernel(format!("{ctx}: delta column {} missing", cols.delta_carry))
112 })?;
113 let delta_y = delta.column(cols.delta_key).ok_or_else(|| {
114 XlogError::Kernel(format!("{ctx}: delta column {} missing", cols.delta_key))
115 })?;
116 let edge_y = edge
117 .column(0)
118 .ok_or_else(|| XlogError::Kernel(format!("{ctx}: edge column 0 missing")))?;
119 let edge_z = edge
120 .column(1)
121 .ok_or_else(|| XlogError::Kernel(format!("{ctx}: edge column 1 missing")))?;
122 let r_x = full_r.column(cols.r_carry).ok_or_else(|| {
123 XlogError::Kernel(format!("{ctx}: full_r column {} missing", cols.r_carry))
124 })?;
125 let r_z = full_r.column(cols.r_value).ok_or_else(|| {
126 XlogError::Kernel(format!("{ctx}: full_r column {} missing", cols.r_value))
127 })?;
128 let delta_y_v = self.column_as_u32_view(delta_y, n_delta as usize)?;
129 let edge_y_v = self.column_as_u32_view(edge_y, n_edge as usize)?;
130
131 let range_lo = self.memory().alloc::<u32>(n_delta as usize)?;
134 let mut wp = self.memory().alloc::<u32>(n_delta as usize + 1)?;
135 {
136 let mut scan_scratch = self.multiblock_scan_u32_scratch_for_len(n_delta + 1)?;
137 let mut rec = LaunchRecorder::new_strict(launch_stream);
138 rec.read_column(delta_y);
139 rec.read_column(edge_y);
140 rec.write(&range_lo);
141 rec.write(&wp);
142 for level in scan_scratch.levels() {
143 rec.read_write(level);
144 }
145 rec.preflight(runtime)
146 .map_err(|e| XlogError::Kernel(format!("{ctx}: range preflight: {e}")))?;
147 let kernel = self
148 .device()
149 .inner()
150 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_RANGE_U32)
151 .ok_or_else(|| XlogError::Kernel("fj_delta_range_u32 not found".to_string()))?;
152 let grid = n_delta.div_ceil(BLOCK_SIZE);
153 let enqueue = |stream: &crate::launch::CudaEnqueue<'_>| -> Result<()> {
155 unsafe {
156 kernel
157 .clone()
158 .launch_in(
159 stream,
160 LaunchConfig {
161 grid_dim: (grid, 1, 1),
162 block_dim: (BLOCK_SIZE, 1, 1),
163 shared_mem_bytes: 0,
164 },
165 (&delta_y_v, n_delta, &edge_y_v, n_edge, &range_lo, &mut wp),
166 )
167 .map_err(|e| {
168 XlogError::Kernel(format!("fj_delta_range_u32 launch: {e}"))
169 })?;
170 }
171 self.multiblock_scan_u32_inplace_on_stream(
172 &mut wp,
173 n_delta + 1,
174 stream,
175 &mut scan_scratch,
176 )?;
177 Ok(())
178 };
179 let rec = unsafe { rec.enqueue_prepared_with(&cu_stream, enqueue) }
181 .map_err(|error| error.into_xlog_error())?;
182 rec.commit()
183 .map_err(|e| XlogError::Kernel(format!("{ctx}: range commit: {e}")))?;
184 }
185 cu_stream
186 .synchronize()
187 .map_err(|e| XlogError::Kernel(format!("{ctx}: range sync: {e}")))?;
188 let total_work = u64::from(self.dtoh_scalar_untracked::<u32>(&wp, n_delta as usize)?);
189 if total_work == 0 {
190 return Ok(Some(self.create_empty_buffer(out_schema)?));
191 }
192 if total_work > u64::from(u32::MAX - 1) {
193 return Err(XlogError::Kernel(format!(
194 "{ctx}: candidate work {total_work} exceeds u32 work-index space"
195 )));
196 }
197 let total_work = total_work as u32;
198
199 const EST_BITS: u32 = 1 << 26;
208 const EST_WORDS: u32 = EST_BITS / 32;
209 let est_bit_mask = EST_BITS - 1;
210 let mut est = self.memory().alloc::<u32>(EST_WORDS as usize)?;
211 self.device()
212 .inner()
213 .memset_zeros(&mut est)
214 .map_err(|e| XlogError::Kernel(format!("{ctx}: zero estimator: {e}")))?;
215 let mut est_counts = self.memory().alloc::<u32>(EST_WORDS as usize + 1)?;
216 {
217 let mut scan_scratch = self.multiblock_scan_u32_scratch_for_len(EST_WORDS + 1)?;
218 let mut rec = LaunchRecorder::new_strict(launch_stream);
219 rec.read_column(delta_x);
220 rec.read_column(edge_z);
221 rec.read(&range_lo);
222 rec.read(&wp);
223 rec.read_write(&est);
224 rec.write(&est_counts);
225 for level in scan_scratch.levels() {
226 rec.read_write(level);
227 }
228 rec.preflight(runtime)
229 .map_err(|e| XlogError::Kernel(format!("{ctx}: estimate preflight: {e}")))?;
230 let delta_x_v = self.column_as_u32_view(delta_x, n_delta as usize)?;
231 let edge_z_v = self.column_as_u32_view(edge_z, n_edge as usize)?;
232 let estimate = self
233 .device()
234 .inner()
235 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_SPARSE_ESTIMATE)
236 .ok_or_else(|| {
237 XlogError::Kernel("fj_delta_sparse_estimate not found".to_string())
238 })?;
239 let grid = total_work.div_ceil(BLOCK_SIZE);
240 let enqueue = |stream: &crate::launch::CudaEnqueue<'_>| -> Result<()> {
243 unsafe {
244 estimate
245 .clone()
246 .launch_in(
247 stream,
248 LaunchConfig {
249 grid_dim: (grid, 1, 1),
250 block_dim: (BLOCK_SIZE, 1, 1),
251 shared_mem_bytes: 0,
252 },
253 (
254 &delta_x_v,
255 n_delta,
256 &range_lo,
257 &wp,
258 total_work,
259 &edge_z_v,
260 &mut est,
261 est_bit_mask,
262 ),
263 )
264 .map_err(|e| {
265 XlogError::Kernel(format!("fj_delta_sparse_estimate launch: {e}"))
266 })?;
267 }
268 let popcount = self
271 .device()
272 .inner()
273 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_POPCOUNT)
274 .ok_or_else(|| XlogError::Kernel("fj_delta_popcount not found".to_string()))?;
275 let pgrid = EST_WORDS.div_ceil(BLOCK_SIZE);
276 unsafe {
278 popcount
279 .clone()
280 .launch_in(
281 stream,
282 LaunchConfig {
283 grid_dim: (pgrid, 1, 1),
284 block_dim: (BLOCK_SIZE, 1, 1),
285 shared_mem_bytes: 0,
286 },
287 (&est, EST_WORDS, &mut est_counts),
288 )
289 .map_err(|e| {
290 XlogError::Kernel(format!("estimator popcount launch: {e}"))
291 })?;
292 }
293 self.multiblock_scan_u32_inplace_on_stream(
294 &mut est_counts,
295 EST_WORDS + 1,
296 stream,
297 &mut scan_scratch,
298 )?;
299 Ok(())
300 };
301 let rec = unsafe { rec.enqueue_prepared_with(&cu_stream, enqueue) }
303 .map_err(|error| error.into_xlog_error())?;
304 rec.commit()
305 .map_err(|e| XlogError::Kernel(format!("{ctx}: estimate commit: {e}")))?;
306 }
307 cu_stream
308 .synchronize()
309 .map_err(|e| XlogError::Kernel(format!("{ctx}: estimate sync: {e}")))?;
310 let distinct_est = self.dtoh_scalar_untracked::<u32>(&est_counts, EST_WORDS as usize)?;
311 drop(est);
314 drop(est_counts);
315
316 let est_margined = (u64::from(distinct_est) * 3) / 2;
322 let upper = u64::from(n_r) + est_margined + 1;
323 let want = upper
324 .checked_mul(2)
325 .ok_or_else(|| XlogError::Kernel(format!("{ctx}: table size overflow")))?;
326 let mut cap: u64 = 1;
327 while cap < want {
328 cap <<= 1;
329 }
330 if cap > u64::from(u32::MAX) {
331 return Err(XlogError::Kernel(format!(
332 "{ctx}: hash table capacity {cap} exceeds u32 slot space (workload too large \
333 for the spike's single-table sizing)"
334 )));
335 }
336 if max_table_bytes != 0 {
340 let table_bytes = cap.saturating_mul(8 + 1 + 4).saturating_add(4);
341 if table_bytes > max_table_bytes {
342 return Ok(None);
343 }
344 }
345 let cap = cap as u32;
346 let mask = cap - 1;
347
348 let mut table = self.memory().alloc::<u64>(cap as usize)?;
349 let mut is_r = self.memory().alloc::<u8>(cap as usize)?;
350 self.device()
351 .inner()
352 .memset_zeros(&mut table)
353 .map_err(|e| XlogError::Kernel(format!("{ctx}: zero table: {e}")))?;
354 self.device()
355 .inner()
356 .memset_zeros(&mut is_r)
357 .map_err(|e| XlogError::Kernel(format!("{ctx}: zero is_r: {e}")))?;
358 let mut overflow = self.memory().alloc::<u32>(1)?;
359 self.device()
360 .inner()
361 .memset_zeros(&mut overflow)
362 .map_err(|e| XlogError::Kernel(format!("{ctx}: zero overflow: {e}")))?;
363
364 {
366 let mut rec = LaunchRecorder::new_strict(launch_stream);
367 rec.read_column(delta_x);
368 rec.read_column(edge_z);
369 rec.read(&range_lo);
370 rec.read(&wp);
371 rec.read_write(&table);
372 rec.read_write(&is_r);
373 rec.write(&overflow);
374 if n_r > 0 {
375 rec.read_column(r_x);
376 rec.read_column(r_z);
377 }
378 rec.preflight(runtime)
379 .map_err(|e| XlogError::Kernel(format!("{ctx}: insert preflight: {e}")))?;
380
381 let enqueue = |stream: &crate::launch::CudaEnqueue<'_>| -> Result<()> {
382 if n_r > 0 {
383 let r_x_v = self.column_as_u32_view(r_x, n_r as usize)?;
384 let r_z_v = self.column_as_u32_view(r_z, n_r as usize)?;
385 let load_r = self
386 .device()
387 .inner()
388 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_SPARSE_LOAD_R)
389 .ok_or_else(|| {
390 XlogError::Kernel("fj_delta_sparse_load_r not found".to_string())
391 })?;
392 let grid = n_r.div_ceil(BLOCK_SIZE);
393 unsafe {
395 load_r
396 .clone()
397 .launch_in(
398 stream,
399 LaunchConfig {
400 grid_dim: (grid, 1, 1),
401 block_dim: (BLOCK_SIZE, 1, 1),
402 shared_mem_bytes: 0,
403 },
404 (
405 &r_x_v,
406 &r_z_v,
407 n_r,
408 &mut table,
409 &mut is_r,
410 mask,
411 &mut overflow,
412 ),
413 )
414 .map_err(|e| {
415 XlogError::Kernel(format!("fj_delta_sparse_load_r launch: {e}"))
416 })?;
417 }
418 }
419
420 let delta_x_v = self.column_as_u32_view(delta_x, n_delta as usize)?;
421 let edge_z_v = self.column_as_u32_view(edge_z, n_edge as usize)?;
422 let insert = self
423 .device()
424 .inner()
425 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_SPARSE_INSERT_CANDIDATES)
426 .ok_or_else(|| {
427 XlogError::Kernel("fj_delta_sparse_insert_candidates not found".to_string())
428 })?;
429 let grid = total_work.div_ceil(BLOCK_SIZE);
430 unsafe {
433 insert
434 .clone()
435 .launch_in(
436 stream,
437 LaunchConfig {
438 grid_dim: (grid, 1, 1),
439 block_dim: (BLOCK_SIZE, 1, 1),
440 shared_mem_bytes: 0,
441 },
442 (
443 &delta_x_v,
444 n_delta,
445 &range_lo,
446 &wp,
447 total_work,
448 &edge_z_v,
449 &mut table,
450 mask,
451 &mut overflow,
452 ),
453 )
454 .map_err(|e| {
455 XlogError::Kernel(format!(
456 "fj_delta_sparse_insert_candidates launch: {e}"
457 ))
458 })?;
459 }
460 Ok(())
461 };
462 let rec = unsafe { rec.enqueue_prepared_with(&cu_stream, enqueue) }
464 .map_err(|error| error.into_xlog_error())?;
465 rec.commit()
466 .map_err(|e| XlogError::Kernel(format!("{ctx}: insert commit: {e}")))?;
467 }
468 cu_stream
469 .synchronize()
470 .map_err(|e| XlogError::Kernel(format!("{ctx}: insert sync: {e}")))?;
471
472 if self.dtoh_scalar_untracked::<u32>(&overflow, 0)? != 0 {
477 return Ok(None);
478 }
479
480 let mut counts = self.memory().alloc::<u32>(cap as usize + 1)?;
482 {
483 let mut scan_scratch = self.multiblock_scan_u32_scratch_for_len(cap + 1)?;
484 let mut rec = LaunchRecorder::new_strict(launch_stream);
485 rec.read(&table);
486 rec.read(&is_r);
487 rec.write(&counts);
488 for level in scan_scratch.levels() {
489 rec.read_write(level);
490 }
491 rec.preflight(runtime)
492 .map_err(|e| XlogError::Kernel(format!("{ctx}: mark preflight: {e}")))?;
493 let mark = self
494 .device()
495 .inner()
496 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_SPARSE_MARK)
497 .ok_or_else(|| XlogError::Kernel("fj_delta_sparse_mark not found".to_string()))?;
498 let grid = cap.div_ceil(BLOCK_SIZE);
499 let enqueue = |stream: &crate::launch::CudaEnqueue<'_>| -> Result<()> {
501 unsafe {
502 mark.clone()
503 .launch_in(
504 stream,
505 LaunchConfig {
506 grid_dim: (grid, 1, 1),
507 block_dim: (BLOCK_SIZE, 1, 1),
508 shared_mem_bytes: 0,
509 },
510 (&table, &is_r, cap, &mut counts),
511 )
512 .map_err(|e| {
513 XlogError::Kernel(format!("fj_delta_sparse_mark launch: {e}"))
514 })?;
515 }
516 self.multiblock_scan_u32_inplace_on_stream(
517 &mut counts,
518 cap + 1,
519 stream,
520 &mut scan_scratch,
521 )?;
522 Ok(())
523 };
524 let rec = unsafe { rec.enqueue_prepared_with(&cu_stream, enqueue) }
526 .map_err(|error| error.into_xlog_error())?;
527 rec.commit()
528 .map_err(|e| XlogError::Kernel(format!("{ctx}: mark commit: {e}")))?;
529 }
530 cu_stream
531 .synchronize()
532 .map_err(|e| XlogError::Kernel(format!("{ctx}: mark sync: {e}")))?;
533 let total_novel = self.dtoh_scalar_untracked::<u32>(&counts, cap as usize)?;
534 if total_novel == 0 {
535 return Ok(Some(self.create_empty_buffer(out_schema)?));
536 }
537
538 let out_x = self.memory().alloc::<u32>(total_novel as usize)?;
539 let out_z = self.memory().alloc::<u32>(total_novel as usize)?;
540 {
541 let mut rec = LaunchRecorder::new_strict(launch_stream);
542 rec.read(&table);
543 rec.read(&is_r);
544 rec.read(&counts);
545 rec.write(&out_x);
546 rec.write(&out_z);
547 rec.preflight(runtime)
548 .map_err(|e| XlogError::Kernel(format!("{ctx}: emit preflight: {e}")))?;
549 let emit = self
550 .device()
551 .inner()
552 .get_func(WCOJ_MODULE, wcoj_kernels::FJ_DELTA_SPARSE_EMIT)
553 .ok_or_else(|| XlogError::Kernel("fj_delta_sparse_emit not found".to_string()))?;
554 let grid = cap.div_ceil(BLOCK_SIZE);
555 let enqueue = |stream: &crate::launch::CudaEnqueue<'_>| -> Result<()> {
557 unsafe {
558 emit.clone()
559 .launch_in(
560 stream,
561 LaunchConfig {
562 grid_dim: (grid, 1, 1),
563 block_dim: (BLOCK_SIZE, 1, 1),
564 shared_mem_bytes: 0,
565 },
566 (&table, &is_r, &counts, cap, &out_x, &out_z),
567 )
568 .map_err(|e| {
569 XlogError::Kernel(format!("fj_delta_sparse_emit launch: {e}"))
570 })?;
571 }
572 Ok(())
573 };
574 let rec = unsafe { rec.enqueue_prepared_with(&cu_stream, enqueue) }
576 .map_err(|error| error.into_xlog_error())?;
577 rec.commit()
578 .map_err(|e| XlogError::Kernel(format!("{ctx}: emit commit: {e}")))?;
579 }
580 cu_stream
581 .synchronize()
582 .map_err(|e| XlogError::Kernel(format!("{ctx}: emit sync: {e}")))?;
583
584 let d_nr = self.memory().alloc::<u32>(1)?;
585 let mut rec_num_rows = LaunchRecorder::new_strict(launch_stream);
586 rec_num_rows.write(&d_nr);
587 rec_num_rows.preflight(runtime).map_err(|error| {
588 XlogError::Kernel(format!("{ctx}: num_rows preflight failed: {error}"))
589 })?;
590 let rec_num_rows = unsafe {
591 rec_num_rows.enqueue_prepared_with(&cu_stream, |enqueue| {
592 self.initialize_launch_metadata_u32(
593 total_novel,
594 &d_nr,
595 enqueue,
596 &format!("{ctx}: result num_rows"),
597 )
598 })
599 }
600 .map_err(crate::launch::LaunchEnqueueError::into_xlog_error)?;
601 rec_num_rows.commit().map_err(|error| {
602 XlogError::Kernel(format!("{ctx}: num_rows commit failed: {error}"))
603 })?;
604 let columns = if cols.r_carry == 0 {
605 vec![out_x.into_bytes().into(), out_z.into_bytes().into()]
606 } else {
607 vec![out_z.into_bytes().into(), out_x.into_bytes().into()]
608 };
609 Ok(Some(CudaBuffer::from_columns_with_host_count(
610 columns,
611 u64::from(total_novel),
612 d_nr,
613 out_schema,
614 total_novel,
615 )))
616 }
617}