在传递到函数和访问C中存储的值时，有效地使用structs中的structs

Question

我有一个代码，它的组织方式是有一个structs结构，在我的主方法中，我有许多函数将指向主结构的指针作为参数。我想知道我在这样一个组织中所做的某些选择会对我的代码速度产生不利影响。为了回答我的问题，一个最小的示例代码如下所示：

#define NPMAX 50000
typedef struct Particles{
double *X, *Y, *Z;
} Particles;
typedef struct Properties{
int Npart;
double Box[3];
double minDist;
} Properties;
typedef struct System{
Properties props;
Particles parts;
} System;
void function(System *sys){
double dist;
int i;
for(i=0; i<sys->props.Npart; i++){
dist = pow(sys->parts.X[i],2.) + pow(sys->parts.Y[i],2.) + pow(sys->parts.Z[i],2.);
if(dist<sys->props.minDist) sys->props.minDist=dist;
}
return;
}

采用以下主要方法：

int main(){
System sys;
sys.parts.X = (double *)malloc(sizeof(double) * NPMAX);
sys.parts.Y = (double *)malloc(sizeof(double) * NPMAX);
sys.parts.Z = (double *)malloc(sizeof(double) * NPMAX);
//... some code to populate sys->parts.X, Y, and Z ... 
sys.props.Npart = 1000;
sys.props.Box[0] = 10.; //etc.
sys.props.minDist = 9999.;
function(&sys);
// some file I/O
return;
}

我的问题是，考虑到这种数据结构，我是否以尽可能好的方式组织我的功能以提高效率？我是说速度，而不是记忆力。更具体地说：

• 例如，访问和分配值给sys->parts.X[i]是否比在函数中直接创建指向sys->parts的指针和执行parts->X[i]慢？

• 在同一结构中同时在堆和堆栈中分配变量是一个明智的选择吗？程序是否因为这种混合而在尝试访问内存中的这些值时浪费了时间？

• 我是否应该期望这种方法比只为结构中声明的每个单独变量使用全局变量更快？

除了gcc之外，我还可以访问英特尔编译器，并且我使用-O3标志进行编译。

Answer 1

正在访问sys->部件并为其赋值。例如，X[i]比直接创建指向函数中sys->parts的指针和执行parts->X[i]慢吗？

从编译器的角度来看，只有副作用才是重要的。我认为这两种情况都应该通过一个具有良好优化的正弦编译器优化为相同的指令。让我们测试一下：

void function(System *sys){
double dist;
int i;
for(i=0; i<sys->props.Npart; i++){
dist = pow(sys->parts.X[i],2.) + pow(sys->parts.Y[i],2.) + pow(sys->parts.Z[i],2.);
if(dist<sys->props.minDist) sys->props.minDist=dist;
}
return;
}
void function2(System *sys){
double dist;
int i;
for(i=0; i<sys->props.Npart; i++){
const struct Particles * const p = &sys->parts;
dist = pow(p->X[i],2.) + pow(p->Y[i],2.) + pow(p->Z[i],2.);
if(dist<sys->props.minDist) sys->props.minDist=dist;
}
return;
}

两个函数都编译成相同的汇编指令，如godbolt所示。在这篇文章中，我使用的是带有64位x8_64体系结构的gcc8.2。

在同一结构中同时在堆和堆栈中分配变量是明智的选择吗？程序是否因为这种混合而在尝试访问内存中的这些值时浪费了时间？

真正的答案应该是：取决于体系结构。在x86_64上，我相信在以下情况下访问(不分配)阵列成员之间不会有可测量的差异：

System sys_instance;
System *sys = &sys_instance;
double Xses[NPMAX];
sys->parts.X = Xses;
double Yses[NPMAX];
sys->parts.Y = Yses;
double Zses[NPMAX];
sys->parts.Z = Zses;

和：

System *sys = alloca(sizeof(*sys));
sys->parts.X = alloca(sizeof(*sys->parts.X) * NPMAX);
sys->parts.Y = alloca(sizeof(*sys->parts.Y) * NPMAX);
sys->parts.Z = alloca(sizeof(*sys->parts.Z) * NPMAX);

和：

System *sys = malloc(sizeof(*sys));
sys->parts.X = malloc(sizeof(*sys->parts.X) * NPMAX);
sys->parts.Y = malloc(sizeof(*sys->parts.Y) * NPMAX);
sys->parts.Z = malloc(sizeof(*sys->parts.Z) * NPMAX);

或这些形式的任何混合物。无论使用malloc还是alloca，都会产生一个指针，从访问的角度来看是一样的。但请记住CPU缓存和其他依赖于体系结构的优化。使用malloc将导致明显"较慢"的分配。

我应该期望这种方法比只为结构中声明的每个单独变量使用全局变量更快吗？

即使你这样做：

static System sys_static;
System *sys = &sys_static;
static double X_static[NPMAX];
sys->parts.X = X_static;
static double Y_static[NPMAX];
sys->parts.Y = Y_static;
static double Z_static[NPMAX];
sys->parts.Z = Z_static;

仍然向函数function传递指向sys的指针，并且所有访问都是相同的。

在同样罕见的情况下，当不使用malloc而sys初始化没有副作用时，您的函数声明为静态的，并且是一个好的优化器，它可以被优化，并且sys->props.minDist可以由编译器在编译阶段预先计算。但我不打算这样做，除非您想将C++与consteval或constexpr一起使用。

>

如果X、Y和Z的数量相同，我会同意@WhozCraig的建议。

void function(System *sys){
double dist;
int i;
for(i=0; i<sys->props.Npart; i++){
const struct Particles * const p = &sys->parts[i];
dist = pow(p->X, 2.) + pow(p->Y, 2.) + pow(p->Z, 2.);
if(dist<sys->props.minDist) sys->props.minDist=dist;
}
return;
}

这将节省乘法所需的周期。此外，它还将减少分配(和调整)元素所需的malloc的数量。对于整个CCD_ 18行，可以计算一次CCD_。在sys->parts.X[i]的情况下，可以计算一次sys->parts，然后对于每个X、Y和Z，必须计算值pointer + sizeof(elem) * i。但是，在一个不错的编译器和优化器的情况下，这并没有什么区别。但实际上，这种方法导致了不同的组装，但指令数量相同，请参阅godbolt。

我肯定会声明所有表示对象大小的变量都具有size_t类型，即循环计数器i具有size_t类型，sys->propc.Npart也将是size_t类型。它们表示元素计数，这就是size_t类型的用途。

但我肯定会手动优化循环。您在每次循环检查中都访问sys->props.Npart。如果使用指针，我会声明double *X, *Y , *Z;相互限制——我想你不希望它们相等。

此外，你在每个循环中访问sys->procp.minDist并有条件地分配它。你只需要在这里尊重sys两次——在开始和结束时(除非你有一些并行代码在计算中期依赖于minDist的值，我希望你不要这样做，因为你在当前代码中没有同步的手段)。使用本地变量并尽可能少地访问sys。

我会将pow调用替换为变量赋值(这样变量只被解除隔离一次)和纯乘法。如果有任何赋值，编译器可能会认为取消隔离的变量可能会在循环中期发生变化——让我们防止这种情况发生。然而，一个好的优化器将优化pow(..., 2.)调用。

如果性能是如此需要，我会选择：

void function3(System * restrict sys){
double minDist = sys->props.minDist;
for (const struct Particles 
* const start = &sys->parts[0],
* const stop = &sys->parts[sys->props.Npart],
* p = start; p < stop; ++p) {
const double X = p->X;
const double Y = p->Y;
const double Z = p->Z;
const double dist = X * X + Y * Y + Z * Z;
if (dist < minDist) {
minDist = dist;
}
}
sys->props.minDist = minDist;
return;
}

这导致汇编代码的减少，主要是因为sys->propc.minDist不是每次在循环中都被访问，不需要使用和增加一些临时计数器。使用consts so向编译器提示您不会修改变量。

Answer 2

内存布局看起来不错。只有少量拨款，结构就没那么重要了。这些双数组确实为向量计算提供了一个很好的选择，中间有一个临时数组。

// collect computations first
double dist[NPMAX];
// process 8 64-bit floating-points at a time
int n = sys->props.Npart & ~7;
for(int i = 0; i < n; i += 8){
_m512d xsq = _mm512_sqrt_pd(&sys->parts.X[i]);
_m512d ysq = _mm512_sqrt_pd(&sys->parts.Y[i]);
_m512d zsq = _mm512_sqrt_pd(&sys->parts.Z[i]);
dist[i] = xsq + ysq + zsq;
}
// deal with remainders (if any)
for (int i = n; i < sys->props.Npart; i++)
dist[i] = sqrt(sys->parts.X[i]) + sqrt(sys->parts.Y[i]) + sqrt(sys->parts.Z[i]);
// then find lowest
for (int i = 0; i < sys->props.Npart; i++)
if(dist[i] < sys->props.minDist) sys->props.minDist = dist[i];