Why does creating and writing to a very large vector cause a core dump?

Question

I'm creating a Sieve of Eratosthenes so I can see all the prime numbers up to the starting number. Just the following code causes a core dump on Rust 1.26. There are no compiler warnings or errors, and the core dump isn't very helpful either with no error message.

fn main() {
    let starting_number: i64 = 600851475143;
    let mut primes = vec![true; 600851475143];

    primes[0] = false;
    primes[1] = false;

    for i in 2..((starting_number as f64).ln() as usize) {
        if primes[i] {
            let mut j = i + i;
            while j < primes.len() {
                primes[j] = false;
                j += i;
            }
        }
    }
}

I thought Rust was all about safety and avoiding core dumps? Is this a legit error with my code which isn't caught by the compiler or something different?

So you’re saying your machine has like over a terabyte of memory? — Sami Kuhmonen, May 20 '18 at 05:23
Your code does. You want to allocate an array of over 600 billion booleans. It takes a lot of memory. So first make that number a lot smaller and see if that’s the problem. — Sami Kuhmonen, May 20 '18 at 05:27
"I thought rust was all about safety and avoiding core dumps?" - No, it's about safety and avoiding undefined behavior. Sudden program aborts are safe and defined. Rust tries to minimize those, but they're by no means impossible. In many situations, there's simply nothing else to do that is safe. — Sebastian Redl, May 20 '18 at 07:51
Orthogonal to the actual problem: are you sure about `ln()` (aka. the natural logarithm) there? I have the feeling you meant `sqrt()` as there are plenty of non-prime numbers where there aren't any divisors smaller than `ln(n)`. Also note that your numeric types are a bit faulty: (a) why isn't your starting number `u64`? (b) not all numbers in `i64` or `u64` can be exactly represented as `f64`, so you'll loose precision. (c) You cast to `usize` at one point; you shouldn't use `usize` in these situations, but rather `u64`. — Lukas Kalbertodt, May 20 '18 at 08:22
You may wish to look into using a segmented seive as outlined here: https://www.geeksforgeeks.org/segmented-sieve/ — stevensonmt, May 20 '18 at 15:21

Stargateur · Accepted Answer · 2018-05-20T16:18:18.887

5

The problem is that you run out of memory.

A lot of operating systems are "lazy" to allocate memory. This means that the OS will not actually allocate the real amount of memory you ask for until you use it. You are asking for at least 75 106 434 393 octets (a.k.a. 70 Gio) but Rust don't optimize the size of Vec<bool>, so you are asking for 600 851 475 143 bytes (a.k.a. 600 GiB) — your OS must not have found enough memory.

It's an error that your OS can't handle because it already told you "OK" when you asked for the memory. It's a critical error, so it ends your process with a core dump.

I thought Rust was all about safety and avoiding core dumps?

A core dump doesn't necessarily imply that your program is not safe. As you see, your program didn't do an out of bounds memory access, it just doesn't have enough memory. It's the best way to handle this error from your OS point of view and there is nothing unsafe according to the definition of safe in Rust.

BTW, on my machine (archlinux), your program is simply killed:

[1]    4901 killed     cargo run

edited May 20 '18 at 16:18

answered May 20 '18 at 06:13

Stargateur

24,473
8
65
91

1

It might be worth stating the actual problem (specifically that OP is trying to allocate around 600GiB) in the beginning of your answer... which might be obvious to you, but not necessarily to other people (including OP). I also don't quite get, why you're naming the amount of memory in octets. At least I never cared about the number of octets and I don't think it's a very intuitive unit. – Lukas Kalbertodt May 20 '18 at 08:11
@LukasKalbertodt: Bytes isn’t a very intuitive unit? – Ry- May 20 '18 at 09:08
1

@LukasKalbertodt I believe that Stargateur wanted to avoid the use of "byte" here, because in C and C++, a byte isn't necessarily composed of 8 bits. Still, since this isn't C nor C++, a more human-readable measure would have been fine. – E_net4 May 20 '18 at 10:21
2

@E_net4: I think it’s because it’s the French word for byte. – Ry- May 20 '18 at 10:26
2

@Stargateur Ah ok, I misunderstood. But then you have a small error: `Vec` occupies exactly as many bytes as `Vec` with the same number of elements. `Vec` isn't specialized as `std::vector`. So no need to divide by 8. And yes, I think "bytes" would be easier to understand :P – Lukas Kalbertodt May 20 '18 at 11:05
@Ry-: I confirm it's French for the word byte, and that Stargateur is French ;) I approved Jan's edit to switch to byte, should be easier to read for non-French folks now ^^ – Matthieu M. May 20 '18 at 11:52
3

*that rust don't optimize the size* — it cannot while still allowing mutable references to elements. If you need the space savings you use a `BitVec` – Shepmaster May 20 '18 at 15:37
Ah, I have never had to think about memory when programming anything. Its always just been 'enough' and worked. So when this happened I didn't even think of that, thanks! – CorruptComputer May 20 '18 at 17:09

Why does creating and writing to a very large vector cause a core dump?

1 Answers1