Оптимизация Головная боль - удаление if из Look Up Table

Question

Я пытаюсь оптимизировать следующий фрагмент кода, который является узким местом в моем приложении. Что он делает: он принимает двойные значения value1 и value2 и пытается найти максимум, включая коэффициент коррекции. Если разница между обоими значениями больше 5,0 (LUT масштабируется в 10 раз), я могу просто взять максимальное значение этих двух. Если разница меньше 5.0, я могу использовать коррекционный коэффициент из LUT.

Есть ли у кого-нибудь идеи, что может быть лучшим стилем для этой части кода? Я не знаю, где я теряю время - это большое количество ifs или умножение на 10?

double value1, value2; 
// Lookup Table scaled by 10 for (ln(1+exp(-abs(x)))), which is almost 0 for x > 5 and symmetrical around 0. LUT[0] is x=0.0, LUT[40] is x=4.0. 
const logValue LUT[50] = { ... } 

if (value1 > value2) 
{ 
    if (value1 - value2 >= 5.0) 
    { 
     return value1; 
    } 
    else 
    { 
     return value1 + LUT[(uint8)((value1 - value2) * 10)]; 
    } 
} 
else 
{ 
    if (value2 - value1 >= 5.0) 
    { 
     return value2; 
    } 
    else 
    { 
     return value2 + LUT[(uint8)((value2 - value1) * 10)]; 
    } 
} 

Answer 1

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

double diff = abs(value1 - value2); 
double dmax = (value1 + value2 + diff) * 0.5; // same as (min+max+(max-min))/2 
if (diff > 5.0) 
    return dmax; 
return dmax + 4.473865638/(2.611112371+diff) + 0.088190879*diff + -1.015046114; 

P.S. Я не гарантирую, что это происходит быстрее, только потому, что это достаточно подходящий подход, чтобы стоить бенчмаркинга.

P.P.S. Можно изменить ограничения, чтобы придумать несколько разные константы, есть много вариаций. Вот еще один набор, который я сделал, когда разница между вашей таблицей и формулой всегда будет меньше 0,008, также каждое значение будет меньше, чем предыдущее.

return dmax + 3.441318133/(2.296924445+diff) + 0.065529678*diff + -0.797081529; 

Редактировать: Я испытал этот код (вторая формула) с 100 проходов против миллиона случайных чисел между 0 и 10, а также с исходным кодом от вопроса, MSalters currently accepted answer и перебор реализация max(value1,value2)+log(1.0+exp(-abs(value1-value2))). Я попробовал его на двухъядерном процессоре AMD Athlon и четырехъядерном процессоре Intel i7, и результаты были примерно согласованы. Вот типичный пробег:

• Оригинал: 1.32 секунд.
• MSalters: 1.13 секунд.
• Шахта: 0.67 секунд.
• Грубая сила: 4.50 секунд.

Процессоры получили невероятно быстро на протяжении многих лет, настолько быстро, что они могут выполнять несколько операций с плавающей запятой и делятся быстрее, чем они могут искать значение в памяти. Этот современный подход не только ускоряется на современном x86, но и более точен; ошибки аппроксимации в уравнении намного меньше ошибок шага, вызванных усечением ввода для поиска.

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

Answer 2

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

Answer 3

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

Вы пробовали профилирование?

Я также предлагаю попробовать использовать стандартную библиотеку и посмотреть, если это помогает (например, если он в состоянии использовать и процессор конкретных инструкций):

double diff = std::fabs(value1 - value2); 
double maxv = std::max(value1, value2); 
return (diff >= 5.0) ? maxv : maxv + LUT[(uint8)((diff) * 10)]; 

Answer 4

Вы вычисление value1 - value2 достаточно несколько раз в вашей функции. Просто сделайте это один раз.

Это отличное от uint8_t также может быть проблематичным. Что касается производительности, лучшим интегральным типом, используемым в качестве преобразования из double в integer, является int, так как наилучшим интегральным типом для использования индекса массива является int.

max_value = value1; 
diff = value1 - value2; 
if (diff < 0.0) { 
    max_value = value2; 
    diff = -diff; 
} 

if (diff >= 5.0) { 
    return max_value; 
} 
else { 
    return max_value + LUT[(int)(diff * 10.0)]; 
} 

Обратите внимание, что приведенное выше гарантирует, что индекс LUT будет находиться между 0 (включительно) и 50 (исключительно). Здесь нет необходимости в uint8_t.

Редактировать
После некоторых игр с некоторыми вариациями, это довольно быстро LUT на основе приближения к log(exp(value1)+exp(value2)):

#include <stdint.h> 

// intptr_t *happens* to be fastest on my machine. YMMV. 
typedef intptr_t IndexType; 

double log_sum_exp (double value1, double value2, double *LUT) { 
    double diff = value1 - value2; 
    if (diff < 0.0) { 
    value1 = value2; 
    diff = -diff; 
    } 
    IndexType idx = diff * 10.0; 
    if (idx < 50) { 
    value1 += LUT[idx]; 
    } 
    return value1; 
} 

Интегральный тип IndexType является одним из ключей к форсированию вещи вверх. Я тестировал с clang и g ++, и оба указали, что литье на intptr_t (long на моем компьютере) и использование intptr_t в качестве индекса в LUT быстрее других интегральных типов. Это значительно быстрее, чем некоторые типы. Например, unsigned long long и uint8_t невероятно плохие выборы на моем компьютере.

Тип - это не просто подсказка, по крайней мере, с использованием компиляторов, которые я использовал. Эти компиляторы сделали именно то, что ему сказал код в отношении преобразования из типа с плавающей точкой в ​​интегральный тип, независимо от уровня оптимизации.

Еще одна ошибка скорости получается из сравнения интегрального типа с 50 в отличие от сравнения типа с плавающей точкой с 5.0.

Последняя удача скорости: не все компиляторы созданы равными. На моем компьютере (YMMV), g++ -O3 генерирует значительно более медленный код (на 25% медленнее с этой проблемой!), Чем clang -O3, который, в свою очередь, генерирует код, который немного медленнее, чем сгенерированный clang -O4.

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

Answer 5

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

double maxval = value1; 
double difference_scaled = (value1-value2)*10; 
if (difference < 0) 
{ 
    difference = -difference; 
    maxval = value2; 
} 
if (difference < 50) 
    return maxval+LUT[(int)difference_scaled]; 
else 
    return maxval; 

Попробуйте это и сообщите мне, улучшит ли производительность вашей программы.

Answer 6

Я бы, наверное, написал код немного отличается для обработки value2<value1 случая:

if (value2 < value1) std::swap(value1, value2); 
assert(value1 <= value2); // Assertion corrected 
int diff = int((value2 - value1) * 10.0); 
if (diff >= 50) diff = 49; // Integer comparison iso floating point 
return value2 + LUT[diff]; 

Answer 7

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

Изменение значения LUT[] на статическую переменную позволило мне увеличить скорость на 600% (с 3,5 до 0,6 с). Что близко к абсолютному минимуму теста, который я использовал (0,4 с). Посмотрите, работает ли это и перепрофилируется, чтобы определить, нужна ли дальнейшая оптимизация.

Для справки, я просто сроков исполнения этого цикла (100 миллионов итераций внутреннего цикла) в VC++ 2010:

int Counter = 0; 

for (double j = 0; j < 10; j += 0.001) 
    { 
     for (double i = 0; i < 10; i += 0.001) 
     { 
      ++Counter; 
      Value1 += TestFunc1(i, j); 
     } 
    }