1 биллион челлендж

Как и следовало ожидать, Вы не смогли ответить на два простейших технических вопроса по Вашей специальности. Но щеки дуть продолжаете… фу быть таким:-(

Так хеши на обычных процах уже несколько лет как так ускорены, если я не ошибаюсь.

Можно у bugfixer спросить, он любит на такие темы рассуждать.

Мне кажется это все таки больше отношение к жизни вообще - че тут думать, трясти надо! Если человек не умеет признавать свои ошибки, то он необучаем. А дальше труба…

Это я не знаю к сожалению, я с хэш-таблицами от строк в плюсах не встречаюсь по работе никогда:-(

Но было бы логично.

А ты взгляни на это с его стороны:

Есть ресурс, есть графики, есть технология, которая многими воспринимается как «золотая пуля» SIMD, векторизация, распараллеливание и пр. и все это говорит, что работает! Потом прикрутят ИИ и покажут еще 4х кратное ускорение.

А тут ты с какой-то непонятной теорией :).

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

https://github.com/simdjson/simdjson

просто взгляните на реализацию

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

Причём на него же никакие аргументы не действуют в принципе, это какой то религиозный экстаз.

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

Те кто так делать не умеют, те не нормальные технари и к серьёзным вещам их лучше не допускать:-)))

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

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

Так же и тут. Есть база – SIMD, ИИ, Квантовый компьютер, Нейронная сеть, … и все, оно может стать точкой отсчета для восприятия технологий, абсолютной и непоколебимой, которая принесет El Dorado, золотой век, а все, кто в это не верит – хейтеры, лохи и мамонты.

Да, наверное ты прав. У меня нынче студентов мало и они вменяемые, а что там было во время бурной преподской молодости я уже позабыл…

Но, увы и ах - боюcь такой тренд нашу цивилизацию ушатает;-(

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

Ладно, специально для soomrack и AntonI: В simdjson нет секретных ингредиентов, только SIMD! Во всех других направлениях, что можно было оптимизировать давно оптимизировано в прочих JSON либах.

Но благодаря SIMD существенные результаты доситгаются в следующих случаях:

• Валидация JSON от сторонних источников. Например, у вас нагруженный REST сервис и вам нужно делать проверку поступающих данных без разложения структур данных в памяти.

• Структуированный поиск по JSON файлу или СУБД. Например, в PostgreSQL есть JSONB формат хранения данных. Многие REST сервисы предоставляют выгрузку JSON файлов. Либо один файл на гигабайты, либо множество мелких файлов того же размера. Например, наша налоговая и другие гос. сервисы дают такие выгрузки общедоступных данных.

• Последовательная обработка JSON файла без построения всего дерева в памяти. Аналогом в XML является SAX парсеры. Как в JSON это называется не в курсе.

• Тот самый парсинг. Да, это не даёт существенный выигрыш, но за счёт выкидывания условных переходов при проверке токенов благодаря SIMD инструкциям и использованию масок мы получаем хороший прирост производительности. По сравнению с классическим циклом и switch-case подходом.

Честно, я не смотрел их код.

Поясни в двух словах в чем достижение? А то я кроме слов «потому что SIMD» пока ничего не увидел.

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

А с т.з. алгоритма парсинга, ускорение хешей там не может дать 4х прироста на всем объеме, если алгоритм был написан для общего случая. И какие инструкции SIMD используются и в какой части алгоритма? В чем алгоритмическое новшество?

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

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

Я третий раз пишу - положите входное файло на tmpfs и проблем с IO не будет. Тогда работа с хэш таблицей заиграет новыми красками и её будет иметь смысл параллелить.

Да и ssd современные тоже неплохую скорость дают.

А если мы про тормознутую Яву говорим, то там многопоточность почти всегда в кассу.

А я давно твержу, что физики и прочие олимпиадники от математики в прикладных направлениях - зло.

Если бы не физики и математики в прикладных направлениях то не было бы ни компьютеров ни ИТ, и Вы бы работали дворником, а выступали бы не в интернетах а перед бабками у подъезда.

Или Вы всерьёз думаете что без физики с математикой можно разработать и создать современное железо? Вы вон на элементарные вопросы по алгоритмам ответить не в состоянии, а ведь эти алгоритмы заложены в яву который Вы типа «свои деньги» зарабатываете - а так бы пришлось Вам метлой вжих-вжих с утра до ночи…

А, ок, хэши можно так ускорить, не спорю. Но 4х кратный рост это вряд ли даст, просто хорошо сделана либа.

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

simdjson - это одно. В ClickHouse оно управляется через SET allow_simdjson=1;.

цитировал я товарища, который предложил на С++ самую быструю реализацию задачи из темы. https://github.com/lehuyduc/1brc-simd

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

Ой вэй…собеседников я обычно хорошо слышу когда они свои мысли ясно излагают:-)

Векторизация при работе со строками, в т.ч. с их хэшами, может оказаться полезной, не отрицаю.

Не могли бы Вы сформулировать почётче свои тезисы, с чем Вы собственно не согласны/что хотите доказать/донести?

что хотите доказать/донести?

то, что ОКМД - объективно полезно, в том числе и для этой частной задачи.

А вот коль был разговор за геофизику... Что там сейчас программируют? В моей юности - всякое БПФ, мат.свертки, выделение сигнала это же руками делалось (в том числе и с ОКМД). Плюс ещё и с теми пресловутыми печатающими устройствами целая возня. Плюс ковыряния с разными форматами OTG профилей. И всё - в одно рыло.

Я так понимаю, что это всё же сейчас есть готовое? Берем Питон и дергаем нужные библиотеки в нужном месте?

Я третий раз пишу - положите входное файло на tmpfs и проблем с IO не будет.

Я до сих пор не понял, при чем тут tmpfs. Есть условия и ограничения зядачи.

Тогда работа с хэш таблицей заиграет новыми красками и её будет иметь смысл параллелить.

А с медленным (100Mb/s) IO нет смысла?

А если мы про тормознутую Яву говорим, то там многопоточность почти всегда в кассу.

Тогда все становится еще более загадочно, ибо я проверил пару представленных вне конкурса решений на C, C++, Rust и они все тоже не в один поток работают.

товарища, который предложил на С++ самую быструю реализацию задачи из темы. https://github.com/lehuyduc/1brc-simd

А если так:

+++ 1brc_final_valid.cpp
@@ -59 +59 @@
-constexpr int N_THREADS = 128;
+constexpr int N_THREADS = 1;

в один поток получается:

real	0m14,057s
user	0m12,889s
sys	0m1,159s

я там под свою машину ставил - N_THREADS = 12; и вывод в cout вместо файла тоже автора поправил, чтоб как у всех было.

собственно, при 12 потоках она и говорит:

real	0m2,075s
user	0m16,950s
sys	0m1,381s

Можно у bugfixer спросить, он любит на такие темы рассуждать.

На самом деле у тебя есть тенденция сильно преувеличивать мои «заслуги перед отечеством». Но если вопрос - можно ли ускорить JSON parsing за счёт SIMD - да конечно можно: __strlen_sse2() and __strlen_avx2() из glibc не просто так торчат. И таких примеров - сильно больше одного.

Интересно. Даже не знал, что это все в glibc есть. Это ведь не только для json, конечно. Где можно почитать про simd работу со строками?

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

Так или иначе это все равно больше действий.

Где можно почитать про simd работу со строками?

Проще на disasm посмотреть. И на IFUNC.

???

динамический синтез кода ( в самом дремучем случае полиморфизм бинаря)

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

---

если есть возможность заменить(нет вопроса реентерабельности )(переписать поверх) проверяющую часть тогда елсе ветка делает B и затирает «делать B» всё тело цикла(включая себя) - и продолжается итерирование

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

Есть условия и ограничения зядачи.

Там сказано что нельзя класть файло на tmpfs? А на ssd можно (они кстати разные бывают)? А на NFS?:-)

Даже более простые бенчи ОЧЕНЬ сильно зависят от железа.

А с медленным (100Mb/s) IO нет смысла?

Гляньте roofline model.

Время работы = max(время загрузки данных, время обработки данных).

Если время обработки в один поток меньше времени загрузки, тот тут параллель-не параллель…

я проверил пару представленных вне конкурса решений на C, C++, Rust и они все тоже не в один поток работают.

И что? Конечно многопоточность это модно/молодежно, но эффект то от неё какой?:-)

Если Вас это и вправду интересует, то попробуйте построить зависимость времени работы кода от числа потоков. Есть понятие эффективности распараллеливания - если время уменьшается пропорционально числу потоков, то все зашибись, но такое бывает очень редко, даже на гораздо более подходящих для параллельности задачах. Если время работы уменьшается незначительно (влупили 64 потока, стало на 10% быстрее) то непонятно нафига параллелили то?!

Чаще всего начиная с какого то числа потоков наступает насыщения, т.е. время перестаёт уменьшаться с ростом числа потоков.

Время работы = max(время загрузки данных, время обработки данных).

.GT.

Я не про simd звал поговорить, а про общефилософское почему оно так есть как есть и нужны ли физматы в ИТ:-)

Насчёт simd - а какой эффект оно дает для json?

Поясни в двух словах в чем достижение? А то я кроме слов «потому что SIMD» пока ничего не увидел.

Вот здесь можно почитать https://arxiv.org/pdf/1902.08318.pdf В конце документа тесты с парсингом, построением дерева JSON документа в памяти и выборкой данных из него. Так вот, библитека c SIMD парсингом всё равно отрывается в 2 раза от библиотек без онного. Аллокации не вносят большого влияния. А вот внедрение branchless алгоритмов с SIMD инструкциями дают заметный прирост производительности.

ОКМД - объективно полезно

С этим вообще никто не спорит. Я лишь утверждаю что из всех видов параллельности юзать его сложнее всего. Ну если хочется получить весь заложенный профит, а не доя галочки…

в том числе и для этой частной задачи.

Вопрос НАСКОЛЬКО полезно?:-) У нас подход - если код нельзя ускорить более чем вдвое, то нефиг возиться…

Что там сейчас программируют?

Конкретно я занимался прямыми/обратным задачами сейсморазведки и немного моделирование резервуаров, включая ГРП. БПФ конечно никто давно не кодит, есть готовые либы - а так да, все ручками.

Я так понимаю, что это всё же сейчас есть готовое? Берем Питон и дергаем нужные библиотеки в нужном месте?

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

Мне тяжело понимать эти сумбурные конструкции. Это раз.

если на си - так делать в ручную будет быстрее

Что и так очевидно и про что я и пишу.

как бе технологичней

Я вообще про это не писал

real 0m14,057s

Неплохо. Мой новый варик навряд ли быстрее, но должен быть близко. С симдами, мне казалось, особого смысла возиться нет. Было лень, короче)

А где взять сам файл с записями? Дайте плиз ссылку на файл. хочу тоже попробовать на досуге :)

Неплохо

Я пока ещё не осознал в чём фундаментальная сложность задачи.

AntonI: что я упускаю? Должно ограничиваться скоростью чтения с диска, не?

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

С диском я предлагаю бороться через tmpfs:-)

Задача дурацкая, но основное бурление говн вызвали simd и параллельность завезенные в яву- дескать щас ява порвёт плюсы и останется главным ЯП в галактиге.

В самой задаче нет особой сложности. Она может быть интересна тем, кто только изучает принципы низкоуровневой оптимизации. Либо тем, кто хочет показать, что он что-то может. Алгоритмически там просто складывание чиселок в хешмапу. Пока что. Но, возможно, ты придумаешь другой, более оптимальный алгоритм, пускай даже и узко специализированный, который порвёт зазнаек в клочья) Лично мне было бы безумно интересно посмотреть на такой алгоритм.

Должно ограничиваться скоростью чтения с диска, не?

Если у тебя достаточно оперативки, то файл полностью закешируется посе первого прочтения и IO не будет в какой-то значительной степени не будет являться ограничителем.

Задача дурацкая

Я всё равно не понимаю почему оно в IO не упирается. Ни один cache с малти-ТБ не справится. Читать больше одного раза - не стОит. Или «читят».

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

Один из аффторов этой статьи:

Daniel Lemire
Computer Science Professor
Université du Québec (TÉLUQ)
Montreal, Canada

Education
PhD in Engineering Mathematics, 1998

École Polytechnique and Université de Montréal

MSc in Mathematics, 1995

University of Toronto

BSc in Mathematics (High Distinction), 1994

University of Toronto

Чо то ржу…

Потому что хэшмэп от строк это дорогая штука?

Файл понятно что читается однократно.

Лично мне было бы безумно интересно посмотреть на такой алгоритм.

Можно заменить хэшмэп на что то более эффективное, заточенное под конкретные названия метеостанций. Для этого надо их пронализировать и мб лексикографическое дерево построить…

Потому что хэшмэп от строк это дорогая штука?

Хех.

А, ещё питон юзается для кодогенрации в таких задачах - но это отдельная история.

Потому что хэшмэп от строк это дорогая штука

Читать дорого - да. Всё остальное - мелочи. Ты реально думаешь от hash много зависит?

Короче. Если просадка не на чтении - что-то делают ну совсем не так.

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

Первая реакция у мну была такая же как у тебя - не майтесь дурью, все упрется в ИО:-)

Сейчас, хорошо подумав- на ssd/tmpfs все упрется в хэшмэп, это уже параллелится.

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

Положили файл в tmpfs, это в RAM. На чем будет следующий затык?

Сейчас, хорошо подумав- на ssd/tmpfs все упрется в хэшмэп, это уже параллелится.

Там нечего параллелить. Главное - вычитать.

Как ты по метеостанциям разберёшь?

Как ты по метеостанциям разберёшь?

По мере прочтения. Ну, или я задачу не понял.