Descubrí que calcular manualmente el operador % en __int128 es significativamente más rápido que el operador del compilador integrado. Te mostraré cómo calcular el módulo 9, pero el método se puede usar para calcular el módulo con cualquier otro número.
Primero, considere el operador del compilador integrado:
uint64_t mod9_v1(unsigned __int128 n) { return n % 9; }Ahora considere mi implementación manual:
uint64_t mod9_v2(unsigned __int128 n) { uint64_t r = 0; r += (uint32_t)(n); r += (uint32_t)(n >> 32) * (uint64_t)4; r += (uint32_t)(n >> 64) * (uint64_t)7; r += (uint32_t)(n >> 96); return r % 9; }La medición de más de 100 000 000 números aleatorios da los siguientes resultados:
mod9_v1 | 3.986052 secs mod9_v2 | 1.814339 secs GCC 9.3.0 con -march=native -O3 se usó en AMD Ryzen Threadripper 2990WX. Aquí hay un enlace a Godbolt.
Me gustaría preguntar si se comporta de la misma manera en su lado. (Antes de informar un error a GCC Bugzilla).
ACTUALIZACIÓN: A pedido, proporciono un ensamblaje generado:
mod9_v1: sub rsp, 8 mov edx, 9 xor ecx, ecx call __umodti3 add rsp, 8 ret mod9_v2: mov rax, rdi shrd rax, rsi, 32 mov rdx, rsi mov r8d, eax shr rdx, 32 mov eax, edi add rax, rdx lea rax, [rax+r8*4] mov esi, esi lea rcx, [rax+rsi*8] sub rcx, rsi mov rax, rcx movabs rdx, -2049638230412172401 mul rdx mov rax, rdx shr rax, 3 and rdx, -8 add rdx, rax mov rax, rcx sub rax, rdx retMientras tanto (mientras espera Bugzilla), puede dejar que el preprocesador haga la optimización por usted. Por ejemplo, defina una macro llamada MOD_INT128(n,d) :
#define MODCALC0(n,d) ((65536*n)%d) #define MODCALC1(n,d) MODCALC0(MODCALC0(n,d),d) #define MODCALC2(n,d) MODCALC1(MODCALC1(n,d),d) #define MODCALC3(n,d) MODCALC2(MODCALC1(n,d),d) #define MODPARAM(n,d,a,b,c) \ ((uint64_t)((uint32_t)(n) ) + \ (uint64_t)((uint32_t)(n >> 32) * (uint64_t)a) + \ (uint64_t)((uint32_t)(n >> 64) * (uint64_t)b) + \ (uint64_t)((uint32_t)(n >> 96) * (uint64_t)c) ) % d #define MOD_INT128(n,d) MODPARAM(n,d,MODCALC1(1,d),MODCALC2(1,d),MODCALC3(1,d))Ahora,
uint64_t mod9_v3(unsigned __int128 n) { return MOD_INT128( n, 9 ); }generará un lenguaje ensamblador similar al de la función mod9_v2(), y
uint64_t mod8_v3(unsigned __int128 n) { return MOD_INT128( n, 8 ); }funciona bien con la optimización ya existente (GCC 10.2.0)