Is __int128 Integral? A Survey | Hacker News Reader

Is __int128 Integral? A Survey

quuxplusone.github.io

41 pointsingve20 comments

It is also useful to know that int128 is not supported as well across all architectures. For example std::atomic<int128>::is_always_lock_free is true for recent x86 architectures but not for PPCs.

Not only that, it's not even supported at all on some architectures. Clang supports int128 but not on armv7-a: https://gcc.godbolt.org/z/5dKh6s

Neat! x86_64 has CMPXCHG16B. Learn something new every day.

It has to - to mitigate ABA problem.

Depending what you use it for.

The bigger problem with it is you can't just load/store a 128 bit value without this instruction. An SSE 128bit load/store is turned into two 64 bit operations under the hood. So to actually get atomic loads and stores you need to use this very expensive compare exchange operation. That really limits the number of algorithms it's useful for.

Why would it? The crucial part is usually a variation of comparing and swapping a 64 bit pointer and a 64 version number at the same time.

If you can do that, for most algorithms it doesn't matter much if you do two 64 bit loads to get the values. If you are out of sync your compare and swap is going to fail anyway, which is likely to be rare.

I've personally found it limiting many times. I know the one place where I did actually end up using it, I had 128 bits of information where I had to be very careful with ordering of loads and stores and had to detect torn writes and retry.

Maybe my experience is not representative, but it's something to be aware of when designing algorithms with it.

Why would you need to do that unless you were writing over individual 128 bit ints from one thread while reading them at the same time from another thread?

There are many better ways to do something like that. Anything that writes a buffer, then makes it available atomically would work much better, or you could just use the compare and swap.

There is always going to be a limit of what is atomic. At some point you have to work with a data structure meant for larger data. The cut off has to be somewhere.

It was the primary key index in a database using MVCC. It stored various flags and a version (transaction timestamp) and data pointer. It also stored something else that I don't recall, maybe a previous version record pointer. All packed into 128 bits. Adding a new record version required cmpxchg16b, but reading it or just updating a flag was tricky because the 64bit words only had meaning together so I had to detect torn writes and retry the read with appropriate memory barriers.

This means though, that you were somehow synchronizing a larger record using this technique. Maybe you were writing it in one thread, then atomically changing your 128 bit struct to make it available to other threads.

Whatever else was part of your 128 bit struct could probably be part of the record instead. You could use a 64 bit address and a 64 bit version number. Looking up could be done by atomically reading the 64 bit version number only. Writing a new record would then require the compare and swap.

Yes, that's correct, that's actually the obvious way to write it. I think the logic behind putting it in the index was to be able to check the transaction timestamp without the extra indirection and cache miss, and to have that information there if the data is on disk, and there is no record loaded in memory. Not having the indirection was a big deal for the cache eviction algorithm which sampled many records and then evicted the coldest %, weighted for frequency of access and size.

There are other ways of doing that though, I'm not sure the trade off was the best one in the end.

Right, so it isn't about lots of algorithms being prevented, it is actually a pretty reasonable constraint and not a huge deal.

If you were worried about cache and indirection, the indices could be aligned to the start of a 64 byte or 128 byte boundary, since 64 bytes is the cache line size but (Intel) cpus will load two cache lines at a time. Because of this, loading in your 64 bit/8 byte index should mean that the 120 bytes after it are going to be cached.

Let’s keep 80s music out of this ;)

Looks like I need to resort to ASM for visual c++. Might do.

Are you sure about that? 128 bit compare and swap has been on x64 for two decades and ARM has it too. I thought PPC also had it.

None of these (as far as I know) can actually do a 128 bit compare and swap when it straddles two cache lines however.

These also aren't the same as doing actual 128 bit math operations, they are just for compare and swap.

Every time I see those new types, I keep thinking about the missed opportunity way back in the language design, to provide a generic syntax like int<N>, and then just gradually add mandatory support for N=64, 128 etc in new language versions as needed.

It's not like it's even some new or radical idea - something like that was the original source of the C syntax for ints. To remind, the actual type names are not "short", "int", and "long", but rather "short int", "int", and "long int" - that is, "short" and "long" are qualifiers, just like "signed" and "unsigned"; it's just that you can omit "int". This all comes from ALGOL 68, where that scheme was explicitly generic - the language spec allowed for arbitrarily many SHORT and LONG before INT (or REAL). Implementations were then expected to use as many as they needed to express the types available on the architecture they were targeting.

Or better yet, the way Ada did it:

   x: Integer;
   y: Integer range 1 .. 1000;
   z: Float digits 10

zig has this:

> In addition to the integer types above, arbitrary bit-width integers can be referenced by using an identifier of i or u followed by digits. For example, the identifier i7 refers to a signed 7-bit integer. The maximum allowed bit-width of an integer type is 65535

intmax_t is a beast in itself https://news.ycombinator.com/item?id=25316933

Maybe it ought to be deprecated in future revisions of the standard.

Is there a different behaviour in C?

intmax_t throws a wrench into the mechanism for adding proper extended width integer types where "integer" is understood in the context of the C standard. intmax_t is defined as "a signed integer type capable of representing any value of any signed integer type". But in practice intmax_t is never made as large as any supported 128-bit types because it would break existing ABIs. In real-world environments 128-bit types are stuck in a grey area of the C standard, incapable of becoming first-class integer types. And it's ironic because part of the idea behind intmax_t was to make it easier to introduce and use extended width integer types.

I'm not sure if GCC had a 128-bit type before 64-bit ABIs were defined, but IIRC its 128-bit type didn't properly support all arithmetic operations until long after modern 64-bit ABIs, including the amd64 ABI, were finalized, so it wouldn't have been possible to specify a 128-bit intmax_t at the time.

There are several proposed amendments to the C standard to address the situation, either by deprecating intmax_t or changing its definition and requirements.

By contrast, the long long type (64-bit minimum width) was added to 32-bit ABIs without a problem because GCC and other compilers added long long support years before intmax_t was introduced with the C99 standard. If intmax_t was already a thing then adding long long to 32-bit ABIs would have been problematic, although there may have been more motivation to deal with the issue in the C standard.

Reply on news.ycombinator.com