Головная боль при оптимизации - удаление if из таблицы поиска

Question

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

У кого-нибудь есть идеи, что может быть лучше для этого фрагмента кода?Я не знаю, где я теряю время - большое ли это число или умножение на 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

Я бы написал код немного по-другому, чтобы обработать случай 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 2

Пару минут игры с 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;

PS Я не гарантирую, что это быстрее, только то, что это достаточно другой подход кстоит сравнить.

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

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

Редактировать: Iпроверил этот код (вторая формула) с 100 проходами против миллиона случайных чисел от 0 до 10, вместе с исходным кодом из вопроса, MSalters в настоящее время принял ответ , и реализацией грубой силы 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 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

Я собираюсь предположить, что при вызове функции вы, скорее всего, получите часть, в которой вам придется использовать справочную таблицу, а не части >=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 5

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

Изменение 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);
        }
    }

Answer 6

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

Это приведение к uint8_t также может быть проблематичным.Что касается производительности, то наилучшим целочисленным типом для использования при преобразовании из двойного в целое является 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) * ​​1036 * генерирует значительно более медленный код (на 25% медленнее с этой проблемой!), Чем clang -O3, который, в свою очередь, генерирует код, который немного медленнее, чем сгенерированный clang -O4.

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

Answer 7

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