News for hackers. Stuff that matters.

A comment on Faster remainders when the divisor is a constant: beating compilers & libdivide. Parent comment

Re:Faster remainders when the divisor is a constant: beating... by mark-r on Friday February 08, 2019 @06:56PM (#19119747)
I recently discovered that x/10 == (x*103)>>10 for the numbers 0-99. Helped speed up something I was working on. The compiler generated a similar multiply/shift for x/10, but mine was faster since it didn't need to work for all possible values of x.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by nitrogen on Friday February 08, 2019 @11:16PM (#19120691)
This is called reciprocal multiplication. You can trade off accuracy for number of bits required, etc. I used this to do meaningful processing of Kinect data on a CPU without an FPU at near full frame rate.

Just curious, did you try making x an 8-bit integer to see if the compiler chose a different multiplier?

[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by mark-r on Friday February 08, 2019 @11:31PM (#19120737)
No, I didn't try casting to char although I thought about it.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by thijsvandien on Friday February 08, 2019 @09:37PM (#19120342)
For a range that small you could even build a lookup table. Or is this a case where cheap computation beats memory access?
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by Const-me on Saturday February 09, 2019 @02:06AM (#19121157)
On modern hardware, computation beats RAM access almost always.

Here's a repo with 2 tests, counting bits, and calculating sine/cosine: https://github.com/Const-me/LookupTables

Neither code is particularly cheap but still faster than RAM.

[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by mark-r on Friday February 08, 2019 @11:33PM (#19120746)
For modern processors you can assume that a couple of instructions will be much faster than a memory lookup. Even if the lookup is cached it will most likely push something else important out of cache.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by saagarjha on Friday February 08, 2019 @08:14PM (#19120073)
Does a multiply/shift pair take a different amount of time based on the operands? Otherwise, I don't see how this would make a difference.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by bdonlan on Friday February 08, 2019 @08:24PM (#19120104)
The compiler has to assume that your operands might be large enough that they would overflow after a straight multiply.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by saagarjha on Saturday February 09, 2019 @04:14AM (#19121463)
As acqq/I have mentioned below, there are ways of telling the compiler that the overflow can't multiply so it can freely optimize these away.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by mark-r on Friday February 08, 2019 @11:27PM (#19120726)
My code was two instructions: imul eax,ecx,67h sar eax,0Ah. The compiler generated code was mov eax,66666667h imul ecx sar edx,2 mov eax,edx shr eax,1Fh add eax,edx.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by acqq on Saturday February 09, 2019 @02:40AM (#19121217)
When input unsigned but before if < 99, output unsigned int:

clang 7

        mov     ecx, edi
        mov     eax, 3435973837
        imul    rax, rcx
        shr     rax, 35
gcc 8.2

        mov     eax, edi
        mov     edx, -858993459
        mul     edx
        mov     eax, edx
        shr     eax, 3
msvc 19

        mov     eax, -858993459  ; cccccccdH
        mul     edx
        shr     edx, 3
        mov     eax, edx
icc 19

        mov       eax, 1717986919                               
        imul      edx                                           
        sar       edx, 2                          
        mov       eax, edx
The same, but when input unsigned char:

clang 7

        movzx   eax, dil
        imul    eax, eax, 205
        shr     eax, 11
gcc 8.2

        movzx   edi, dil
        lea     eax, [rdi+rdi*4]
        lea     eax, [rdi+rax*8]
        lea     eax, [rax+rax*4]
        shr     ax, 11
        movzx   eax, al
msvc 19

        movzx   ecx, al
        mov     eax, -858993459  ; cccccccdH
        mul     ecx
        shr     edx, 3
        mov     eax, edx
icc 19

        mov       eax, 1717986919
        imul      edi            
        sar       edx, 2        
        mov       eax, edx
clang and gcc with -O3, msvc -O2
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by saagarjha on Saturday February 09, 2019 @04:13AM (#19121461)
This was exactly what I was about to mention; I can reproduce your results in Clang but it seems GCC doesn't want to optimize this? Here's what Godbolt gives me: https://godbolt.org/z/aFTdur
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by acqq on Saturday February 09, 2019 @10:24AM (#19122696)
Just write a function “mydiv10” which returns if x < 99 { x /10 and 0 otherwise and try again.
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by acqq on Sunday February 10, 2019 @04:39PM (#19130218)
Like this:

https://godbolt.org/z/bS2yzB

But also note that when the input is unsigned short we get:

https://godbolt.org/z/sbDbMU

        movzx   eax, di
        imul    eax, eax, 52429
        shr     eax, 19
[ Parent | on HN ]
Re:Faster remainders when the divisor is a constant: beating... by nitrogen on Friday February 08, 2019 @11:18PM (#19120696)
It's conceivable that multiplication time might be proportional to the number of 1 bits in the multiplier.
[ Parent | on HN ]