3 ms·

I doubt it the slow version uses division instead of bit shifting. My guess would be the fast version saturated like i/o or some non cpu portion of the processo

by gmm1990 3y ago

I doubt it the slow version uses division instead of bit shifting. My guess would be the fast version saturated like i/o or some non cpu portion of the processor and the division one was bottle necked by the division logic in the processor.

bogwog 3y ago
But it's iterating through the result vectors twice, so that's basically guaranteed to miss. Moving the threshold check into the loop above would at least eliminate that factor. Maybe division vs bit shifting does play a factor, but it's hard to compare that while the cache behavior is so different.
cogman10 3y ago
Recalibrate how you feel about division and multiplication. It turns out, integer division on new processors is a 1 cycle process (and has been for a while now). Most of the multicycle instructions now-a-days are things like SIMD and encryption.
- jandrewrogers 3y ago
  Which processor has 1-cycle latency for integer division? Even Apple Silicon, which has the mostly highly optimized implementation I am aware of appears to have 2-cycle latency. Recent x86 are much worse, though greatly improved. Integer division is much faster than it used to be but not single cycle. Also, most of those SIMD and encryption instructions can retire one per cycle on modern cores, but that isn't the same as latency.
  - cogman10 3y ago
    You are correct, I mistakenly thought it was 1/cycle because I had previously remembered IMUL taking 30 cycles (and now it has a 1 cycle throughput). Agner Fog is reporting anywhere from 4->30 cycles on semi-recent architectures.
  - gpderetta 3y ago
    2-cycle latency for division seems extremely unlikely. From the instruction tables it seems that firestorm has 7-9 cycles latency SDIV (which is excellent). It also has an impressive 2-cycles reciprocal throughput.
    - jandrewrogers 3y ago
      Quite possible. I am not confident Apple Silicon has 2-cycle div latency, that seems improbably fast to me, but I had heard some reasonably well-sourced rumors to that effect. I have not measured it myself. Even at somewhat higher latency it is still fast enough to not be worth optimizing around in most cases, which is great.

bogwog 3y ago

But it's iterating through the result vectors twice, so that's basically guaranteed to miss. Moving the threshold check into the loop above would at least eliminate that factor. Maybe division vs bit shifting does play a factor, but it's hard to compare that while the cache behavior is so different.

cogman10 3y ago

Recalibrate how you feel about division and multiplication. It turns out, integer division on new processors is a 1 cycle process (and has been for a while now). Most of the multicycle instructions now-a-days are things like SIMD and encryption.

jandrewrogers 3y ago
Which processor has 1-cycle latency for integer division? Even Apple Silicon, which has the mostly highly optimized implementation I am aware of appears to have 2-cycle latency. Recent x86 are much worse, though greatly improved. Integer division is much faster than it used to be but not single cycle. Also, most of those SIMD and encryption instructions can retire one per cycle on modern cores, but that isn't the same as latency.
- cogman10 3y ago
  You are correct, I mistakenly thought it was 1/cycle because I had previously remembered IMUL taking 30 cycles (and now it has a 1 cycle throughput). Agner Fog is reporting anywhere from 4->30 cycles on semi-recent architectures.
- gpderetta 3y ago
  2-cycle latency for division seems extremely unlikely. From the instruction tables it seems that firestorm has 7-9 cycles latency SDIV (which is excellent). It also has an impressive 2-cycles reciprocal throughput.
  - jandrewrogers 3y ago
    Quite possible. I am not confident Apple Silicon has 2-cycle div latency, that seems improbably fast to me, but I had heard some reasonably well-sourced rumors to that effect. I have not measured it myself. Even at somewhat higher latency it is still fast enough to not be worth optimizing around in most cases, which is great.