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

Я разговаривал не с тобой. Почему тебя это так беспокоит?

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

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

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

Хотите дам интересную вещь почитать?

Ого, друзья, я открыл для себя интересную вещь. Оказывается, если у вас современный 8-ядерный проц с набором AVX-512, то это дело вполне реально ускорить в ... 128 раз! На 8-ядерном же старье с поддержкой AVX — в 64 разаза.

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

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

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

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

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

i5-760

дома лучше (q9550):

igor:...projects/test/balls% time ./opt
./opt  3,75s user 0,00s system 99% cpu 3,754 total
igor:...projects/test/balls% time ./orig 
./orig  4,28s user 0,00s system 99% cpu 4,286 total

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

Как можно узнать сколько пайплайнов у моего процессора?

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

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

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

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

О боже - уйди отсюда, ибо совсем нулёвая ламерюга.

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

которые могут работать и читать с диска или что-то ещё медленное будет мало, т.к. есть конвейер, которому поплохеет с твоих потоков.

Да. Как я сразу этого не увидел.

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

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

Оказывается, если у вас современный 8-ядерный проц с набором AVX-512, то это дело вполне реально ускорить в ... 128 раз! На 8-ядерном же старье с поддержкой AVX — в 64 разаза.

Не взлетит, на деле упрётся в кэши и i/o.
https://channel9.msdn.com/Events/Build/2013/4-329

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

Ждём когда амд в последних потугах выдаст матплаты с gddr для apu.

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

Зачем ламерки кукарекают на те темы, в которых ничего не понимают? Иди дальше улицу мети - там ты специалист.

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

В целом недобитая ламерюга обоссанна, но пытается что-то мне там кукарекать. Как это мило. Обделалась и пытается съехать с темы.

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

Но давай я помогу погрузится тебе ещё глубже в дерьмо, прям чтоб 100% не всплыл.

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

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

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

Кста, удивительно, но никак. Предсказатели ветвлений хорошие стали.

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

Анон что-то там пропищал со стороны параши. Ему ещё перед одноклассниками свежепоставленным арчиком понтоваться.

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

Не взлетит, на деле упрётся в кэши и i/o.
https://channel9.msdn.com/Events/Build/2013/4-329

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

Интересно, а существуют ли сборки линуксов и всяких гнумов с использованием интеловского или «какого-нибудь другого» компилятора? Или там защита вшивается от проприетарщины?

Ведь навряд ли в стандартных сборках используются все возможности современного процессора и gcc, вроде бы, автоматом не умеет векторизовать данные и применять к ним инструкции AVX или даже AVX-512.

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

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

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

Короче, у меня получилось для int'ов и без ветвлений — 5.88 секунды на 8 ядрах и 13.73 секунды на одном ядре.

Для float'ов и с ветвлениями — 4.99 :) секунды на 8 ядрах и 28.49 секунды на одном.

Это для 15000 * 1млн итераций. Это много или мало?

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

Не, я походу вас обманул. Из того, что выше, правда — только 13.73 и 28.49 на одно ядро. Но 11 секунд на 8 ядер «вроде точно» есть :)

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

SIMD?

Ну да, типа того: gcc -Ofast -march=native, данные — как AOS. Но вот почему-то когда использую OpenMP, то результат отличается от последовательного. Вероятно надо делить между ядрами не 1000000 циклов, а 15000 шаров. Надо попробовать вывернуть циклы.

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

Можно увидеть код?

Код. Сильно только не пинайте, я не настоящий сварщик. В общем-то тоже самое, почти:

#include <stdio.h>
#include <time.h>
#include <omp.h>

typedef struct {
    float  x;
    float  y;
    float  dx;
    float  dy;
} ball_t;

void test_arr() {

    float  min_x = 10;
    float  max_x = 20;
    float  min_y = 30;
    float  max_y = 42;
    
    const int  balls_count = 15000;
    ball_t  b[balls_count];

    
    for (int i=0; i<balls_count; i++) {
        b[i].x = min_x;
        b[i].y = min_y;
        
        b[i].dx = 1;
        b[i].dy = 1;
    }
    
    clock_t t = clock();
    
    #pragma omp parallel for collapse(2) 
    for (int iters=0; iters<1000000; iters++) {
        
        for (int i=0; i<balls_count; i++) {
            if (b[i].x <= min_x || b[i].x >= max_x)
                b[i].dx *= -1;
            if (b[i].y <= min_y || b[i].y >= max_y)
                b[i].dy *= -1;
            
            b[i].x += b[i].dx;
            b[i].y += b[i].dy;
        }
        
    }
    
    printf("Time: %f sec.\n", (float)(clock() - t) / CLOCKS_PER_SEC);
    
    int sx = 0, sy = 0;
    
    for (int i=0; i<balls_count; i++) {
        sx += b[i].x;
        sy += b[i].y;
    }

    printf("SX: %i\t SY: %i\n", sx, sy);
}

И в main() потом однократный вызов. Для целых — использовал отдельные массивы для x, y, dx, dy, а от ветвления избавлялся так:

dx[i] += -2 * ((x[i] - min_x - half_range_x) / half_range_x);
x[i] += dx[i];

anonymous
()

Вывернул циклы и поставил collapse(1). «793% cpu 9.160 total». Результат сходится с последовательным.

Если оставить collapse(2), то результат «почти» сходится, но время сокращается драматикалли — до 1.5 секунд! Чего-то я тут недопонимаю :(

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

ето процесс на avx, 8 шаров за проход

	__m256 min_x = _mm256_set1_ps(0.0f);
	__m256 min_y = _mm256_set1_ps(0.0f);
	__m256 max_x = _mm256_set1_ps(640.0f);
	__m256 max_y = _mm256_set1_ps(480.0f);
	__m256 reverse_dir = _mm256_set1_ps(-1.0f);
	__m256 normal_dir = _mm256_set1_ps(1.0f);
		
	for (int i = 0; i < m_count; i += 8)
	{		
		__m256  curr_value = _mm256_load_ps(x + i);
		__m256  curr_dir = _mm256_load_ps(dir_x + i);
	
		__m256 too_small_x = _mm256_cmp_ps(curr_value, min_x, _CMP_LE_OQ);
		__m256 too_big_x = _mm256_cmp_ps(curr_value, max_x, _CMP_GE_OQ);

		__m256 change_dir = _mm256_or_ps(too_small_x, too_big_x);

		__m256 new_dir_factor = _mm256_blendv_ps(normal_dir, reverse_dir, change_dir);
		__m256 new_dir = _mm256_mul_ps(curr_dir, new_dir_factor);

		curr_value = _mm256_add_ps(curr_value, new_dir);
		
		_mm256_store_ps(x + i, curr_value);		
		_mm256_store_ps(dir_x + i, new_dir);
	}

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

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

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

и шо ты там в гнуме ускорять будешь? дибилобас?

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

чуть меньше операций

Ну, там эти операции не очень заметны на фоне доступа к памяти. Я сделал еще подход к снаряду ( http://pastebin.com/ydTY26kj ), больше чем в 3-4 раза (на разных железках) ускорить не получилось

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

Я никогда не работал с опенмп, поетому не могу сказать, я не знаю как именно он разбивает на секции, делает локи или как Попробуй explicitly created threads.

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

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

Есть у меня сильное подозрение, что это не будет иметь никакого отношения к C++ для платформ ARM, MIPS, SPARC и пр. не-x86-тым архитектурам. Даже не смотря на наличие компилятора для этих платформ.

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

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

Разве заточеность под платформу делает код компилируемый согласно стандарту c++ и компилируемый обшепринятыме компиляторами этого языка не c++?

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

Простите, не распарсил то, что вы написали.

Ваша «задача» оказалась задачей под одну конкретную аппаратную платформу. Никаких языковых особенностей C++ для ее решения не требуется, задача будет решаться в точности так же на любом другом языке, будь то C, D, Pascal, Fortran или, прости хоcпади, Rust.

Ну и, как следствие, ваш C++ный код автоматически перестанет быть компилируемым C++ными кодом на любой платформе, где этих расширений и системно-зависимых функций/типов нет.

Собственно, привязки C++ного кода к специфическим для платформам вещам — это обычное дело. Но, т.к. C++ все-таки платформенно-независимый язык, то хочется, чтобы привязка задачи к x86 была обозначена гораздо четче.

eao197 ★★★★★
()
Ответ на: комментарий от eao197
BallManager::progress()
{
#ifdef _ARM_NEON_
...
#else
....
#endif
}

Так лучше?

Ну и, как следствие, ваш C++ный код автоматически перестанет быть компилируемым C++ными кодом на любой платформе, где этих расширений и системно-зависимых функций/типов нет.

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

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

Так лучше?

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

А если серьёзно то мы никогда не пишем

Отучаемся говорить за всех.

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

1. идёшь в ютуб.

2. в строку поиска ютуба Bjarne Stroustrup cppcon 2015

3. смотришь слушаешь и листаешь презенташки.

4. понимаешь.

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