在展开的链表上运行大约需要40%的代码运行时间——有什么明显的方法可以优化它吗

Question

我是一个名为吸血鬼（http://github.com/richard-evans/vampire），而计算密集型意味着代码性能的任何改进都可以显著增加可以进行的研究数量。此代码的典型运行时间可能长达数百个核心小时，因此我一直在寻找改进代码中性能关键部分的方法。然而，我有点拘泥于以下看起来相对无害的代码，它大约占运行时的40%：

for (int atom = start_index; atom < end_index; atom++){
    register double Hx = 0.0;
    register double Hy = 0.0;
    register double Hz = 0.0;
    const int start = atoms::neighbour_list_start_index[atom];
    const int end = atoms::neighbour_list_end_index[atom] + 1;
    for (int nn = start; nn < end; nn++){
        const int natom = atoms::neighbour_list_array[nn];
        const double Jij = atoms::i_exchange_list[atoms::neighbour_interaction_type_array[nn]].Jij;
        Hx -= Jij * atoms::x_spin_array[natom];
        Hy -= Jij * atoms::y_spin_array[natom];
        Hz -= Jij * atoms::z_spin_array[natom];
    }
    atoms::x_total_spin_field_array[atom] += Hx;
    atoms::y_total_spin_field_array[atom] += Hy;
    atoms::z_total_spin_field_array[atom] += Hz;
}

该代码的函数和变量的高级概述如下：有一个称为"spin"的物理向量的1D阵列（为了内存缓存目的，为每个分量x、y、z、atoms::x_spin_array等划分为三个1D阵列）。这些自旋中的每一个与一些其他自旋相互作用，并且所有的相互作用被存储为1D邻居列表（atoms::neighbour_list_array）。每个原子的相关交互列表由两个单独阵列中的邻居listarray的开始和结束索引确定。在计算结束时，每个原子自旋都有一个有效场，它是相互作用的矢量和。

考虑到代码量很小，占用的运行时间相当大，我已经尽了最大努力，但我觉得必须有一种方法来进一步优化它，但作为一名物理学家而不是计算机科学家，也许我错过了什么？

Answer 1

在连续数据上有一个恒定的乘法、减法和加法流。这似乎是SSE的理想用途。如果内存带宽有限，请改用OpenCL/CUDA。

如果您不熟悉所有的低级指令，请尝试使用此库。

然后，这种内部循环可能会被大幅重组，可能会加快速度。

Answer 2

如果x、y、z组件确实是链表，那么执行x[i]、y[i]和z[i]将导致列表被多次遍历，从而给出(n^2)/2迭代。使用矢量将使其成为O(1)操作。

您提到，出于内存缓存的目的，三个坐标是分开的，但当您访问内存中的三个不同区域时，这将影响级别1和级别2的缓存位置。链表也会影响您的缓存位置。

使用类似的东西

struct vector3d {
    double x;
    double y;
    double z;
};
std::vector<vector3d> spin;
std::vector<vector3d> total_spin;

这应该会提高缓存的局部性，因为x、y和z值在内存中是相邻的，并且旋转占用了内存的线性块。

Answer 3

我觉得以下建议可以帮助您优化代码，即使不是完全优化：

1. 尽可能使用初始化而不是分配
2. 为了获得更好的速度，更喜欢提前增量而不是后增量。（相信我，它确实改变了）

除此之外，我认为代码还不错。每个DS都有一些优点和缺点……你必须接受它。

快乐编码！