使用 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;

然而，事实上我并没有得到大约的改善。 4x 意味着它引入了开销，我猜是从 2x 到 1.5x。部分开销是不可避免的（创建和销毁线程），但是由于 OpenMP 不允许 break 来自并行循环并且我添加了一个 if每次迭代，如果可能的话，我想摆脱它。

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

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

我将 GCC 9 与 -O3 -flto（以及其他）一起使用。

编辑：

CPU：i7-5775C

但我打算使用其他具有更多内核的 x64 CPUs。

Answer 1

您可以将 k 合并为位 tables，然后一次进行 64 次比较。如果主 table 中的条目发生更改，则重新计算位 table.

中的该位

如果不同的查询使用不同的 M_RWS 或 P_LVL 之类的东西，那么您需要为单独的搜索输入使用单独的缓存。或者，如果您在更改之间进行多次查询，则为它们的当前值重建缓存。但希望情况并非如此，否则全部大写的名称会产生误导。

设置k为位table

#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 位块，然后使用位扫描找到该块中的位来找到 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]);
}

您可能希望拆分数据读取，以便获得顺序数据访问（如所述，每个 table 超过 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];
}

如果像这样拆分，您还可以在设置其他 table 时初始化（其中一些）它们。或者，如果 tables 更新了，您也可以更新 k 值。

使用 OpenMP 对巨大数组的线性搜索循环进行微优化：无法在命中时中断

Micro-optimizing a linear search loop over a huge array with OpenMP: can't break on a hit

c

loops

pthreads

openmp

micro-optimization