Table causing a stack overflow

Question

I am creating a transposition table for chess in Rust. To do this, I am creating a TranspositonEntry which records a u64 that represents the hash of a position and a move which is really just a u16. I want to store 2^19 entries into an array. However, there is an issue. The array is causing a stack overflow.

I would think the size of the array in bytes would be 10 * 2^19, or just over 5 MB, which shouldn’t cause a stack overflow. However, I think this is incorrect, as I cannot fix the code in order to not cause a stack overflow.

A small example would be

struct Move {
    val : u16
}

impl Move {
    const NULL : Self = Self {val : 0};
}

struct TranspositionEntry {
    mov : Move,
    hash : u64
}

impl TranspositionEntry {
    const NULL_ENTRY: Self = Self { mov : Move::NULL, hash : 0};
}

fn main() {
    let table = [TranspositionEntry::NULL_ENTRY; 524288];
}

I think the table shouldn’t be large enough to cause a stack overflow, but yet it does.

Answer 1

Default stack sizes are smaller than you think. On Windows, the stack size is only 1 MiB by default. On Linux it is typically 8 MiB, which you can check like this:

$ ulimit -s
8192

When you spawn a thread, you can specify a different stack size:

use std::thread;

fn main() {
    let builder = thread::Builder::new().stack_size(32 * 1024); // 32 MiB

    let handler = builder.spawn(|| {
        // this should work now
        let table = [TranspositionEntry::NULL_ENTRY; 524288];
    }).unwrap();

    handler.join().unwrap();
}

But in this case, the better solution is to allocate the table on the heap.

fn main() {
    let table = vec![TranspositionEntry::NULL_ENTRY; 524288];
}