C ++ готовит набор Mandlebrot, плохая производительность

Question

C ++ готовит набор Mandlebrot, плохая производительность

Я не уверен, есть ли фактическое увеличение производительности или мой компьютер просто старый и медленный, но я все равно спрошу.

Поэтому я попытался создать программу для построения множества Мандельброта с использованием библиотеки Каира.

Цикл, который рисует пиксели, выглядит следующим образом:

vector<point_t*>::iterator it;
for(unsigned int i = 0; i < iterations; i++){
it = points->begin();
//cout << points->size() << endl;
double r,g,b;
r = (double)i+1 / (double)iterations;
g = 0;
b = 0;
while(it != points->end()){
point_t *p = *it;
p->Z = (p->Z * p->Z) + p->C;
if(abs(p->Z) > 2.0){
cairo_set_source_rgba(cr, r, g, b, 1);
cairo_rectangle (cr, p->x, p->y, 1, 1);
cairo_fill (cr);
it = points->erase(it);
} else {
it++;
}
}
}

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

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

Может ли кто-нибудь определить какие-либо проблемы с производительностью в цикле? или это так хорошо, как это получается?

Заранее спасибо 🙂

РЕШЕНИЕ

Очень хорошие ответы, спасибо 🙂 — у меня получился некий гибрид ответов. Думая о том, что было предложено, я понял, что вычисление каждой точки, помещение их в вектор и затем извлечение их — это огромная трата процессорного времени и памяти. Таким образом, вместо этого, программа теперь просто вычисляет значение Z каждой точки без использования point_t или вектора. Теперь он работает намного быстрее!

2

c++cairo performance

Решение

Другие решения

Z_N Расхождение расхождений — это то, что делает алгоритм медленным (конечно, в зависимости от области, над которой вы работаете). Для сравнения, рисование пикселей — это просто фоновый шум.

Ваша петля имеет недостатки, потому что это делает Z_N вычисления медленные.

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

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

Предполагая ваш points массив содержит только значения C (в основном вам не нужна вся эта векторная ерунда, но это также не повредит производительности), вы можете сделать что-то подобное:

for(vector<point_t>::iterator it=points->begin(); it!=points->end(); ++it)
{
point_t Z = 0;
point_t C = *it;
for(unsigned int i = 0; i < iterations; i++) // <-- this is the CPU burner
{
Z = Z * Z + C;
if(abs(Z) > 2.0) break;
}
cairo_set_source_rgba(cr, (double)i+1 / (double)iterations, g, b, 1);
cairo_rectangle (cr, p->x, p->y, 1, 1);
cairo_fill (cr);
}

Попробуйте выполнить это с и без каира, и вы не увидите заметной разницы во времени выполнения (если только вы не смотрите на пустое место сета).

Теперь, если вы хотите пойти быстрее, попробуйте разбить вычисление Z = Z * Z + C на реальные и мнимые части и оптимизировать его. Вы можете даже использовать mmx или что-то еще для параллельных вычислений.

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

Это может показаться не столь очевидным, поскольку каждое подизображение будет иметь разное время вычисления (черные области вычисляются очень медленно, а белые области вычисляются практически мгновенно).
Один из способов сделать это — разделить область на большое количество прямоугольников, и все рабочие потоки выбирают случайный прямоугольник из общего пула, пока все прямоугольники не будут обработаны.
Эта простая схема балансировки нагрузки, которая гарантирует, что ни одно ядро ЦП не останется бездействующим, пока его собеседники заняты в других частях экрана.

2

Первым шагом к оптимизации производительности является выяснение того, что происходит медленно. В вашем коде смешаны три задачи: итерация для расчета того, уходит ли точка, манипулирование вектором точек для проверки и построение точки.

Разделите эти три операции и измерьте их вклад. Вы можете оптимизировать расчет эвакуации, распараллеливая его с помощью операций simd. Вы можете оптимизировать векторные операции, не стирая из вектора, если вы хотите удалить его, а добавляя его в другой вектор, если вы хотите сохранить его (так как стирание — это O (N) и добавление O (1)) и улучшать локальность, имея вектор точек, а не указатели на точки, и если построение графика медленное, тогда используйте закадровое растровое изображение и задайте точки, манипулируя резервной памятью, а не используя функции Каира.

(Я собирался опубликовать это, но @Werner Henze уже высказал то же самое в комментарии, отсюда и вики сообщества)

1

Источник

Accepted Answer

редактировать: Я думаю, что предложение в ответе Курои Неко также является очень Хорошая идея, если вы не заботитесь о «инкрементных» вычислениях, но имеете фиксированное количество итераций.

Вы должны использовать vector<point_t> вместо vector<point_t*>,

vector<point_t*> это список указателей на point_t, Каждая точка хранится в некотором случайном месте в памяти. Если вы перебираете точки, шаблон, в котором осуществляется доступ к памяти, выглядит совершенно случайным. Вы получите много промахов кеша.

На противоположной vector<point_t> использования непрерывный память для хранения очков. Таким образом, следующая точка сохраняется непосредственно после текущей точки. Это позволяет эффективно кэшировать.
Вы не должны звонить erase(it); в вашем внутреннем цикле.

Каждый звонок erase должен переместить все элементы после того, который вы удалите. Это имеет O (N) времени выполнения. Например, вы можете добавить флаг point_t чтобы указать, что это не должно быть обработано больше. Может быть даже быстрее удалить все «неактивные» точки после каждой итерации.
Вероятно, не очень хорошая идея рисовать отдельные пиксели, используя cairo_rectangle, Я бы посоветовал вам создать изображение и сохранить цвет для каждого пикселя. Затем нарисуйте все изображение одним вызовом.

Ваш код может выглядеть так:

for(unsigned int i = 0; i < iterations; i++){
double r,g,b;
r = (double)i+1 / (double)iterations;
g = 0;
b = 0;
for(vector<point_t>::iterator it=points->begin(); it!=points->end(); ++it) {
point_t& p = *it;
if(!p.active) {
continue;
}
p.Z = (p.Z * p.Z) + p.C;
if(abs(p.Z) > 2.0) {
cairo_set_source_rgba(cr, r, g, b, 1);
cairo_rectangle (cr, p.x, p.y, 1, 1);
cairo_fill (cr);
p.active = false;
}
}
// perhaps remove all points where p.active = false
}

Если вы не можете изменить point_tВы можете использовать дополнительный vector<char> хранить, если точка стала «неактивной».

4