Здравствуйте, Алексей., Вы писали:
А>>>Как выжать максимум скорости из switch-блока?
EK>>Никак. Этим должен заниматься компилятор. Если он не справляется — надо оптимизировать алгоритм, равно как и при любой другой оптимизации. В качестве таковой могу предложить заменить линейное ветвление иерархическим, log2 N сравнений at most.
А>Это понятно. Цепочка if'ов должна строиться с учетои вероятностей каждого case'а, а также с учетом "эффекта памяти" BTB-таблиц процесора.
[хитро прищурившись] А какого менно процессора ?
Еще раз, медленно и печально: оптимизацией под железо должен заниматься компилятор. Если где-то что-то тормозит, меняй алгоритм. Если и это не помогает, начинай выжимать такты. В твоем свитче средняя длина пробега по нему — 128, это если априори считать все символы поступающие на вход равновероятными. Замена свитча на иерархию if/else — дает восемь сравнений _постоянно_. Это ускорение в 16-32 раза, не считая того что длинные цепочки сравнений попросту трэшат BTB.
Можно оптимизировать дерево, скажем, выбирая в качестве точки ветвления медиану распределения (опционально другие стат. характеристики) каждого поддиапазона входных данных. Надо только отдавать себе отчет в том, что бесплатно ничего не достается, и укорочение пути в одной части множества значений (более вероятной), компенсируется удлинением в другой (менее вероятной). Ты уверен, что у тебя есть априорная статистика о входных данных ?

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

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

EK>[хитро прищурившись] А какого менно процессора ?
Имелся ввиду Pentium 4.

EK>Еще раз, медленно и печально: оптимизацией под железо должен заниматься компилятор. Если где-то что-то тормозит, меняй алгоритм. Если и это не помогает, начинай выжимать такты. В твоем свитче средняя длина пробега по нему — 128, это если априори считать все символы поступающие на вход равновероятными. Замена свитча на иерархию if/else — дает восемь сравнений _постоянно_. Это ускорение в 16-32 раза, не считая того что длинные цепочки сравнений попросту трэшат BTB.
EK>Можно оптимизировать дерево, скажем, выбирая в качестве точки ветвления медиану распределения (опционально другие стат. характеристики) каждого поддиапазона входных данных. Надо только отдавать себе отчет в том, что бесплатно ничего не достается, и укорочение пути в одной части множества значений (более вероятной), компенсируется удлинением в другой (менее вероятной). Ты уверен, что у тебя есть априорная статистика о входных данных ?
Априорной статистики нет. Но можно собрать достаточно большую выборку данных.
В целом, я уже убедился что в моем конкретном случае замена switch-блока на цепочку if'ов приведет к ухудшению производительности. Число перезагрузок конвейера увеличится с 1 до 3-4.

EK>Еще такой коварный вопрос: где окажется твоя оптимизация, если в следующей ревизии процессора интел поменяет алгоритм BTB ? Впрочем, если хочешь побаловаться ковырянием в асме, то вот это выдается яндексом второй ссылкой по запросу "оптимизация BTB".
Можно сделать оптимизацию под новый процессор. За ссылку отдельное спасибо.

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

EK>Если ты ваяешь виртуальную машину, я бы рекомендовал посмотреть в сторону других подходов. В fido7.su.c-cpp это сейчас как раз обсуждают, почитай.

А можно кратко сюда запостить?

Здравствуйте, stalcer, Вы писали:
EK>>Если ты ваяешь виртуальную машину, я бы рекомендовал посмотреть в сторону других подходов. В fido7.su.c-cpp это сейчас как раз обсуждают, почитай.
S>А можно кратко сюда запостить?
Ну, ссылка вот. А так, если написать туда пару недель назад, можно было бы спровоцировать народ на дальнейшее обсуждение. Ну, а тема теперь заглохла сама собой.