c语言 - 使用 OpenMP 对大型数组上的线性搜索循环进行微优化：无法在命中时中断

Question

我有一个循环，大约占用90%到99%的程序时间。 它读取一个巨大的LUT，并且此循环>执行100,000次，因此值得进行一些优化。

编辑：

LUT(实际上有各种数组组成LUT(由ptrdiff_t数组和unsigned __int128数组组成。 由于算法(尤其是 128 位算法(，它们必须那么宽。T_RDY是唯一bool数组。

编辑：

LUT 存储过去用于尝试解决不起作用的问题的组合。它们之间没有关系(我还可以看到(，所以我没有看到更合适的搜索模式。

循环的单线程版本为：

k   = false;
for (ptrdiff_t i = 0; i < T_IND; i++) {
if (T_RDY[i] && !(~T_RWS[i] & M_RWS) && ((T_NUM[i] + P_LVL) <= P_LEN)) {
k = true;
break;
}
}

通过这段使用 OpenMP 的代码，我将 4 核处理器中的 2 倍到 3 倍之间的时间缩短了：

k   = false;
#pragma omp parallel for shared(k)
for (ptrdiff_t i = 0; i < T_IND; i++) {
if (k)
continue;
if (T_RDY[i] && !(~T_RWS[i] & M_RWS) && ((T_NUM[i] + P_LVL) <= P_LEN))
k = true;
}

编辑：

有关所用数据的信息：

#define DIM_MAX     128
#define P_LEN       prb_lvl[0]
#define P_LVL       prb_lvl[1]
#define M_RWS       prb_mtx_rws[prb_lvl[1]]
#define T_RWS       prb_tab
#define T_NUM       prb_tab_num
#define T_RDY       prb_tab_rdy
#define T_IND       prb_tab_ind

extern  ptrdiff_t   prb_lvl [2];
extern  uint128_t   prb_mtx_rws [DIM_MAX];
extern  uint128_t   prb_tab [10000000];
extern  ptrdiff_t   prb_tab_num [10000000];
extern  bool        prb_tab_rdy [10000000];
extern  ptrdiff_t   prb_tab_ind;

但是，我没有获得大约 4 倍的改进这一事实意味着它引入了开销，我猜从 2 倍增加到 1.5 倍。 部分开销是不可避免的(创建和销毁线程(，但由于 OpenMP 不允许从并行循环break，并且我在每次迭代中添加了一个if，如果可能的话，我想摆脱它，因此存在一些新的开销。

我还可以应用任何其他优化吗？ 也许改用 pthreads。

我应该费心编辑一些程序集吗？

我正在使用带有 -O3 -flto 的 GCC 9(以及其他(。

编辑：

处理器： i7-5775C

但我计划使用其他具有更多内核的 x64 CPU。

Answer 1

您可以将 k 合并为位表，然后一次比较 64 个。 如果主表中的条目发生更改，请在位表中重新计算该位。

如果不同的查询使用不同的M_RWS或P_LVL或其他东西，则需要为单独的搜索输入提供单独的缓存。 或者，如果在更改之间执行多个查询，请为其当前值重建缓存。 但希望情况并非如此，否则全大写字母的名称具有误导性。

将 k 设置为位表

#define KSZ (10000000/64 + !!(10000000 % 63))
static uint64_t k[KSZ];
void init_k(void){
// We can split this up to minimize cache misses, see below
for (size_t i;i<10000000;++i)
k[i/64] |= (uint64_t)((!!T_RDY[i]) & (!(~T_RWS[i] & M_RWS)) &((T_NUM[i] + P_LVL) <= P_LEN) ) << (i&63);
}

您可以通过搜索非零 64 位块，然后使用 bitscan 查找该块中的位来查找 k 中的位索引：

size_t k2index(void){
size_t i;
for (i=0; i<KSZ;++i)
if (k[i]) break;
return 64 * i + __builtin_ctzll(k[i]);
}

您可能希望拆分数据读取，以便获得顺序数据访问(如前所述，每个表超过 40=80MB(，并且不会在每次迭代时都出现缓存未命中。

#define KSZ (10000000/64 + !!(10000000%63))
static uint64_t k[KSZ], k0[KSZ], k1[KSZ]; //use calloc instead?
void init_k(void){
//I split these up to minimize cache misses
for (size_t i;i<10000000;++i)
k[i/64] |= (uint64_t)(!!T_RDY[i]) << (i&63);
for (size_t i;i<10000000;++i)
k0[i/64] |= (uint64_t)(!(~T_RWS[i] & M_RWS)) << (i&63);
for (size_t i;i<10000000;++i)
k1[i/64] |= (uint64_t)((T_NUM[i] + P_LVL) <= P_LEN) << (i&63);
//now combine them 64 bits at a time
for (size_t i;i<KSZ;++i)
k[i] &= k0[i];
for (size_t i;i<KSZ;++i)
k[i] &= k1[i];
}

如果像这样拆分它，也可以在设置其他表时初始化(其中一些(它们。 或者，如果表已更新，您也可以更新 k 值。