61–70 of 75 posts
Earlier quoted context omitted.
See https://godbolt.org/z/3Yqbceaza for what godbolt says clang produces. Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63.
> Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63. You can use __builtin_assume for this: https://godbolt.org/z/K4jKhxnTq
The compiler is already reducing integer division by a constant into these things. Those algorithms become more important when you're dividing by a value known at runtime but which remains the same during parts of the program. That's where libdivide comes in.
libdivide tl;dr: > libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster. [...] divide SIMD vectors by runtime constants, [1] > libdivide.h is a header-only…
Earlier quoted context omitted.
Cache pressure is not really relevant, the result can be represented in 3 bits, so the entire table can fit in three 64 bit ints. It's uglier and you still need to do bitshifts, but much easier to write.
The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this. You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare. So naively you get: table[nlz / 21] >> (nlz % 21) Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spre…
Timing of instructions for Intel can be found here: www.agner.org/optimize/instruction_tables.pdf
1 1 1 1
--- - --- = --- --- (a-b)
b a b a
1 1 1 1
--- = --- + --- --- (a-b)
b a b a
[X]
1 1 (a-b) 1 1
--- = --- + ----- (1 + --- --- (a-b))
b a a^2 b a
__
1 \ -(n+1) n
--- = > a (a-b)
b /_
n=0...inf
1 1 1 1
--- = --- - --- + --- -+ ...
3 2 4 16
Earlier quoted context omitted.
libdivide tl;dr: > libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster. [...] divide SIMD vectors by runtime constants, [1] > libdivide.h is a header-only…
The obvious question this invites: if this is generally faster for unknown values, why don't compilers use this optimization directly in emitted code?
Earlier quoted context omitted.
The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this. You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare. So naively you get: table[nlz / 21] >> (nlz % 21) Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spre…
No need to pack bits. Use whole words. The table with 64 entries is small, and if the operation is performed often, the table will always be in L1 cache. Table lookup will take 1 cycle. The method with shifts takes 4 cycles. (It can make sense only in tight loops. The gain is really negligible in absolute terms in the large scheme of things) Timing of instructions for Intel can be found here: www.agner.org/optimize/i…
Best I can come up with is using 32 8-bit integers (so 6h bits more than 3 times 64 bitss in size) and doing thir:
(table[nlz >> 2] >> (nlz & 3)) & 7
Earlier quoted context omitted.
libdivide tl;dr: > libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster. [...] divide SIMD vectors by runtime constants, [1] > libdivide.h is a header-only…
The obvious question this invites: if this is generally faster for unknown values, why don't compilers use this optimization directly in emitted code?
if the divisor is in a variable or otherwise 'hidden', the compiler can't deduce enought to get to it, is my guess.
Earlier quoted context omitted.
libdivide tl;dr: > libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster. [...] divide SIMD vectors by runtime constants, [1] > libdivide.h is a header-only…
The obvious question this invites: if this is generally faster for unknown values, why don't compilers use this optimization directly in emitted code?
loop for i from 0 to n
f(a[i]/y)
I wonder whether the author ever ran a benchmark? Alas, the commenting system on their website seems broken, so can't ask there.
Author her. I didn't run benchmarks. I'm suspicious of micro-benchmarks and I don't have a context where I can try it against realistic data. Also, I just enjoy the maths of it even if it turns out not to make a huge performance difference in practice.
You are right that micro-benchmarks are a bit suspicious, but they are better than nothing.
Btw, have a look at https://godbolt.org/z/zMarEnYP5 to see what Clang come up with on her own.
#include
uint64_t div(uint64_t nlz) {
__builtin_assume(nlz I haven't analysed it in detail. But it looks like Clang doesn't seem to mind multiplication.
Earlier quoted context omitted.
Cache pressure is not really relevant, the result can be represented in 3 bits, so the entire table can fit in three 64 bit ints. It's uglier and you still need to do bitshifts, but much easier to write.
The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this. You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare. So naively you get: table[nlz / 21] >> (nlz % 21) Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spre…
> Which is five shifts and two additions, so more work plus lookup.
Something like that, perhaps with more bitmasking and less addition. There is no lookup, just three constants loaded into different registers and handled by different out of order execution units, then combined in a final addition / or-ing. So what you will "see" on the critical path is two bitshifts and three bitwise ORs/ANDs.
It's not faster, the point is that the speedup of "binary division" is probably not worth the day or so spent developing it unless in extreme cases.