[FATAL] Thread 'main' has overflowed its stack

Hello, thank you for implementing song recognition for Rust!

After analyzing the code and how it works, I decided to run the code and ran into a problem...

rustc 1.74.1 (a28077b28 2023-12-04)

The error me encountering, "thread 'main' has overflowed its stack," typically occurs in Rust when there's too much data being allocated on the stack. In Rust, each thread has a fixed-size stack (commonly around 1-2 MB on many systems), and program exceeds this limit, me encounter a stack overflow.

Problem code

use std::collections::HashMap;
use chfft::RFft1D;

#[derive(Hash, Eq, PartialEq, Debug, Clone, Copy)]
pub enum FrequencyBand {
    _250_520 = 0,
    _520_1450 = 1,
    _1450_3500 = 2,
    _3500_5500 = 3,
}

pub struct FrequencyPeak {
    pub fft_pass_number: u32,
    pub peak_magnitude: u16,
    pub corrected_peak_frequency_bin: u16,
    pub sample_rate_hz: u32,
}

pub struct DecodedSignature {
    pub sample_rate_hz: u32,
    pub number_samples: u32,
    pub frequency_band_to_sound_peaks: HashMap<FrequencyBand, Vec<FrequencyPeak>>,
}

pub struct SignatureGenerator {

    // Used when processing input:

    ring_buffer_of_samples: [i16; 2048],
    /// Ring buffer.
    ring_buffer_of_samples_index: usize,

    reordered_ring_buffer_of_samples: [f32; 2048],
    /// Reordered, temporary version of the ring buffer above, with floats for precision because we applied Hanning window.

    fft_outputs: [[f32; 1025]; 256],
    /// Ring buffer. Lists of 1025 floats, premultiplied with a Hanning function before being passed through FFT, computed from the ring buffer every new 128 samples
    fft_outputs_index: usize,

    fft_object: RFft1D::<f32>,

    spread_fft_outputs: [[f32; 1025]; 256],
    /// Ring buffer.
    spread_fft_outputs_index: usize,

    num_spread_ffts_done: u32,

    signature: DecodedSignature,
}

fn main() {
    let mut this = SignatureGenerator {
        ring_buffer_of_samples: [0; 2048],
        ring_buffer_of_samples_index: 0,

        reordered_ring_buffer_of_samples: [0.0; 2048],

        fft_outputs: [[0.0; 1025]; 256],
        fft_outputs_index: 0,

        fft_object: RFft1D::<f32>::new(2048),

        spread_fft_outputs: [[0.0; 1025]; 256],
        spread_fft_outputs_index: 0,

        num_spread_ffts_done: 0,

        signature: DecodedSignature {
            sample_rate_hz: 16000,
            number_samples: 160000u32,
            frequency_band_to_sound_peaks: HashMap::new(),
        },
    };
}

In this code, a stack overflow occurs if run in the main thread.

thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\debug\untitled.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

Fix

pub struct SignatureGenerator {
    ring_buffer_of_samples: Vec<i16>,
    reordered_ring_buffer_of_samples: Vec<f32>,
    fft_outputs: Vec<Vec<f32>>,
    spread_fft_outputs: Vec<Vec<f32>>,
    ring_buffer_of_samples_index: usize,
    fft_outputs_index: usize,
    fft_object: RFft1D<f32>,
    spread_fft_outputs_index: usize,
    num_spread_ffts_done: u32,
    signature: DecodedSignature,
}

let mut this = SignatureGenerator {
    ring_buffer_of_samples: vec![0i16; 2048],
    ring_buffer_of_samples_index: 0,

    reordered_ring_buffer_of_samples: vec![0.0f32; 2048],

    fft_outputs: vec![vec![0.0f32; 1025]; 256],
    fft_outputs_index: 0,

    fft_object: RFft1D::new(2048),

    spread_fft_outputs: vec![vec![0.0f32; 1025]; 256],
    spread_fft_outputs_index: 0,

    num_spread_ffts_done: 0,

    signature: DecodedSignature {
        sample_rate_hz: 16000,
        number_samples: s16_mono_16khz_buffer.len() as u32,
        frequency_band_to_sound_peaks: HashMap::new(),
    },
};

Replacing fixed-size arrays with vectors in SignatureGenerator structure in Rust is a significant change that affects memory management and the way data is accessed

Original Structure

Static Arrays

Fields such as ring_buffer_of_samples, reordered_ring_buffer_of_samples, fft_outputs, and spread_fft_outputs are implemented as fixed-size arrays.
Memory allocation for these arrays is done on the stack.
The size of each array is fixed and cannot be changed during runtime.

Modified Structure

Dynamic Vectors

The arrays are replaced by vectors (Vec<i16> and Vec<f32>), which are dynamic arrays with sizes that can be modified during runtime.
Memory allocation for vectors is on the heap, accommodating larger data sets and reducing the risk of stack overflow.
Vectors offer greater flexibility due to their adjustable size.

I tested the code and it works the same, I don't see any overflow errors anymore. If you are ready to accept these changes, I can open a PR.

marin-m / SongRec