Зловещие циклы

[Andrey_Kireew]

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

Используется синтаксис 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;
 

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

[Pphantom]

Ну, например, многократный вызов функции clock() - удовольствие не дешевое.

[Andrey_Kireew]

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

[Pphantom]

А что вы вообще собирались в этом участке кода сделать? Что такое b?

[arseniiv]

Andrey_Kireew в сообщении #1450524 писал(а):

Зато clock() показывает, что около 90% времени, программа проводит именно в этом месте.

А профилирование что показывает?

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

[Andrey_Kireew]

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

[Pphantom]

Andrey_Kireew в сообщении #1450543 писал(а):

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

Это совершенно очевидно. Вопрос в том, что конкретно там делается. В идеале - в формульном виде.

[Munin]

arseniiv в сообщении #1450539 писал(а):

Правда я не могу ничего предложить насчёт профилировщиков C++

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

[Andrey_Kireew]

я пытался использовать gprof, но у меня ничего не получилось, out файл так и не появился,
но всё равно, по результатам многократных замеров, ситуация та же самая, время выполнения различается примерно в 4 раза

[photon]

Pphantom в сообщении #1450530 писал(а):

А что вы вообще собирались в этом участке кода сделать? Что такое b?

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


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

[Andrey_Kireew]

Andrey_Kireew в сообщении #1450543 писал(а):

все данные такие же (X и b это массивы double)

[photon]

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

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

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

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

[Munin]

photon в сообщении #1450673 писал(а):

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

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

[Andrey_Kireew]

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

[photon]

Andrey_Kireew в сообщении #1450688 писал(а):

Вообще то, у меня вопрос не по поводу оформления кода, а о том, почему один цикл работает в 2 раза быстрее другого.

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

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

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