42 different cases on a match causes a StackOverflowError

nologik · February 11, 2020, 6:27pm

Essentially, I want to use dynamic dispatch to return one of 42 different types of PostQuantumTypes as seen below:

fn get_new_alice(algorithm: u8) -> Box<dyn PostQuantumType> {
        assert!(algorithm < ALGORITHM_COUNT);
        match algorithm {
            // 0
            BABYBEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice())
            }
            // 1
            BABYBEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice())
            }
            // 2
            FIRESABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_firesaber::new_alice())
            }
            // ...
            FRODOKEM640AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem640aes::new_alice())
            }

            FRODOKEM640SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem640shake::new_alice())
            }

            FRODOKEM976AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem976aes::new_alice())
            }

            FRODOKEM976SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem976shake::new_alice())
            }

            FRODOKEM1344AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem1344aes::new_alice())
            }

            FRODOKEM1344SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem1344shake::new_alice())
            }

            KYBER512 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber512::new_alice())
            }

            KYBER768 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber768::new_alice())
            }

            KYBER1024 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber1024::new_alice())
            }

            KYBER51290S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber51290s::new_alice())
            }

            KYBER76890S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber76890s::new_alice())
            }

            KYBER102490S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber102490s::new_alice())
            }

            LEDAKEMLT12 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt12::new_alice())
            }

            LEDAKEMLT32 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt32::new_alice())
            }

            LEDAKEMLT52 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt52::new_alice())
            }

            LIGHTSABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_lightsaber::new_alice())
            }

            MAMABEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mamabear::new_alice())
            }

            MAMABEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mamabearephem::new_alice())
            }

            MCELIECE348864 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece348864::new_alice())
            }

            MCELIECE348864F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece348864f::new_alice())
            }

            MCELIECE460896 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece460896::new_alice())
            }

            MCELIECE460896F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece460896f::new_alice())
            }

            MCELIECE6688128 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6688128::new_alice())
            }

            MCELIECE6688128F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6688128f::new_alice())
            }

            MCELIECE6960119 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6960119::new_alice())
            }

            MCELIECE6960119F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6960119f::new_alice())
            }

            MCELIECE8192128 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece8192128::new_alice())
            }

            MCELIECE8192128F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece8192128f::new_alice())
            }

            NEWHOPE512CCA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope512cca::new_alice())
            }

            NEWHOPE512CPA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope512cpa::new_alice())
            }

            NEWHOPE1024CCA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope1024cca::new_alice())
            }

            NEWHOPE1024CPA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope1024cpa::new_alice())
            }

            NTRUHPS2048509 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps2048509::new_alice())
            }

            NTRUHPS2048677 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps2048677::new_alice())
            }

            NTRUHPS4096821 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps4096821::new_alice())
            }

            NTRUHRSS701 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhrss701::new_alice())
            }

            PAPABEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_papabear::new_alice())
            }

            PAPABEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_papabearephem::new_alice())
            }

            SABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_saber::new_alice())
            }

            _ => {
                unreachable!()
            }
        }

However, when there are this many cases, it causes a StackOverflowError. What would be a better way of mapping byte-sized values to the corresponding constructor?

nologik · February 11, 2020, 7:02pm

This works, but is undesirable:

        std::thread::Builder::new()
            .stack_size(16*1024*1024)
            .spawn(run)
            .unwrap()
            .join()
            .unwrap();

alice · February 11, 2020, 7:04pm

Note that when creating a box, the boxed value is first created on the stack, then moved into the box. Could one of the kinds being super large (e.g. containing a large array) by any chance be the problem?

If the issue really is the match itself, you can create a top-level function that isn't generic for each case, make an array of function pointers, then index into that and call the corresponding function.

nologik · February 11, 2020, 7:07pm

Yeah, there are some types with a fixed array size (e.g., [u8; size])

I think so, it makes sense from the debugging

This would work well. Good thinking! I'll give it a shot and see what happens.

alice · February 11, 2020, 7:11pm

You may want to consider using vec_utils::UninitBox to create the boxes of types with large arrays, as it's much better at allowing the optimizer to create the box directly in the heap allocation as opposed to moving it after creating it on the stack.

nologik · February 11, 2020, 7:22pm

I think I'm not expressing the idea correctly in this language. How might the correct implementation look?

pub(crate) mod function_pointers {
    use crate::PostQuantumType;
    use crate::algorithm_dictionary::ALGORITHM_COUNT;

    pub static ALICE_FP: [fn() -> dyn PostQuantumType; ALGORITHM_COUNT as usize] = [
        crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice,
        crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice,
        // ...
    ];
}

alice · February 11, 2020, 7:30pm

Sorry, the constructors don't return dyn PostQuantumType — they return the concrete instance. There's a difference between a trait object and a concrete instance. You also need them to wrap them in a box, so you need something like this:

fn box_babybear() -> Box<dyn PostQuantumType> {
    Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice())
}
fn box_babybearephem() -> Box<dyn PostQuantumType> {
    Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice())
}
// ...

Then create an array to these functions. You may find this macro interesting:

macro_rules! box_fn {
    ($constructor:expr) => {{
        fn my_box_fn() -> Box<dyn PostQuantumType> {
            Box::new($constructor)
        }
        
        my_box_fn
    }};
}
static CONSTRUCTORS: [fn() -> Box<dyn PostQuantumType>; ALGORITHM_COUNT] = [
    box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice()),
    box_fn!(...),
    box_fn!(...),
];

playground

kornel · February 11, 2020, 7:53pm

I'd suggest also adding #[inline(never)] on these functions.

nologik · February 11, 2020, 8:46pm

This is what I have now:

pub(crate) mod function_pointers {
    use crate::PostQuantumType;
    use crate::algorithm_dictionary::ALGORITHM_COUNT;

    macro_rules! box_fn {
    ($constructor:expr) => {{
        fn my_box_fn() -> Box<dyn PostQuantumType> {
            Box::new($constructor)
        }

        my_box_fn
    }};
}

    pub(crate) static ALICE_FP: [fn() -> Box<dyn PostQuantumType>; 2] = [
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice),
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice)
    ];

    pub(crate) static BOB_FP: [fn(&[u8]) -> Box<dyn PostQuantumType>; 2] = [
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_bob)
    ];

}

(I set the array len to 2 for sake of debugging process)

I get this error now:

error[E0308]: mismatched types
   --> ez_pqcrypto\src\lib.rs:259:9
    |
259 |         my_box_fn
    |         ^^^^^^^^^ incorrect number of function parameters
...
269 |         box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
    |         -------------------------------------------------------------------------------- in this macro invocation
    |
    = note: expected fn pointer `for<'r> fn(&'r [u8]) -> std::boxed::Box<_>`
                  found fn item `fn() -> std::boxed::Box<_> {function_pointers::BOB_FP::my_box_fn}`

alice · February 11, 2020, 8:55pm

You will need a separate macro for the bob case.

nologik · February 11, 2020, 8:58pm

Okay, I tried this:

    macro_rules! box_alice {
        ($constructor:expr) => {{
            fn alice_box_fn() -> Box<dyn PostQuantumType> {
                Box::new($constructor)
            }

            alice_box_fn
        }};
    }

    macro_rules! box_bob {
        ($constructor:expr) => {{
            fn bob_box_fn() -> Box<dyn PostQuantumType> {
                Box::new($constructor)
            }

            bob_box_fn
        }};
    }

    pub(crate) static ALICE_FP: [fn() -> Box<dyn PostQuantumType>; 2] = [
        box_alice!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice),
        box_alice!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice)
    ];

    pub(crate) static BOB_FP: [fn(&[u8]) -> Box<dyn PostQuantumType>; 2] = [
        box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
        box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_bob)
    ];

Getting closer. This error is now the barrier:

error[E0308]: mismatched types
   --> ez_pqcrypto\src\lib.rs:269:13
    |
269 |             bob_box_fn
    |             ^^^^^^^^^^ incorrect number of function parameters
...
279 |         box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
    |         --------------------------------------------------------------------------------- in this macro invocation
    |
    = note: expected fn pointer `for<'r> fn(&'r [u8]) -> std::boxed::Box<_>`
                  found fn item `fn() -> std::boxed::Box<_> {function_pointers::BOB_FP::bob_box_fn}`

alice · February 11, 2020, 9:00pm

You probably want this:

macro_rules! box_alice {
    ($constructor:expr) => {{
        #[inline(never)]
        fn alice_box_fn() -> Box<dyn PostQuantumType> {
            Box::new(($constructor)())
        }

        alice_box_fn
    }};
}

macro_rules! box_bob {
    ($constructor:expr) => {{
        #[inline(never)]
        fn bob_box_fn(arr: &[u8]) -> Box<dyn PostQuantumType> {
            Box::new(($constructor)(arr))
        }

        bob_box_fn
    }};
}

nologik · February 11, 2020, 9:01pm

You did it! Thank you

system · May 11, 2020, 9:01pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
Debugging and fixing stack overflow for extremely large function help	3	130	February 10, 2025
[Solved] Dynamic dispatch: Trait object not object-save, alternatives? help	9	2679	January 12, 2023
Implementing my own dynamic function dispatch in constant time help	1	323	April 5, 2022
Are there alternative better ways for multiple `Box::new(something) as Box<dyn std::fmt::Display>` in `match`? help	3	64	January 2, 2025
Selecting a type with type arguments from numerous combinations at runtime? help	5	247	August 30, 2024

42 different cases on a match causes a StackOverflowError

Related topics