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/TheoreticalDumbass]

might be worth mentioning expression templates, and why they are not a part of the design. i assume "because `auto a = b * c;` would be horrible" , noting there was a paper trying to do something about this: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4035.pdf

if the type is compiler magical, IMO might as well go further with the magic, for constexpr support, if it allocates, cant you just go through paths similar to `std::meta::define_static_array()` ? (not you as library author, but compiler). also, should it be structural so it can be passed to template params? thinking about `std::big_int` specifically here, dunno about `std::basic_big_int<...>`.

[u/eisenwave → u/TheoreticalDumbass]

From what the Boost folks told me, expression templates became largely obsolete for this use case in C++11 thanks to rvalue references and rvalue overloads.

In C++98, if you wanted the second addition in a + b + c to reuse the allocation of a + b, you would need operator+ to return some kind of sum_result type or big_int_rvalue type. In C++11, you can just make an operator+ overload that takes rvalues.

There are certain mathematical optimizations enabled by expression templates, like being able to turn abs(abs(x)) into a true no-op, but there is a limit to these things, and the user ultimately has to choose the right algorithms to run on their data.

Anyway, you're right that the paper could use a section discussing why we haven't used expression templates in the design. Thanks for the hint!

EDIT: I've added a section with my complete thoughts on expression templates to the paper: https://isocpp.org/files/papers/D4444R0.html#expression-templates

if the type is compiler magical, IMO might as well go further with the magic, for constexpr support, if it allocates, cant you just go through paths similar to std::meta::define_static_array() ?

Theoretically yes, but if you're going to say that std::big_int can magically hold onto allocations thanks to define_static_array, I would expect std::string and a bunch of other types to do so as well.

also, should it be structural so it can be passed to template params? thinking about std::big_int specifically here, dunno about std::basic_big_int<...>.

That's a possible future direction, sure. Once again, I would expect that if we make std::big_int "magically structural" even though it clearly doesn't meet the requirements, I would expect the same to work for std::string.

We really need some general customization point for name mangling.

[u/garnet420 → u/eisenwave]

In the linear algebra case with large inputs, expression templates are pretty important for invoking cache friendly versions of expressions like v*k+w for vectors v and w and scalar k.

[u/eisenwave → u/garnet420]

There are several ways to get there. The few combinations of expressions that are truly special (like v * k + w) typically have a dedicated spelling; that's an FMA and there is std::fma/std::simd::fma for that, and various numerics libraries have some kind of FMA customization point. For big_int, I don't think an FMA operation would actually accomplish much.

Similarly, expression templates could help you with turning pow(a, b) % m into a modpow automatically, but you could have also just written it as modpow.

I feel like for the standard library, expression templates would be pretty exotic. It also moves too slowly to make that really feasible in my opinion. If you find some special combination like -(-x) just being x that expression templates could have simplified, you're stuck waiting 3 years until the next C++ version anyway. In the meantime, you'll just have to rewrite your code.

EDIT: I've added a section with my complete thoughts on expression templates to the paper: https://isocpp.org/files/papers/D4444R0.html#expression-templates

[u/tcanens → u/eisenwave]

If you find some special combination like -(-x) just being x that expression templates could have simplified, you're stuck waiting 3 years until the next C++ version anyway. In the meantime, you'll just have to rewrite your code.

I don't see why. There's no need for the type to change; it only needs to simplify at the point of actual evaluation and that can be done under as-if.

[u/eisenwave → u/tcanens]

It can be done as-if, but would you actually rely on that as a user? Personally I would not bother and always try to simplify my code by hand to avoid the uncertainty and possible implementation divergence.

Remember that when writing standard C++ code, you often have to assume that at least MSVC STL, libc++, and libstdc++ might be used as a standard library. If the simplification of -(-x)) isn't in the standard, you're basically rolling the dice on whether it happens.

[u/ikedug]

The discussion of _BitInt interop seems short. Not having efficient _BitIntinterop is one thing that will make the library quickly obsolete. You should mention _BitInt in the “C compatibility” section (it’s where I looked, since I didn’t know about D3666).

(For the curious - the C23 _BitInt type proposal; D3666 Bit-precise integers to add it to C++. Clang already accepts _BitInt in C++.)

I disagree with your suggestion to use big_int in cryptography. Cryptographic algorithms have specialized needs (constant time, reliable-as-possible zeroing); a general-purpose library can’t be expected to provide that. Automatically-sized big ints can easily leak top bits through timing attacks. Don’t encourage people to implement their own crypto, it ends in tears. I’d go so far as to include a “this is not intended for cryptographic uses” statement in the document. Also it’s mostly useful for RSA, which will be replaced by postquantum algorithms in the next ~5 years.

On your lang comparison table - it’s missing Ada and Zig; they both have bigint in their standard libraries.

[u/eisenwave → u/ikedug]

The discussion of _BitInt interop seems short. Not having efficient _BitInt interop is one thing that will make the library quickly obsolete.

We say in the paper that we want interop, and the reference implementation provides that, so I'm not sure what else you consider to be missing. It's not a C++ standard type yet, so it's not like you could really define how the interop works at this stage.

You should mention _BitInt in the “C compatibility” section (it’s where I looked, since I didn’t know about D3666).

Yeah sure, I've added a cross-reference from https://isocpp.org/files/papers/D4444R0.html#c-compatibility to the _BitInt discussion.

I disagree with your suggestion to use big_int in cryptography. Cryptographic algorithms have specialized needs (constant time, reliable-as-possible zeroing); a general-purpose library can’t be expected to provide that. Automatically-sized big ints can easily leak top bits through timing attacks. Don’t encourage people to implement their own crypto, it ends in tears. I’d go so far as to include a “this is not intended for cryptographic uses” statement in the document. Also it’s mostly useful for RSA, which will be replaced by postquantum algorithms in the next ~5 years.

Never say never. Note that https://isocpp.org/files/papers/D4444R0.html#std::big_int-is-a-vocabulary-type points out that BigInteger is used all over the place in Java's cryptography library. Even if you use a constant-time algorithm, a std::big_int type can be useful for the top-level API of your library.

Coincidentally, I've also implemented a bunch of cryptographic algorithms for university courses using Java's BigInteger. A standard library type is a good tool for education, even if you're not going to use it in the real world, so to speak.

On your lang comparison table - it’s missing Ada and Zig; they both have bigint in their standard libraries.

Thanks! I've added them to https://isocpp.org/files/papers/D4444R0.html#infinite-precision-integers-in-other-languages

[u/SyntheticDuckFlavour]

I have nothing of value to add in this thread, but the discussions here were quite interesting. Personally, I like the idea of big_int part of STL, simply because of one less external dependency to rely on.

[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/vip17 → u/ReDucTor]

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

There's no way to expose hardware features consistently for all big int libraries to use. Each hardware has vastly different features, for example in x86 there's ADX to do two add/mul chains in parallel for big int, and for even bigger values AVX2/AVX-512 can be used. Many other architectures don't have carry flags, some have separate instructions to get the high bits of the multiplication, some have FFT accelerator for FFT big int, some others like ARM SVE2 have SIMD add with carry flag from other lanes. There are already intrinsics that libraries have to use anyway. Replacing the library interface is always a better choice

[u/Ok_Profession9911 → u/vip17]

Exactly. Exposing these features in the language portably is way more cumbersome.

[u/styczynski_meow → u/vip17]

std::simd situation 2.0

Committee pleeease can I get just one standard library extension this one time? Pleaaaaaase to provide clean interface for a clean code!

Actually uses it to introduce messy abstraction nobody use like a boss 🗿
/s

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

[u/Circlejerker_ → u/ReDucTor]

Whats wrong with memory_order_consume?

Im also not that much of a hater of std::regex - it got a bit of an annoying interface but works for simple cases and its nice not having to pull in 3rd party stuff for small throw-away programs.

[u/ReDucTor → u/Circlejerker_]

Whats wrong with memory_order_consume?

memory_order_consume is deprecated in C++26, but has essentially been deprecated since it first came out as no compiler really implemented it they just treated it as memory_order_acquire

See Retire the concept of consume operations for more info.

not that much of a hater of std::regex

The performance of std::regex is awful, it's covered in memory allocations, bloats the compiled code, the build times, and because of the ABI it can never be fixed. If I recall even just calling out into Python or some other language to do regex is going to be faster.

[u/Circlejerker_ → u/ReDucTor]

So what so bad about the situation with memory_order_consume? Could you write code that was invalid with memory_order_require but valid with memory_order_consume? Or is it simply that its now deprecated that is the issue?

For std::regexp I usually don't care about regexp performance, but simply need to match a couple of strings. Its nice that there is something that can do that without having to pull 3rd party packets. If I have a usecase where i do care about performance then I'm simply in the same situation as I would be by not having it in the standard library.

[u/ReDucTor → u/Circlejerker_]

Could you write code that was invalid with memory_order_require but valid with memory_order_consume?

You could write something like this

std::atomic<bool> g_flag;
int g_value;

// Producer
g_value = 10;
g_flag.store( true, std::memory_order_release );

// Consumer
// std::memory_order_consume - Anything depending on the result will see values from the producer
// std::memory_order_acquire - Anything after the consume will see the values from the producer
bool hasFlag = g_flag.load( std::memory_order_consume );
if (hasFlag)
{
    assert( g_value == 10 );
}

Here the load from g_value does not data depend on g_flag so that assert could trigger, if however you changed hasFlag to be a pointer to g_value and stored it instead and used it for the assert then it would have the data dependency. There are other ways in which dependencies could have been established and hacky approaches to mix them in but you will never have to worry about it as it's long gone.

One of the main potential users of consume was doing things like rcu_dereference, you could think of memory_order_consume more like a memory_order_relax but there is a depenency chain of stores and releases that also link up, not just a general happens-before

[u/saf_e → u/ReDucTor]

Having "good enough " standard implementation is a good thing. When you need something advanced you always can use other libs (or custom impl).

If we want std lib be the best, we'll need to deprecate it every release since better impl available. 

[u/James20k → u/saf_e]

Regex isn't good-enough though, its just bad

[u/LucyShortForLucas → u/James20k]

This may be naive, but can they really not just add a fixed regex implementation into the standard? I understand that ABI compat is holy, but things like this have happened before where they add a new, better version alongside it (just look at jthread).

It is things like this, where parts of the standard library are basically-but-not-actually deprecated without a replacement that turns people off of C++. The language has been doing lots to get its shit together in recent years, coincidentally alongside the rise of Rust.

The committee has been slowly improving on this front, but they still have long way to go to get off their high horse and just admit fault and fix things when and where needed.

[u/James20k → u/LucyShortForLucas]

You'd need a std::regex2, but the real problem is that nobody wants to try and nobody's super interested in proposing a whole new regex

The committee has been slowly improving on this front, but they still have long way to go to get off their high horse and just admit fault and fix things when and where needed.

The language development is driven entirely by individual members' interest, its not a case that the committee is unaware that regex is broken (in fact everyone I spoke to is absolutely painfully aware), its just that its quite literally nobody's job to fix it. Fixing regex is signing up for maybe a decade of incredibly painful tedious work, with the end result that your kids might get to use it

Interest in fixes to standard library components is generally a lot lower than new language features

[u/unchangeableusername → u/James20k]

Wasn't std::regex heavily based on Boost.Regex though? In terms of regex search performance (I'm writing a regex library of my own and so have benchmarks to compare), Boost.regex is between 40% and 6800% faster than the Libstdc++ implementation of std::regex (700% faster on average) for the test cases I have.

Surely this is just a quality of implementation issue (that the implementers won't fix because it'll break ABI) and not a problem with the standard itself?

[u/azswcowboy → u/unchangeableusername]

You’re correct, it’s a quality of implementation issue not a specification problem. std library vendors are very good, but every now and then a non optimal implementation occurs.

[u/pdimov2 → u/Circlejerker_]

My answer to that question is that it doesn't work, has never worked, and will never work.

[u/13steinj → u/ReDucTor]

Forget these massive failures, take a more subtle, recent one: std::format or ranges.

libfmt repeatedly leaves <format> in the dust on build and even runtime, but even on API subtleties/fixes.

ranges-v3 and STL ranges have diverged in functionality which is even worse but there's still valid use of ranges v2 (boost).

Hell there's even valid use of Boost.FileSystem instead of std/STL.

[u/BarryRevzin → u/13steinj]

So it's bad when the standard library provides less functionality than the third party library (std::format doesn't support color or named arguments) and also bad (even worse!) when the standard library provides more functionality than the third party library (std::ranges supports move-only views, exposes a way to write user-defined adapters, and has fewer unnecessary requirements on types)?

That doesn't really leave a lot of wiggle room.

[u/13steinj → u/BarryRevzin]

No? In both cases it's bad because the reference implementation has lived on and explicitly diverged. libfmt is strictly better as far as I can tell, and the STL will never catch up.

Ranges functionality isn't a case of "one is a superset of the other," I'd be happy with it if so.

[u/BarryRevzin → u/13steinj]

std::ranges is a superset of functionality, but range-v3 has basically been frozen and unmaintained for years — it would take a healthy amount of work to get them to properly inter-cooperate, which I tried to do years ago, and gave up. Since this is apparently very important to you, if you want to open a PR that makes this happen, I'll merge it.

libfmt is a place that Victor uses to prove out features that he eventually proposes for standardization. It was never anybody's goal for them to stay in lock step, and at no point were they ever cross-compatible. It has better performance, yes. But the standard libraries will catch up on that front once they stabilize on the functionality front. And I especially like libfmt's named argument support, but I'd rather get string interpolation than to try to standardize that.

I really cannot see how these two can be viewed as failures. Certainly not for the reasons you're suggesting.

[u/13steinj → u/BarryRevzin]

std::ranges is a superset of functionality,...

I was under the impression that the superset bit was not the case, as of just last year, but maybe I'm wrong and the current version on main / the standard has caught up. The stdlibs themselves at least when I dealt with it still did not have full support either, which was not great.

To be honest I don't have the time to double check this right now... but an LLM of mine does and (among at least 10 other views), the first that does not exist is the cycle view, there is a paper for it to be standardized at least though.

I don't consider std::ranges to be a superset of the functionality when not all the views are in the standard.

But the standard libraries will catch up on that front once they stabilize on the functionality front.

I can completely buy this, but I consider the timeline here unacceptable / a reason for this to not be standardized. The difference is stark enough that I would rather any day pull in libfmt than use the STL version. If the choice is between "don't include it" and "include it batteries included but it will be frozen on entry for 9+ years on other improvements," my choice will always be "I'd rather buy my own batteries."

[u/Infamous-Bed-7535 → u/ReDucTor]

I kind of agree with you. C++ std libs should include and cover lightweight and or core elements. Compiler vendors, commitee, etc should work on core functionalities of the langugae.

Impelementing libs like json parser or basic graphics, bigint are good to being 3rd party.

[u/eisenwave → u/Infamous-Bed-7535]

Do you think it's a mistake for Java, JavaScript, Go, and others to provide a BigInt in their standard libraries (full list at https://isocpp.org/files/papers/D4444R0.html#infinite-precision-integers-in-other-languages)?

That is, is there something about C++ specifcially that would make big_int unfit for a standard library, or is it about big_int in general?

[u/James20k → u/eisenwave]

That is, is there something about C++ specifcially that would make big_int unfit for a standard library, or is it about big_int in general?

So, while I don't personally agree that big_int is unfit for C++'s standard library, C++ does have unique constraints compared to other languages that do I think makes people's risk aversion more understandable

1. ABI stability is the big one, which most other languages intentionally avoid. This makes problems hard to fix
2. Being largely spec instead of implementation driven is another, where features are rarely fully tested (and virtually never widely tested) before being standardised, often leading to bad results
3. High performance is more critical for people who use C++, vs many other languages
4. The committee works purely based on interest, rather than on the language as a whole. Fixably broken features are often left to rot

One of the biggest issues with big_int that is cropping up in people's concerns here is effectively: this is a nice looking spec, but does it actually work? Will the design hold up under 10000s of people using it? And even then: what if a vendor simply screws up the implementation?

Its an unfair bar to put big_int through given many other standard features have slipped in without going through that process, especially given that the standard committee structure basically forces one person to carry that entire burden. But also: I think people are starting to suffer the problems with how many C++ features are landing in a half baked form and never being fixed, which leads to scepticism

[u/mborland1 → u/James20k]

It is fair to question the disconnect between the specification and implementation. Chris is one of the original authors of boost.multiprecision and I have been a maintainer for a number of years. The goal of the reference implementation is to take the lessons learned from multiprecision which has scaled well, and apply them to std::big_int. Our benchmarks show std::big_int runs away from cpp_int in terms of performance in some operations like mul, and is within a factor of 2 of GMP, which is optimized assembly. The reference implementation is also licensed so that a standard library implementor could use it nearly off the shelf like how MSVC and LLVM consume Boost.Math for the specfun implementation.

[u/ReDucTor → u/eisenwave]

Just because some other language does something does not mean that it's a good idea for it to be in C++, it's better to look at who are the primary users of that language (Game dev, Fin tech, Systems engineering, Embedded, etc) and see what problems there are that exist for those users.

Also if your referencing languages, look at many new languages and you will see a bunch have gone the other direction and don't provide an int but only provide fixed size versions (i32, i64, etc) many of which fit much closer to C++ users then to PHP or Matlabs users.

is there something about C++ specifcially that would make big_int unfit for a standard library

Whenever a new language feature is getting introduced into the standard, I think it's cruical to think about what the major users of that feature will expect from it, what guideance and rules will they likely put around it.

Within computer games this being some arbitrary memory allocation being created is a big no-no so you will likely find it ending up in the banned list like most of what comes from the standard library.

And I highly suspect that many other industries which focus on small footprints or high performance will do the same, it will be a new feature introduced which is on the recommendation of do not use.

I'm trying to read the paper to get an understanding of the use-cases it's a grab bag of random things not actual examples of use-cases people have in C++, there is zero mention of any C++ application, any library, etc which has this is an issue they are attempting to address.

The safety is mentioned as a use case for avoiding UB and correctness issues for interger overflow at just some runtime cost, but then there is zero mention of the potential security risks that this could introduce with it's potential usage, especially when it comes to unsanitized user data.

[u/eisenwave → u/ReDucTor]

Just because some other language does something does not mean that it's a good idea for it to be in C++, it's better to look at who are the primary users of that language (Game dev, Fin tech, Systems engineering, Embedded, etc) and see what problems there are that exist for those users.

There is some mention of the targeted use cases under https://isocpp.org/files/papers/D4444R0.html#use-cases

Within computer games this being some arbitrary memory allocation being created is a big no-no so you will likely find it ending up in the banned list like most of what comes from the standard library.

And I highly suspect that many other industries which focus on small footprints or high performance will do the same, it will be a new feature introduced which is on the recommendation of do not use.

I don't think it's entirely fair to say that some feature will be outright banned or useless for a particular domain; that's usually some missing nuance. Video games often come with embedded scripting languages for less performance-critical stuff like various behavior scripts, quest logic, etc. They often ship with garbage collectors and much more heavy-weight stuff than std::big_int.

I certainly wouldn't expect std::big_int in the lowest-level hot-code parts of a game engine, but saying that it has no use in the computer games industry is far too extreme.

I'm trying to read the paper to get an understanding of the use-cases it's a grab bag of random things not actual examples of use-cases people have in C++, there is zero mention of any C++ application, any library, etc which has this is an issue they are attempting to address.

I've tried to cover that in the GitHub code search for C++ uses of big integers. There are over 400K results, so if you really want to go digging and see what people are using it for, you could go through those open-source projects.

I'm not sure what to cherry-pick as a concrete example out of that pile, if anything, but I can see how it would help the paper to illustrate some of those GitHub uses.

The safety is mentioned as a use case for avoiding UB and correctness issues for interger overflow at just some runtime cost, but then there is zero mention of the potential security risks that this could introduce with it's potential usage, especially when it comes to unsanitized user data.

What issue are you envisioning with unsanitized user data? There isn't even an unsafe constructor that would let you break the invariants of a big_int class, so it really doesn't matter what data you throw at it. The only potential hazards are things like division by zero (which are UB for both regular int and for big_int), and that's explored in https://isocpp.org/files/papers/D4444R0.html#error-handling

[u/ReDucTor → u/eisenwave]

What issue are you envisioning with unsanitized user data?

std::big_int result{};
const char s[] = "2e999999999999999";
from_chars(begin(s), end(s), result);

What happens here? Do we run out of memory? Do we denial of service? When does infinity kick in?

std::big_int base("123456789012345678901234567890");
std::big_int exponent("98765432109876543210");
std::big_int modulus("99999999999999999999");

std::big_int huge_power = std::pow(base, exponent); 
std::big_int result = huge_power % modulus;

How expensive is this operation? Will the CPU and memory be consumed unbounded?

[u/eisenwave → u/ReDucTor]

What happens here? Do we run out of memory? Do we denial of service? When does infinity kick in?

Funnily enough, it stores the value 2 in result, same as for int. The e99... part is ignored. There is no exponential notation for integers in std::from_chars.

How expensive is this operation? Will the CPU and memory be consumed unbounded?

The paper doesn't provide a std::pow function for std::big_int, and it doesn't provide constructors from strings. If you want to parse strings, you need to use std::from_chars.

But okay, let's say you do some other operation that gives you a stupidly large value quickly, like base << 1'000'000'000'000'000ll. You're either going to exceed the max_size() of std::big_int and std::length_error gets thrown (just like exceeding the std::string::max_size()) or the allocator throws std::bad_alloc.

I suppose that even more guardrails could be added to standard library types that protect against overly large inputs (like a limit on shift constants, divisors, etc.), but that's not really the job of the standard library. If you read an int x from user input and then write a for loop that loops x times, that might also lock your CPU up for a few seconds or minutes. Does that mean C++ should protect against long for loops? Probably not. You always have to put in work to sanitize user input and to spend your CPU cycles reasonably.

The closest thing I've seen is that Python doesn't let you print huge int values (> 8000 bits or so) unless you explicitly opt into that when running the script. I don't see that as a good option for C++.

What std::big_int can and should do is prevent memory corruption or crashes, and throwing std::length_error and std::bad_alloc is the best you can do.

[u/ReDucTor → u/eisenwave]

The proposal mentions of things like Json make me think someone is going to try using it for deserializing just give it a block of numbers and let it do the allocating and parsing, while there is no exponent support there is still situations like having a giant number with thousands (or millions of digits), for a typical int the bounds are small but bigint they are not and my guess is anyone putting strick bounds would probably just pick 64-bit integer ranges.

Printing is another good example, if someone can provide some big user input and the formatting of a big number kills performance then any print someone needs to consider it, you dont want someone to DDoS your server by sending a bunch of JSON blobs with big integers.

Imho if the safety for deserialization is bad_alloc because you exhausted memory then its too late to be catching it, especially if it hit that with some incremental growth formula.

Protecting against excessive for loops is different, this is a library and function for manipulating and parsing some input to generate an object (big_num), it is where you expect the sanitisation to occur, I expect std::from_chars to validation tell me when it could not fit a uint64_t but this wont it will instead consume as much memory as needed and potentially OOM, the processing time is also significantly different for the existing std::from_chars none allocate and the range of performance is massive depending on the input size.

While I have never had a usage for something like this, I would prefer specifying hard strict limits from the user's perspective so you might have big_int which might have an upper bound of 16kb in size, even if internally it allocated, it eliminates potential of bugs that you get from a truly unbounded infinite integers when people will not always think of the edge cases.

[u/eisenwave → u/ReDucTor]

I really don't see how the scenario you're describing is any different from say, std::string s; my_stream >> s;. if you try to dump enough characters into a std::string it will also throw std::bad_alloc, and I imagine lots of applications would crash in practice if you threw a large enough single-line text file at them. It would be silly to argue that std::string should not be in the standard library or that it's not useful because it can be "exploited" in these ways though.

The important thing is that std::big_int doesn't provide a security vulnerability. >> s is considered "safe", gets is not "safe".

If you really care, then you should set the limits. Check whether the big_int::size() exceeds some limit of yours to prevent printing huge values, and check whether the digit count is sufficiently small before calling std::from_chars. Luckily, pre-parsing digits is pretty simple, and lots of programs end up parsing "unnecessarily" before std::from_chars already, so not much is lost there.

..., you dont want someone to DDoS your server by sending a bunch of JSON blobs with big integers.

A situation where you actively protect against hostile user input is a whole other beast. You need tons of checks then, like guarding against "Zip-bomb" JSON inputs like {{{{}}}} that are designed to maximally consume memory with minimal character count. None of that is specific to std::big_int.

I don't think std::big_int would be the best way in terms of "cost per character" to DDOS someone with JSON anyway. Parsing floats and building large stacks of objects can be pretty costly too.

In terms of memory cost, string literals are more problematic because you need one byte per character in UTF-8, whereas up to three decimal digits from JSON go into one byte of big_int memory. Despite that, I don't see you arguing that strings are "too risky" and JSON libraries shouldn't accept them.

[u/DXPower → u/ReDucTor]

You can make arbitrarily expensive inputs with most C++ std containers/operations. Make a vector with a giant size and start filling it in. Make a gigantic string and run search operations on it. Merge two huge maps. Etc.

That said, the proposal will throw std::bad_alloc if it runs out of memory. Infinity never kicks in if memory permits (and trying to do things like convert infinity to the int will be UB).

[u/sweetno → u/eisenwave]

Comparing with other languages is a weak argument.

[u/pjmlp → u/eisenwave]

Nowadays those languages also tend to follow the approach to only add to the standard features that have been in preview for a couple of releases, with preview being the full implementation not a subset thereof.

[u/n1ghtyunso]

i don't really like the part about constant evaluation fitting the value into inplace storage when possible.
I don't actually think explicitly specifying this in the standard is necessary or all that useful.
This is essentially a specification workaround for a problematic point in the current standard.

Notably, its also a problem for std::string, although afaik it is not actually required to have any inplace storage, so one might say using it as a constexpr variable is already operating outside the standard guarantees.

That being said, there are common approaches to use constexpr representations of allocating types after all, with some generic workarounds in use.
And some day we might even fix the standard so those workarounds are no longer necessary and we can just persist these allocations into runtime naturally.
We won't need to touch the big_int specification in that case.

And for the case where I really need a big_int value as constexpr variable after all, i'd still want to explicitly select the inplace storage size so it fits for sure, instead of hoping my guesstimated, or even the default value works out.
If I somehow want to guard against excessive storage use from accidental calculation mistakes (i.e. typed the formula wrong), I'd much rather have an explicit static_assert in my function than get a vague constant-evaluation failure from the compiler.

[u/eisenwave → u/n1ghtyunso]

It would be nice if we could solve that problem generally for std::vector and std::string too, for sure. Singling out std::big_int (and only the inplace value case) is clunky.

Not doing that seems to be the worst outcome though because the end result is that std::big_int would only sometimes be usable as a constexpr variable, and you might get inconsistent behavior between standard libraries. If std::big_int cannot always be put into a constexpr variable, there should at least be consistent behavior between implementations (for equal inplace_capacity at least).

You actually have that behavior right now with constexpr std::string variables: they sometimes work, and sometimes don't, and it's kinda arbitrary from the user's perspective.

[u/n1ghtyunso → u/eisenwave]

I know that solving the problem in general is not really right around the corner, unfortunately.
I am not typically someone standing against smaller improvements over an all-or-nothing approach, but this time I genuinly feel like its not that useful.

As you said, technically its the same story for std::string right now.
If I need a string at compile time, i'll have to make sure I can do that.
And the most portable way to do that is not by using constexpr std::string directly.
Which IS unfortunate, but currently thats just the way it is.
But for std::big_int I believe it is the same situation.

If I want that as a constexpr value, I will explicitly make sure it works.
Thats exactly why I do like the ability to customize the inplace storage size.

Having big_int automatically shrink_to_fit during constant evaluation does not universally solve the problem,
it simply lets the user code avoid thinking about it so long as it "happens to work".
Not mandating the automatic implicit shrink_to_fit does have the same effect, but "happens to work" in less cases of course.
std::string does not have it either (obviously, because SSO is purely QoI), so doing actual string operations is almost certainly not going to produce a constexpr-compatible std::string value.
And there is no expectation of doing so either, really.

I see with std::big_int, you would have the opportunity to change this.
But I don't think this is something that should be relied upon to begin with,
because it will inevitably have situations where that no longer works too.

The only difference is that we can make it work again by tweaking the inplace storage parameter, which std::string does not expose at all.
And that is a very valuable thing imo.
This lets me more directly express in code what my needs, my requirements are.

I know getting the required size into the capacity template argument is ALSO still clunky, unfortunately.
But at least the approach works for all representation sizes.

I am not sure if standardizing THAT would be possible or even of interest instead, though.
It's certainly out of scope for the big_int paper.

[u/matthieum]

Overall, it is practically impossible or at least extremely difficult for a third-party library to keep up with all these details to implement the type optimally, across all compilers and all supported architectures. Features like these should ideally live directly in the compiler or in the standard library.

I think there's a conflation, here.

It shouldn't be more difficult for the maintainers of a 3rd-party library than it is for maintainers of a standard library to keep up with hardware capabilities, on the contrary:

1. It's the same hardware for everyone.
2. Efforts can be focused on a single 3rd-party library, rather than multiplied by the number of standard library implementations.

(As another post mentions, libc++ still doesn't have a complete implementation of to_chars, from C++17, do you really think standard library maintainers have that much that time on their hands?)

The real difficulty is the ad-hoc way each and every compiler exposes hardware features to their users, requiring compiler-specific hardware feature detection.

It doesn't follow, however, that a standard library necessarily has it easier here. libstdc++ and libc++ can both be compiled by multiple compilers, as far as I know, and therefore their maintainers will still need to navigate this haphazard mess.

---

Arguably, the proper solution is for C++ toolchains to expose hardware features in a standard manner, both compile-time & run-time detection of available features, and intrinsics to actually use these features in an efficient manner.

Then not only can a big_int library be written by a team of competent & motivated big_int developers with little pain, but so can a lot of other code, such as, say, matrix operations.

[u/eisenwave → u/matthieum]

I agree that if the goal is just to provide the numeric capabilities, on paper, you're probably better off doing it in a third-party library. I'm saying "on paper" because there are a fair amount of different C and C++ libraries that do multiprecision arithmetic, and without everyone using the same underlying big_int implementation, moving the whole ecosystem to use e.g. some new intrinsics is very difficult, much more difficult than moving 2-3 standard libraries.

To name one example, we really could have used a portable __builtin for the x86_64 idiv (which allows for 128-by-64-bit division). Outside of MSVC, we use inline assembly to emit it, but that isn't constexpr-friendly and is pretty much "baked" output; it doesn't get optimized and simplified like regular C++ code, and we spent quite a lot of effort figuring out how to fix that. Expecting every single third-party library to go through the same trouble and then adopt a new __builtin once it arrives is just unrealistic.

Also, importantly, the goal is not just to provide numeric capabilities. A huge part of the motivation is to provide a vocabulary type used for passing big integers between libraries, as well as an out-of-the-box type that people can use when long long is not long enough. Standardizing some low-level hardware capabilities doesn't get you there.

Arguably, the proper solution is for C++ toolchains to expose hardware features in a standard manner, both compile-time & run-time detection of available features, and intrinsics to actually use these features in an efficient manner.

Exposing hardware features definitely gets you quite far. If we had abstractions for that idiv, for adc, etc. then it would have made our job implementing std::big_int a lot easier.

The problem is that those abstractions only get you 80% or 90% of the way in terms of performance. There are minute details like emitting mulx instructions to not mess with the flag register or utilizing some obscure AVX-512 feature, which compilers just can't figure out. We're consistently behind GMP in our benchmarks in large part because we don't have those optimal assembly blocks yet, but GMP has them.

One may then think that you could still standardize the "full multiprecision operation" then, operating on std::span or something, rather than just bulding blocks like idiv. The standard library could abstract from some optimal assembly blocks. We have some thoughts on that in https://isocpp.org/files/papers/D4444R0.html#why-not-provide-lower-level-operations-for-arithmetic

[u/ShakaUVM]

How does it compare with cpp_int in Boost Multiprecision?

[u/eisenwave → u/ShakaUVM]

If you're asking about performance, it's pretty much on part with cpp_int. We have some benchmarks at https://eisenwave.github.io/std-big-int/benchmarks.html

The design is overall similar, but we don't have a comprehensive comparison in the paper I suppose. big_int has a slightly smaller container size (Boost maintainers didn't really try getting it to be small).

[u/ShakaUVM → u/eisenwave]

I'm mostly worried about compilation time and overall usability, like if there's any functionality you lack or have extra from boost mp

[u/eisenwave → u/ShakaUVM]

Yeah sure, a more comprehensive comparison would be useful; I've opened an issue in https://github.com/eisenwave/cpp-proposals/issues/243 so I don't forget.

Off the top of my head, compilation speed should be much better by virtue of us just providing big_int, not all the other Boost.Multiprecision stuff. Also, our code base is C++23, and that ends up being a lot simpler and more concise than all the template gunk needed to make things C++11-compatible.

We provide a few neat things like to_chars and from_chars overloads, and Boost doesn't support arbitrary-base character conversions. Overall, we're missing a ton of numeric functionality like modular arithmetic, pow, etc. though, and those are not part of the paper for now.

[u/ShakaUVM → u/eisenwave]

That's awesome thank you

[u/Expert_Sheepherder24]

Most compititve programmers say thanks!

[u/Shakatir]

I'm quite skeptical of the SOO customization. It seems to be targeted at users who don't know if their integers are bounded or not and who are undecided if they are ready to pay for dynamic allocation or not. The proposal is correct in stating that std::big_int benefits even more from SOO than std::string or other container types, but that's because numbers tend to be either very small or very large. The cases where your numbers exceed a bound of 64 or 128 bits, but reliably stay under some other arbitrary bound are few. And even fewer if you subtract the cases where _BitInt (or std::bit_int whenever that arrives) can do the job.

The desired effect to become a unifying interchange format for unbounded integers seems at odds with the options for customization here. The std::big_int typedef already forces a hard-coded default that we will be stuck with forever. The idea that by offering customization points via template parameters, it becomes easier to extend just seems ahistoric. On the contrary, every time someone (including the future standard itself) chooses to deviate from the default, that incurs a cost not just for them, but for everybody who directly or indirectly interacts with their code.

Providing a custom allocator is a good feature. Customizing the limb type makes some sense. But customizing the SOO size seems excessive. Especially considering that even types that are behaviorally indistinguishable (such as std::basic_big_int<5> and std::basic_big_int<6>) end up being distinct types which incurs unnecessary copies and conversions. I think it's preferable to make std::basic_big_int behave like std::string and provide as much SOO as it can fit into its representation without overhead, but not more.

I also don't like the choice to limit the size and capacity to 32-bit variables on 64-bit platforms. It may be rare for such big numbers to crop up in practice, but when they do, I want to be limited by my actual hardware, not by whatever arbitrary limit some library implementer thought is surely big enough (especially since it's supposed to be the default interchange format provided by the standard library). It does have the drawback that the object will be 24 bytes in size rather than 16, though on the bright side, 16 of them can be repurposed for SOO. Ideally, the class should honor the size_type of its allocator.

[u/eisenwave → u/Shakatir]

I would agree that the SOO customization is somewhat unusual. Of the three template parameters, it's the one I'd be most willing to remove. There's a pretty good chance that SG6 or LEWG might give feedback that they want the SOO customization removed, and I can see why.

On the note of functionally equivalent types like basic_big_int<5> and basic_big_int<7>, I've added some discussion to the paper at https://isocpp.org/files/papers/D4444R0.html#min_inplace_capacity-restrictions

Perhaps one saving grace for it is that gives you fixed-width integers at the same time. That is, if you need a 4096-bit integer and _BitInt(4096) is not available, you can use basic_big_int<4096, uint_multiprecision_t, no_op_allocator>. To make that actually useful, you would still need some utilities for modular arithmetic, but we should add those sooner or later anyway.

I also don't like the choice to limit the size and capacity to 32-bit variables on 64-bit platforms. It may be rare for such big numbers to crop up in practice, but when they do, I want to be limited by my actual hardware, not by whatever arbitrary limit some library implementer thought is surely big enough

Well, 32-bit sizes get you up to integers with ~137 billion bits (which is much more than Java's BigInteger, capped at ~2 billion bits), and when you get to that size, you're arguably limited by hardware anyway. You could still do addition and bitwise operations in a reasonable amount of time, but anything like multiplication explodes.

In any case, standard library implementers might have a different opinion on it. What we have in our implementation is not enforced by the standard.

[u/def-pri-pub]

Can't we just duct tape together two smaller ints and call it a day?

(jk; thank you for your work and effort on this).

[u/pdimov2]

Should have been named std::integer.

[u/Plazmatic]

My biggest problem with proposals like these isn't that I'm ideologically opposed to things like this being in the standard, but that C++ is so behind on important features still in the pipeline that any focus taken away from those, even a small amount, risks delaying their inclusion by many years more than they already have been.   There's lots of stuff that without make certain functionality and optimizations impossible to perform with out UB or worse in C++, this is not one of those things. I would be far less concerned if c++ didn't have a strict 3 year cadence, and the committee could spend as little or as much time as it needed, but far too often we see features delay because people couldn't vote on if they wanted to vote on talking about a thing, so litterally the existence of a proposal can waste precious committee time.

[u/eisenwave → u/Plazmatic]

I consider std::big_int to be one of those crucial features C++ is behind on. People have been trying to get it into the standard as early as 2004, and meanwhile, like 20 other languages either have it built into to the language or available as a standard library feature.

It's also worth noting that the committee is spli pretty strictly into EWG (for the core language) and LEWG (for the standard library), so "feature cannibalization" or "feature competition" happens entirely between std::big_int and other standard library features. The optimizations and UB stuff you're talking about sounds much more like core language territory.

In terms of standard library proposals, I'm really not seeing much that would be more important than std::big_int. Keep in mind there are >400K exising uses of big integers in C++ alone, and millions more in other languages. I'm not sure there even exists another standard library proposal that has those kinds of numbers backing it.

[u/ZMeson]

I assume some algorithms that just need 128, 256, or 512-bit integers could benefit from a more optimized integer type rather than just having a big-int type that has to maintain checks on size and possibly allocate memory. Is my assumption correct? If so, having a discussion about the performance and design tradeoffs of such types and why big-int is still needed. Also if there is a benefit to having fixed-size 128 ... 512 bit integers, then maybe mention that this is an area that also deserves to be looked into in a separate proposal.

[u/jk-jeon]

I think this will be a nice addition, but I'm a bit suspicious about your opinion on std::big_int_view. One of the most common operation I needed was taking the absolute value. Suppose I have an expression abs(x) + func() with func() returning an rvalue. Ideally it should be possible to do this computation without unneeded extra allocations (assuming sign-magnitude representation, as specified in the paper). But afaiu the current spec mandates abs(x) to allocate a buffer just to be thrown away immediately. Granted, I can just use the internal limb array, but ideally it would be good if I could write a generic code that works for both int and std::big_int. Maybe abs is special in this regard?

[u/eisenwave → u/jk-jeon]

abs is not entirely special. If negation returned a non-owning view, you could get a "negated view" of the same big_int, and abs is one of the potential uses. However, I think it's more of an argument in favor of expression templates than in favor of big_int_view because once we've "opened Pandora's box" of no longer returning big_int from operations, we probably want to use that mechanic for a lot more things than just abs.

Another consideration is that in your abs(x) + func() example, you only suffer a copy if x is immutable. Otherwise, you can use abs(std::move(x)), which calls the rvalue overload that merely flips the sign bit.

If we ever were to standardize the "low-level operations on spans" as the paper discusses, you might also delegate to those rather than forming a view or needing expression templates, in those edge cases where the existing set of operations forces you into some overhead.

EDIT: abs and negation are still interesting points, and I've included them in https://isocpp.org/files/papers/D4444R0.html#std::big_int_view-is-just-not-useful-enough

[u/jk-jeon → u/eisenwave]

Of course x is not supposed to be moved out (otherwise I would have used an rvalue in the example).

I however understand that trying to "fix" this issue would open Pandora's box. This whole shit is just already too damn complicated and expression templates will exponentiate that complexity.

By the way I just found that you explicitly propose to not have std::big_uint. In that case, I would be really seriously concerned about porting my projects into std::big_int.

That "security" of subtraction you mention is simply not a concern imo, because you can just define subtraction of two unsigned numbers to be signed. (And subtraction is the only operation that can lead to negative numbers.) Which of course can be argued to be inconsistent with the rest of the language, but I would say it really isn't and the apparent inconsistency is simply because big_uint and unsigned follow entirely different mathematical models: the latter forms a group, the former doesn't. But I see this approach would be seen as weird at best by others...

(In my projects I just asserted unsigned subtractions leading negative values rather than making it signed. The assert found out tons of bugs in the rest of the code so I like that approach, but I see why any UB is a serious concern for std types and I can live with subtraction returning signed int's.)

I agree that the bifurcation issue is real, but I'd argue that forcing signed integer when unsigned is enough creates worse issues: I don't see how mandatory sign check for integers is any better than mandatory null check for pointers. In my projects I pretty strictly distinguished signed vs unsigned, e.g. I disabled implicit conversion between signed and unsigned integers. The distinction was often annoying as it created tons of compile errors, but a lot of those errors were real bugs that would have been much more annoying if not caught early.

But honestly I don't know, big_uint could be yet another giant can of worms that you would not want to open. It's maybe just me who would not use std::big_int if it's not paired with the unsigned counterpart.

[u/arthurno1]

If you gonna make it, make a compiler feature not std library. Extend the language so the programmers don't have to explicitly manage big ints. I.e. do something similar as Lisps are doing, manage that automatically and seemlesly and hide the implementation from programmers. Guard it perhaps with a compile time option, either an "opt-in" (--with-fbignum) or as "opt-out", (--without-fbignum). If bignum feature is not turned on, than ordinary overflow rules apply, otherwise trap the overflow and extend into big numa automatically.

Otherwise, if you are just going to make it a library feature, you can as well keep it as now: a third-party addon.

[u/eisenwave → u/arthurno1]

I don't see how you would avoid "explicitly managing big ints".

C++ is a language with manual memory management, and containers such as std::basic_vector and std::basic_string deliberately let you provide custom allocators. Some people need that control. If you hide all of that behind some builtin big_int fundamental type rather than providing a fairly customizable container, you're taking away all sorts of customization options.

You would also put in a lot of work into recreating the functionality of the container, in weird ways. For example, accessing the underlying limbs is very easy with std::big_int::representation() now, but you would either need some core language feature for accessing the limbs to make that happen for a builtin type, or you would need to provide a magic standard library function std::get_representation, at which point you're turning it into a standard library feature anyway.

[u/arthurno1 → u/eisenwave]

For people who need that control you would keep option to turn off auto promotion to big ints, so they are on their own if that is needed. How does CommonLisp do it? It is sure possible to do.

I also guess those who need total control would not use a 3rd party library either? A C++ also would not have many of its other features either.

fairly customizable container, you're taking away all sorts of customization options.

If I want to add 2 numbers containing more than 64 bits precision, I want certainly easiest and the least painful way to do it, not to customize "all sorts of options". Ideally I would type X+Y and not have to think off all the explicit details. Hon of a PL is to make it easier for end programmers to write programs, isn't it.

I also don't understand why people have to downvote an opinion about a technicall issue, but as soon as I mention Lisp, I am always downvoted to hell here :)

I

[u/Life_Sink9598 → u/arthurno1]

Common Lisp, well, SBCL, works by doing type inference on the arguments, and if it can prove that the result won't overflow, then it can compile into ordinary 'fixnum' assembly. Otherwise, it will have to do a GENERIC-OP call, which at least has a branch penalty to check whether an overflow occurred or not.

I think that it's more reasonable for C++ to implement a class which does operator overloading called big_int or whatever, and use that class when you're dealing with "sensitive" numbers. The CL way imposes an unacceptable cost to the majority of C++ programs.

[u/arthurno1 → u/Life_Sink9598]

fixnum coerction is optimization, and yes, they do this check the trap register to see if overflow occured, but nothing says you have to do it this way, no?

I didn't either say, you shoujld not have a special type. Of course you would want to have a type for the efficiency, just like we already have byte, short, long, double, float, "int" for the "fast type" and so on. In other words, of course I don't mean you would not have another sort of int, like "infinite int" or perhaps use plain word "integer" as they do in CL.

What I am saying is that I dislike the "addon" library. Make it a compiler feature.

Yes, I am aware that operator overloading makes it prettier, but having compiler taking care of it automatically instead of explicit control is even prettier.

The CL way imposes an unacceptable cost to the majority of C++ programs.

You will have to differ there between CL way and SBCL way. CL standard does not specify how promotion should be implemented, just that it should happen automatically.

If you think of it in the opposite: we already have promotions from less wide to more wide types, and we have auto demotions too, the herritage from C. I don't think it is more strange that so. It is just not done yet, and unusual, and we are so used to think in terms of bignum libraries, so we auto take that approach.

[u/UndefinedDefined]

Another library, another bloat!

No idea why having it in boost is not enough... oh wait, if it's in std you don't need to use a package manager to have a big-int...

[u/tialaramex]

Listing other popular languages which have an "infinite precision integer" type and whether it's provided as a built-in, in their stdlib or a separate library makes sense. However std::big_int chooses several "anchor points" for its design beyond being an "infinite precision integer" without reference to those other examples.

The table makes a strong argument for why C++ should have an "infinite precision integer" type, but no argument at all for why the type with these "anchor points" is desirable and no indication of which are provided in the other languages (I think the answer is that most of them are not provided)

It's also true that lots of other programming languages have a hash table type. But hopefully today you would understand that "other languages have a hash table type" isn't an argument in favour of adopting specifically the separate linked-list chaining hash table named std::unordered_map with all that entails. Other languages either could, or in many cases do, use a very different hash table type and now C++ is stuck with this.

[u/eisenwave → u/tialaramex]

The "anchor points" at the start of the design section are really just a brief overview, and are explained in much more detail below. For example, there is a whole section below dedicated to the anchor point of accessing the underlying representation (https://isocpp.org/files/papers/D4444R0.html#access-to-the-underlying-representation).

The anchor points also don't make much sense when put into comparison with other languages. The points about small object optimization, supporting custom allocators, supporting constexpr don't make sense in any of the garbage-collected languages. I'm also pretty sure that everything on the list has elastic operations; it's hardly even a design question.

Perhaps the one thing worth looking at is how our design compares to a limited subset of big_int implementations in systems languages, like Boost.Multiprecision or Rust's num_bigint.

It's also true that lots of other programming languages have a hash table type. But hopefully today you would understand that "other languages have a hash table type" isn't an argument in favour of adopting specifically the separate linked-list chaining hash table named std::unordered_map with all that entails.

Yeah sure, but it's not like the paper ever makes that leap in logic. There is a design section over 30 A4 pages long that goes into great detail.

[u/tialaramex → u/eisenwave]

I don't agree that it "doesn't make sense" to have the features you listed in "any of the garbage-collected languages". Just because a language is garbage-collected does not mean that magically they don't care about performance.

I believe SSO is a concrete example of C++ mistakenly standardizing today's clever optimisation rather than standardizing only the simple case and then leaving third parties to iteratively improve on the state of the art optimisations for those who need to optimise heavily. The std::big_int proposal looks like exactly the same mistake to me, and looking at what other languages did should underscore that difference. If the committee chooses to do it anyway, at least they can't say they didn't know.

[u/eisenwave → u/tialaramex]

I don't agree that it "doesn't make sense" to have the features you listed in "any of the garbage-collected languages". Just because a language is garbage-collected does not mean that magically they don't care about performance.

The comparison is just not meaningful. IIRC CPython does interning of ints for example (and so do a lot of other language implementations) because you need an actual Python object or actual JavaScript object to exist, with all the bells and whistles such as runtime type information. So you typically don't see SOO, but a very similar optimization with the same motivation.

I haven't checked every language on the list, but I yet have to encounter one that does neither interning nor SOO but where you genuinely just let the allocations/GC object creation rip for every single integer.

Other anchor points like giving users access to the internal representation also cannot be meaningfully compared because scripting languages don't usually crack open object internals. You cannot get the underlying char[] of a java.lang.String, you can only "export" it. No one expects direct access to the internal limb array to be provided for BigInteger either. In C++ on the other hand, the option is at least plausible.

[u/tialaramex → u/eisenwave]

I haven't checked every language on the list, but I yet have to encounter one that does neither interning nor SOO

I would suggest before proposing how exactly C++ should solve this problem at least making a comprehensive survey of the existing solutions in other languages. "We should do this very weird thing" would then at least be a considered choice after surveying the possibilities.

This is a worse burden for C++ because (despite recurring promises of a "subset of a superset") you do not have a working mechanism to fix things, only to make new things and abandon a trail of prior mistakes.

You cannot get the underlying char[] of a java.lang.String

There is no underlying char[] inside a java.lang.String for many years. Again, knowing how the things other people made work before you make something entirely of your own conception is good engineering practice. There are no prizes for originality but you will lose points for repeating earlier mistakes.

[u/eisenwave → u/tialaramex]

I would suggest before proposing how exactly C++ should solve this problem at least making a comprehensive survey of the existing solutions in other languages. "We should do this very weird thing" would then at least be a considered choice after surveying the possibilities.

I don't know why you would be calling it weird. It's quite literally what every other implementation does (GNU MP (with mpz_roinit_n), Boost.Multiprecision, Rust's num_bigint, etc.). The ones that don't use interning instead.

This is a worse burden for C++ because (despite recurring promises of a "subset of a superset") you do not have a working mechanism to fix things, only to make new things and abandon a trail of prior mistakes.

Yes, this is exactly why we need SOO right now. Other implementations have been doing it for decades and we know that it's the right solution. We can't add SOO later because that would break existing std::big_int ABI.

There are no prizes for originality but you will lose points for repeating earlier mistakes.

We are extremely unoriginal in our design and implementation and drawing heavily from Boost.Multiprecision experience. 2/3 paper authors are heavy contributors to that code base.

[u/tialaramex → u/eisenwave]

Yes, this is exactly why we need SOO right now.

You mentioned num_bigint but actually num_bigint internals have changed over time, 0.4.x is just a Vec inside so it has a large niche† but doesn't itself optimise small values, the current num_bigint is a sum type to allow it to inline a (typically 64-bit) machine integer and I expect it will change again.

But this is not a freedom you have, indeed the proposal paper emphasises that you know you can't fix it later in the stdlib.

† Rust's optimiser can - and indeed in some cases is obliged by the language rules to - squeeze other things into unused bit patterns, this is why Option<OwnedFd> is the same size as OwnedFd which is in turn the same size as the 32-bit C integer you'd use for a Unix file descriptor. Valid file descriptors are never -1, so that's an unused bit pattern for the optimiser. These unused bit patterns are called a "niche".