Comments (5)
ridiculousfish
commented on July 23, 2024
You'd think so, but (at least on x86) the mask is actually not emitted at all, because the shift instruction only looks at the bottom bits. So the mask currently costs 0 instructions.
This isn't true for the vector case, so we can leave this open to track that.
from libdivide.
kimwalisch
commented on July 23, 2024
Are you sure about this?
I compiled both versions using GCC -O2 -S and the 2nd version t >> (denom->more & LIBDIVIDE_64_SHIFT_MASK) contains many andl $63, %ecx instructions whereas the 1st version t >> denom->more contains none!
Here is the assembly diff of both versions (1st version t >> denom->more, 2nd version t >> (denom->more & LIBDIVIDE_64_SHIFT_MASK)):
$ diff S2_easy_libdivide_new.s S2_easy_libdivide_old.s
333a334
> andl $63, %ecx
356a358
> andl $63, %ecx
398a401
> andl $63, %ecx
791a795
> andl $63, %ecx
811,815c815,816
< leaq (%rcx,%rdx), %rax
< movq 48(%rsp), %rcx
< subq %rax, %rcx
< shrq %rcx
< addq %rcx, %rax
---
> movq 48(%rsp), %rax
> addq %rcx, %rdx
816a818,821
> subq %rdx, %rax
> shrq %rax
> addq %rdx, %rax
> andl $63, %ecx
867a873
> andl $63, %ecx
1409a1416
> andl $63, %ecx
1429,1433c1436,1437
< leaq (%rcx,%rdx), %rax
< movq 48(%rsp), %rcx
< subq %rax, %rcx
< shrq %rcx
< addq %rcx, %rax
---
> movq 48(%rsp), %rax
> addq %rcx, %rdx
1434a1439,1442
> subq %rdx, %rax
> shrq %rax
> addq %rdx, %rax
> andl $63, %ecx
1485a1494
> andl $63, %ecxSo I still think you could save one andl $63, %ecx instruction in libdivide_u64_branchfree_do(). But I also think that it would not be faster because today's out of order CPUs can execute up to 4 independent instructions simultaneously.
from libdivide.
ridiculousfish
commented on July 23, 2024
Ugh, you're right, clang is getting it right, but gcc is being stupid here. Ok, I guess we ought to fix this. Nice catch!
from libdivide.
ridiculousfish
commented on July 23, 2024
Fixed by #13
from libdivide.
kimwalisch
commented on July 23, 2024
I have compiled my code using the very latest branchfree libdivide.h using GCC 5.2 and -std=c++11 and got some warnings which have been introduced by my Save 1 instruction in libdivide_u64_branchfree_do() code changes:
g++ -std=c++11 -DPACKAGE_NAME=\"primecount\" -DPACKAGE_TARNAME=\"primecount\" -DPACKAGE_VERSION=\"3.1\" "-DPACKAGE_STRING=\"primecount 3.1\"" -DPACKAGE_BUGREPORT=\"[email protected]\" -DPACKAGE_URL=\"\" -DPACKAGE=\"primecount\" -DVERSION=\"3.1\" -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DHAVE_DLFCN_H=1 -DLT_OBJDIR=\".libs/\" -DNDEBUG=1 -DHAVE___BUILTIN_POPCOUNT=1 -DHAVE___BUILTIN_POPCOUNTLL=1 -DHAVE___INT128_T=1 -DHAVE_LIBDIVIDE=1 -I. -I./include -fopenmp -mpopcnt -DHAVE_POPCNT=1 -O2 -Iprimesieve-5.6.0/include -MT src/libprimecount_la-phi_libdivide.lo -MD -MP -MF src/.deps/libprimecount_la-phi_libdivide.Tpo -c src/phi_libdivide.cpp -fPIC -DPIC -o src/.libs/libprimecount_la-phi_libdivide.o
In file included from src/phi_libdivide.cpp:22:0:
./include/libdivide.h: In function ‘{anonymous}::libdivide::libdivide_u32_branchfree_t {anonymous}::libdivide::libdivide_u32_branchfree_gen(uint32_t)’:
./include/libdivide.h:774:66: warning: narrowing conversion of ‘(((int)tmp.{anonymous}::libdivide::libdivide_u32_t::more) & 31)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
struct libdivide_u32_branchfree_t ret = {tmp.magic, tmp.more & LIBDIVIDE_32_SHIFT_MASK};
^
./include/libdivide.h: In function ‘uint32_t {anonymous}::libdivide::libdivide_u32_branchfree_recover(const {anonymous}::libdivide::libdivide_u32_branchfree_t*)’:
./include/libdivide.h:833:67: warning: narrowing conversion of ‘(int)(((unsigned char)denom->{anonymous}::libdivide::libdivide_u32_branchfree_t::more) | 64u)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
struct libdivide_u32_t denom_u32 = {denom->magic, denom->more | LIBDIVIDE_ADD_MARKER};
^
./include/libdivide.h: In function ‘{anonymous}::libdivide::libdivide_u64_branchfree_t {anonymous}::libdivide::libdivide_u64_branchfree_gen(uint64_t)’:
./include/libdivide.h:969:66: warning: narrowing conversion of ‘(((int)tmp.{anonymous}::libdivide::libdivide_u64_t::more) & 63)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
struct libdivide_u64_branchfree_t ret = {tmp.magic, tmp.more & LIBDIVIDE_64_SHIFT_MASK};
^
./include/libdivide.h: In function ‘uint64_t {anonymous}::libdivide::libdivide_u64_branchfree_recover(const {anonymous}::libdivide::libdivide_u64_branchfree_t*)’:
./include/libdivide.h:1039:67: warning: narrowing conversion of ‘(int)(((unsigned char)denom->{anonymous}::libdivide::libdivide_u64_branchfree_t::more) | 64u)’ from ‘int’ to ‘uint8_t {aka unsigned char}’ inside { } [-Wnarrowing]
struct libdivide_u64_t denom_u64 = {denom->magic, denom->more | LIBDIVIDE_ADD_MARKER};
In order to fix the warnings we must add a (uint8_t) cast at lines 774, 833, 969 and 1039.
For example:
struct libdivide_u64_t denom_u64 = {denom->magic, (uint8_t)(denom->more | LIBDIVIDE_ADD_MARKER)};from libdivide.
Related Issues (20)
- NEON is not for AArch32
- Faster divlu HOT 10
- error: a function declaration without a prototype is deprecated in all versions of C HOT 1
- Branchfree divider cannot be 1 HOT 1
- Division by 0 causes non-AVR mcus hang HOT 3
- Question: why not support SSE2, AVX, and AVX512 all in the same time? (or am I missing something?) HOT 2
- Status update on +-1 branchfree dividers HOT 1
- clang-cl: error LNK2019: unresolved external symbol __udivti3 HOT 2
- size_t support HOT 6
- CMake cross compilation error HOT 1
- Consider automatically defining LIBDIVIDE_SSE2 et al HOT 1
- Libdivide is using exit instead of abort on errors. HOT 3
- Greater magic/shift value than with gcc HOT 2
- On my mac, system divide gives the fastest result HOT 10
- Appveyor build inconsistent with cmake
- Incorrect NEON function signature
- Unnecessary static linkage
- libdivide.h:1691:59: error: ‘numers’ may be used uninitialized in this function HOT 2
- Special support for 63-bit division (unsigned)? HOT 2
- Regression: ptrdiff_t/size_t on macOS don't work anymore HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from libdivide.