Мечты по поводу switch

https://github.com/solodon4/Mach7

gperf, re2c

Имеется массив строк, и пока бежим по строке, в зависимости от текущей, дергается какой-нибудь метод класса

С радостью выслушаю гуру.

Сделай map.

да я решил как хешмап <string, enum>

можно хеш посчитать, и по хешу уже свич пускать

А можно std::unordered_map<std::string, std::function> сделать уже давно было.

Смысл switch не столько в сахаре для каскадных if, сколько в возможности заменить n сравнений таблицей переходов, в которой либо индексировать за константное время, либо делать бинарный поиск за log(n). Для не-целочисленных типов такую таблицу не сделать, а значит switch будет просто сахаром, причем поощряющий неоптимальный код - для тех же строк эффективнее делать вначале поиск в std::unordered_map<std::string, my_string_enum_t> и потом свитч по энуму, получая log(n) сравнений вместо n.

Вообще интересно как это в C# или Java реализовано, не простым же перебором?

хм, оборачивают метод класса в std::function? интересно-интересно, спасибо за наводку.

log(n) сравнений вместо n.

Точнее константу в лучшем случае вместо n. log(n) был бы с std::map.

ну тогда давайте введём, к примеру, ограничение, что для классов, чтобы по ним свич прыгал, должна быть определена операция hash(), чтобы сразу прыгать. ну или operator< определять, чтобы могли бинпоиск устроить. Я согласен на такое.

Насчёт джавы не знаю - пойду гугл крутить

я это всё к тому, что зачем мне это руками писать? пусть свич всё это под капотом делает.

Вот о свиче в Java : https://habrahabr.ru/post/174065/

Потому, что you don't pay for what you don't use. Комитет не пойдет на добавление неясных и неоптимальных сущностей, невидимых для пользователя, с непонятными требованиями к памяти, производительности и неясным временем жизни только ради сахарка.

Зачем памятью вручную управлять? Пусть GC все это под капотом делает.

Если нужен сахар и производительность не критична - используй Java и подобные и не парься. Если используешь С++, то будь готов к тому, что почти абстракции zero cost, и что-то надо писать руками, или привлекать нетривиальные решения, вроде http://arcticinteractive.com/2009/04/18/compile-time-string-hashing-boost-mpl/ .

так тут это правило и не нарушается же : мы и не будем платить, что мы не используем. Тут всё открыто : если юзаем switch для интов и енумов, то пусть работает старый switch, иначе же пусть работает новый вариант. Плюсы : удобство. Минусы : нужно будет для своих типов определять hash()\operator< (это смотря что в середину впихнут, скорее всего unordered, поэтому hash), погромисту придётся выучить, что свич так себя ведёт. Нужный свич всё равно будет выбираться на этапе компиляции, так что всё вроде чисто получается.

Смысл switch не столько в сахаре для каскадных if, сколько в возможности заменить n сравнений таблицей переходов, в которой либо индексировать за константное время, либо делать бинарный поиск за log(n).

Нет такого смысла, как будет положен switch в коде зависит от компилятора. Сейчас if'ы с int и switch компиляторы раскроют примерно одинаково. В обычном if нельзя только требовать обработки всех значений из enum, это единственная фича switch на текущий день.

для тех же строк эффективнее делать вначале поиск в std::unordered_map<std::string, my_string_enum_t> и потом свитч по энуму, получая log(n) сравнений вместо n.

С чего это? unordered_map не очень оптитмальный контейнер для такой задачи. Для строк можно сделать много чего в зависимости от их кол-ва и содержания с точки зрения оптимальности - от простого перебора по списку и до специальных деревьев и хешов, что в общем то является примерно такими же таблицами. Проблема в том, что c++ не знает что такое строки потому и в switch с ними ничего сделать нельзя.

Всё что угодно, хоть методы класса, хоть лямбды.

спасибо за ссылку, интересно.

ну не кидайтесь в крайности. Да, я как и многие другие, против GC в крестах по умолчанию. НО! Если бы была возможность его подключения аля import gc; gc.enabled(); (это утопически, но всё же), то почему бы и нет? Да, сложно это всё. Но почему бы и нет?

Сейчас if'ы с int и switch компиляторы раскроют примерно одинаково

Согласен, я имел ввиду исторические причины, по которым switch был изначально добавлен.

Для строк можно сделать много чего
Проблема в том, что c++ не знает что такое строки потому и в switch с ними ничего сделать нельзя.

Дело не столько в том, что С++ не знает, что такое строки, сколько в том, что в каждом конкретном юзкейсе будут оптимальны различные подходы, о чем может знать только программист.

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

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

нет-нет, лично мне GC совсем не нужен и как-то пока не возникала прям уж дикая потребность в нём. Да, удобно это, за памятью не следить, спору нет. Но мне он не нужен.

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

А про всякие Java и питоны я знаю

Согласитесь, так и просится switch

Как по мне, так просится объект, в который засовываем функции-предикаты и скармливаем ему массив. Он последовательно применяет предикаты на строке и, если предикат сработал, вызывает связанный с предикатом обработчик. И не надо трогать switch.

В С++ отсутствие выбора лучше, серьезно. Любое потенциальное «подковерное» решение поднимает кучу вопросов, например, когда и как аллоцировать/освобождать хэштаблицу? Или вот решение из Java что ты привел с хабра, без хэш-таблиц, но предполагает существование строк-паттернов в каком-то виде для сравнения. Получается, надо либо каждый раз при заходе в контекст switch неявно создавать на стеке множество объектов std::string, которые в свою очередь будут аллоцировать свои хранилища на куче, либо просто держать их созданными в куче все время работы программы, при том что в общем случае память - ограниченный ресурс. Все это можно так или иначе решить, конечно, но результат получится хуже ручной реализации в большинстве случаев.

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

Сейчас мало кто может сделать больее оптимальный asm код чем делает компилятор. Задача создания оптимальной константной структуры поиска по заранее определённому набору примерно такого же плана. Даже мало кто осилит оптимально развернуть конкретный switch.

Если это будет стандартизировано, то всё ок будет. Только это должно быть везде описано четко, как это работает. И реализовано одинаково. А вот как оно уже всё будет, пусть дядьки из комитета думают, всяко они умнее меня :) А отсутствие выбора это пожалуй к питонистам. ЕМНИП у них в Дзене что-то есть об этом даже

Просвятите, в чём проблема использовать свич для других типов

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

Нужен матчинг по строкам - делай map, или просто if else if

if else if - уродливо. Тут тред о том, что пусть switch сам делает map, если нужно. А мы под его требования, если надо, подстроим класс. А лишняя или нет, это как уже посмотреть.

Ну как бы ни хотелось, комитет на это не пойдет. Они скорее полноценный match запилят, где-нибудь к С++26.

А отсутствие выбора это пожалуй к питонистам.

Имелось ввиду отсутствие выбора строк switch-ем. Наличие некой универсальной реализации switch по строкам как раз ограничивает выбор.

if else if - уродливо.

Наоборот же, if более компактен по записи, без мусорных berak и без проблем с лишними отступами. swith крайне неудачная синстаксическая конструкция в c/c++

Согласен, я имел ввиду исторические причины, по которым switch был изначально добавлен.

привет идиоту который написал

Сейчас if'ы с int и switch компиляторы раскроют примерно одинаково

даже питон и тот их транслирует по разному(если численные)

но чисто почему так,не потому что «c++ не знает что такое строки потому и в switch» а потму что:

операция «сравнения» самая медленная операция для процессора
поэтому и придумывают упрощения
помещая в оператор «IF» математическую формулу без сравнения дающую true/false на выходе
либо делая условия сравнения-именами функций и произойдет сразу переход к нужной ветви без самого сравнения,как goto
либо этот самый switch-который по сути являлся быстрым «if» для цифр,ибо в бинарной логике/на всех процессорах операция if(55==66) выполняется в несколько десятков раз дольше чем switch(55){...44...55...66....}

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

еще один идиот

Наоборот же, if более компактен по записи, без мусорных berak и без проблем с лишними отступами. swith крайне неудачная синстаксическая конструкция в c/c++

чтото сложнее блокнота кодил а?

покажи мне хоть ОДИН проект,вообще любой «большой» не использующий ОПТИМИЗАЦИЮ

ибо твое заявление равносильно-«оптимизируют только идиоты»

QT-использует switch,GTK также,драйвера интеля-да там просто каждый сантиметр if-ов заменен свитчами,также как и в llvm....

современных калькуляторов даже с 8 ядрами не хватит чтоб обработать мусорный код с ифами на каждый чих

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

до объектного программирования 99% текущих «программистов» как до луны и дальше

жду переизобретения «ООП» для жабоскрипта в ближайшие годы и очередную риволюцию

«о боже это так свежо и гениально»-будут вопить востроженные кодеры которым показали что такое объект в 21 веке

...и будут сидеть никому не нужные си-кодеры из 90-х и убиваться фейсепальмом

Переключатель для не-целых был полвека назад в PL/1. В более поздних языках оказался невостребованным (до появления C# и Java7, разумеется).

А вообще, на хабре публиковался велосипед, сделанный на C++11.

Сейчас if'ы с int и switch компиляторы раскроют примерно одинаково.

Хоть и согласился, но решил проверить, оказалось ты не прав: http://goo.gl/uXYi3L . «Короткий» switch заменяется индексацией таблицы, «длинный» свитч заменяется бинарным поиском, а каскад if остается линейным сравнением, даже для простейшего случая с -O3.

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

Что интересно, clang, в отличие от gcc, понимает, что побочных эффектов при сравнении интов нет, и приводит таки каскадные if к коду, эквивалентному switch, в обоих случаях - http://goo.gl/NSSX7M .

Тут есть и обратная сторона медали. Программист может свои if-ы не от балды расставлять, а в таком порядке, в котором ему кажется что будет оптимальней. Например первый if (a==1) return 22; из примера может стоять первым по причине того, что по мнению программиста это первое условие с большей вероятностью может сработать, т.е значение переменной a, передаваемое в функцию, в 99% случаев будет равнятся именно единице, а не чему-то другому, и такая самодеятельность компилятора, когда он этот код переводит в какие-то непонятные деревья, может все испортить.

Другой интересный пример http://goo.gl/2p8MfN - компилятор clang тут делает очень глупую вещь - два раза cmp вместо очевидного решения:

        cmpl    $100, %edi
        jg      a1
        jne     a2
        jmp     a3

а нет никакой пометки для компила, что мол «не оптимизируй данный участок кода, а переведи в ассемблер ровно то, что здесь написал погромист»?

https://stackoverflow.com/questions/2219829/how-to-prevent-gcc-optimizing-som... в GCC такое есть. Не знаю, работает ли оно в шланге. Может быть можно отрубить какие-то специфические оптимизации, которые именно за оптимизацию этих if-ов отвечают. Точно сказат не могу

В GCC еще есть __builtin_expect https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html которая в Linux ядре завернута как макросы likely(x) unlikely(x) http://lxr.free-electrons.com/source/include/linux/compiler.h?v=3.2#L114

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

Если используешь С++, то будь готов к тому, что почти абстракции zero cost

Вот в расте, который тоже объявляют zero-cost, не то, что свитч, а аж целый паттерн матчинг сделали. Врут?

тоже объявляют zero-cost

[citation needed]

[citation needed]

Какая цитата требуется? Написанного на главной странице языка недостаточно?

Действительно, еще и первым пунктом, опрометчиво с их стороны.

В C# у любого Object есть функция int GetHashCode() или как-то похоже называется. Суть в том, что ты определяешь правило хеширования твоего объекта в int и по нему дальше идёт работа с теми же switch. как-то так

Просвятите, в чём проблема использовать свич для других типов, если для них определена операция operator==() ?

Ты вообще понимаешь, что такое switch? Внутри это или ДЕРЕВО if-ов (а не цепочка, как ты посмел подумать), так что нужно как минимум еще и порядок определить, operator<() и operator>(), или, что более вероятно для хоть немного больших switch, вообще jump table, что предполагает возможность приведения к компактной целочисленной форме. Что, будешь perfect hash функцию для строк выводить, да?

Сейчас там есть shared_ptr и unique_ptr, это почти то же самое. Но возможность выстрелить в ногу там не отключена.

если у меня посчитан хеш для каждого обьекта, то operator<() нам не нужен ведь. Я понимаю это как хеш-таблицу. То есть нам нужно, чтобы брался хеш. И как эта хеш-таблица будет работать : берём хеш от обьекта, если такого хеша нет - уходим из свича, если есть такой только 1 - прыгаем в нужную ветку. Если несколько (это вдруг наш хеш коллизии дал) - запустим проверку через operator==(), который мы и определим для нашего обьекта.

Perfect hash не будем, а просто будем так разруливать коллизии. Да, их может быть много, но тут можно поиграться с хеш-функцией. Но всё равно, они могут быть и замедлять работу. Но прогер будет предупреждён об этом.

Или я какую-то проблему в реализации упустил?

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