Оптимизация прогноза прогноза ветвления и ветвления

Question

Мой код часто вызывает вызовы функции с несколькими (непредсказуемыми) ветвями. Когда я профилировал, я обнаружил, что это небольшое узкое место, причем большинство процессорных времени используется для условных JMP.

Рассмотрим следующие две функции, в которых оригинал имеет несколько явных ветвей.

void branch_example_original(void* mem, size_t s) 
{ 
    if(!(s & 7)) { 
     /* logic in _process_mem_64 inlined */ 
    } 
    else if(!(s & 3)) { 
     /* logic in _process_mem_32 inlined */ 
    } 
    else if(!(s & 1)) { 
     /* logic in _process_mem_16 inlined */ 
    } 
    else { 
     /* logic in _process_mem_8 inlined */ 
    } 
} 

Вот новая функция, в которой я попытался удалить ветви, вызывающие узкое место.

void branch_example_new(void* mem, size_t s) 
{ 
    const fprocess_mem mem_funcs[] = {_process_mem_8, _process_mem_16, _process_mem_32, _process_mem_64}; 
    const uint32_t magic = 3 - !!(s & 7) - !!(s & 3) - !!(s & 1); 
    mem_funcs[magic](mem, size >> magic); 
} 

Однако, когда я профилированный новый код, производительность увеличилась лишь на ~ 20%, а сам вызов (к FUNC в массиве mem_funcs) занимает очень много времени.

Является ли второй вариант просто более неявным условным, поскольку CPU все еще не может предсказать функцию, которая будет вызвана? Правильно ли я полагаю, что это связано с предсказанием целевой ветви?

Почему это происходит, и есть ли другие решения?

Edit:

Спасибо за идеи, но я хотел бы объяснить, почему это происходит, как хорошо.

Answer 1

Является ли второй вариант просто более неявным условным, поскольку CPU все еще не может предсказать функцию, которая будет вызвана? Правильно ли в , предполагая, что это связано с предсказанием целевой ветви?

Да, для безусловных косвенных ветвей требуется, чтобы процессор-бэк-процессор получал процессор, чтобы выяснить, где взять код из следующего. Современные процессоры в значительной степени конвейерны и должны получать код намного раньше того, где они выполняются, если они избегают пузырей в трубе, где им нечего делать. Ожидание до magic рассчитывается слишком поздно, чтобы избежать пузырька выборки команд. Полагаю, что счетчики производительности покажут промахи BTB как неверный прогноз отрасли.

Как я уже сказал в комментарии, если вы можете перестроить свой код, чтобы выполнить скалярное вступление и очистку вокруг векторизованного цикла. Intro обрабатывает элементы до тех пор, пока вы не достигнете выровненного элемента. Цикл очистки обрабатывает случаи, когда после последнего полного вектора осталось ненулевое количество элементов, оставшихся для обработки. Тогда вы не застреваете, выполняя скалярную петлю только потому, что размер или выравнивание первого элемента не был идеальным.

---

В зависимости от того, что вы обрабатываете, если это нормально, чтобы повторить работу и перекрытие, то вы можете сделать стартап безфилиального, что делает невыровненный кусок, то остальные выровненным.Некоторые библиотеки, вероятно impement memset что-то вроде этого:

// not shown: check that count >= 16 
endp = dest + count; 
unaligned_store_16B(dest); // e.g. x86 movdqu 
dest+=16; 
dest &= ~0xf; // align by 16, first aligned write overlaps by up to 15B 
for (; dest < endp-15 ; dest+=16) { 
    aligned_store_16B(dest); // e.g. x86 movdqa 
} 
// handle the last up-to-15 bytes from dest to endp similarly. 

Это делает обработку выровненного начала суков петли, потому что вы не заботитесь сколько выровненное начало перекрывается.

Обратите внимание, что большинство функций с одним буфером не повторяются. например на месте a[i] *= 2 или sum+=a[i] необходимо избегать обработки одного и того же входа дважды. Обычно со скалярным циклом, пока вы не достигнете выровненного адреса. a[i] &= 0x7f, или maxval = max(a[i], maxval) являются исключениями.

---

функция с двумя независимыми указателями, которые могут быть смещен различными количествами являются хитрее. Вы должны быть осторожны, чтобы не менять относительное смещение с помощью маскировки. memcpy - это самый простой пример функции, которая обрабатывает данные из src в буфер dest. memcpy должен работать, если (src+3) %16 == 0 и (dest+7) %16 ==0. Если вы не можете установить ограничения на вызывающих абонентов, то лучше всего вы можете сделать в общем случае либо каждую нагрузку, либо каждое хранилище, выровненное в основном цикле.

На x86, выровненные сдвигают (movdqu и друзья) так же быстро, как выравнивание требуемых для версии когда адрес выровнен. Таким образом, вам не нужна отдельная версия цикла для специального случая, когда src и dest имеют одинаковое (неправильное) выравнивание, а нагрузки и магазины могут быть выровнены. IIRC, это верно для Intel Nehalem и более новых процессоров, а также для недавних AMD.

// check count >= 16 
endp = dest + count; 
unaligned_copy_16B(dest, src); // load with movdqu, store with movdqu 
// src+=16; dest+=16; // combine this with aligning dest, below 

dest_misalign = dest & 0xf; // number of bytes the first aligned iteration will overlap 
src += 16 - dest_misalign; // src potentially still misaligned 
dest += 16 - dest_misalign; // dest aligned 

for (; dest <= endp-16 ; src+=16, dest+=16) { 
    tmpvec = unaligned_load_16B(src); // x86 movdqu is fast if src is aligned 
    aligned_store_16B(dest, tmpvec); // x86 movdqa 
} 
// handle the last dest to endp bytes. 

---

совмещенного приемник, возможно, более вероятно, чем выровненный источник. Никакая дублирующаяся повторяющаяся работа не выполняется, когда выровненный указатель уже выровнен.

Если вы не используете memcpy, это может быть преимуществом для выравнивания src, чтобы загрузка могла складываться в другую команду в качестве операнда памяти. Это сохраняет инструкцию, и во многих случаях также сохраняет внутренний процессор Intel.

Для случая, когда src и dest имеют разные выравнивания, я не тестировал, быстрее ли выполнять согласованные нагрузки и неустановленные магазины, или наоборот. Я выбрал выровненные хранилища из-за потенциальных возможностей загрузки-> нагрузки для коротких буферов. Если выравнивающий буфер будет выровнен, а только несколько векторов длинны и будут прочитаны снова сразу, то выровненные нагрузки из dest будут останавливаться на ~ 10 циклов (Intel SnB), если нагрузка пересекает границу между двумя предыдущими магазинами, t дошел до кеша L1. (т. е. переадресация хранилища). См. http://agner.org/optimize/ для получения информации о низкоуровневых деталях, подобных этому (например, руководство по микроархитектуре.)

Сохранение пересылки с memcpy на нагрузки в следующем цикле произойдет только в том случае, если буферы невелики (возможно, до 64B?). , или если ваш следующий цикл начнет считываться с конца буфера (который все еще будет в кеше, даже если начало уже было выведено). В противном случае хранилища в начале буфера сделают это из буфера хранилища до L1, поэтому сохранение в магазине не будет входить в игру.

Возможно, что для больших буферов с различными выравниваниями выровненные нагрузки и неуравновешенные магазины будут работать лучше. Я просто делаю что-то здесь, но это может быть правдой, если несобранные магазины могут быстро уйти в отставку, даже если они пересекают линию кэша или линию страницы. Конечно, невыровненные нагрузки не могут уйти в отставку, пока данные не будут загружены. С большим количеством инструкций по загрузке/хранению в полете меньше шансов на то, что промахи в кеше не сработают.(Вы потенциально пользуетесь преимуществами буферов загрузки/хранения процессора.) Опять же, чистая спекуляция. Я попробовал google, если неудовлетворенные магазины были лучше или хуже, чем неуравновешенные нагрузки, но просто получили обращения о том, как их выполнять, и штрафы за несогласованность, которые применяются к обоим.

Answer 2

Вы могли бы попробовать что-то вроде этого:

switch(s & 7) { 
case 0: 
    /* _process_mem_64 */ 
    break; 
case 1: 
case 3: 
case 5: 
case 7: 
    /* _process_mem_8 */ 
    break; 
case 2: 
case 6: 
    /* _process_mem_16 */ 
    break; 
case 4: 
    /* _process_mem_32 */ 
    break; 
} 

Это включает в себя только один прыжок в таблицу переходов, и не требует инструкции вызова.

Answer 3

Современный процессор имеет не только предсказание ветвления, но и предсказание скачка. Например, если вы вызываете виртуальную функцию, она может предсказать, что фактическая функция будет такой же, как и в предыдущем вызове, и начнет выполнение до того, как указатель на функцию будет фактически прочитан - если предсказание скачка было неправильным, все становится медленным.

То же самое происходит в вашем коде. Вы больше не используете предсказание ветвления, но процессор использует предсказание предсказания, чтобы предсказать, какой из четырех указателей функции вызван, и это замедляется, когда указатели функций непредсказуемы.