LINUX.ORG.RU

Непонятная ошибка хеширования string_view

 ,


0

2

Пытаюсь сделать простенький парсер входных данных из string_view, разбирая токены через хеш-функцию:

#include <string_view>
#include <format>
#include <iostream>
#include <ranges>

/******************************************************************************/
inline constexpr size_t _hash (const char *str, size_t n=0) {
	// FNV-1a
	size_t res{0xcbf29ce484222325}, prime{0x00000100000001b3};
//	                  vvvvvvvvvvvvvvv здесь была ошибка
//	for (size_t i{0}; i < n or str[i]; ++i) {
	for (size_t i{0}; (i < n) or (n == 0 and str[i]); ++i) { // *fixed* FTGJ
		res = res ^ str[i];
		res = res * prime;
	}
	return res;
}

inline constexpr size_t operator ""_hash (const char *str, size_t n) {
	return _hash (str, n);
};

inline constexpr size_t _hash (const std::string_view &strv) {
	return _hash (strv.data(), strv.size());
};
auto to_string_view = [] (auto &&r) -> std::string_view {
	return std::string_view(&*r.begin(), std::ranges::distance(r));
};

auto not_empty = [](auto x) -> bool {
	return not x.empty();
};
void parse_key_flags(std::string_view input) {

	std::cout<<std::format("\"TOKEN\"_hash = {}\n", "TOKEN"_hash);

	for (auto entry : input
	                | std::views::split(' ')
	                | std::views::filter(not_empty)
	                
	) {
		
		auto row = entry | std::views::split(':')
		                 | std::views::filter(not_empty)
		                 | std::views::transform(to_string_view);
		
		auto key = row.front();
		std::cout<<std::format("key = \"{}\", tokens:\n", key);

		for (auto flag : row
		               | std::views::drop(1)
		               | std::views::transform(to_string_view)
		) {
			std::cout<<std::format("\t\"{}\" (hash = {})",flag, _hash(flag));
			switch (_hash(flag)) {
				default:
					std::cout<<" -> [FAIL]\n";
					continue;
				case "TOKEN"_hash:
					std::cout<<" -> [TOKEN]\n";
			}
		}
	}
}

Пытаюсь парсить строку

int main() {
	std::string_view input = "KEY1:TOKEN KEY2:TOKEN:FAIL";
	parse_key_flags(input);

}
И получаю ерунду
"TOKEN"_hash = 15101299456084321266 // ok
key = "KEY1", tokens:
	"TOKEN" (hash = 10353157926286166668) -> [FAIL] // WAT?
key = "KEY2", tokens:
	"TOKEN" (hash = 5196937941191725884) -> [FAIL] // WUT!?
	"FAIL" (hash = 3215402482899151853) -> [FAIL]
В чём тут дело?

★★★★★

Последнее исправление: thunar (всего исправлений: 2)
Ответ на: комментарий от thunar

Твоя функция хеша читает за пределами string_view:

for (size_t i{0}; i < n or str[i]; ++i) {
                        ^^^^^^^^^

Потому что string_view у тебя якобы TOKEN, а на самом деле он ссылкается на строку

KEY1:TOKEN KEY2:TOKEN:FAIL
     ^^^^^
И при хешировании она забирает все
KEY1:TOKEN KEY2:TOKEN:FAIL
     ^^^^^^^^^^^^^^^^^^^^^

MOPKOBKA ★★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

Тфу ты, слона в комнате я-то и проглядел! Добавлял эту проверку давным-давно что бы c-строки читать, но ни разу не понадобилось. Вот так тогда получается: i < n or (n==0 and str[i]!='\0')

thunar ★★★★★
() автор топика
Последнее исправление: thunar (всего исправлений: 1)
Ответ на: комментарий от thunar

да — ИЛИ нужно заменить на И для корректности проверки. Ну или вообще выбросить проверку на «терминатор» — да и вообще считаю следует отказаться от перегрузки от указателя и размера — таковое уже используется в std::string_view

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

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

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

тут могу предложить такой вариант хэша

Яркий пример выпендрёжа и переусложнения кода на пустом месте. Лучи любви от тех кто это будет вынужден поддерживать - практически гарантированы.

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

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

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

а в чём выпендрёж то?

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

bugfixer ★★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

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

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

или возможно ты из тех лиц, которые считают что си может быть производительнее чем с++?

И что самое главное - если это развернётся в столь же эффективный асм авторам компилятора можно будет поаплодировать.

как минимум не хуже... поскольку тоже самое...

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

ну и да — можешь конечно вообще кодировать всё снуля — без переиспользования кода — зачем тебе лишние функции, составленные ранее — делай весь код в main сразу...

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

или возможно ты из тех лиц, которые считают что си может быть производительнее чем с++?

Я из тех кто уже давно наигрался и ценит прежде всего простоту.

как минимум не хуже… поскольку тоже самое…

Щаз, ага.

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

можешь конечно вообще кодировать всё снуля

Разберусь.

без переиспользования кода

Дык, нет там переиспользования. Есть абсолютно неоправданный code-bloat и показушничество.

зачем тебе лишние функции, составленные ранее — делай весь код в main сразу…

Вы только не нервничайте так. И извините что не подаю ниц перед вашим умением крестиком вышивать.

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

Щаз, ага.

эмм... та функция с явным циклом енто и есть фолд... (ну прям почти построчно-дословно в реализации может быть — как минимум на cppreference предоставлен возможный вариант именно такой — ну и там я даже хз что еще нужно или можно придумать...)

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

Вы только не нервничайте так.

дак чож тут нервничать то — видно же, что ты не разбираешься попросту в языке (либе) раз такое высказываешь — конечно дело-то твоё, но вещаешь ты это так, будто это объективное что-то... других путаешь.

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 1)
Ответ на: комментарий от safocl

видно же — что ты не разбираешься попросту в языке (либе)

К счастью, мнение по поводу моих скилов меня интересует исключительно от моего начальства (в большей степени) и коллег (в меньшей степени). Но это всё лирика.

но вещаешь ты это так, будто это объективное

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

bugfixer ★★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Повод задуматься

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

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

ни одного фолда

ну если стандарт c++ ниже 20ого — то не удивительно — однако так же удивительно и отсутствие как выше указал std::reduce (std::accumulate) (и других стандартных алгоритмов).

ну и скорее всего можно иметь уверенность, что более 30-50% кода можно сократить только на применении стандартных алгоритмов вместо дублирования кода этих же алгоритмов.

а так же вообще порицательно предоставлять в рамках «объективного довода» исполнение своей какой то кодовой базы — поскольку нет доказательства что она именно сделана лучшим образом и никак иначе, как минимум для иных лиц, её лучше не сделать.

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 3)

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

на си прекрасно пишутся и непростенькие парсеры. он для того и создан.

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

база кодовая без использования std::reduce (std::accumulate), с использованием вместо этого явных циклов — ну такое себе — будешь в ней разбираться очень долго и уныло

Циклы завёрнутые в фолды и “accumulate / reduce” и обмазанные сверху лямбдами простоты не добавляют, вот вообще никак.

а так же вообще порицательно

Короче, я пошёл напрямую к источнику и обсудил это с коллегой являющимся по совместительству комитетчиком и довольно активным контрибьютором в gcc / boost. Как и ожидалось, по его словам нет ни одной причины использовать фолды + лямбды там где range-based for-loops хватает. Это никогда (подчеркну - никогда) не приводит к более быстрому асму, а зачастую - так вообще замедляет. И даже если вам повезло и код не замедлился, как минимум вы нарываетесь на debug-info bloat из-за дополнительных типов сгенерированных для лямбд. И чем больше проект тем более критично всё это становится. И это совсем не тот стиль который эти люди пытаются запромоутить среди app-level devs. И это всё на поверхности, мы ещё даже не начали обсуждать подводные камни связанные с багами конкретных версий конкретных компиляторов. Так что мой вам бесплатный совет: будьте проще, и не создавайте себе проблем на пустом месте - их и без того хватает.

bugfixer ★★★★★
()
Последнее исправление: bugfixer (всего исправлений: 2)
Ответ на: комментарий от bugfixer

Циклы завёрнутые в фолды и “accumulate / reduce” и обмазанные сверху лямбдами простоты не добавляют, вот вообще никак.

скорее всего такое только для лиц, которые не знакомы с c++ — которые просто бегло заглянули.
чего уж проще понять, что тут именно только то, что указано — гарантировано — и не нужно понимать, что тут куда-то что-то записывается (накапливается) — как в случае с явным циклом.

Короче, я пошёл напрямую к источнику и обсудил это с коллегой являющимся по совместительству комитетчиком и довольно активным контрибьютором в gcc / boost.

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

вы нарываетесь на debug-info bloat из-за дополнительных типов сгенерированных для лямбд

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

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

вот именно — как раз тут ты прав — поскольку что может быть проще, чем использование уже готового, без копирования этого кода в своём прожекте многократно.

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

там где range-based for-loops хватает.

ну и я вроде бы уже задавал вопрос и он остался без ответа — каковы критериальности для «хватает»? Можешь как-либо формализовать (желательно с математическим доказательством)? Либо это попросту игра твоего воображения.

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

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

Если принимаешь string_view, должен не выходить за его size, иначе зачем тебе string_view, передавай просто const char*.

string_view по сути аналог пары аргументов (const char*, size_t). Если бы функция принимала их, то у тебя был бы ворнинг за неиспользованный аргумент.

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

вы нарываетесь на debug-info bloat из-за дополнительных типов сгенерированных для лямбд

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

Куда оно встроится то в отладочной сборке?

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

ну тогда и явный цикл будет в таком случае вполне себе неоптимизированным — тут уж определись — либо одно, либо другое...
ну и дебаг-аспектовое является исключительно намерениями компилятора выразить как можно более дословно твой код в бинарь... тут уж совсем нельзя никаким образом к таковому придираться. (п.с. ну и в отладочной сборке я думаю многие комипляторы просто сделают такой же цикл из моего примера)

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

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

а я что изначально сказал? вот ты сказал изначально именно такого вообще быть не может (присутствовать терминатор).

Если принимаешь string_view, должен не выходить за его size, иначе зачем тебе string_view, передавай просто const char*.

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

string_view по сути аналог пары аргументов (const char*, size_t). Если бы функция принимала их, то у тебя был бы ворнинг за неиспользованный аргумент.

именно — по данной причине нет никакого смысла использовать вместо string_view указатель на char

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

тут собственно всё дело в том — что не там ты хочешь «оптимизировать» что-то — оптимизировать хочешь в своём коде, хотя если действительно что-то не так получается в выходе асма — нужно оптимизировать в компиляторе.

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

https://godbolt.org/z/nezzdc63n — ну тут видно, что генерится именно от asan какие то литералы примерно на 1к строк — посему тут сам код то при чём?

https://godbolt.org/z/EKqsMo8vK — clang значительно сокращает таковое...

п.с. тоесть как я уже писал — не там «оптимизировать» пытаетесь...

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

ну и кстати да — там он многое в константы перевёл, вместо переиспользования данных для перезаписи — что тоже получается выгоднее для производительности (хотя для памяти может быть несколько хуже — но тут уже невозможно принципиально и то и то сделать максимально оптимальным)

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 4)
Ответ на: комментарий от safocl

ну тут видно, что генерится именно от asan какие то литералы примерно на 1к строк — посему тут сам код то при чём?

Бинарник раздуется на 1к строк (не знаю сколько байт на каждую строку в среднем), вроде речь про раздутие отладочной информации, вот она и раздувается, скопипасть свою функцию, назови hash2 и уже почти в два раза больше строк будет, то есть это не единоразовый штраф по размеру.

Думаю от чейна функций там раздутие не линейное вовсе будет, а хуже.

п.с. тоесть как я уже писал — не там «оптимизировать» пытаетесь...

Я ничего не пытаюсь оптимизировать, речь не про оптимизацию, мне тут интересна конкретна тема «debug-info bloat», и на godbolt видно что выхлоп раздувается почти в 10 раз.

MOPKOBKA ★★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 5)
Ответ на: комментарий от MOPKOBKA

Думаю от чейна функций там раздутие не линейное вовсе будет, а хуже.

думается как раз обратно все — поскольку будет делать одинаковые куски для переходов. тут эти все примеры «синтетические» особо не роляют — нужно какой то прожект взять и сделать и сравнить — иначе таковое лишь сотрясание клавиатуры в постах...

почти в 10 раз

менее чем в 2 раза в случае с clang

ну и тут не понятно — это разовая акция от gcc или он на каждую таковую будет так же кратно генерить — синтетика это ну такое себе для таковых проверок... спроси у своего сокомандника-контрибутера-в-компиляторы (и по совместительству коммитетчика c++)

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 2)
Ответ на: комментарий от safocl

тут эти все примеры «синтетические» особо не роляют — нужно какой то прожект взять и сделать и сравнить

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

почти в 10 раз

менее чем в 2 раза в случае с clang

Это знаешь ли, говорит не в пользу твоего варианта, проект вообще может clang не собираться, не говорю уже о предпочтении разработчика.

MOPKOBKA ★★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от MOPKOBKA
╰─>$ ll main*.o
-rw-r--r-- 1 safocl users 294K Sep  9 17:56 main1.o
-rw-r--r-- 1 safocl users 259K Sep  9 17:56 main2.o

╰─>$ cat main1.cpp 
#include <algorithm>
#include <string_view>
#include <cstddef>

constexpr size_t res{0xcbf29ce484222325};
constexpr size_t prime{0x00000100000001b3};

size_t _hash (std::string_view strv) {
    return std::ranges::fold_left(strv, res, 
            [](auto l, auto r) -> size_t { return (l ^ r) * prime; }
        );
}

╰─>$ cat main2.cpp
#include <algorithm>
#include <string_view>
#include <cstddef>

size_t _hash (std::string_view strv) {
        // FNV-1a
        size_t res{0xcbf29ce484222325}, prime{0x00000100000001b3};
//                        vvvvvvvvvvvvvvv здесь была ошибка
//      for (size_t i{0}; i < n or str[i]; ++i) {
    if (strv.size())
        for (size_t i{0}; i < strv.size(); ++i) { // *fixed* FTGJ
                res = res ^ strv[i];
                res = res * prime;
        }
        return res;
}
safocl ★★
()
Ответ на: комментарий от safocl

«Пичаль» в том что вы за деревьями леса не видите, и почему-то решили что умение жонглировать лямбдами по поводу и без является неотъемлемым скилом напрочь отказываясь использовать более простые альтернативы. И это при том что вам прямым текстом говорят что это не то направление в котором «люди у руля» хотят двигать индустрию. Ну что ж, это пройдёт.

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

И это при том что вам прямым текстом говорят

так а кто таковое изрекает? — не обычные люди разве? которые тоже просто субъективно оценивают «со своей колокольни»... никаких объективных реалий в твоих речах нет. никакого абсолютного обоснования не имеется. лишь твоё мнение — которое ты даже сам для себя не можешь обосновать — поскольку уже нескоклько раз отложил ответ на мой вопрос про критериальности применимости того, о чем ты выговариваешь не применять «без необходимости»...

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

так это и есть «более простая альтернатива» явному циклу — в котором ничего не понятно (в отличии от фолда с той же лямбдой).

Ну что ж, это пройдёт.

конечно пройдёт — тебе однажды выскажут на работе и ты будешь вынужден перестраивать совою логику построения кода в нормальное русло.

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

так а кто таковое изрекает?

Это завуалированная попытка обвинить меня во лжи? Ну так делов-то: спросите сами - у вас же есть выход на кого-нибудь из комитетчиков?

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

В контексте фиксированных типов лямбды должны хотя-бы позволять печатать меньше. Так ведь и этого здесь не происходит. Нормальные люди написали бы этот фрагмент так:

    for (char c : strv) { res = (c ^ res) * prime; }
    return res;

Тут и компактность (буковки считать будем?), и прозрачность (любой студент поймет что здесь написано), и надёжность, и скорость, и меньше стресса на компилятор, и отсутствие необходимости требовать c++23. Вот это я бы хотел видеть в прод коде. А те выкрутасы c лямбдами что вы устроили способны впечатлить разве что сопливых гимназисток, у серьёзных дядек они вызывают лишь улыбку (в лучшем случае) и легкое раздражение (в худшем). Но признать это вам «лямбда головного мозга в терминальной стадии» не позволит.

конечно пройдёт — тебе однажды выскажут на работе и ты будешь вынужден перестраивать совою логику построения кода в нормальное русло.

Ой, боюсь-боюсь. Смотрите как бы вас ссаными тряпками не погнали из профессии.

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

Шо ты хочешь от человека с таким хвилософским ником?! Тут можно тока обнять и плакать…

тебе однажды выскажут на работе и ты будешь вынужден перестраивать совою логику построения кода в нормальное русло.

В психологии это называется проекцией. Ему уже видимо не раз высказывали:-)

AntonI ★★★★★
()
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от bugfixer

ты забыл что нужно хранить изменяемое состояние явно в своём коде.

и прозрачность (любой студент поймет что здесь написано), и надёжность, и скорость, и меньше стресса на компилятор, и отсутствие необходимости требовать c++23

первые три вообще под сильным сомнением.
стресс компилятор мне кажется вообще не будет чуствовать.
ниже c++23 вообще не стоит делать проги — пожалуй теперь уже ниже c++26.
а то сплошь и рядом «хаки оптимизации производительности» из union-ов и float-to-int-to-float корвертаций с «магическими изменениями битиков вручную», а так же пакованные структуры с прямым доступом к их неоднобайтовым мемберам (без копирования из/в) — вот такое возможно тру-кодирование по мнению неких лиц...

некоторые прожекты прислушались к исправлениям/рефакторингам, однако многим вообще пофиг как получается, даже в прожектах системного толка.

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

Хоть всякие `std::bit_cast` норм юзаться начались — уже радость. Жаль что вроде бы пока не сделали `std::start_lifetime_as` и `std::start_lifetime_as_array`

_

safocl ★★
()
Последнее исправление: safocl (всего исправлений: 3)