By Kokizzu


2015-01-31 07:24:05 8 Comments

I'm implementing combsort. I'd like to create fixed-size array on the stack, but it shows stack overflow. When I change it to be on the heap (Rust by Example says to allocate in the heap we must use Box), it still shows stack overflow.

fn new_gap(gap: usize) -> usize {
    let ngap = ((gap as f64) / 1.3) as usize;
    if ngap == 9 || ngap == 10 {
        return 11;
    }
    if ngap < 1 {
        return 1;
    }
    return ngap;
}

fn comb_sort(a: &mut Box<[f64]>) {
    // previously: [f64]
    let xlen = a.len();
    let mut gap = xlen;
    let mut swapped: bool;
    let mut temp: f64;
    loop {
        swapped = false;
        gap = new_gap(gap);
        for i in 0..(xlen - gap) {
            if a[i] > a[i + gap] {
                swapped = true;
                temp = a[i];
                a[i] = a[i + gap];
                a[i + gap] = temp;
            }
        }
        if !(gap > 1 || swapped) {
            break;
        }
    }
}

const N: usize = 10000000;

fn main() {
    let mut arr: Box<[f64]> = Box::new([0.0; N]); // previously: [f64; N] = [0.0; N];
    for z in 0..(N) {
        arr[z] = (N - z) as f64;
    }
    comb_sort(&mut arr);
    for z in 1..(N) {
        if arr[z] < arr[z - 1] {
            print!("!")
        }
    }
}

The output:

thread '<main>' has overflowed its stack
Illegal instruction (core dumped)

Or

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

I know that my stack size is not enough, the same as C++ when creating a non-heap array that is too big inside a function, but this code is using heap but still shows stack overflow. What's really wrong with this code?

2 comments

@Scott Olson 2015-01-31 07:38:01

As far as I can tell, it seems like that code is still trying to allocate the array on the stack first, and then move it into the box after.

It works for me if I switch to Vec<f64> in place of Box<[f64]> like this:

fn new_gap(gap: usize) -> usize {
    let ngap = ((gap as f64) / 1.3) as usize;
    if ngap == 9 || ngap == 10 {
        return 11;
    }
    if ngap < 1 {
        return 1;
    }
    return ngap;
}

fn comb_sort(a: &mut [f64]) {
    // previously: [f64]
    let xlen = a.len();
    let mut gap = xlen;
    let mut swapped: bool;
    let mut temp: f64;
    loop {
        swapped = false;
        gap = new_gap(gap);
        for i in 0..(xlen - gap) {
            if a[i] > a[i + gap] {
                swapped = true;
                temp = a[i];
                a[i] = a[i + gap];
                a[i + gap] = temp;
            }
        }
        if !(gap > 1 || swapped) {
            break;
        }
    }
}

const N: usize = 10000000;

fn main() {
    let mut arr: Vec<f64> = std::iter::repeat(0.0).take(N).collect();
    //let mut arr: Box<[f64]> = Box::new([0.0; N]); // previously: [f64; N] = [0.0; N];
    for z in 0..(N) {
        arr[z] = (N - z) as f64;
    }
    comb_sort(arr.as_mut_slice());
    for z in 1..(N) {
        if arr[z] < arr[z - 1] {
            print!("!")
        }
    }
}

@Shepmaster 2015-01-31 14:49:52

Checking out the LLVM IR for a smaller example shows this: alloca [10000000 x double], align 8, so I believe you are correct - the array is allocated on the stack first.

@Shepmaster 2016-12-04 00:02:12

In the future, the box syntax will be stabilized. When it is, it will support this large allocation, as no function call to Box::new will be needed, thus the array will never be placed on the stack. For example:

#![feature(box_syntax)]

fn main() {
    let v = box [0i32; 5_000_000];
    println!("{}", v[1_000_000])
}

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] thread '<main>' has overflowed its stack in Rust

  • 2015-03-07 10:45:23
  • VDimir
  • 3165 View
  • 5 Score
  • 2 Answer
  • Tags:   rust

5 Answered Questions

2 Answered Questions

1 Answered Questions

[SOLVED] thread '<main>' has overflowed its stack when creating a large array

2 Answered Questions

[SOLVED] How do I return an vector of dynamic length in a pub extern "C" fn?

  • 2016-10-20 13:56:50
  • The Unfun Cat
  • 1248 View
  • 5 Score
  • 2 Answer
  • Tags:   rust ffi

1 Answered Questions

[SOLVED] Four different outcomes when overflowing main stack

  • 2015-07-04 03:26:43
  • Akavall
  • 130 View
  • 12 Score
  • 1 Answer
  • Tags:   memory stack rust

2 Answered Questions

[SOLVED] What happens when a stack-allocated value is boxed?

  • 2015-04-13 22:07:33
  • Sergii Bogomolov
  • 485 View
  • 6 Score
  • 2 Answer
  • Tags:   rust boxing

1 Answered Questions

[SOLVED] "thread '<main>' has overflowed its stack" when constructing a large tree

  • 2015-02-22 16:40:27
  • qdwang
  • 940 View
  • 3 Score
  • 1 Answer
  • Tags:   rust

5 Answered Questions

Sponsored Content