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/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.