News for hackers. Stuff that matters.
Re:Counting bytes fast by jevinskie on Saturday September 27, 2014 @09:32PM (#8378688)
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.
Re:Counting bytes fast by userbinator on Sunday September 28, 2014 @01:34AM (#8379028)
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
Re:Counting bytes fast by nkurz on Sunday September 28, 2014 @02:11AM (#8379082)
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).

Re:Counting bytes fast by userbinator on Sunday September 28, 2014 @02:28AM (#8379102)
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.

Re:Counting bytes fast by zvrba on Sunday September 28, 2014 @03:00AM (#8379147)
> 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.

Re:Counting bytes fast by nkurz on Sunday September 28, 2014 @03:41AM (#8379188)
This Intel Forum post entitled "AVX-512 is a big step forward - but repeating past mistakes" addresses some of these issues: https://software.intel.com/en-us/forums/topic/477541

The debate is essentially whether AVX-512 is making a mistake by giving up 8-bit and 16-bit operations. Agner feels it's a mistake, but other smart people argue that it's not a problem.

Re:Counting bytes fast by innocenat on Sunday September 28, 2014 @06:40AM (#8379393)
And those has been added back in AVX512BW.
Re:Counting bytes fast by nkurz on Sunday September 28, 2014 @02:02PM (#8380415)
Thanks! That's big news, and I'd missed it: https://software.intel.com/en-us/blogs/additional-avx-512-in...
Re:Counting bytes fast by Narishma on Sunday September 28, 2014 @07:13AM (#8379437)
There seems to be only one person in that thread arguing that it's not a problem.
Re:Counting bytes fast by dbaupp on Sunday September 28, 2014 @02:21AM (#8379093)
AVX-512 has 32 512-bit registers.
Re:Counting bytes fast by dbaupp on Saturday September 27, 2014 @09:43PM (#8378710)
Is there an efficient way to take a byte and increment the appropriate location of the appropriate register?
Re:Counting bytes fast by nkurz on Saturday September 27, 2014 @11:41PM (#8378854)
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?

Re:Counting bytes fast by pmalynin on Sunday September 28, 2014 @12:48AM (#8378964)
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.
Re:Counting bytes fast by nkurz on Sunday September 28, 2014 @02:04AM (#8379075)
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.

Re:Counting bytes fast by userbinator on Sunday September 28, 2014 @01:03AM (#8378978)
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.)
Re:Counting bytes fast by pmalynin on Sunday September 28, 2014 @01:07AM (#8378983)
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.
Re:Counting bytes fast by nialo on Saturday September 27, 2014 @10:39PM (#8378779)
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.

Re:Counting bytes fast by pmalynin on Saturday September 27, 2014 @11:03PM (#8378812)
Right. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.
Re:Counting bytes fast by acqq on Sunday September 28, 2014 @04:43PM (#8380859)
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.