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;
}

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

Чуть меньше чем 50%

Ага, а вторая половина уходит на вызов bm.process();. Пиши на асме или используй goto :)

А ещё, так как у тебя приращение дискретное, то целые числа-таки можно запилить, но не думаю что это прибавит прям 100500% перформанса, если вообще прибавит. То есть, для каждого шарика надо будет ещё, для начала, отдельно высчитать целочисленные значения границ и потом сравнивать не с общими границами, а с «собственными». Правда, при изменении скорости собственные границы надо будет пересчитывать.

Попробуй ещё компилятор нормальный взять :)

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

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

Круто, чё. А зачем там одно и то же 8 раз скопировано? Это для OpenMP?

anonymous
()

У меня так быстрее примерно на 15-20%:

#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)
  {
    const float curr_x = x[i];
    const float curr_y = y[i];

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

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

int main()
{
  BallsManager bm(15000);

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

  return 0;
}
anonymous
()
Ответ на: комментарий от Deleted

по знаку достаточно

signof(x-b)*signof(a-x)) - 0 считать за минус :)

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

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

Ну потому что а) надо чётное б) нужна степень двойки.

2 мало, 4 мало, 8 уже нормально.

Почему 4 мало - отпопа. Конечно это надо считать, но пока у тебя горячего кода меньше l1i - на это покласть. В целом если не знаешь насколько и нет возможности проверить/побенчить - бахай на максимальное вменяемое кол-во. Сделаешь больше, чем нужно - толку не даст, но и не повредит.

anonymous
()

А промежуточные вычисления нужны или достаточно конечного результата?

unC0Rr ★★★★★
()

15 млрд итераций

за 2 секунды

ловите наркомана

на gpu можно, да. /thread

anonymous
()

попробуй этот код, он в 32 раза быстрее работает. я гарантирую это.


template <typename F>
class Z1
{
  F f_;
  public:
    Z1(const F &f): f_(f) {}
    void operator()(int N) {
      f_((void *)f_, N, 1);
    }
};

template <typename F>
class Z
{
  public:
    Z1 <F> operator()(const F &f) {
      return Z1 <F> (f);
    }
};

template <typename F>
class ZZ
{
  public:
    int operator()(void *f, int n, int a) {
      if (n == 1) {
        return a;
      } else {
        return ((F *)f)((F *)f, n-1, a*n);
      }
    }
};

template <typename F>
int f(int x) {
  auto f1 = Z <F> (ZZ<F>());
  return f1(x);
}

int main()
{
  printf("%d\n", f <void (*) (void *, int, int) > (5));
}

anonymous
()

Использовать parallel_for и считать с фиксированной точкой.

invy ★★★★★
()

оптимизация 1:

#include <stdlib.h>
#include <vector>

struct Ball {
  float x;
  float y;
  float dir_x;
  float dir_y;
};

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

  size_t m_count;
  std::vector<Ball> balls;
};


BallsManager::BallsManager(size_t count):
	m_count(count), balls(count)
{
  for (size_t i = 0; i < m_count; ++i) {
    balls[i].x = (i % 200) + 5.0f;
    balls[i].dir_x = 1.0f;
    balls[i].y = (i % 200) + 5.0f;
    balls[i].dir_y = 1.0f;
  }
}


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 (Ball &ball : balls)
  {
    if (ball.x <= min_x || ball.x >= max_x)
       ball.dir_x *= -1;
    ball.x += ball.dir_x;

    if (ball.y <= min_y || ball.y >= max_y)
       ball.dir_y *= -1;
    ball.y += ball.dir_y;
  }
}
оптимизация 2:
#include <stdlib.h>
#include <vector>

struct Ball {
  int x;
  int y;
  int dir_x;
  int dir_y;
};

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

  size_t m_count;
  std::vector<Ball> balls;
};


BallsManager::BallsManager(size_t count):
	m_count(count), balls(count)
{
  for (size_t i = 0; i < m_count; ++i) {
    balls[i].x = ((i % 200) + 5) * 100;
    balls[i].dir_x = 100;
    balls[i].y = ((i % 200) + 5) * 100;
    balls[i].dir_y = 100;
  }
}


void BallsManager::process()
{
  static const int min_x = 0;
  static const int max_x = 64000;
  static const int min_y = 0;
  static const int max_y = 48000;

  for (Ball &ball : balls)
  {
    if (ball.x <= min_x || ball.x >= max_x)
       ball.dir_x *= -1;
    ball.x += ball.dir_x;

    if (ball.y <= min_y || ball.y >= max_y)
       ball.dir_y *= -1;
    ball.y += ball.dir_y;
  }
}
венда, MSVS, с опцией /O2
100 000 итераций
$ time opt2.exe
real    0m3.373s
user    0m0.015s
sys     0m0.046s

$ time opt1.exe
real    0m4.248s
user    0m0.031s
sys     0m0.015s

$ time orig.exe
real    0m8.663s
user    0m0.031s
sys     0m0.015s

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

Внушаить, насколько код на нормальном C++ стал компактнее и понятнее. Плюс, такое ощущение, что в BallsManager теперь m_count и не нужен, т.к. при необходимости можно использовать balls.size().

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

I changed the ints to floats (according to original request) set it to same number of balls and iterations as original

this code is 6 sec slower than original 31 sec vs 25 on my machine

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

Но до сих пор не выполнено основное требование, ускорить в минимум 16 раз :) Какая разница как красиво выглядит код если он не выполняет работу которую от него требовали?

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

а чё банального не хватает?

void BallsManager::processX()
{
  static const float min_x = 0.0f;
  static const float max_x = 640.0f;

  #pragma omp parallel for
  for (size_t i = 0; i < m_count; ++i)
  {
    const float curr_x = x[i];

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

void BallsManager::processY() {
  static const float min_y = 0.0f;
  static const float max_y = 480.0f;

  #pragma omp parallel for
  for (size_t i = 0; i < m_count; ++i) {
    const float curr_y = y[i];

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

  }
}

int main()
{
  BallsManager bm(15000);

  //-- need to speedup from here --
  const int itSize = 1000000;
  #pragma omp parallel for
  for (int iterations = 0; iterations < itSize; ++iterations) {
    bm.processX();
  }
  #pragma omp parallel for
  for (int iterations = 0; iterations < itSize; ++iterations) {
    bm.processY();
  }
  //-- to here --

  return 0;
}

g++ -O2 mod.cc -fopenmp -o mod

в 16 процессорной виртуалке, где то в 12 раз +)

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

Вы до сих пор не ответили на вопрос о том, кто дал вам такую задачу: преподаватель или работодатель. Если вы занимаетесь такими вещами на работе, то вот здесь уже дали правильный ответ :)

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

На GPU можно.

Вы уже попробовали и у вас получилось?

И еще: «Можно использовать GPU? Факт не тривиальный, мы же не знаем, что за задача, а GPU не везде есть. Еще и вопрос технологии встает».

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

Ещё можно Intel C++ Compiler попробовать. Он скорее всего выбросит весь код как не имеющий побочных эффектов.

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

Зависит наше понимание твоего отношения к нам.

Если это задача от работодателя, то ты используешь местную публику как бесплатную раб. силу. Более того, тебе лень выполнять поставленную на работе задачу (или ты недостаточно квалифицирован, что еще хуже).

Если же это по учебе — тебе помогут советом.

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

Смотрите на ето как упражнение для мозгов - Кто хочет пусть делает, а кто не хочет пусть не делает :)

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

как влияет знание о том кто дал этот код на поставленную задачу?

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

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

А можно нескромный вопрос

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

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

eao197 ★★★★★
()
Ответ на: комментарий от i-rinat

Если я правильно понимаю тому кому она бессмысленна - сюда даже и не зашел, а если и зашел то просто ушел из треда. Те же кто захотел небольшую умственную нагрузку стали пытаться решить задачу :)

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

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

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

Ясно, только те кто не осилил, не захотел, не интересно или вообше по какой либо причине попал на тред случайно могут легко его закрыть :)

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

Мне кажется что этот тред для вас себя исчерпал

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

Брехня.

$ time ./govno2 
1.833969sec
6.093817GB/s

real    0m1.835s
user    0m1.833s
sys     0m0.001s
$ time ./origin 
2.347596sec
4.760560GB/s

real    0m2.349s
user    0m2.346s
sys     0m0.001s

uint64_t count = 15000, i = 100000;

Этож на каком дерьме надо было бенчить, чтобы на 1.5к х 100к получить 9секунд.

anonymous
()

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

anonymous
()
Ответ на: комментарий от invy

Посмеялся.

Скорее всего всё намного прозаичней - умственно нагрузки нету по причине отсутствия того, что нужно нагружать.

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

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

упрощеный концепт (сильно упрощенный)

создаём по потоку на каждый core

каждому из них даём брут форсить свой участок индехсов (например первому от 1 до 1000, второму от 1001 до 2000 и так далее) каждый из них работает с SIMD. получается каждая итерация обрабатывает по 4 шара.

не нужно никаких локов так как память не пересекается.

так же по томуже принципу часть шаров сливается в GPU (люди здесь правильно говорили),

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

в принципе можно сделать всё только на GPU, но если у меня есть допустим 8 cores на cpu, то зачем им простаивать, пусть тоже работают.

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

Но гарантировано будет быстрее больше чем в 16 раз.

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

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

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

Люди просто привыкли подгонять задачу под решение

Нет, люди привыкли подгонять под готовое, не ими сделанное решение.

делать красивый ооп код и так далее

Никто из них не может в красивый ооп-код. Он может делать так, как его сказали делать. А т.к. нихрена не может и его мнение ничего не стоит - пытается задачи/решения и прочее, которые не подходят под готовое говно, под то, как его научили и прочее называть говном.

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

И прочее.

Никому не нужен красивый многоуровневый код если он не решает поставленую задачу.

Никто не ставит вменяемых задач. Их некому ставить - везде одни ламерки.

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

Поэтому и условия решения к задачам не ставят - единственное условие чтобы кое-как работало.

А т.к. задачи, которые решает ламерок задачами не являются, а являются вариациями на тему решенных задач - т.е. скриптуха, аля взял готовые данные готового формата загнал в готовое говно, после чего обработал с помощью готового говна подёргав рычаги.

Т.е. это не типичный птушник. Ламерок - это типичная секретарша.

anonymous
()
Ответ на: комментарий от uuwaan

А как выглядит на asm код для обновления структуры целиком а не по элементам?

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

Какая спесь!

Ты сперва роди код, который был бы заметно быстрее чем в исходном сообщении ТС, а потом и про спесь порассуждаешь

Вполне забавную задачку он предложил

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

Код который решает поставленую задачу

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

А ты не выдумывай правил, которых нет. В «задаче» об этом ни слова. Если хочешь наложить на себя дополнительные ограничения — дело твоё.

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