Counting bytes fast
fastcompression.blogspot.com
Counting bytes fast
1–10 of 50 posts
Re: Counting bytes fast
#2It seems what you really want is probability for different symbols. Have you considered estimating them by sampling?
Re: Counting bytes fast
#3Thanks 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.
Re: Counting bytes fast
#4It seems what you really want is probability for different symbols. Have you considered estimating them by sampling?
If 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.
Re: Counting bytes fast
#5I 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...
Re: Counting bytes fast
#6interestingly this is the kind of tasks where i fear languages with no pointer exposed may be slower. Any one has a good comparison?
Re: Counting bytes fast
#7I 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.
Re: Counting bytes fast
#8If 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
Re: Counting bytes fast
#9So 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?
Re: Counting bytes fast
#10So 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.