Производительность вычисления constexpr во время компиляции

Question

У меня есть несколько нетривиальных функций C ++ 17, помеченных как constexpr.Они выполняют вычисления, связанные с графами (обход в глубину) и общие алгоритмы (например, находят, сортируют, уникальные ...).

Если я попытаюсь форсировать вычисление во время компиляции, поместив результат вconstexpr глобальная переменная, может произойти 3 вещи:

1. Для вычислений небольшого размера (чтобы дать представление, скажем, графики ~ 100 узлов, узлы которых являются более или менее целыми числами), компиляциянормально (занимает ~ 2 с)
2. При ~ 500 узлах компиляция занимает ~ 1 мин и занимает 30 ГБ памяти (!).
3. При ~ 1000 узлах компиляция требует слишком много памяти для менячтобы он закончил.

Если я удаляю квалификаторы constexpr и запрашиваю вычисления во время выполнения, компиляция и выполнение выполняются очень быстро (менее 5 с)

Я использовалg ++ 8.2 с -O3 -std = c ++ 17.

Почему так долго?Известен ли g ++ для задач оптимизации во время компиляции constexpr?Какую производительность следует ожидать от constexpr функций во время компиляции?Из того, что я понимаю, компилятор превращается в интерпретатор для constexpr вычислений.Но я абсолютно не сомневаюсь, что оценка той же программы на Python будет очень быстрой, учитывая очень маленький размер данных.

Edit : здесь упоминаются такие проблемы (Блог разработчика GCC)

Answer 1

g ++ запоминает структуры времени компиляции.Более того, структуры времени компиляции могут создаваться и проверяться вдоль как ветви, которую вы хотите взять, так и той, которую вы не выбираете, если не будете осторожны.

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

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

Я имею в виду, исследуйте действительно простое:

std::conditional_t< (A<B), make_type_A<Ts...>, make_type_B<Ts...> >

Автор этого кода, вероятно, намеревался сделать только один тип,но этот код требует создания обоих типов.

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

Для каждого вызова отрабатывайтеРазмер государства требуется.Сложите общее необходимое состояние.Добавьте 10-кратные накладные расходы.

Вы также можете проанализировать, какова O-нотация вашей проблемы, имея больше выборок, чем 2.Проверьте 100, 200, 300, 400, 500 размеров графиков.Попробуйте линейные графики, тривиальные графики, полные графики, случайные графики с постоянным или процентным соединением.

O-обозначение роста во время компиляции может помочь вам сузить суть проблемы.Если он является линейным, полиномиальным или экспоненциальным, вы будете искать различные виды проблем.

Линейный с резким перегибом означает, что вы попали в узкое место ресурса.Может быть, память.Начните составлять график использования других ресурсов и посмотрите, сможете ли вы найти узкое место.

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

Полиномиал становится интересным.Порядок полинома (лог-график может помочь найти это) может сказать, какая операция вас обманывает.Как если бы вы знали, что ваш обычный алгоритм равен O (n ^ 3), это означает, что вы ищете тройной цикл.Время компиляции O (n ^ 3) означает, что вы каким-то образом создаете экземпляр эквивалента тройного цикла.