@Efrit23 янв 2013 в 04:01

Switch для строк в C++11

6 мин

98K

Программирование * C++ *

+50

Комментарии 52

@arabesc 23 янв 2013 в 05:02

так что под CASE мы её всё равно не загоним

Легко, через escape-последовательности. Например:

ullong const h1 = str_hash("\x03\x01", 2);
ullong const h2 = str_hash("\x01\x01\x01", 3);

Кстати, о коллизиях — эти строки дают одинаковый хэш.

@arabesc 23 янв 2013 в 05:10

Про хэш прошу прощения, поторопился, успел поиграться с кодом и сломать.

@arabesc 23 янв 2013 в 05:17

Переписал raise_128_to покороче и потерял множитель:

constexpr ullong raise_128_to(const uchar power)
{
    return 0x1ULL << 7*power;
}

@Efrit 23 янв 2013 в 05:29

Кстати, да — ведь при возведении 128 в степень и впрямь можно использовать битовую арифметику, хотя на результат это не повлияет. Я про это что-то не подумал, спасибо за уточнение. Надо будет файл обновить.

Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.

@SOLON7 23 янв 2013 в 06:58

Вообще звучит очень правильно использовать функцию хеширования.

До пустим возьмем строку 'FIBONACI_STRING_REPLACE' ( ее размер 24 байта если это только MBC строка). Ее нужно сравнить с многими другими строками как например с 'MACLIACI_STRING_REPLACE' итд. Правда одно дело когда строк всего пару для сравнения, другое дело когда количество строк переваливает за 10 тысяч.

Куда проще будет вычислить Хешкод (в итоге у нас будет 4 байта для типа INT). И сравнить просто числа размером по 4 байта. у нас получится примерно 5 кратное увеличение производительности.

Господа как Вы думаете стоит ли перевести или написать статью про внутренности Хеш таблицы и про Хеширование ??
Мне сама это тема интересена так как я сечас работаю над оптимизацией кода в проекте связаного с хешированием и хеш таблицами!!!

@Efrit 23 янв 2013 в 08:36

Конечно, пишите. Хорошие статьи про алгоритмы украшают Хабр.

@tyrotoxin 23 янв 2013 в 12:10

Только не стоит забывать про коллизии, ведь для 2 разных строк может быть один и тот-же хэш код. Описанный способ одназначно лучше, если (а) нет коллизий в изначальном наборе строк и (б) на входе в функцию приходят строки, у которых нет коллизий с существующим набором. Однако, даже если эти условия не выполняются, для отдельных случаев можно придумать хитрое решение и минимизировать вероятность коллизий :)

@zikher 23 янв 2013 в 07:15

конечно, понятно, что статья больше о constexpr и красоте кода, но для решения конкретной задачи лучше бы подошел perfect hash. А то ограничение на 10 символов как-то смущает.

@Efrit 23 янв 2013 в 07:23

Конечно, я рассматривал и perfect hash. С его применением ограничения вообще бы не чувствовались :)
Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
Хотя, конечно, функцию str_hash можно переделать на всё что угодно.

@zikher 23 янв 2013 в 07:40

Конечно, я рассматривал и perfect hash. Однако потом посчитал, что отсутствие коллизий важнее.

Вы что-то путаете. Perfect hash как раз коллизий не имеет. Его основная проблема — это то, что для создания конкретной функции необходимо иметь «на руках» весь начальный набор значений.

@Efrit 23 янв 2013 в 07:50

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

@jcmvbkbc 23 янв 2013 в 12:53

Да не придётся же. perfect hash как раз и генерирует эту функцию.

@Efrit 23 янв 2013 в 13:01

Но как Вы в этом случае будете реализовывать функцию подсчёта хэша, работающую во время компиляции?
Ведь аргументы макроса CASE могут встречаться в коде где угодно…

@jcmvbkbc 23 янв 2013 в 13:09

Функцию вам реализует gperf или другой инструмент типа него. Вот как собрать ему все кейсы одного свитча — это вопрос.
А, ну и кстати, с perfect hash возможны коллизии для строк не из первоначального набора.

@Efrit 23 янв 2013 в 13:14

gperf её реализовать сможет — но хочется переложить всю работу на компилятор, не прибегая к каким-либо сторонним средствам.

@jcmvbkbc 23 янв 2013 в 13:10

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

@antonyter 23 янв 2013 в 07:33

Если хэши двух различных строк совпадут, то программа может перепрыгнуть со switch на ложную case-ветку.

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

@dotsquid 23 янв 2013 в 07:45

Имелся ввиду хэш сравниваемой строки в самом switch'e (который вычисляется в рантайме) и хэш строки в одном из case'ов.

@Alexei_987 23 янв 2013 в 08:14

надо обновлять страницу перед отправкой :)

@mejedi 23 янв 2013 в 07:58

сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно

Обычно «кейс по строкам» попадает в те 80% кода программы, которые вобще не влияют на производительность. Исключения невероятно редки, для них придуманы утилиты вроде gperf (подбирает совершенную хеш-функцию для заданного набора строк).

Afaik сделать такое не привлекая сторонних тулзов в процесс компиляции, даже в C++ последней ревизии, невозможно.

@e_asphyx 23 янв 2013 в 08:40

Похожий механизм есть в glib (хоть он и не имеет отношения к C++), называется GQuark. В glib есть что-то типа глобальной статической строковой коллекции, состоящей из массива и хэш-таблицы. При переводе строки в GQuark, если эта операция делается впервые, строка дописывается в массив, полученный индекс заносится в хеш-таблицу, и возвращается этот же индекс. Сам по себе GQuark просто является синонимом int. Повторная попытка приведения той же строки к GQuark приведёт к получению того же индекса. Обратная же операция сводится к получению элемента массива по индексу.

switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.

@dima_mendeleev 23 янв 2013 в 10:00

Посмотрите тут, как можно static_assert, заменив его на throw, перенести в constexpr функцию. Тогда можно обойтись без макросов:

case hash("string"):

@Efrit 23 янв 2013 в 16:15

Спасибо за ссылку, весьма интересное решение. Хотя там не хэш ищется, а иная информация по строкам (также в compile-time).
Про макросы — главное, что они здесь безопасны.

@dima_mendeleev 23 янв 2013 в 16:43

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

@Efrit 24 янв 2013 в 10:12

Кстати, когда я экспериментировал с constexpr-функциями, я обнаружил, что constexpr-функции также могут иметь "..." (троеточие) в своей сигнатуре, как и «обычные» функции.
То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…

@dima_mendeleev 24 янв 2013 в 10:36

Ну можно и без трех точек через variadic templates.
Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.

@dima_mendeleev 24 янв 2013 в 10:44

А не перестанет ли функция, гуляющая по стеку, быть constexpr?

@Efrit 24 янв 2013 в 12:37

Ну лично у меня компилятор (GCC) на это не ругается — видимо, там какая-то хитрая отпимизация.

@X-Ray_3D 15 авг 2023 в 10:02

....
template <std::size_t N>
struct Hash {
    ullong value;
    bool ok;
    enum { size = N - 1 };
    constexpr Hash(char const (&str)[N])
        : value { str_hash(str,size) }
        , ok { str_is_correct(str) }
    {
        static_assert((size <= MAX_LEN), "CASE string length is greater than 9");
    };
};

} // namespace s_s

template <s_s::Hash H>
constexpr auto operator""_h()
{
    static_assert(H.ok, "CASE string contains wrong characters");
    return H.value;
}

....

case "april"_h:

Я тоже не люблю макросы и немного подшаманил https://godbolt.org/z/j8q6fafrY

@oleg1977 23 янв 2013 в 10:30

Если MAX_LEN=10, то есть 70 бит, то как они могут упаковаться в 64 бита?

@Efrit 23 янв 2013 в 12:48

Да, Вы правы, должно быть 9. Спасибо за уточнение. Перебил константу в файле, обновил статью.

@oleg1977 23 янв 2013 в 10:36

В юникоде русская А имеет код 0x041A, оба символа 0x04 и 0x1A — из первых 128, так что, этот символ все-таки пройдет?

@Efrit 23 янв 2013 в 10:58

Лично у меня не проходит, static_assert срабатывает; в диапазон 0-127 кастятся только ASCII-символы.

@Moonrise 23 янв 2013 в 13:13

0x04 и 0x1A это именно два символа. Не ASCII символы во всех кодировках будут иметь коды, большие 128. Например, в UTF-8 русская А (0x410, btw) кодируется как 0xC0 0x90.

@andreishe 23 янв 2013 в 17:33

В UTF-8 в символах, которые занимают больше одного байта, старший бит у первого байта всегда 0, а старший бит у всех последующих — всегда 1 (т.е. они заведомо будут больше или равны 128).

@Volfram 23 янв 2013 в 10:41

Важное замечание насчёт кодировок — Linux и Windows тут ни при чём, UTF-8 сейчас стандарт практически везде… кроме самого C++. Есть хорошее эмпирическое правило — не работать с юникодом в C++ без соответствующих библиотек вообще, слишком много подводных камней. Так что попытка скормить UTF-8 литерал куда попало абсолютно точно попадает под ошибочное использование.

@Efrit 23 янв 2013 в 13:19

Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка (хотя и Юникод нынешние версии винды, конечно, держат). Лично я все исходники сохраняю в UTF-8, даже если работаю под виндой — потом зато меньше сложностей с перекомпиляцией. А в диапазон 0-127 могут каститься только ASCII-символы, поскольку Юникод по этой часть полностью совместим с ASCII.

@StrangeAttractor 23 янв 2013 в 13:48

Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка

Чô?? В Windows NT (к коим, если вдруг кто не знает, относятся все современные версии Windows) Unicode используется с самой первой версии — Windows NT 3.1 (1993-й год) (начиная с Windows 2000 используется формат UTF-16, до 2000 — UCS-2). Когда я начинал пробовать Linux (во времена Windows NT 4 и 2000) в Linux ещё во всю использовалась KOI-8.

Существует заблуждение, что само слово «Unicode» означает «Unix code», на самом деле, на сколько мне известно, это не так.

@Efrit 23 янв 2013 в 13:53

Извиняюсь насчёт «исторически». Я имел в виду то, что по умолчанию Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает.
Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.

@StrangeAttractor 23 янв 2013 в 15:36

Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает

Проверил и был удивлён тем, что это, можно сказать, действительно так. Но это не Windows, а Notepad, в котором, видимо, просто забыли/забили это менять. Visual Studio 2012 (других версий нет под рукой проверить) сохраняет в UTF-8, Word перещёл на Unicode с версии не то 97, не то 2000. Полагаю блокнотом пользуются только истинные ценители, а во всех нормальных редакторах (например NotePad++, Sublime 2 и т.п.) кодировка по-умолчанию либо сразу человеческая, либо настраивается).

Вообще, в этих кодировках сам чёрт ногу сломит :)

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

@prograholic 23 янв 2013 в 14:00

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

int eval(const Expr& e)
{
    Match(e)
    {
        Case(const Value&  x) return x.value;
        Case(const Plus&   x) return eval(x.e1) + eval(x.e2);
        Case(const Minus&  x) return eval(x.e1) - eval(x.e2);
        Case(const Times&  y) return eval(y.e1) * eval(y.e2);
        Case(const Divide& z) return eval(z.e1) / eval(z.e2);
    }
    EndMatch
}

Или здесь

Причем сами авторы позиционируют данную библиотеку, как максимально быструю и эффективную.

@dima_mendeleev 23 янв 2013 в 16:49

Ага=)
Пишут, что догоняет Хаксел и Окамл :-D

@Efrit 23 янв 2013 в 17:30

А она является кросс-платформенной?

@prograholic 23 янв 2013 в 23:12

Я собирал только под linux, но насколько я понял, поддерживается несколько платформ

@ncix 23 янв 2013 в 19:38

Из практики, свитчи имеют тенденцию превращаться со временем в лапшу и в конце концов, как правило, заменяются подходящей конструкцией ООП. Поэтому подумайте сразу — будет ли расти количество case'ов со временем, и сложность внутренней логики каждого case'а.

@happybyte 23 янв 2013 в 23:30

Здесь дело не в этом — отпишусь ниже немного.

@happybyte 23 янв 2013 в 23:44

Прежде всего — чтобы это был полноценный switch, а не его «эмуляция» путём скрытия if-операторов и функций для сравнения строк внутри макросов, поскольку сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно.

Пройдусь по пунктам.

То, что это реальный switch/case это хорошо, но есть ряд нюансов.

switch стоит использовать не из-за удобства, а из-за быстродействия.

Ветвление со сравнениями (if) плохо влияет на быстродействие.

Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.

Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.

Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.

Кстати, ради интереса — смотрели, какой машинный код получается на выходе?

@Efrit 24 янв 2013 в 02:42

Согласен со всем. У меня в рантайме происходит лишь однократное вычисление хэша для switch, так что считал, что с производительностью всё должно быть в порядке… Хотя насчёт «более одного байта» я не был в курсе — а у меня явно больше.
Машинный код не смотрел, но попробую.

@X-Ray_3D 15 авг 2023 в 10:12

https://godbolt.org/z/j8q6fafrY

@happybyte 23 янв 2013 в 23:52

Когда строки заранее известны, то вместо хэша более быстрым может быть конечный автомат реализованный на том же switch, например (из старого кода):

/* Jan-Dec to 1-12 */
unsigned long time_parse_month(unsigned char *b)
{
	switch(*b)
	{
		case 'j':
		case 'J':
			if((b[1]=='a')||(b[1]=='A'))
			{
				return(1);
			}
			if((b[2]=='n')||(b[2]=='N'))
			{
				return(6);
			}
			return(7);
		case 'f':
		case 'F':
			return(2);
		case 'm':
		case 'M':
			if((b[2]=='r')||(b[2]=='R'))
			{
				return(3);
			}
			return(5);
		case 'a':
		case 'A':
			if((b[1]=='p')||(b[1]=='P'))
			{
				return(4);
			}
			return(8);
		case 's':
		case 'S':
			return(9);
		case 'o':
		case 'O':
			return(10);
		case 'n':
		case 'N':
			return(11);
		case 'd':
		case 'D':
			return(12);
		default:
			break;
	}
	return(0);
}

У нас это для парсинга логов использовалось — вариант с if внутри switch вышел быстрее на практике.

@e_asphyx 24 янв 2013 в 11:06

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

@tyrotoxin 27 янв 2013 в 11:35

На самом деле тут много факторов, которые влияют на производительность решения. Например, такой код для 10000 заранее известных строк будет занимать очень много байтов. Такое раздутие может привести только к деградации производительности, из-за того что весь код может не содержаться в кэше процессора, и ему постоянно прийдётся подгружать его из памяти. В таком случае скорость подсчёта хэша и использование хэш-таблицы могут оказаться быстрее. Это только один из сценариев, их может быть уйма. И точно сказать что один подход всегда лучше другого — невозможно. Нужно отталкиваться от конкретного сценария.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий