Extra sizes and certain sizes not working with `ConcatMixed`

[Fethbita]

The following example

// [dependencies]
// crypto-bigint = "0.7.0-rc.17"

use crypto_bigint::{ConcatMixed, U1024, U1536, U2048, U3072, U4096, Uint};

pub struct KeyGenerator<const LIMBS: usize, const LIMBS_HALF: usize, const LIMBS_TIMES_TWO: usize>
{}

impl<const LIMBS: usize, const LIMBS_HALF: usize, const LIMBS_TIMES_TWO: usize>
    KeyGenerator<LIMBS, LIMBS_HALF, LIMBS_TIMES_TWO>
where
    // LIMBS_HALF * LIMBS_HALF = LIMBS
    Uint<LIMBS_HALF>: ConcatMixed<Uint<LIMBS_HALF>, MixedOutput = Uint<LIMBS>>,
    // LIMBS * LIMBS = LIMBS_TIMES_TWO
    Uint<LIMBS>: ConcatMixed<Uint<LIMBS>, MixedOutput = Uint<LIMBS_TIMES_TWO>>,
{
    pub fn new() -> Self {
        Self {}
    }
}

fn main() {
    let key_generator_2k = KeyGenerator::<_, { U1024::LIMBS }, _>::new();
    let key_generator_3k = KeyGenerator::<_, { U1536::LIMBS }, _>::new();
    let key_generator_4k = KeyGenerator::<_, { U2048::LIMBS }, _>::new();
    // TODO: Following line fails
    // let key_generator_6k = KeyGenerator::<_, { U3072::LIMBS }, _>::new();
    let key_generator_8k = KeyGenerator::<_, { U4096::LIMBS }, _>::new();
}

results in the following error if the key_generator_6k line is uncommented:

error[E0599]: the function or associated item `new` exists for struct `KeyGenerator<_, 48, _>`, but its trait bounds were not satisfied
   --> src/main.rs:533:68
    |
513 | pub struct KeyGenerator<const LIMBS: usize, const LIMBS_HALF: usize, const LIMBS_TIMES_TWO: usize>
    | -------------------------------------------------------------------------------------------------- function or associated item `new` not found for this struct
...
533 |     let key_generator_6k = KeyGenerator::<_, { U3072::LIMBS }, _>::new();
    |                                                                    ^^^ function or associated item cannot be called on `KeyGenerator<_, 48, _>` due to unsatisfied trait bounds
    |
   ::: /home/user/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/crypto-bigint-0.7.0-rc.17/src/uint.rs:88:1
    |
 88 | pub struct Uint<const LIMBS: usize> {
    | ----------------------------------- doesn't satisfy `<Uint<96> as ConcatMixed>::MixedOutput = Uint<_>` or `Uint<96>: ConcatMixed`
    |
note: trait bound `Uint<96>: ConcatMixed` was not satisfied
   --> src/main.rs:522:18
    |
517 |     KeyGenerator<LIMBS, LIMBS_HALF, LIMBS_TIMES_TWO>
    |     ------------------------------------------------
...
522 |     Uint<LIMBS>: ConcatMixed<Uint<LIMBS>, MixedOutput = Uint<LIMBS_TIMES_TWO>>,
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                  |                        |
    |                  |                        unsatisfied trait bound introduced here
    |                  unsatisfied trait bound introduced here
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following trait defines an item `new`, perhaps you need to implement it:
            candidate #1: `Monty`

For more information about this error, try `rustc --explain E0599`.
error: could not compile `rust-tests` (bin "rust-tests" test) due to 1 previous error

which blocks us from using certain sizes (even with extra-sizes feature) in our code.

[Fethbita]

Related to: #793, #1007, #1008 and #1015.

[tarcieri]

The current implementation has a sort of permutation table for what it supports:

https://github.com/RustCrypto/crypto-bigint/blob/a54858d9/src/uint.rs#L528-L548

We can potentially extend it with more combinations, but this sort of approach will always have its limitations.

To even begin to get around this and have any sort of generalized support for all sizes, the minimum thing we need from the Rust type system is min_const_generic_args. That would allow for a fully generalized hybrid-array, and with that we could implement certain (hybrid-array feature-gated) operations using typenum to perform size calculations and express bounds, which would allow them to be fully generalized and actually work on any size (we could actually do this today, but hybrid-array also has similar limitations around the sizes it supports which require min_const_generic_args to overcome)

To get rid of hybrid-array and implement everything in terms of const generics in a fully generalizable way, we'd need generic_const_exprs.

[Fethbita]

Still, for this particular use-case, would you consider adding more sizes to extra-sizes? 3ecf6b8

Currently values up to 8k are added but it would be really good to have the rest of them (particularly U8320 and U12288 for my problem (ed669f6)) in the next release. It would also be possible to add the sizes up to 16k gated behind a different feature until a more generalized solution using min_const_generic_args or generic_const_exprs can be implemented.

[tarcieri]

We'd have to measure the impact on compile times, which are already pretty bad. In my experience rustc's performance decreases quadratically with the number of overlapping trait impls.

I would ideally prefer to find solutions that let you do the arithmetic operations you need without having to add an excessive number of special cases, even if that means the result doesn't fit in a single integer value.

[Fethbita]

I tried to measure the compile times with cargo build --release --all-features after only adding U8320, U12288 and the results were not consistent at all, at times faster builds with these types added and at times faster builds without these types.

I later tested with hyperfine and the results look like this:
Without U8320, U12288:

hyperfine -p 'rm -rf target' --warmup 3 'cargo build --release --all-features'
Benchmark 1: cargo build --release --all-features
  Time (mean ± σ):      8.946 s ±  0.138 s    [User: 26.577 s, System: 2.492 s]
  Range (min … max):    8.717 s …  9.174 s    10 runs

With U8320, U12288 (https://github.com/RustCrypto/crypto-bigint/pull/1007/files/3c75f05bb16e4a39d8418ba772a27adb077abcb3):

hyperfine -p 'rm -rf target' --warmup 3 'cargo build --release --all-features'
Benchmark 1: cargo build --release --all-features
  Time (mean ± σ):      9.016 s ±  0.098 s    [User: 26.869 s, System: 2.525 s]
  Range (min … max):    8.855 s …  9.200 s    10 runs

Adding a new feature extra_sizes_16k that has all values up to 16k (https://github.com/RustCrypto/crypto-bigint/pull/1007/files/688676c46c69c04ce22079b2a6f71389712513af):

hyperfine -p 'rm -rf target' --warmup 3 'cargo build --release --all-features'
Benchmark 1: cargo build --release --all-features
  Time (mean ± σ):     10.379 s ±  0.203 s    [User: 28.344 s, System: 2.663 s]
  Range (min … max):   10.106 s … 10.722 s    10 runs

[tarcieri]

We can add a couple sizes, the question is do we want to get into adding bespoke sizes for random algorithms like we do in hybrid-array, or are there other workarounds which can be used to avoid that.

If you really think these are the only two sizes you're ever going to need and you're not going to come back here next week asking for more, I guess we can add them to unblock you, but I'm really not eager to make it a policy the way we do with hybrid-array as the maintenance burden is high.

[Fethbita]

I definitely understand not wanting to have these different types and having to maintain them but these two types are the only types I really need and I would really appreciate if you could add them.

I won't be coming back next week to ask for more types to be added :D

Edit: Created #1101