Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Counting bytes fast

fastcompression.blogspot.com

Post reply on HN
Print view View original

41–50 of 50 posts

Re: Counting bytes fast

#41

Post by nkurz »

innocenat wrote: post #37
nkurz wrote: post #34

Earlier quoted context omitted.

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.

And those has been added back in AVX512BW.

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

#42

Post by nkurz »

sitkack wrote: post #40
danbruc wrote: post #35

Earlier quoted context omitted.

How could packed addition help for this task? The project description on GitHub says benchmarking happens on a »Intel Core i5-3340M (oc'ed to 3.0GHz)« so maybe the article is based on numbers from the same machine.

the avx registers have 512 bytes of storage.

The space is there, but it's difficult to see how to make use of it for this problem. You'd need to be able to use an 8-bit input value to choose which position in which register to update. Incrementing the position (pos = input % 32) is possible, though not as straightforward as you might hope.

But choosing which of the vectors to update (vecX where X = input / 32) doesn't have a good answer without requiring unpredictable branching. There's a thread elsewhere on this page where we muse about the possibility of using self-modifying code, but otherwise I don't know of any answer.

Re: Counting bytes fast

#43

Post by Tractor4973 »

sitkack wrote: post #31
nkurz wrote: post #5

I wish the author would have been more specific about the processor being tested. This is the sort of thing that is extremely dependent on the microarchitecture of processor used. I wonder if he's testing on AMD or older Intel? Modern Intel chips usually do an very good job of "store-to-load forwarding" when the load is the same size or smaller than the store. Although it's testing a slightly different effect, this i…

Pretty sure this would help. https://software.intel.com/en-us/node/513929 Author should have supplied test code and a benchmark suite.

Actually, the test code and the benchmark suite are present within the FSE project (linked from the article)

Re: Counting bytes fast

#44

Post by Tractor4973 »

danbruc wrote: post #35
sitkack wrote: post #31

Earlier quoted context omitted.

Pretty sure this would help. https://software.intel.com/en-us/node/513929 Author should have supplied test code and a benchmark suite.

How could packed addition help for this task? The project description on GitHub says benchmarking happens on a »Intel Core i5-3340M (oc'ed to 3.0GHz)« so maybe the article is based on numbers from the same machine.

Yes it is

Re: Counting bytes fast

#45

Post by acqq »

pmalynin wrote: post #21
nialo wrote: post #19

Earlier quoted context omitted.

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.

Right. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.

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.

Re: Counting bytes fast

#46

Post by rcthompson »

bodyfour wrote: post #10
rcthompson wrote: post #9

So the problem is when the same byte occurs 2 or more times in rapid succession, right? Couldn't you use a temporary variable to count the number of consecutive occurrences of the same byte, and then once you hit a different byte, add the total consecutive count to the appropriate slot? That way you only write to the count table once for each run of identical bytes, and you never write to the same slot of the table t…

The cost of an unpredicted branch inside the loop would probably outweigh the benefit.

Ah yes, branch prediction would kill this approach pretty badly. Data-dependent branching = bad.

Re: Counting bytes fast

#47

Post by sitkack »

nkurz wrote: post #42
sitkack wrote: post #40

Earlier quoted context omitted.

the avx registers have 512 bytes of storage.

The space is there, but it's difficult to see how to make use of it for this problem. You'd need to be able to use an 8-bit input value to choose which position in which register to update. Incrementing the position (pos = input % 32) is possible, though not as straightforward as you might hope. But choosing which of the vectors to update (vecX where X = input / 32) doesn't have a good answer without requiring unpred…

During my morning boot (awakening) I was thinking about the self modifying code solution. I don't think it is needed and that it would eat up lots of memory bandwidth. I think a 256 entry jump table is sufficient which could be inlined so

    R8
Each AVX_INCR_ROUTINE would be the same size and have an absolute jump back to A0. There would need to be a DEC counter so the whole thing was only done 8 times. Also memory reads could be interleaved during the count or use the AVX register for a destination directly from memory. But it seems like a waste if there are already 64 bit registers sitting there.

If one used U16 counters, every 65k elements read would need to sweep through and write the high buckets out to 32 bit counters to prevent overflow.

I don't yet have any solid evidence but I think using the AVX registers for histogram storage could enable histogramming at the read bandwidth of main memory.

https://software.intel.com/sites/landingpage/IntrinsicsGuide...

Re: Counting bytes fast

#48

Post by nkurz »

sitkack wrote: post #47
nkurz wrote: post #42

Earlier quoted context omitted.

The space is there, but it's difficult to see how to make use of it for this problem. You'd need to be able to use an 8-bit input value to choose which position in which register to update. Incrementing the position (pos = input % 32) is possible, though not as straightforward as you might hope. But choosing which of the vectors to update (vecX where X = input / 32) doesn't have a good answer without requiring unpred…

During my morning boot (awakening) I was thinking about the self modifying code solution. I don't think it is needed and that it would eat up lots of memory bandwidth. I think a 256 entry jump table is sufficient which could be inlined so R8 Each AVX_INCR_ROUTINE would be the same size and have an absolute jump back to A0. There would need to be a DEC counter so the whole thing was only done 8 times. Also memory read…

I don't think any approach based around a jump table is going to perform well. The issue is that modern processors use speculative execution, and have a deep pipeline that needs to be refilled whenever the wrong path is chosen. A jump table and an cmp/jc are predicted in the same way, but the jump table is usually harder to predict. Every time the prediction is wrong, you lose ~15 cycles. The 4-table approach describes takes about 2 cycles per byte, so there isn't much room for error.

The whole idea of "the" program counter is almost gone. You can still set it to affect program behaviour, but in reality there is a "reorder buffer" filled with instructions from an "execution window" that are issued by the backend as soon as their dependencies are available, and the front end has a mostly independent "speculative pc" that is fetching and decoding instructions 10-100 cycles ahead of the current execution window. The guess as to which execution path will be taken at the jump table will probably be made even before the load is issued to get the address.

Per your earlier recommendation, I did read through "Inner Loops". It's a really good book, and offers a great overall approach to programming, but this is one of the places where the details of modern processors have changed so much that the older approach is counterproductive. To be competitive for this task, you probably need to be branch free, so that you have speculative execution working with you rather than against you.

Re: Counting bytes fast

#49

Post by sitkack »

nkurz wrote: post #48
sitkack wrote: post #47

Earlier quoted context omitted.

During my morning boot (awakening) I was thinking about the self modifying code solution. I don't think it is needed and that it would eat up lots of memory bandwidth. I think a 256 entry jump table is sufficient which could be inlined so R8 Each AVX_INCR_ROUTINE would be the same size and have an absolute jump back to A0. There would need to be a DEC counter so the whole thing was only done 8 times. Also memory read…

I don't think any approach based around a jump table is going to perform well. The issue is that modern processors use speculative execution, and have a deep pipeline that needs to be refilled whenever the wrong path is chosen. A jump table and an cmp/jc are predicted in the same way, but the jump table is usually harder to predict. Every time the prediction is wrong, you lose ~15 cycles. The 4-table approach describ…

I see your point. I am going to try and implement the approach I outlined above as well as the code gen. Glad you checked out "Inner Loops", I a guess my take away from that book is understand the machine, your code and most of all do some science. The hardware used the book is very dated, and I'd love to see a second edition using SkyLake or newer.

Maybe ... instead of doing the JMP back to the top of the loop, you combine the two approaches to like a direct threaded interpreter. In each AVX_INCR_ROUTINE modify the code by over writing the next JMP address, don't jump back to A0. The issue of consecutive duplicates arrises again.

Or ask the processor for some L1 cache that never gets flushed to main memory.

Or use R8-R15 as an 8x8 array of U8 counters, do 4 passes [0-63] [64-127] [128-191] [192-255] or a 4x8 array of U16 counters, would have to test.

    Function    Best Rate MB/s  Avg time     Min time     Max time
    Copy:           11569.0     0.145255     0.138301     0.154563
    Scale:          11383.5     0.145140     0.140555     0.148503
    Add:            12544.6     0.196920     0.191318     0.204782
    Triad:          12464.8     0.198199     0.192542     0.207492
from http://www.cs.virginia.edu/stream/FTP/Code/stream.c

I still think the histogramming can get above 6GB/s

Re: Counting bytes fast

#50

Post by sitkack »

nkurz wrote: post #48
sitkack wrote: post #47

Earlier quoted context omitted.

During my morning boot (awakening) I was thinking about the self modifying code solution. I don't think it is needed and that it would eat up lots of memory bandwidth. I think a 256 entry jump table is sufficient which could be inlined so R8 Each AVX_INCR_ROUTINE would be the same size and have an absolute jump back to A0. There would need to be a DEC counter so the whole thing was only done 8 times. Also memory read…

I don't think any approach based around a jump table is going to perform well. The issue is that modern processors use speculative execution, and have a deep pipeline that needs to be refilled whenever the wrong path is chosen. A jump table and an cmp/jc are predicted in the same way, but the jump table is usually harder to predict. Every time the prediction is wrong, you lose ~15 cycles. The 4-table approach describ…

The entropy in those counter writes is a single bit, so most of the traffic is zeros. INCR and CAS needs to be built into the ram.
Post reply on HN