driftsort implementation uses an out-of-range literal on 16-bit targets

[saethlin]

Run

cargo +nightly miri setup --target avr-unknown-gnu-atmega328

Or

x check library/core --target avr-unknown-gnu-atmega328

And you'll get this diagnostic (cargo miri setup makes it a warning, lol):

error: literal out of range for `usize`
  --> core/src/slice/sort/stable/mod.rs:62:41
   |
62 |     const MAX_FULL_ALLOC_BYTES: usize = 8_000_000; // 8MB
   |                                         ^^^^^^^^^
   |
   = note: the literal `8_000_000` does not fit into the type `usize` whose range is `0..=65535`
   = note: `#[deny(overflowing_literals)]` on by default

I don't know what effect this has at runtime but it can't be good.

[workingjubilee]

It's worse than one might think, because many AVR microarchitectures, including the atmega328 we nominally support, have only 2KiB of SRAM, which means that this line is literally impossible:

    // For small inputs 4KiB of stack storage suffices, which allows us to avoid
    // calling the (de-)allocator. Benchmarks showed this was quite beneficial.
    let mut stack_buf = AlignedStorage::<T, 4096>::new();

[workingjubilee]

these targets should probably use some of the code in #129587 with perhaps a few more tweaks.

[Voultapher]

Good to know, 16-bit wasn't something we had in mind during development, in terms of less standard targets, we did test big endian with miri.

I agree with @workingjubilee the code in #129587 would be a better fit for such targets. What kind of tweaks did you have in mind?

[Voultapher]

There are other places in driftsort and ipnsort that use stack arrays, e.g:

rust/library/core/src/slice/sort/shared/smallsort.rs

Line 327 in d6c8169

let mut stack_array = MaybeUninit::<[T; SMALL_SORT_NETWORK_SCRATCH_LEN]>::uninit();

They are all size bound to <= 4KiB through various means, but still a poor fit for tiny chips.

[orlp]

these targets should probably use some of the code in #129587 with perhaps a few more tweaks.

I think that's necessary, I don't believe driftsort could ever meaningfully run on machines this small.

[workingjubilee]

What kind of tweaks did you have in mind?

You already figured it out: dropping all the stack arrays to the absolute minimum.

Note that you are not obligated to fix these targets, as usual.

[Voultapher]

I think it should be a single additional cfg_if in the impl, so I don't mind doing it.

[RalfJung]

(cargo miri setup makes it a warning, lol)

Yeah, we'd get CI failures way too often if we errored on warnings for tier 3 targets.

[RalfJung]

Related: #130818