LINUX.ORG.RU

[c][быдлокод] ресурсоёмкость операторов ветвления

 ,


0

1

У меня такой вопрос... есть pic18, он работает на перекодировке символьных сообщений. Сообщения приходят к нему со скоростью 4800 бод, и в соответствии с определённой логической схемой символы надо переставить местами и некоторые - заменить. У меня есть около 1000 тактов на одну посылку, что совсем не много. Ранее этой операцией занималась dll-ка в неправославной винде, теперь надо сделать кросплатформенное (вот здесь «при чём» Linux) решение, наиболее универсальным вариантом является аппаратный конвертер.

Вопрос у меня собственно следующий. Я реализую посимвольный разбор сообщения с помощью if и switch, какая разница в транслировании исходного текста в машинный код при использовании этих конструкций? Что лучше использовать, нагромождение if-ов или switch? И где можно почитать про трансляцию команд в машинный код и написание «быстрого и надёжного» кода?

★★★★

написать на ассемблере, например

switch не медленнее, для него возможны оптимизации типа бинарного поиска или таблицы переходов

note173 ★★★★★
()

Если компилятор не дурак - switch должен быть быстрее, т.к. можно что-то типа сортировки вариантов использовать(деревья там всякие бинарные).

vbnm
()

Компилятор - проприетарный MCC18, sdcc брать опасаюсь, там вроде как проблемы с оптимизацией кода. А бинарные деревья - это мысль. Очень хорошая кстати мысль. Я конечно предыдущий вариант (который в dll-ине до меня писался, на 100500 if-ов) разобрал на 5-7 уровневое дерево, но оно совсем не бинарное.

aiqu6Ait ★★★★
() автор топика

гдето тут в этом форуме натыкался на одно сообщение - в котором автор был весьма удивлен - когда оказалось что свитчь был быстрее чем переход по указателю из таблици на нужную функцию
но там был обычьный комп и gcc
а обычьный проц то в себе кучу оптимизаций несет

что врятли есть в простом пике
если ты хочеш точно узнать - то надо получить асемблерный код того и другого решения и подсчитать

а так - имхо тут лучше всего наверняка пойдет хеш + несколько свитчей

ну типа - по мере анализа символа за сиволом - включаеться выключаеться несколько битов признаков
вот и ( эти быти признаков + след символ ) % 16 = хешу
вот и получили 16 вариантый хеш - а по нему - переходить на функцию которая будет анализировать дальше

ae1234 ★★
()
Ответ на: комментарий от ae1234

>гдето тут в этом форуме натыкался на одно сообщение - в котором автор был весьма удивлен - когда оказалось что свитчь был быстрее чем переход по указателю из таблици на нужную функцию

На pic переход по указателю (computed goto) займет пару тактов, только нужно ассемблер знать, который ТС не осилил.

anonymous
()

Написать два теста (так и так) и сравнить. Все эти рассуждения хороши, но жизнь оказывается куда прихотливее;-)

На обычном проце результат будет зависеть не тока от реализации, но и от самих сообщений - если сист. предсказаний «пристреляется» (все сообщения одинаковы), то на if-aх вообще не должно бы быть расходов, наск я понимаю. С Вашей железякой - ХЗ...

AIv ★★★★★
()

Нужно попробовать оба варианта и посмотреть выхлоп дизассемблера. Естественно, if-ы нужно организовать древовидным образом.

У меня есть около 1000 тактов на одну посылку


Сколько байт в посылке?

Manhunt ★★★★★
()

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

Вообще, if на i386 как правило транслируется в инструкции вида cmp/test + jz/jg/jl/..., а switch - либо так же, как серия if, либо в cmp + косвенный jmp, что в среднем быстрее.

Если и использовать кучу if-ов, то наиболее вероятный вариант следует располагать вначале, а наименее вероятный - в конце, чтобы количество пройденных сравнений для вероятного варианта было минимальным.

amomymous ★★★
()
Ответ на: комментарий от Manhunt

12-14 на входе и 30 на выходе. ветвление уже древовидное. расположил сообщения в порядке статистически наиболее приемлемом (статистика по приходу сообщений есть). В общем буду пробовать и считать такты. Всем спасибо.

aiqu6Ait ★★★★
() автор топика
Ответ на: комментарий от aiqu6Ait

> 12-14 на входе

То есть по 60 тактов на байт. Совсем впритык.

расположил сообщения в порядке статистически наиболее приемлемом


Оценивать нужно наихудший для твоего кода случай, а не среднестатистический.

Manhunt ★★★★★
()
Ответ на: комментарий от aiqu6Ait

Смотря, что называть «проектированием ПО» :)

По алгоритмам - Шень «Программирование: теоремы и задачи» ftp://ftp.mccme.ru/users/shen/progbook2/progbookpdf.zip

По высокоуровневой архитектуре - всякие разные учебники по UML и по паттернам. Ничего конкретного советовать не буду, тк всё что прочитал - во время чтения вызывало приступы рвоты.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

А если про низкий уровень, то в свое время доставила книжка Пустоварова про ассемблер (точное название сейчас не вспомню). Правда, там жестка привязка к x86

Manhunt ★★★★★
()
Ответ на: комментарий от yoghurt

В микроконтроллерах из-за малого объема памяти компилятор может не оптимизировать switch.

anonymous
()

> Что лучше использовать, нагромождение if-ов или switch?

Что читабельней то и использовать, т.к. полагаться на то, что сгенерится именно то что вам нужно в общем случае нельзя. Рядом можно расположить версию оптимизированную под конкретный компилятор и конкретные настройки.

И где можно почитать про трансляцию команд в машинный код

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

и написание «быстрого и надёжного» кода?

Быстрый код это к вопроса оптимизации и в первую очередь высокоуровневой оптимизации.

anonymous
()
Ответ на: комментарий от vbnm

> Если компилятор не дурак

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

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