优化乘加

共6个回答, 标签: c optimization

我使用 C,我有两个非负整数 n 和 m (都> = 0,n <500)。我需要形成产品

N * (n 1)/2 m

这将需要数亿次,所以我想尽可能优化它。我目前的实现是:

Inline int func (const int n,const int m) {return (n * (n1)>> 1) m);}

使用inline and the >> 1除以 2。有没有其他方法来加快这个计算?

第1个答案

考虑到这一点n will be less that 500, you can precompute all possible values of n*(n 1)/2然后将它们放入一个表中,然后使用该表执行计算:

Int _ sum [500];

//在程序开始时调用一次
虚空 init_sum ()
{
I;
对于 (i = 0; i <500; i) {
N _ sum [i] = i * (i 1)/2;
}
}

直插智力功能 (const int n,const int 的米)
{
返回 n _ sum [n] m;
}
第2个答案

在实践中,你想做的是编写一个循环,编译器可以轻松高效地对其进行向量化和并行化。如果你有两个数组n[i] and m[i], any modern compiler can probably figure out how to optimize n[i]*(n[i] 1)/2 m[i]如果有合适的旗帜通常,试图强迫编译器一次对一个单词进行优化会适得其反。当您并行关键环路时,现代硬件速度最快。如果您不想使用为此目的设计的不可移植的内部函数或库,您可以通过最小化数据依赖关系和编写易于静态分析的代码来最好地实现这一点。

您可能会改进生成的代码,也可能无法改进生成的代码(n*n n)/2 m, that is, converting the polynomial to nested form. This is efficient because it enables the code generator to use just one vector register as the accumulator, maximizing the number available for SIMD. You should use restrict and alignas根据需要启用最大优化。

(编辑:负数的右移是实现定义的,因为它可能是逻辑的,也可能是算术的。我写的代码做无符号数学,让编译器优化/2 to >>1 for you. In a comment, robthebloke brings up that, if you use signed rather than unsigned variables, and you know that they will always be non-negative, the compiler might not be able to statically deduce this and therefore might not optimize /2 to >>1. In that case, you can either write >>1 or cast (uint32_t)n[i]更好地定义无符号数学。不安全的数学优化标志也可能会重新启用此功能。))

这种向量化可能比每个元素上的单个表查找更快。

结果将在 0 到 125,750 的范围内,对于一个unsigned short, and therefore the smallest type that could hold it is int32_t or uint32_t. (Or uint_least32_t如果你愿意的话。)使用最小类型的数组可以实现最大的向量化。

如果要帮助优化器,可以启用 OpenMP 并添加#pragma omp simd,显式告诉编译器将此循环向量化。您也可以使用 OpenMP 启用多线程。

在 C 中,你可以选择std::valarray或者表达式模板,这是一种非常优雅的方式来表达像这种令人尴尬的并行计算。

下面的程序编译为向量化代码当给定适当的优化标志时,在 GCC 、 Clang 或 ICC 上。Clang 编译为一个循环,每次迭代计算 256 个元素。

# 包括
# 包括
# 包括

# 定义 N (1L <20)
的 typedef uint_least32_t elem_t;

【 N 】;
Const element _ t m [N];
元素 a [N];

Int main (void)
{
对于 (ptrdiff_t i = 0; i <N; i) {
A [i] = (n [i] * n [i)/2 m [i];
}

返回 exit _ 成功;
}

您可以尝试添加alignas数组的说明符,但这实际上不会导致 GCC 、 Clang 或 ICC 执行对齐的加载或存储。(为了实现这种优化,有一个 GCC 扩展。))

如果启用 OpenMP 库 (-fopenmp在 GCC 或 Clang) 中,您可以添加行

# Pragma omp 的

就在for循环或更复杂的版本,并获得既多线程又向量化的循环。如果有办法用标准的便携式 C 来显著改进这一点,我很想自己知道。

我写我的 MWE 是为了简单。在现实世界中

第3个答案

最后,问题是: 你真的能比你简单的实现优化更多吗?

以下是使用具有-O2 优化级别的 arm-none-eabi-gcc 的快速测试:看到这里

Int func (int n,int m)
{
返回 (n * (n 1)>> 1) m);
}

编译在:

Func (int,int):
Mla r3,r0,r0,r0
添加 r2 、 r1 、 r3 、 asr #1
Bx lr

所以两个装配说明 (不包括bx lr这将随着内衬而消失)。我看不出你如何更快地实现。

编辑: 如果你用 level-O0 编译,这是你得到的:

Func (int,int):
Str fp,[sp,#-4]!
添加 fp,sp,#0
#12 分 sp 、 sp
Str r2,[fp,#-8]
Str r1,[fp,#-12]
Ldr r3,[fp,#-8]
新增 r3,r3,#1
Ldr r2,[fp,#-8]
Mul r3,r2,r3
Asr #1 的 mov r2 、 r3
Ldr r3,[fp,#-12]
新增 r3,r2,r3
R3 的 mov t0
分 sp,fp,#0
Ldr fp,[sp],#4
Bx lr

GCC 可以很聪明,你只需要告诉他是;))

第4个答案

我认为更好的方法是问你是否真的需要计算这么多次。例如,如果在内部循环中 n 是常数,你能在外部计算 n * (n1)/2 吗?(尽管优化编译器可能会这样做)。或者,如果你在内部循环中增加 n,也许你可以使用

(N 1) * (n 2)/2 = n * (n 1)/2 n 1

更新 n * (n1)/2,而不是每次都重新计算。

第5个答案

您可以使用直接装配说明。在 VC 中可以用吗:__asm keyword to start assembly section. You can use a regular function and use this section inside there. And call that function normally. For gcc based you can use asm()

第6个答案

你说 “这将需要数亿次”,就好像需要很多次一样。但是这些天,数以亿计的时间没什么.

我刚刚写了一个很明显的小程序n*(n+1)/2 + m100,000,000 次为了让它 “高效”,我什么也没做。在普通的消费级笔记本电脑上,它运行了大约半秒钟 -- 这太快了,甚至无法准确地计时。所以我试了 100 次,只要 10,000,000,000 次。在这种情况下,大约需要 52 秒,大约需要 5.2 秒纳米秒每次计算。(因此,每次计算的实际时间甚至更少。))

比如说,你花了一个小时试图加快这个功能。(你可能花了那么多时间来发布你的问题来堆叠溢出和阅读回复,更不用说我们都花了这么多时间回复了。))假设你设法将速度提高 50% (也就是说,使速度提高一倍)。根据我的结果,在你回来之前,你必须运行 1.4e12 次 (超过万亿次) 这样的函数。

因此,如果你要运行这个计算数万亿次 (不仅仅是数亿次),那么也许 (也许!) 花一些时间来加快速度。否则 -- 很抱歉对此感到沮丧 -- 不要打扰。

另见这个答案类似的问题。

(我并不是想说效率从来都不重要,但是从你的实际情况来看也是很重要的。))

相关问题

我投的是 malloc 的结果吗? 为什么是统计:: st _ size 0 为设备, 但同时 lseek 正确地定义了设备大小? 允许在易失对象上进行优化 优化乘加 尽可能快地比较表单中的两个值 (a sqrt (b))?