Удалить переключатель из цикла

Question

У меня есть петля с переключателем внутри, что выглядит примерно так (но гораздо сложнее).

for(int i = 0; i < N; i += inc) 
{ 
    v = 0.0; 
    switch(ConstVal) 
    { 
    case 2: v += A[i]; 
    case 1: v += A[i+k]; 
    case 0: v += A[i+j]; 
    } 
    // do some stuff with v 
} 

ConstVal неизвестен во время компиляции, но исправлен во время процедуры инициализации. Есть ли способ удалить оператор switch без компиляции нескольких вариантов цикла for? Учитывая, что x86 имеет непрямое ветвление, должен быть простой способ встроить сборку, чтобы перейти к случаю, который я хочу, а не возвращаться к вершине цикла на каждой итерации. Как бы вы это сделали (в gcc)? Наконец, можно ли это сделать, не мешая анализу оптимизации компилятора. Я уже вручную разворачиваю циклы, но я уверен, что происходит еще много оптимизаций, которые я не хочу ломать.

Я понимаю, что функция мета-программирования Julia дает вам доступ к синтаксическому синтаксическому анализатору и абстрактному синтаксическому дереву. В сочетании с JIT вы можете решить эту проблему. Я бы подумал, что в C было бы разумное решение, даже без семантики для непрямой ветви. Обратите внимание, что устройство Duff не является решением, так как я хочу вернуться к одному и тому же описанию case на каждой итерации цикла. Эта проблема часто возникает.

EDIT

я обнаружил, что нет условного непрямого команда перехода x86. Кроме того, встроенная сборка gcc допускает только фиксированные метки. И все же, используя gcc-расширения, это все равно можно сделать. См., Например, https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values.

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

void *forswitch; 
switch(ConstVal) 
{ 
case 2: forswitch = &&C; break; 
case 1: forswitch = &&B; break; 
case 0: forswitch = &&A; break; 
} 
void *_forswitch[] = {forswitch, &&END_FOR_SWITCH}; 


i = 0; 
{ 
    v = 0.0; 
    C: v += _A[i]; 
    B: v += _A[i+k]; 
    A: v += _A[i+j]; 

    // do some stuff with v 

    i += inc; 
    forswitch = _forswitch[i==N]; 
    //forswitch = (i<N)? forswitch: &&END_FOR_SWITCH; 
    goto *forswitch; 
} 

END_FOR_SWITCH: 
return; 

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

С этим решением существует ряд очевидных проблем. (1) Это не переносимо. (2) Реализуя цикл самостоятельно, это не только сложнее понять код, но может помешать оптимизации компилятора (например, автоматическое разворачивание цикла). (3) Компилятор не может совместно оптимизировать весь оператор switch, даже если нет разрывов, потому что он не знает, во время компиляции, какие операторы будут выполняться. Тем не менее, он может умело переорганизовать коммутатор таким же образом, как другие указали в некоторых из приведенных ниже ответов. Путем ручного внедрения коммутатора (в сочетании с циклом for) я затрудняю компилятор сделать такую ​​оптимизацию, поскольку, удалив семантику переключения, мое намерение скрывается за счет оптимизации.

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

EDIT 2

Я нашел гораздо лучшее решение, которое является более портативными и более эффективным. Когда у вас есть ситуация, когда существует небольшое количество возможных опций времени исполнения, вы можете создать оболочку вокруг оптимизированной функции, исправить все константы времени выполнения, а затем встроить функцию для каждой копии констант.Если существует только одна константа, вы можете использовать таблицу поиска указателей функций, каждая из которых устанавливает константу и строит функцию. Если у вас более сложная ситуация, вам понадобится структура управления if-elseif-else. Одна из функций может быть оставлена ​​со всеми свободными переменными, поэтому нет потери общности. Я думаю об этом как о закрытии компиляции. Компилятор делает всю тяжелую работу без каких-либо грязных макросов или дублирует код для поддержки.

В моем коде это увеличение производительности на 10% -20% на уже значительно оптимизированном коде (из-за жесткого кодирования различных констант и не имеет ничего общего с самим коммутатором). В моем игрушечном примере изменение выглядело бы примерно так.

inline void __foo(const int ConstVal) 
{ 
    for(int i = 0; i < N; i += inc) 
    { 
     v = 0.0; 
     switch(ConstVal) 
     { 
     case 2: v += A[i]; 
     case 1: v += A[i+k]; 
     case 0: v += A[i+j]; 
     } 
     // do some stuff with v 
    } 
} 

void foo() 
{ 
    // this could be done with a lookup table 
    switch(ConstVal) 
    { 
    case2: __foo(2); break; 
    case1: __foo(1); break; 
    case0: __foo(0); break; 
    } 
} 

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

Answer 1

Нет, я не вижу возможности оптимизировать оператор switch. Кроме того, это не так дорого. Поскольку нет заявлений break, переключатель имеет тенденцию «ослабевать». Это приводит к:

switch(ConstVal) 
    { 
    case 2: v= A[i] + A[i+k] + A[i+j]; break; 
    case 1: v=  A[i+k] + A[i+j]; break; 
    case 0: v=     A[i+j]; break; 
    } 
    // do some stuff with v 

, и я не вижу, как снять зависимость от ConstVal.

Вы можете сделать переключатель перед циклом с тремя петлями, по одному для каждого значения ConstVal, но это наверняка будет выглядеть уродливым кодом, в зависимости от того, что делает do some stuff with v.

Answer 2

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

Сказав это, вы знаете, что это проблема? Является ли это switch ответственным за 10% или более времени выполнения? Очень часто люди сосредотачиваются на проблемах. Они знают, что должны сначала «профилировать», но на самом деле они этого не делают. (Это случай «готового огня»)

Метод, на который положительно полагаются люди, - this.

Answer 3

Есть ли способ удалить оператор switch без компиляции нескольких вариантов цикла for?

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

switch (constVal) { 
case 2: 
    A1 = A; 
    B1 = A + k; 
    C1 = A + j; 
    break; 
case 1: 
    A1 = big_zero_array; 
    B1 = A + k; 
    C1 = A + j; 
    break; 
case 0: 
    A1 = B1 = big_zero_array; 
    C1 = A + j 
    break; 
} 

for (int i = 0; i < N; i += inc) { 
    v = A1[i] + B1[i] + C1[i]; 
    //.... 
} 

Все еще эта вещь требует дополнительной памяти и может быть еще медленнее при некоторых обстоятельствах.