Критический цикл, содержащий много «если», чей вывод является постоянным: Как сэкономить на тестах условий? - PullRequest
Новая
       16

Критический цикл, содержащий много «если», чей вывод является постоянным: Как сэкономить на тестах условий?

4 голосов
/ 02 апреля 2011

У меня есть критический цикл в моем коде с этой формой: 

int myloop(int a, .....){

   /* some stuff */

   // Critical loop
   while(...){
       /* Some Stuff */
       if(a == 1){
          // .....
       }
       else if(a == 2){
          // .....
       }
       else if(a == 3){
          // .....
       }
       else{
          // ....
       }
   }
}

Поскольку цикл никогда не касается значения «a», взятая ветвь никогда не изменится, но, поскольку этот цикл действительно тяжел, ему потребуется многократно проверять значение «a», что совершенно не нужно. Лучше всего, вероятно, дублировать цикл, чтобы можно было проверить «если» до начала цикла, но это означало бы копирование множества вещей, общих для обеих ситуаций, и привело бы к очень уродливому коду ...

Есть ли способ попросить GCC / G ++ продублировать этот код при компиляции? Или любой другой прием, чтобы избежать многократного тестирования значения?

Спасибо за вашу помощь!

Nathann

Ответы [ 10 ]

6 голосов
/ 02 апреля 2011

Прежде всего, вы можете использовать оператор switch здесь: 

switch(a) {

   case 0:
     // handle a==0
     break;

   case 1:
     // handle a==1
     break;

   default:
     // handle all other cases
}

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

это будет означать копирование множества материалов, общих для обеих ситуаций

Refactor !Как насчет помещения общего кода в отдельную функцию, возможно, объявите его inline и надеетесь, что компилятор последует подсказке?Встраивание функций - это хороший способ позволить компилятору выполнять дублирование кода (два других способа - это шаблоны и препроцессор, оба здесь явно неуместны).цикл, но вы должны получить основной принцип.

Последнее, но не менее важное: профиль .Проверьте, действительно ли цикл является узким местом производительности.Посмотрите на сгенерированный машинный код.Скорее всего, компилятор уже использует большинство предложенных оптимизаций.

2 голосов
/ 02 апреля 2011

Один из распространенных способов сделать это заключается в следующем: 

// make function implementation inline...
static inline int myloop_inline(int a, .....){

   /* some stuff */

   // Critical loop
   while(...){
       /* Some Stuff */
       if(a == 1){
          // .....
       }
       else if(a == 2){
          // .....
       }
       else if(a == 3){
          // .....
       }
       else{
          // ....
       }
   }
}

// wrapper function which calls myloop_inline with hard-coded values of a
int myloop(int a, .....){
{
    switch (a)
    {

    // expand inline function for all performance-critical values of a...

    case 1:
        myloop_inline(1);
        break;

    case 2:
        myloop_inline(2);
        break;

    case 3:
        myloop_inline(3);
        break;

    ...

    // for any values of a for which the function is not performance-critical
    // we can just use a default case...

    default:
        myloop_inline(a);
        break;

    }
}

Обратите внимание, что поскольку a передается как литеральная константа, когда myloop_inline() называется формой myloop(), компилятор может оптимизировать всенерелевантные тесты и мертвый код при расширении встроенной функции.

Возможно, вы захотите предпринять шаги, чтобы убедиться, что myloop_inline() действительно встроен, это включает в себя компиляцию с включенной оптимизацией, конечно (например, -O3), ив случае, например, gcc вы можете добавить __attribute__ ((always_inline)).

2 голосов
/ 02 апреля 2011

Вы можете использовать switch оператор: 

while(...)
{
   switch(a)
   {
   case 1:
      // do what you want
      break;
   case 2:
      // do what you want
      break;
   case x:
      // do what you want
      break;
   default:
      //if not matching any previous..
   }
}
1 голос
/ 02 апреля 2011

Как насчет создания каждой отдельной функции, а затем иметь указатель на функцию? 

void func_a() {
    // ...
}

void func_b() {
    // ...
}

int myloop(int a, ...) {
    void (*func)();
    if (a == 1) {
        func = &func_a;
    } else if (a == 2) {
        func = &func_b;
    } ...

    while (1) {
        /* Some stuff */
        func();
    }
}
1 голос
/ 02 апреля 2011

Как насчет определения функции, которая делает все, что происходит внутри цикла while, и определения ее inline?Затем переместите цикл while внутрь каждого if и вызовите функцию там.Это будет делать именно то, что вы хотите.

1 голос
/ 02 апреля 2011

Я бы посоветовал передать «a» в качестве параметра шаблона, т.е. 

template< int a > 
int myloop(.....) {
  if( a==1 ) { ... }
}

Как будто он будет оптимизирован должным образом.

Однако вы не сможетепередать переменную в качестве параметра шаблона, так что где-то еще вы должны поместить этот переключатель. 

switch(a) { 
  case 1: myloop<1>(...); break;
  ...
}
0 голосов
/ 26 апреля 2012

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

if (a == 0) {
    while (...) {
       /* some stuff */
       // 0 stuff
    }
} else if (a == 2) {
    while (...) {
       /* some stuff */
       // 2 stuff
    }
} else if (a == 3) {
 ....
}
0 голосов
/ 12 апреля 2011

Вы можете использовать массив с указателем на функции, если ваши условия в основном соседние. 

typedef void ( *case_func )( type1 param1, type2 param2 );

void case_func1( type1 param1, type2 param2 );
void case_func2( type1 param1, type2 param2 );
void case_func3( type1 param1, type2 param2 );
void case_func5( type1 param1, type2 param2 );

case_func    func_array[] =
{
    &case_func1,
    &case_func2,
    &case_func3,
    NULL,        // Just a place holder, for non-contiguous values.
    &case_func5
};

int myloop(int a, .....){

   /* some stuff */

   // Critical loop
   while(...)
   {
       if ( func_array[ a ] && a < sizeof( func_array ) )
           func_array[ a ]( .... );
   }
}

Если вы можете быть уверены, что в вашем массиве не будет дыр и что a никогда не будет выходить за границы массива, вы можете пропустить if ( func_array[ a ] && a < sizeof( func_array ) ), уменьшив код до совсем не сравниваемого.

В любом случае, этот подход может быть немного понятнее и может стоить, даже если он не дает большого прироста производительности.

0 голосов
/ 02 апреля 2011

Схожи ли операции, выполняемые при каждом условии?В этих ситуациях я обычно использую операторы if, чтобы установить значение ключевых объектов или указателей на объекты, а затем использую эти значения в оставшемся коде ... в основном, максимизирую использование косвенного обращения.

dim x в качестве объекта
dim y в виде строки
Если (a == 1), то
x = foo.object
y = bar.string
elseif (a == 2)
x = yuk.object
y = yo.string
конец, если
while ...
dofunction (x, y)
end, пока

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

0 голосов
/ 02 апреля 2011 
int myloop(int a, ...){
    if(a == 1){
      myloop1(a, ...);
    }
    else if(a == 2){
      myloop2(a, ...);
    }
    else if(a == 3){
      myloop3(a, ...);
    }
    else{
      myloopelse(a, ...);
    }
}

myloop#(int a, ...){
    SomeStuffAboveLoop(...)
    while(...){
        SomeStuffInsideLoop(...)
        //Do what you want for the appropriate #
    }
}

Вы можете также поменять блок if на переключатель, что показывают многие другие ответы.

...