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

__m256 min_x = _mm256_set1_ps(0.0f);

Отлично. 7.57 секунды на одно ядро. Но распараллеливается с OpenMP чё-то вообще никак. В конце-то концов, где мои 0.5 секунды, явасспрашиваю?

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

Make a thread pool with number of threads that equal to number of your cores.

Each such thread should perform 1000000 iterations over a section of the arrays (make sure the section size will be a multiply of 8) For example first thread goes from indexes 0 to 799, second from 800 to 1499 and etc..

then test it again.

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

Я готов вам поверит на слово. Сколько у вас получилось с 8 тредами?

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

Точнее

I'm gonna believe what you say. How much performance boost do you have with 8 threads instead of one?

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

Ну ты не шлангуй. Считай, что начальные значения считал из stdin, а результирующие значения высрал в stdout.

Кстати, ещё один способ шлангования придумал; уже для твоей задачи.

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

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

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

Разница такая, что у тебя в тегах стоит С++ а на деле код - С с классами.

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

Для начала:

class BallsManager
{
    const std::size_t m_count;
    std::vector<float> m_buffer;
    
    const std::vector<float>::iterator x;
    const std::vector<float>::iterator dir_x;
    const std::vector<float>::iterator y;
    const std::vector<float>::iterator dir_y;

public:
    BallsManager(std::size_t count);
    
    void process();
};

BallsManager::BallsManager(std::size_t count)
  : m_count(count),
    m_buffer(count * 4),
    x(std::begin(m_buffer)),
    dir_x(x + count),
    y(dir_x + count),
    dir_y(y + count)
{
    struct init_seq
    {
        std::size_t i { 0 };
        float operator()() { return static_cast<float>(i++ % 200) + 5.0f; }
    };
    std::generate_n(x, count, init_seq());
    std::fill_n(dir_x, count, 1.0f);
    std::generate_n(y, count, init_seq());
    std::fill_n(dir_y, count, 1.0f);
}

void BallsManager::process()
{
    constexpr float min_x = 0.0f;
    constexpr float max_x = 640.0f;
    constexpr float min_y = 0.0f;
    constexpr 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;
    }
}
По производительности на нормальном компиляторе ничем не отличается. Дальше:
template <int Min, int Max>
struct BoundsHelper {
    constexpr static float center { static_cast<float>(Max + Min) / 2.0f };
    constexpr static float half_size { static_cast<float>(Max - Min) / 2.0f };
}

void BallsManager::process()
{
    typedef BoundsHelper<0, 640> bx;
    typedef BoundsHelper<0, 480> by;
  
    for (std::size_t i = 0; i < m_count; ++i) {
        dir_x[i] *= std::copysign(1.0f, bx::half_size - std::abs(x[i] - bx::center));
        x[i] += dir_x[i];
        dir_y[i] *= std::copysign(1.0f, by::half_size - std::abs(y[i] - by::center));
        y[i] += dir_y[i];
    }
}
Это примерно в 2 раза быстрее. В пределах кроссплатформенного варианта дальше ты вряд ли уйдешь без распараллеливания и использования сторонних библиотек. Дальше уже в зависимости от платформы и компилятора можешь извращаться как хочешь, но это будет уже к С++ никак не относится.

anonymous
()
$ gcc -O -march=native -fopenmp test.c && time ./a.out 
Time: 16.474621 sec / 8 threads = 2.059328 sec/th.
./a.out  16.48s user 0.00s system 793% cpu 2.076 total

Интринсики AVX, OpenMP и т.п. Наверное это предел для моей системы. Конечно, это всё не серьёзно, но было интересно.

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

Не предел, есть ещё процессоры в графической карте

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

You fucking kidding me https://goo.gl/N4BHvi vs https://goo.gl/mbOHKM

Я не просил переписать это на красивый кросс абсолютно кроссплатформеный c++ использюший возможности новых стандартов.

Я просил ускорить этот код в 16 раз - не в 2, не в 3 не 4, а в 16. Вместо этого мне начали посылать линки на то как писать правильный код, начали присылать код который даже близко не подходит к требованиям задачки - НО намного дольше компилируется и намного больше ест памяти.

Короче всё, модераторы. удалите пожалуйста этот тред.

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

Я просил ускорить этот код в 16 раз - не в 2, не в 3 не 4, а в 16.

Я просил свой остров на Мальдивах, но меня почему то послали на х

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

Разница такая, что у тебя в тегах стоит С++ а на деле код - С с классами.

Я так понял, что constexpr и std::vector резко сделал из вашего «С с классами» настоящий С++?

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

Я просил свой остров на Мальдивах, но меня почему то послали на х

Наверное ваш С++ был не настоящий, а обычный «С с классами».

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

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

Проверенно на линуксе, маке и виндоус. Corei7. Собрался с clang, GCC и msvc.

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