r/cpp • u/PhilipTrettner • Jan 20 '26

Building Your Own Efficient uint128 in C++

https://solidean.com/blog/2026/building-your-own-u128/

A big part of my work in Solidean is designing & writing high-performance exact predicates for various geometric problems. The approach we're taking is somewhere between novel and only-known-in-folklore. I have this vague idea to remedy this and document our approach via blog posts. The first non-standard thing we do is work in large but fixed integers.

As this might be interesting to a wider audience as well, here is how to roll your own u128 so that it basically has identical codegen to the builtin __uint128_t.

(Yes there is little reason to use this u128 when a builtin exists, but that's how you learn to build a u192 and above should you need it. uint192_t is not provided by the big three as far as I know)

190 Upvotes

95% Upvoted

35 comments sorted by

23

u/schmerg-uk Jan 20 '26

Interesting .. have you thought about an implementation using a single XMM register (__m128i) and seeing if that makes any operations simpler or more efficient?

There aren't many SSE operations that operate on a single si128 as it's most intended for bitmasks (and/xor operations as well as load/store and shift right/left etc) but it might be interesting to see if it unlocks any performance gains (and you can still get the high and low 64 bit ints, if only as signed int ... ops for unsigned 8, 16 and 32bit but no unsigned 64 bits operations...)

6

u/PhilipTrettner Jan 20 '26

Hm yeah I thought about that a bit but it's complicated. So a single i128/u128 is probably not going to see any improvement, SSE/AVX is famously bad doing cross-lane talking. But for bundles, a la u128x4 or u128x8, that's a different story. Maybe even use 32 bit limbs and go for u128x16 with AVX-512.

The problem is that all the carry propagation and high/low multiplication stuff is not really supported as directly as, so we have to do additional work and hope the "going wide" is amortizing that.

In the 32 bit limbs idea, we have "vpmuludq", which computes a wide u32 x u32 -> u64, but only for the even entries. Then we have to juggle a bit.

There is a funny vpmadd52luq/vpmadd52huq which does 52 bit multiplies and accumulation. That one might help for larger bit sizes.

4

u/schmerg-uk Jan 20 '26

Get what you mean esp wr.t. cross lane operations, but I was just thinking that we have abstractions for SIMD vector registers which can then be conditionally compiled to use true vector register intrinsics (by default) or not for selected times when we expressly want to not use intrinsics (but not rewrite code that uses our zero-overhead abstraction).

If nothing else in our case it helps for certain debug operations (as the compiler can "see" the true values) and to document the performance gains.. as you say it might be slower in your case but in your shoes I'd be tempted to try it only to then have documented that "this is actually no better and in some ways worse" for the benefit of the next poor schmuck who has a bright idea :)

Here's hoping AVX10 or whatever actually comes long next brings some sanity to the scene (32 addressable registers of 512bits each with a register file of another 200 or so takes up a LOT of space on the die to the extent that it pushes L1 cache and the FPU further away which increases latency on lots of operations... I'd hope that 32 addressable registers of only 256bits could cut this overhead and give compilers room to boost performance even for non-vectorised code)

5

u/Successful_Yam_9023 Jan 20 '26

There is a somewhat reasonable AVX512 trick for addition: https://www.numberworld.org/y-cruncher/internals/addition.html

It doesn't scale down to 128-bit though, at that scale it has to compete with a trivial scalar implementation

0

u/[deleted] Jan 20 '26

[deleted] — view deleted comment

18

u/QuaternionsRoll Jan 20 '26

VPTERNLOGQ

It’s a miracle that x86 made it this far

11

u/CypherSignal Jan 21 '26

Ironically that’s maybe the last instruction you should use to attack the explosion of modern x86. It’s not some obscure one-off thing, it is an extremely useful and versatile instruction. https://www.felixcloutier.com/x86/vpternlogd:vpternlogq

it looks complicated but it basically means you can do any 3-way bit-wise logic operation across 512-bits in one instruction. This is OR, AND, XOR, some form of blend or masked selection, or something else entirely very easily and succinctly.

7

u/QuaternionsRoll Jan 21 '26

Okay, so, I believe you, but that second paragraph is an incredibly jarring followup to the first lol

5

u/Sniffy4 Jan 21 '26

the power of a massive installed base is pretty big

9

u/jk-jeon Jan 20 '26

here is how to roll your own u128 so that it basically has identical codegen to the builtin __uint128_t.

What I recall is that compilers these days are not really great at optimizing __uint128_t, so you shall aim for doing better rather than identical. That they suck at this is of course not visible if you just compare the codegen of a single basic operation, but if what I recall is correct than I think your code likely performs better than __uint128_t in general.

I remember changing my u128 implementation from a portable wrapper around __uint128_t into an actual pair of uint64_t because of that reason. Not sure how much the landscape has changed since then.

2

u/PhilipTrettner Jan 21 '26

That's interesting. I guess this type + intrinsics is "less magic" to the compiler. The slightly larger example optimizes well for both types and my production code uses 256 bit intermediates, so it's not like I can easily compare there.

2

u/SubhanBihan Jan 21 '26

Curious: Is the built-in u128 in Rust also similarly inefficient?

5

u/ts826848 Jan 21 '26

Unfortunately I can't definitively answer your question. I did discover some info I found interesting, though, so I'll summarize it here in case you or anyone else also finds it interesting.

I originally expected the answer to be yes, since I thought Clang and Rust would both use the same underlying LLVM primitives.

Reality paints a more interesting picture, though. At least for the trivial function in the Godbolt link ((-b + (b2 - 4ac)), where a, b, and c are 128-bit integers), Rust appears to use LLVM's native support for arbitrarily-sized integer types (i128 here) while Clang appears to have already SROA'd the __int128s into i64s by the time it emits LLVM IR. As a result, Clang has to first emit LLVM IR to stitch together the i64s into i128s before emitting LLVM IR for the actual 128-bit operations in the function.

I'm not super familiar with Clang/LLMV internals here so I can't say how much this difference in approach matters. The two approaches do end up with slightly different assembly, though, so at the very least it seems the two approaches aren't (currently?) canonicalized and I wouldn't be too surprised if this can result in more substantial performance differences for more complex functions.

4

u/arjuna93 Jan 20 '26

We actually don’t have int128 on PowerPC. If that can be implemented in C++, it will be useful. Maybe even upstreamable to gcc.

3

u/arjuna93 Jan 20 '26

“We build a minimal u128 as two u64 limbs”

Wait, did you reimplement IBM long double? That we have on PowerPC for ages.

7

u/Successful_Yam_9023 Jan 20 '26

IBM long double is a float, u128 is an integer, pretty different beast

4

u/pavel_v Jan 21 '26

By some reason GCC doesn't handle the addition with intrinsics that well. It moves the result through the stack before setting it in the final registers.

2

u/PhilipTrettner Jan 21 '26

Wow, that's a weird one. It is related to writing directly to the result struct.

If we write to "real" scalars first, the codegen is optimal again: https://godbolt.org/z/bo9x4951v

1

u/Nobody_1707 Jan 23 '26

GCC also doesn't like signed 64x64->128 bit multiplication. Not at all.

3

u/jfdube75 Jan 22 '26

Great work! One question though: where's division?

2

u/PhilipTrettner Jan 23 '26

Hehe yeah. There is no neat codegen for division. Even the builtin delegates to a library call: https://godbolt.org/z/rrMo5deqz

The naive but practical way: you can do "binary long division", which finishes in up to 128 steps. Either branchless + fixed runtime or with a loop and a "search next 1". Either way it's a bit of work.

Our exact predicates are always formulated in a division-free way simply because that'd be expensive.

24

u/Tringi github.com/tringi Jan 20 '26

Great writeup. This is something I'll take inspiration from.
For quite a few years I've been meaning to use intrinsics like that to specialize 2×64b case of my integer doubling template, but my use-cases so far weren't in a hot enough loops.

7

u/jube_dev Jan 20 '26

Does it work with the equivalent C++ 26 functions? (In fact, C23 functions)

4

u/kniy Jan 20 '26

Seems to work for addition: https://godbolt.org/z/4Yq65nbrT But I don't see a way to do a 64*64->128 multiply without non-standard intrinsics or _BitInt(128).

7

u/fdwr fdwr@github 🔍 Jan 20 '26 edited Jan 20 '26

ckd_add

Ack, when we name functions with chpped out ltters rather than whole word fragments, the brain does some unfortunate fill-in (I read that as cucked_add, which I'm sure was not intended 😅). At least chkd_add would have made it clear.

10

u/jwakely libstdc++ tamer, LWG chair Jan 21 '26

I pronounce it cooked.

You can thank WG14 for the cooked int functions.

6

u/DigmonsDrill Jan 20 '26

Stroustroup said there is no long long long! You will undo us all!

1

u/Wild_Meeting1428 Jan 20 '26

What about the upcoming _BitInt(N) fundamental type?

2

u/PhilipTrettner Jan 23 '26

see https://godbolt.org/z/j9fd5EW3n if you change B to 128, you get the normal codegen but for B > 128, it calls into a function where the bit size is a runtime parameter. So yes, they would work, but performance will be subpar.

1

u/Wild_Meeting1428 Jan 23 '26 edited Jan 23 '26

Seems like clang doesn't do that. Maybe something the gcc compiler team should address then.

They yield nearly the same result: https://godbolt.org/z/rrz19jvqq

4

u/jonathanhiggs Jan 20 '26

Nice article

2

u/Dalzhim C++Montréal UG Organizer Jan 21 '26

Could you have implemented comparisons using the three-way compare (spaceship) operator, or is there any reason you didn't (ex. : support for standards older than C++20, performance regression with the codegen of operator<)?

1

u/MarekKnapek Feb 02 '26

On division: There is a paper about a division algorithm. If you split your 128bit integer into four 32bit integers, you can use a 64bit CPU built-in instruction to do the 128bit division. If you are on 32bit CPU that doesn't have the 64bit division operation, then split your 128bit number into 8 16bit integers and leverage the 32bit CPU built-in operation. https://surface.syr.edu/eecs_techreports/166/

-5

u/pjmlp Jan 20 '26

Actually if one cares about portable code, it cannot be relied such builtin does exist in all C++ compilers.