c - 模运算符比手动执行慢?
问题描述
我发现手动计算%
运算符__int128
比内置编译器运算符快得多。我将向您展示如何计算模 9,但该方法可用于计算模任何其他数字。
首先,考虑内置的编译器运算符:
uint64_t mod9_v1(unsigned __int128 n)
{
return n % 9;
}
现在考虑我的手动实现:
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;
}
测量超过 100,000,000 个随机数会得出以下结果:
mod9_v1 | 3.986052 secs
mod9_v2 | 1.814339 secs
GCC 9.3.0-march=native -O3
用于 AMD Ryzen Threadripper 2990WX。
这是godbolt的链接。
我想问一下它在你这边的行为是否相同?(在向 GCC Bugzilla 报告错误之前)。
更新: 根据要求,我提供了一个生成的程序集:
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
ret
解决方案
从汇编列表中可以清楚地看出这种差异的原因:%
应用于 128 位整数的运算符是通过对无法利用除数值的编译时知识的通用函数的库调用来实现的,这使得转换除法成为可能和模运算到更快的乘法。
mod_v2()
在我使用clang的旧 Macbook-pro 上,时间差异更加显着,我的速度比mod_v1()
.
但请注意以下备注:
- 您应该在
for
循环结束后测量 cpu 时间,而不是在printf
当前编码的第一个之后。 rand_u128()
RAND_MAX
假设is仅产生 124 位0x7fffffff
。- 大部分时间都花在计算随机数上。
使用您的切片方法,我扩展了您的代码以减少使用 42、42 和 44 位切片的步骤数,这进一步改进了时序(因为 2 42 % 9 == 1):
#pragma GCC diagnostic ignored "-Wpedantic"
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <time.h>
static uint64_t mod9_v1(unsigned __int128 n) {
return n % 9;
}
static uint64_t mod9_v2(unsigned __int128 n) {
uint64_t r = 0;
r += (uint32_t)(n);
r += (uint32_t)(n >> 32) * (uint64_t)(((uint64_t)1ULL << 32) % 9);
r += (uint32_t)(n >> 64) * (uint64_t)(((unsigned __int128)1 << 64) % 9);
r += (uint32_t)(n >> 96);
return r % 9;
}
static uint64_t mod9_v3(unsigned __int128 n) {
return (((uint64_t)(n >> 0) & 0x3ffffffffff) +
((uint64_t)(n >> 42) & 0x3ffffffffff) +
((uint64_t)(n >> 84))) % 9;
}
unsigned __int128 rand_u128() {
return ((unsigned __int128)rand() << 97 ^
(unsigned __int128)rand() << 66 ^
(unsigned __int128)rand() << 35 ^
(unsigned __int128)rand() << 4 ^
(unsigned __int128)rand());
}
#define N 100000000
int main() {
srand(42);
unsigned __int128 *arr = malloc(sizeof(unsigned __int128) * N);
if (arr == NULL) {
return 1;
}
for (size_t n = 0; n < N; ++n) {
arr[n] = rand_u128();
}
#if 1
/* check that modulo 9 is calculated correctly */
for (size_t n = 0; n < N; ++n) {
uint64_t m = mod9_v1(arr[n]);
assert(m == mod9_v2(arr[n]));
assert(m == mod9_v3(arr[n]));
}
#endif
clock_t clk1 = -clock();
uint64_t sum1 = 0;
for (size_t n = 0; n < N; ++n) {
sum1 += mod9_v1(arr[n]);
}
clk1 += clock();
clock_t clk2 = -clock();
uint64_t sum2 = 0;
for (size_t n = 0; n < N; ++n) {
sum2 += mod9_v2(arr[n]);
}
clk2 += clock();
clock_t clk3 = -clock();
uint64_t sum3 = 0;
for (size_t n = 0; n < N; ++n) {
sum3 += mod9_v3(arr[n]);
}
clk3 += clock();
printf("mod9_v1: sum=%"PRIu64", elapsed time: %.3f secs\n", sum1, clk1 / (double)CLOCKS_PER_SEC);
printf("mod9_v2: sum=%"PRIu64", elapsed time: %.3f secs\n", sum2, clk2 / (double)CLOCKS_PER_SEC);
printf("mod9_v3: sum=%"PRIu64", elapsed time: %.3f secs\n", sum3, clk3 / (double)CLOCKS_PER_SEC);
free(arr);
return 0;
}
以下是我的 linux 服务器 (gcc) 上的时间安排:
mod9_v1: sum=400041273, elapsed time: 7.992 secs
mod9_v2: sum=400041273, elapsed time: 1.295 secs
mod9_v3: sum=400041273, elapsed time: 1.131 secs
我的 Macbook 上的相同代码(clang):
mod9_v1: sum=399978071, elapsed time: 32.900 secs
mod9_v2: sum=399978071, elapsed time: 0.204 secs
mod9_v3: sum=399978071, elapsed time: 0.185 secs
推荐阅读
- javascript - 如何从 axios 响应的数组中显示对象的单个属性(多次)?
- mysql - mysql内部连接表上的左连接
- sql - 按键/值过滤 JSON 数组元素的 PostgreSQL (v9.6) 查询
- python - 数字字符串转换为 int 并添加到列表中(优化问题)
- python - 如何在最后两个反斜杠之间查找和添加子字符串?
- python - 如何使用比较运算符过滤还包含字符串作为值的字典中的整数?
- javascript - HTML & Javascript - 仅显示特定对象的按钮
- c - 在函数中修改和返回结构
- excel - 在 EXCEL/GOOGLE SHEETS 中计算具有多个条件和范围的多个值
- ssl - 在 EC2 上的生产中的 Phoenix 未使用 AWS 负载均衡器在 HTTPS 中呈现