5 ms·

128 bit address space is overkill, but I wonder if a hardware-backed 128 bit integer type would be useful for bit twiddling - or whether spreading the bits over

128 bit address space is overkill, but I wonder if a hardware-backed 128 bit integer type would be useful for bit twiddling - or whether spreading the bits over two 64-bits integers is 'good enough' assuming that both halfs reside in the same cache line, and it's unlikely that a single bit twiddling operation needs to affect both halfs. I guess I will find out soon because I started a home computer emulator experiment in Zig where I'm essentially mapping mainboard wires to bits in a wide integer, and where 64-bits definitely won't enough, but 128 bits most likely will cover most target systems. Very curious about the x86-64 and ARM compiler output.

yjftsjthsd-h 2y ago
> 128 bit address space is overkill, but I wonder if a hardware-backed 128 bit integer type would be useful for bit twiddling - or whether spreading the bits over two 64-bits integers is 'good enough' assuming that both halfs reside in the same cache line, and it's unlikely that a single bit twiddling operation needs to affect both halfs. Don't we already have that? My reading of https://en.wikipedia.org/wiki/Advanced_Vector_Extensions https://en.wikipedia.org/wiki/Advanced_Vector_Extensions is that AVX starts at 128-bit and goes up from there.
- flohofwoe 2y ago
  Yeah, but can compilers actually do the necessary magic when encountering something like: x = ((y & (1<<101)|(1<<102)) >> 10); My impression was always that the vector extensions are good for SIMD operations, but not "wide integer" operations, but I might be wrong of course (e.g. is bit-shifting across "lanes" even possible?)
  - acchow 2y ago
    It's not really a compiler issue tho. SIMD is meant to pointwise map an operation across multiple "lanes" in a single operation. You can't have lane interdependence on the result.
    - LegionMammal978 2y ago
      (V)PALIGNR shifts between lanes just fine, but only with byte granularity.
      - acchow 2y ago
        Because of the byte granularity, there's no interdependence between lanes. The result within a lane is not affected by the values of the other lanes.
  - eigenket 2y ago
    On 64 bit computers you've been able to use 128 bit unsigned ints as a gcc extension for a long time now and the bit twiddling stuff works exactly as you'd expect. The relevant types are __int128 / unsigned __int128. Clang has something similar and my understanding is that c23's _BitInt will let you do this.
    - flohofwoe 2y ago
      Yes, but compilers seem to disagree on whether they use a pair of 64-bit registers, or an SSE register under the hood (reusing link from a reply): https://godbolt.org/z/xEqrx5dY4 https://godbolt.org/z/xEqrx5dY4
  - jcranmer 2y ago
    As it turns out, yes: https://godbolt.org/z/xEqrx5dY4 https://godbolt.org/z/xEqrx5dY4 SSE2 adds the PSRL/PSLL operators, which are basically i128 shift operators on vector registers (i.e., shift continues between lanes), so you can pretty easily map i128 to vector registers if you're only doing and/or/xor/shifts.
    - pbsd 2y ago
      The 128-bit wide shifts PS{L,R}LDQ only have byte granularity. They're a special case of a byte shuffle.
      - acchow 2y ago
        The "Q" at the end is "quadword", so it's 64 bits (8 bytes).
        pbsd 2y ago
        No, you're thinking of PS{R,L}LQ.
    - acchow 2y ago
      No, it doesn't shift across 64-bit boundaries. Take a look at the gcc output in your link ``` movdqa xmm0, XMMWORD PTR [rdi] movdqa xmm1, xmm0 psrlq xmm0, 10 psrldq xmm1, 8 psllq xmm1, 54 por xmm0, xmm1 movdqa xmm1, XMMWORD PTR .LC0[rip] ``` That's a lot of psr and psl instructions for a "single 128-bit wide shift"...
pclmulqdq 2y ago
I am actually currently working on a CPU that has an auxiliary unit with a 521-bit integer type (although many instructions are 512-bit). These have some interesting effects, but I can't say they are tremendously useful for bit hacks, at least not at the cost of the hardware to support them. Multiplications of this size are a very costly operation, for example. Even an addition or a leading zero count is a significant area. Vector units are about as good as you will get for most of this stuff. This unit, by the way, is intended primarily for cryptography (521 is the length of a large mersenne prime). Cryptography operations are the only times I have ever seen an integer wider than 64 bits in the wild, and most people use bignum libraries. The same pressures apply to 128-bit cores. It will make a lot of hardware a lot bigger and more complicated.
- Findecanor 2y ago
  Aren't there physical limits to how large integers you can add with carry at once per GHz?
  - pclmulqdq 2y ago
    Not when you build the CPU. You can pipeline the operation. All these ops have very long latency.
kryptiskt 2y ago
128 bits of address space would be useful if you're building an architecture with one level of storage. And there actually has been one family of computers that have used 128-bit pointers. IBM S/38 and its successors did that. It has a machine independent instruction set that is then compiled down to actual machine code, and that uses 128-bit pointers for future proofing.
- cduzz 2y ago
  I thought this was where optane was going to take us, back to the days of "your memory is also your persistent storage" like an old PDP/8 with core memory...
- RetroTechie 2y ago
  There have been a few research OSes designed around a concept of "all memory is persistent". Iirc this allows some simplifications. For example, no need for a file system: the copy-from-disk-to-RAM is pointless when there's no difference between RAM & disk. This didn't catch on as the tech to make it practical wasn't there. And existing OSes were 'good enough' due to memory-mapped files, smart caching techniques etc. Plus boatloads of software using that. But if all background storage were treated as one giant RAM, I could see some cloud/AI big boys crossing that 64-bit size boundary. Or some science/engineering projects like CERN. That said: it's the apps, really. If OS + biggest app working sets easily fit in a 64-bit address space, then why throw 2x the bits at it? And disk <-> RAM transfers (+filesystems, cache etc) are a solved problem.

yjftsjthsd-h 2y ago

> 128 bit address space is overkill, but I wonder if a hardware-backed 128 bit integer type would be useful for bit twiddling - or whether spreading the bits over two 64-bits integers is 'good enough' assuming that both halfs reside in the same cache line, and it's unlikely that a single bit twiddling operation needs to affect both halfs. Don't we already have that? My reading of https://en.wikipedia.org/wiki/Advanced_Vector_Extensions https://en.wikipedia.org/wiki/Advanced_Vector_Extensions is that AVX starts at 128-bit and goes up from there.

flohofwoe 2y ago
Yeah, but can compilers actually do the necessary magic when encountering something like: x = ((y & (1<<101)|(1<<102)) >> 10); My impression was always that the vector extensions are good for SIMD operations, but not "wide integer" operations, but I might be wrong of course (e.g. is bit-shifting across "lanes" even possible?)
- acchow 2y ago
  It's not really a compiler issue tho. SIMD is meant to pointwise map an operation across multiple "lanes" in a single operation. You can't have lane interdependence on the result.
  - LegionMammal978 2y ago
    (V)PALIGNR shifts between lanes just fine, but only with byte granularity.
    - acchow 2y ago
      Because of the byte granularity, there's no interdependence between lanes. The result within a lane is not affected by the values of the other lanes.
- eigenket 2y ago
  On 64 bit computers you've been able to use 128 bit unsigned ints as a gcc extension for a long time now and the bit twiddling stuff works exactly as you'd expect. The relevant types are __int128 / unsigned __int128. Clang has something similar and my understanding is that c23's _BitInt will let you do this.
  - flohofwoe 2y ago
    Yes, but compilers seem to disagree on whether they use a pair of 64-bit registers, or an SSE register under the hood (reusing link from a reply): https://godbolt.org/z/xEqrx5dY4 https://godbolt.org/z/xEqrx5dY4
- jcranmer 2y ago
  As it turns out, yes: https://godbolt.org/z/xEqrx5dY4 https://godbolt.org/z/xEqrx5dY4 SSE2 adds the PSRL/PSLL operators, which are basically i128 shift operators on vector registers (i.e., shift continues between lanes), so you can pretty easily map i128 to vector registers if you're only doing and/or/xor/shifts.
  - pbsd 2y ago
    The 128-bit wide shifts PS{L,R}LDQ only have byte granularity. They're a special case of a byte shuffle.
    - acchow 2y ago
      The "Q" at the end is "quadword", so it's 64 bits (8 bytes).
      - pbsd 2y ago
        No, you're thinking of PS{R,L}LQ.
  - acchow 2y ago
    No, it doesn't shift across 64-bit boundaries. Take a look at the gcc output in your link ``` movdqa xmm0, XMMWORD PTR [rdi] movdqa xmm1, xmm0 psrlq xmm0, 10 psrldq xmm1, 8 psllq xmm1, 54 por xmm0, xmm1 movdqa xmm1, XMMWORD PTR .LC0[rip] ``` That's a lot of psr and psl instructions for a "single 128-bit wide shift"...

pclmulqdq 2y ago

I am actually currently working on a CPU that has an auxiliary unit with a 521-bit integer type (although many instructions are 512-bit). These have some interesting effects, but I can't say they are tremendously useful for bit hacks, at least not at the cost of the hardware to support them. Multiplications of this size are a very costly operation, for example. Even an addition or a leading zero count is a significant area. Vector units are about as good as you will get for most of this stuff. This unit, by the way, is intended primarily for cryptography (521 is the length of a large mersenne prime). Cryptography operations are the only times I have ever seen an integer wider than 64 bits in the wild, and most people use bignum libraries. The same pressures apply to 128-bit cores. It will make a lot of hardware a lot bigger and more complicated.

Findecanor 2y ago
Aren't there physical limits to how large integers you can add with carry at once per GHz?
- pclmulqdq 2y ago
  Not when you build the CPU. You can pipeline the operation. All these ops have very long latency.

kryptiskt 2y ago

128 bits of address space would be useful if you're building an architecture with one level of storage. And there actually has been one family of computers that have used 128-bit pointers. IBM S/38 and its successors did that. It has a machine independent instruction set that is then compiled down to actual machine code, and that uses 128-bit pointers for future proofing.

cduzz 2y ago
I thought this was where optane was going to take us, back to the days of "your memory is also your persistent storage" like an old PDP/8 with core memory...
RetroTechie 2y ago
There have been a few research OSes designed around a concept of "all memory is persistent". Iirc this allows some simplifications. For example, no need for a file system: the copy-from-disk-to-RAM is pointless when there's no difference between RAM & disk. This didn't catch on as the tech to make it practical wasn't there. And existing OSes were 'good enough' due to memory-mapped files, smart caching techniques etc. Plus boatloads of software using that. But if all background storage were treated as one giant RAM, I could see some cloud/AI big boys crossing that 64-bit size boundary. Or some science/engineering projects like CERN. That said: it's the apps, really. If OS + biggest app working sets easily fit in a 64-bit address space, then why throw 2x the bits at it? And disk <-> RAM transfers (+filesystems, cache etc) are a solved problem.