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.
Counting bytes fast
11–20 of 50 posts
Re: Counting bytes fast
#12So 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…
I did a test on this as well. It approaches the speed of distributed version only if there are a lot of consecutive bytes. The distributed version is fast in any case.
Re: Counting bytes fast
#13I 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.
Can you share your test harness and implementations? This would be fun to tinker with. =)
Re: Counting bytes fast
#14I 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.
Is there an efficient way to take a byte and increment the appropriate location of the appropriate register?
Re: Counting bytes fast
#15I 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.
Can you share your test harness and implementations? This would be fun to tinker with. =)
[deleted]
Re: Counting bytes fast
#16So 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.
This 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.
Re: Counting bytes fast
#17I 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.
Which architecture i5? i5 doesn't tell us very much more than Xeon.
Re: Counting bytes fast
#18It 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.
I think you may be a few years out in that. The hash DoS's were discovered about 11 years ago. Time flies eh?
Re: Counting bytes fast
#19I 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.
Is there an efficient way to take a byte and increment the appropriate location of the appropriate register?
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
#20Earlier quoted context omitted.
The cost of an unpredicted branch inside the loop would probably outweigh the benefit.
This 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.
I 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.