- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
static inline uint64_t parse_hex_uint64(const char *s) {
const uint64_t m1 = 0x4040404040404040ll;
const uint64_t m2 = 0x000F000F000F000Fll;
const uint64_t m3 = 0x0F000F000F000F00ll;
const uint64_t *p = (const uint64_t*)s;
int64_t a = p[0], b = p[1];
a += ((a & m1) >> 6) * 9;
b += ((b & m1) >> 6) * 9;
a = (a & m2) << 12 | (a & m3);
b = (b & m2) << 12 | (b & m3);
a |= a >> 24;
b = b >> 8 | b << 16;
return (a & 0x0000FFFF00000000ll) | (a & 0xFFFF) << 48 | b >> 48 | (b & 0xFFFF0000);
}
Follow us!
ждём base64
base64 на стадии проектирования на бумажке, свободного времени на него пока нет.
Всё, хватит, оно уже полное!
Испытал ли ты при этом оргазм?
Карандаш же острый. Насколько надо упороться, чтобы куда-то его совать?
Вторым предметом, побывавшим в моей жопе, была отвёртка с круглой ручкой (14 лет).
http://clubsamodelok.ru/wp-content/uploads/2018/03/SHilo-svoimi-rukami-45.jpg
Борманд плохого не посоветует.
В данном случае интереснее не насколько, а чем. От «Солнцедара» на засовывание карандашей в прямую кишку не тянет.
и вот наконец-то я понял о чем мне постоянно твердили более опытные товарищи
только ведь не 100 строк в неделю, а 30 в 5 лет!
Вот написать бы к этой функцие прямое (вместо итеративного) вычисление? ;)
base64 туда-сюда гоняется по сети гораздо чаще, причем его объемы вполне позволяют пачкой обрабатывать блоки
> оптимальнее
*facepalm*. Здесь 39 ассемблерных инструкций (если я не обсчитался), т.е. в районе 2.5 инструкций на разряд, и ни одного перехода.
Обогнать по идее можно только раскрученным циклом и табличкой которая преобразовывает 2 цифры в один байт (65кб). Но это нанесет удар по L1.
> почти наверняка
Предлагайте алгоритм, буду рад провести бенчмарк ;)
P.S. У этой функции, конечно же есть и недостаток - на кривых данных ее поведение не определено.
что-то не сходится в твоей функции, не знаю почему
но показатели времени хорошие
http://liveworkspace.org/code/33rWZ9$3
Кстати, какие подобные сервисы сейчас существуют? У меня в кокококоллекции такие:
https://ideone.com/
https://godbolt.org/
https://wandbox.org/
https://rextester.com/
http://codepad.org/
http://coliru.stacked-crooked.com/
https://www.codechef.com/ide
https://tio.run/
https://code.hackerearth.com/
На tio.run, кстати, самое большое число языков, ограничение по времени там, если не ошибаюсь чуть ли не минута, и вообще он самый удобный.
З.Ы. вопрос об онлайн-конпеляторах: достаточно ли им запускать код в виртуоленной мышыне которой нет доступа к сети и там ещё не знаю что, чтобы было бизапасна?
Очень много языков, включая «Аду», «Brainfuck» и «Forth».
Быстрый бенчмарк для кода на крестах/цэ, очень удобная штука для холиваров.
Именно поэтому я за "Forth".
Походу кто-то опять досит говнокодик :(
https://cppinsights.io/about.html
Не компилятор и не песочница, а что-то типа современного аналога Cfront: компилирует лямбды, for по итераторам, auto, decltype, рекурсивные шаблоны, инициализаторы в фигурных скобках в конструкции, понятные C++03/C++98.
Спасибо Elvenfighter.
Хз, бенчмарков не делал, ну и как бы ничего в этом нетривиальног вроде нет... Ну да делать бенчмарки функций которые в принципе никогда не будут выполнять ничего такого, что может повлиять на производительность? :) Как бы даже не знаю... я чет совсем не в настроении спорить, ну точно не про производительность такой функции.
да разве ж нам жалко сделать бенчмарк?
вот так вот одно вычитание ухудшает почти в 2 раза результат, притом, что с маленькими буквами не работает вовсе
И потом распинался почему оно должно быть быстрее.
>вот так вот одно вычитание ухудшает почти в 2 раза
> маленькими буквами не работает вовсе
В старом треде вы же сами постили:
chr & ~(_T('a') - _T('A'))
Забавно, но раньше на «Говнокоде» было популярным обращение на «вы», а сейчас чаще обращаются на «ты».
Вот у меня руки дошли сделать бенч. И оказалось, как я и думал впрочем, бутылочое горлышко в перестановке. И всё работает еще быстрее.
http://liveworkspace.org/code/1lmQMa$15
Да и в целом всё оказалось еще удивительное. Не пойму почему мой вариант с проверками (который содержит раза в 3-4 больше кода) работает так же быстро как и борманда:? 26ms
Логично предположить что еще где-то есть тормознутый кусок. То есть преимущество над жалкими потугами с условиями и таблицами, как я и предполагал, в десятки раз.
Хе-хе-хе.
Спорное утверждение. У интела уже лет 7 лучше переходы предсказываются. Вообще интел лучше работает. А у амд ядер больше за те же деньги.
Тем более что Борманд и я реализовывали одну идею. Только я добавил проверку корректности, на "чистой" же "арифметике".
Исключение один if, который проверяет валидность входных данных и кидает исключение, например (чего не было у Борманда). Без него тут никак.
За исключением очевидного
>(a & 0xFFFF) << 48
>a<<48
Мои попытки написать reverse+compress с нуля заняли тоже ровно 20 инструкций и обе медленее.
Я чуть-чуть причесал код борманда, так что оба упакованных способа (с проверкой и без) делают самый быстрый из примеров на 1мс :)
http://liveworkspace.org/code/1lmQMa$56
crap_PI: 96 ms, control 3811068283262806208
bormand: 92 ms, control 3811068283262806208
dual un: 97 ms, control 3811068283262806208
PS Православные шаффлы SSE серъезно усилили бы разрыв.
http://liveworkspace.org/code/33rWZ9$18
таблица 256 получилась в 2 раза медленнее таблицы 256*256
Кстати, первый раз в жизни пишу что-то на сиплюсплюс.
Многие экзотические языки пробовал именно тут.
А HEX тоже много гоняется по сети. Уникод в xmlе ( ) и в jsone
Вот StringEscapeUtils в apache commons он практически все символы, без разбору, превращал при экранировании в такой hex.
Так что практическое применение, безусловно есть.
>бы к этой функцие прямое (вместо итеративного) вычисление? ;)
Надо много думать. Но нет ничего невозможного.
А какая практическая ценность такого?
От HEXа - явно польза есть. А методы куда более общие: можно быстро искать в тексте, сравнивать текст по маске.
И кривая Гильберта на практике используется.
звучит...
Всего лишь перепутал "э" с "е" и какой результат!
В последнее время много заимствований делается по принципу "кто первый перевел - так и будет". Особенно в этом смысле показательны заимствования из Китайского, где русская фонетическая транскрипция, как правило, абсолютно не похожа ни на один из использующихся диалектов, плюс к тому еще и непхожа каждый раз по-разному. Обычный китаец никогда в жизни бы не догадался, кто такой Чан Кайши или Мао Дзедун.
Хотя, конечно, викижопия не является достоверным источником информации.
> из Китайского
Оный Китай почти во всём мире называется "Сина" (в старорусском тоже), там сама история с азиатскими языками лютая.
Не, я вру. Его подругому звали.
> a += ((a & m1) >> 6) * 9;
> b += ((b & m1) >> 6) * 9;
Не асспараллельно как-то. Или оно в одну коммаду компилируется?
>mmx
Не сможет. Он 64.
Зато AVX2 сможет и по 4 за раз.
Брал 2 блока чтобы заполнить 64 битное число. Если читать его как 2 32битных а потом сдвигать и клеить - получим немного лишних операций, а тут 3-4 такта выигрываю засчет этого "инлайна".
У вас 2 64-битных.
>int64_t a = p[0], b = p[1];
Почему не обрабатывать одним махом, раз это для x64
одним махом - это 128 разрядное целое должно быть
GCC оптимизирует при наличии SSE? Или это своеобразный анроллинг?
Это фиксится теми же способами. Вчера я чего-то тупил, никак не мог найти маски.
А сегодня мне очевидно как искать.
Вот, примерная версия с заделом на оптимизацию:
lm и im могут быть полезны сами по себе.
Тут:
http://ideone.com/hCqsxb
Просто это самый сложный кусок, на мой взгляд. Как проверка на диапазоны [30-50),[60,70) - багов не имеет.
Остальное - довольно тривиально. Будет отдельным патчем.
Да и мой подход универсальный. если не хватает денег на процессор с SSE 4.2 c pcmpestri, а сильно хочется быстрого поиска по диапазонам, или конкретных значений.
Все буквы, цифры. По сути это простейшие регэксы, но ускоренные на аппаратном уровне. Область применения шире hex-ов.
Использовал на дня эту фичу. Поиск подстроки получался где-то на 30% быстрее (чем strstr). Поиск строки из 4-х элементов уже 2-3 раза в зависимости от компилятора.
А хочется перфоманса. В конце концов парсеры спирита на него переписать;)
Прям просятся. Просто lm может быть ценен сам по себе, потому я оставил промежуточные значения.
Позже удивляясь чего же они там плюсуют?
Мудр не тот, кто не постит хуйню, а тот, кто ее вовремя стирает.
Но нули тоже просто сделать, используя мою маску fm и выполнив еще 2 комманды.
Итак продолжаем наш праздник.
Когда мы знаем что числа в диапазоне 30-50, то тут уже всё просто.
К тем цифрам что в диапазоне 30-40 надо прибавить 6.
А к буквам в диапазоне 40-50 надо прибавить 10.
То есть 3 -> 6, а 4(6) ->10
Это s=((a>>2)+a)<<1.
Маскируем верхний полубайт | 7 и потом прибавляем s к младшему ниблу .
В итоге получаем корректность верхнем бите , как и в прошлом случае.
Остается одно говно. 40/60h
http://ideone.com/tm6MZT
http://ideone.com/2rpXth
Делайте ваши тесты, господа.
А как же выравнивание? UB будет. Надо через memcpy.
Нельзя просто так взять, и скастовать из char* в uint64_t*
Можно же, стандарт разрешает. Указатель на char и другой указатель могут алиаситься, лишь бы выравнивания хватало...
> А как же выравнивание? UB будет. Надо через memcpy.
const uint64_t *p = (const uint64_t*)(s-s%sizeof(uint64_t));
fixed.
З.Ы. Удачного разбора, ня.