производительность — таблица соответствия и эффективность вычислений во время выполнения

Question

производительность — таблица соответствия и эффективность вычислений во время выполнения

Мой код требует непрерывного вычисления значения из следующей функции:

inline double f (double x) {
return ( tanh( 3*(5-x)  ) *0.5 + 0.5);
}

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

Я знаю, что эффективность справочной таблицы зависит от размера самой таблицы и способа ее создания. В настоящее время я не могу использовать менее 100 МБ и могу использовать до 2 ГБ. Значения между двумя точками в матрице будут линейно интерполированы.

Будет ли использование таблицы поиска быстрее, чем вычисления? Кроме того, будет ли использование N-мерной матрицы лучше, чем 1-D std :: vector, и какой порог (если таковой имеется) для размера таблицы, который не следует пересекать?

1

c++caching lookup-tables optimization performance

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Пока мне не разрешено использовать менее 100 МБ, и я могу использовать до 2 ГБ. Линейная интерполяция будет использоваться для точек между точками в матрице.

Если бы у вас была огромная таблица поиска (как вы сказали, сотни МБ), которая не подходит для кэширования — скорее всего, время поиска в памяти будет намного выше, чем сам расчет. Оперативная память «очень медленная», особенно при выборке из случайных мест огромных массивов.

Вот синтетический тест:

живое демо

#include <boost/progress.hpp>
#include <iostream>
#include <ostream>
#include <vector>
#include <cmath>

using namespace boost;
using namespace std;

inline double calc(double x)
{
return ( tanh( 3*(5-x)  ) *0.5 + 0.5);
}

template<typename F>
void test(F &&f)
{
progress_timer t;
volatile double res;
for(unsigned i=0;i!=1<<26;++i)
res = f(i);
(void)res;
}

int main()
{
const unsigned size = (1 << 26) + 1;
vector<double> table(size);
cout << "table size is " << 1.0*sizeof(double)*size/(1 << 20) << "MiB" << endl;
cout << "calc ";
test(calc);
cout << "dummy lookup ";
test([&](unsigned i){return table[(i << 12)%size];}); // dummy lookup, not real values
}

Выход на моей машине:

table size is 512MiB
calc 0.52 s

dummy lookup 0.92 s

4