6 ms·
Counting bytes fast
- im3w1l 12y agoIt seems what you really want is probability for different symbols. Have you considered estimating them by sampling?
- 0x0 12y agoIf the sampling is deterministic, it sounds like you'd risk malicious input being able to cause pathological results? Not unlike the various hashmap DoS'es from a couple of years ago.
- 0x0 12y agoThanks for this post! I've known about the massive effects of optimizing for cache lines but this is the first time I've heard of the write commit delay. Great example as well.
- nkurz 12y agoI 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 is a great recent article on the topic: http://blog.stuffedcow.net/2014/01/x86-memory-disambiguation/ http://blog.stuffedcow.net/2014/01/x86-memory-disambiguation...
- sitkack 12y agoPretty sure this would help. https://software.intel.com/en-us/node/513929 https://software.intel.com/en-us/node/513929 Author should have supplied test code and a benchmark suite.
- danbruc 12y agoHow 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.
- sitkack 12y agothe avx registers have 512 bytes of storage.
- nkurz 12y agoThe 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.
- sitkack 12y agoDuring 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 <- load 64 bits from ram JUMP A1 @A0 SHIFT R8 @A1 R9 load low 8 bits to register pc += R9 * SIZEOF_AVX_INCR_ROUTINE 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/ https://software.intel.com/sites/landingpage/IntrinsicsGuide...
- zobzu 12y agointerestingly this is the kind of tasks where i fear languages with no pointer exposed may be slower. Any one has a good comparison?
- readerrrr 12y agoI did a quick test on an i5( Ivy Bridge ) proc using c, and surprisingly when on a non-random table, the distributed version retained the speed of a random table, while the single version became 2.5x slower.
- infogulch 12y agoIf I remember correctly, the Mill wouldn't have this issue, since all stores go through the cache hierarchy (by default) so they finish as soon as it's in L1 (~3 cycles typically). It's then evicted down through the cache and into to main memory as usual, while retaining consistent aliasing semantics automatically. I may have misunderstood, but this is covered in more detail in the memory talk I believe: http://youtu.be/bjRDaaGlER8 http://youtu.be/bjRDaaGlER8
- rcthompson 12y agoSo 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 twice in a row. Assuming that the compiler can fit all the necessary temporary variables into registers, wouldn't this eliminate the problem entirely? Or would this be so much extra work that the processor becomes the bottleneck instead of writes to memory?
- bodyfour 12y agoThe cost of an unpredicted branch inside the loop would probably outweigh the benefit.
- kabdib 12y agoThis code is generating tons of D-cache misses, at the cost of hundreds of cycles (in a modern x86 memory system), so you can afford a branch miss now and then.
- nkurz 12y agoI don't think this is correct. The input is sequential, so the hardware prefetcher should be very successful: the only misses will be 1/4096 for the first entry into a new 4KB page, and even this could be avoided with a single judicious software prefetch. He's counting 8-bit bytes, and thus has 256 entries per table. Using 64-bit counters, this is 8 * 256 = 2048 contiguous bytes per table. 4 tables gets him up to 8KB. Modern L1D is 32KB. Alternatively viewed, 1700MB/s is 1.7 billion table additions per second. A processor is running at about 3.5 GHz, which is 3.5 billion cycles per second. Thus his current algorithm is takes ~2 cycles per byte. A branch prediction errors costs 15 cycles, and thus would be relatively very expensive. You'd probably be right for the 16-bit U16 version, though.
- 12y ago
- jevinskie 12y agoI 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 agoIs there an efficient way to take a byte and increment the appropriate location of the appropriate register?
- nialo 12y agoI 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 agoRight. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.
- acqq 12y agoActually, 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 agoNo, 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?
- deleted 12y ago[deleted]