use super::{Failure, KeyCache, allocation, storage};
use std::ops::Range;
const MIN_PART: usize = if cfg!(test) { 2 } else { 4096 };
const MIN_PART_BYTES: usize = if cfg!(test) { 64 } else { 64 << 10 };
const RECORDS: usize = if cfg!(test) { 5 } else { 65536 };
const RAW_SHARE: usize = 6;
const PER_RECORD: usize =
(std::mem::size_of::<usize>() + std::mem::size_of::<(u64, u8, usize)>()).div_ceil(RAW_SHARE);
const REUSED: usize = 64 << 10;
pub(super) fn share(threads: usize, target: usize) -> usize {
if threads <= 1 {
0
} else {
(target / 16).min(48 << 20)
}
}
#[derive(Default)]
pub(super) struct Scratch {
pub sequence: u64,
pub spans: Vec<Range<usize>>,
pub sort_keys: storage::SortKeys,
pub language: storage::LanguageScratch,
}
impl Scratch {
fn trim(&mut self) {
let language = &mut self.language;
if language.bytes.capacity() > REUSED {
language.bytes = Vec::new();
}
if language.text.folded.capacity() > REUSED {
language.text.folded = String::new();
}
if language.text.composed.capacity() > REUSED {
language.text.composed = String::new();
}
}
}
pub(super) struct Projected<'a> {
pub(super) body: &'a [u8],
pub(super) prefix: u64,
pub(super) key_len: u8,
pub(super) sequence: u64,
}
#[derive(Default)]
struct Part {
bytes: Vec<u8>,
records: Vec<(u64, u8, usize)>,
failure: Option<Failure>,
}
pub(super) struct Batch {
bytes: Vec<u8>,
ends: Vec<usize>,
threads: usize,
limit: usize,
per_record: usize,
next_sequence: u64,
scratch: Scratch,
single: Vec<u8>,
}
impl Batch {
pub(super) fn new(threads: usize, target: usize) -> Self {
let threads = threads.max(1);
Self {
bytes: Vec::new(),
ends: Vec::new(),
threads,
limit: (share(threads, target) / RAW_SHARE).max(1),
per_record: PER_RECORD,
next_sequence: 0,
scratch: Scratch::default(),
single: Vec::new(),
}
}
pub(super) fn with_projected_overhead(mut self, bytes: usize) -> Self {
self.per_record = self.per_record.saturating_add(bytes.div_ceil(RAW_SHARE));
self
}
pub(super) fn push(
&mut self,
record: &[u8],
project: &(impl Fn(&[u8], &mut Scratch, &mut Vec<u8>) -> Result<KeyCache, Failure> + Sync),
mut accept: impl FnMut(Projected<'_>) -> Result<(), Failure>,
) -> Result<(), Failure> {
if self.threads == 1 {
self.single.clear();
self.scratch.sequence = self.next_sequence;
let (prefix, key_len) = project(record, &mut self.scratch, &mut self.single)?;
let sequence = self.next_sequence;
self.next_sequence = sequence.checked_add(1).ok_or_else(allocation)?;
let result = accept(Projected {
body: &self.single,
prefix,
key_len,
sequence,
});
if self.single.capacity() > REUSED {
self.single = Vec::new();
}
self.scratch.trim();
return result;
}
self.bytes
.try_reserve(record.len())
.map_err(|_| allocation())?;
self.bytes.extend_from_slice(record);
self.ends.try_reserve(1).map_err(|_| allocation())?;
self.ends.push(self.bytes.len());
let held = self
.bytes
.len()
.saturating_add(self.ends.len().saturating_mul(self.per_record));
if self.ends.len() >= RECORDS || held >= self.limit {
self.finish(project, accept)?;
}
Ok(())
}
pub(super) fn finish(
&mut self,
project: &(impl Fn(&[u8], &mut Scratch, &mut Vec<u8>) -> Result<KeyCache, Failure> + Sync),
mut accept: impl FnMut(Projected<'_>) -> Result<(), Failure>,
) -> Result<(), Failure> {
let count = self.ends.len();
let first = self.next_sequence;
let next = first.checked_add(count as u64).ok_or_else(allocation)?;
let (bytes, ends) = (&self.bytes, &self.ends);
let record = |at: usize| -> &[u8] {
let start = if at == 0 { 0 } else { ends[at - 1] };
&bytes[start..ends[at]]
};
let part = |from: usize, to: usize| -> Part {
let mut scratch = Scratch::default();
let mut out = Part::default();
if out.records.try_reserve_exact(to - from).is_err() {
out.failure = Some(allocation());
return out;
}
for at in from..to {
scratch.sequence = first + at as u64;
match project(record(at), &mut scratch, &mut out.bytes) {
Ok((prefix, key_len)) => out.records.push((prefix, key_len, out.bytes.len())),
Err(failure) => {
out.failure = Some(failure);
break;
}
}
}
out
};
let worth = (count / MIN_PART).max(bytes.len() / MIN_PART_BYTES);
let size = count.div_ceil(self.threads.min(worth).min(count).max(1));
let parts = count.div_ceil(size.max(1)).max(1);
let results = if parts == 1 {
vec![part(0, count)]
} else {
std::thread::scope(|scope| {
let spawned: Vec<_> = (0..parts)
.map(|p| {
let (from, to) = (p * size, ((p + 1) * size).min(count));
let part = ∂
std::thread::Builder::new()
.spawn_scoped(scope, move || part(from, to))
.map_err(|_| (from, to))
})
.collect();
spawned
.into_iter()
.map(|handle| match handle {
Ok(handle) => handle.join().expect("projection thread"),
Err((from, to)) => part(from, to),
})
.collect::<Vec<_>>()
})
};
let mut sequence = first;
for part in results {
let mut start = 0;
for &(prefix, key_len, end) in &part.records {
accept(Projected {
body: &part.bytes[start..end],
prefix,
key_len,
sequence,
})?;
sequence += 1;
start = end;
}
if let Some(failure) = part.failure {
return Err(failure);
}
}
self.next_sequence = next;
self.bytes.clear();
self.ends.clear();
if self.bytes.capacity() > self.limit.saturating_mul(2).max(REUSED) {
self.bytes = Vec::new();
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
fn numbers(batch: &mut Batch, rows: &[&[u8]]) -> Result<Vec<(u64, Vec<u8>)>, Failure> {
let mut seen = Vec::new();
for row in rows {
batch.push(row, &project, |r| {
seen.push((r.sequence, r.body.to_vec()));
Ok(())
})?;
}
batch.finish(&project, |r| {
seen.push((r.sequence, r.body.to_vec()));
Ok(())
})?;
Ok(seen)
}
fn project(bytes: &[u8], _: &mut Scratch, out: &mut Vec<u8>) -> Result<KeyCache, Failure> {
if bytes == b"bad" {
return Err(super::super::failure(
format!("bad record {}\n", String::from_utf8_lossy(bytes)).into_bytes(),
));
}
out.extend_from_slice(bytes);
Ok((bytes.len() as u64, 9))
}
#[test]
fn records_keep_input_order_and_sequence_on_any_thread_count() {
let rows: Vec<Vec<u8>> = (0..23).map(|i| format!("k{i}\t{i}").into_bytes()).collect();
let rows: Vec<&[u8]> = rows.iter().map(Vec::as_slice).collect();
let expected: Vec<(u64, Vec<u8>)> = rows
.iter()
.enumerate()
.map(|(at, row)| (at as u64, row.to_vec()))
.collect();
for threads in [1, 2, 3, 8] {
let seen = numbers(&mut Batch::new(threads, usize::MAX), &rows)
.ok()
.unwrap();
assert_eq!(seen, expected, "{threads}");
}
}
#[test]
fn projected_metadata_cannot_accumulate_a_batch_of_oversized_records() {
use std::sync::atomic::{AtomicUsize, Ordering};
let waiting = AtomicUsize::new(0);
let most = AtomicUsize::new(0);
let project = |_: &[u8], _: &mut Scratch, out: &mut Vec<u8>| {
out.try_reserve(8192).map_err(|_| allocation())?;
out.resize(out.len() + 8192, 0);
let now = waiting.fetch_add(1, Ordering::Relaxed) + 1;
most.fetch_max(now, Ordering::Relaxed);
Ok((0, 0))
};
let mut batch = Batch::new(4, 64 << 10).with_projected_overhead(8192);
let accept = |_: Projected<'_>| {
waiting.fetch_sub(1, Ordering::Relaxed);
Ok(())
};
for _ in 0..100 {
batch.push(b"a", &project, accept).ok().unwrap();
}
batch.finish(&project, accept).ok().unwrap();
assert_eq!(waiting.load(Ordering::Relaxed), 0);
assert_eq!(most.load(Ordering::Relaxed), 1);
}
#[test]
fn the_first_failure_in_input_order_wins() {
let mut rows: Vec<&[u8]> = vec![b"a\t1"; 12];
rows[3] = b"bad";
rows[9] = b"bad";
for threads in [1, 4] {
let mut accepted = 0;
let mut batch = Batch::new(threads, usize::MAX);
let mut result = Ok(());
for row in &rows {
result = batch.push(row, &project, |_| {
accepted += 1;
Ok(())
});
if result.is_err() {
break;
}
}
if result.is_ok() {
result = batch.finish(&project, |_| {
accepted += 1;
Ok(())
});
}
assert_eq!(
result.err().unwrap().message,
b"bad record bad\n",
"{threads}"
);
assert_eq!(accepted, 3, "{threads}");
}
}
#[test]
fn batches_of_long_records_are_projected_on_several_threads() {
use std::{collections::HashSet, sync::Mutex};
let threads = Mutex::new(HashSet::new());
let tracked = |bytes: &[u8], scratch: &mut Scratch, out: &mut Vec<u8>| {
threads.lock().unwrap().insert(std::thread::current().id());
project(bytes, scratch, out)
};
let mut batch = Batch::new(4, usize::MAX);
for row in [[b'a'; 300], [b'b'; 300]] {
batch.push(&row, &tracked, |_| Ok(())).ok().unwrap();
}
batch.finish(&tracked, |_| Ok(())).ok().unwrap();
let threads = threads.into_inner().unwrap();
assert_eq!(threads.len(), 2);
assert!(!threads.contains(&std::thread::current().id()));
}
#[test]
fn every_record_is_projected_once_however_the_batch_is_split() {
for threads in 1..=8 {
for count in 1..=24 {
let rows: Vec<Vec<u8>> = (0..count)
.map(|i| vec![b'a' + (i % 26) as u8; 100 + i])
.collect();
let rows: Vec<&[u8]> = rows.iter().map(Vec::as_slice).collect();
let expected: Vec<(u64, Vec<u8>)> = rows
.iter()
.enumerate()
.map(|(at, row)| (at as u64, row.to_vec()))
.collect();
let seen = numbers(&mut Batch::new(threads, usize::MAX), &rows)
.ok()
.unwrap();
assert_eq!(seen, expected, "{threads} threads, {count} records");
}
}
}
#[test]
fn batches_scale_with_their_share_and_give_back_large_buffers() {
let target = 64 << 10;
assert_eq!(share(4, target), 4096);
assert_eq!(share(1, target), 0);
assert_eq!(share(8, usize::MAX), 48 << 20);
let mut batch = Batch::new(4, target);
let mut sizes = Vec::new();
let mut seen = 0;
for _ in 0..90 {
batch
.push(&[b'x'; 300], &project, |_| {
seen += 1;
Ok(())
})
.ok()
.unwrap();
sizes.push(batch.bytes.len());
}
assert_eq!(seen, 90);
assert!(sizes.iter().all(|&size| size < 900), "{sizes:?}");
batch
.push(&vec![b'y'; 1 << 20], &project, |record| {
assert_eq!(record.body.len(), 1 << 20);
Ok(())
})
.ok()
.unwrap();
assert!(batch.bytes.capacity() <= REUSED);
let mut single = Batch::new(1, target);
single
.push(&vec![b'z'; 1 << 20], &project, |_| Ok(()))
.ok()
.unwrap();
assert!(single.single.capacity() <= REUSED);
}
}