Ускорение код C++

Мне любопытно, почему вы сделали это шаблон, когда вы сказали, что вычисления выполняются с использованием двойников? Почему бы не написать стандартный метод, функцию или просто 'x * x'?

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

Есть ли причина, по которой вы реализуете собственный оператор sqr?

Вы пробовали использовать его в libm, он должен быть сильно оптимизирован.

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

Я думаю, что необходим более подробный анализ ваших данных. Сказать, что большая часть времени в программе тратится на выполнение команд MOV и JUMp, может быть правильным, но это не поможет вам сильно оптимизировать. Информация слишком низкого уровня. Например, если вы знаете, что целочисленные аргументы достаточно хороши для dist2, а значения находятся в диапазоне от 0 до 9, тогда предварительно кэшированная таблица будет состоять из 1000 элементов - не слишком большой. Вы всегда можете использовать код для его генерации.

Вы разворачивали петли? Разбитая матрица? Искал места, где можно обойтись поиском по таблице вместо фактического расчета.

Наиболее радикальным было бы применение методов, описанных в: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.8660&rep=rep1&type=pdf хотя это, по общему признанию, трудное чтение, и вам следует получить помощь от кого-то, кто знает Common Lisp, если вы этого не сделаете.

(зачеркните это!! sqr != sqrt )

Посмотрите, применим ли "Быстрый sqrt" в вашем случае:

http://en.wikipedia.org/wiki/Fast_inverse_square_root

Всего несколько мыслей, но вряд ли я добавлю что-нибудь ценное после 18 ответов :)

Если вы тратите 80% времени на эти две функции, я могу представить себе два типичных сценария:

Ваш алгоритм как минимум полиномиальный
Поскольку ваши данные кажутся пространственными, возможно, вы может снизить O (n), введя пространственные индексы?

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

Также в отношении кеша вы должны определить требуемую точность (и диапазон ввода) - может быть, можно использовать какой-то поиск / кеш?

Посмотрите на контекст. Вы ничего не можете сделать для оптимизации такой простой операции, как x * x . Вместо этого вам следует взглянуть на более высокий уровень: откуда вызывается функция? Как часто? Почему? Можете ли вы уменьшить количество звонков? Можете ли вы использовать инструкции SIMD для выполнения умножения нескольких элементов за раз?

Возможно, вы выгрузите целые части алгоритма на GPU?

Определена ли функция таким образом, чтобы ее можно было встроить? (в основном, его определение видно на местах вызова)

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

И, конечно же, проверьте сгенерированную сборку и убедитесь, что она соответствует вашим ожиданиям.

По подсчету операций я не понимаю, как это можно ускорить, не углубляясь в аппаратную оптимизацию (например, SSE), как указывали другие. Альтернативой является использование другой нормы , например, 1-норма - это просто сумма абсолютных значений членов. Тогда умножения не нужны. Однако это изменяет базовую геометрию вашего пространства, меняя видимые интервалы между объектами, но это может не иметь значения для вашего приложения.

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

Если вы уверены, что все вызовы необходимы, вы можете выжать последнюю каплю производительности, используя компилятор, учитывающий архитектуру. У меня были хорошие результаты, например, при использовании компилятора Intel на x86.

Вы используете Visual Studio? В таком случае вам может потребоваться указать элемент управления с плавающей запятой, используя / fp fast в качестве переключателя компиляции. Взгляните на Режим fp: fast для семантики с плавающей запятой . В GCC есть множество оптимизаций с плавающей запятой -fOPTION, которые вы, возможно, захотите рассмотреть (если, как вы говорите, точность не является большой проблемой).

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

Что сообщает ваш профилировщик, происходит внутри dist2 . Вы действительно используете 100% ЦП или у вас отсутствует кэш и вы ждете загрузки данных?

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

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

Если вы сможете организовать свои данные соответствующим образом, тогда вы вполне сможете использовать здесь оптимизацию SIMD. Для эффективной реализации вы, вероятно, захотите дополнить свою структуру Point так, чтобы она имела 4 элемента (т.е. добавить четвертый фиктивный элемент для заполнения).

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

Предполагая архитектуру x86, обязательно разрешите компилятору генерировать код с использованием инструкций SSE2 (пример набора инструкций SIMD), если они доступны на целевой архитектуре. Чтобы дать компилятору наилучшую возможность оптимизировать их, вы можете попробовать объединить операции sqr в пакет (инструкции SSE2 должны быть способны выполнять до 4 операций с плавающей точкой или 2 двойных операций одновременно в зависимости от инструкции... но, конечно, это возможно только в том случае, если у вас есть готовые входы для более чем одной операции). Я бы не был слишком оптимистичен относительно способности компилятора понять, что он может объединять их в пакет... но вы можете, по крайней мере, настроить свой код так, чтобы это было возможно теоретически.

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

Чтобы пойти еще дальше, (и как уже упоминал glowcoder) вы можете выполнять эти операции на GPU. Для вашего конкретного случая имейте в виду, что GPU часто не поддерживают двойную точность плавающей точки... хотя, если это подходит для того, что вы делаете, вы получите на порядки лучшую производительность таким образом. Наберите в Google GPGPU или что-то подобное и посмотрите, что лучше для вас.

Если у вас есть несколько таких задач, и вы выполняете графические или "графикоподобные" задачи (тепловое моделирование, почти любое 3d моделирование), вы можете рассмотреть возможность использования OpenGL и перегрузки задач на GPU. Это позволит выполнять вычисления параллельно, с высокой оптимизацией операционной мощности. В конце концов, можно ожидать, что что-то вроде distance или distancesq будет иметь свой собственный опкод на GPU.

Исследователь из местного университета перегрузил почти все свои 3d-вычисления для работы ИИ на GPU и добился гораздо более быстрых результатов.

Что такое Base ?

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

template<class T> inline T sqr(const T& x){return x*x;}
Base   dist2(const Point& p) const {
  return sqr(x-p.x) + sqr(y-p.y) + sqr(z-p.z);
}

Если переменные-члены p имеют тип Base , вы могли бы вызвать sqr для объектов Base, которые будут создавать временные объекты для вычитаемых координат. , в sqr , а затем для каждого добавленного компонента.

(Мы не можем сказать без определений классов)

Вы, вероятно, могли бы ускорить это, заставив вызовы sqr выполняться на примитивах и не используя Base , пока вы не дойдете до возвращаемого типа dist2 .

Другие возможности повышения производительности:

• Используйте операции без чисел с плавающей запятой, если вас устраивает меньшая точность.
• Используйте алгоритмы, которым не нужно столько вызывать dist2 , возможно, кэширование или использование транзитивного свойства.
• (это, вероятно, очевидно, но) Убедитесь, что вы компилируете с включенной оптимизацией.

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

РЕДАКТИРОВАТЬ: После того, как высказал Пол Ри, я переформулировал свой совет не утверждать, что операции с плавающей запятой всегда медленнее. Спасибо.

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

С другой стороны, если вы ищете близость, то вы можете передать функции dist2() ваше текущее минимальное значение. Таким образом, если sqr(x-p.x) уже больше вашего текущего минимального значения, вы можете избежать вычисления оставшихся двух квадратов.

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

Если sqr () используется только для примитивных типов, вы можете попробовать взять аргумент по значению вместо ссылки. Это избавит вас от косвенного обращения.

Я предлагаю два метода:

1. Переместите элементы структуры в локальные переменные в начале.
2. Выполните аналогичные операции вместе.

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

Вот код:

Base   dist2(const Point& p) const
{
    //  Load the cache with data values.
    register x1 = p.x;
    register y1 = p.y;
    register z1 = p.z;

    // Perform subtraction together
    x1 = x - x1;
    y1 = y - y1;
    z1 = z - z2;

    // Perform multiplication together
    x1 *= x1;
    y1 *= y1;
    z1 *= z1;

    // Perform final sum
    x1 += y1;
    x1 += z1;

    // Return the final value
    return x1;
}

Другой альтернативой является группировка по размерности. Например, сначала выполните все операции «X», затем Y и затем Z . Это может показать компилятору, что части независимы, и он может делегировать другому ядру или процессору.

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

Кроме того, вы можете исследовать использование других процессоров в системе. Например, BOINC Project может делегировать вычисления графическому процессору.

Надеюсь, это поможет.

См. инструкции SUBPD, MULPD и DPPD. (Для DPPD требуется SSE4)

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