Remove some memory allocations

4 files changed, 132 insertions, 20 deletions

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<Move, _, Evaluation, { PossibleMoves::MAX_POSSIBLE_MOVES }> =
+			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<T, F: Fn(&T) -> R, R: Ord> {
-	collection: Box<[T]>,
+use crate::stackvec::StackVec;
+
+pub struct LazySort<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> {
+	collection: StackVec<T, CAPACITY>,
 	sorted: usize,
 	sort_by: F,
 }
 
-pub struct LazySortIter<T, F: Fn(&T) -> R, R: Ord> {
-	sorter: LazySort<T, F, R>,
+pub struct LazySortIter<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> {
+	sorter: LazySort<T, F, R, CAPACITY>,
 	index: usize,
 }
 
-impl<T: Clone, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
-	pub fn new(collection: &[T], sort_by: F) -> Self {
+impl<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> LazySort<T, F, R, CAPACITY> {
+	pub fn new(collection: impl IntoIterator<Item = T>, 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<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> LazySort<T, F, R, CAPACITY> {
 	fn sort(&mut self, index: usize) {
 		let mut min: Option<R> = None;
 		let mut min_index = None;
@@ -56,8 +59,10 @@ impl<T: Clone, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
 	}
 }
 
-impl<T: Copy, F: Fn(&T) -> R, R: Ord> IntoIterator for LazySort<T, F, R> {
-	type IntoIter = LazySortIter<T, F, R>;
+impl<T: Copy, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> IntoIterator
+	for LazySort<T, F, R, CAPACITY>
+{
+	type IntoIter = LazySortIter<T, F, R, CAPACITY>;
 	type Item = T;
 
 	fn into_iter(self) -> Self::IntoIter {
@@ -68,7 +73,9 @@ impl<T: Copy, F: Fn(&T) -> R, R: Ord> IntoIterator for LazySort<T, F, R> {
 	}
 }
 
-impl<T: Copy, F: Fn(&T) -> R, R: Ord> Iterator for LazySortIter<T, F, R> {
+impl<T: Copy, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> Iterator
+	for LazySortIter<T, F, R, CAPACITY>
+{
 	type Item = T;
 
 	fn next(&mut self) -> Option<Self::Item> {
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<T, const CAPACITY: usize> {
+	values: [MaybeUninit<T>; CAPACITY],
+	len: usize,
+}
+
+impl<T, const CAPACITY: usize> Deref for StackVec<T, CAPACITY> {
+	type Target = [T];
+
+	fn deref(&self) -> &Self::Target {
+		self.as_slice()
+	}
+}
+
+impl<T, const CAPACITY: usize> DerefMut for StackVec<T, CAPACITY> {
+	fn deref_mut(&mut self) -> &mut Self::Target {
+		self.as_mut_slice()
+	}
+}
+
+impl<T, const CAPACITY: usize> FromIterator<T> for StackVec<T, CAPACITY> {
+	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
+		let mut this = Self::new();
+		for item in iter {
+			this.push(item);
+		}
+
+		this
+	}
+}
+
+impl<T, const CAPACITY: usize> StackVec<T, CAPACITY> {
+	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<T> {
+		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;
+	}
+}