// 725. Maximising stack allocation, avoiding heap
//
// Demonstrates [T; N] arrays, inline string buffers, and ArrayVec patterns.
use std::fmt;
// ── Stack-allocated fixed-size array ──────────────────────────────────────────
/// Process a fixed-size array entirely on the stack.
fn sum_stack_array() -> f64 {
// This array lives in the stack frame — no heap involved.
let data: [f64; 16] = [
1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0,
9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0,
];
data.iter().copied().sum()
}
/// Matrix multiply 4×4 — all data on the stack, no allocation.
fn matmul4(a: &[[f32; 4]; 4], b: &[[f32; 4]; 4]) -> [[f32; 4]; 4] {
let mut c = [[0.0f32; 4]; 4];
for i in 0..4 {
for k in 0..4 {
for j in 0..4 {
c[i][j] += a[i][k] * b[k][j];
}
}
}
c
}
// ── Inline string buffer ──────────────────────────────────────────────────────
/// A UTF-8 string that lives entirely on the stack (max `CAP` bytes).
/// Equivalent to `smallstr::SmallString` but std-only.
#[derive(Clone, Copy)]
pub struct StackStr<const CAP: usize> {
buf: [u8; CAP],
len: usize,
}
impl<const CAP: usize> StackStr<CAP> {
pub const fn new() -> Self {
Self { buf: [0u8; CAP], len: 0 }
}
/// Try to append a string slice. Returns `Err(())` if it doesn't fit.
pub fn push_str(&mut self, s: &str) -> Result<(), ()> {
let bytes = s.as_bytes();
if self.len + bytes.len() > CAP {
return Err(());
}
self.buf[self.len..self.len + bytes.len()].copy_from_slice(bytes);
self.len += bytes.len();
Ok(())
}
/// Try to append a single char.
pub fn push_char(&mut self, c: char) -> Result<(), ()> {
let mut tmp = [0u8; 4];
self.push_str(c.encode_utf8(&mut tmp))
}
pub fn as_str(&self) -> &str {
// SAFETY: We only accept valid UTF-8 via `push_str`/`push_char`,
// so `self.buf[..self.len]` is always valid UTF-8.
unsafe { std::str::from_utf8_unchecked(&self.buf[..self.len]) }
}
pub fn len(&self) -> usize { self.len }
pub fn is_empty(&self) -> bool { self.len == 0 }
pub fn clear(&mut self) { self.len = 0; }
}
impl<const CAP: usize> fmt::Display for StackStr<CAP> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
impl<const CAP: usize> fmt::Debug for StackStr<CAP> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "StackStr({:?})", self.as_str())
}
}
// ── ArrayVec — stack-backed growable slice ────────────────────────────────────
/// A `Vec`-like collection backed by a fixed-size stack array.
/// No heap allocation; panics if capacity exceeded.
pub struct ArrayVec<T, const CAP: usize> {
data: [std::mem::MaybeUninit<T>; CAP],
len: usize,
}
impl<T, const CAP: usize> ArrayVec<T, CAP> {
pub fn new() -> Self {
Self {
// SAFETY: Array of MaybeUninit needs no initialisation.
data: unsafe { std::mem::MaybeUninit::uninit().assume_init() },
len: 0,
}
}
pub fn push(&mut self, val: T) {
assert!(self.len < CAP, "ArrayVec capacity ({CAP}) exceeded");
self.data[self.len].write(val);
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 { return None; }
self.len -= 1;
// SAFETY: Element at `self.len` was written by `push` and not yet read.
Some(unsafe { self.data[self.len].assume_init_read() })
}
pub fn as_slice(&self) -> &[T] {
// SAFETY: Elements 0..self.len were written by `push`.
unsafe { std::slice::from_raw_parts(self.data.as_ptr() as *const T, self.len) }
}
pub fn len(&self) -> usize { self.len }
pub fn is_empty(&self) -> bool { self.len == 0 }
pub fn capacity(&self) -> usize { CAP }
}
impl<T, const CAP: usize> Drop for ArrayVec<T, CAP> {
fn drop(&mut self) {
for i in 0..self.len {
// SAFETY: elements 0..self.len are initialised.
unsafe { self.data[i].assume_init_drop(); }
}
}
}
// ── Small fixed-size ring buffer ──────────────────────────────────────────────
pub struct RingBuf<T: Copy + Default, const N: usize> {
buf: [T; N],
head: usize,
count: usize,
}
impl<T: Copy + Default, const N: usize> RingBuf<T, N> {
pub fn new() -> Self {
Self { buf: [T::default(); N], head: 0, count: 0 }
}
pub fn push(&mut self, val: T) -> bool {
if self.count == N { return false; }
let tail = (self.head + self.count) % N;
self.buf[tail] = val;
self.count += 1;
true
}
pub fn pop(&mut self) -> Option<T> {
if self.count == 0 { return None; }
let val = self.buf[self.head];
self.head = (self.head + 1) % N;
self.count -= 1;
Some(val)
}
pub fn len(&self) -> usize { self.count }
}
// ── main ──────────────────────────────────────────────────────────────────────
fn main() {
println!("=== Stack arrays ===");
println!("sum [1..16]: {}", sum_stack_array());
let identity = [[1.0, 0.0, 0.0, 0.0],
[0.0, 1.0, 0.0, 0.0],
[0.0, 0.0, 1.0, 0.0],
[0.0, 0.0, 0.0, 1.0f32]];
let result = matmul4(&identity, &identity);
println!("I × I diagonal: {:?}", [result[0][0], result[1][1], result[2][2], result[3][3]]);
println!("\n=== StackStr<64> ===");
let mut s = StackStr::<64>::new();
s.push_str("Hello, ").unwrap();
s.push_str("Rust!").unwrap();
s.push_char(' ').unwrap();
s.push_char('🦀').unwrap();
println!(" \"{s}\" (len={})", s.len());
let overflow = s.push_str(&"x".repeat(64));
println!(" Overflow result: {:?}", overflow);
println!("\n=== ArrayVec<i32, 8> ===");
let mut av = ArrayVec::<i32, 8>::new();
for i in 0..6 { av.push(i * i); }
println!(" contents: {:?}", av.as_slice());
println!(" len={} cap={}", av.len(), av.capacity());
println!(" pop: {:?}", av.pop());
println!("\n=== RingBuf<u8, 4> ===");
let mut rb = RingBuf::<u8, 4>::new();
for i in 0..4u8 { rb.push(i); }
println!(" full={}", rb.len() == 4);
println!(" push when full: {}", rb.push(99));
println!(" pop: {:?}", rb.pop());
println!(" pop: {:?}", rb.pop());
println!("\n=== Sizes (all stack) ===");
println!(" StackStr<64>: {} bytes", std::mem::size_of::<StackStr<64>>());
println!(" ArrayVec<i32, 8>: {} bytes", std::mem::size_of::<ArrayVec<i32, 8>>());
println!(" RingBuf<u8, 4>: {} bytes", std::mem::size_of::<RingBuf<u8, 4>>());
}
// ── Tests ─────────────────────────────────────────────────────────────────────
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn stack_str_basic() {
let mut s = StackStr::<32>::new();
s.push_str("hello").unwrap();
s.push_char('!').unwrap();
assert_eq!(s.as_str(), "hello!");
}
#[test]
fn stack_str_overflow() {
let mut s = StackStr::<4>::new();
assert!(s.push_str("abcd").is_ok());
assert!(s.push_str("e").is_err());
}
#[test]
fn arrayvec_push_pop() {
let mut av = ArrayVec::<u32, 4>::new();
av.push(10); av.push(20); av.push(30);
assert_eq!(av.as_slice(), &[10, 20, 30]);
assert_eq!(av.pop(), Some(30));
assert_eq!(av.len(), 2);
}
#[test]
#[should_panic(expected = "capacity")]
fn arrayvec_overflow_panics() {
let mut av = ArrayVec::<i32, 2>::new();
av.push(1); av.push(2); av.push(3); // should panic
}
#[test]
fn ringbuf_fifo() {
let mut rb = RingBuf::<i32, 3>::new();
rb.push(1); rb.push(2); rb.push(3);
assert_eq!(rb.pop(), Some(1));
assert_eq!(rb.pop(), Some(2));
rb.push(4);
assert_eq!(rb.pop(), Some(3));
assert_eq!(rb.pop(), Some(4));
assert_eq!(rb.pop(), None);
}
#[test]
fn matmul4_identity() {
let id: [[f32; 4]; 4] = [
[1.0, 0.0, 0.0, 0.0], [0.0, 1.0, 0.0, 0.0],
[0.0, 0.0, 1.0, 0.0], [0.0, 0.0, 0.0, 1.0],
];
let r = matmul4(&id, &id);
for i in 0..4 { assert_eq!(r[i][i], 1.0); }
}
}
(* OCaml: Stack allocation concepts
OCaml's GC allocates most values on the heap. Integers and floats
in local variables are unboxed on the stack. Float arrays have a
special optimisation path. *)
(* Integers and small tuples: unboxed, stack-allocated *)
let stack_int_ops () =
let a = 42 in (* unboxed int — stack *)
let b = 100 in (* unboxed int — stack *)
let sum = a + b in (* no allocation *)
Printf.printf "sum=%d (unboxed stack ints)\n" sum
(* Float local variables: unboxed when not in a record or variant *)
let stack_float_ops () =
let x = 3.14 in
let y = 2.71 in
Printf.printf "x+y=%.4f (unboxed floats)\n" (x +. y)
(* Float arrays: OCaml optimises these to unboxed flat arrays *)
let unboxed_float_array () =
let arr = Array.init 8 (fun i -> float_of_int i *. 1.5) in
let sum = Array.fold_left (+.) 0.0 arr in
Printf.printf "float array sum=%.2f (unboxed flat)\n" sum
(* Closest to a stack-allocated byte buffer: local Bytes *)
(* Note: Bytes is heap-allocated in OCaml, but it's the idiom *)
let local_buffer () =
let buf = Bytes.create 64 in (* heap, but small and short-lived *)
let len = ref 0 in
let push b = Bytes.set buf !len b; incr len in
List.iter push [Char.chr 72; Char.chr 105]; (* 'H', 'i' *)
Printf.printf "Buffer: %s\n" (Bytes.sub_string buf 0 !len)
(* Simulate ArrayVec: array with explicit length *)
type 'a arrayvec = { mutable data: 'a array; mutable len: int; cap: int }
let make_arrayvec cap default =
{ data = Array.make cap default; len = 0; cap }
let push_av av x =
if av.len >= av.cap then failwith "ArrayVec full"
else begin av.data.(av.len) <- x; av.len <- av.len + 1 end
let slice_av av = Array.sub av.data 0 av.len
let () =
stack_int_ops ();
stack_float_ops ();
unboxed_float_array ();
local_buffer ();
let av = make_arrayvec 8 0 in
List.iter (push_av av) [1; 2; 3; 4; 5];
Printf.printf "ArrayVec: [%s] len=%d cap=%d\n"
(String.concat "; " (Array.to_list (Array.map string_of_int (slice_av av))))
av.len av.cap