Long-running const-eval (loops) unusable in practice.

[oli-obk]

I've recently hit the problem of the hard error in the case when there is no infinite loop: my code generates PEXT Bitboards for a chess engine and it requires few seconds to finish but it's certainly not an infinite loop. The problem is that it forces me into either computing in the build time and going the code generation route (which is not pleasant) or having to only allow Rust Nightly which is maybe even less pleasant.

Originally posted by @kirillbobyrev in #71800 (comment)

[oli-obk]

I moved your comment from the other issue, as it is unrelated. Fixing the other issue will not make your problem worse.

Do you have more information about your failure? E.g. the entire error? Your code should definitely work, and we're gonna make it work.

What makes nightly different for your case?

[kirillbobyrev]

Thanks a lot! This was the issue linked to by the compiler so I thought it belongs there.

What I'm trying to do is to fill some arrays with pre-computed values in compile-time. The computation shouldn't take more than few seconds and is mostly bearable when I put it somewhere, e.g. in "independent" (of the project code) build.rs file. However, having it in the build script slows down cargo build and other commands, which seems to create a huge delay for the tooling (e.g. Rust-Analyzer) and is quite frustrating because it slows down the feedback cycle by a lot.

The computation on its own is not too "heavy": it fills an array of up to ~1e6 elements performing ~1e2 operations (rough estimate) for each of them, so it takes seconds instead of minutes or hours.

Error message

When trying to compile the compile-time evaluation version of the computation, I get two errors:

error: any use of this value will cause an error
  --> src/chess/attacks.rs:52:35
   |
14 | / const BISHOP_ATTACK_OFFSETS: [usize; BOARD_SIZE as usize] =
15 | |     generate_table::<BISHOP_ATTACKS_COUNT>(&BISHOP_ATTACK_DIRECTIONS).2;
   | |________________________________________________________________________-
...
52 |               let attacked_square = to_square(column, row);
   |                                     ^^^^^^^^^^^^^^^^^^^^^^
   |                                     |
   |                                     exceeded interpreter step limit (see `#[const_eval_limit]`)
   |                                     inside `generate_attacks` at src/chess/attacks.rs:52:35
   |                                     inside `generate_table::<5248_usize>` at src/chess/attacks.rs:129:61
   |                                     inside `BISHOP_ATTACK_OFFSETS` at src/chess/attacks.rs:15:5
   |
   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
   = note: for more information, see issue #71800 <https://github.com/rust-lang/rust/issues/71800>

and

error: any use of this value will cause an error
  --> src/chess/attacks.rs:70:5
   |
21 | / const ROOK_ATTACK_OFFSETS: [usize; BOARD_SIZE as usize] =
22 | |     generate_table::<ROOK_ATTACKS_COUNT>(&ROOK_ATTACK_DIRECTIONS).2;
   | |____________________________________________________________________-
...
70 |       while scanning_bit < 64 {
   |  _____^
   | |_____|
   | |_____|
   | |_____|
   | |
71 | |         if mask == 0 {
72 | |             break;
73 | |         }
...  |
79 | |         scanning_bit += 1;
80 | |     }
   | |     ^
   | |_____|
   | |_____exceeded interpreter step limit (see `#[const_eval_limit]`)
   | |_____inside `pdep` at src/chess/attacks.rs:70:5
   | |_____inside `generate_table::<102400_usize>` at src/chess/attacks.rs:128:35
   |       inside `ROOK_ATTACK_OFFSETS` at src/chess/attacks.rs:22:5
   |
   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
   = note: for more information, see issue #71800 <https://github.com/rust-lang/rust/issues/71800>

I don't know exactly why these two are pointed out by the compiler but it seems that in both cases the variables in question are really large (those are bitmasks, so I'm moving 1s close to the Most Significant Bit of u64). The variables themselves are just stored in array afterwards, they're not being the limit for loops or whiles. The only bitmasks that are are at most 2^12 which does not look very large.

Unstable Rust

So, the thing that forces me to use Nightly Rust is that there I can do

#![feature(const_eval_limit)]
#![const_eval_limit = "0"]

After I do that and switch to nightly version of the compiler, the code works as expected and is compiled without a noticeable delay (maybe 2-3 extra seconds as most for a single array computation, more if I do 6 computations instead of 2 because of the inability to do tuple deconstruction). But the point is, even in compile-time the code looks to be correct and doesn't loop infinitely.

Context

Also, apologies for the code being super dense and maybe hard to understand. Please let me know if you want me to extract (and possibly minimize) the entire snippet to make it independent of the project I'm building (it's quite easy to do so) or just make it cleaner & easier to follow. If you need more information, please let me know.

[oli-obk]

Thanks for the details, yea, this is an unfortunate situation. The only recommendation I have at this time for stable code is to split the computation into multiple constants and merge it in another constant.

A minimal repro is

const _: () = {
    let mut i = 333_333;
    while i > 0 {
        i -= 1;
    }
};

If the initial value of i is 333_332, then this code compiles.

It is very suboptimal that stable code mentions #[const_eval_limit]. We should probably just stabilize this attribute.

Opinions @rust-lang/wg-const-eval

[kirillbobyrev]

Thanks for the details, yea, this is an unfortunate situation. The only recommendation I have at this time for stable code is to split the computation into multiple constants and merge it in another constant.

A minimal repro is

const _: () = {
    let mut i = 333_333;
    while i > 0 {
        i -= 1;
    }
};

If the initial value of i is 333_332, then this code compiles.

It is very suboptimal that stable code mentions #[const_eval_limit]. We should probably just stabilize this attribute.

Opinions @rust-lang/wg-const-eval

Thanks! Splitting is... I would say very hard: the code is really tightly coupled, I don't think I can decompose.

Stabilizing #![feature(const_eval_limit)] sounds great to me, but better defaults also make sense to me. I'm not very well versed in the Rust Compiler internals, so I wouldn't know where to look for it but having some sensible limit allowing few seconds in compile-time should probably be preferable. Maybe have a warning for it, but certainly not denying such attempts to move parts of computation to the compile-time.

[oli-obk]

I'm not very well versed in the Rust Compiler internals, so I wouldn't know where to look for it but having some sensible limit allowing few seconds in compile-time should probably be preferable.

Yea... it's hard to come up with a good limit. The problem is that we also want a quick response when you end up in an infinite loop. Can you check what limit will allow your example to run so we have some numbers?

[Mark-Simulacrum]

The problem is that we also want a quick response when you end up in an infinite loop.

@oli-obk Is there somewhere to read more detail on this? It seems to me that const eval shouldn't necessarily be special compared to just running a program -- i.e., an infinite loop leads to hanging, which we probably 'always' want to diagnose (unlikely to be intended unless written literally as loop {} or so) but otherwise 'seems ok'.

In general a limit seems pretty annoying, since presumably then users will constantly need to be bumping it or setting it "infinitely" high if they're e.g. expecting to deserialize configuration data at compile-time which can be somewhat arbitrarily large. That seems like a pretty terrible experience, and comparatively the value of "detecting stalls" feels lower.

Ideally we'd have a nice way to debug those -- maybe we can hook things up such that rustc will provide and/or dump a const backtrace in some way when stopped via gdb/lldb or something like that? Those are typically the tools I at least reach for when trying to debug a stalled loop in a normal program, and it's not clear that it's terrible for const to be similar.

[RalfJung]

@Mark-Simulacrum I would liken this more to the recursion limit that we have for trait resolution. Both are really just different forms of user-defined computation happening at compile time. The compiler cannot reliably tell apart infinite loops from long computations, so any heuristic that diagnoses infinite loops will be wrong sometimes.

[Mark-Simulacrum]

Sure, they're similar/equivalent at a theoretical level, but I suspect that many users will not view them as such. Notably, it seems easy to write long-running const-eval code (it's just regular Rust code!) whereas the number of folks writing traits and clauses that cause 'sufficiently deep' recursion seems pretty likely to be low and/or at least more indicative of unintentional behavior.

Maybe it just means we should bump the default limit up really high (e.g., so that it takes minutes to get there on an average computer), or make an assumption that most users aren't using const-eval to compute anything serious, but it feels like a materially different case to me compared to trait resolution based on how users typically interact with these things.

My suggestion of basically removing the limit entirely and working on good interfaces to debugging const eval (e.g., making gdb/lldb or similar tooling work well with const eval) sort of goes towards that direction -- it leaves the user to determine whether they've created an infinite loop or not, and then provides tools to fix it, rather than heuristically guessing at an arbitrary point that a loop has been hit.

[kirillbobyrev]

I'm not very well versed in the Rust Compiler internals, so I wouldn't know where to look for it but having some sensible limit allowing few seconds in compile-time should probably be preferable.

Yea... it's hard to come up with a good limit. The problem is that we also want a quick response when you end up in an infinite loop. Can you check what limit will allow your example to run so we have some numbers?

A quick binary search over #[const_eval_limit] limit shows that 40000000 seems to work, 30000000 doesn't, so it's on magnitude of 3e7..4e7 ops (meaning my original estimate was about right, I honestly didn't expect that).

[RalfJung]

A quick binary search over #[const_eval_limit] limit shows that 40000000 seems to work, 30000000 doesn't, so it's on magnitude of 3e7..4e7 ops (meaning my original estimate was about right, I honestly didn't expect that).

So that's 30-40 times the current default limit.
How long does this computation take, roughly?

[kirillbobyrev]

A quick binary search over #[const_eval_limit] limit shows that 40000000 seems to work, 30000000 doesn't, so it's on magnitude of 3e7..4e7 ops (meaning my original estimate was about right, I honestly didn't expect that).

So that's 30-40 times the current default limit. How long does this computation take, roughly?

time cargo +nightly build gives ~3.5 secs when I change the file (so, this should include other operations on top of the actual compilation), so not much.

[gavofyork]

FWIW I'm also coming up against this. Thankfully I can work around by splitting the expression, but I'd definitely be grateful for stabilising const_eval_limit.