use core::num::NonZeroUsize;
use core::time::Duration;
use std::sync::OnceLock;
pub const PAYS: f64 = 3.0;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DispatchKind {
Team,
InPool,
Outside,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct WidthCosts {
widths: [u16; CAPACITY],
ns: [u64; CAPACITY],
len: u8,
}
const CAPACITY: usize = 12;
const fn to_ns(d: Duration) -> u64 {
let n = d.as_nanos();
if n > u64::MAX as u128 {
u64::MAX
} else {
n as u64
}
}
#[inline]
fn interpolate(c0: u64, c1: u64, w0: u16, w1: u16, w: usize) -> u64 {
let dw = (w - usize::from(w0)) as i64;
if let (Ok(a), Ok(b)) = (i64::try_from(c0), i64::try_from(c1)) {
if let Some(t) = (b - a).checked_mul(dw) {
let v = a + t / i64::from(w1 - w0);
return if v < 0 { 0 } else { v as u64 };
}
}
let (c0, c1) = (i128::from(c0), i128::from(c1));
let v = c0 + (c1 - c0) * (w - usize::from(w0)) as i128 / i128::from(w1 - w0);
if v < 0 {
0
} else {
v as u64
}
}
impl WidthCosts {
pub const MAX_ANCHORS: usize = CAPACITY;
pub const fn new(at_2_4_6: [Duration; 3]) -> Self {
Self::store(&[(2, at_2_4_6[0]), (4, at_2_4_6[1]), (6, at_2_4_6[2])])
}
pub const fn flat(cost: Duration) -> Self {
WidthCosts::new([cost; 3])
}
pub const fn from_anchors(anchors: &[(usize, Duration)]) -> Option<Self> {
let n = anchors.len();
if n == 0 || n > CAPACITY {
return None;
}
let mut k = 0;
while k < n {
let w = anchors[k].0;
if w < 2 || w > u16::MAX as usize {
return None;
}
if k > 0 && w <= anchors[k - 1].0 {
return None;
}
k += 1;
}
Some(Self::store(anchors))
}
const fn store(anchors: &[(usize, Duration)]) -> Self {
let mut widths = [0u16; CAPACITY];
let mut ns = [0u64; CAPACITY];
let mut k = 0;
while k < CAPACITY {
if k < anchors.len() {
widths[k] = anchors[k].0 as u16;
ns[k] = to_ns(anchors[k].1);
}
k += 1;
}
WidthCosts {
widths,
ns,
len: anchors.len() as u8,
}
}
#[inline]
pub(crate) fn ns_at(&self, width: NonZeroUsize) -> u64 {
let w = width.get();
let len = usize::from(self.len);
if w <= usize::from(self.widths[0]) {
return self.ns[0];
}
let mut i = 0;
while i + 1 < len {
let w1 = self.widths[i + 1];
if w <= usize::from(w1) {
return interpolate(self.ns[i], self.ns[i + 1], self.widths[i], w1, w);
}
i += 1;
}
let (last, w_m) = (self.ns[len - 1], u64::from(self.widths[len - 1]));
if let Some(p) = last.checked_mul(w as u64) {
return p / w_m;
}
let v = u128::from(last) * w as u128 / u128::from(w_m);
if v > u64::MAX as u128 {
u64::MAX
} else {
v as u64
}
}
#[inline]
pub fn at(&self, width: NonZeroUsize) -> Duration {
Duration::from_nanos(self.ns_at(width))
}
#[inline]
pub fn min(&self) -> Duration {
let len = usize::from(self.len);
let mut m = self.ns[0];
let mut k = 1;
while k < len {
if self.ns[k] < m {
m = self.ns[k];
}
k += 1;
}
Duration::from_nanos(m)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum HostClass {
X86_64Avx512,
X86_64Avx2,
X86_64Scalar,
Aarch64Apple,
Aarch64,
Generic,
}
impl HostClass {
pub fn detect() -> Self {
static CLASS: OnceLock<HostClass> = OnceLock::new();
*CLASS.get_or_init(Self::detect_uncached)
}
#[cfg(target_arch = "x86_64")]
fn detect_uncached() -> Self {
if std::arch::is_x86_feature_detected!("avx512f") {
HostClass::X86_64Avx512
} else if std::arch::is_x86_feature_detected!("avx2")
&& std::arch::is_x86_feature_detected!("fma")
{
HostClass::X86_64Avx2
} else {
HostClass::X86_64Scalar
}
}
#[cfg(all(target_arch = "aarch64", target_os = "macos"))]
fn detect_uncached() -> Self {
HostClass::Aarch64Apple
}
#[cfg(all(target_arch = "aarch64", not(target_os = "macos")))]
fn detect_uncached() -> Self {
HostClass::Aarch64
}
#[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
fn detect_uncached() -> Self {
HostClass::Generic
}
pub const fn name(self) -> &'static str {
match self {
HostClass::X86_64Avx512 => "x86_64-avx512",
HostClass::X86_64Avx2 => "x86_64-avx2",
HostClass::X86_64Scalar => "x86_64-scalar",
HostClass::Aarch64Apple => "aarch64-apple",
HostClass::Aarch64 => "aarch64",
HostClass::Generic => "generic",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DispatchCosts {
team: WidthCosts,
in_pool: WidthCosts,
outside: WidthCosts,
}
const fn us_f(x: f64) -> Duration {
Duration::from_nanos((x * 1000.0) as u64)
}
const fn anchored(anchors: &[(usize, Duration)]) -> WidthCosts {
match WidthCosts::from_anchors(anchors) {
Some(costs) => costs,
None => panic!("invalid measured anchors"),
}
}
const AVX512_TEAM: WidthCosts = anchored(&[
(2, us_f(0.6)),
(4, us_f(0.7)),
(6, us_f(0.9)),
(8, us_f(0.98)),
]);
const AVX2_TEAM: WidthCosts = anchored(&[
(2, Duration::from_nanos(1423)),
(4, Duration::from_nanos(1992)),
(6, Duration::from_nanos(2329)),
(8, Duration::from_nanos(2738)),
(12, Duration::from_nanos(3558)),
(16, Duration::from_nanos(4076)),
(24, Duration::from_nanos(4292)),
(32, Duration::from_nanos(4838)),
(48, Duration::from_nanos(6402)),
(64, Duration::from_nanos(9333)),
]);
impl DispatchCosts {
pub fn new(team: WidthCosts, in_pool: WidthCosts, outside: WidthCosts) -> Self {
DispatchCosts {
team,
in_pool,
outside,
}
}
pub fn for_class(class: HostClass) -> Self {
match class {
HostClass::X86_64Avx512 => DispatchCosts {
team: AVX512_TEAM,
in_pool: WidthCosts::new([us_f(3.0), us_f(3.6), us_f(3.5)]),
outside: WidthCosts::new([us_f(9.7), us_f(10.1), us_f(8.7)]),
},
HostClass::Aarch64Apple => DispatchCosts {
team: WidthCosts::new([us_f(3.0), us_f(2.3), us_f(1.4)]),
in_pool: WidthCosts::new([us_f(6.0), us_f(11.0), us_f(5.5)]),
outside: WidthCosts::new([us_f(14.0), us_f(18.0), us_f(19.0)]),
},
HostClass::X86_64Avx2 => DispatchCosts {
team: AVX2_TEAM,
in_pool: WidthCosts::flat(us_f(15.0)),
outside: WidthCosts::flat(us_f(40.0)),
},
HostClass::X86_64Scalar | HostClass::Aarch64 | HostClass::Generic => DispatchCosts {
team: WidthCosts::flat(us_f(3.0)),
in_pool: WidthCosts::flat(us_f(15.0)),
outside: WidthCosts::flat(us_f(40.0)),
},
}
}
pub fn host_default() -> Self {
Self::for_class(HostClass::detect())
}
#[must_use]
pub fn with(mut self, kind: DispatchKind, costs: WidthCosts) -> Self {
match kind {
DispatchKind::Team => self.team = costs,
DispatchKind::InPool => self.in_pool = costs,
DispatchKind::Outside => self.outside = costs,
}
self
}
pub fn min_cost(&self, kind: DispatchKind) -> Duration {
match kind {
DispatchKind::Team => self.team.min(),
DispatchKind::InPool => self.in_pool.min(),
DispatchKind::Outside => self.outside.min(),
}
}
#[inline]
pub fn cost(&self, kind: DispatchKind, width: NonZeroUsize) -> Duration {
match kind {
DispatchKind::Team => self.team.at(width),
DispatchKind::InPool => self.in_pool.at(width),
DispatchKind::Outside => self.outside.at(width),
}
}
}
impl Default for DispatchCosts {
fn default() -> Self {
DispatchCosts::host_default()
}
}
const PAYS_INT: u128 = 3;
#[inline]
fn pays_ns(est_ns: u64, sections: u32, cost_ns: u64) -> bool {
u128::from(est_ns) >= PAYS_INT * u128::from(sections) * u128::from(cost_ns)
}
pub fn pays_at(estimate: Duration, sections: u32, dispatch_cost: Duration) -> bool {
if dispatch_cost == Duration::MAX {
return false;
}
if sections == 0 {
return true;
}
pays_ns(to_ns(estimate), sections, to_ns(dispatch_cost))
}
pub fn width_for_by(
estimate: Duration,
sections: u32,
budget: NonZeroUsize,
cost: impl Fn(NonZeroUsize) -> Duration,
) -> NonZeroUsize {
let est_ns = to_ns(estimate);
let est = est_ns as f64;
let mut best = NonZeroUsize::MIN;
let mut best_obj = est;
for k in 2..=budget.get() {
let Some(width) = NonZeroUsize::new(k) else {
continue;
};
let d = cost(width);
if d == Duration::MAX {
continue;
}
let d_ns = to_ns(d);
if sections != 0 && !pays_ns(est_ns, sections, d_ns) {
continue;
}
let obj = f64::from(sections) * d_ns as f64 + est / k as f64;
if obj < best_obj {
best = width;
best_obj = obj;
}
}
best
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SplitCost {
pub estimate: Duration,
pub sections: u32,
pub resident_bytes: u64,
}
impl SplitCost {
#[must_use]
pub const fn with_resident_bytes(self, resident_bytes: u64) -> Self {
SplitCost {
resident_bytes,
..self
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct TransferRate {
ns_per_kib: u64,
}
impl TransferRate {
pub const fn per_kib(ns_per_kib: u64) -> Self {
Self { ns_per_kib }
}
pub fn for_class(class: HostClass) -> Self {
match class {
HostClass::Aarch64Apple => Self::per_kib(8),
HostClass::X86_64Avx512
| HostClass::X86_64Avx2
| HostClass::X86_64Scalar
| HostClass::Aarch64
| HostClass::Generic => Self::per_kib(41),
}
}
pub fn host_default() -> Self {
Self::for_class(HostClass::detect())
}
pub const fn ns_per_kib(&self) -> u64 {
self.ns_per_kib
}
pub fn time(&self, bytes: u64) -> Duration {
Duration::from_nanos(self.ns_of_bytes(bytes))
}
#[inline]
pub(crate) fn ns_of_bytes(&self, bytes: u64) -> u64 {
let ns = u128::from(bytes) * u128::from(self.ns_per_kib) / 1024;
if ns > u64::MAX as u128 {
u64::MAX
} else {
ns as u64
}
}
}
pub fn width_for_split_by(
split: SplitCost,
budget: NonZeroUsize,
dispatch: impl Fn(NonZeroUsize) -> Duration,
rate: TransferRate,
) -> NonZeroUsize {
let est_ns = to_ns(split.estimate);
let est = est_ns as f64;
let mut best = NonZeroUsize::MIN;
let mut best_obj = est;
for k in 2..=budget.get() {
let Some(width) = NonZeroUsize::new(k) else {
continue;
};
let d = dispatch(width);
if d == Duration::MAX {
continue;
}
let d_ns = to_ns(d);
if split.sections != 0 && !pays_ns(est_ns, split.sections, d_ns) {
continue;
}
let moved = u128::from(split.resident_bytes) * (k as u128 - 1) / k as u128;
let moved = if moved > u128::from(u64::MAX) {
u64::MAX
} else {
moved as u64
};
let transfer = rate.ns_of_bytes(moved) as f64;
let obj = f64::from(split.sections) * d_ns as f64 + est / k as f64 + transfer;
if obj < best_obj {
best = width;
best_obj = obj;
}
}
best
}
#[cfg(test)]
mod tests;