6 ms·

I wonder what would happen if you used AVX-512 registers to store the byte distribution. You could use 16 of the 32 512 bit SIMD registers instead of relying on

I wonder what would happen if you used AVX-512 registers to store the byte distribution. You could use 16 of the 32 512 bit SIMD registers instead of relying on memory. AVX-256 would require 32 SIMD registers but it has just 16 available.

dbaupp 12y ago
Is there an efficient way to take a byte and increment the appropriate location of the appropriate register?
- nialo 12y ago
  I am not an assembly programmer, and there is probably a better way, but something neat that thinking about this resulted in: If instead of 16 512bit registers, we simply want to increment the appropriate section of one big register, we can add 2^(byte * n), where byte is the value of the byte in question, and n is the number of bits we're using to count the results.
  - pmalynin 12y ago
    Right. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.
    - acqq 12y ago
      Actually, you can add one 512-bit register with another 512 bit register in a single instruction. You won't get a carry from a segment to a segment but nialo's general idea can be implemented. How fast it can be done is another topic.
- nkurz 12y ago
  No, there is not. There are reasonable branch free ways to increment one of the low 16 bytes of an XMM register (shift and add), and slower ways to increment any of the low 32 bytes in a single YMM register (permute and add). Interestingly, a lookup table that loads the appropriate addend vector is surprisingly fast as well. But there is no branch free way to select which of several AVX/AVX2 registers to work with. But I'd be happy to be wrong -- maybe there is a way to address them using the older stack oriented FPU instructions?
  - pmalynin 12y ago
    If one is willing to write self-modifying code, then it is possible to overwrite VEX.vvvv instruction encoding with the register select, so for example to select XMM0/YMM0 you'd have VEX.1111 (one's complement) or for XMM15/YMM15 VEX.0000.
    - userbinator 12y ago
      Unfortunately although SMC could be shorter, it's even slower since the pipeline gets flushed every time a write occurs to locations within the current fetch window (not sure exactly how long that is, but it's not small.)
      - pmalynin 12y ago
        Yes, and the instruction cache becomes stale as well. I guess one way to avoid is to have 16 code blocks back-to-back and then to do a like a jmp into the section that contains the right register. JMP are pretty cheap, and the end point is likely to be in cache anyway.
    - nkurz 12y ago
      My first thought was that this was an interesting approach, but that there was no speed advantage because of the cache flush and pipeline reset. But maybe it could be made to work... What if instead of overwriting an existing instruction, you generated the instructions you needed and appended them to a new writable and executable buffer. Then every 100/1000/1000000 characters, you terminate it with a 'ret' and 'call' into it. It branchlessly updates the set of XMM/YMM/ZMM registers you are using without touching memory. Repeat until you've read to the end of your input, then store the vector register results by writing their contents out to RAM in a known order. Perhaps you cycle between a few buffers so that the address you are calling into is never cached. Overkill, but it seems like this might actually be pretty fast, presuming you can generate the instructions fast enough. I've considered this technique before for fast integer decompression when trying to avoid branch errors, but never so far as to actually test it.
userbinator 12y ago
With the newer extensions like AVX it looks like there are so many registers that it makes sense to have some sort of addressing mode that treats them like RAM. I mean, there are 2048 bytes of storage available there. It would be great if they could be accessed as 2048 bytes, 1024 words, 512 dwords, or 256 qwords. Something like this... inc dword ptr AVX:[eax] ; low 9 bits of eax are used as index into the register set
- nkurz 12y ago
  I agree that this would occasionally be a very useful feature. Any idea if this would be architecturally feasible? Might it be similar to modern a GPU's "register file"? Maxwell (current generation NVidia) has 64KB of registers. How did you come up with 2048 bytes for x64, though? I get 16 * 32B = 256 if I count logical registers, or 168 * 32B = 5376 if I count physical (for Haswell).
  - dbaupp 12y ago
    AVX-512 has 32 512-bit registers.
  - userbinator 12y ago
    Architecturally, it would merely be a matter of taking the register selection bits not from the instruction itself but from some other source, like another register; there will certainly be a bit more complexity due to dependencies etc. 2048 bytes since AVX-512 has 32 registers, each 512 bits (64 bytes) wide.
    - zvrba 12y ago
      > Architecturally, it would merely be a matter of taking the register selection bits Except these do not exist for individual SIMD lanes; that's why you have permutation instructions. Treating individual lanes as registers would increase the needed number of addressing bits, which I'm sure would complicate stuff much more than "just" changing the possible source.

dbaupp 12y ago

Is there an efficient way to take a byte and increment the appropriate location of the appropriate register?

nialo 12y ago
I am not an assembly programmer, and there is probably a better way, but something neat that thinking about this resulted in: If instead of 16 512bit registers, we simply want to increment the appropriate section of one big register, we can add 2^(byte * n), where byte is the value of the byte in question, and n is the number of bits we're using to count the results.
- pmalynin 12y ago
  Right. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.
  - acqq 12y ago
    Actually, you can add one 512-bit register with another 512 bit register in a single instruction. You won't get a carry from a segment to a segment but nialo's general idea can be implemented. How fast it can be done is another topic.
nkurz 12y ago
No, there is not. There are reasonable branch free ways to increment one of the low 16 bytes of an XMM register (shift and add), and slower ways to increment any of the low 32 bytes in a single YMM register (permute and add). Interestingly, a lookup table that loads the appropriate addend vector is surprisingly fast as well. But there is no branch free way to select which of several AVX/AVX2 registers to work with. But I'd be happy to be wrong -- maybe there is a way to address them using the older stack oriented FPU instructions?
- pmalynin 12y ago
  If one is willing to write self-modifying code, then it is possible to overwrite VEX.vvvv instruction encoding with the register select, so for example to select XMM0/YMM0 you'd have VEX.1111 (one's complement) or for XMM15/YMM15 VEX.0000.
  - userbinator 12y ago
    Unfortunately although SMC could be shorter, it's even slower since the pipeline gets flushed every time a write occurs to locations within the current fetch window (not sure exactly how long that is, but it's not small.)
    - pmalynin 12y ago
      Yes, and the instruction cache becomes stale as well. I guess one way to avoid is to have 16 code blocks back-to-back and then to do a like a jmp into the section that contains the right register. JMP are pretty cheap, and the end point is likely to be in cache anyway.
  - nkurz 12y ago
    My first thought was that this was an interesting approach, but that there was no speed advantage because of the cache flush and pipeline reset. But maybe it could be made to work... What if instead of overwriting an existing instruction, you generated the instructions you needed and appended them to a new writable and executable buffer. Then every 100/1000/1000000 characters, you terminate it with a 'ret' and 'call' into it. It branchlessly updates the set of XMM/YMM/ZMM registers you are using without touching memory. Repeat until you've read to the end of your input, then store the vector register results by writing their contents out to RAM in a known order. Perhaps you cycle between a few buffers so that the address you are calling into is never cached. Overkill, but it seems like this might actually be pretty fast, presuming you can generate the instructions fast enough. I've considered this technique before for fast integer decompression when trying to avoid branch errors, but never so far as to actually test it.

userbinator 12y ago

With the newer extensions like AVX it looks like there are so many registers that it makes sense to have some sort of addressing mode that treats them like RAM. I mean, there are 2048 bytes of storage available there. It would be great if they could be accessed as 2048 bytes, 1024 words, 512 dwords, or 256 qwords. Something like this... inc dword ptr AVX:[eax] ; low 9 bits of eax are used as index into the register set

nkurz 12y ago
I agree that this would occasionally be a very useful feature. Any idea if this would be architecturally feasible? Might it be similar to modern a GPU's "register file"? Maxwell (current generation NVidia) has 64KB of registers. How did you come up with 2048 bytes for x64, though? I get 16 * 32B = 256 if I count logical registers, or 168 * 32B = 5376 if I count physical (for Haswell).
- dbaupp 12y ago
  AVX-512 has 32 512-bit registers.
- userbinator 12y ago
  Architecturally, it would merely be a matter of taking the register selection bits not from the instruction itself but from some other source, like another register; there will certainly be a bit more complexity due to dependencies etc. 2048 bytes since AVX-512 has 32 registers, each 512 bits (64 bytes) wide.
  - zvrba 12y ago
    > Architecturally, it would merely be a matter of taking the register selection bits Except these do not exist for individual SIMD lanes; that's why you have permutation instructions. Treating individual lanes as registers would increase the needed number of addressing bits, which I'm sure would complicate stuff much more than "just" changing the possible source.