Микро-оптимизация цикла линейного поиска по огромному массиву с OpenMP: не может сломаться при попадании

Question

У меня есть цикл, который занимает примерно от 90% до 99% времени программы.Он читает огромную LUT, и этот цикл выполняется> 100 000 раз, поэтому он заслуживает некоторой оптимизации.

EDIT:

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, я сократил время между 2x и 3x в 4-ядерном процессоре:

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;
}

EDIT:

Информация о данныхиспользуется:

#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 (среди прочих).

EDIT:

Процессор: i7-5775C

Но я планирую использовать другие процессоры x64 с большим количеством ядер.

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);
}

Вы можете найти битовый индекс в k, выполнив поискненулевой 64-битный блок, затем с помощью битового сканирования для нахождения бита в этом блоке:

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 = 80 МБ, как описано), и не пропускайте кэш-память при каждой итерации.

#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.