core::array::from_fn segfaults (v1.64, v1.63)

[mvniekerk]

I tried this code:

Git git@github.com:mvniekerk/ga-perf.git , branch segfault_array_from_fn

I expected to see this happen: It to initialize an array using a function

Instead, this happened: It segfaulted

Meta

Also checked on Docker images for 1.63, 1.64

rustc --version --verbose:

rustc 1.64.0 (a55dd71d5 2022-09-19)
binary: rustc
commit-hash: a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52
commit-date: 2022-09-19
host: aarch64-apple-darwin
release: 1.64.0
LLVM version: 14.0.6

Backtrace

    Finished dev [unoptimized + debuginfo] target(s) in 0.27s
     Running `target/debug/rust`
[1]    35557 segmentation fault  cargo run

[yjhn]

Backtrace (from gdb):

#0  0x00005555555ec38c in __rust_probestack ()
#1  0x0000555555560f9a in core::array::try_collect_into_array<core::iter::adapters::map::Map<&mut core::iter::adapters::map::Map<core::array::iter::IntoIter<(), 1000>, core::array::from_fn::{closure_env#0}<[usize; 256], 1000, rust::main::{closure_env#1}>>, fn([usize; 256]) -> core::ops::try_trait::NeverShortCircuit<[usize; 256]>>, [usize; 256], core::ops::try_trait::NeverShortCircuitResidual, 1000> (
    iter=<error reading variable: Cannot access memory at address 0x800000bb7d60>)
    at /rustc/a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52/library/core/src/array/mod.rs:793
#2  0x0000555555561ff9 in core::array::try_collect_into_array_unchecked<core::iter::adapters::map::Map<&mut core::iter::adapters::map::Map<core::array::iter::IntoIter<(), 1000>, core::array::from_fn::{closure_env#0}<[usize; 256], 1000, rust::main::{closure_env#1}>>, fn([usize; 256]) -> core::ops::try_trait::NeverShortCircuit<[usize; 256]>>, [usize; 256], core::ops::try_trait::NeverShortCircuitResidual, 1000>
    (iter=0x7fffffa204a8)
    at /rustc/a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52/library/core/src/array/mod.rs:764
#3  0x0000555555561f53 in core::array::collect_into_array_unchecked<core::iter::adapters::map::Map<core::array::iter::IntoIter<(), 1000>, core::array::from_fn::{closure_env#0}<[usize; 256], 1000, rust::main::{closure_env#1}>>, 1000> (iter=0x7fffffc144f8)
    at /rustc/a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52/library/core/src/array/mod.rs:777
#4  0x0000555555562242 in core::array::{impl#23}::map<(), 1000, core::array::from_fn::{closure_env#0}<[usize; 256], 1000, rust::main::{closure_env#1}>, [usize; 256]> (self=..., f=...)
    at /rustc/a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52/library/core/src/array/mod.rs:445
#5  0x000055555556258c in core::array::from_fn<[usize; 256], 1000, rust::main::{closure_env#1}> (
    cb=...) at /rustc/a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52/library/core/src/array/mod.rs:44
#6  0x000055555556b9ed in rust::main () at src/main.rs:30

[Noratrieb]

I get thread 'main' has overflowed its stack on my system. So this segfault you're getting is caused by a stackoverflow. This happens because you allocate a Population on the stack, which has a size of 2_048_000 bytes, which is too big for the (relatively small) stack of the main thread.
Increasing the stack size by spawning a new thread with a 100MB stack fixes the issue.

diff --git a/rust/src/main.rs b/rust/src/main.rs
index 57b1f20..1f201b7 100644
--- a/rust/src/main.rs
+++ b/rust/src/main.rs
@@ -18,6 +18,10 @@ type Population = [[usize; NUM_POINTS]; MAX_POPULATION];
 type World = [Point; NUM_POINTS];

 fn main() {
+    std::thread::Builder::new().stack_size(100_000_00).spawn(run).unwrap().join().unwrap();
+}
+
+fn run() {
     // set up world
     let world: World = core::array::from_fn(|_| (fastrand::f64(), fastrand::f64()));

Alternatively, consider allocating the populations on the heap.

diff --git a/rust/src/main.rs b/rust/src/main.rs
index 57b1f20..9476cc0 100644
--- a/rust/src/main.rs
+++ b/rust/src/main.rs
@@ -14,7 +14,7 @@ const NUM_GENERATIONS: i32 = 50;
 const NUM_SURVIVORS: usize = 100;

 type Point = (f64, f64);
-type Population = [[usize; NUM_POINTS]; MAX_POPULATION];
+type Population = [Vec<usize>; MAX_POPULATION];
 type World = [Point; NUM_POINTS];

 fn main() {
@@ -48,22 +48,22 @@ fn main() {
     println!("Elapsed: {:?}", elapsed);
 }

-fn new_random_agent(rng: &mut ThreadRng) -> [usize; NUM_POINTS]
+fn new_random_agent(rng: &mut ThreadRng) -> Vec<usize>
 {
     let mut agent: [usize; NUM_POINTS] = core::array::from_fn(|i| i);
     agent.shuffle(rng);
-    agent
+    agent.into()
 }

-fn new_agent_from_parents(parents: &[[usize; NUM_POINTS]], mut rng: &mut ThreadRng) -> [usize; NUM_POINTS] {
+fn new_agent_from_parents(parents: &[Vec<usize>], mut rng: &mut ThreadRng) -> Vec<usize> {
     let parent = parents.choose(&mut rng).unwrap();

-    let mut agent = *parent;
+    let mut agent = parent.clone();
     agent.swap(
         rng.gen_range(0..NUM_POINTS) as usize,
         rng.gen_range(0..NUM_POINTS) as usize,
     );
-    agent
+    agent.into()
 }

 fn distance(a: &Point, b: &Point) -> f64 {

According to a few local benchmarks between the two patches above, the heap actually seems to be faster:

Benchmark 1: ./heap
  Time (mean ± σ):     622.7 ms ±  15.7 ms    [User: 611.7 ms, System: 11.0 ms]
  Range (min … max):   598.9 ms … 646.6 ms    10 runs

Benchmark 2: ./stack
  Time (mean ± σ):     651.5 ms ±  20.6 ms    [User: 641.0 ms, System: 5.9 ms]
  Range (min … max):   628.1 ms … 687.3 ms    10 runs

Summary
  './heap' ran
    1.05 ± 0.04 times faster than './stack'

rustc 1.66.0-nightly (5e9772042 2022-10-29)
binary: rustc
commit-hash: 5e9772042948002f9c6f60c4c81603170035fffa
commit-date: 2022-10-29
host: x86_64-unknown-linux-gnu
release: 1.66.0-nightly
LLVM version: 15.0.2

[Noratrieb]

It's interesting that Rusts SIGSEGV handler doesn't detect it as a stackoverflow for you

[dehanjl]

For anyone interested in the actual reason for the slow rust performance, for each comparison of the sort, the eval function was called. Updating to use sort_by_cached_key fixed it. The rust performance is now much better 😄

dehanjl/ga-perf@05699e7#diff-6830e545eaa10c62f07d60f7b6339ab85b95c03bf93ee5123e912a54fe09cdc8

Thanks, @keegancsmith for pointing it out.