4 ms·

So 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

So 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?

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

bodyfour 12y ago

The cost of an unpredicted branch inside the loop would probably outweigh the benefit.

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 ago
  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.
  - kabdib 12y ago
    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.
rcthompson 12y ago
Ah yes, branch prediction would kill this approach pretty badly. Data-dependent branching = bad.

readerrrr 12y ago

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.