оптимизация — C ++ Eigen Library — Квадратичное программирование, фиксированная и динамическая производительность, производительность
Я занимаюсь квадратичным программированием и видел разные библиотеки. Я видел различные Eigen варианты QuadProg ++ (Форумы KDE, Бенджамин Стивенс, Сообщения StackOverflow). Просто в качестве теста я раздвоил собственный вариант Вингсита, доступен на GitHub, реализовать задачи размера компиляции для измерения производительности с помощью шаблонов.
Я обнаружил, что у меня хуже производительность в шаблоне, чем в случае динамического размера (MatrixXD / VectorXD) из кода wings. Я знаю, что это не простой вопрос, но кто-нибудь может увидеть причину, почему это может быть?
Примечание: мне нужно увеличить размер проблемы / количество итераций, я опубликую это, как только смогу.
РЕДАКТИРОВАТЬ: я использую GCC 4.6.3 на Ubuntu 12.04. Вот флаги, которые я использую (модифицировано из кода wings):
CFLAGS = -O4 -Wall -msse2 -fopenmp # option for obj
LFLAGS = -O4 -Wall -msse2 -fopenmp # option for exe (-lefence ...)
Решение
Преимущества кода статического размера, как правило, уменьшаются по мере увеличения размеров. Типичные преимущества кода статического размера в основном включают (но не ограничиваются) следующее:
- выделение на основе стека, которое выполняется быстрее, чем выделение из кучи. Однако при больших размерах выделения на основе стека больше не осуществимы (переполнение стека) или даже полезны с точки зрения предварительной выборки и местоположения ссылки.
- Развертывание цикла, когда компилятор видит небольшой цикл статического размера, он может просто развернуть его и, возможно, использовать инструкции SSE. Это не относится к большим размерам.
Другими словами, для небольших размеров (до N = 12 или около того) статический код может быть намного лучше и быстрее, чем эквивалентный динамически изменяемый код, если компилятор довольно агрессивно относится к встраиванию и циклу разворачивания. Но когда размеры больше, нет смысла.
Кроме того, у статического размера есть ряд недостатков:
- Нет эффективных стратегий перемещения-семантики / обмена / копирования-при-записи, поскольку такой код обычно реализуется с помощью статических массивов (для получения преимуществ, упомянутых выше), которые нельзя просто поменять местами (например, поменять местами внутренний указатель).
- Большие исполняемые файлы, которые содержат функции, которые распространяются. Допустим, у вас есть один шаблон функции для умножения двух матриц, и поэтому для каждой комбинации размеров создается новая скомпилированная функция (встроенная или нет). Затем у вас есть некоторый алгоритм, который выполняет много умножений матриц, и при каждом умножении придется переходить (или выполнять inline) специализацию для этой комбинации размеров. В конце концов, вы получите намного больше кода, который необходимо кэшировать, а затем пропадание кэша станет намного более частым, и это полностью разрушит производительность вашего алгоритма.
Итак, урок, который можно извлечь из этого, состоит в том, чтобы использовать векторы и матрицы статического размера только для небольших вещей, таких как 2-6-мерные векторы или матрицы. Но помимо этого, предпочтительнее использовать код динамического размера (или попробовать код статического размера, но убедиться, что он работает лучше, потому что это не гарантировано). Итак, я бы посоветовал вам пересмотреть свою идею использования кода со статическим размером для более крупных проблем.
Другие решения
Других решений пока нет …