Add Array sizes up to 5000 (some of which are required for NTRU-Prime)

[oddcoder]

I would kindly ask you to wait and not merge this until I am 100% sure I will not need more sizes (When NTRU patch is ready). Best

[oddcoder]

@tarcieri I propose slightly different thing from the original PR, I modified the patch to include numbers up to 5000. I tried adding numbers manually for NTRU but there were too many of them and it is painful to do it manually.

This version takes 9 seconds to compile on my laptop which is not that bad. If later someone complains and need faster compile time we can split the ranges into smaller feature flags?

One thing that might require a deep look is this line. I am no sure why is it there

Last but not least, I am not sure what tests are failing. This is the view I see

If you have no objection, I would consider this patch ready to merge

[tarcieri]

This version takes 9 seconds to compile on my laptop which is not that bad

@oddcoder that seems really slow to me. What's the relative change in compilation time as a percentage?

[oddcoder]

➜  hybrid-array git:(ntru) time cargo build
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.85s
cargo build  0.40s user 0.09s system 53% cpu 0.926 total
➜  hybrid-array git:(ntru) time cargo build --features=extra-sizes
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 12.74s
cargo build --features=extra-sizes  11.87s user 0.41s system 96% cpu 12.770 total

Percentage wise, it is bad, almost 13X. However, we are talking about few seconds. So it shouldn't be that bad waiting for it to build.

The problem is for NTRU I need 18 constants between U653 and U2067, then I will need variants of them like C + 1, 2*C - 1 and bunch of others, and it doesn't scale well to keep adding them one by one. If you can accept the slow down, I can try to do it with proc macros. We can even split them with ranges (1000-1999), (2000, 2999) .... But then NTRU will need all the ranges.

[tarcieri]

@oddcoder could you try adding only the sizes you need for NTRU?

If that's too onerous, we can consider feature-gating various sizes in batches

[tarcieri]

Closing this as causing too much of an adverse effect on compile times.

81 might be nice for pluggable sizes, but for now I would suggest submitting another PR with exactly the sizes you need.

[oddcoder]

@tarcieri appologies for the long delay, got some busy weeks. I prototype a solution with feature flags. But it is abit too intrusive, so instead I will split it into smaller PRs each can be reviewed separately. The idea is is to use proc macros to improve felxibility but once we have proc macrs, some macros can be done nicer..... if you wouldn't mind, I can send smaller prs improving some of the stuff (like moving uint, and friends to proc macro) and then this patch will become nature all the sudden.

[tarcieri]

I would prefer to avoid proc macros in codegen, and just check in the generated files, so long as they have Rust code to generate them.

But also, I would like to get a stable release of hybrid-array out soon as it's blocking literally every release of every other crate our project maintains, so the "pencils down" moment is going to come very soon.

[oddcoder]

so my idea for proc macro is few things: 1- things like pub type U1040 = uint!(0 0 0 0 1 0 0 0 0 0 1); looks a bit error prone, pub type U1040 = uint!(1040); feels more natural 2- impl_array_sizes_with_import and impl_array_sizes are almost a derive. 3- generating ranges of uint! + impl_array_sizes can be also done by a proc macro.

if can reconsider this, I can send series of patches very very quickly, since I kinda have prototype, I just need to test split things into meaningful commit. If not, I can rework the python script to something in rust, But I feel it is a bit hacky.

[tarcieri]

Compile time, simplicity, and maintaining our current status of having zero hard dependencies matter a lot more than ergonomics for the implementation of hybrid-array.