3 ms·
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.
by kabdib 12y ago
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.
- 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.