41–50 of 75 posts
Nice, if a little bit hand wavy. Seems a little bit of a stretch to call an operation that still includes a multiply bitwise , though.
(v + (v > 6Compare here for the DEC PDP-1 (1959) and related algorithms:
[0] https://www.masswerk.at/spacewar/inside/insidespacewar-pt6-g...
Wouldn’t a lookup table be a whole lot easier? I’d think a 64 entry table of integers would be fast to access once cached.
Say you’re animating a jump and the character slows down towards the apex. I’ve seen an approach where it’s just “every X frames halve the speed until it’s zero.” This is done with the `SLA` (shift-left, LSB to 0) and `SRL` (shift-right, MSB to 0)` operations, which are very fast (8 cycles!) The bonus is that these opcodes will set the Zero Carry flag to 0 if the result is zero, so you know when your jump animation (up) is done if there is no ceiling collision, without having to check the value of the byte.
(I’ve also seen a set of hard coded speeds to animate through, and cases where they don’t change the speed at all, making the animation feel very rigid. It’s amazing what little details are important)
I wonder whether the author ever ran a benchmark? Alas, the commenting system on their website seems broken, so can't ask there.
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 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 C/C++ library for optimizing integer division. Integer division is one of the slowest instructions on most CPUs e.g. on current x64 CPUs a 64-bit integer division has a latency of up to 90 clock cycles whereas a multiplication has a latency of only 3 clock cycles. libdivide allows you to replace expensive integer divsion instructions by a sequence of shift, add and multiply instructions that will calculate the integer division much faster.
> On current CPUs you can get a speedup of up to 10x for 64-bit integer division and a speedup of up to to 5x for 32-bit integer division when using libdivide. libdivide also supports SSE2, AVX2 and AVX512 vector division which provides an even larger speedup. You can test how much speedup you can achieve on your CPU using the benchmark program.[2]
[1] https://libdivide.com/ [2] https://github.com/ridiculousfish/libdivide
Earlier quoted context omitted.
A bitshift oneliner IS nicer.
Maybe nicer, but slower. And I'm not even sure about the former.
Nice, if a little bit hand wavy. Seems a little bit of a stretch to call an operation that still includes a multiply bitwise , though.
Naw, it’s standard to call such tricks “bitwise” even when including a multiply. Remember you’re multiplying into a specific bit range and then shifting down (dividing by a power of 2) to capture the bits you want, it’s bitwise in a very literal sense. Probably quite fair to call any expression “bitwise” if any single operation in the expression is bitwise, regardless of the other operators & functions, no? What part…
I always have a hard time grooking bit wise operations. Any good resources?
Most of it is pattern recognition and learning common idioms, like multiplying by 0x01010101..., extracting substrings of bits ((x >> y) & z), thinking of values as sets of integers and so on.
Also bitwise manipulations lend themselves well to function composition, so try to keep an eye out for that. For example, if you have a fast function that checks if any byte is zero, you can generalize it to any value by applying xor beforehand. Similarly, the fast bit matrix transpose (which absolutely terrified me) is simply applying the least number of "shift a subset of bits" operations such that each bit travels the required distance.
ChatGPT tells me: Dividing a number by 7 using bitwise operations can be done using a technique called "magic numbers." This involves precomputing a number that, when combined with bitwise operations, will give the correct result. Here's how it can be done: First, we need to find a "magic number" that will help us divide by 7. One way to do this is to use the fact that 7 is a prime number, which means that there is a…
so... 7/7 = (7+(7>>3))*3 = 21? gotcha