我有一个循环大约需要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核处理器中减少了2x到3x的时间：
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。
我应该麻烦编辑一些程序集吗？
[我正在将GCC 9与-O3 -flto一起使用。
编辑：
CPU：i7-5775C
但是我计划使用具有更多内核的其他x64 CPU。
您可以将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] |= ((!!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]);
}
[您可能希望拆分数据读取，以便获得顺序的数据访问（每个表都超过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] |= (!!T_RDY[i]) << (i%63);
for (size_t i;i<10000000;++i)
k0[i/64] |= (!(~T_RWS[i] & M_RWS)) << (i%63);
for (size_t i;i<10000000;++i)
k1[i/64] |= ((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值。
统计上，匹配将位于中间，这意味着不必要的迭代将大约占其中一半。假设在必要的迭代中使用的表达式if (T_RDY[i] && !(~T_RWS[i] & M_RWS) && ((T_NUM[i] + P_LVL) <= P_LEN))由许多运算组成，则单个if (k) continue;对最终时间的影响不会很大，即使它执行的次数大约是大表达式的两倍。
此外，在速度上没有太多收获；可以循环直到LUT的中间，检查k，如果为false，则继续循环直到结束，以尝试赢得一些时间，但平均而言不是很长的时间。
自定义pthread也可以通过调整线程数来减少线程的开销，但是鉴于可以预期的小收益，编程时间将不值得。
此外，随着CPU中内核的增多，可以获得的时间会更短，因此，使用pthread编写非常复杂的循环或将循环划分为多个步骤的理由就更少了。
TL，DR：
存在一些可以稍微改善时间的可能性，但是浪费时间来编程它们是不值得的。