Избавиться от ветвления внутри цикла
От: kfmn Россия  
Дата: 25.08.09 11:23
Оценка:
Всем привет!

Может быть вопрос совершенно ламерский, но вот сижу-торможу и никак не сообразить...
Есть функция примерно следующего вида:

void f(double *pArray,int mode)
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        switch (mode)
        {
            case 0: 
               pObj->Fun0(pArray[i]);
               break;
            case 1: 
               pObj->Fun1(pArray[i]);
               break;
            case 2: 
               pObj->Fun2(pArray[i]);
               break;
            case 3: 
               pObj->Fun3(pArray[i]);
               break;
        }
     }
  }  
}


Т.е. в нее передается длинный массив, диапазоны индексов которого соответствуют некотором объектам.
Внутри каждого диапазона перебираются элементы массива и для тех из них, которые удовлетворяют некому условию, вызывается тот или иной метод соответствующего объекта.

Поскольку массив длинный, и функция вызывается часто, хочется, чтобы работала она по возможности быстрее. В этом смысле от ветвления внутри цикла хотелось бы избавиться. Но писать четыре совершенно идентичные за исключением имени методов Fun0-Fun3 функции неохота. Можно, конечно, вынести switch во внешний цикл, но это некая полумера — и код дублируется достаточно сильно, и если диапазонов много и они короткие — то прирост эффективности небольшой...

Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?
Re: Избавиться от ветвления внутри цикла
От: jazzer Россия Skype: enerjazzer
Дата: 25.08.09 11:36
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

Указатель на функцию поможет?
Его можно передавать вместо mode, кстати, код станет чище.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[2]: Избавиться от ветвления внутри цикла
От: kfmn Россия  
Дата: 25.08.09 11:38
Оценка:
Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, kfmn, Вы писали:

K>>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

J>Указатель на функцию поможет?
J>Его можно передавать вместо mode, кстати, код станет чище.

Дык функции-то не статические! От разных объектов вызываются. Или я чего-то не понимаю?
Re: Избавиться от ветвления внутри цикла
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 25.08.09 11:43
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

Самый простой вариант — табличный метод.
Создаем таблицу указателей на функции-члены, и вызываем их по индексу.

(На компилируемость не проверял, но должно работать)

typedef void (Class::*my_mem_fun)(double);
my_mem_fun mem_funs[4] = { &Class::Fun0, &Class::Fun1, &Class::Fun2, &Class::Fun3 };

void f(double *pArray,int mode)
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        (pObj->*mem_funs)[mode];
     }
  }  
}


От косвенности не избавишься, но код стал намного чище.

И как уже заметил jazzer, можно передавать указатель на функцию-член вместо mode (а в коде применять его к pObj).
Re: Избавиться от ветвления внутри цикла
От: Chorkov Россия  
Дата: 25.08.09 11:55
Оценка: 1 (1) +1
Здравствуйте, kfmn, Вы писали:

K>Всем привет!

K>Может быть вопрос совершенно ламерский, но вот сижу-торможу и никак не сообразить...
K>Есть функция примерно следующего вида:

K>
K>void f(double *pArray,int mode)
K>{
K>  for (int k=0; k<K; k++)
K>  {
K>     Class *pObj=GetObj(k);
K>     for (int i=From(k); i<To(k); i++)
K>     {
K>        if (!Condition(i))
K>             continue;
K>        switch (mode)
K>        {
K>            case 0: 
               pObj->>Fun0(pArray[i]);
K>               break;
K>            case 1: 
               pObj->>Fun1(pArray[i]);
K>               break;
K>            case 2: 
               pObj->>Fun2(pArray[i]);
K>               break;
K>            case 3: 
               pObj->>Fun3(pArray[i]);
K>               break;
K>        }
K>     }
K>  }  
K>}
K>


K>Т.е. в нее передается длинный массив, диапазоны индексов которого соответствуют некотором объектам.
K>Внутри каждого диапазона перебираются элементы массива и для тех из них, которые удовлетворяют некому условию, вызывается тот или иной метод соответствующего объекта.

K>Поскольку массив длинный, и функция вызывается часто, хочется, чтобы работала она по возможности быстрее. В этом смысле от ветвления внутри цикла хотелось бы избавиться. Но писать четыре совершенно идентичные за исключением имени методов Fun0-Fun3 функции неохота. Можно, конечно, вынести switch во внешний цикл, но это некая полумера — и код дублируется достаточно сильно, и если диапазонов много и они короткие — то прирост эффективности небольшой...

K>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

смотри "указатели на члены класса" .
//(осложнится синтаксис вызова, но будет ИМХО прозрачнее)
void f(double *pArray , void (Class::*FunN)(double) )
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        (pObj->*FunN)(pArray[i]);
     }
  }
}

f(A, & Class::Fun0 );

//Вариант, совместимый с твоей сигнатурой функции:
void f(double *pArray , int mode )
{
  void (Class::*FunN)(double);
  switch(mode)
  {
      case 0: FunN = & Class::Fun0;
      case 1: FunN = & Class::Fun1;
      case 2: FunN = & Class::Fun2;
      case 3: FunN = & Class::Fun3;
  };
  
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        (pObj->*FunN)(pArray[i]);
     }
  }
}


2) Шаблонная реализация функции:
(Будет своя реализация функции f для каждой вызываемой функции.)
template< void (Class::*FunN)(double) >
void f(double *pArray )
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        (pObj->*FunN)(pArray[i]);
     }
  }
}

f<& Class::Fun0>(A);


Но ИМХО:
То чем ты сейчас занимаешся — экономия на спичках.
У тебя на каждой итерации вызов еще 3-х функций, + содержимое собственно FunN. Затраты на косвенный вызов функции и switch, наверняка очень малы по сравнению с прочими затратами.
Re[2]: Избавиться от ветвления внутри цикла
От: K13 http://akvis.com
Дата: 25.08.09 11:57
Оценка:
A>От косвенности не избавишься, но код стал намного чище.

Можно избавиться от косвенности за счет раздувания кода:

template< int mode >
void fImpl( double *pArray )
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        switch (mode)
        {
            case 0: 
               pObj->Fun0(pArray[i]);
               break;
            case 1: 
               pObj->Fun1(pArray[i]);
               break;
            case 2: 
               pObj->Fun2(pArray[i]);
               break;
            case 3: 
               pObj->Fun3(pArray[i]);
               break;
            default:
               assert( false );
        }
     }
  }  
}

void f( double *pArray, int mode )
{
    switch( mode )
    {
    case 0: fImpl<0>( pArray ); break;
    case 1: fImpl<1>( pArray ); break;
    case 2: fImpl<2>( pArray ); break;
    case 3: fImpl<3>( pArray ); break;
    default: assert( false );
    }
}


Компилятор должен выкинуть switch совсем, поскольку инстанцировав шаблон, обнаруживает что там константа.

Надо ли так делать -- другой вопрос.
Re: Избавиться от ветвления внутри цикла
От: kfmn Россия  
Дата: 25.08.09 11:57
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

Большое спасибо всем ответившим!
Re[3]: Избавиться от ветвления внутри цикла
От: rg45 СССР  
Дата: 25.08.09 11:59
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Здравствуйте, jazzer, Вы писали:

J>>Здравствуйте, kfmn, Вы писали:

K>>>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

J>>Указатель на функцию поможет?
J>>Его можно передавать вместо mode, кстати, код станет чище.

K>Дык функции-то не статические! От разных объектов вызываются. Или я чего-то не понимаю?

Указатель на функцию-член тоже можно передавать:
void f(double *pArray, void (Class::*Fun)(double))
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
        if (Condition(i))
             (pObj->*Fun)(pArray[i]);
  }  
}
--
Завтра сегодня будет вчера
Re[3]: Избавиться от ветвления внутри цикла
От: rg45 СССР  
Дата: 25.08.09 12:33
Оценка:
Здравствуйте, K13, Вы писали:

A>>От косвенности не избавишься, но код стал намного чище.

K13>Можно избавиться от косвенности за счет раздувания кода:

K13>
K13>template< int mode >
K13>void fImpl( double *pArray )
K13>{
K13>  for (int k=0; k<K; k++)
K13>  {
K13>     Class *pObj=GetObj(k);
K13>     for (int i=From(k); i<To(k); i++)
K13>     {
K13>        if (!Condition(i))
K13>             continue;
K13>        switch (mode)
K13>        {
K13>            case 0: 
               pObj->Fun0(pArray[i]);
K13>               break;
K13>            case 1: 
               pObj->Fun1(pArray[i]);
K13>               break;
K13>            case 2: 
               pObj->Fun2(pArray[i]);
K13>               break;
K13>            case 3: 
               pObj->Fun3(pArray[i]);
K13>               break;
K13>            default:
K13>               assert( false );
K13>        }
K13>     }
K13>  }  
K13>}
K13>

K13>Компилятор должен выкинуть switch совсем, поскольку инстанцировав шаблон, обнаруживает что там константа.

Зачем же ждать от компилятора то, что несложно сделать самому:
template<int Mode> struct ModeTraits 
{ 
  static void (Class::*handler)(double);
};

template<> void (Class::*ModeTraits<0>::handler)(double) = &Class::Fun0;
template<> void (Class::*ModeTraits<1>::handler)(double) = &Class::Fun1;
template<> void (Class::*ModeTraits<2>::handler)(double) = &Class::Fun2;
template<> void (Class::*ModeTraits<3>::handler)(double) = &Class::Fun3;

template< int mode >
void fImpl( double *pArray )
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
        if (Condition(i))
             (pObj->*ModeTraits<mode>::handler)(pArray[i]);
  }  
}
--
Завтра сегодня будет вчера
Re[4]: Избавиться от ветвления внутри цикла
От: Alexander G Украина  
Дата: 25.08.09 12:38
Оценка:
Здравствуйте, rg45, Вы писали:

R>Зачем же ждать от компилятора то, что несложно сделать самому:

Я больше верю, что компилятор соптимизирует switch, чем соптимизирует такой вызов функции-члена до некосвенного вызова.
Русский военный корабль идёт ко дну!
Re[5]: Избавиться от ветвления внутри цикла
От: rg45 СССР  
Дата: 25.08.09 12:47
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Здравствуйте, rg45, Вы писали:

R>>Зачем же ждать от компилятора то, что несложно сделать самому:

AG>Я больше верю, что компилятор соптимизирует switch, чем соптимизирует такой вызов функции-члена до некосвенного вызова.

А, пардон, я как-то выпустил из виду, что в центре внимания лишняя косвенность. Тогда так:

template<int Mode> struct ModeTraits;

template<> struct ModeTraits<0> { static void handle(Class* pObj, double value) { pObj->Fun0(value); } };
template<> struct ModeTraits<1> { static void handle(Class* pObj, double value) { pObj->Fun1(value); } };
template<> struct ModeTraits<2> { static void handle(Class* pObj, double value) { pObj->Fun2(value); } };
template<> struct ModeTraits<3> { static void handle(Class* pObj, double value) { pObj->Fun3(value); } };
 
template< int mode >
void fImpl( double *pArray )
{
  for (int k=0; k<K; k++)
  {
     Class *pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
        if (Condition(i))
             ModeTraits<mode>::handle(pObj, pArray[i]);
  }  
}
--
Завтра сегодня будет вчера
Re: Избавиться от ветвления внутри цикла
От: igna Россия  
Дата: 25.08.09 13:15
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Подскажите, можно ли это эффективно сделать по-другому, без ненужного дублирования кода?

Сделай mode шаблонным параметром:

template <int mode>
void f(double *pArray)


Ну и вызовы f(pArray, mode) замени на f<mode>(pArray).

Больше ничего менять не придется.
Re: Избавиться от ветвления внутри цикла
От: Igore Россия  
Дата: 26.08.09 08:07
Оценка: :))
Может наследование?
class IClass
{
public:
  virtual void Fun(double) = 0;
};

class CClass1 : public IClass
{
public:
  // from base
  virtual void Fun(double tmp){/*...*/};
};

void f(double *pArray,int mode)
{
  for (int k=0; k<K; k++)
  {
     IClass* pObj=GetObj(k);
     for (int i=From(k); i<To(k); i++)
     {
        if (!Condition(i))
             continue;
        pObj->Fun(pArray[i]);
     }
  }  
}


Здравствуйте, kfmn, Вы писали:

K>Всем привет!

K>Может быть вопрос совершенно ламерский, но вот сижу-торможу и никак не сообразить...
K>Есть функция примерно следующего вида:
Re[2]: Избавиться от ветвления внутри цикла
От: Кодт Россия  
Дата: 26.08.09 09:11
Оценка: :))
Здравствуйте, Igore, Вы писали:

I>Может наследование?
Объекты — это замыкания для бедных!
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.