我正在使用C，并且我有两个非负整数n和m（均> = 0，n <500）。我需要形成产品
n*(n+1)/2 + m
这将需要数亿次，所以我想尽可能地优化它。我当前的实现是：
inline int func(const int n, const int m) { return ( (n*(n+1) >> 1) + m); }
使用inline和>> 1进行除以2。还有其他方法可以加快计算速度吗？
假设该n值小于500，则可以预先计算的所有可能值n*(n+1)/2并将它们放在表中，然后使用该表执行计算：
int n_sum[500];
// call this once at program start
void init_sum()
{
int i;
for (i=0;i<500;i++) {
n_sum[i] = i*(i+1)/2;
}
}
inline int func(const int n, const int m)
{
return n_sum[n] + m;
}
实际上，您要做的是编写一个循环，编译器可以轻松有效地对其进行矢量化和并行化。如果您有两个数组n[i]和m[i]，则任何现代编译器都可能会弄清楚n[i]*(n[i]+1)/2 + m[i]如果给定了正确的标志，如何进行优化。通常，试图迫使编译器一次对一个单词进行优化会适得其反。当并行化关键循环时，现代硬件最快。如果您不想使用为此目的而设计的不可移植的内在函数或库，则可以通过最小化数据依赖关系并编写易于静态分析的代码来最好地实现这一点。
您可能无法使用来改进生成的代码(n*n + n)/2 + m，也就是将多项式转换为嵌套形式。这是有效的，因为它使代码生成器仅使用一个向量寄存器作为累加器，从而最大限度地增加了SIMD的可用数量。您应该使用restrict和alignas适当地启用最大优化。
（编辑： 负数的右移是实现定义的，因为它可能是逻辑或算术运算。我编写的代码执行无符号数学运算，这使编译器/2可以>>1为您优化。您使用有符号变量而不是无符号变量，并且您知道它们将始终是非负变量，因此编译器可能无法静态推断出此变量，因此可能无法优化/2为>>1。在这种情况下，您可以编写>>1或强制转换(uint32_t)n[i]以做得更好定义的无符号数学。不安全数学优化标记也可能会重新启用它。）
这种矢量化可能比每个元素上的单个表查找要快。
结果将在0到125,750的范围内，对于an来说太大了unsigned short，因此可以容纳它的最小类型是int32_tor uint32_t。（或者，uint_least32_t如果您愿意的话。）使用最小类型的数组可以实现最大的向量化。
如果要帮助优化器，可以启用OpenMP并添加#pragma omp simd，以明确告诉编译器向量化此循环。您还可以使用OpenMP启用多线程。
在C ++中，您可以使用std::valarray<uint32_t>或表达式模板的选项，这是表达此类尴尬并行计算的非常优雅的方式。
当给出适当的优化标志时，以下程序将编译为 GCC，Clang或ICC上的矢量化代码。Clang编译为一个循环，每个循环计算256个元素。
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#define N (1L<<20)
typedef uint_least32_t elem_t;
const elem_t n[N];
const elem_t m[N];
elem_t a[N];
int main(void)
{
for ( ptrdiff_t i = 0; i < N; ++i) {
a[i] = (n[i]*n[i] + n[i])/2 + m[i];
}
return EXIT_SUCCESS;
}
您可以尝试向alignas数组添加说明符，但这实际上不会导致GCC，Clang或ICC执行对齐的加载或存储。（有一个GCC扩展程序可启用此优化。）
如果启用OpenMP库（-fopenmp在GCC或Clang中），则可以添加以下行
#pragma omp for
紧接for循环之前或更复杂的版本，并获得一个多线程和向量化的循环。如果有一种方法可以使用标准的便携式C进行重大改进，我想自己了解一下。
我写的MWE很简单。在现实世界的代码中，您可能希望将整个循环（包括此内部循环的一部分）main()移入或移出诸如
elem_t* func( const ptrdiff_t nelems,
const elem_t n[nelems],
const elem_t m[nelems],
elem_t a[nelems]
)
{
for ( ptrdiff_t i = 0; i < nelems; ++i) {
a[i] = (n[i]*n[i] + n[i])/2 + m[i];
}
return a;
}
如果您比较生成的程序集，您会发现它效率不高，除非您对其内联，主要是因为编译器不再知道编译时的迭代次数或有关n，m或的对齐方式的任何信息a。
通过将输入元素存储为，还可以节省一些内存，但可能不会节省计算时间uint16_t。输入数组使用的内存只有原来的一半，但是循环无法处理比以前更多的元素，因为计算使用的元素大小相同。注意将用于计算的临时值转换为不会溢出的类型！
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#define N (1L<<20)
const uint16_t n[N];
const uint16_t m[N];
uint32_t a[N];
int main(void)
{
for ( ptrdiff_t i = 0; i < N; ++i) {
a[i] = ((uint32_t)n[i]*n[i] + n[i])/2 + m[i];
}
return EXIT_SUCCESS;
}
您可以使用直接组装指令。在VC++中，您可以使用__asm关键字来启动汇编部分。您可以使用常规函数并在其中使用此部分。并正常调用该函数。对于基于 gcc 的您可以使用asm().