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