Итератор же.

чтобы пробегать цикл A наиболее быстро, необходимо запускать перебор элементов вектора последовательностями в параллель (например один поток - перебор 0..999, второй - 1000..1999 и т.д.), если позволяет целевая функция

если же нужен простой перебор - std::for_each во все поля, можно итераторами, никакой особой разницы

> необходимо запускать перебор элементов вектора последовательностями в параллель (например один поток - перебор 0..999, второй - 1000..1999 и т.д.), если позволяет целевая функция

OpenMP я туда впихну, но вопрос не в том :)

если же нужен простой перебор - std::for_each во все поля, можно итераторами, никакой особой разницы

у меня объекты с не статическими методами, а для for_each надо или глобальные ф-ции, или статические методы... или нет?

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

=)

Как уже сказали, распараллеливание.

И часто надо совершать такие циклы? Может таки не все в порядке в датском королевстве, и надо бы алгоритм (на высшем уровне) пересмотреть, м?

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

Меня интересует один момент. Я слышал, что процессоры x86 «любят» циклы, идущие в обратном порядке и оптимизатор обычно переворачивает цикл верх-ногами. Может кто-нибудь что-то умное скажет по этому поводу?

Если без GPU, то pthreads помогут. А оптимальное количество их можно узнать на этапе configure/cmake (например, равное количеству ядер в системе, или удвоенному количеству ядер).

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

А что за алгоритм-то?

При цикле задом-наперед на каждой итерации происходит сравнение счетчика с нулём

Ага. Вернемся к коду:

for(int i = 0; i<len; ++i)
{
    arr[i]->Method(a, b);
}

Ты имеешь ввиду зависимость корректности результата от направления обхода? Можно ж сделать цикл задом наперед и при этом arr[len - i]. Только так оно уже врядли будет работать быстрее :) Было бы интересно, конечно, погонять тесты и посмотреть, как всё будет на самом деле, но всё времени нет. Какой логики придерживается компилятор при оптимизации, я не знаю.

Может есть смысл вручную сделать цикл с конца?

Я думаю в наше время это уже не актуально.

>Я слышал, что процессоры x86 «любят» циклы, идущие в обратном порядке и оптимизатор обычно переворачивает цикл верх-ногами.

Для циклов по счетчику когда-то сделали даже специальную инструкцию - loop. Но где-то в районе первопня пара инструкций dec/jnz стала быстрее. На современных процессорах с несколькими исполнительными устройствами в каких-то ситуациях может оказаться, что три инструкции inc/cmp/jne с учетом предыдущих разложаться лучше. Компилятор сам не совсем дурак и такие элементарные вещи учитывать умеет. Вообще нет смысла об этом задумываться.
А то бывает, кто-то кривоголовый в целях «оптимизации» итератора начинает данные обрабатывать в обратном порядке, отчего префетч кэша может выжить из ума.

отчего префетч кэша может выжить из ума.

А может и не выжить. Может loop быстрее, а может быстрее dec/jnz, а может быстрее inc/cmp/jne, а может быть ещё какой-то фокус с раскидыванием по конвейерам или с кэшем для определенного поколения процессоров когда третий, совершенно не очевидный вариант окажется быстрее.

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

у меня объекты с не статическими методами, а для for_each надо или

глобальные ф-ции, или статические методы... или нет?

Нет, man std::tr1::bind

Сомневаюсь что он имеет право разворачивать цикл, ведь у нас изменяется состояние.

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

у меня объекты с не статическими методами, а для for_each надо или глобальные ф-ции, или статические методы... или нет?

стоп, нафуа Вам статические методы объектов? for_each работает по другому

#include <iostream>

#include <algorithm>
#include <string>
#include <vector>

class Foo {
public:
	Foo(const std::string& s) : _s(s) { }
	void bar() const { std::cout << _s << std::endl; }

private:
	std::string _s;
};

int main( ) {

	std::vector<Foo> v;

	v.push_back( Foo("something Fooish") );
	v.push_back( Foo("Fooishness is not a crime") );
	v.push_back( Foo("all king's Fooes") );
	v.push_back( Foo("to Foo or not to Foo") );

	std::for_each(
			v.begin(), v.end(),
			[](const Foo& foo){ foo.bar(); } );

	return 0;
}

собирать с ключиком -std=c++0x

> Как реализовать цикл А, чтобы делать рассчёты наиболее быстро?

как уже говорили - итератор, все оптимизации надо уже продумывать в этом методе, если он небольшой - то можно попробовать сделать его inline

собирать с ключиком -std=c++0x

в С++0х можно написать красивее:

for( Foo& foo : v )
	foo.bar();

> собирать с ключиком -std=c++0x

в С++0х можно написать красивее:

конечно можно, просто в данном случае иллюстрировался принцип работы std::for_each, а делать функцию-костыль я не очень люблю - уж лучше анонимную, так появился c++0x... если хотите - это унаследованное решение, легаси блин :)

Только на 4.6, который еще очень сыр.

   std::for_each(
         v.begin(), v.end(),
       [](const Foo& foo){ foo.bar(); } 

   for(auto f = v.begin(); f != v.end(); f++)
         f->bar();

for(auto f = v.begin(); f != v.end(); f++)
      f->bar();

f++

семён семёныч, ну кто так делает?

Ты думаешь, компилер не сообразит, что это одно и то же с ++f?

Ты думаешь, компилер не сообразит, что это одно и то же с ++f?

не, ну чё тогда мелочиться - тогда и const не будем ставить, да?

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

Зачем? Можно проще:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

struct Object
{
};

class Foo 
{
public:
    Foo(const Object _object) : m_object(_object)
    { } 
    void operator() (const std::string& _s) const
    {   
        // do something useful with m_object
        std::cout << _s << std::endl;
    }   

private:
    Object m_object;
};

int main()
{
    std::vector<std::string> v;

    v.push_back("something Fooish");
    v.push_back("Fooishness is not a crime");
    v.push_back("all king's Fooes");
    v.push_back("to Foo or not to Foo");

    Object object;

    std::for_each(
            v.begin(), v.end(),
            Foo(object)
            );  

    return 0;
}

> Ваша задача ему помочь, а не мешать, не так ли?

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

:3

А насколько толстые элементы вектора и насколько легкие запускаемые методы элементов? если элементы толстые, а методы легкие, то пофигу как делать и никакие шреды тут не помогут (скорей помешают) - все упрется в пропускную способность памяти.

Если элементы вектора независимы, то лучше переставить циклы местами.

А что за алгоритм-то?

Да всё те же самые рассчёты теплофизики, нужные инженерным геокриологам и о которых уже было несколько архиполезных (для меня) топиков на ЛОРе. Первая моя большая программа, долгострой, делаю уже год (в паре с одним парнем, но он по большей части по теории), уже 20 тыщ строк с лишним:

http://cloc.sourceforge.net v 1.53  T=1.0 s (145.0 files/s, 20463.0 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C++                             71           1586           2155           8877
C/C++ Header                    74           1275           3159           3411
-------------------------------------------------------------------------------
SUM:                           145           2861           5314          12288
-------------------------------------------------------------------------------

Сегодня второй раз получил за неё первую премию на конференции :). Она нужна практически всем людям моей профессии. Приходит на замену старой досовской софтине, та считает как минимум на 3 порядка медленней (после распараллеливания станет на 4 порядка).

Та старая программа — очень полезный инструмент, у нас на кафедре в ней многие считает важные вещи. И в фирмах используют. Только ей лет 20, она безнадёжно устарела: как интерфейсом и скоростью рассчётов, так и возможностями (в плане того, что нужно геокриологам).

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

Скрин (насыпь и труба).

И да, старая программа закрытая и продаётся фирмам по 40 косарей за экземпляр (и ведь до сих пор покупают!). А мы хотим распространять нашу под GPLv3. Хотя ещё посмотрим, не будет ли против кафедра. У них когнитивный диссонанс — с одной стороны, наша программа им ах как нужна (аплодисменты на конференции, никогда их не забуду :)), а с другой (наверное! но пока не обсуждал) получать деньги от фирм это хорошо.

Не знаю, нафиг я эту простыню накатал, похвастаться охота и время занять надо, а то уже вторые сутки не сплю.

По-моему, ++i читается лучше, чем i++.

На вопрос-то я не ответил. Видишь, там на скрине проглядывает сетка (прямоугольнички)? Эти прямоугольнички — часть численного решения задачи теплофизики. Так вот, между каждыми двумя блоками (SoilBlock) есть площадка теплопотока (HeatSurface). Надо сначала пробежаться по каждой площадке и вызвать там вот такой метод:

void HeatSurface::moveInTime() const
{
    double h;

    // Рассчитываем плотность теплопотока.
    if(m_boundary_condition == NULL) {
        h = 2 *
            (m_soil_block2->temperature() - m_soil_block1->temperature())
            / (m_soil_block1->dimension(m_axe) * m_soil_block1->invertedEffectiveConductivity()
               + m_soil_block2->dimension(m_axe) * m_soil_block2->invertedEffectiveConductivity());
    } else {
        switch (m_boundary_condition->type()) {
        case BoundaryCondition::FirstType:
            h = (m_boundary_condition->temperature() - m_soil_block1->temperature())
                / (m_r * m_soil_block1->invertedEffectiveConductivity());
            break;
        case BoundaryCondition::SecondType:
            h = m_boundary_condition->heat_flow_density();
            break;
        case BoundaryCondition::ThirdType:
            h = (m_boundary_condition->temperature() - m_soil_block1->temperature())
                / (m_r * m_soil_block1->invertedEffectiveConductivity()
                   + m_boundary_condition->resistivity());
            break;
        }
    }

    // Переводим плотность теплопотока в теплопоток
    h *= m_square;
    // и передаём его в ячейки
    m_soil_block1->addHeat(h);
    if(m_soil_block2 != NULL) {
        m_soil_block2->addHeat(-h);
    }
}
// (все методы чужие, вызываемые тут — заинлайнены)

А потом пробежаться по всем блокам и сделать там это:

void SoilBlock::moveInTime()
{
    m_enthalpy += (m_heat_diff * m_time_step_per_volume);
    m_heat_diff = 0;
    calcCondition();
    calcIEConductivity();
}

/**
 * Используются следующие формулы:
 * - \f$ T=1/C_f+T_{bf}, V=0 \f$ при \f$ I<0 \f$
 * - \f$ T=T_{bf}, V=1/L_\nu \f$ при \f$ 0 \leq I \leq L_\nu \f$
 * - \f$ T=(I-L_\nu)/C_{th}+T_{bf}, V=1 \f$ при \f$ I > L_\nu \f$
 */
void SoilBlock::calcCondition()
{
    if(m_enthalpy < 0) {
        m_temperature = m_enthalpy / m_capacity.frozen + m_transition_temperature;
        m_thawed_part = 0;
    } else if(m_enthalpy > m_transition_heat) {
        m_temperature = (m_enthalpy - m_transition_heat) / m_capacity.thawed +
                        m_transition_temperature;
        m_thawed_part = 1;
    } else { /* 0 <= I <= L_v */
        m_temperature = m_transition_temperature;
        m_thawed_part = m_enthalpy / m_transition_heat;
    }
}

/// \f$ 1/\lambda = V/\lambda_{th} + (1-V)/\lambda_f \f$.
void SoilBlock::calcIEConductivity()
{
    if(m_thawed_part == 0) {
        m_ie_conductivity = 1 / m_conductivity.frozen;
    } else if(m_thawed_part == 1) {
        m_ie_conductivity = 1 / m_conductivity.thawed;
    } else {
        m_ie_conductivity = m_thawed_part / m_conductivity.thawed +
                            (1 - m_thawed_part) / m_conductivity.frozen;
    }
}

Вот. И вот такие 2 цикла позволят нам сделать шаг, как правило от 10 до 30 минут. И вот таким раком надо прошагать лет 50. Блоков, как правило, от 1000 до 10000.

> Если элементы вектора независимы, то лучше переставить циклы местами.

Не понял насчёт перестановки :).

В общем, ясно. Всё инлайню (тем более, метод этот нигде кроме как в этом цикле не вызывается) и юзаю итератор.

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

Если так сделать нельзя, то нужно подумать как изменить алгоритм;-)

> Если можно в цикле по элементам вектора запустить цикл по итерациям (элементы независимы)

Нет, никак. Элементы независимы только в одной итерации внутреннего цикла. Это диффура.

> ++i читается лучше, чем i++.

Дело не в ++N vs. N++. Есть устойчивые идеоматические обороты, типа плюсового for( int i = 0; i < max; i++)

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

А почему бы вам не распараллелить эту задачу для вычисления на GPU?

> А почему бы вам не распараллелить эту задачу для вычисления на GPU?

потому-что делают не для себя - т.е. запускаться должна на разном железе

Так можно два варианта сделать: медленный, для CPU, и быстрый - для GPU.

> Так можно два варианта сделать: медленный, для CPU, и быстрый - для GPU.

можно, но если уже получается на «4 порядка» быстрее старой программы, то возможно наличие одного варианта предпочтительней - меньше геморроя сейчас и потом, хотя конечно это уже на усмотрение ТС

> А почему бы вам не распараллелить эту задачу для вычисления на GPU?

Это входит в наши планы. Но не в ближайшие. Если что, кафедра не обломается и поставит два-три компа с крутыми видеокартами в кабинете (два уже есть). Будет выбор способа рассчётов.

можно, но если уже получается на «4 порядка» быстрее старой программы, то возможно наличие одного варианта предпочтительней - меньше геморроя сейчас и потом, хотя конечно это уже на усмотрение ТС

Старая программа могла считать многие задачи сутками (хотя некоторые задачи укладывались в 15 минут). В нашей программе я вырубил в рассчётной модели одну фичу, которая позволяла в 10 раз увеличить шаг по времени. Но эта фича таки делала модель кривее, как показывает практика, поэтому я и отказался от неё (фича, кстати, называется «регуляризация»). Таким образом, на деле получается не 3, а 2 порядка: шаг нужен в 10 раз меньше, зато считает в 1000 раз быстрее, итого надо в 100 раз меньше времени. То, что считалось сутки, теперь считается 15 минут. Это совсем не долго (работы делаются месяцами, так что если рассчёты займут какие-то жалкие 2 часа — ерунда по сравнению с несколькими неделями машинного времени), но увеличение скорости было бы полезно.

> for( int i = 0; i < max; i++)

всю жизнь писал там ++i... щас глянул исходники Qt ­— там тоже всегда ++i.

> фича, кстати, называется «регуляризация»

У вас там некорректная задача?

Глянул исходники линукса - везде i++.

:3

А какая разница? Хоть ++i, хоть i++, хоть i+=1, хоть max-- (если i не используется в теле цикла) напишите - результат от этого не изменится...

> Ваша задача ему помочь, а не мешать, не так ли?

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

что-ж, тогда вынужден Вас огорчить - использование постфиксного инкремента в данном случае читабельность не улучшает :)

Глянул исходники линукса - везде i++.

и последний вопрос - что ты со своими исходниками линуска делаешь в теме по С++?

>>конечно, погонять тесты и посмотреть, как всё будет на самом деле, но всё времени нет

пустой цикл

#include <stdio.h>

static const unsigned long MAX = 0xffffffff;

int main(int argc, char *argv[])
{
	unsigned long i;

	for (i = 0; i < MAX; i++);

	//~ for (i = MAX; i > 0; i--);

	return 0;
}

в одном случае
real 0m8.679s
user 0m8.630s
sys 0m0.030s

в другом:
real 0m7.797s
user 0m7.790s
sys 0m0.000s

У меня для случая с int дало одинаковые результаты. То ли от компилятора зависит, то ли еще непонятно от чего...