use std::sync::Arc;
use crate::chunk_cache::{CacheEntry, ChunkCache};
use crate::triples::{GroupDirectory, Triple, TripleBlock, TripleBlockBuilder};
pub type Pattern = (Option<u32>, Option<u32>, Option<u32>);
pub(crate) const PROBE_WINDOW_TILES: usize = 1024;
#[derive(Default)]
pub(crate) struct ProbeBatch {
want: [std::collections::BTreeSet<usize>; NUM_PERMS],
tiles: usize,
bytes: u64,
patterns: usize,
}
pub const INDEX_TILE_BUDGET: usize = crate::write_opts::DEFAULT_TILE_BUDGET_BYTES;
const PREFETCH_WINDOW_START: usize = 4;
const PREFETCH_WINDOW_MAX: usize = 512;
pub type TileLoader = Box<dyn Fn(usize, usize) -> Option<Vec<u8>> + Send + Sync>;
pub type TileBulkLoader = Box<dyn Fn(usize, &[usize]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
pub struct Tile {
min_a: u32,
max_a: u32,
pub(crate) syn: Option<(u32, u32, u32, u32)>,
len: u32,
staged: Option<Vec<u8>>,
}
impl Tile {
fn local(min_a: u32, max_a: u32, bytes: Vec<u8>) -> Self {
let len = bytes.len().min(u32::MAX as usize) as u32;
Tile {
min_a,
max_a,
syn: None,
len,
staged: Some(bytes),
}
}
pub(crate) fn remote_with_len(
min_a: u32,
max_a: u32,
syn: Option<(u32, u32, u32, u32)>,
len: u32,
) -> Self {
Tile {
len,
..Tile::remote(min_a, max_a, syn)
}
}
fn remote(min_a: u32, max_a: u32, syn: Option<(u32, u32, u32, u32)>) -> Self {
Tile {
min_a,
max_a,
syn,
len: 0,
staged: None,
}
}
pub(crate) fn encoded_len(&self) -> u64 {
if self.len > 0 {
self.len as u64
} else {
self.staged.as_ref().map_or(0, |d| d.len() as u64)
}
}
pub fn leading_range(&self) -> (u32, u32) {
(self.min_a, self.max_a)
}
pub(crate) fn column_range(&self, col: usize) -> Option<(u32, u32)> {
match col {
0 => Some((self.min_a, self.max_a)),
1 => self.syn.map(|s| (s.0, s.1)),
_ => self.syn.map(|s| (s.2, s.3)),
}
}
pub(crate) fn syn_admits(&self, pb: Option<u32>, pc: Option<u32>) -> bool {
match self.syn {
None => true,
Some((min_b, max_b, min_c, max_c)) => {
let ok = |v: Option<u32>, lo: u32, hi: u32| v.is_none_or(|x| lo <= x && x <= hi);
ok(pb, min_b, max_b) && ok(pc, min_c, max_c)
}
}
}
}
pub type LeafFetch = Arc<dyn Fn(&[(u64, u64)]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
pub(crate) trait LeafDir {
fn missing_leaf(&self, li: usize) -> Option<(u64, u64)>;
fn install_leaf(&self, li: usize, stored: &[u8]);
fn fail_leaves(&self);
fn leaf_fetch(&self) -> &LeafFetch;
}
pub(crate) fn ensure_leaves_across(dirs: &[(&dyn LeafDir, &[usize])]) {
let mut ranges: Vec<(u64, u64)> = Vec::new();
let mut slots: Vec<(usize, usize)> = Vec::new();
for (di, (dir, lis)) in dirs.iter().enumerate() {
let mut lis: Vec<usize> = lis.to_vec();
lis.sort_unstable();
lis.dedup();
for li in lis {
if let Some(r) = dir.missing_leaf(li) {
ranges.push(r);
slots.push((di, li));
}
}
}
let Some((first, _)) = dirs.first() else {
return;
};
if ranges.is_empty() {
return;
}
match (first.leaf_fetch())(&ranges) {
Some(blobs) if blobs.len() == slots.len() => {
for (&(di, li), b) in slots.iter().zip(&blobs) {
dirs[di].0.install_leaf(li, b);
}
}
_ => {
for &(di, _) in &slots {
dirs[di].0.fail_leaves();
}
}
}
}
#[derive(Debug, Clone)]
pub struct TileLeaf {
pub first: usize,
pub n: usize,
pub min_a: u32,
pub max_a: u32,
pub leaf: (u64, u64),
pub tile_base: u64,
}
type TileCell = std::sync::OnceLock<Box<[(Tile, u64)]>>;
pub struct LeafedTiles {
leaves: Vec<TileLeaf>,
cells: Vec<TileCell>,
total: usize,
total_bytes: u64,
fetch: LeafFetch,
codec: u8,
max_block: u64,
failed: std::sync::atomic::AtomicBool,
}
static UNREADABLE_TILE: Tile = Tile {
min_a: u32::MAX,
max_a: u32::MAX,
syn: Some((1, 0, 1, 0)),
len: 0,
staged: None,
};
impl LeafDir for LeafedTiles {
fn missing_leaf(&self, li: usize) -> Option<(u64, u64)> {
(li < self.cells.len() && self.cells[li].get().is_none()).then(|| self.leaves[li].leaf)
}
fn install_leaf(&self, li: usize, stored: &[u8]) {
match self.decode_leaf(li, stored) {
Some(v) => {
let _ = self.cells[li].set(v);
}
None => self
.failed
.store(true, std::sync::atomic::Ordering::Relaxed),
}
}
fn fail_leaves(&self) {
self.failed
.store(true, std::sync::atomic::Ordering::Relaxed);
}
fn leaf_fetch(&self) -> &LeafFetch {
&self.fetch
}
}
impl LeafedTiles {
pub fn with_max_block(mut self, max: u64) -> Self {
self.max_block = max;
self
}
pub fn new(
leaves: Vec<TileLeaf>,
total: usize,
total_bytes: u64,
fetch: LeafFetch,
codec: u8,
) -> Self {
let cells = leaves.iter().map(|_| std::sync::OnceLock::new()).collect();
LeafedTiles {
leaves,
cells,
total,
total_bytes,
fetch,
codec,
max_block: u64::MAX,
failed: std::sync::atomic::AtomicBool::new(false),
}
}
pub(crate) fn admitted_unfaulted(&self, a: u32) -> f64 {
let mut tiles = 0.0;
for (li, lf) in self.leaves.iter().enumerate() {
if a < lf.min_a || a > lf.max_a {
continue;
}
tiles += match self.cells[li].get() {
Some(v) => v
.iter()
.filter(|(t, _)| t.min_a <= a && a <= t.max_a)
.count() as f64,
None if lf.min_a == lf.max_a => lf.n as f64,
None => {
let width = (lf.max_a as f64 - lf.min_a as f64) + 1.0;
(lf.n as f64 / width).max(1.0)
}
};
}
tiles
}
fn leaf_b_span(&self, li: usize) -> Option<(u32, u32)> {
self.ensure_leaves(&[li]);
let v = self.cells[li].get()?;
let first = v.first()?.0.syn?;
let last = v.last()?.0.syn?;
Some((first.0, last.1))
}
pub(crate) fn run_end_leaves(&self, a: u32) -> Vec<usize> {
let first = self.leaves.partition_point(|lf| lf.max_a < a);
let mut last = first;
while last < self.leaves.len() && self.leaves[last].min_a <= a {
last += 1;
}
let shared = |li: usize| !(self.leaves[li].min_a == a && self.leaves[li].max_a == a);
let mut out = Vec::new();
if first < last {
if shared(first) {
out.push(first);
}
if last - 1 != first && shared(last - 1) {
out.push(last - 1);
}
}
out
}
fn count_in_leaf(&self, li: usize, a: u32, pb: Option<u32>, pc: Option<u32>) -> f64 {
self.ensure_leaves(&[li]);
match self.cells[li].get() {
Some(v) => v
.iter()
.filter(|(t, _)| t.min_a <= a && a <= t.max_a && t.syn_admits(pb, pc))
.count() as f64,
None => {
let lf = &self.leaves[li];
let width = (lf.max_a as f64 - lf.min_a as f64) + 1.0;
(lf.n as f64 / width).max(1.0)
}
}
}
pub(crate) fn admitted_estimate(&self, a: u32, pb: Option<u32>, pc: Option<u32>) -> f64 {
let first = self.leaves.partition_point(|lf| lf.max_a < a);
let mut last = first;
while last < self.leaves.len() && self.leaves[last].min_a <= a {
last += 1;
}
if first >= last {
return 0.0;
}
let mut tiles = 0.0;
let pure = |li: usize| self.leaves[li].min_a == a && self.leaves[li].max_a == a;
let (mut p0, mut p1) = (first, last);
if !pure(first) {
tiles += self.count_in_leaf(first, a, pb, pc);
p0 += 1;
}
if p1 > p0 && !pure(p1 - 1) {
tiles += self.count_in_leaf(p1 - 1, a, pb, pc);
p1 -= 1;
}
if p0 >= p1 {
return tiles;
}
let Some(b) = pb else {
return tiles + self.leaves[p0..p1].iter().map(|l| l.n as f64).sum::<f64>();
};
let search = |past: bool| -> Option<usize> {
let (mut lo, mut hi) = (p0, p1);
while lo < hi {
let mid = lo + (hi - lo) / 2;
let (min_b, max_b) = self.leaf_b_span(mid)?;
if if past { min_b > b } else { max_b >= b } {
hi = mid;
} else {
lo = mid + 1;
}
}
Some(lo)
};
let (Some(f), Some(g)) = (search(false), search(true)) else {
return tiles + self.leaves[p0..p1].iter().map(|l| l.n as f64).sum::<f64>();
};
if f >= g {
return tiles;
}
tiles += self.count_in_leaf(f, a, pb, pc);
if g - 1 > f {
tiles += self.count_in_leaf(g - 1, a, pb, pc);
tiles += self.leaves[f + 1..g - 1]
.iter()
.map(|l| l.n as f64)
.sum::<f64>();
}
tiles
}
fn leaf_of(&self, ti: usize) -> usize {
self.leaves
.partition_point(|l| l.first <= ti)
.saturating_sub(1)
}
fn decode_leaf(&self, li: usize, stored: &[u8]) -> Option<Box<[(Tile, u64)]>> {
let l = &self.leaves[li];
let raw = crate::file::decompress_bounded(self.codec, stored, self.max_block).ok()?;
let ents = crate::v06::decode_tile_leaf(&raw, l.n).ok()?;
let mut at = l.tile_base;
let mut out = Vec::with_capacity(ents.len());
for e in ents {
let mut t = Tile::remote(e.min_a, e.max_a, Some(e.syn));
t.len = e.clen.min(u32::MAX as u64) as u32;
out.push((t, at));
at = at.checked_add(e.clen)?;
}
Some(out.into_boxed_slice())
}
pub fn ensure_leaves(&self, lis: &[usize]) {
ensure_leaves_across(&[(self, lis)]);
}
pub fn ensure_span(&self, start: usize, end: usize) {
if start >= end || start >= self.total {
return;
}
let a = self.leaf_of(start);
let b = self.leaf_of(end.min(self.total) - 1);
self.ensure_leaves(&(a..=b).collect::<Vec<_>>());
}
fn entry(&self, ti: usize) -> Option<&(Tile, u64)> {
if ti >= self.total {
return None;
}
let li = self.leaf_of(ti);
if self.cells[li].get().is_none() {
self.ensure_leaves(&[li]);
}
self.cells[li].get()?.get(ti - self.leaves[li].first)
}
pub fn range(&self, ti: usize) -> Option<(u64, u64)> {
self.entry(ti).map(|(t, off)| (*off, t.len as u64))
}
pub fn load_failed(&self) -> bool {
self.failed.load(std::sync::atomic::Ordering::Relaxed)
}
pub fn reset_load_failure(&self) {
self.failed
.store(false, std::sync::atomic::Ordering::Relaxed);
}
fn resident_bytes(&self) -> u64 {
let n: usize = self
.cells
.iter()
.filter_map(|c| c.get())
.map(|v| v.len())
.sum();
(n * (std::mem::size_of::<Tile>() + 8)) as u64
+ (self.leaves.len() * std::mem::size_of::<TileLeaf>()) as u64
}
}
pub struct DeferredTiles {
cell: std::sync::OnceLock<Vec<Tile>>,
approx_bytes: u64,
load: Box<dyn Fn() -> Option<Vec<Tile>> + Send + Sync>,
failed: std::sync::atomic::AtomicBool,
}
impl DeferredTiles {
pub fn new(approx_bytes: u64, load: Box<dyn Fn() -> Option<Vec<Tile>> + Send + Sync>) -> Self {
DeferredTiles {
cell: std::sync::OnceLock::new(),
approx_bytes,
load,
failed: std::sync::atomic::AtomicBool::new(false),
}
}
fn get(&self) -> &[Tile] {
if let Some(v) = self.cell.get() {
return v;
}
match (self.load)() {
Some(v) => {
let _ = self.cell.set(v);
self.cell.get().map_or(&[][..], Vec::as_slice)
}
None => {
self.failed
.store(true, std::sync::atomic::Ordering::Relaxed);
&[]
}
}
}
}
pub struct ClusterRuns {
pub runs: Vec<(usize, usize)>,
pub classes: Vec<u32>,
pub(crate) hint: std::sync::atomic::AtomicUsize,
memo: std::sync::Mutex<std::collections::HashMap<u32, u8>>,
}
const ABSENT_RUN: u8 = u8::MAX;
const RUN_MEMO_MAX: usize = 1 << 20;
impl ClusterRuns {
pub fn new(classes: Vec<u32>, run_tiles: &[usize]) -> Self {
let mut at = 0usize;
let runs = run_tiles
.iter()
.map(|&n| {
at += n;
(at - n, at)
})
.collect();
ClusterRuns {
runs,
classes,
hint: std::sync::atomic::AtomicUsize::new(0),
memo: std::sync::Mutex::new(std::collections::HashMap::new()),
}
}
pub(crate) fn remember(&self, a: u32, run: Option<usize>) {
if let Ok(mut m) = self.memo.lock() {
if m.len() >= RUN_MEMO_MAX {
m.clear();
}
m.insert(a, run.map_or(ABSENT_RUN, |r| r as u8));
}
if let Some(r) = run {
self.hint.store(r, std::sync::atomic::Ordering::Relaxed);
}
}
pub(crate) fn recall(&self, a: u32) -> Option<Option<usize>> {
let m = self.memo.lock().ok()?;
m.get(&a).map(|&r| {
if r == ABSENT_RUN {
None
} else {
Some(r as usize)
}
})
}
}
pub enum TileList {
Full(Vec<Tile>),
Leafed(Arc<LeafedTiles>),
Deferred(Arc<DeferredTiles>),
}
impl Default for TileList {
fn default() -> Self {
TileList::Full(Vec::new())
}
}
impl std::ops::Index<usize> for TileList {
type Output = Tile;
fn index(&self, ti: usize) -> &Tile {
match self {
TileList::Full(v) => &v[ti],
TileList::Deferred(d) => d.get().get(ti).unwrap_or(&UNREADABLE_TILE),
TileList::Leafed(l) => match l.entry(ti) {
Some((t, _)) => t,
None => {
l.failed.store(true, std::sync::atomic::Ordering::Relaxed);
&UNREADABLE_TILE
}
},
}
}
}
impl TileList {
fn known_len(&self) -> usize {
match self {
TileList::Deferred(d) => d.cell.get().map_or(0, Vec::len),
other => other.len(),
}
}
pub fn len(&self) -> usize {
match self {
TileList::Full(v) => v.len(),
TileList::Deferred(d) => d.get().len(),
TileList::Leafed(l) => l.total,
}
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn as_full(&self) -> Option<&[Tile]> {
match self {
TileList::Full(v) => Some(v),
TileList::Deferred(d) => Some(d.get()),
TileList::Leafed(_) => None,
}
}
pub fn iter(&self) -> impl Iterator<Item = &Tile> {
if let TileList::Leafed(l) = self {
l.ensure_span(0, l.total);
}
(0..self.len()).map(move |i| &self[i])
}
pub fn first(&self) -> Option<&Tile> {
(!self.is_empty()).then(|| &self[0])
}
pub fn last(&self) -> Option<&Tile> {
(!self.is_empty()).then(|| &self[self.len() - 1])
}
pub fn ensure_span(&self, start: usize, end: usize) {
if let TileList::Leafed(l) = self {
l.ensure_span(start, end);
}
}
pub fn first_max_ge(&self, a: u32) -> usize {
match self {
TileList::Full(v) => v.partition_point(|t| t.max_a < a),
TileList::Deferred(d) => d.get().partition_point(|t| t.max_a < a),
TileList::Leafed(l) => {
let li = l.leaves.partition_point(|lf| lf.max_a < a);
if li >= l.leaves.len() {
return l.total;
}
let lf = &l.leaves[li];
l.ensure_leaves(&[li]);
match l.cells[li].get() {
Some(v) => lf.first + v.partition_point(|(t, _)| t.max_a < a),
None => lf.first,
}
}
}
}
pub fn first_min_gt(&self, a: u32) -> usize {
match self {
TileList::Full(v) => v.partition_point(|t| t.min_a <= a),
TileList::Deferred(d) => d.get().partition_point(|t| t.min_a <= a),
TileList::Leafed(l) => {
let next = l.leaves.partition_point(|lf| lf.min_a <= a);
if next == 0 {
return 0;
}
let li = next - 1;
let lf = &l.leaves[li];
l.ensure_leaves(&[li]);
match l.cells[li].get() {
Some(v) => lf.first + v.partition_point(|(t, _)| t.min_a <= a),
None => lf.first,
}
}
}
}
pub(crate) fn first_max_ge_in(&self, a: u32, lo: usize, hi: usize) -> usize {
if lo >= hi {
return lo;
}
match self {
TileList::Full(v) => lo + v[lo..hi].partition_point(|t| t.max_a < a),
TileList::Deferred(d) => lo + d.get()[lo..hi].partition_point(|t| t.max_a < a),
TileList::Leafed(l) => {
let (l0, l1) = (l.leaf_of(lo), l.leaf_of(hi - 1) + 1);
let li = l0 + l.leaves[l0..l1].partition_point(|lf| lf.max_a < a);
if li >= l1 {
return hi;
}
let lf = &l.leaves[li];
l.ensure_leaves(&[li]);
match l.cells[li].get() {
Some(v) => lf.first + v.partition_point(|(t, _)| t.max_a < a),
None => lf.first,
}
}
}
}
pub(crate) fn first_min_gt_in(&self, a: u32, lo: usize, hi: usize) -> usize {
if lo >= hi {
return lo;
}
match self {
TileList::Full(v) => lo + v[lo..hi].partition_point(|t| t.min_a <= a),
TileList::Deferred(d) => lo + d.get()[lo..hi].partition_point(|t| t.min_a <= a),
TileList::Leafed(l) => {
let (l0, l1) = (l.leaf_of(lo), l.leaf_of(hi - 1) + 1);
let next = l0 + l.leaves[l0..l1].partition_point(|lf| lf.min_a <= a);
if next == l0 {
return lo;
}
let li = next - 1;
let lf = &l.leaves[li];
l.ensure_leaves(&[li]);
match l.cells[li].get() {
Some(v) => lf.first + v.partition_point(|(t, _)| t.min_a <= a),
None => lf.first,
}
}
}
}
pub(crate) fn leaves_for_in(&self, a: u32, lo: usize, hi: usize) -> Vec<usize> {
let TileList::Leafed(l) = self else {
return Vec::new();
};
if lo >= hi {
return Vec::new();
}
let (l0, l1) = (l.leaf_of(lo), l.leaf_of(hi - 1) + 1);
let mut out = Vec::new();
let li = l0 + l.leaves[l0..l1].partition_point(|lf| lf.max_a < a);
if li < l1 {
out.push(li);
}
let next = l0 + l.leaves[l0..l1].partition_point(|lf| lf.min_a <= a);
if next > l0 && !out.contains(&(next - 1)) {
out.push(next - 1);
}
out
}
pub fn total_bytes(&self) -> u64 {
match self {
TileList::Full(v) => v.iter().map(Tile::encoded_len).sum(),
TileList::Deferred(d) => d.get().iter().map(Tile::encoded_len).sum(),
TileList::Leafed(l) => l.total_bytes,
}
}
pub fn routed_bytes(&self, a: u32) -> u64 {
match self {
TileList::Full(v) => v
.iter()
.filter(|t| t.min_a <= a && a <= t.max_a)
.map(Tile::encoded_len)
.sum(),
TileList::Deferred(d) => match d.cell.get() {
Some(v) => v
.iter()
.filter(|t| t.min_a <= a && a <= t.max_a)
.map(Tile::encoded_len)
.sum(),
None => d.approx_bytes,
},
TileList::Leafed(l) => {
let lis: Vec<usize> = l
.leaves
.iter()
.enumerate()
.filter(|(_, lf)| lf.min_a <= a && a <= lf.max_a)
.map(|(i, _)| i)
.collect();
if lis.is_empty() {
return 0;
}
if lis.iter().all(|&li| l.cells[li].get().is_some()) {
lis.iter()
.flat_map(|&li| l.cells[li].get().into_iter().flat_map(|v| v.iter()))
.filter(|(t, _)| t.min_a <= a && a <= t.max_a)
.map(|(t, _)| t.encoded_len())
.sum()
} else {
let mean = l.total_bytes as f64 / l.total.max(1) as f64;
(l.admitted_unfaulted(a).max(1.0) * mean) as u64
}
}
}
}
pub fn resident_at(&self, ti: usize) -> bool {
match self {
TileList::Full(_) => true,
TileList::Deferred(d) => d.cell.get().is_some(),
TileList::Leafed(l) => ti < l.total && l.cells[l.leaf_of(ti)].get().is_some(),
}
}
pub fn range(&self, ti: usize) -> Option<(u64, u64)> {
match self {
TileList::Full(_) | TileList::Deferred(_) => None,
TileList::Leafed(l) => l.range(ti),
}
}
fn load_failed(&self) -> bool {
match self {
TileList::Leafed(l) => l.load_failed(),
TileList::Deferred(d) => d.failed.load(std::sync::atomic::Ordering::Relaxed),
TileList::Full(_) => false,
}
}
fn reset_load_failure(&self) {
match self {
TileList::Leafed(l) => l.reset_load_failure(),
TileList::Deferred(d) => d.failed.store(false, std::sync::atomic::Ordering::Relaxed),
TileList::Full(_) => {}
}
}
fn directory_bytes(&self) -> u64 {
match self {
TileList::Full(v) => (v.capacity() * std::mem::size_of::<Tile>()) as u64,
TileList::Deferred(d) => d
.cell
.get()
.map_or(0, |v| (v.capacity() * std::mem::size_of::<Tile>()) as u64),
TileList::Leafed(l) => l.resident_bytes(),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ScanPlan {
pub permutation: IndexPermutation,
pub tiles_total: usize,
pub tiles_routed: usize,
pub tiles_admitted: usize,
pub tile_bytes: u64,
pub section_bytes: u64,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum IndexPermutation {
Spo,
Sop,
Pso,
Pos,
Osp,
Ops,
}
pub(crate) const NUM_PERMS: usize = 6;
pub(crate) const ALL_PERMS: [IndexPermutation; NUM_PERMS] = [
IndexPermutation::Spo,
IndexPermutation::Pos,
IndexPermutation::Osp,
IndexPermutation::Sop,
IndexPermutation::Pso,
IndexPermutation::Ops,
];
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct PermSet(u8);
impl Default for PermSet {
fn default() -> Self {
PermSet::ALL
}
}
impl PermSet {
pub const ALL: PermSet = PermSet(0b0011_1111);
pub const CORE: PermSet = PermSet(0b0000_0111);
pub fn from_bits(bits: u8) -> Result<PermSet, &'static str> {
if bits & !PermSet::ALL.0 != 0 {
return Err("permutation mask addresses more than six permutations");
}
if bits & PermSet::CORE.0 != PermSet::CORE.0 {
return Err("permutation mask must contain SPO, POS and OSP");
}
Ok(PermSet(bits))
}
pub fn bits(self) -> u8 {
self.0
}
pub fn contains(self, perm: IndexPermutation) -> bool {
self.0 & (1 << perm.section_index()) != 0
}
pub fn len(self) -> usize {
self.0.count_ones() as usize
}
pub fn is_empty(self) -> bool {
false
}
pub fn iter(self) -> impl Iterator<Item = IndexPermutation> {
ALL_PERMS.into_iter().filter(move |p| self.contains(*p))
}
pub fn position(self, perm: IndexPermutation) -> Option<usize> {
self.contains(perm)
.then(|| (self.0 & ((1u8 << perm.section_index()) - 1)).count_ones() as usize)
}
pub fn names(self) -> Vec<&'static str> {
self.iter().map(|p| p.name()).collect()
}
pub fn has_merge_orders(self) -> bool {
self == PermSet::ALL
}
}
impl IndexPermutation {
pub fn name(self) -> &'static str {
match self {
IndexPermutation::Spo => "SPO",
IndexPermutation::Sop => "SOP",
IndexPermutation::Pso => "PSO",
IndexPermutation::Pos => "POS",
IndexPermutation::Osp => "OSP",
IndexPermutation::Ops => "OPS",
}
}
pub fn section_index(self) -> usize {
match self {
IndexPermutation::Spo => 0,
IndexPermutation::Pos => 1,
IndexPermutation::Osp => 2,
IndexPermutation::Sop => 3,
IndexPermutation::Pso => 4,
IndexPermutation::Ops => 5,
}
}
pub(crate) const fn roles(self) -> [usize; 3] {
match self {
IndexPermutation::Spo => [0, 1, 2],
IndexPermutation::Sop => [0, 2, 1],
IndexPermutation::Pso => [1, 0, 2],
IndexPermutation::Pos => [1, 2, 0],
IndexPermutation::Osp => [2, 0, 1],
IndexPermutation::Ops => [2, 1, 0],
}
}
pub(crate) fn forward(self, t: Triple) -> Triple {
let c = [t.0, t.1, t.2];
let r = self.roles();
(c[r[0]], c[r[1]], c[r[2]])
}
pub(crate) fn back(self, abc: Triple) -> Triple {
let a = [abc.0, abc.1, abc.2];
let r = self.roles();
let mut out = [0u32; 3];
out[r[0]] = a[0];
out[r[1]] = a[1];
out[r[2]] = a[2];
(out[0], out[1], out[2])
}
pub(crate) fn order_pattern(self, p: Pattern) -> [Option<u32>; 3] {
let c = [p.0, p.1, p.2];
let r = self.roles();
[c[r[0]], c[r[1]], c[r[2]]]
}
fn leading_bound(self, pat: Pattern) -> usize {
self.order_pattern(pat)
.iter()
.take_while(|c| c.is_some())
.count()
}
}
pub struct GraphIndexBuilder {
triples: Vec<Triple>,
tile_budget: usize,
perms: PermSet,
progress: bool,
}
impl Default for GraphIndexBuilder {
fn default() -> Self {
Self {
triples: Vec::new(),
tile_budget: crate::write_opts::tile_budget(),
perms: PermSet::ALL,
progress: false,
}
}
}
impl GraphIndexBuilder {
pub fn new() -> Self {
Self::default()
}
pub fn from_triples(triples: Vec<Triple>) -> Self {
Self {
triples,
..Self::default()
}
}
pub fn with_tile_budget(mut self, bytes: usize) -> Self {
self.tile_budget = bytes.max(1);
self
}
pub fn with_perms(mut self, perms: PermSet) -> Self {
self.perms = perms;
self
}
pub(crate) fn with_progress(mut self) -> Self {
self.progress = true;
self
}
pub fn push(&mut self, t: Triple) {
self.triples.push(t);
}
pub fn build_seq(self) -> GraphIndex {
let triples = &self.triples;
let budget = self.tile_budget;
let progress = self.progress;
let wanted: Vec<IndexPermutation> = self.perms.iter().collect();
let build_one = |perm: IndexPermutation| -> Vec<Tile> {
#[cfg(feature = "parallel")]
let permuted: Vec<Triple> = {
use rayon::prelude::*;
triples.par_iter().map(|&t| perm.forward(t)).collect()
};
#[cfg(not(feature = "parallel"))]
let permuted: Vec<Triple> = triples.iter().map(|&t| perm.forward(t)).collect();
let tiles = build_tiles(permuted, budget);
if progress {
crate::build_progress::advance(triples.len() as u64);
}
tiles
};
#[cfg(feature = "parallel")]
let built: Vec<Vec<Tile>> = {
use rayon::prelude::*;
let mut built: Vec<Vec<Tile>> = Vec::with_capacity(wanted.len());
for chunk in wanted.chunks(2) {
built.extend(
chunk
.to_vec()
.into_par_iter()
.map(build_one)
.collect::<Vec<_>>(),
);
}
built
};
#[cfg(not(feature = "parallel"))]
let built: Vec<Vec<Tile>> = wanted.iter().copied().map(build_one).collect();
GraphIndex::from_sections(scatter(&wanted, built), self.perms)
}
pub fn build(self) -> GraphIndex {
let wanted: Vec<IndexPermutation> = self.perms.iter().collect();
let triples = &self.triples;
let budget = self.tile_budget;
let progress = self.progress;
let build_one = move |perm: IndexPermutation| -> Vec<Tile> {
let permuted: Vec<Triple> = triples.iter().map(|&t| perm.forward(t)).collect();
let tiles = build_tiles(permuted, budget);
if progress {
crate::build_progress::advance(triples.len() as u64);
}
tiles
};
#[cfg(feature = "parallel")]
let built: Vec<Vec<Tile>> = {
use rayon::iter::{IntoParallelIterator, ParallelIterator};
wanted.clone().into_par_iter().map(build_one).collect()
};
#[cfg(not(feature = "parallel"))]
let built: Vec<Vec<Tile>> = wanted.iter().copied().map(build_one).collect();
GraphIndex::from_sections(scatter(&wanted, built), self.perms)
}
}
fn scatter(wanted: &[IndexPermutation], built: Vec<Vec<Tile>>) -> [Vec<Tile>; NUM_PERMS] {
let mut sections: [Vec<Tile>; NUM_PERMS] = Default::default();
for (perm, tiles) in wanted.iter().zip(built) {
sections[perm.section_index()] = tiles;
}
sections
}
fn varint_len(mut v: u64) -> usize {
let mut n = 1;
while v >= 0x80 {
v >>= 7;
n += 1;
}
n
}
pub(crate) struct GroupSizer {
size: usize,
num_b: u64,
cur_b: u32,
num_c: u64,
prev_c: u32,
empty: bool,
}
impl GroupSizer {
pub(crate) fn start(a: u32, prev_a: u32) -> Self {
GroupSizer {
size: varint_len((a - prev_a) as u64),
num_b: 0,
cur_b: 0,
num_c: 0,
prev_c: 0,
empty: true,
}
}
pub(crate) fn push(&mut self, b: u32, c: u32) -> usize {
if self.empty || b != self.cur_b {
if self.empty {
self.size += varint_len(b as u64); } else {
self.size += varint_len(self.num_c); self.size += varint_len((b - self.cur_b) as u64);
}
self.cur_b = b;
self.num_c = 0;
self.prev_c = 0;
self.num_b += 1;
self.empty = false;
}
self.size += varint_len((c - self.prev_c) as u64);
self.prev_c = c;
self.num_c += 1;
self.total()
}
pub(crate) fn total(&self) -> usize {
self.size
+ if self.empty {
0
} else {
varint_len(self.num_c)
}
+ varint_len(self.num_b)
}
}
fn build_tiles(mut triples: Vec<Triple>, budget: usize) -> Vec<Tile> {
#[cfg(feature = "parallel")]
{
use rayon::slice::ParallelSliceMut;
triples.par_sort_unstable();
}
#[cfg(not(feature = "parallel"))]
triples.sort_unstable();
triples.dedup();
if triples.is_empty() {
return Vec::new();
}
let make_tile = |run: &[Triple]| -> Tile {
let mut b = TripleBlockBuilder::new();
for &t in run {
b.push(t);
}
Tile::local(run[0].0, run[run.len() - 1].0, b.build())
};
let mut tiles = Vec::new();
let mut tile_start = 0usize;
let mut tile_size = 0usize; let mut prev_a = 0u32;
let mut i = 0usize;
while i < triples.len() {
let a = triples[i].0;
let mut slice_start = i; let mut sizer = GroupSizer::start(a, prev_a);
let mut gtotal = 0usize;
while i < triples.len() && triples[i].0 == a {
gtotal = sizer.push(triples[i].1, triples[i].2);
i += 1;
if gtotal > budget {
tiles.push(make_tile(&triples[tile_start..i]));
tile_start = i;
tile_size = 0;
prev_a = a;
slice_start = i;
sizer = GroupSizer::start(a, a);
gtotal = 0;
}
}
if slice_start == i {
continue; }
if slice_start > tile_start && tile_size + gtotal > budget {
tiles.push(make_tile(&triples[tile_start..slice_start]));
tile_start = slice_start;
tile_size = 0;
}
tile_size += gtotal;
prev_a = a;
}
if tile_start < triples.len() {
tiles.push(make_tile(&triples[tile_start..]));
}
tiles
}
pub struct GraphIndex {
pub(crate) sections: [TileList; NUM_PERMS],
perms: PermSet,
loader: Option<TileLoader>,
bulk: Option<TileBulkLoader>,
scattered: Option<TileBulkLoader>,
load_failed: std::sync::atomic::AtomicBool,
read_concurrency: usize,
cache: Arc<ChunkCache>,
size_hint: std::sync::atomic::AtomicU64,
clusters: [Option<Arc<ClusterRuns>>; NUM_PERMS],
pub(crate) union: Option<Box<crate::union_scan::UnionOverlay>>,
}
pub(crate) enum Either<A, B> {
Plain(A),
Union(B),
}
impl<A: Iterator<Item = Triple>, B: Iterator<Item = Triple>> Iterator for Either<A, B> {
type Item = Triple;
#[inline]
fn next(&mut self) -> Option<Triple> {
match self {
Either::Plain(a) => a.next(),
Either::Union(b) => b.next(),
}
}
}
impl GraphIndex {
fn from_sections(mut sections: [Vec<Tile>; NUM_PERMS], perms: PermSet) -> Self {
let cache = ChunkCache::unlimited_arc();
for (si, tiles) in sections.iter_mut().enumerate() {
for (ti, tile) in tiles.iter_mut().enumerate() {
if let Some(body) = tile.staged.take() {
cache.insert((si as u8, ti as u32), Arc::from(body));
}
}
}
GraphIndex {
sections: sections.map(TileList::Full),
perms,
loader: None,
bulk: None,
scattered: None,
load_failed: std::sync::atomic::AtomicBool::new(false),
read_concurrency: 1,
cache,
size_hint: std::sync::atomic::AtomicU64::new(0),
clusters: Default::default(),
union: None,
}
}
pub(crate) fn empty_with(perms: PermSet) -> Self {
Self::from_sections(Default::default(), perms)
}
pub fn from_tiles(sections: [Vec<(u32, u32, Vec<u8>)>; NUM_PERMS], perms: PermSet) -> Self {
let sections = sections.map(|tiles| {
tiles
.into_iter()
.map(|(min_a, max_a, bytes)| Tile::local(min_a, max_a, bytes))
.collect()
});
Self::from_sections(sections, perms)
}
pub fn perms(&self) -> PermSet {
self.perms
}
pub fn set_cache_cap(&self, cap: u64) {
self.cache.set_cap(cap);
}
pub fn cache_cap(&self) -> u64 {
self.cache.cap()
}
pub fn is_lazy(&self) -> bool {
self.loader.is_some()
}
pub fn cache_stats(&self) -> crate::chunk_cache::CacheStats {
self.cache.stats()
}
pub fn directory_bytes(&self) -> u64 {
let tiles: u64 = self.sections.iter().map(|s| s.known_len() as u64).sum();
let caps: u64 = self.sections.iter().map(TileList::directory_bytes).sum();
let ranges = if self.loader.is_some() {
2 * 24 * tiles
} else {
0
};
caps + ranges
}
#[allow(clippy::type_complexity)]
pub fn from_remote_directories(
directories: [Vec<(u32, u32, Option<(u32, u32, u32, u32)>)>; NUM_PERMS],
perms: PermSet,
loader: TileLoader,
) -> Self {
let sections = directories.map(|dir| {
TileList::Full(
dir.into_iter()
.map(|(min_a, max_a, syn)| Tile::remote(min_a, max_a, syn))
.collect(),
)
});
GraphIndex {
sections,
perms,
loader: Some(loader),
bulk: None,
scattered: None,
load_failed: std::sync::atomic::AtomicBool::new(false),
read_concurrency: 1,
cache: ChunkCache::unlimited_arc(),
size_hint: std::sync::atomic::AtomicU64::new(0),
clusters: Default::default(),
union: None,
}
}
pub fn from_remote_deferred(
lists: [Option<Arc<DeferredTiles>>; NUM_PERMS],
perms: PermSet,
loader: TileLoader,
) -> Self {
GraphIndex {
sections: lists.map(|l| match l {
Some(l) => TileList::Deferred(l),
None => TileList::Full(Vec::new()),
}),
perms,
loader: Some(loader),
bulk: None,
scattered: None,
load_failed: std::sync::atomic::AtomicBool::new(false),
read_concurrency: 1,
cache: ChunkCache::unlimited_arc(),
size_hint: std::sync::atomic::AtomicU64::new(0),
clusters: Default::default(),
union: None,
}
}
pub fn with_bulk_loader(mut self, bulk: TileBulkLoader) -> Self {
self.bulk = Some(bulk);
self
}
pub fn with_scattered_loader(mut self, scattered: TileBulkLoader) -> Self {
self.scattered = Some(scattered);
self
}
pub(crate) fn set_tile_lens(&mut self, lens: [Vec<u32>; NUM_PERMS]) {
for (section, ls) in self.sections.iter_mut().zip(lens) {
if let TileList::Full(section) = section {
for (tile, l) in section.iter_mut().zip(ls) {
tile.len = l;
}
}
}
}
pub(crate) fn set_read_concurrency(&mut self, c: usize) {
self.read_concurrency = c.max(1);
}
pub(crate) fn set_size_hint(&self, triples: u64) {
self.size_hint
.store(triples, std::sync::atomic::Ordering::Relaxed);
}
pub(crate) fn size_hint(&self) -> Option<u64> {
match self.size_hint.load(std::sync::atomic::Ordering::Relaxed) {
0 => None,
n => Some(n),
}
}
pub(crate) fn read_concurrency(&self) -> usize {
if let Some(u) = &self.union {
return u.read_concurrency();
}
self.read_concurrency
}
pub fn load_incomplete(&self) -> bool {
self.load_failed.load(std::sync::atomic::Ordering::Relaxed)
|| self.sections.iter().any(TileList::load_failed)
}
pub fn reset_load_failure(&self) {
self.load_failed
.store(false, std::sync::atomic::Ordering::Relaxed);
for s in &self.sections {
s.reset_load_failure();
}
}
pub fn is_remote(&self) -> bool {
if let Some(u) = &self.union {
return u.is_remote();
}
self.loader.is_some()
}
pub(crate) fn prefault_leaves(&self, patterns: &[Pattern]) {
let mut want: [std::collections::BTreeSet<usize>; NUM_PERMS] = Default::default();
let mut subjects: [Vec<u32>; NUM_PERMS] = Default::default();
for &pat in patterns {
let perm = Self::best_permutation_in(self.perms, pat);
let [pa, _, _] = perm.order_pattern(pat);
let si = perm.section_index();
if self.clusters[si].is_some() {
subjects[si].extend(pa);
continue;
}
if let (TileList::Leafed(l), Some(a)) = (&self.sections[si], pa) {
let from = l.leaves.partition_point(|lf| lf.max_a < a);
for (li, lf) in l.leaves.iter().enumerate().skip(from) {
if lf.min_a > a {
break;
}
want[si].insert(li);
}
}
}
for (si, lis) in want.iter().enumerate() {
if let TileList::Leafed(l) = &self.sections[si] {
if !lis.is_empty() {
l.ensure_leaves(&lis.iter().copied().collect::<Vec<_>>());
}
}
}
for (si, a) in subjects.iter().enumerate() {
if !a.is_empty() {
self.resolve_batch(si, a);
}
}
}
pub fn tile_range(&self, section: usize, tile: usize) -> Option<(u64, u64)> {
self.sections.get(section)?.range(tile)
}
pub fn from_leafed(
lists: [Option<Arc<LeafedTiles>>; NUM_PERMS],
perms: PermSet,
loader: TileLoader,
) -> Self {
GraphIndex {
sections: lists.map(|l| match l {
Some(l) => TileList::Leafed(l),
None => TileList::Full(Vec::new()),
}),
perms,
loader: Some(loader),
bulk: None,
scattered: None,
load_failed: std::sync::atomic::AtomicBool::new(false),
read_concurrency: 1,
cache: ChunkCache::unlimited_arc(),
size_hint: std::sync::atomic::AtomicU64::new(0),
clusters: Default::default(),
union: None,
}
}
pub fn with_clusters(mut self, si: usize, runs: ClusterRuns) -> Self {
self.clusters[si] = Some(Arc::new(runs));
self
}
pub fn cluster_runs(&self, si: usize) -> Option<&ClusterRuns> {
self.clusters.get(si)?.as_deref()
}
pub(crate) fn clustered_subject_bytes(&self, si: usize) -> u64 {
let t = &self.sections[si];
t.total_bytes() / t.len().max(1) as u64
}
fn run_span(&self, si: usize, run: usize, a: u32) -> (usize, usize) {
let Some(cr) = &self.clusters[si] else {
return (0, 0);
};
let (lo, hi) = cr.runs[run];
let t = &self.sections[si];
let i = t.first_max_ge_in(a, lo, hi);
let j = t.first_min_gt_in(a, lo, hi).max(i);
(i, j)
}
fn tile_holds(&self, si: usize, ti: usize, a: u32) -> bool {
let Some(entry) = self.tile_entry(si, ti) else {
return false;
};
let Ok(block) = TripleBlock::parse(entry.body()) else {
return false;
};
self.tile_dir(si, ti, &entry, &block).first_at_or_after(a) == Some(a)
}
fn find_in_runs(&self, si: usize, subjects: &[u32], order: &[usize]) -> Vec<Option<usize>> {
let Some(cr) = &self.clusters[si] else {
return vec![None; subjects.len()];
};
let t = &self.sections[si];
if let TileList::Leafed(l) = t {
let mut lis: Vec<usize> = Vec::new();
for &a in subjects {
for &r in order {
let (lo, hi) = cr.runs[r];
lis.extend(t.leaves_for_in(a, lo, hi));
}
}
lis.sort_unstable();
lis.dedup();
l.ensure_leaves(&lis);
}
let spans: Vec<Vec<(usize, (usize, usize))>> = subjects
.iter()
.map(|&a| {
order
.iter()
.map(|&r| (r, self.run_span(si, r, a)))
.filter(|(_, (i, j))| i < j)
.collect()
})
.collect();
if self.is_remote() {
let mut missing: Vec<usize> = spans
.iter()
.flatten()
.flat_map(|(_, (i, j))| *i..*j)
.filter(|&ti| !self.tile_resident(si, ti))
.collect();
missing.sort_unstable();
missing.dedup();
self.bulk_fault(si, &missing);
}
subjects
.iter()
.zip(&spans)
.map(|(&a, cands)| {
cands
.iter()
.find(|(_, (i, j))| (*i..*j).any(|ti| self.tile_holds(si, ti, a)))
.map(|&(r, _)| r)
})
.collect()
}
fn resolve_run(&self, si: usize, a: u32) -> Option<usize> {
let cr = self.clusters[si].as_ref()?;
if let Some(known) = cr.recall(a) {
return known;
}
let hint = cr.hint.load(std::sync::atomic::Ordering::Relaxed);
let mut found = self.find_in_runs(si, &[a], &[hint])[0];
if found.is_none() {
let rest: Vec<usize> = (0..cr.runs.len()).filter(|&r| r != hint).collect();
found = self.find_in_runs(si, &[a], &rest)[0];
}
if found.is_some() || !self.load_incomplete() {
cr.remember(a, found);
}
found
}
fn resolve_batch(&self, si: usize, subjects: &[u32]) {
let Some(cr) = self.clusters[si].as_ref() else {
return;
};
let mut todo: Vec<u32> = subjects
.iter()
.copied()
.filter(|&a| cr.recall(a).is_none())
.collect();
todo.sort_unstable();
todo.dedup();
let Some(&first) = todo.first() else {
return;
};
let _ = self.resolve_run(si, first);
let hint = cr.hint.load(std::sync::atomic::Ordering::Relaxed);
let rest: Vec<u32> = todo[1..]
.iter()
.copied()
.filter(|&a| cr.recall(a).is_none())
.collect();
let guessed = self.find_in_runs(si, &rest, &[hint]);
let mut missed: Vec<u32> = Vec::new();
for (&a, g) in rest.iter().zip(guessed) {
match g {
Some(r) => cr.remember(a, Some(r)),
None => missed.push(a),
}
}
if missed.is_empty() {
return;
}
let others: Vec<usize> = (0..cr.runs.len()).filter(|&r| r != hint).collect();
let found = self.find_in_runs(si, &missed, &others);
if !self.load_incomplete() {
for (&a, f) in missed.iter().zip(found) {
cr.remember(a, f);
}
}
}
pub(crate) fn leading_bounds(&self, si: usize) -> Option<(u32, u32)> {
let t = &self.sections[si];
let ranges: Vec<(usize, usize)> = match &self.clusters[si] {
Some(cr) => cr.runs.clone(),
None => vec![(0, t.len())],
};
let mut out: Option<(u32, u32)> = None;
for (lo, hi) in ranges.into_iter().filter(|(l, h)| l < h) {
let (a, b) = (t[lo].leading_range().0, t[hi - 1].leading_range().1);
out = Some(out.map_or((a, b), |(x, y)| (x.min(a), y.max(b))));
}
out
}
pub(crate) fn next_tile_start(&self, si: usize, sid: u32) -> Option<u32> {
let t = &self.sections[si];
let ranges: Vec<(usize, usize)> = match &self.clusters[si] {
Some(cr) => cr.runs.clone(),
None => vec![(0, t.len())],
};
let mut best: Option<u32> = None;
for (lo, hi) in ranges {
let i = t.first_max_ge_in(sid, lo, hi);
if i < hi {
let x = t[i].leading_range().0.max(sid);
best = Some(best.map_or(x, |b| b.min(x)));
}
}
best
}
pub(crate) fn routed_spans(&self, si: usize, pa: Option<u32>) -> Vec<(usize, usize)> {
match (&self.clusters[si], pa) {
(Some(cr), Some(a)) => {
let spans: Vec<(usize, usize)> = (0..cr.runs.len())
.map(|r| self.run_span(si, r, a))
.filter(|(i, j)| i < j)
.collect();
for &(i, j) in &spans {
self.sections[si].ensure_span(i, j);
}
spans
}
_ => vec![self.tile_span(si, pa)],
}
}
fn prefetch_span(&self, section: usize, start: usize, end: usize) {
let missing: Vec<usize> = (start..end)
.filter(|&ti| !self.tile_resident(section, ti))
.collect();
self.bulk_fault(section, &missing);
}
fn tile_resident(&self, section: usize, tile: usize) -> bool {
self.cache.contains((section as u8, tile as u32))
}
fn bulk_fault(&self, section: usize, tiles: &[usize]) {
self.fault_with(self.bulk.as_ref(), section, tiles);
}
fn fault_with(&self, loader: Option<&TileBulkLoader>, section: usize, tiles: &[usize]) {
if tiles.len() < 2 {
return;
}
let Some(bulk) = loader else { return };
if let Some(images) = bulk(section, tiles) {
if images.len() == tiles.len() {
for (&ti, img) in tiles.iter().zip(images) {
self.cache
.insert((section as u8, ti as u32), Arc::from(img));
}
}
}
}
pub(crate) fn prefetch_probe_tiles(&self, patterns: &[Pattern]) -> usize {
if self.bulk.is_none() {
return patterns.len();
}
self.prefault_leaves(patterns);
let mut batch = ProbeBatch::default();
let mut covered = 0;
for &pat in patterns {
if !self.probe_batch_add(&mut batch, pat) {
break;
}
covered += 1;
}
self.probe_batch_fault(batch);
covered
}
pub(crate) fn probe_batch_add(&self, batch: &mut ProbeBatch, pat: Pattern) -> bool {
let perm = Self::best_permutation(pat);
let [pa, pb, pc] = perm.order_pattern(pat);
let si = perm.section_index();
let (start, end) = self.tile_span(si, pa);
let mut fresh: Vec<usize> = Vec::new();
for ti in start..end {
if self.sections[si][ti].syn_admits(pb, pc)
&& !self.tile_resident(si, ti)
&& !batch.want[si].contains(&ti)
{
fresh.push(ti);
}
}
let fresh_bytes: u64 = fresh
.iter()
.map(|&ti| self.sections[si][ti].len as u64)
.sum();
if batch.tiles + fresh.len() > PROBE_WINDOW_TILES
|| batch.bytes + fresh_bytes > self.probe_window_bytes()
{
if batch.patterns > 0 {
return false;
}
batch.patterns = 1;
return true;
}
batch.tiles += fresh.len();
batch.bytes += fresh_bytes;
batch.want[si].extend(fresh);
batch.patterns += 1;
true
}
pub(crate) fn probe_batch_fault(&self, batch: ProbeBatch) {
for (si, set) in batch.want.iter().enumerate() {
let tiles: Vec<usize> = set.iter().copied().collect();
self.fault_with(self.scattered.as_ref().or(self.bulk.as_ref()), si, &tiles);
}
}
fn probe_window_bytes(&self) -> u64 {
const KIB: u64 = 1 << 10;
match self.cache.cap() {
u64::MAX => 64 * KIB * KIB,
cap => (cap / 8).clamp(256 * KIB, 64 * KIB * KIB),
}
}
fn tile_entry(&self, section: usize, tile: usize) -> Option<Arc<CacheEntry>> {
crate::guard::check();
let key = (section as u8, tile as u32);
if let Some(e) = self.cache.get(key) {
return Some(e);
}
match &self.loader {
Some(load) => match load(section, tile) {
Some(bytes) => Some(self.cache.insert(key, Arc::from(bytes))),
None => {
self.load_failed
.store(true, std::sync::atomic::Ordering::Relaxed);
None
}
},
None => Some(self.cache.insert(key, Arc::from(Vec::new()))),
}
}
fn tile_dir<'e>(
&self,
section: usize,
tile: usize,
entry: &'e Arc<CacheEntry>,
block: &TripleBlock<'_>,
) -> &'e GroupDirectory {
let (dir, built) = entry.group_dir(|| block.group_directory());
if built {
self.cache.charge_extra(
(section as u8, tile as u32),
entry,
dir.heap_bytes() + std::mem::size_of::<GroupDirectory>() as u64,
);
}
dir
}
pub(crate) fn tile_body(&self, section: usize, tile: usize) -> Arc<[u8]> {
self.tile_entry(section, tile)
.map(|e| e.body_arc())
.unwrap_or_else(|| Arc::from(Vec::new()))
}
pub fn triple_count(&self) -> u32 {
if let Some(u) = &self.union {
let perm = IndexPermutation::Spo;
return u.scan((None, None, None), perm, None).0.count() as u32;
}
self.prefetch_span(0, 0, self.sections[0].len());
(0..self.sections[0].len())
.filter_map(|ti| {
let entry = self.tile_entry(0, ti)?;
TripleBlock::parse(entry.body())
.ok()
.map(|b| b.zone().count)
})
.fold(0u32, u32::saturating_add)
}
pub fn for_each_in_order(
&self,
perm: IndexPermutation,
f: &mut dyn FnMut(u32, u32, u32),
) -> bool {
if self.union.is_some() || !self.perms.contains(perm) {
return false;
}
let si = perm.section_index();
let end = self.sections[si].len();
let mut window = PREFETCH_WINDOW_START;
for ti in 0..end {
if !self.tile_resident(si, ti) {
self.prefetch_span(si, ti, (ti + window).min(end));
window = window.saturating_mul(2).min(PREFETCH_WINDOW_MAX);
}
if let Some(entry) = self.tile_entry(si, ti) {
if let Ok(block) = TripleBlock::parse(entry.body()) {
for (a, b, c) in block.scan(None, None, None) {
f(a, b, c);
}
}
}
}
true
}
pub fn tile_sections(&self) -> [&TileList; NUM_PERMS] {
[
&self.sections[0],
&self.sections[1],
&self.sections[2],
&self.sections[3],
&self.sections[4],
&self.sections[5],
]
}
pub fn best_permutation(pattern: Pattern) -> IndexPermutation {
Self::best_permutation_in(PermSet::ALL, pattern)
}
pub fn best_permutation_in(perms: PermSet, pattern: Pattern) -> IndexPermutation {
let mut best = IndexPermutation::Spo;
let mut best_score = best.leading_bound(pattern);
for perm in perms.iter() {
let score = perm.leading_bound(pattern);
if score > best_score {
best = perm;
best_score = score;
}
}
best
}
pub fn permutation_sorted_on(pattern: Pattern, sort_col: usize) -> Option<IndexPermutation> {
Self::permutation_sorted_on_in(PermSet::ALL, pattern, sort_col)
}
pub fn permutation_sorted_on_in(
perms: PermSet,
pattern: Pattern,
sort_col: usize,
) -> Option<IndexPermutation> {
let bound = [
pattern.0.is_some(),
pattern.1.is_some(),
pattern.2.is_some(),
];
if bound[sort_col] {
return None;
}
let routed = Self::best_permutation_in(perms, pattern).leading_bound(pattern);
let mut best: Option<(IndexPermutation, usize)> = None;
for perm in perms.iter() {
let roles = perm.roles();
let lead = perm.leading_bound(pattern);
if lead < 3 && roles[lead] == sort_col && best.map(|(_, s)| lead > s).unwrap_or(true) {
best = Some((perm, lead));
}
}
best.filter(|&(_, lead)| lead >= routed).map(|(p, _)| p)
}
pub fn match_serialized_block(
bytes: &[u8],
permutation: IndexPermutation,
pattern: Pattern,
) -> Vec<Triple> {
let [pa, pb, pc] = permutation.order_pattern(pattern);
let mut out: Vec<Triple> = TripleBlock::parse(bytes)
.ok()
.filter(|b| b.zone().may_contain(pa, pb, pc))
.map(|b| b.scan(pa, pb, pc))
.into_iter()
.flatten()
.map(move |abc| permutation.back(abc))
.collect();
out.sort_unstable();
out
}
pub fn match_pattern(&self, pattern: Pattern) -> Vec<Triple> {
let mut out: Vec<Triple> = self.scan_iter(pattern).collect();
out.sort_unstable();
out
}
pub fn scan_iter(&self, pattern: Pattern) -> impl Iterator<Item = Triple> + '_ {
self.scan_iter_with(
pattern,
Self::best_permutation_in(self.perms, pattern),
None,
)
}
pub(crate) fn scan_iter_cut<'a>(
&'a self,
pattern: Pattern,
cut: &dyn Fn(usize, usize) -> (usize, usize),
) -> impl Iterator<Item = Triple> + 'a {
self.scan_iter_with(
pattern,
Self::best_permutation_in(self.perms, pattern),
Some(cut),
)
}
pub fn scan_plan(&self, pattern: Pattern) -> ScanPlan {
let perm = Self::best_permutation_in(self.perms, pattern);
if let Some(u) = &self.union {
return u.plan(pattern, perm);
}
let [_, pb, pc] = perm.order_pattern(pattern);
let si = perm.section_index();
let tiles = &self.sections[si];
let (start, end) = self.tile_span(si, perm.order_pattern(pattern)[0]);
let mut admitted = 0usize;
let mut tile_bytes = 0u64;
for ti in start..end {
let t = &tiles[ti];
if t.syn_admits(pb, pc) {
admitted += 1;
tile_bytes += t.encoded_len();
}
}
ScanPlan {
permutation: perm,
tiles_total: tiles.len(),
tiles_routed: end - start,
tiles_admitted: admitted,
tile_bytes,
section_bytes: tiles.total_bytes(),
}
}
pub fn scan_batch(
&self,
pattern: Pattern,
cursor: u64,
max_rows: usize,
) -> (Vec<Triple>, u64, bool) {
let max_rows = max_rows.max(1);
let perm = Self::best_permutation(pattern);
if let Some(u) = &self.union {
return u.scan_batch(
pattern,
cursor,
max_rows,
Self::best_permutation_in(self.perms, pattern),
);
}
let [pa, pb, pc] = perm.order_pattern(pattern);
let si = perm.section_index();
let (start, end) = self.tile_span(si, pa);
let mut ti = ((cursor >> 32) as usize).max(start);
let mut from_a = cursor as u32;
let mut out: Vec<Triple> = Vec::new();
let mut window = PREFETCH_WINDOW_START;
while ti < end {
if !self.sections[si][ti].syn_admits(pb, pc) {
ti += 1;
from_a = 0;
continue;
}
if !self.tile_resident(si, ti) {
self.prefetch_span(si, ti, (ti + window).min(end));
window = window.saturating_mul(2).min(PREFETCH_WINDOW_MAX);
}
let entry = self.tile_entry(si, ti);
let mut resume_at: Option<u32> = None;
if let Some(block) = entry
.as_deref()
.and_then(|e| TripleBlock::parse(e.body()).ok())
.filter(|b| b.zone().may_contain(pa, pb, pc))
{
let rows = match pa {
Some(a) => {
let dir = self.tile_dir(si, ti, entry.as_ref().unwrap(), &block);
block.scan_from(dir, a, pb, pc)
}
None if from_a == 0 => block.scan(None, pb, pc),
None => {
let dir = self.tile_dir(si, ti, entry.as_ref().unwrap(), &block);
block.scan_resume(dir, from_a, pb, pc)
}
};
let splittable = pa.is_none();
let mut last_a: Option<u32> = None;
for abc in rows {
if splittable && out.len() >= max_rows && last_a != Some(abc.0) {
resume_at = Some(abc.0);
break;
}
last_a = Some(abc.0);
out.push(perm.back(abc));
}
}
if let Some(a) = resume_at {
out.sort_unstable();
return (out, ((ti as u64) << 32) | a as u64, false);
}
ti += 1;
from_a = 0;
if out.len() >= max_rows {
break;
}
}
let done = ti >= end;
out.sort_unstable();
(out, (ti as u64) << 32, done)
}
pub(crate) fn scan_iter_sorted_on(
&self,
pattern: Pattern,
sort_col: usize,
) -> Option<impl Iterator<Item = Triple> + '_> {
let perm = Self::permutation_sorted_on_in(self.perms, pattern, sort_col)?;
if let Some(u) = &self.union {
if !u.scan_is_ordered(pattern, perm) {
return None;
}
return Some(Either::Union(u.scan(pattern, perm, None).0));
}
if self.clusters[perm.section_index()].is_some() && perm.leading_bound(pattern) == 0 {
return None;
}
Some(Either::Plain(self.scan_plain(pattern, perm, None, None)))
}
fn sorted_route(&self, pattern: Pattern, sort_col: usize) -> Option<(IndexPermutation, usize)> {
if self.union.is_some() {
return None;
}
let perm = Self::permutation_sorted_on_in(self.perms, pattern, sort_col)?;
let lead = perm.leading_bound(pattern);
if self.clusters[perm.section_index()].is_some() && lead == 0 {
return None;
}
Some((perm, lead))
}
pub(crate) fn scan_iter_sorted_between(
&self,
pattern: Pattern,
sort_col: usize,
lo: u32,
hi: u64,
) -> Option<impl Iterator<Item = Triple> + '_> {
let (perm, lead) = self.sorted_route(pattern, sort_col)?;
let key = move |t: &Triple| match sort_col {
0 => t.0,
1 => t.1,
_ => t.2,
};
Some(
self.scan_plain(pattern, perm, None, Some((lead, lo, hi)))
.filter(move |t| {
let v = key(t);
lo <= v && u64::from(v) < hi
}),
)
}
pub(crate) fn sorted_cuts(
&self,
pattern: Pattern,
sort_col: usize,
n: usize,
) -> Option<(Vec<u32>, usize)> {
let (perm, lead) = self.sorted_route(pattern, sort_col)?;
let si = perm.section_index();
let (start, end) = self.tile_span(si, perm.order_pattern(pattern)[0]);
let tiles = end - start;
let mut cuts = Vec::with_capacity(n.saturating_sub(1));
for k in 1..n.max(1) {
let ti = start + (tiles as u128 * k as u128 / n as u128) as usize;
if ti >= end {
break;
}
cuts.push(self.sections[si][ti].column_range(lead)?.0);
}
cuts.sort_unstable();
Some((cuts, tiles))
}
fn scan_iter_with(
&self,
pattern: Pattern,
perm: IndexPermutation,
cut: Option<&dyn Fn(usize, usize) -> (usize, usize)>,
) -> impl Iterator<Item = Triple> + '_ {
if let Some(u) = &self.union {
return Either::Union(u.scan(pattern, perm, cut).0);
}
Either::Plain(self.scan_plain(pattern, perm, cut, None))
}
pub(crate) fn scan_iter_in(
&self,
pattern: Pattern,
perm: IndexPermutation,
cut: Option<&dyn Fn(usize, usize) -> (usize, usize)>,
) -> impl Iterator<Item = Triple> + '_ {
self.scan_iter_with(pattern, perm, cut)
}
pub(crate) fn scan_is_ordered(&self, perm: IndexPermutation, pattern: Pattern) -> bool {
match &self.union {
Some(u) => u.scan_is_ordered(pattern, perm),
None => {
!(self.clusters[perm.section_index()].is_some() && perm.leading_bound(pattern) == 0)
}
}
}
fn scan_plain(
&self,
pattern: Pattern,
perm: IndexPermutation,
cut: Option<&dyn Fn(usize, usize) -> (usize, usize)>,
between: Option<(usize, u32, u64)>,
) -> impl Iterator<Item = Triple> + '_ {
let [pa, pb, pc] = perm.order_pattern(pattern);
let si = perm.section_index();
let (start, end) = self.tile_span(si, pa);
let (start, end) = match cut {
Some(cut) => {
let (lo, hi) = cut(start, end);
let lo = lo.clamp(start, end);
(lo, hi.clamp(lo, end))
}
None => (start, end),
};
let window = std::cell::Cell::new(if cut.is_some() {
PREFETCH_WINDOW_MAX
} else {
PREFETCH_WINDOW_START
});
(start..end)
.filter(move |&ti| {
let t = &self.sections[si][ti];
t.syn_admits(pb, pc)
&& between.is_none_or(|(col, lo, hi)| {
t.column_range(col)
.is_none_or(|(min, max)| max >= lo && u64::from(min) < hi)
})
})
.flat_map(move |ti| {
if !self.tile_resident(si, ti) {
let w = window.get();
self.prefetch_span(si, ti, (ti + w).min(end));
window.set(w.saturating_mul(2).min(PREFETCH_WINDOW_MAX));
}
let rows: Vec<Triple> = self.tile_rows(si, ti, pa, pb, pc).unwrap_or_default();
rows.into_iter()
})
.map(move |abc| perm.back(abc))
}
fn tile_rows(
&self,
si: usize,
ti: usize,
pa: Option<u32>,
pb: Option<u32>,
pc: Option<u32>,
) -> Option<Vec<Triple>> {
let entry = self.tile_entry(si, ti)?;
Some(
TripleBlock::parse(entry.body())
.ok()
.filter(|b| b.zone().may_contain(pa, pb, pc))
.map(|b| match pa {
Some(a) => {
let dir = self.tile_dir(si, ti, &entry, &b);
b.scan_from(dir, a, pb, pc).collect()
}
None => b.scan(pa, pb, pc).collect(),
})
.unwrap_or_default(),
)
}
pub(crate) fn predicate_objects_within(
&self,
p: u32,
covers: impl Fn(u32, u32) -> bool,
max_read: usize,
) -> bool {
if self.union.is_some() {
return false; }
let (perm, object_is_b) = if self.perms.contains(IndexPermutation::Pos) {
(IndexPermutation::Pos, true)
} else if self.perms.contains(IndexPermutation::Pso) {
(IndexPermutation::Pso, false)
} else {
return false;
};
let si = perm.section_index();
let (start, end) = self.tile_span(si, Some(p));
let unproven: Vec<usize> = (start..end)
.filter(|&ti| match self.sections[si][ti].syn {
Some((min_b, max_b, min_c, max_c)) => {
let (lo, hi) = if object_is_b {
(min_b, max_b)
} else {
(min_c, max_c)
};
!covers(lo, hi)
}
None => true,
})
.collect();
if unproven.is_empty() {
return true;
}
if self.is_lazy() {
if unproven.len() > max_read {
return false;
}
let missing: Vec<usize> = unproven
.iter()
.copied()
.filter(|&ti| !self.tile_resident(si, ti))
.collect();
self.bulk_fault(si, &missing);
}
for ti in unproven {
let Some(rows) = self.tile_rows(si, ti, Some(p), None, None) else {
return false;
};
let all = rows.iter().all(|&(_, b, c)| {
let o = if object_is_b { b } else { c };
covers(o, o)
});
if !all {
return false;
}
}
true
}
pub(crate) fn prefault_estimate_leaves(&self, patterns: &[Pattern]) {
let mut want: [std::collections::BTreeSet<usize>; NUM_PERMS] = Default::default();
for &pattern in patterns {
for perm in self.perms.iter() {
let [Some(a), _, _] = perm.order_pattern(pattern) else {
continue;
};
let si = perm.section_index();
if self.clusters[si].is_some() {
continue;
}
if let TileList::Leafed(l) = &self.sections[si] {
want[si].extend(l.run_end_leaves(a));
}
}
}
let wanted: Vec<(usize, Vec<usize>)> = want
.into_iter()
.enumerate()
.filter(|(_, lis)| !lis.is_empty())
.map(|(si, lis)| (si, lis.into_iter().collect()))
.collect();
let across: Vec<(&dyn LeafDir, &[usize])> = wanted
.iter()
.filter_map(|(si, lis)| match &self.sections[*si] {
TileList::Leafed(l) => Some((&**l as &dyn LeafDir, lis.as_slice())),
_ => None,
})
.collect();
ensure_leaves_across(&across);
}
pub(crate) fn estimate_matches(&self, pattern: Pattern, total: u64) -> f64 {
if let Some(u) = &self.union {
return u.estimate(pattern, total);
}
let mut best = total as f64;
for perm in self.perms.iter() {
let [pa, pb, pc] = perm.order_pattern(pattern);
if pa.is_none() {
continue;
}
let si = perm.section_index();
let tiles = &self.sections[si];
if tiles.is_empty() {
return 0.0;
}
let per_tile = total as f64 / tiles.len() as f64;
let admitted = match (tiles, pa) {
(_, Some(_)) if self.clusters[si].is_some() => 1.0,
(TileList::Leafed(l), Some(a))
if !l
.leaves
.iter()
.enumerate()
.filter(|(_, lf)| lf.min_a <= a && a <= lf.max_a)
.all(|(li, _)| l.cells[li].get().is_some()) =>
{
l.admitted_estimate(a, pb, pc)
}
_ => {
let (start, end) = self.tile_span(si, pa);
(start..end)
.filter(|&ti| tiles[ti].syn_admits(pb, pc))
.count() as f64
}
};
let est = if admitted <= 0.0 {
0.0
} else {
(admitted - 0.5).max(0.5) * per_tile
};
best = best.min(est);
}
best
}
pub(crate) fn next_leading(&self, section: usize, a: u32) -> Option<u32> {
if let Some(cr) = &self.clusters[section] {
let mut best: Option<u32> = None;
for &(lo, hi) in &cr.runs {
if let Some(x) = self.next_leading_in(section, a, lo, hi) {
best = Some(best.map_or(x, |b| b.min(x)));
}
}
return best;
}
let n = self.sections[section].len();
self.next_leading_in(section, a, 0, n)
}
fn next_leading_in(&self, section: usize, a: u32, lo: usize, hi: usize) -> Option<u32> {
let tiles = &self.sections[section];
let mut ti = tiles.first_max_ge_in(a, lo, hi);
while ti < hi {
let from = a.max(tiles[ti].min_a);
let entry = self.tile_entry(section, ti)?;
if let Ok(block) = TripleBlock::parse(entry.body()) {
let dir = self.tile_dir(section, ti, &entry, &block);
if let Some(x) = dir.first_at_or_after(from) {
return Some(x);
}
}
ti += 1;
}
None
}
pub(crate) fn tile_span(&self, section: usize, pa: Option<u32>) -> (usize, usize) {
let tiles = &self.sections[section];
match pa {
None => {
tiles.ensure_span(0, tiles.len());
(0, tiles.len())
}
Some(a) if self.clusters[section].is_some() => {
let (i, j) = match self.resolve_run(section, a) {
Some(run) => self.run_span(section, run, a),
None => (0, 0),
};
tiles.ensure_span(i, j);
(i, j)
}
Some(a) => {
let i = tiles.first_max_ge(a);
let j = tiles.first_min_gt(a).max(i);
tiles.ensure_span(i, j);
(i, j)
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn graph() -> (GraphIndex, Vec<Triple>) {
let data = vec![
(1, 10, 100),
(1, 10, 101),
(1, 11, 100),
(2, 10, 100),
(2, 12, 200),
(3, 11, 300),
];
let mut b = GraphIndexBuilder::new();
for &t in &data {
b.push(t);
}
(b.build(), data)
}
fn reference(data: &[Triple], (s, p, o): Pattern) -> Vec<Triple> {
let mut v: Vec<Triple> = data
.iter()
.copied()
.filter(|&(a, b, c)| {
s.is_none_or(|x| x == a) && p.is_none_or(|x| x == b) && o.is_none_or(|x| x == c)
})
.collect();
v.sort_unstable();
v
}
#[test]
fn tile_estimates_rank_patterns_by_size() {
let mut b = GraphIndexBuilder::new().with_tile_budget(256);
let mut n = 0u64;
for s in 0..4000u32 {
b.push((s, 1, 50));
b.push((s, 3, 1000 + s));
n += 2;
if s % 1000 == 0 {
b.push((s, 2, 60));
n += 1;
}
}
let idx = b.build();
let est = |p: Pattern| idx.estimate_matches(p, n);
assert_eq!(est((None, None, None)), n as f64);
assert!(est((None, Some(2), None)) < est((None, Some(1), None)));
assert!(est((None, None, Some(60))) < est((None, None, Some(50))));
assert!(est((Some(7), None, None)) < est((None, Some(3), None)));
let per_tile = n as f64 / idx.tile_sections()[0].len() as f64;
assert!(est((None, Some(2), None)) <= 1.5 * per_tile);
assert!(est((None, Some(1), None)) > 10.0 * per_tile);
assert_eq!(est((Some(99_999), None, None)), 0.0);
let empty = GraphIndexBuilder::new().build();
assert_eq!(empty.estimate_matches((Some(1), None, None), 0), 0.0);
}
#[test]
fn every_pattern_shape_matches_reference() {
let (idx, data) = graph();
let vals = |opts: &[u32]| {
let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
v.push(None);
v
};
for s in vals(&[1, 2, 9]) {
for p in vals(&[10, 11, 99]) {
for o in vals(&[100, 300, 999]) {
let pat = (s, p, o);
assert_eq!(
idx.match_pattern(pat),
reference(&data, pat),
"pattern {pat:?}"
);
let mut streamed: Vec<Triple> = idx.scan_iter(pat).collect();
streamed.sort_unstable();
assert_eq!(streamed, reference(&data, pat), "scan_iter {pat:?}");
}
}
}
}
#[test]
fn unbound_returns_everything_sorted() {
let (idx, data) = graph();
let mut sorted = data.clone();
sorted.sort_unstable();
assert_eq!(idx.match_pattern((None, None, None)), sorted);
}
#[test]
fn multi_tile_sections_match_reference_every_shape() {
let mut data: Vec<Triple> = Vec::new();
for s in 1..=40u32 {
for p in [10u32, 11] {
for o in [100u32, 100 + s] {
data.push((s, p, o));
}
}
}
for budget in [1usize, 16, 64, 1 << 20] {
let mut b = GraphIndexBuilder::new().with_tile_budget(budget);
for &t in &data {
b.push(t);
}
let idx = b.build();
let spo_tiles = idx.tile_sections()[0].len();
if budget <= 16 {
assert!(spo_tiles > 1, "budget {budget} should force tiling");
}
for w in idx.tile_sections()[0].as_full().unwrap().windows(2) {
assert!(w[0].leading_range().1 <= w[1].leading_range().0);
}
assert_eq!(idx.triple_count() as usize, data.len(), "budget {budget}");
let vals = |opts: &[u32]| {
let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
v.push(None);
v
};
for _round in 0..2 {
for s in vals(&[1, 20, 40, 99]) {
for p in vals(&[10, 11, 99]) {
for o in vals(&[100, 120, 999]) {
let pat = (s, p, o);
assert_eq!(
idx.match_pattern(pat),
reference(&data, pat),
"budget {budget} pattern {pat:?}"
);
}
}
}
}
}
}
#[test]
fn mega_group_splits_across_tiles_and_lookups_stay_complete() {
let hot_p = 7u32;
let mut data: Vec<Triple> = Vec::new();
for i in 0..40_000u32 {
data.push((1_000 + i % 200, hot_p, 50_000 + i));
}
data.push((1, 1, 1));
data.push((2, 2, 2));
let mut b = GraphIndexBuilder::new(); for &t in &data {
b.push(t);
}
let idx = b.build();
let pso = ALL_PERMS
.iter()
.position(|p| matches!(p, IndexPermutation::Pso))
.unwrap();
let covering = idx.tile_sections()[pso]
.iter()
.filter(|t| {
let (lo, hi) = t.leading_range();
lo <= hot_p && hot_p <= hi
})
.count();
assert!(
covering > 1,
"expected the hot predicate split across tiles, got {covering}"
);
for pat in [
(None, Some(hot_p), None),
(Some(1_050), Some(hot_p), None),
(None, Some(hot_p), Some(50_123)), (None, Some(hot_p), Some(70_000)), (None, Some(hot_p), Some(89_999)), (None, Some(hot_p), Some(49_000)), (None, Some(hot_p), Some(95_000)), ] {
assert_eq!(idx.match_pattern(pat), reference(&data, pat), "{pat:?}");
}
}
#[test]
fn directory_backed_scans_match_reference_every_shape() {
let (idx, data) = graph();
let vals = |opts: &[u32]| {
let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
v.push(None);
v
};
for round in 0..3 {
for s in vals(&[1, 2, 3, 0, 9]) {
for p in vals(&[10, 11, 12, 99]) {
for o in vals(&[100, 200, 300, 999]) {
let pat = (s, p, o);
let mut got: Vec<Triple> = idx.scan_iter(pat).collect();
got.sort_unstable();
assert_eq!(got, reference(&data, pat), "round {round} scan {pat:?}");
}
}
}
}
}
#[test]
fn synopsis_prunes_the_routed_tile_before_fetch() {
use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
use std::sync::Arc;
let block = {
let mut b = TripleBlockBuilder::new();
b.push((5, 10, 100));
b.push((5, 11, 100));
b.build()
};
let fetches = Arc::new(AtomicUsize::new(0));
let (blk, fc) = (block.clone(), fetches.clone());
let loader: TileLoader = Box::new(move |_si, _ti| {
fc.fetch_add(1, SeqCst);
Some(blk.clone())
});
let dirs = [
vec![(5u32, 5u32, Some((10u32, 11u32, 100u32, 100u32)))],
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
];
let idx = GraphIndex::from_remote_directories(dirs, PermSet::ALL, loader);
assert!(idx.match_pattern((Some(5), Some(99), None)).is_empty());
assert_eq!(fetches.load(SeqCst), 0, "synopsis must skip the fetch");
assert!(idx.match_pattern((Some(5), None, Some(999))).is_empty());
assert_eq!(
fetches.load(SeqCst),
0,
"secondary-c prune also skips the fetch"
);
assert_eq!(
idx.match_pattern((Some(5), Some(10), None)),
vec![(5, 10, 100)]
);
assert_eq!(
fetches.load(SeqCst),
1,
"an admissible secondary still fetches"
);
}
#[test]
fn absent_synopsis_never_prunes() {
use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
use std::sync::Arc;
let block = {
let mut b = TripleBlockBuilder::new();
b.push((5, 10, 100));
b.build()
};
let fetches = Arc::new(AtomicUsize::new(0));
let (blk, fc) = (block.clone(), fetches.clone());
let loader: TileLoader = Box::new(move |_si, _ti| {
fc.fetch_add(1, SeqCst);
Some(blk.clone())
});
let dirs = [
vec![(5u32, 5u32, None)],
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
];
let idx = GraphIndex::from_remote_directories(dirs, PermSet::ALL, loader);
assert!(idx.match_pattern((Some(5), Some(99), None)).is_empty());
assert_eq!(fetches.load(SeqCst), 1, "no synopsis ⇒ no early prune");
}
fn all_patterns() -> Vec<Pattern> {
(0..8u8)
.map(|mask| {
(
(mask & 1 != 0).then_some(1u32),
(mask & 2 != 0).then_some(2u32),
(mask & 4 != 0).then_some(3u32),
)
})
.collect()
}
#[test]
fn perm_routing_never_leaves_core() {
for pat in all_patterns() {
let best_all = ALL_PERMS
.iter()
.map(|p| p.leading_bound(pat))
.max()
.unwrap();
let best_core = PermSet::CORE
.iter()
.map(|p| p.leading_bound(pat))
.max()
.unwrap();
let scores: Vec<String> = ALL_PERMS
.iter()
.map(|p| format!("{}={}", p.name(), p.leading_bound(pat)))
.collect();
eprintln!(
"s={} p={} o={} | {} | best6={best_all} best3={best_core} chosen={}",
pat.0.is_some() as u8,
pat.1.is_some() as u8,
pat.2.is_some() as u8,
scores.join(" "),
GraphIndex::best_permutation(pat).name(),
);
assert_eq!(
best_core, best_all,
"the three routing permutations must tie the best of six on {pat:?}"
);
let chosen = GraphIndex::best_permutation(pat);
assert!(
PermSet::CORE.contains(chosen),
"best_permutation chose {} for {pat:?}, outside the routing three",
chosen.name()
);
assert_eq!(
chosen,
GraphIndex::best_permutation_in(PermSet::CORE, pat),
"routing must be identical with three permutations and with six"
);
}
}
#[test]
fn sorted_permutation_never_sacrifices_routing() {
let mut declined = Vec::new();
for pat in all_patterns() {
for col in 0..3usize {
let routed_all = GraphIndex::best_permutation(pat).leading_bound(pat);
if let Some(p) = GraphIndex::permutation_sorted_on(pat, col) {
assert_eq!(
p.leading_bound(pat),
routed_all,
"six permutations must always co-sort at the best prefix"
);
assert_eq!(p.roles()[p.leading_bound(pat)], col);
}
match GraphIndex::permutation_sorted_on_in(PermSet::CORE, pat, col) {
Some(p) => {
assert!(PermSet::CORE.contains(p));
assert_eq!(
p.leading_bound(pat),
GraphIndex::best_permutation_in(PermSet::CORE, pat).leading_bound(pat)
);
}
None => {
if GraphIndex::permutation_sorted_on(pat, col).is_some() {
declined.push((pat, col));
}
}
}
}
}
for (pat, col) in &declined {
let bound: Vec<usize> = (0..3)
.filter(|&i| [pat.0, pat.1, pat.2][i].is_some())
.collect();
assert_eq!(
bound.len(),
1,
"only single-bound shapes lose a merge order"
);
assert_ne!(bound[0], *col);
}
eprintln!("three-permutation merge-join declines: {declined:?}");
assert_eq!(declined.len(), 3, "exactly three (bound, sort) shapes lost");
}
#[test]
fn perm_set_masks_and_positions() {
assert_eq!(PermSet::ALL.len(), 6);
assert_eq!(PermSet::CORE.len(), 3);
assert_eq!(PermSet::CORE.bits(), 0b0000_0111);
assert_eq!(PermSet::CORE.names(), vec!["SPO", "POS", "OSP"]);
assert_eq!(
PermSet::ALL.names(),
vec!["SPO", "POS", "OSP", "SOP", "PSO", "OPS"]
);
for (i, p) in PermSet::CORE.iter().enumerate() {
assert_eq!(PermSet::CORE.position(p), Some(i));
assert_eq!(p.section_index(), i);
}
assert_eq!(PermSet::CORE.position(IndexPermutation::Sop), None);
assert_eq!(PermSet::ALL.position(IndexPermutation::Ops), Some(5));
assert!(PermSet::from_bits(0b0000_0111).is_ok());
assert!(PermSet::from_bits(0b0011_1111).is_ok());
assert!(PermSet::from_bits(0b0000_1111).is_ok());
assert!(PermSet::from_bits(0b0000_0011).is_err());
assert!(PermSet::from_bits(0b0011_1000).is_err());
assert!(PermSet::from_bits(0b1000_0111).is_err());
}
#[test]
fn three_and_six_agree_on_every_pattern() {
let triples: Vec<Triple> = (0..200u32)
.map(|i| (i % 17 + 1, i % 5 + 1, i % 23 + 1))
.collect();
let six = GraphIndexBuilder::from_triples(triples.clone())
.with_tile_budget(128)
.build();
let three = GraphIndexBuilder::from_triples(triples)
.with_tile_budget(128)
.with_perms(PermSet::CORE)
.build();
assert_eq!(six.perms(), PermSet::ALL);
assert_eq!(three.perms(), PermSet::CORE);
for perm in [
IndexPermutation::Sop,
IndexPermutation::Pso,
IndexPermutation::Ops,
] {
assert!(three.tile_sections()[perm.section_index()].is_empty());
}
for a in [None, Some(3u32)] {
for b in [None, Some(2u32)] {
for c in [None, Some(9u32)] {
let mut x = six.match_pattern((a, b, c));
let mut y = three.match_pattern((a, b, c));
x.sort_unstable();
y.sort_unstable();
assert_eq!(x, y, "pattern {:?} disagreed", (a, b, c));
}
}
}
}
}