Reorganize the entire crate's structure

[AaronKutch]

I have had a lot of thinking over the past month about apint, and I think I will put most of it here. These are things I had off the top of my head that I had to type down, maybe I will remember more.

Calling BitWidth::new(...).unwrap() just to handle the 0 width case outside the function might seem to have barely any performance increase when dynamically setting a variable with it and then calling several constructors with that one variable, but I think doing many small things like it will make a significant difference. In benchmarks I just did, we are outperforming ramp by about 0.4x on basic ops, and I think it is because of many small branching choices I am making in the new arithmetic.rs and because of all your small design choices working together to make a big difference. For brevity though, I think we should make a macro, perhaps bw!(), and make it a procedural macro so that it produces compilation errors on 0. We could also use the procedural macro crate for future compile time stuff. BitWidth::new() should be kept for dynamic bit size purposes, and I wonder if we should get rid of the other BitWidth constructors since they have the unwrap inside them, and I much prefer to be able to see unwraps and mess with Results. We obviously cannot do the same thing with ShiftAmount but we should keep that, BitPos, and Radix for purposes of easily distinguishing between widths and positions and shifts and them having special purpose methods. Thorough documentation could also be included for each of these types later.

I had some trouble getting around the crate for a long while, and I think making the following organizational changes would help alot. Make sure that all tests pass before doing this, change to edition = 2018, cargo fix it

• Keep the stuff in uint.rs and int.rs where they are. They are just complicated wrappers around ApInt and almost no impls for them should be anywhere else.
• mod.rs should be changed to apint.rs. The extremely unsafe and important stuff like the Drop impls in constructor.rs and the Clone impl in casting.rs should be moved here.
• The debug and hash impls in apint/utils.rs should be moved to serialization.rs
• The is_one, is_even, etc in apint/utils.rs should be put in relational.rs
• The outer utils.rs should be merged with apint/utils.rs
• I would take the impls for ShiftAmount and what is in checks.rs and put them in a new file shiftamount.rs.
• Then put shiftamount.rs, bitpos.rs, bitwidth.rs, radix.rs, traits.rs, and error.rs in their own folder, maybe called info.
• apint.rs,int.rs, uint.rs, digit.rs, digit_seq.rs are put into a folder called data
• arithmetic.rs, casting.rs, constructors.rs, relational.rs, shift.rs,bitwise.rs, and utils.rs are put into a folder called logic
• rand_impl.rs, serialization.rs, serde_impl.rs, to_primitive.rs, lib.rs, and the folders are what remain at the top level of src

A while ago I raised an issue about the Clone impl you wrote for apint but benchmarks show that it is performing as quickly as what ramp has, so unless we happened to end up with a same less than optimal cloning routine, it is good.

I just realized something. The impl for ApInt looks like:

/// An arbitrary precision integer with modulo arithmetics similar to machine integers.
pub struct ApInt {
    /// The width in bits of this `ApInt`.
    len : BitWidth,
    /// The actual data (bits) of this `ApInt`.
    data: ApIntData
}

union ApIntData {
    /// Inline storage (up to 64 bits) for small-space optimization.
    inl: Digit,
    /// Extern storage (>64 bits) for larger `ApInt`s.
    ext: NonNull<Digit>
}

How does this work? wouldn't the ext have to be NonNull<Storage>?

[AaronKutch]

I know from benchmarking now what I need to work on (currently everything below 512 bits is superior to ramp except for division). I think the next steps are for me to finish the initial implementing unimplemented! in division functions commit, then you and me can work in parallel (most of the next work I will be doing will involve messing with the insides of functions and not with library layout which you can work on and it will be easy to merge commits). I will get the commits straightened out and hopefully this weekend is when you can start working on apint again. I read a comment I made on May 1 about getting multiplication and division working (I probably thought the time frame was only 1 month or less then), wow I was so wrong. If I add simd and other things onto the already strong base we have, we are on track to outperform everything for medium sized integers, maybe even GMP itself.

[AaronKutch]

Do you have enough time to do this refactoring by the end of November? I really want to have this refactoring done with #![feature(rust_2018_preview)] before December 6 even if that means the division function still has bad performance. If you don't have enough time, then I will do the refactoring. Also, don't release any more releases until I have gone through my checklist. When you accepted my pull request for the arithmetic rewrite I actually didn't intend for you to immediately release but I decided later that it was good enough.

[Robbepop]

This is some awesome information btw!

I like your checklist and I am also strongly favoring the proposed restructuring of apint in general.
Having started a new job I cannot tell when I have enough time for the entire revamp of the crate but I am motivated to do the work that has to be done in apint.

In the next days I will create a proper 0.3 release tracking issue where we collect everything that has to be done to channel our efforts.

It is also awesome to hear that apint currently outperforms ramp in some scenarios. I have never designed apint for that and it is funny to hear that now. So let's make it perfect then! Maybe I can even find use cases for apint in my company's codebases. That would be really epic.

Thanks for all your work!
Are you okay if I mention you as co-author of the crate with my next commit on it?

[AaronKutch]

Its ok if you make me coauthor.
One key place where ramp outperforms apint is whenever the inputs are multiple Digits (or limbs in ramp's own terminology) but the output fits in just one single Digit. I panicked when I first saw my division benchmark results vs ramp, with ramp being slightly faster. If instead I made the division to have a quotient of more than one digit, then we outperform ramp up to about 192 bits.
In the future, I think I will implement a division function with a more generic signature similar to GMP's and other libraries that allows differently sized ApInt inputs. It will also include two ApInts to use as internal buffers to give users maximum performance. This should solve any sizing performance issues.

I just realized that ramp might not be using Knuth's algorithm, it just has functions named similar to the ones I see in the c++ GMP library and says it uses some kind of school book implementation. Either way, I am making an optimized function that uses Knuth's for my specialized_div_rem crate to make sure that my function still outperforms Knuth's for medium sized integers (EDIT: to be clear, Knuth's outperforms my algorithm pretty quickly after ~128-256 bits, but hey I made an improvement in that area). Then I will open an issue for Rust to use my algorithm on 128 bit integer division. Then I will use what I learn from that to fix the perf in my more general function used in apint. Later this Christmas break I will make a proper Knuth's algorithm for larger integers in apint.

[AaronKutch]

wait did you not see this issue until now?

[Robbepop]

About your question in the beginning:
The NonNull<Digit> is very similar to a *mut Digit that cannot be NULL. This isn't even required because currently Rust cannot use the non-null guarantee for further optimizations. However, it still is good for documenting the purpose of the thing.
So the entire union is either a Digit (64 bits) in the inl case or a *mut Digit (32 or 64 bits).

Btw.: I am also greatly in favor of moving to Rust 2018 as soon as possible - I think the next Rust release 1.31 will be Rust 2018 already. That's about in 6 weeks from now.

Reeeeeeeally looking forward to your div/rem implementations. Do we have a useful set of performance tests, yet? Would be great to have a benchmark comparing ramp, bigint, apint and maybe even GMP for some operations and bitwidths.

[AaronKutch]

Yeah I should make a file just for benchmarks and preventing perf regressions between releases. I have a partial one already that includes ramp and bigint. There is the gmp bindings crate, but that requires linking to c++, and I don't know how to go about that.

[Robbepop]

Comparisons to ramp and bigint would be awesome already if we had them. :)
And yeah, performance regressions are bad and we really should find ways (bench suite?) to avoid them.

[AaronKutch]

The beta for Rust 2018 is ready to go, I would start compiling with it.

[Robbepop]

Yeah you can do that. But keep in mind that we cannot release a new version of Apint as long as Rust 2018 ist not stable. It will be stabilized in approx. 6 weeks.

[AaronKutch]

EDIT: I figured out that the errors happen when compiling with default-features=false, we can fix it in the reorganization.
I am getting errors when trying to compile apint 2.0 that I'm pretty sure I didn't get before, only warnings I think. How close are you to finishing reorganizing?

[Robbepop]

EDIT: I figured out that the errors happen when compiling with default-features=false, we can fix it in the reorganization.

Ah that's a good hint!

I am getting errors when trying to compile apint 2.0 that I'm pretty sure I didn't get before, only warnings I think.

What do you mean by apint 2.0 ?

How close are you to finishing reorganizing?

I get the idea that there is some kind of misunderstanding. I thought I shall wait for the reorganization of modules until you are done with your current task. So I had lots of ideas for apint, like no_std support but didn't do anything, yet.

[AaronKutch]

I thought I shall wait for the reorganization of modules until you are done with your current task.

Have you not done anything in the last month? I said that you can work in parallel with me because I was fixing performance problems inside functions and you were reorganizing where the functions are. Then when you were done with your commits it would be easy for me to replace the insides of the functions in a later PR. That was one of the points of the last PR I made.

What do you mean by apint 2.0 ?

Whoops I meant 0.2.0, that's the current version of apint on crates.io.

[AaronKutch]

I almost forgot to say that along with the crate reorganization, you can maybe change some things about the error type in the crate. I think that message and annotation part of the Error struct should not be there taking up space between when it is generated and when it is displayed, and it should only be generated as part of displaying the Error.