3 ms·
The cost of an unpredicted branch inside the loop would probably outweigh the benefit.
by bodyfour 12y ago
The 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.
- kabdib 12y agoGood 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.
- rcthompson 12y agoAh yes, branch prediction would kill this approach pretty badly. Data-dependent branching = bad.