#![allow(clippy::collapsible_if)]
use std::sync::atomic::{AtomicU64, Ordering};
use cubecl::prelude::*;
use cubecl::wgpu::WgpuRuntime;
use jerky::bit_vector::BitVectorIndex;
use jerky::bit_vector::{BitVector, Select};
use jerky::gpu::{DeviceU32Buffer, GpuContext, GpuWaveletMatrix};
use triblespace_core::blob::encodings::succinctarchive::{
SuccinctArchive, SuccinctArchiveConstraint, SuccinctRotation, Universe,
};
use triblespace_core::inline::encodings::genid::GenId;
use triblespace_core::inline::{InlineEncoding, RawInline};
use triblespace_core::query::{
and_words, Binding, Candidates, Constraint, Frontier, ProposalBuffer, RawTerm, Term,
TriblePattern, VariableId, VariableSet, LIVENESS_WORD_BITS,
};
const THREADS: u32 = super::THREADS;
const _: () = assert!(
LIVENESS_WORD_BITS == 32,
"packed confirm hardcodes 32 bits per liveness word: the plane ballot's \
component 0, the one-store-per-plane guard, and the bit/word arithmetic \
in the confirm kernels all assume it. Widen those with the word."
);
const _: () = assert!(
THREADS % 32 == 0,
"packed confirm needs a cube dim that is a multiple of the 32-bit liveness word"
);
const RANK_OUT_OF_RANGE: u32 = u32::MAX;
pub type WgpuWaveletMatrix = GpuWaveletMatrix<WgpuRuntime>;
pub type WgpuContext = GpuContext<WgpuRuntime>;
pub const DEFAULT_MIN_CONFIRM_BATCH: usize = 16384;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct WgpuConfirmStats {
pub gpu_confirms: u64,
pub gpu_candidates: u64,
pub gpu_parents: u64,
pub cpu_fallback_confirms: u64,
pub cpu_fallback_candidates: u64,
pub gpu_errors: u64,
}
#[derive(Default)]
struct ConfirmStats {
gpu_confirms: AtomicU64,
gpu_candidates: AtomicU64,
gpu_parents: AtomicU64,
cpu_fallback_confirms: AtomicU64,
cpu_fallback_candidates: AtomicU64,
gpu_errors: AtomicU64,
}
impl ConfirmStats {
fn record_gpu(&self, candidates: usize, parents: usize) {
self.gpu_confirms.fetch_add(1, Ordering::Relaxed);
self.gpu_candidates
.fetch_add(candidates as u64, Ordering::Relaxed);
self.gpu_parents
.fetch_add(parents as u64, Ordering::Relaxed);
}
fn record_cpu(&self, candidates: usize) {
self.cpu_fallback_confirms.fetch_add(1, Ordering::Relaxed);
self.cpu_fallback_candidates
.fetch_add(candidates as u64, Ordering::Relaxed);
}
fn record_error(&self) {
self.gpu_errors.fetch_add(1, Ordering::Relaxed);
}
fn snapshot(&self) -> WgpuConfirmStats {
WgpuConfirmStats {
gpu_confirms: self.gpu_confirms.load(Ordering::Relaxed),
gpu_candidates: self.gpu_candidates.load(Ordering::Relaxed),
gpu_parents: self.gpu_parents.load(Ordering::Relaxed),
cpu_fallback_confirms: self.cpu_fallback_confirms.load(Ordering::Relaxed),
cpu_fallback_candidates: self.cpu_fallback_candidates.load(Ordering::Relaxed),
gpu_errors: self.gpu_errors.load(Ordering::Relaxed),
}
}
fn reset(&self) {
self.gpu_confirms.store(0, Ordering::Relaxed);
self.gpu_candidates.store(0, Ordering::Relaxed);
self.gpu_parents.store(0, Ordering::Relaxed);
self.cpu_fallback_confirms.store(0, Ordering::Relaxed);
self.cpu_fallback_candidates.store(0, Ordering::Relaxed);
self.gpu_errors.store(0, Ordering::Relaxed);
}
}
#[cube]
fn value_order(universe: &Array<u32>, d: u32, probes: &Array<u32>, i: u32) -> u32 {
let mut order = u32::new(0);
let mut w = u32::new(0);
while w < 8u32 {
if order == 0u32 {
let dv = universe[(d * 8u32 + w) as usize];
let cv = probes[(i * 8u32 + w) as usize];
if dv < cv {
order = 1u32;
}
if dv > cv {
order = 2u32;
}
}
w += 1u32;
}
order
}
#[cube]
fn universe_lower_bound(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
let mut lo = u32::new(0);
let mut hi = m;
while lo < hi {
let mid = lo + (hi - lo) / 2u32;
if value_order(universe, mid, probes, i) == 1u32 {
lo = mid + 1u32;
} else {
hi = mid;
}
}
lo
}
#[cube]
fn universe_code(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
let mut code = m;
let d = universe_lower_bound(universe, m, probes, i);
if d < m {
if value_order(universe, d, probes, i) == 0u32 {
code = d;
}
}
code
}
#[cube]
fn candidate_is_live(live: &Array<u32>, bit_offset: u32, i: u32) -> u32 {
let b = bit_offset + i;
(live[(b / 32u32) as usize] >> (b % 32u32)) & 1u32
}
#[cube(launch_unchecked)]
fn membership_confirm_ballot_kernel(
cands: &Array<u32>,
live: &Array<u32>,
universe: &Array<u32>,
bounds: &Array<u32>,
verdicts: &mut Array<u32>,
n: u32,
m: u32,
bit_offset: u32,
) {
let b = ABSOLUTE_POS as u32;
let n_bits = bit_offset + n;
let words = (n_bits + 31u32) / 32u32;
let mut verdict = u32::new(0);
if b >= bit_offset {
if b < n_bits {
let i = b - bit_offset;
if candidate_is_live(live, bit_offset, i) != 0u32 {
let d = universe_code(universe, m, cands, i);
if d < m {
if bounds[(d + 1u32) as usize] > bounds[d as usize] {
verdict = 1u32;
}
}
}
}
}
let ballot = plane_ballot(verdict != 0u32);
if UNIT_POS_PLANE == 0u32 {
let w = b / 32u32;
if w < words {
verdicts[w as usize] = ballot[0];
}
}
}
#[cube]
#[allow(clippy::too_many_arguments)]
fn emit_candidate_probe(
cands: &Array<u32>,
live: &Array<u32>,
universe: &Array<u32>,
i: u32,
m: u32,
bit_offset: u32,
start: u32,
end: u32,
flags: &mut Array<u32>,
positions: &mut Array<u32>,
probes: &mut Array<u32>,
) {
let mut flag = u32::new(0);
let mut code = u32::new(0);
let mut lo = u32::new(0);
let mut hi = u32::new(0);
if candidate_is_live(live, bit_offset, i) != 0u32 {
if start < end {
let d = universe_code(universe, m, cands, i);
if d < m {
flag = 1u32;
code = d;
lo = start;
hi = end;
}
}
}
flags[i as usize] = flag;
positions[(2u32 * i) as usize] = lo;
positions[(2u32 * i + 1u32) as usize] = hi;
probes[(2u32 * i) as usize] = code;
probes[(2u32 * i + 1u32) as usize] = code;
}
#[cube(launch_unchecked)]
fn base_probe_fill_kernel(
cands: &Array<u32>,
live: &Array<u32>,
universe: &Array<u32>,
slots: &Array<u32>,
parent_values: &Array<u32>,
bounds: &Array<u32>,
flags: &mut Array<u32>,
positions: &mut Array<u32>,
probes: &mut Array<u32>,
n: u32,
m: u32,
bit_offset: u32,
) {
let i = ABSOLUTE_POS as u32;
if i < n {
let mut start = u32::new(0);
let mut end = u32::new(0);
if candidate_is_live(live, bit_offset, i) != 0u32 {
let slot = slots[i as usize];
let d = universe_code(universe, m, parent_values, slot);
if d < m {
start = bounds[d as usize];
end = bounds[(d + 1u32) as usize];
}
}
emit_candidate_probe(
cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
);
}
}
#[cube(launch_unchecked)]
fn parent_restrict_probe_kernel(
universe: &Array<u32>,
outer_bounds: &Array<u32>,
outer_values: &Array<u32>,
inner_values: &Array<u32>,
codes: &mut Array<u32>,
flags: &mut Array<u32>,
positions: &mut Array<u32>,
probes: &mut Array<u32>,
p: u32,
m: u32,
) {
let j = ABSOLUTE_POS as u32;
if j < p {
let mut flag = u32::new(0);
let mut code = u32::new(0);
let mut lo = u32::new(0);
let mut hi = u32::new(0);
let outer = universe_code(universe, m, outer_values, j);
if outer < m {
let inner = universe_code(universe, m, inner_values, j);
if inner < m {
flag = 1u32;
code = inner;
lo = outer_bounds[outer as usize];
hi = outer_bounds[(outer + 1u32) as usize];
}
}
codes[j as usize] = code;
flags[j as usize] = flag;
positions[(2u32 * j) as usize] = lo;
positions[(2u32 * j + 1u32) as usize] = hi;
probes[(2u32 * j) as usize] = code;
probes[(2u32 * j + 1u32) as usize] = code;
}
}
#[cube(launch_unchecked)]
fn restrict_probe_fill_kernel(
cands: &Array<u32>,
live: &Array<u32>,
universe: &Array<u32>,
slots: &Array<u32>,
parent_flags: &Array<u32>,
parent_codes: &Array<u32>,
parent_ranks: &Array<u32>,
inner_bounds: &Array<u32>,
flags: &mut Array<u32>,
positions: &mut Array<u32>,
probes: &mut Array<u32>,
n: u32,
m: u32,
out_of_range: u32,
bit_offset: u32,
) {
let i = ABSOLUTE_POS as u32;
if i < n {
let mut start = u32::new(0);
let mut end = u32::new(0);
if candidate_is_live(live, bit_offset, i) != 0u32 {
let slot = slots[i as usize];
if parent_flags[slot as usize] != 0u32 {
let lo = parent_ranks[(2u32 * slot) as usize];
let hi = parent_ranks[(2u32 * slot + 1u32) as usize];
if lo != out_of_range {
if hi != out_of_range {
let base = inner_bounds[parent_codes[slot as usize] as usize];
start = base + lo;
end = base + hi;
}
}
}
}
emit_candidate_probe(
cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
);
}
}
#[cube(launch_unchecked)]
fn range_verdict_ballot_kernel(
flags: &Array<u32>,
ranks: &Array<u32>,
verdicts: &mut Array<u32>,
n: u32,
out_of_range: u32,
bit_offset: u32,
) {
let b = ABSOLUTE_POS as u32;
let n_bits = bit_offset + n;
let words = (n_bits + 31u32) / 32u32;
let mut verdict = u32::new(0);
if b >= bit_offset {
if b < n_bits {
let i = b - bit_offset;
if flags[i as usize] != 0u32 {
let lo = ranks[(2u32 * i) as usize];
let hi = ranks[(2u32 * i + 1u32) as usize];
if lo != out_of_range {
if hi != out_of_range {
if lo != hi {
verdict = 1u32;
}
}
}
}
}
}
let ballot = plane_ballot(verdict != 0u32);
if UNIT_POS_PLANE == 0u32 {
let w = b / 32u32;
if w < words {
verdicts[w as usize] = ballot[0];
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Axis {
Entity,
Attribute,
Value,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum ConfirmPlan {
Membership { axis: Axis },
Base {
bound: Axis,
rotation: SuccinctRotation,
},
Restrict {
outer: Axis,
inner: Axis,
inner_col: SuccinctRotation,
rotation: SuccinctRotation,
},
}
fn pack_be_words(values: &[RawInline]) -> Vec<u32> {
let mut words = Vec::with_capacity(values.len() * 8);
for value in values {
for chunk in value.chunks_exact(4) {
words.push(u32::from_be_bytes(chunk.try_into().unwrap()));
}
}
words
}
fn count_live(cands: &Candidates<'_>) -> usize {
(0..cands.len()).filter(|&i| cands.is_live(i)).count()
}
fn parent_table(
frontier: &Frontier<'_>,
cands: &Candidates<'_>,
) -> jerky::Result<(Vec<u32>, Vec<u32>)> {
let width = frontier.len();
let mut slot_of_row = vec![u32::MAX; width];
let mut slots = Vec::with_capacity(cands.len());
let mut rows: Vec<u32> = Vec::new();
for &parent in cands.parents() {
let row = parent as usize;
if row >= width {
return Err(jerky::Error::invalid_argument(format!(
"candidate parent tag {parent} exceeds the {width} rows of its frontier"
)));
}
let mut slot = slot_of_row[row];
if slot == u32::MAX {
slot = rows.len() as u32;
slot_of_row[row] = slot;
rows.push(parent);
}
slots.push(slot);
}
Ok((slots, rows))
}
pub struct WgpuSuccinctArchive<U>
where
U: Universe,
{
archive: SuccinctArchive<U>,
context: WgpuContext,
universe_words: DeviceU32Buffer<WgpuRuntime>,
domain_len: usize,
e_bounds: DeviceU32Buffer<WgpuRuntime>,
a_bounds: DeviceU32Buffer<WgpuRuntime>,
v_bounds: DeviceU32Buffer<WgpuRuntime>,
ring: [WgpuWaveletMatrix; SuccinctRotation::ALL.len()],
min_confirm_batch: usize,
stats: ConfirmStats,
}
fn axis_bounds<I: BitVectorIndex>(
context: &WgpuContext,
prefix: &BitVector<I>,
domain_len: usize,
axis: &'static str,
) -> jerky::Result<DeviceU32Buffer<WgpuRuntime>> {
let mut bounds = Vec::with_capacity(domain_len + 1);
for d in 0..=domain_len {
let position = prefix.select1(d).ok_or_else(|| {
jerky::Error::invalid_argument(format!(
"{axis} prefix is missing delimiter {d} of {domain_len}"
))
})?;
let count = position - d;
bounds.push(u32::try_from(count).map_err(|_| {
jerky::Error::invalid_argument(format!(
"{axis} prefix count {count} does not fit the resident u32 domain"
))
})?);
}
context.upload_u32(&bounds)
}
impl<U> WgpuSuccinctArchive<U>
where
U: Universe,
{
pub fn new(archive: SuccinctArchive<U>) -> jerky::Result<Self> {
let domain_len = archive.domain.len();
let triple_count = archive.eav_c.len();
if domain_len >= (u32::MAX as usize) / 8 {
return Err(jerky::Error::invalid_argument(format!(
"universe of {domain_len} values does not fit the resident u32 domain"
)));
}
if triple_count >= u32::MAX as usize {
return Err(jerky::Error::invalid_argument(format!(
"archive of {triple_count} rows does not fit the resident u32 domain"
)));
}
let mut universe_values = Vec::with_capacity(domain_len);
for d in 0..domain_len {
let value = archive.domain.access(d);
if let Some(previous) = universe_values.last() {
if *previous >= value {
return Err(jerky::Error::invalid_argument(format!(
"universe access order is not strictly ascending at code {d}"
)));
}
}
universe_values.push(value);
}
let universe_image = pack_be_words(&universe_values);
let context = WgpuContext::on_wgpu();
let universe_words = context.upload_u32(&universe_image)?;
let e_bounds = axis_bounds(&context, &archive.e_a, domain_len, "entity")?;
let a_bounds = axis_bounds(&context, &archive.a_a, domain_len, "attribute")?;
let v_bounds = axis_bounds(&context, &archive.v_a, domain_len, "value")?;
let ring = [
WgpuWaveletMatrix::with_context(context.clone(), &archive.eav_c)?,
WgpuWaveletMatrix::with_context(context.clone(), &archive.vea_c)?,
WgpuWaveletMatrix::with_context(context.clone(), &archive.ave_c)?,
WgpuWaveletMatrix::with_context(context.clone(), &archive.vae_c)?,
WgpuWaveletMatrix::with_context(context.clone(), &archive.eva_c)?,
WgpuWaveletMatrix::with_context(context.clone(), &archive.aev_c)?,
];
Ok(Self {
archive,
context,
universe_words,
domain_len,
e_bounds,
a_bounds,
v_bounds,
ring,
min_confirm_batch: DEFAULT_MIN_CONFIRM_BATCH,
stats: ConfirmStats::default(),
})
}
pub fn with_min_confirm_batch(mut self, min_confirm_batch: usize) -> Self {
self.min_confirm_batch = min_confirm_batch;
self
}
pub fn set_min_confirm_batch(&mut self, min_confirm_batch: usize) {
self.min_confirm_batch = min_confirm_batch;
}
pub fn min_confirm_batch(&self) -> usize {
self.min_confirm_batch
}
pub fn archive(&self) -> &SuccinctArchive<U> {
&self.archive
}
pub fn into_archive(self) -> SuccinctArchive<U> {
self.archive
}
pub fn context(&self) -> &WgpuContext {
&self.context
}
pub fn stats(&self) -> WgpuConfirmStats {
self.stats.snapshot()
}
pub fn reset_stats(&self) {
self.stats.reset();
}
pub fn ring_col(&self, rotation: SuccinctRotation) -> &WgpuWaveletMatrix {
&self.ring[rotation.index()]
}
fn axis_bounds_buffer(&self, axis: Axis) -> &DeviceU32Buffer<WgpuRuntime> {
match axis {
Axis::Entity => &self.e_bounds,
Axis::Attribute => &self.a_bounds,
Axis::Value => &self.v_bounds,
}
}
fn elemwise(&self, len: usize) -> (CubeCount, CubeDim) {
let cube_dim = CubeDim::new_1d(THREADS);
let cube_count =
cubecl::calculate_cube_count_elemwise(self.context.client(), len, cube_dim);
(cube_count, cube_dim)
}
fn require_plane_packing(&self) -> jerky::Result<()> {
use cubecl::ir::features::Plane;
let properties = self.context.client().properties();
if !properties.features.plane.contains(Plane::Ops) {
return Err(jerky::Error::invalid_argument(
"device does not support plane (subgroup) operations",
));
}
let (min, max) = (
properties.hardware.plane_size_min,
properties.hardware.plane_size_max,
);
if min != 32 || max != 32 {
return Err(jerky::Error::invalid_argument(format!(
"packed confirm needs a plane size of exactly 32, device reports {min}..={max}"
)));
}
Ok(())
}
fn confirm_membership_gpu(&self, axis: Axis, cands: &mut Candidates<'_>) -> jerky::Result<()> {
let n = cands.len();
self.require_plane_packing()?;
let bit_offset = cands.bit_offset();
let words = cands.live_word_len();
let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
let mut live = cands.live_words();
let live_words = self.context.upload_u32(&live)?;
let mut verdict_words = self.context.empty_u32(words)?;
let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
unsafe {
membership_confirm_ballot_kernel::launch_unchecked::<WgpuRuntime>(
self.context.client(),
cube_count,
cube_dim,
cand_words.input_arg(),
live_words.input_arg(),
self.universe_words.input_arg(),
self.axis_bounds_buffer(axis).input_arg(),
verdict_words.output_arg(),
n as u32,
self.domain_len as u32,
bit_offset as u32,
)
};
let verdicts = verdict_words.read();
and_words(&mut live, &verdicts);
cands.set_live_words(&live);
Ok(())
}
fn confirm_base_gpu(
&self,
axis: Axis,
rotation: SuccinctRotation,
slots: &[u32],
parent_values: &[RawInline],
cands: &mut Candidates<'_>,
) -> jerky::Result<()> {
let n = cands.len();
self.require_plane_packing()?;
let bit_offset = cands.bit_offset() as u32;
let slot_words = self.context.upload_u32(slots)?;
let value_words = self.context.upload_u32(&pack_be_words(parent_values))?;
let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
let live_words = self.context.upload_u32(&cands.live_words())?;
let mut flags = self.context.empty_u32(n)?;
let mut positions = self.context.empty_u32(2 * n)?;
let mut probes = self.context.empty_u32(2 * n)?;
let (cube_count, cube_dim) = self.elemwise(n);
unsafe {
base_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
self.context.client(),
cube_count,
cube_dim,
cand_words.input_arg(),
live_words.input_arg(),
self.universe_words.input_arg(),
slot_words.input_arg(),
value_words.input_arg(),
self.axis_bounds_buffer(axis).input_arg(),
flags.output_arg(),
positions.output_arg(),
probes.output_arg(),
n as u32,
self.domain_len as u32,
bit_offset,
)
};
self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
}
#[allow(clippy::too_many_arguments)]
fn confirm_restrict_gpu(
&self,
outer: Axis,
inner: Axis,
inner_col: SuccinctRotation,
rotation: SuccinctRotation,
slots: &[u32],
outer_values: &[RawInline],
inner_values: &[RawInline],
cands: &mut Candidates<'_>,
) -> jerky::Result<()> {
let n = cands.len();
self.require_plane_packing()?;
let bit_offset = cands.bit_offset() as u32;
let p = outer_values.len();
let outer_words = self.context.upload_u32(&pack_be_words(outer_values))?;
let inner_words = self.context.upload_u32(&pack_be_words(inner_values))?;
let mut parent_codes = self.context.empty_u32(p)?;
let mut parent_flags = self.context.empty_u32(p)?;
let mut parent_positions = self.context.empty_u32(2 * p)?;
let mut parent_probes = self.context.empty_u32(2 * p)?;
let mut parent_ranks = self.context.empty_u32(2 * p)?;
let (parent_count, cube_dim) = self.elemwise(p);
unsafe {
parent_restrict_probe_kernel::launch_unchecked::<WgpuRuntime>(
self.context.client(),
parent_count,
cube_dim,
self.universe_words.input_arg(),
self.axis_bounds_buffer(outer).input_arg(),
outer_words.input_arg(),
inner_words.input_arg(),
parent_codes.output_arg(),
parent_flags.output_arg(),
parent_positions.output_arg(),
parent_probes.output_arg(),
p as u32,
self.domain_len as u32,
)
};
self.ring_col(inner_col).rank_batch_into(
&parent_positions,
&parent_probes,
&mut parent_ranks,
)?;
let slot_words = self.context.upload_u32(slots)?;
let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
let live_words = self.context.upload_u32(&cands.live_words())?;
let mut flags = self.context.empty_u32(n)?;
let mut positions = self.context.empty_u32(2 * n)?;
let mut probes = self.context.empty_u32(2 * n)?;
let (cube_count, cube_dim) = self.elemwise(n);
unsafe {
restrict_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
self.context.client(),
cube_count,
cube_dim,
cand_words.input_arg(),
live_words.input_arg(),
self.universe_words.input_arg(),
slot_words.input_arg(),
parent_flags.input_arg(),
parent_codes.input_arg(),
parent_ranks.input_arg(),
self.axis_bounds_buffer(inner).input_arg(),
flags.output_arg(),
positions.output_arg(),
probes.output_arg(),
n as u32,
self.domain_len as u32,
RANK_OUT_OF_RANGE,
bit_offset,
)
};
self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
}
fn fold_range_verdicts(
&self,
rotation: SuccinctRotation,
flags: &DeviceU32Buffer<WgpuRuntime>,
positions: &DeviceU32Buffer<WgpuRuntime>,
probes: &DeviceU32Buffer<WgpuRuntime>,
cands: &mut Candidates<'_>,
) -> jerky::Result<()> {
let n = cands.len();
let bit_offset = cands.bit_offset();
let mut ranks = self.context.empty_u32(2 * n)?;
let mut verdict_words = self.context.empty_u32(cands.live_word_len())?;
self.ring_col(rotation)
.rank_batch_into(positions, probes, &mut ranks)?;
let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
unsafe {
range_verdict_ballot_kernel::launch_unchecked::<WgpuRuntime>(
self.context.client(),
cube_count,
cube_dim,
flags.input_arg(),
ranks.input_arg(),
verdict_words.output_arg(),
n as u32,
RANK_OUT_OF_RANGE,
bit_offset as u32,
)
};
let verdicts = verdict_words.read();
let mut live = cands.live_words();
and_words(&mut live, &verdicts);
cands.set_live_words(&live);
Ok(())
}
}
impl<U> TriblePattern for WgpuSuccinctArchive<U>
where
U: Universe + Send + Sync,
{
type PatternConstraint<'a>
= WgpuSuccinctArchiveConstraint<'a, U>
where
U: 'a;
fn pattern<'a, V: InlineEncoding>(
&'a self,
e: impl Into<Term<GenId>>,
a: impl Into<Term<GenId>>,
v: impl Into<Term<V>>,
) -> Self::PatternConstraint<'a> {
WgpuSuccinctArchiveConstraint::new(e, a, v, self)
}
}
pub struct WgpuSuccinctArchiveConstraint<'a, U>
where
U: Universe,
{
inner: SuccinctArchiveConstraint<'a, U>,
gpu: &'a WgpuSuccinctArchive<U>,
term_e: RawTerm,
term_a: RawTerm,
term_v: RawTerm,
}
impl<'a, U> WgpuSuccinctArchiveConstraint<'a, U>
where
U: Universe,
{
pub fn new<V: InlineEncoding>(
e: impl Into<Term<GenId>>,
a: impl Into<Term<GenId>>,
v: impl Into<Term<V>>,
gpu: &'a WgpuSuccinctArchive<U>,
) -> Self {
let e: Term<GenId> = e.into();
let a: Term<GenId> = a.into();
let v: Term<V> = v.into();
WgpuSuccinctArchiveConstraint {
inner: SuccinctArchiveConstraint::new(e, a, v, &gpu.archive),
gpu,
term_e: e.erase(),
term_a: a.erase(),
term_v: v.erase(),
}
}
fn term(&self, axis: Axis) -> &RawTerm {
match axis {
Axis::Entity => &self.term_e,
Axis::Attribute => &self.term_a,
Axis::Value => &self.term_v,
}
}
fn plan(&self, variable: VariableId, binding: &Binding) -> ConfirmPlan {
let e_var = self.term_e.is_var(variable);
let a_var = self.term_a.is_var(variable);
let v_var = self.term_v.is_var(variable);
let e_bound = self.term_e.position_value(binding).is_some();
let a_bound = self.term_a.position_value(binding).is_some();
let v_bound = self.term_v.position_value(binding).is_some();
match (e_bound, a_bound, v_bound, e_var, a_var, v_var) {
(false, false, false, true, false, false) => {
ConfirmPlan::Membership { axis: Axis::Entity }
}
(false, false, false, false, true, false) => ConfirmPlan::Membership {
axis: Axis::Attribute,
},
(false, false, false, false, false, true) => {
ConfirmPlan::Membership { axis: Axis::Value }
}
(true, false, false, false, true, false) => ConfirmPlan::Base {
bound: Axis::Entity,
rotation: SuccinctRotation::Eva,
},
(true, false, false, false, false, true) => ConfirmPlan::Base {
bound: Axis::Entity,
rotation: SuccinctRotation::Eav,
},
(false, true, false, true, false, false) => ConfirmPlan::Base {
bound: Axis::Attribute,
rotation: SuccinctRotation::Ave,
},
(false, true, false, false, false, true) => ConfirmPlan::Base {
bound: Axis::Attribute,
rotation: SuccinctRotation::Aev,
},
(false, false, true, true, false, false) => ConfirmPlan::Base {
bound: Axis::Value,
rotation: SuccinctRotation::Vae,
},
(false, false, true, false, true, false) => ConfirmPlan::Base {
bound: Axis::Value,
rotation: SuccinctRotation::Vea,
},
(false, true, true, true, false, false) => ConfirmPlan::Restrict {
outer: Axis::Attribute,
inner: Axis::Value,
inner_col: SuccinctRotation::Aev,
rotation: SuccinctRotation::Vae,
},
(true, false, true, false, true, false) => ConfirmPlan::Restrict {
outer: Axis::Entity,
inner: Axis::Value,
inner_col: SuccinctRotation::Eav,
rotation: SuccinctRotation::Vea,
},
(true, true, false, false, false, true) => ConfirmPlan::Restrict {
outer: Axis::Entity,
inner: Axis::Attribute,
inner_col: SuccinctRotation::Eva,
rotation: SuccinctRotation::Aev,
},
_ => unreachable!("invalid trible constraint state"),
}
}
fn parent_values(
&self,
axis: Axis,
frontier: &Frontier<'_>,
rows: &[u32],
) -> jerky::Result<Vec<RawInline>> {
let term = self.term(axis);
let mut values = Vec::with_capacity(rows.len());
for &row in rows {
let binding = frontier.row(row as usize);
let value = term.position_value(&binding).ok_or_else(|| {
jerky::Error::invalid_argument(format!(
"frontier row {row} left a bound position of the arm unbound"
))
})?;
values.push(*value);
}
Ok(values)
}
fn confirm_gpu(
&self,
variable: VariableId,
frontier: &Frontier<'_>,
cands: &mut Candidates<'_>,
) -> jerky::Result<usize> {
match self.plan(variable, &frontier.row(0)) {
ConfirmPlan::Membership { axis } => {
self.gpu.confirm_membership_gpu(axis, cands)?;
Ok(0)
}
ConfirmPlan::Base { bound, rotation } => {
let (slots, rows) = parent_table(frontier, cands)?;
let values = self.parent_values(bound, frontier, &rows)?;
self.gpu
.confirm_base_gpu(bound, rotation, &slots, &values, cands)?;
Ok(rows.len())
}
ConfirmPlan::Restrict {
outer,
inner,
inner_col,
rotation,
} => {
let (slots, rows) = parent_table(frontier, cands)?;
let outer_values = self.parent_values(outer, frontier, &rows)?;
let inner_values = self.parent_values(inner, frontier, &rows)?;
self.gpu.confirm_restrict_gpu(
outer,
inner,
inner_col,
rotation,
&slots,
&outer_values,
&inner_values,
cands,
)?;
Ok(rows.len())
}
}
}
}
impl<'a, U> Constraint<'a> for WgpuSuccinctArchiveConstraint<'a, U>
where
U: Universe,
{
fn variables(&self) -> VariableSet {
self.inner.variables()
}
fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
self.inner.estimate(variable, binding)
}
fn propose(
&self,
variable: VariableId,
frontier: &Frontier<'_>,
proposals: &mut ProposalBuffer,
) {
self.inner.propose(variable, frontier, proposals)
}
fn confirm(&self, variable: VariableId, frontier: &Frontier<'_>, cands: &mut Candidates<'_>) {
if !self.term_e.is_var(variable)
&& !self.term_a.is_var(variable)
&& !self.term_v.is_var(variable)
{
return;
}
if frontier.is_empty() || cands.is_empty() {
return;
}
let live = count_live(cands);
if live < self.gpu.min_confirm_batch {
self.gpu.stats.record_cpu(cands.len());
self.inner.confirm(variable, frontier, cands);
return;
}
match self.confirm_gpu(variable, frontier, cands) {
Ok(parents) => self.gpu.stats.record_gpu(cands.len(), parents),
Err(_) => {
self.gpu.stats.record_error();
self.inner.confirm(variable, frontier, cands);
}
}
}
fn satisfied(&self, binding: &Binding) -> bool {
self.inner.satisfied(binding)
}
fn influence(&self, variable: VariableId) -> VariableSet {
self.inner.influence(variable)
}
}