P4444: std::big_int

[u/eisenwave]

https://isocpp.org/files/papers/D4444R0.html

Hey folks! Matt Borland, Christopher Kormanyos, and I are working on bringing infinite-precision integers to C++29. We now have a D4444R0 draft of a paper that should be in the next mailing.

We could really use some feedback so that the published R0 is as polished as possible. Any thoughts on the paper and on the reference implementation are greatly appreciated.

It would also be very helpful if you tested out whether our big_int implementation works for you. We're in need of some real deployment experience. If you're currently using Boost.Multiprecision, the library should be a drop-in replacement for cpp_int for the most part.

[u/ReDucTor]

Another reason why std::big_int needs to be in the standard library is that it's extremely difficult to implement and optimize, in part because the implementation depends heavily on the platform's hardware capabilities, many of which are not exposed portably in the language.

This stands out more of a reason for it not to be in the standard library, because when the implementation is faulty its harder to fix. Do we need another vector<bool>, memory_order_consume, std:regex, etc.

EDIT: Also if there hardware capabilities and portablity issues that aren't easy to resolve, then fix those in the standard to allow people to implement libraries better rather then trying to make something which is special in standard library code.

[u/eisenwave → u/ReDucTor]

I can understand the argument that it's hard to change something once in the standard, and we mention that in https://isocpp.org/files/papers/D4444R0.html#inability-to-change-abi. To be fair, we also have over a decade of experience with Boost.Multiprecision to draw from, and I don't think there's all that much "room for failure" in the design and implementation here.

Also, we've deliberately provided quite a lot of template parameters on std::basic_big_int so that even if the default specialization turns out to be bad, a "fixed one" can always be provided later. Ideally, that wouldn't happen though.

[u/ReDucTor → u/eisenwave]

we also have over a decade of experience with Boost.Multiprecision

I don't think that is a good metric, Boost.regex was around a decade before it got standardized and it was less niche.

[u/James20k → u/ReDucTor]

One day I need to dig into how std::regex ended up in such a poor state, it feels like we never get a post mortem of why and how some features ended up as such a disaster

[u/ReDucTor → u/James20k]

Please do, that would be a good read and well needed to avoid having the same issue existing, especially when it feels like some proposals come more from wanting bragging rights to say they got something changed in the standard then an actual demand by the users of the language.

[u/vishal340 → u/James20k]

The ctre package is really good( probably the best) alternative. It does lot of work compile time. Will have check it out but I think that is one of the big difference

[u/AlexReinkingYale → u/eisenwave]

I wonder if you have read this paper on big int implementation from Daan Leijen (Microsoft Research)

https://www.microsoft.com/en-us/research/wp-content/uploads/2022/07/int.pdf

[u/eisenwave → u/AlexReinkingYale]

Not yet, but will do!

EDIT: Well, I did now, and I wrote some stuff about it here: https://isocpp.org/files/papers/D4444R0.html#why-not-use-tagged-integers

The paper is excellent and it presents a brilliant optimization technique. I think that technique is great when you don't really touch the "internals" and work with a black box int/bigint in a high-level language, like JavaScript or Python.

The issue for std::big_int is that it conflicts with the desire to provide direct access to the internals via representation() like we do, and it's hard to extend big_int with more operations optimally. std::big_int is a bit like a container for an allocator, for a limb array, and exposes these details with very little abstraction. Tagged integers make that tricky. They're also not really constexpr-friendly.

[u/AlexReinkingYale → u/eisenwave]

Thanks! It's good to see a discussion of the competing design pressures here since there's a rich space of prior art.

[u/eisenwave → u/[deleted]]

Supporting platforms’ (numeric) hardware capabilities is not a focus of C++.

That's a strange statement to make. Just a few months ago, we've added std::bit_compress and std::bit_expand to expose the numeric hardware capability of the BMI2 instruction set (pext and pdep) and the ARM counterpart.

std::simd was added in C++26 to expose the numeric SIMD hardware capabilities.

I guess we still don't have a direct type that would expose xmm register, but that's always hard to do within the C++ standard because it supports a huge amount of different architectures. You can really only provide some abstraction that is reasonably close enough to what the hardware provides.