Ответ 1
Не зная ничего о вашей проблеме или вашей текущей реализации, один (несколько) простой способ повысить производительность (в некоторой степени) - это вручную предварительно выбрать значения, которые будет действовать ваша функция "sum".
Игнорируя нюансы архитектуры и компилятора, ручная предварительная выборка может выглядеть так:
SmallStruct values [value_count] = {/*whatever*/};
int indices [index_count] = {/*whatever*/};
...
SmallStruct v = values[indices[0]];
for (int i = 1; i < index_count; ++i)
{
SmallStruct v_next = values[indices[i]];
DoSomethingWith (v); // Note the *v*
v = v_next; // You don't want to copy, but this is the simplest form
}
DoSomethingWith (v); // Do the final item
Вышеприведенная является самой простой возможной формой предварительной выборки. Вы можете немного развернуть цикл, чтобы избежать упомянутого выше копирования, а также вы, вероятно, захотите сделать больше, чем одну предварительную выборку.
Эта оптимизация работает, потому что большинство современных (всех?) современных архитектур могут иметь более одного запроса памяти в полете, а это означает, что эти запросы перекрываются, а среднее время ожидания для этих (предположительно нераскрытых) запросов делится на их concurrency (что хорошо!) Итак, неважно, сколько у вас неиспользуемых строк кеша; важным фактором является количество одновременных считываний памяти, которые система памяти может поддерживать в любой момент времени.
Заметка о влиянии линий кэша
Вышеприведенный (по общему признанию, упрощенный) код игнорирует два очень важных факта: весь SmallStruct не может быть прочитан в одном доступе к памяти (с точки зрения ЦП), что плохо, и эта память всегда читается в единицах строк кеша (64 или 128 байт, в наши дни), что очень хорошо!
Итак, вместо того, чтобы читать весь values[indices[i]] в v_next, мы можем просто прочитать один байт, и если массив values правильно выровнен, значительный объем памяти (одна полная строка кэша) будут загружены и под рукой для возможной обработки.
Два важных момента:
- Если ваш
SmallStructна самом деле невелик и не будет полностью вписываться в строку кэша, вы должны изменить его элементы, чтобы убедиться, что его части, которые требуются вDoSomethingWith(), смежны и упакованы и подходят в одной строке кэша. Если они все еще не подходят, вам следует рассмотреть возможность разделения вашего алгоритма на два или более проходов, каждый из которых работает с данными, которые вписываются в одну строку кэша. - Если вы просто прочитали один байт (или одно слово или что-то еще) из следующего значения, которое вы получите, убедитесь, что компилятор не оптимизирует это чтение!
Альтернативные реализации
Вторая точка выше может быть выражена в коде, например:
touch (&values[indices[0]]);
for (int i = 0; i < index_count; ++i)
{
if (i + 1 < index_count)
touch (&values[indices[i + 1]]);
DoSomethingWith (values[indices[i]]);
}
Функция touch() семантически подобна (хотя реализация, вероятно, будет более сложной).
void touch (void * p)
{
char c = *(char *)p;
}
Чтобы предварительно выбрать несколько значений, вы должны сделать что-то вроде этого: (Обновление: я изменил свой код на (я считаю) более эффективную реализацию.)
const int PrefetchCount = 3;
// Get the ball rolling...
for (int j = 0; j < PrefetchCount; ++j)
touch (&values[indices[j]]);
for (int i = 0; i < index_count; ++i)
{
if (i + PrefetchCount < index_count)
touch (&values[indices[i + PrefetchCount]]);
DoSomethingWith (values[indices[i]]);
}
Снова отметим, что все описанные выше реализации очень просты и упрощены. Кроме того, если вы слишком много предварительно выберете, вы можете снести свой кеш L1 и свою производительность.
Выполнение фактической предварительной выборки
У процессора x86-64 есть инструкция, которую вы используете, чтобы попросить ЦП предварительно запрограммировать данные памяти в кеш-строке в свои кеши. Фактически, используя эту инструкцию, вы даете подсказку процессору о том, что ваше конкретное место памяти будет использоваться вашим приложением, а процессор попытается привести его в кеш. Если вы сделаете это достаточно быстро, данные будут готовы к тому времени, когда вам это понадобится, и ваши вычисления не будут остановлены.
Инструкция PREFETCH*, и вы можете использовать встроенные функции для компилятора, а не прибегать к сборке. Эти встроенные функции называются _mm_prefetch для компиляторов Microsoft и Intel С++ и __builtin_prefetch для GCC. (Если вы закончили использовать это, просто помните, что вам нужен самый низкий уровень предварительной выборки, т.е. T0.)
Обратите внимание, что они входят в реализацию функции touch, которую я использовал выше.
Я не знаю никакой библиотеки, которая делает это многоразовым способом. Кроме того, я не знаком с библиотеками С#, чтобы узнать, доступны ли они там или нет.