go
go copied to clipboard
golang
proposal: spec: add support for int128 and uint128
it's good for UUID, IPv6, hashing (MD5) etc, we can store IPv6 into uint128 instead byte slice and do some mathematics with subnetworks, checking range of IP addresses
These use cases are not strong enough to justify adding 128-bit types, which is a big task to emulate it on all targets.
- MD5 is not secure anymore, so there is little benefit adding types to store its result.
- How often do you need to manipulate a UUID as a number rather than a byte slice (or a string)?
- The other use cases can be done with math/big just as easy.
Also note that GCC doesn't support __int128 on 32-bit targets and Go do want consistent language features across all supported architectures.
I agree with you there aren't a lot of benefits for int128/uint128, maybe a little better performance for comparing and hashing in maps when we use uint128 for storing UUID/IPv6 because for byte slices or string we need do some loops and extra memory but it isn't important I think
In addition to crypto, UUID and IPv6, int128 would be enormously helpful for volatile memory analysis, by giving you a safe uintptr diff type.
It also just makes code that much more readable if you have to deal with large IDs e.g. those you get back from google directory API amongst others (effectively they're uuids encoded as uint128).
Obviously you can use math/big but it makes the code much harder to reason about because you have to parse the code mentally first, distracting you from reading the code.
Adding a data point: ran into a situation with a current project where I need to compute (x * y) % m where x*y can possibly overflow and require a 128-bit integer. Doing the modulus by hand for the high and low halves is needlessly complicated.
The examples of UUID and IPv6 are not convincing to me. Those types can be done as a struct just as easily.
It's not clear that this is worth doing if processors do not have hardware support for the type; are there processors with 128-bit integer multiply and divide instructions?
See also #19623.
@ianlancetaylor I do not think so. GCC seems to use the obvious 6 instructions for mul, 4 for add and sub, and a more involved routine for quo. I'm not how anybody could emulate mul, add, or sub that precisely (in Go) without assembly, but that prohibits inlining and adds function call overhead.
The fact that the current tools can't yet inline asm code is not in itself an argument for changing the language. We would additionally need to see a significant need for efficient int128 arithmetic.
If there were hardware support, that in itself would suggest a need, since presumably the processor manufacturers would only add such instructions if people wanted them.
If there were hardware support, that in itself would suggest a need
A need that—presumably—compilers couldn't meet by adding their own 128-bit types, which they have. I mean, for all but division it's a couple extra instructions. For most cases that's been sufficient.
I confess I'm not an expert on CPU characteristics, but my understanding is much of the driving force behind adding larger sizes was the ability to address more memory. That makes me think general 128-bit support is rather unlikely.
Yet major compilers have added support (GCC, Clang, ICC, ...) for C and C++. Rust has them because of LLVM. Julia has them as well.
Other languages and compilers having support isn't sufficient reason to make a language change, sure. But it's evidence there exists a need other than simply UUIDs.
Their domain seems to lie in cryptography and arbitrary-precision calculations, for now.
Additional usecases are timestamps, cryptographic nonces and database keys.
Examples like database keys, nonces and UUID represent a pretty large collection of applications where keys/handles can't ever be reused or number ranges can't overlap.
@FlorianUekermann People keep saying UUID, but I see no reason that a UUID could not be implemented using a struct. It's not like people use arithmetic on a UUID once it has been created. The only reason to add int128 to the language is if people are going to use arithmetic on values of that type.
It's not like people use arithmetic on a UUID once it has been created
They do. UUIDs don't have to be random. Sequential UUIDs are common in databases for example. Combine sequential UUIDs with some range partitioning and you'll wish for integer ops in practice.
Still, timestamps seem like the most obvious example to me, where 64bit is not sufficient and the full range of arithmetic operations is obviously meaningful. Had it been available, I would expect that the time package contained some examples.
How big of an undertaking is the implementation of div? The rest seems rather straightforward.
How big of an undertaking is the implementation of div?
The code for naïve 128-bit division exists in the stdlib already (math/big). The PowerPC Compiler Writer’s Guide has a 32-bit implementation of 64-bit division (https://cr.yp.to/2005-590/powerpc-cwg.pdf, page 82) that can be translated upwards.
Use case: [u]int128 can be used to check for overflow of [u]int64 operations in a natural way. Yes, this could make you want int256, but since int64 is the word size of many machines, this particular overflow matters a lot. See e.g. #21588. Other obvious options to address this use case are math/bits and #19623.
Somewhat related use case: https://github.com/golang/go/issues/21835#issuecomment-356478304.
If there were hardware support, that in itself would suggest a need
The ADX and BMI2 ISA extensions are implemented by recent Intel and AMD processors.
For example MULX does 128bit=64bit*64bit.
are there processors with 128-bit integer multiply and divide instructions
There are instructions that let you multiply two 64-bit registers to two 64-bit registers. Having access to those in the form of uint128 can significantly speed up cryptographic code, which might reduce our reliance on assembly implementations.
An example from what I'm looking at today: https://github.com/mit-plv/fiat-crypto/blob/f7b212b9/src/Specific/X25519/C64/femulDisplay.log
(I am however also very much unconvinced by the data storage use cases: there's no reason to store hashes or foreign IDs as numbers if you are not doing arithmetic on them. []byte is fine.)
How about (uint64, uint64) -> (uint64, uint64) math/bits intrinsics if not uint128 in the language?
[...] Unfortunately, this requires writing assembly, because writing high-performance arithmetic is not possible in Go — it's simply not a design goal of the language. (There are a few reasons, most notably that there's no way to directly compute the (128-bit) product of 64-bit integers.)
https://blog.cloudflare.com/sidh-go/
How about (uint64, uint64) -> (uint64, uint64) math/bits intrinsics if not uint128 in the language?
How would the API work? ISTM there's two options:
- Each function takes two
uint64and returns the upper and lower halves and it's DIY with the results, or - Each function takes two
uint64returns atype Uint128 [2]uint64that has various methods
#1 has the downside of not making arithmetic operations any easier. For example, one use case is convolutions in a prime field. If you need to compute (a * b) % p then getting the upper and lower halves of the 128-bit multiplication of a and b means you still need to do the modulus by hand.
#2 seems to just be a clumsy wrapper for a builtin uint128 type.
(BTW: I don't want to shoot down your idea right off the bat, and I'd rather have bits.Uint128 than nothing—those two issues just stood out to me.)
I'd much appreciate atomic.CompareAndSwapUint128 (or CASDoubleUint64(*[2]int64 to avoid language change), since double-word CAS makes it easy to implement tagged (or version) pointers to prevent ABA problem in lockless algorithms.
If we add these types, we will presumably need to change at least the strconv package to support converting int128 (and uint128) from string to integer. This will require new functions, as the existing functions take int64 arguments. What should these new functions be called? What should we do if we decide to add int256 in the future?
The math/big package might need new setters and getters.
What packages other than strconv should change if we add these types?
(By the way, #24813 seems to be working well for the cryptography use case, so we don't really need the uint128 type for that anymore.)
Everything related to currencies/finance should be done in fixed-point ... and the 18 digits of precision you get with int64 is not enough. It seems to me that 'int128' and 'uint128' should be reserved words in the language ... even if you choose not to implement it at this time.
@michaelthoward That's not necessary, as none of the predeclared type names like int, int64, etc., are reserved words. They are declared in the "universe block" and can be shadowed by names defined in package scope.
none of the predeclared type names like int, int64, etc., are reserved words
Thank you for explaining
The Snowflake data warehouse supports int128, and the type is useful for anything from IPv6 addresses, to time-plus-ID serials that sort well. (I e, 64 bit nanosecond timestamp in high order, 64-bit random node id in low order.)
The most-generic option would be support for array-as-int-of-fixed-size, which is different from the math/big.Int type. I e, I could pass in a [16]byte, or a [32]byte, or a [6]byte, or whatever, and the compiler would perhaps have smarts enough to generate better code in cases where that's possible?
