Как выжать максимум скорости из switch-блока?
Есть функция со switch-блоком с большим числом case'ов, которая сжирает 10-15% времени выполнения программы. Возникла потребность в оптимизации. Насколько я понимаю, для увеличения скорости ветвления необходимо уменьшить долю ложных предсказаний переходов, т.к. практически каждое ложное предсказание приводит к полной (или почти полной) перезагрузке конвейера процессора — а это в современных процессорах (Pentium 4) это 20 тактов. В процессорах для динамического предсказания переходов используется BTB-таблица хранящая 2 бита истории ветвления. Соответственно для построения оптимальной цепочки if'ов (заменяющих switch) необходимо собрать статистику входных параметров и произвести "моделирование" поведения BTB-таблиц. Вот такая вот идея.
Вопросы:
1. Если какие документы/ссылки по оптимизации цепочки if'ов? Если есть, дайте пожалуйста ссылку.
2. Кто-нибудь занимался оптимизацией if'ов/switch'ей? Поделитесь опытом.
Здравствуйте, Алексей., Вы писали:
А>Как выжать максимум скорости из switch-блока? А>Есть функция со switch-блоком с большим числом case'ов, которая сжирает 10-15% времени выполнения программы. Возникла потребность в оптимизации. Насколько я понимаю, для увеличения скорости ветвления необходимо уменьшить долю ложных предсказаний переходов, т.к. практически каждое ложное предсказание приводит к полной (или почти полной) перезагрузке конвейера процессора — а это в современных процессорах (Pentium 4) это 20 тактов. В процессорах для динамического предсказания переходов используется BTB-таблица хранящая 2 бита истории ветвления. Соответственно для построения оптимальной цепочки if'ов (заменяющих switch) необходимо собрать статистику входных параметров и произвести "моделирование" поведения BTB-таблиц. Вот такая вот идея. А>Вопросы: А>1. Если какие документы/ссылки по оптимизации цепочки if'ов? Если есть, дайте пожалуйста ссылку. А>2. Кто-нибудь занимался оптимизацией if'ов/switch'ей? Поделитесь опытом.
Если условия последовательные то можно применить карту переходов что значительно эффективнее :
typedef void (*pvoid_void)(void);
void f1(void){}
void f2(void){}
void f3(void){}
void f4(void){}
void f5(void){}
static const pvoid_void map_f[]={f1,f2,f3,f4,f5};
void f(int i) { (*map_f[i])(); } // сразу переходим куда надо
Здравствуйте, _nn_, Вы писали:
__>Если условия последовательные то можно применить карту переходов что значительно эффективнее : __>
__>typedef void (*pvoid_void)(void);
__>void f1(void){}
__>void f2(void){}
__>void f3(void){}
__>void f4(void){}
__>void f5(void){}
__>static const pvoid_void map_f[]={f1,f2,f3,f4,f5};
__>void f(int i) { (*map_f[i])(); } // сразу переходим куда надо
__>
Думаю, будет еще хуже. Табличный переход в 100% случаев приводит к приостановке/перезагрузке конвейера процессора. Ведь адрес следующей инструкции процессор узнает в самый последний момент! — непосредственно перед переходом.
Здравствуйте, Алексей., Вы писали:
__>>void f(int i) { (*map_f[i])(); } // сразу переходим куда надо __>>[/c]
А>Думаю, будет еще хуже. Табличный переход в 100% случаев приводит к приостановке/перезагрузке конвейера процессора. Ведь адрес следующей инструкции процессор узнает в самый последний момент! — непосредственно перед переходом
нестрадайте ненужным перфекционизмом, те потери о которых вы говроите ничтожно малы на современных частотах, той разницы.которую вы добиваетесь от кода switch — никтоне заметит. Вы больше времени потратите на ненужную оптимизацию, чем на дело. Герб Саттер как-то сказал, что главный враг программиста — это попытка оптимизировать код на этапе разработки. так что это все есть фигня.
Здравствуйте, Алексей., Вы писали:
А>Здравствуйте, _nn_, Вы писали:
__>>Если условия последовательные то можно применить карту переходов что значительно эффективнее : __>>
__>>typedef void (*pvoid_void)(void);
__>>void f1(void){}
__>>void f2(void){}
__>>void f3(void){}
__>>void f4(void){}
__>>void f5(void){}
__>>static const pvoid_void map_f[]={f1,f2,f3,f4,f5};
__>>void f(int i) { (*map_f[i])(); } // сразу переходим куда надо
__>>
А>Думаю, будет еще хуже. Табличный переход в 100% случаев приводит к приостановке/перезагрузке конвейера процессора. Ведь адрес следующей инструкции процессор узнает в самый последний момент! — непосредственно перед переходом.
А так мы теряем такты на сравнении, ведь если окажется что нужен последний вариант мы проделаем все сравнения.
void f_sw(int i)
{
switch(i)
{
case 1: f1(); break;
case 2: f2(); break;
case 3: f3(); break;
case 4: f4(); break;
case 5: f5(); break;
//...
}
}
void f_map(int i)
{
(*map[i])();
}
f_sw(100); // 100 сравнений + 100 переходов
f_map(100); // получение адреса + вызов
VC7.1 придерживается другого мнения. Он часть switch-блока перевел на цепочки cmp/jump'ы (не уверен что все), а не на один jump по таблице. (В таблице 256-case'ов от 0 до 255).
Здравствуйте, Алексей., Вы писали:
А>Здравствуйте, _nn_, Вы писали:
__>>А так мы теряем такты на сравнении, ведь если окажется что нужен последний вариант мы проделаем все сравнения.
__>>
А>VC7.1 придерживается другого мнения. Он часть switch-блока перевел на цепочки cmp/jump'ы (не уверен что все), а не на один jump по таблице. (В таблице 256-case'ов от 0 до 255).
Это доказательсто того что лучше использовать карту перехода ?
Все же если есть последовательные значения и их много switch не выгодно применять, много писать, а скорость может быть хуже или идентична.
А если нет разницы зачем писать больше ?
Здравствуйте, Алексей., Вы писали:
А>Как выжать максимум скорости из switch-блока? А>Есть функция со switch-блоком с большим числом case'ов, которая сжирает 10-15% времени выполнения программы.
А>>VC7.1 придерживается другого мнения. Он часть switch-блока перевел на цепочки cmp/jump'ы (не уверен что все), а не на один jump по таблице. (В таблице 256-case'ов от 0 до 255). __>Это доказательсто того что лучше использовать карту перехода ?
Опечатка:
(В таблице 256-case'ов от 0 до 255).
имелось ввиду (В switch'е 256-case'ов от 0 до 255).
__>Все же если есть последовательные значения и их много switch не выгодно применять, много писать, а скорость может быть хуже или идентична. __>А если нет разницы зачем писать больше ?
Хм. Если приглядеться, то все переходы производятся по таблице (я был неправ). По неизвестным причинам для '/' сделано отдельное исключение (несмотря на то что case '/' присутствует). Впрочем, это из области необъяснимого.
Здравствуйте, bkat, Вы писали:
B>Здравствуйте, Алексей., Вы писали:
А>>Как выжать максимум скорости из switch-блока? А>>Есть функция со switch-блоком с большим числом case'ов, которая сжирает 10-15% времени выполнения программы.
B>А можно глянуть на этот switch-case блок?
case '0': // 0x30
case '1': // 0x31
case '2': // 0x32
case '3': // 0x33
case '4': // 0x34
case '5': // 0x35
case '6': // 0x36
case '7': // 0x37
case '8': // 0x38
case '9': // 0x39
return ...;
case '$':
case 'A': // 0x41
case 'B': // 0x42
case 'C': // 0x43
case 'D': // 0x44
case 'E': // 0x45
case 'F': // 0x46
case 'G': // 0x47
case 'H': // 0x48
case 'I': // 0x49
case 'J': // 0x4a
case 'K': // 0x4b
case 'L': // 0x4c
case 'M': // 0x4d
case 'N': // 0x4e
case 'O': // 0x4f
case 'P': // 0x50
case 'Q': // 0x51
case 'R': // 0x52
case 'S': // 0x53
case 'T': // 0x54
case 'U': // 0x55
case 'V': // 0x56
case 'W': // 0x57
case 'X': // 0x58
case 'Y': // 0x59
case 'Z': // 0x5a
case '_': // 0x5f
case 'a': // 0x61
case 'b': // 0x62
case 'c': // 0x63
case 'd': // 0x64
case 'e': // 0x65
case 'f': // 0x66
case 'g': // 0x67
case 'h': // 0x68
case 'i': // 0x69
case 'j': // 0x6a
case 'k': // 0x6b
case 'l': // 0x6c
case 'm': // 0x6d
case 'n': // 0x6e
case 'o': // 0x6f
case 'p': // 0x70
case 'q': // 0x71
case 'r': // 0x72
case 's': // 0x73
case 't': // 0x74
case 'u': // 0x75
case 'v': // 0x76
case 'w': // 0x77
case 'x': // 0x78
case 'y': // 0x79
case 'z': // 0x7a
{
}
case '\x01':
case '\x02':
case '\x03':
case '\x04':
case '\x05':
case '\x06':
case '\x07':
case '\x08':
case '\x0e':
case '\x0f':
case '\x10':
case '\x11':
case '\x12':
case '\x13':
case '\x14':
case '\x15':
case '\x16':
case '\x17':
case '\x18':
case '\x19':
case '\x1a':
case '\x1b':
case '\x1c':
case '\x1d':
case '\x1e':
case '\x1f':
case '\\': // 0x5c
case '`': // 0x60
case 0x7f:
case 0x80:
case 0x81:
case 0x82:
case 0x83:
case 0x84:
case 0x85:
case 0x86:
case 0x87:
case 0x88:
case 0x89:
case 0x8a:
case 0x8b:
case 0x8c:
case 0x8d:
case 0x8e:
case 0x8f:
case 0x90:
case 0x91:
case 0x92:
case 0x93:
case 0x94:
case 0x95:
case 0x96:
case 0x97:
case 0x98:
case 0x99:
case 0x9a:
case 0x9b:
case 0x9c:
case 0x9d:
case 0x9e:
case 0x9f:
case 0xa0:
case 0xa1:
case 0xa2:
case 0xa3:
case 0xa4:
case 0xa5:
case 0xa6:
case 0xa7:
case 0xa8:
case 0xa9:
case 0xaa:
case 0xab:
case 0xac:
case 0xad:
case 0xae:
case 0xaf:
case 0xb0:
case 0xb1:
case 0xb2:
case 0xb3:
case 0xb4:
case 0xb5:
case 0xb6:
case 0xb7:
case 0xb8:
case 0xb9:
case 0xba:
case 0xbb:
case 0xbc:
case 0xbd:
case 0xbe:
case 0xbf:
case 0xc0:
case 0xc1:
case 0xc2:
case 0xc3:
case 0xc4:
case 0xc5:
case 0xc6:
case 0xc7:
case 0xc8:
case 0xc9:
case 0xca:
case 0xcb:
case 0xcc:
case 0xcd:
case 0xce:
case 0xcf:
case 0xd0:
case 0xd1:
case 0xd2:
case 0xd3:
case 0xd4:
case 0xd5:
case 0xd6:
case 0xd7:
case 0xd8:
case 0xd9:
case 0xda:
case 0xdb:
case 0xdc:
case 0xdd:
case 0xde:
case 0xdf:
case 0xe0:
case 0xe1:
case 0xe2:
case 0xe3:
case 0xe4:
case 0xe5:
case 0xe6:
case 0xe7:
case 0xe8:
case 0xe9:
case 0xea:
case 0xeb:
case 0xec:
case 0xed:
case 0xee:
case 0xef:
case 0xf0:
case 0xf1:
case 0xf2:
case 0xf3:
case 0xf4:
case 0xf5:
case 0xf6:
case 0xf7:
case 0xf8:
case 0xf9:
case 0xfa:
case 0xfb:
case 0xfc:
case 0xfd:
case 0xfe:
case 0xff:
{
}
Здравствуйте, Алексей., Вы писали:
А>Здравствуйте, bkat, Вы писали:
B>>Здравствуйте, Алексей., Вы писали:
А>>>Как выжать максимум скорости из switch-блока? А>>>Есть функция со switch-блоком с большим числом case'ов, которая сжирает 10-15% времени выполнения программы.
B>>А можно глянуть на этот switch-case блок?
А>Cодержимое case-блоков вырезано:
А зря... Думаю оптимизировать стоит только содержимое этих блоков
или то, как эта фукнция используется.
Кстати, то, что функция сжирает 10-15% времени выполнения программы,
не означает, что именно сами переходы отнимают столько времени.
switch-case блок есть смысл изменить, но не для увеличения скорости,
а для улучшения читабельности кода.
Если ты все же будешь оптимизировать переходы,
то попробуй для начала сделать тест. Создай switch блок с 10-ю case
и другой с 255 (как у тебя) case.
Запусти цикл с миллиардом итераций и сравни оба switch-блока.
Сомневаюсь, что ты заметишь существенную разницу.
Здравствуйте, Алексей., Вы писали: А>Как выжать максимум скорости из switch-блока?
Никак. Этим должен заниматься компилятор. Если он не справляется — надо оптимизировать алгоритм, равно как и при любой другой оптимизации. В качестве таковой могу предложить заменить линейное ветвление иерархическим, log2 N сравнений at most.
if ( value < 128 )
{
if ( value < 64 )
{
...
}
else
{
...
}
}
else
{
if ( value < 128+64 )
{
...
}
else
{
...
}
}
Если ты ваяешь виртуальную машину, я бы рекомендовал посмотреть в сторону других подходов. В fido7.su.c-cpp это сейчас как раз обсуждают, почитай.
Здравствуйте, bkat, Вы писали:
B>А зря... Думаю оптимизировать стоит только содержимое этих блоков B>или то, как эта фукнция используется.
B>Кстати, то, что функция сжирает 10-15% времени выполнения программы, B>не означает, что именно сами переходы отнимают столько времени. B>switch-case блок есть смысл изменить, но не для увеличения скорости, B>а для улучшения читабельности кода.
B>Если ты все же будешь оптимизировать переходы, B>то попробуй для начала сделать тест. Создай switch блок с 10-ю case B>и другой с 255 (как у тебя) case. B>Запусти цикл с миллиардом итераций и сравни оба switch-блока. B>Сомневаюсь, что ты заметишь существенную разницу.
B>Резюмируя, не там ты ищешь свой bottleneck...
Собрал статистику по частоте case'ов. Видимо соптимизировать не удастся — получится только хуже.
Видимо тема исчерпана.
Здравствуйте, Eugene Kilachkoff, Вы писали:
EK>Здравствуйте, Алексей., Вы писали: А>>Как выжать максимум скорости из switch-блока? EK>Никак. Этим должен заниматься компилятор. Если он не справляется — надо оптимизировать алгоритм, равно как и при любой другой оптимизации. В качестве таковой могу предложить заменить линейное ветвление иерархическим, log2 N сравнений at most. EK>
What's interesting is that, based on my tests, I exceeded the
speed of C++'s switch-case.
...
vs. a corresponding perfect hash table. I got 6.6 secs (switch)
vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster
(i got 2.2) but still 4X slower than the perfect hash.
ME>What's interesting is that, based on my tests, I exceeded the
ME>speed of C++'s switch-case.
ME>...
ME>vs. a corresponding perfect hash table. I got 6.6 secs (switch)
ME>vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster
ME>(i got 2.2) but still 4X slower than the perfect hash.
ME>-- ME>Maxim Yegorushkin
Максим, речь идет о байте (или 8-битовом символе) со всеми его 256 состояниями.
Я всегда говорил, что в Си не хватает вычисляемого goto, как в том же Фортране или PL/I.
switch это конечно хорошо, но никто не гарантирует его производительности. Конечно, компилятор попытается соптимизировать его к сложности O(1), но никаких гарантий нет. А хочется именно гарантированной производительности. Вызов функции по указателю — вот единтсвенно возможное решение, которое, впрочем, тоже не всегда возможно.
Кстати, насколько я знаю, практически на всех современных процах косвенный вызов не сбивает конвейер. Вот вызов с двойной косвенностью (виртуальная функция) — уже сбивает. Поэтому "ручная" эмуляция виртуальных функций работает быстрее.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
