Как объяснено в комментариях, такого рода замедление вполне ожидаемо от такой библиотеки, как GMP.
Построение double умножения являются одной из областей, где современные процессоры и компиляторы наиболее оптимизированы; Процессоры имеют несколько исполнительных блоков, которым удается выполнять параллельно несколько операций с плавающей запятой, часто с помощью компиляторов, которые пытаются автоматически векторизовать циклы (хотя это не особенно применимо к вашему случаю, поскольку ваш внутренний цикл сильно зависит от предыдущая итерация).
С другой стороны, во множественных динамических библиотеках точности, таких как GMP, каждая операция представляет собой большую работу - есть несколько ветвей, которые нужно проверить даже для проверки того, имеют ли оба операнда одинаковую / правильную степень точности, и алгоритмы вычисления. реализованы являются общими и адаптированы к конечной точке «высокой точности», что означает, что они не особенно оптимизированы для вашего текущего варианта использования (используя их с той же точностью, что и double); Кроме того, значения GMP могут выделять память при ее создании, что является еще одной дорогостоящей операцией.
Я взял вашу программу и слегка изменил ее, чтобы сделать ее параметрической по используемому типу (с #define), уменьшив сторону квадрата выборки (с 3200 до 800, чтобы ускорить тестирование) и добавив аккумулятор возвращаемого значения iterate, чтобы напечатать его в конце, чтобы проверить, все ли работает одинаково между различными версиями, и чтобы убедиться, что оптимизатор не сбрасывает цикл полностью.
Версия double на моей машине занимает примерно 0,16 секунды, и, столкнувшись с профилировщиком, демонстрирует совершенно плоский профиль в пламенном графе; все происходит в iterate.
Версия GMP вместо этого, как и ожидалось, занимает 45 секунд (в 300 раз; вы говорили о замедлении в 60 раз, но сравнивали с неоптимизированным базовым случаем) и более разнообразна:
Как и прежде, iterate занимает почти все время (поэтому мы можем полностью игнорировать linear_map, если речь идет об оптимизации). Все эти «башни» являются вызовами в коде GMP; материал __gmp_expr<...> не особенно важен - это всего лишь шаблонный шаблон, позволяющий оценивать сложные выражения без слишком большого количества временных значений, и он полностью встроен. Большая часть времени уходит на вершину этих башен, где выполняются фактические расчеты.
Действительно, в конечном итоге большую часть времени проводят в примитивах GMP и в распределении памяти:
Учитывая, что мы не можем касаться внутренних органов GMP, единственное, что мы можем сделать, - это быть более осторожными в использовании, поскольку каждая операция GMP действительно дорогая.
Действительно важно помнить, что, хотя компилятор может избежать многократного вычисления одних и тех же выражений для значений double, он не может делать то же самое для значений GMP, так как они оба имеют побочные эффекты (выделение памяти, внешняя функция). звонки) и слишком сложны, чтобы их можно было проверить в любом случае. В вашем внутреннем цикле мы имеем:
double x, y;
x = 0;
y = 0;
int i;
for (i = 0; i < 1000 && x*x + y*y <= 65536; i++) {
T xtemp = x*x - y*y + x0;
(T - это общий тип, который я использую, определенный как double или mpf_class)
Здесь вы вычисляете x*x и y*y дважды на каждой итерации. Мы можем оптимизировать его как:
T x = 0, y = 0, xsq, ysq;
for(i = 0; i < 1000; i++) {
xsq = x*x;
ysq = y*y;
if(xsq+ysq > 65536) break;
T xtemp = xsq - ysq + y0;
Повторно запуская версию GMP с этой модификацией, мы получаем 38 секунд, что на 18% лучше.
Обратите внимание, что мы держали xsq и ysq вне цикла, чтобы избежать их повторного создания на каждой итерации; это связано с тем, что в отличие от double значений (которые в конечном итоге являются просто регистровым пространством или, что еще хуже, стековым пространством, оба из которых свободны и обрабатываются компилятором статически), объекты mpt_class не могут заново создавать каждый время, на что намекает выдающаяся роль распределения памяти в трассировке профилировщика выше; Я не совсем осведомлен о внутренней работе оболочки GMP C ++, но я подозреваю, что она обладает оптимизацией, подобной std::vector - при присваивании уже выделенное значение сможет перерабатывать свое пространство при выделении вместо повторного выделения.
Следовательно, мы можем вывести из цикла даже определение xtemp
int iterate(T x0, T y0) {
T x = 0, y = 0, xsq , ysq, xtemp;
int i;
for (i = 0; i < 1000; i++) {
xsq = x*x;
ysq = y*y;
if(xsq+ysq > 65536) break;
xtemp = xsq - ysq + y0;
y = 2*x*y + y0;
x = xtemp;
}
return i;
}
, что сокращает время выполнения до 33 секунд, что на 27% меньше исходного времени.
Флеймграф похож на предыдущий, но кажется более компактным - мы сбрили некоторые «промежуточные» потери времени, оставив лишь ядро вычислений. Что наиболее важно, глядя на верхние горячие точки, мы действительно можем видеть, что умножение поменялось местами с вычитанием, и malloc / free потерял несколько позиций.
Я не думаю, что это можно оптимизировать гораздо больше с точки зрения чисто черного ящика. Если это те расчеты, я боюсь, что нет простого способа выполнить их быстрее, используя GMP mpf_class. На этом этапе вы должны либо:
- отбросить GMP и использовать другую библиотеку, с лучшей производительностью для случая фиксированного размера; Я подозреваю, что здесь есть что-то выиграть - даже просто избежать полного выделения средств и встраивания расчета - большая победа;
- начать применять некоторые алгоритмические оптимизации ; это обеспечит значительно более короткое время выполнения независимо от типа данных, который вы в конечном итоге решите использовать.
Примечания
- полный код (в разных его итерациях) можно найти по адресу https://bitbucket.org/mitalia/mandelbrot_gmp_test/
- все тесты выполнены на g ++ 7.3 с уровнем оптимизации -O3 на 64-битной Linux, работающей на моем i7-6700
- профилирование выполнено с использованием
perf record из linux-tools 4.15 с захватом стека вызовов; графики и таблицы, созданные с помощью KDAB Hotspot 1.1.0