From 655e896fb57ede428f889c6c7598f8954784e0dd Mon Sep 17 00:00:00 2001 From: Micha White Date: Thu, 21 Dec 2023 19:31:09 -0500 Subject: Remove some memory allocations --- engine/src/eval.rs | 17 +++++---- engine/src/lazysort.rs | 33 ++++++++++------- engine/src/lib.rs | 3 ++ engine/src/stackvec.rs | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 132 insertions(+), 20 deletions(-) create mode 100644 engine/src/stackvec.rs (limited to 'engine') diff --git a/engine/src/eval.rs b/engine/src/eval.rs index 4d7d540..01f07f6 100644 --- a/engine/src/eval.rs +++ b/engine/src/eval.rs @@ -171,17 +171,20 @@ pub fn negamax( let turn = board.turn(); let mut best_eval = Evaluation::NULL_MIN; let mut best_move = None; - let moves: Arc<[Move]> = if let Some(moves) = allowed_moves { - moves - } else { - PossibleMoves::moves(board).into_iter().collect() - }; - if moves.is_empty() { + let sort_fn = |m: &Move| unsafe { sort_moves(m, board, table) }; + let sorter: LazySort = + if let Some(moves) = allowed_moves { + LazySort::new(moves.iter().cloned(), sort_fn) + } else { + let moves = PossibleMoves::moves(board); + LazySort::new(moves, sort_fn) + }; + + if sorter.is_empty() { return (Evaluation::LOSS, None); } - let sorter = LazySort::new(&moves, |m| unsafe { sort_moves(m, board, table) }); for current_move in sorter.into_iter() { if cancel_flag.load(std::sync::atomic::Ordering::Acquire) { return (best_eval, best_move); diff --git a/engine/src/lazysort.rs b/engine/src/lazysort.rs index bec372c..ba32ee8 100644 --- a/engine/src/lazysort.rs +++ b/engine/src/lazysort.rs @@ -1,28 +1,31 @@ -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct LazySort R, R: Ord> { - collection: Box<[T]>, +use crate::stackvec::StackVec; + +pub struct LazySort R, R: Ord, const CAPACITY: usize> { + collection: StackVec, sorted: usize, sort_by: F, } -pub struct LazySortIter R, R: Ord> { - sorter: LazySort, +pub struct LazySortIter R, R: Ord, const CAPACITY: usize> { + sorter: LazySort, index: usize, } -impl R, R: Ord> LazySort { - pub fn new(collection: &[T], sort_by: F) -> Self { +impl R, R: Ord, const CAPACITY: usize> LazySort { + pub fn new(collection: impl IntoIterator, sort_by: F) -> Self { Self { - collection: collection.into(), + collection: collection.into_iter().collect(), sort_by, sorted: 0, } } - fn len(&self) -> usize { - self.collection.len() + pub fn is_empty(&self) -> bool { + self.collection.is_empty() } +} +impl R, R: Ord, const CAPACITY: usize> LazySort { fn sort(&mut self, index: usize) { let mut min: Option = None; let mut min_index = None; @@ -56,8 +59,10 @@ impl R, R: Ord> LazySort { } } -impl R, R: Ord> IntoIterator for LazySort { - type IntoIter = LazySortIter; +impl R, R: Ord, const CAPACITY: usize> IntoIterator + for LazySort +{ + type IntoIter = LazySortIter; type Item = T; fn into_iter(self) -> Self::IntoIter { @@ -68,7 +73,9 @@ impl R, R: Ord> IntoIterator for LazySort { } } -impl R, R: Ord> Iterator for LazySortIter { +impl R, R: Ord, const CAPACITY: usize> Iterator + for LazySortIter +{ type Item = T; fn next(&mut self) -> Option { diff --git a/engine/src/lib.rs b/engine/src/lib.rs index 27a1f2d..fdb50e6 100644 --- a/engine/src/lib.rs +++ b/engine/src/lib.rs @@ -1,4 +1,6 @@ #![feature(new_uninit)] +#![feature(maybe_uninit_uninit_array)] +#![feature(maybe_uninit_slice)] use std::num::{NonZeroU8, NonZeroUsize}; use std::sync::atomic::{AtomicBool, AtomicU8, AtomicUsize, Ordering}; @@ -15,6 +17,7 @@ pub use transposition_table::{TranspositionTable, TranspositionTableRef}; mod eval; mod lazysort; +mod stackvec; mod tablebase; mod transposition_table; diff --git a/engine/src/stackvec.rs b/engine/src/stackvec.rs new file mode 100644 index 0000000..9c00461 --- /dev/null +++ b/engine/src/stackvec.rs @@ -0,0 +1,99 @@ +use std::mem::MaybeUninit; +use std::ops::{Deref, DerefMut}; + +pub struct StackVec { + values: [MaybeUninit; CAPACITY], + len: usize, +} + +impl Deref for StackVec { + type Target = [T]; + + fn deref(&self) -> &Self::Target { + self.as_slice() + } +} + +impl DerefMut for StackVec { + fn deref_mut(&mut self) -> &mut Self::Target { + self.as_mut_slice() + } +} + +impl FromIterator for StackVec { + fn from_iter>(iter: I) -> Self { + let mut this = Self::new(); + for item in iter { + this.push(item); + } + + this + } +} + +impl StackVec { + pub fn new() -> Self { + Self { + values: MaybeUninit::uninit_array(), + len: 0, + } + } + + pub fn capcity(&self) -> usize { + CAPACITY + } + + pub fn len(&self) -> usize { + self.len + } + + pub fn is_empty(&self) -> bool { + self.len == 0 + } + + pub fn as_slice(&self) -> &[T] { + // safety: the first `len` elements are guaranteed to be initialized + unsafe { MaybeUninit::slice_assume_init_ref(&self.values[..self.len]) } + } + + pub fn as_mut_slice(&mut self) -> &mut [T] { + // safety: the first `len` elements are guaranteed to be initialized + unsafe { MaybeUninit::slice_assume_init_mut(&mut self.values[..self.len]) } + } + + pub fn as_ptr(&self) -> *const T { + self.values.as_ptr().cast() + } + + pub fn as_mut_ptr(&mut self) -> *mut T { + self.values.as_mut_ptr().cast() + } + + pub fn try_push(&mut self, value: T) -> Option<()> { + self.values.get_mut(self.len)?.write(value); + self.len += 1; + Some(()) + } + + pub fn push(&mut self, value: T) { + self.values[self.len].write(value); + self.len += 1; + } + + pub fn pop(&mut self) -> Option { + if self.is_empty() { + return None; + } + + // safety: this value will no longer be used, and the value is valid + // because it appears in the valid part of the array + unsafe { + self.len -= 1; + Some(std::ptr::read(self.as_ptr().add(self.len()))) + } + } + + pub fn clear(&mut self) { + self.len = 0; + } +} -- cgit v1.2.3