LINUX.ORG.RU

Kак ускорить исполнение данного кода?

 ,


2

5

Есть код, очень - очень медленный, нужно ускорить ну пару хотя-бы раз в 16. конструктор и деструктор не учитываются в бенчмарке Какие есть идеи?

#include <stdlib.h>

struct BallsManager
{
  BallsManager(size_t count);
  ~BallsManager();
  void process();

  float * x;
  float * y;
  float * dir_x;
  float * dir_y;

  size_t m_count;
  float * m_buffer;
};


BallsManager::BallsManager(size_t count):
	m_count(count)
{
  m_buffer = new float[count * 4] ;
  x = m_buffer;
  dir_x = (x + count);
  y = (dir_x + count);
  dir_y = (y + m_count);

  for (size_t i = 0; i < m_count; ++i)
    x[i] = (i % 200) + 5.0f;

  for (size_t i = 0; i < m_count; ++i)
    dir_x[i] = 1.0f;

  for (size_t i = 0; i < m_count; ++i)
    y[i] = (i % 200) + 5.0f;

  for (size_t i = 0; i < m_count; ++i)
    dir_y[i] = 1.0f;
}

BallsManager::~BallsManager()
{
  delete[] m_buffer;
}


void BallsManager::process()
{
  static const float min_x = 0.0f;
  static const float max_x = 640.0f;
  static const float min_y = 0.0f;
  static const float max_y = 480.0f;

  for (size_t i = 0; i < m_count; ++i)
  {
    float curr_x = x[i];
    float curr_y = y[i];
    float curr_dir_x = dir_x[i];
    float curr_dir_y = dir_y[i];

    if (curr_x <= min_x || curr_x >= max_x)
    {
       curr_dir_x = -curr_dir_x;
       dir_x[i] = curr_dir_x;
    }
    x[i] = curr_x + curr_dir_x;

    if (curr_y <= min_y || curr_y >= max_y)
    {
       curr_dir_y = -curr_dir_y;
       dir_y[i] = curr_dir_y;
    }
    y[i] = curr_y + curr_dir_y;
  }
}

int main()
{
  BallsManager bm(15000);

  //-- need to speedup from here --
  for (int iterations = 0; iterations < 1000000; ++iterations)
    bm.process();
  //-- to here --

  return 0;
}

Конструктор:

for (size_t i = 0; i < m_count; ++i) {
x = (i % 200) + 5.0f;
dir_x = 1.0f;
y = (i % 200) + 5.0f;


dir_y = 1.0f;
}
Метод распаралелить.

ymuv ★★★★
()
Последнее исправление: ymuv (всего исправлений: 3)
Ответ на: комментарий от ymuv

Thanx

Я просил не оптимизировать конструктор :)

а распараллелить это хорошо. но только даст буст перформансу только в несколько раз (на количество доступных cores, обычно это 4 или 8) чтоб еще сделать для того чтоб ускорить как минимум в 16 раз

CyberK
() автор топика

Для начала улучшить локальность данных, я считаю. Координаты и направления у тебя лежат в 4х смежных кусках памяти. В конструкторе ты работаешь с ними адекватно их расположению, а в process() у тебя постянные cache misses, потому что ты сначала схватил в начале буфера, потом прыгаешь в конец, потом в середину. x,y,dir_x, dir_y – внутрь структуры, заодно в конструкторе вместо 4х циклов можно сделать один.

uuwaan ★★
()

Навскидку: у вас очень неудачное расположение данных в памяти. Вам нужны x(i) и dir_x(i), но они отстоят друг от друга на count элементов. Аналогично с y(i) и dir_y(i). Плюс к тому вы в одном цикле делаете обработку и x и y, что дает еще больше промахов мимо кэша.

Можно было бы попробовать делать два массива структур { float v, dir; } и обрабатывать их в двух независимых циклах.

PS. Откуда такое задание: от преподавателя или от работодателя?

eao197 ★★★★★
()
Последнее исправление: eao197 (всего исправлений: 1)
Ответ на: комментарий от uuwaan

если я не ошибаюсь, у моего core i7 размер cache L1 32kb, каждый лайн по 64 байта. в каждом лайне находится по 16 флоатов. и каждый лайн не зависит от другого. так что там ето не должно повлиять. по крайней мере в профайлере ничего не поменялось. в добавок почти весь буффер помещается в L2, так что не особенно должно влиять.

но спасибо, еще идеи?

CyberK
() автор топика
Ответ на: комментарий от eao197

Вам нужны x(i) и dir_x(i), но они отстоят друг от друга на count элементов.

Это не проблема. Напротив, для векторизации его раскладка — более удобная.

Manhunt ★★★★★
()
Ответ на: комментарий от CyberK

Что это за условие и зачем оно, если у тебя все равно все числа кратны целым и нет ни одного деления?

CatsCantFly
()
Ответ на: комментарий от CyberK

А числа с фиксированной точкой не подойдут?

annulen ★★★★★
()
Ответ на: комментарий от CyberK

Второе, что приходит на ум, это двойная индексация массивов в цикле. Поскольку компилятор может быть не уверен, что в теле цикла i не меняется, то dir в двух местах породит две пачки инструкций по вычислению адреса. Так что, предполагая, что у нас теперь структура, а не 4 массива, делаем:

struct ball *b = balls[i];
и дальше работаем через этот указатель.

Далее можно почитать про strict aliasing. Сутьв том, что компилятор не может проверить, что *b – единственный рабочий указатель. Всегда предполагается, что помимо *b может быть ещё один указатель, через который область, на которую *b сылается, может быть изменена. Это приводит к тому, что каждый раз встречая чтение b->x, компилятор генерит код, заново читающий эту область памяти на случай, если её поменяли. Аналогично для записи: изменения сразу коммитятся в оперативную память, вдруг кто-то другой захочет прочитать. Но можно объявить указатель через restricted, этим объявлением мы берём на себя обязательство, что наш указатель *b – единственный, через который мы с памятью работаем. Исчезают дополнительные проверки, код записи данных по указателю может быть собран в одну кучку, т.е. вся структура обновится целиком, а не отдельными элементами.

uuwaan ★★
()

Ты хочешь запилить физику шаров. Дело в том, что скорее всего:

1) считатать 15000 process не нужно. Нужно выделить шары, входящие в определенную область интересов и уже в ней решать эту задачу на небольшом количестве шаров.

2) нужно использовать GPU. Он на раз-два справится с этой задачей, только хорошо подумай сначала над 1 пунктом. Я почему-то почти уверен, что без GPU можно обойтись

Burns
()
Ответ на: комментарий от CyberK

по крайней мере в профайлере ничего не поменялось.

cachegrind юзал?

annulen ★★★★★
()

Здесь ктото давал «причесаный» код, а потом его удалил. Причесаный код работает на 10 секунд дольше, 25 против 35 и занимает на 8 кб больше рама

CyberK
() автор топика
Ответ на: комментарий от CyberK

И профилировщик вставляет в твой код свой, т.н. инструментальный, который портит картину в данном случае. Кэш-миссы им не словишь.

uuwaan ★★
()

А смысл в том, чтобы код остался точно таким же, или его можно переписать в event-driven стиле? Просто вместо проверки выхода за границы будет предсказание момента, когда это произойдёт, соответственно внутренний цикл будет ожидать следующее событие и выполнять его, а не повторять одинаковые проверки снова и снова, это должно быть значительно быстрее.

xaizek ★★★★★
()
Ответ на: комментарий от xaizek

Можно переписать, Можеш пожалуйста написать полный пример, а то я себе смутно представляю как это ускорит

CyberK
() автор топика
Ответ на: комментарий от CyberK

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

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

Ну и если ты все-таки непреклонен к своему решению написать свой вариант с GPU, то скажу, что при работе с GPU основная ресурсоемкость - копирование данных из RAM в GRAM, в оба направления. Так что если вычислительных операций совсем мало, а данных много, то туда гонять нет смысла

Burns
()

профайлер показывает что очен' много времени он сидит на

if (curr_x <= min_x || curr_x >= max_x)
и
if (curr_y <= min_y || curr_y >= max_y)
Чуть меньше чем 50% от обшего времени работы кода

CyberK
() автор топика
Ответ на: комментарий от CyberK

Это невозможно, ты сам запретил:

Я просил не оптимизировать конструктор :)

А там не только конструктор, там всё нужно переписывать.

asaw ★★★★★
()
Ответ на: комментарий от asaw

Вам лично можно переписать всё, с любыми стандарными контейнерами и вкусняшками :) Уж очень хочется посмотреть на правильный c++ code

CyberK
() автор топика
Ответ на: комментарий от CyberK

Вот возьми букварь и перепиши с контейнерами. Потом замени std::for_each() на параллельный отсюда: https://parallelstl.codeplex.com/ и будет тебе и распараллеливание, и ускорение. А все твои кривляния с указателями ничего кроме улыбки не вызывают. Просто раскладываешь грабли чтобы по ним гордо ходить. Никакого смысла, даже для микроулучшений производительности (что само по себе лютый антипаттерн - начинать нужно с алгоритма, а не с ловли блох) в этом нет.

asaw ★★★★★
()
Ответ на: Thanx от CyberK

но только даст буст перформансу только в несколько раз (на количество доступных cores, обычно это 4 или 8)

Не даст, там будет меньше прирост по идее. Если вообще будет.

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от CyberK

Полный пример писать сейчас некогда, можно глянуть на описание тут (там ещё и для столкновений между шарами, но то можно игнорировать; все столкновения в лоб реализовывать слишком медленно, а на событиях оно шустро работает). Надо взять std::priority_queue вместо MinPQ и переписать кусок из CollisionSystem (там Java, кстати).

xaizek ★★★★★
()
Последнее исправление: xaizek (всего исправлений: 1)
Ответ на: комментарий от asaw

Так если бы я знал как, я бы написал, можно мне всё таки как исключение сделать пример? Это же мало кода, и логика простая.. я этот код написал минуты за 4.

CyberK
() автор топика

чиста на интуицию. 6 c четвертью процента от исходного мало возможно.

итераторы сила.


void BallsManager::process(){
        static const float min_x = 0.0f;
        static const float max_x = 640.0f;
        static const float min_y = 0.0f;
        static const float max_y = 480.0f;
        float *xx=&x,*yy=&y,*dx=&dir_x,*dy=&dir_y;

        for(size_t i = 0; i < m_count; ++i){
                if (*xx<= min_x || *xx >= max_x){
                        *dx*=-1.0;
                }
                if (*yy <= min_y || *yy >= max_y){
                        *dy*=-1.0;
                }
                *(xx++)+=*(dx++);
                *(yy++)+=*(dy++);
        }
}

qulinxao ★★☆
()
Ответ на: комментарий от xaizek

Так там же всё равно будут те самые проверки на колизию с границей, только поверх етого будет еще много чего намазано. Я в упор не понимаю почему ето будет быстрее

CyberK
() автор топика
Ответ на: комментарий от CyberK

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

qulinxao ★★☆
()
Ответ на: комментарий от CyberK

:)

void BallsManager::process(){
        static const float min_x = 0.0f;
        static const float max_x = 640.0f;
        static const float min_y = 0.0f;
        static const float max_y = 480.0f;
        float *xx=x,*yy=y,*dx=dir_x,*dy=dir_y;

        for(size_t i = 0; i < m_count; ++i){
                if (*xx<= min_x || *xx >= max_x){
                        *dx*=-1.0;
                }
                if (*yy <= min_y || *yy >= max_y){
                        *dy*=-1.0;
                }
                *(xx++)+=*(dx++);
                *(yy++)+=*(dy++);
        }
}

так?

qulinxao ★★☆
()
Ответ на: комментарий от qulinxao

етот пример медленей чем мой на 6 секунд

CyberK
() автор топика
Ответ на: комментарий от CyberK

если вернуть смену знака вместо умножения?

и добавить ветки else т.е в обоих случаях скорипровать модификацию

т.е. уменьшить число переходов.

ну и 3

затем скопировать второе - т.е копипастить для уменьшении доли прижков в общем коде :

void BallsManager::process(){
        static const float min_x = 0.0f;
        static const float max_x = 640.0f;
        static const float min_y = 0.0f;
        static const float max_y = 480.0f;
        float *xx=x,*yy=y,*dx=dir_x,*dy=dir_y;

        for(size_t i = 0; i < m_count; ++i){
                if (*xx<= min_x || *xx >= max_x){
                        *dx*=-*dx;
                        *(xx++)+=*(dx++);
                        if (*yy <= min_y || *yy >= max_y){
                                *dy*=-*dy;
                                *(yy++)+=*(dy++);
                                continue;   
                        }else{
                                *(yy++)+=*(dy++);
                                continue; 
                        }
                 }else{
                        *(xx++)+=*(dx++);
                        if (*yy <= min_y || *yy >= max_y){
                                *dy*=-*dy;
                                *(yy++)+=*(dy++);
                                continue;
                        }else{
                                *(yy++)+=*(dy++);
                                continue;
                        }
                }
}

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

pps. у float sign bit такшта достаточно его xor 1 :)

сколько ещё секуднд добавилось?

qulinxao ★★☆
()
Ответ на: комментарий от CyberK

Да ты охренел. Тут люди потратили своё время, некоторые ещё пердолятся с профайлерами, а тебе «больше не интересно»

Chaser_Andrey ★★★★★
()
Последнее исправление: Chaser_Andrey (всего исправлений: 1)

хотя-бы раз в 16

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

prefetch
()
Ответ на: комментарий от CyberK

Ах ты подлец.

На - мне лень что-то писать и разбираться. Вроде работает - идея должны быть понятна.

http://pastebin.com/uSqmH032

::process((float_v4_t *)x, (float_v4_t *)dir_x, (float_v4_t *)y, (float_v4_t *)dir_y, m_count);

Должно быть в 4раза быстрее. Ну там выпили свои 15000 и поставить нормальное число.

anonymous
()

Branchless вариант. У меня получилось почти 30% выигрыша (мог напутать со знаками, не проверял). Ну, наверное с OpenMP+SSE можно в несколько раз ускорить

void BallsManager::process()
{
  static const float min_x = 0.0f;
  static const float max_x = 640.0f;
  static const float min_y = 0.0f;
  static const float max_y = 480.0f;

  for (size_t i = 0; i < m_count; ++i)
  {
    float curr_x = x[i];
    float curr_y = y[i];
    float curr_dir_x = dir_x[i];
    float curr_dir_y = dir_y[i];

    curr_dir_x = copysignf(curr_dir_x, fabs(curr_x - ((min_x + max_x) / 2)) - ((max_x - min_x) / 2));
    dir_x[i] = curr_dir_x;

    x[i] = curr_x + curr_dir_x;

    curr_dir_y = copysignf(curr_dir_y, fabs(curr_y - ((min_y + max_y) / 2)) - ((max_y - min_y) / 2));
    dir_y[i] = curr_dir_y;

    y[i] = curr_y + curr_dir_y;
  }
}
Deleted
()
Ответ на: комментарий от prefetch

Не знаю, как там с префетчем, но меня больше смущает, что там идет модификация векторов x-ов и y-ков. Т.к. размер кэша не резиновый, то при выкачивании из ОП очередных порций x(i),dir_x(i),y(i),dir_y(i), нужно выталкивать модифицированные старые значения. Имхо, если бы x и dir_x (а так же y и dir_y) лежали рядышком, возможно, картинка на апдейтах была бы другая. Особенно если сначала обрабатывать x/dir_x, а затем, вторым циклом, y/dir_y.

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

eao197 ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.