use super::{Work, lock};
use crate::Error;
use rayon::{ThreadPool, ThreadPoolBuilder};
use std::fmt::{Debug, Formatter, Result as FmtResult};
use std::ops::Deref;
use std::sync::atomic::{AtomicBool, AtomicU32, Ordering};
use std::sync::mpsc::{RecvTimeoutError, channel};
use std::sync::{Arc, Mutex, MutexGuard};
use std::time::Duration;
const POLL: Duration = Duration::from_millis(1);
pub(crate) fn threads(jobs: usize) -> usize {
if jobs <= 1 {
return jobs;
}
std::thread::available_parallelism().map_or(jobs, |machine| jobs.min(machine.get()))
}
const MAX_KEPT: usize = 4;
#[derive(Clone, Default)]
pub struct Pool {
inner: Arc<Kept>,
}
#[derive(Default)]
struct Kept {
idle: Mutex<Vec<Runtime>>,
#[cfg(test)]
built: std::sync::atomic::AtomicUsize,
}
impl Pool {
pub fn new() -> Self {
Self::default()
}
fn idle(&self) -> MutexGuard<'_, Vec<Runtime>> {
lock(&self.inner.idle)
}
fn give_back(&self, runtime: Runtime) {
let evicted = {
let mut idle = self.idle();
idle.push(runtime);
(idle.len() > MAX_KEPT).then(|| idle.remove(0))
};
drop(evicted);
}
}
impl PartialEq for Pool {
fn eq(&self, other: &Self) -> bool {
Arc::ptr_eq(&self.inner, &other.inner)
}
}
impl Eq for Pool {}
impl Debug for Pool {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
let threads: Vec<usize> = self.idle().iter().map(Runtime::threads).collect();
f.debug_struct("Pool")
.field("at", &Arc::as_ptr(&self.inner))
.field("idle", &threads)
.finish()
}
}
pub(crate) struct Lent<'p> {
runtime: Option<Runtime>,
pool: Option<&'p Pool>,
}
impl<'p> Lent<'p> {
pub(crate) fn take(
pool: Option<&'p Pool>,
threads: usize,
stack_size: usize,
) -> Result<Self, Error> {
let threads = threads.max(1);
let kept = pool.and_then(|pool| {
let mut idle = pool.idle();
let at = idle
.iter()
.rposition(|r| r.threads == threads && r.stack_size >= stack_size)?;
Some(idle.remove(at))
});
let runtime = match kept {
Some(runtime) => runtime,
None => {
let runtime = Runtime::new(threads, stack_size)?;
#[cfg(test)]
if let Some(pool) = pool {
pool.inner.built.fetch_add(1, Ordering::Relaxed);
}
runtime
}
};
Ok(Self {
runtime: Some(runtime),
pool,
})
}
}
impl Deref for Lent<'_> {
type Target = Runtime;
fn deref(&self) -> &Runtime {
self.runtime
.as_ref()
.expect("a lent runtime is taken only when it is dropped")
}
}
impl Drop for Lent<'_> {
fn drop(&mut self) {
if let (Some(runtime), Some(pool)) = (self.runtime.take(), self.pool) {
pool.give_back(runtime);
}
}
}
pub(crate) struct Runtime {
pub(crate) pool: ThreadPool,
threads: usize,
stack_size: usize,
depths: Box<[AtomicU32]>,
}
impl Runtime {
pub(crate) fn new(threads: usize, stack_size: usize) -> Result<Self, Error> {
let threads = threads.max(1);
let pool = ThreadPoolBuilder::new()
.num_threads(threads)
.stack_size(stack_size)
.thread_name(|i| format!("deduxit-search-{i}"))
.build()
.map_err(|e| Error::ThreadPool {
threads,
message: e.to_string(),
})?;
Ok(Self {
pool,
threads,
stack_size,
depths: (0..threads).map(|_| AtomicU32::new(0)).collect(),
})
}
pub(crate) fn threads(&self) -> usize {
self.threads
}
pub(crate) fn depth_here(&self) -> u32 {
self.pool
.current_thread_index()
.map_or(0, |i| self.depths[i].load(Ordering::Relaxed))
}
pub(crate) fn waiting(&self, depth: u32) -> Waiting<'_> {
let saved = self.pool.current_thread_index().map(|i| {
let before = self.depths[i].swap(depth, Ordering::Relaxed);
(i, before)
});
Waiting {
runtime: self,
saved,
}
}
pub(crate) fn drive<T: Send>(
&self,
stop: &mut dyn FnMut(u64) -> bool,
done: &Work,
work: impl FnOnce(Flags<'_>) -> T + Send,
) -> T {
let flag = AtomicBool::new(false);
let (sender, receiver) = channel();
let result = self.pool.in_place_scope(|scope| {
let flag = &flag;
scope.spawn(move |_| {
let result = work(Flags::root(flag, done));
let _ = sender.send(result);
});
let _raise = RaiseOnPanic(flag);
loop {
match receiver.recv_timeout(POLL) {
Ok(result) => return Some(result),
Err(RecvTimeoutError::Timeout) => {
if stop(0) {
flag.store(true, Ordering::Relaxed);
}
}
Err(RecvTimeoutError::Disconnected) => return None,
}
}
});
result.expect("a task that ends without a result panicked, which the scope propagates")
}
}
pub(crate) struct Waiting<'a> {
runtime: &'a Runtime,
saved: Option<(usize, u32)>,
}
impl Drop for Waiting<'_> {
fn drop(&mut self) {
if let Some((i, before)) = self.saved {
self.runtime.depths[i].store(before, Ordering::Relaxed);
}
}
}
pub(crate) fn record(slot: &mut Option<super::Reason>, reason: super::Reason) {
if slot.is_none_or(|old| old == super::Reason::Stopped) {
*slot = Some(reason);
}
}
pub(crate) struct RaiseOnPanic<'a>(pub(crate) &'a AtomicBool);
impl Drop for RaiseOnPanic<'_> {
fn drop(&mut self) {
if std::thread::panicking() {
self.0.store(true, Ordering::Relaxed);
}
}
}
pub(crate) fn race<T: Send>(
runtimes: (&Runtime, &Runtime),
stop: &mut dyn FnMut(u64) -> bool,
done: &Work,
work: (
impl FnOnce(Flags<'_>) -> T + Send,
impl FnOnce(Flags<'_>) -> T + Send,
),
settles: impl Fn(&T) -> bool,
) -> (T, T) {
let flags = [AtomicBool::new(false), AtomicBool::new(false)];
let (sender, receiver) = channel();
let mut results = (None, None);
runtimes.0.pool.in_place_scope(|first| {
runtimes.1.pool.in_place_scope(|second| {
let flags = &flags;
let other = sender.clone();
first.spawn(move |_| {
let _other = RaiseOnPanic(&flags[1]);
let _ = sender.send((0, work.0(Flags::root(&flags[0], done))));
});
second.spawn(move |_| {
let _other = RaiseOnPanic(&flags[0]);
let _ = other.send((1, work.1(Flags::root(&flags[1], done))));
});
let _raise = [RaiseOnPanic(&flags[0]), RaiseOnPanic(&flags[1])];
while results.0.is_none() || results.1.is_none() {
match receiver.recv_timeout(POLL) {
Ok((i, result)) => {
if settles(&result) {
flags[1 - i].store(true, Ordering::Relaxed);
}
if i == 0 {
results.0 = Some(result);
} else {
results.1 = Some(result);
}
}
Err(RecvTimeoutError::Timeout) => {
if stop(0) {
flags[0].store(true, Ordering::Relaxed);
flags[1].store(true, Ordering::Relaxed);
}
}
Err(RecvTimeoutError::Disconnected) => break,
}
}
});
});
match results {
(Some(first), Some(second)) => (first, second),
_ => unreachable!("a task that ends without a result panicked, which its scope propagates"),
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Flags<'a> {
flag: &'a AtomicBool,
parent: Option<&'a Flags<'a>>,
work: &'a Work,
}
impl<'a> Flags<'a> {
pub(crate) fn root(flag: &'a AtomicBool, work: &'a Work) -> Self {
Self {
flag,
parent: None,
work,
}
}
pub(crate) fn child<'b>(&'b self, flag: &'b AtomicBool) -> Flags<'b>
where
'a: 'b,
{
Flags {
flag,
parent: Some(self),
work: self.work,
}
}
#[inline(never)]
pub(crate) fn fired(
&self,
units: u64,
counted: &mut crate::linear::search::Counted<'_>,
) -> bool {
counted.add(units);
counted.passed() || self.raised()
}
pub(crate) const fn counted(&self) -> crate::linear::search::Counted<'a> {
crate::linear::search::Counted::new(self.work)
}
pub(crate) fn raised(&self) -> bool {
let mut level = Some(self);
while let Some(flags) = level {
if flags.flag.load(Ordering::Relaxed) {
return true;
}
level = flags.parent;
}
false
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::{Pool, threads};
use crate::linear::fragment::Mode;
use crate::linear::search::{Engine, Options, Verdict, prove};
use std::sync::atomic::Ordering;
#[test]
fn searches_share_a_kept_runtime() {
let pool = Pool::new();
let alone = Options::default().with_jobs(2);
let pooled = alone.clone().with_pool(Some(pool.clone()));
let built = usize::from(threads(2) > 1);
let cases = [
("a & b, c |- c * (b & a)", Engine::Focus, true),
("a * b |- b * a", Engine::Net, true),
("a + b, c |- c * (a & b)", Engine::Focus, false),
];
for (text, engine, provable) in cases {
let sequent = text.parse().unwrap();
let forced = Some(engine).filter(|&e| e == Engine::Net);
let (alone, pooled) = (
alone.clone().with_engine(forced),
pooled.clone().with_engine(forced),
);
let fresh = prove(&sequent, Mode::CLASSICAL, &alone).unwrap();
let kept = prove(&sequent, Mode::CLASSICAL, &pooled).unwrap();
assert_eq!(kept.engine, engine, "{text}");
for outcome in [&fresh, &kept] {
let verdict = &outcome.verdict;
assert_eq!(matches!(verdict, Verdict::Proved(_)), provable, "{text}");
assert_eq!(
matches!(verdict, Verdict::Unprovable(_)),
!provable,
"{text}"
);
}
assert_eq!(pool.inner.built.load(Ordering::Relaxed), built, "{text}");
assert_eq!(pool.idle().len(), built, "{text}");
}
}
}