Re:Counting bytes fast
by bodyfour on Saturday September 27, 2014 @09:11PM
(#8378644)
The cost of an unpredicted branch inside the loop would probably outweigh the benefit.
[ Parent
| on HN ]
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.
Good point about prefetch.
The U16 version can probably benefit from a test for the first 256 values, and leave the remainder of the range as vanilla counters. You might get a win for less than 128 on the first test, in fact.
Re:Counting bytes fast
by rcthompson on Sunday September 28, 2014 @06:48PM
(#8381111)
Ah yes, branch prediction would kill this approach pretty badly. Data-dependent branching = bad.