2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Зловещие циклы
Сообщение02.04.2020, 16:30 
Добрый день уважаемые участники. Долгое время пытался написать одну программу, и наконец, как это обычно бывает - она заработала, преподнеся ряд сюрпризов. В первую очередь, это относится к циклу:

Используется синтаксис C++
for (j=0; j<Lstr; j++)
{
     t0=clock();
        val=0; pos_x=X+j*nVar;  
        for (int ii=0; ii<nVar; ii++)
        {val+=(*(b+ii)**pos_x); pos_x++;}
      T+=clock()-t0;

...........
}
 


работает он на удивление медленно, что сводит все мои усилия на нет. В этом цикле, матрица X заполнена по столбцам в стиле fortran, раньше была заполнена по строкам, как в С, но внесённые изменения практически ничего не дали.

Вместе с этим, есть фрагмент кода, содержащий циклы с таким же количеством повторений, который работает в 4 раза быстрее:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
t0=clock();
        pos_x=X;
      for (ii=0; ii<nVar; ii++)
      {
          if (ii!=id)
          {
          val=*(pos_x+iCol);
          for(j=0; j<Lstr; j++) {*pos_x-=(*(pos_v+j)*val); pos_x++;}
          *(d+ii)-=(*(d+id)*val);
          }
          else
              pos_x+=Lstr;
      }
T+=clock()-t0;
 


в чём тут может быть дело?

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 17:50 
Ну, например, многократный вызов функции clock() - удовольствие не дешевое. :-)

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 18:00 
Это особо не влияет, clock() можно закомментировать, от этого общее время выполнение программы почти не меняется. Зато clock() показывает, что около 90% времени, программа проводит именно в этом месте.

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 18:12 
А что вы вообще собирались в этом участке кода сделать? Что такое b?

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 18:23 
Andrey_Kireew в сообщении #1450524 писал(а):
Зато clock() показывает, что около 90% времени, программа проводит именно в этом месте.
А профилирование что показывает?

Правда я не могу ничего предложить насчёт профилировщиков C++, но для Python это делается довольно просто, так что будет очень странно, если для такого языка как C++ простых вариантов действий не найдётся. От клиентского кода, когда программа запускается с профилировщиком, обычно условие простое: чтобы она поработала достаточно большое время и с достаточно близкими к реальным данными, но это обычно соблюдается.

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 18:27 
Там в обоих участках кода примерно один и тот же процесс умножение - сложение. Только в первом случае перемножаются элементы разных массивов и складываются в одном буфере val, а во втором - элементы одного массива умножаются на один и тот же val, а результат прибавляется к разным элементам другого массива.
Количество операций одинаковое, все данные такие же (X и b это массивы double), но первый вариант, почему то, работает в 4 раза медленнее второго.

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 18:45 
Andrey_Kireew в сообщении #1450543 писал(а):
Там в обоих участках кода примерно один и тот же процесс умножение - сложение. Только в первом случае перемножаются элементы разных массивов и складываются в одном буфере val, а во втором - элементы одного массива умножаются на один и тот же val, а результат прибавляется к разным элементам другого массива.
Это совершенно очевидно. Вопрос в том, что конкретно там делается. В идеале - в формульном виде.

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 19:05 
Аватара пользователя
arseniiv в сообщении #1450539 писал(а):
Правда я не могу ничего предложить насчёт профилировщиков C++

1. Они есть (и сравнительно легко находятся).
2. Использовать профайлер гораздо лучше, чем самому пытаться что-то замеря́ть.

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 19:52 
я пытался использовать gprof, но у меня ничего не получилось, out файл так и не появился,
но всё равно, по результатам многократных замеров, ситуация та же самая, время выполнения различается примерно в 4 раза

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 21:14 
Аватара пользователя
Pphantom в сообщении #1450530 писал(а):
А что вы вообще собирались в этом участке кода сделать? Что такое b?

Похоже на какую-то свертку матрицы X со строкой b.


Какого типа хранимые в них данные?

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 22:08 
Andrey_Kireew в сообщении #1450543 писал(а):
все данные такие же (X и b это массивы double)

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 22:30 
Аватара пользователя
Насколько вам критична точность в double? Знаете ли вы предельные возможные значения? Ускорения можно добиться, перейдя к целочисленной арифметике. Во-первых, само по себе умножение-сложение даблов медленнее, во-вторых операции с целыми числами лучше оптимизируются компилятором - результат не зависит от порядка действий, поэтому можно разбивать на куски, векторизовать, параллелить как угодно, а для чисел с плавающей точкой в общем случае $a+b+c \neq a+c +b$.

Попутно совет: не надо писать *(b + ii). b[ii] читается лучше, а с точки зрения производительности будет то же самое - ассемблерный код одинаковый. И не ставьте две операции в одну строку - отлаживать и читать такой код сложнее, не экономьте место.

-- Thu Apr 02, 2020 21:37:40 --

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

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 22:46 
Аватара пользователя
photon в сообщении #1450673 писал(а):
Попутно совет: не надо писать *(b + ii). b[ii] читается лучше, а с точки зрения производительности будет то же самое - ассемблерный код одинаковый.

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

 
 
 
 Re: Зловещие циклы
Сообщение02.04.2020, 23:30 
Вообще то, у меня вопрос не по поводу оформления кода, а о том, почему один цикл работает в 2 раза быстрее другого. То, что clock() не очень точный, я знаю, но 2-х кратные различия он обнаружить всё таки в состоянии. Обнаружилось это вообще без clock(), а по тому, что программа работала яво медленнее, чем ожидалось. clock() лишь помог найти слабое место

 
 
 
 Re: Зловещие циклы
Сообщение03.04.2020, 00:45 
Аватара пользователя
Andrey_Kireew в сообщении #1450688 писал(а):
Вообще то, у меня вопрос не по поводу оформления кода, а о том, почему один цикл работает в 2 раза быстрее другого.

1) Вообще-то, если код нормально оформлен, то у других обычно не возникает проблем с пониманием, что он делает. Вы просите других помочь и выплёскиваете что-то неудобоваримое, что надо сначала переписать, а потом уже попытаться понять. Как минимум, это стоит сделать из уважения к собеседникам, как максимум - вам же будет проще код отлаживать.

2) Почему разница в разы? Я вижу три варианта ответа: а) В первом случае вы дергаете перемножаемые данные из двух массивов, во втором - из одного и умножаете на константу val. Обращение к памяти, особенно для больших массивов, далеко разнесенных по памяти может дорого обойтись на фоне таких простых операций, как умножения и сложения; б) ваш метод замера времени может преподнести неприятные сюрпризы и соврать и в разы, фактически замеряя не то; в) влияет что-то вне этих циклов, но вы оставляете это за пределами своего и нашего внимания.

3) Я так понимаю, вас бОльше все-таки должно интересовать не почему быстрее или медленнее, а как сделать быстрее. Для того чтобы помочь с этим надо понимать, чего вы хотите добиться - что делает ваша функция. Иногда можно выиграть в разы, поменяв алгоритм. Поэтому вас спрашивают, что вы хотите получить.

 
 
 [ Сообщений: 34 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group