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

Какие-то вялые симды, к тому же и избыточные

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

Их доля в HPC относительно невелика, особенно тех кто требует разработки именно что новых CPU. Даже GPGPU из геймдева как пришли так и молотят чиселки.

Заканчивайте уже фантазировать об области в которой Вы нифига не знаете.

Наоборот, кто тупее учит, что проще, т.е. джаву, жс и т.п

Всё гениальное просто, и всё простое гениально )

Зачем яве симды? В плюсах то вектрризацию юзать эффективно далеко не всегда выходит (есть алгоритмические ограничения), а уж в яве…

Даже GPGPU из геймдева как пришли так и молотят чиселки

Потому что у вас денег нет или санкции. Нейронки сейчас молотят на другом железе - не игровом.

Потому что Вы, повторяю, нихрена не знаете о чем пишете… не устали?

Зачем яве симды? В плюсах то вектрризацию юзать эффективно далеко не всегда выходит (есть алгоритмические ограничения), а уж в яве…

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

Так я вижу и вы нихрена не знаете, только пыжитесь в своих цифровых молотилках и щёки надуваете )

Зачем в заголовке эти американизмы - «биллион». Вы, случайно, не замышляете чего то?

Я много чего замышляю. Но в иностранные агенты пока не записывали.

Вы уже давно у меня на карандаше, ещё пару встреч с узбекской разведкой и я вам гарантирую пристрастную встречу.

Эх, если бы с узбекской, тут хотя бы встречи с монгольской вместо унылых серых будней…

тут хотя бы встречи с монгольской вместо унылых серых будней…

Хотите пару таджикских резидентов к вам подселю? Серые будни растают как белых яблонь дым. Я гарантирую.

Наоборот, кто тупее учит, что проще, т.е. джаву, жс и т.п.

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

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

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

я вижу и вы нихрена не знаете

Дяденька, что б такое видеть надо самому хоть немного знать - это точно не про Вас. Сначала ugoday не может ответить на тривиальные вопросы уровня джуна на собеседовании, потом Вы с векторизацией для парсинга джсонов - лор окончательно в цирк превратился:-(

Потому что у вас денег нет или санкции. Нейронки сейчас молотят на другом железе - не игровом.

Вы дупля не отбиваете о чем рассуждаете.

Мимо под двумя слоями санкций в Крыму молочу нейронки в том числе на RTX A6000. Коллеги вполне себе молотят на игровых RTX 4090. Cuda ядра и необходимый объем видеопамяти есть и там и там.

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

Сишка намного проще джавы же

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

Проблема еще в том, что на С нельзя писать без понимания указателей. На Яве же можно писать не понимая практически ничего.

Наконец подвезли SIMD

Крутяк. Три секунды даёт на моей машине.

Там, оказывается, С++ версия есть - две секунды )

----

Посмотрел, что там ребятишки в ClickHouse с DuckDB предлагают - те секунды, которые они там называют, на моей машине не получаются хоть лопни. У них там и ЦПУ мощнее, и памяти больше. А так - практически те же запросы по коду.

У них там и ЦПУ мощнее, и памяти больше.

Пока квантовые компьютера не будут у нас под столовом стоять, нужно заботится о разработке высокоэффективных алгоритмов.
Для их разработки нужен «навык».
Когда навык приобретён, то разработка высокоэффективных алгоритмов становится обычным делом.

Те кто «не может», скорее всего просто ленятся «научиться».

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

Там, оказывается, С++ версия есть - две секунды )

Там по SIMD ещё скромненько, осталось суммирование и сравнение батчами через SIMD допилить и будет как на крестах ) Джава фактически на место крестов метит, по тем планам что хотят в ней сделать на ближайшее будущее и что уже сделали.

осталось суммирование и сравнение батчами через SIMD допилить

Насколько я понимаю - это соревнование становится похоже на «кто лучше сможет имитировать архитектуру советской ПС 2000 из 70х».

Жесть, соболезную.

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

Все что запланировали в яве уже давно сделали в C# но что-то на место крестов встать у него никак ни получилось.

американизмы - «биллион»

https://ru.wikipedia.org/wiki/Биллион

Слово было использовано французским математиком Николя Шюке (в 1475) для обозначения числа 10^12

Николя Шюке был хорошим математиком, он подсчитал с точностью до минуты время прибытия Колумба в америку и там, вместе с индейцами, его встретил и поздравил с её открытием. Словечко, кстати, он у индейцев же и позаимствовал. Поэтому да, совершенно точно это американизм. Тут невозможно не согласиться.

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

@@ -54 +54,2 @@
-        id += (id << 7) ^ *p;   /* this hash function is very data specific */
+        uint16_t rol = (id<<2) | (id >>14);
+        id = rol ^ *p;          /* this hash function is very data specific */

На x86 компилится в

        rol     ax, 2
        xor     eax, edx

Все что запланировали в яве уже давно сделали в C# но что-то на место крестов встать у него никак ни получилось

Так он большую часть жизни к оффтопику был приколочен. И в бинарник не компилился, таская за собой SDK. А джава компилится в бинарник официально. И сейчас бинарник всех уделал https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java

На Яве же …

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

(с) Ребятам-о-зверятах

Когда я слышу про векторизацию по отношению к парсингу джсона, я не знаю плакать или смеяцца - чел же вообще не понимает даже азов того как это работает на уровне железа, но пытается какими то бенчами меряться… с такими кадрами плюсовики могут спать спокойно, как Яву не апгрейдь такие кадры все равно ничего хорошего не напишут:-(

Ну ладно, паттерн фабрика на всех яп бывает полезен:-)

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

Пардон, не могу осознанно разделить ваше негодование. Возможно что-то не понимаю.

Чем вам https://github.com/simdjson/simdjson не угодил?

Если можно сложить в кучку данные, а потом одной инструкцией всю кучку и обработать, получив профит - почему бы нет-то?

Потому что гладиуолус ветвления.

Рассмотрим произвольный json файл. Я не делал профилирование разбора, тем более на яве, но могу предположить что основные ресуры уйдут на:

1. преобразование строк в числа

2. набивку ассоциативных массивов, если там есть словари

3. работу с менеджером памяти.

Если мы говорим про аппаратную реализацию SIMD на основе SSE/AVX, то ни один из этих пунктов толком ускорен быть не может - потому что входные данные в общем случае произвольны, и ветвления сьедят весь профит. Если мы говорим про SIMD как про реализацию какой то явовской конструкции в виде обычного цикла, даже развернутого, то тем более не понятно как здесь можно обогнать те же плюсы - в плюсах компилятор такие вещи делает по умолчанию.

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

Да и сама постановка задачи звучит двольно смешно - мы хотим ускорить парсинг джисона! Блджад, нормальные люди не хранят большие обьемы данных в джисоне - большие обьемы данных хранятся в бинарных форматах допускающих мапирование в память. Поэтому парсинг не является узким место ни разу, и ускорять его довольно глупо. SIMD используется для обработки этих обьемов, и то это не всегда возможно, есть целая куча ограничений. Собственно из всех видов параллелизма сейчас векторизацию использовать сложнее всего, скажем даже для stencil вычислений, где данные уже подготовены и лежат в упорядоченной струкутре стройными рядами, векторизацию использовать ой как непросто…

в плюсах компилятор такие вещи делает по умолчанию.

        __m128i separators = _mm_set1_epi8(';');
        __m128i chars = _mm_loadu_si128((__m128i*)data);
        __m128i compared = _mm_cmpeq_epi8(chars, separators);
        uint32_t separator_mask = _mm_movemask_epi8(compared);

вообще-то не похоже на «компилятор по умолчанию» в решении обсуждаемой задачи на С++ от вьетнамца по имени Le Huy Duc.

нормальные люди не хранят большие обьемы данных в джисоне

где ж их взять-то нормальных? я ж не шучу - реально гигабайт джсона люди из БД тянут и возмущаются, что и БДшник плохой, и ПГ надо убить.

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

Не готов сказать однозначно - но судя по тому, что этот simdjson используется (вроде бы) в ClickHouse - возможно именно поэтому КХ быстрее в два раза, чем DuckDB получился на ровно том же запросе.

Вы клоун по жизни или придуриваетесь? Вам уже дали ссылку на библиотеку, где 17 900 звёздочек на гитхабе, используемую в хайлоде корпораций, где прямым текстом на ангельском написано:

Fast: Over 4x faster than commonly used production-grade JSON parsers.
Record Breaking Features: Minify JSON at 6 GB/s, validate UTF-8 at 13 GB/s, NDJSON at 3.5 GB/s.

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

We compare against the best and fastest C++ libraries on benchmarks that load and process the data. The simdjson library offers full unicode (UTF-8) validation and exact number parsing.

нормальные люди не хранят большие обьемы данных в джисоне

Опять эта самоуверенность и надувание щёк. Где вы на этой планете видели нормальных людей? 99% идиотов, если не 99.99% Если бы это было не так - летали бы ужё к звёздам и посылали зонды к чёрным дырам.

Реализация на всяких rtx это скорей модель нейронки. Есть спецчипы которые делают тоже самое, но жрут 3 вата , а не 600.

Слово было использовано французским математиком Николя Шюке (в 1475) для обозначения числа 10^12

Так здесь в задаче разве 10^12 записей? Или это намеренное введение в заблуждение?

не похоже на «компилятор по умолчанию» в решении обсуждаемой задачи на С++

Вьетнамец походу напихал интринсиков, молодец. Непонятно только напуркуа - что это ему дало? Что бы такое выстрелило, надо что бы входные данные были хоть чуточку однородны, для строки «1;23;45e3» это уже бестолку. Наверное что бы ТС и ко бились в экстазе - нам тут SIMD завезли!

где ж их взять-то нормальных?

ХЗ. Учить? Хотя не все обучаемые, ТС вот нет.

этот simdjson используется (вроде бы) в ClickHouse - возможно именно поэтому КХ быстрее в два раза, чем DuckDB получился на ровно том же запросе.

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

Вы клоун по жизни или придуриваетесь?

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

Over 4x faster than commonly used production-grade JSON parsers.

С чего Вы взяли что это ускорение полчено за счет векторизации? Ой. Вы же не знаете что это такое… печаль.

Опять эта самоуверенность и надувание щёк. Где вы на этой планете видели нормальных людей?

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

Среди моих коллег таких большинство

То-то я и вижу как мы летаем к звёздам. Действительно - большинство.

клоуна вроде Вас не вышибли бы через две недели работы

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

Ваши познания в космонавтике уступают только Вашим познаниям в программировании - хотя такое себе очень трудно представить…

Стандартный вопрос джуну на собеседовании - какова алгоритмическая сложность добавления элемента в конец вектора и в конец списка? И что как правило занимает больше времени на реальном железе?

ugoday как ни пыжился, ответить не смог. Вангую что и Вы не справитесь, бггг.

У меня бы такой сотрудник долго не продержался.

Бедная та контора, которой такие как Вы имеют в подчинении сотрудников… если это конечно не менеджеры по клинингу.

Еще один вопрос по матчасти - во сколько раз будет отличаться время парсинга жсоновских фалов содержащих один словарь флотов, если размер одного файла 50Кб а второго 500Мб? И почему?

Стандартный вопрос джуну на собеседовании - какова алгоритмическая сложность добавления элемента в конец вектора и в конец списка? И что как правило занимает больше времени на реальном железе?

Вопрос не так прост, кмк.

Если говорить о добавлении нового элемента в массив, то это означает создание нового массива, т.е. O(n). Если говорить о добавлении нового элемента в linked list, то это надо найти хвост и добавить новый элемент, т.е. это тоже может быть O(n).

Если говорить о std::vector, то добавление нового элемента может привести к переносу массива в новую область памяти, т.е. это O(n). Если говорить о std::list, то добавление элемента в хвост это O(1), т.к. есть доступ к хвосту.

А вот что будет занимать больше времени на реальном железе это сильно зависит от ситуации. Если память под std::vector выделена с запасом (т.е. программист предусмотрительный и знает как он будет использоваться), то добавление нового элемента может занять совсем немного времени O(1), причем это будет очень быстро, т.к. новой памяти выделять не нужно, у ядра операционки ее запрашивать не придется. А вот добавление в конец std::list точно приведет к запросу новой памяти и это в зависимости от используемого аллокатора может занять много времени.

Я не сомневался что Вы то ответ знаете (в std::vector ЕМНИП дефолтный аллокатор при push_back удваивает память при переполнении).

Хотелось услышать хоть что по делу от ТС, теперь уж вряд ли…

А смысл? Я, правда, прочел только последнюю страницу треда, но ТС не производит впечатление системного программиста. Может быть он хороший разработчик с т.з. быстро сделать чтобы посмотреть что будет, и плевать на ошибки и нестабильность решения… Я таких встречал, причем реально хорошие ребята, много делают, проекты клепают, но абсолютно ничего не смыслят в алгоритмической базе. Помню услышал как-то фразу «база тормозит, нужно больше серверов!», а чего бы ей не тормозить, если там индексов нет, а числа хранятся в строком поле…

И объективно говоря, таких ребят абсолютное большинство. Даже в РФ, где хороших программистов в процентном соотношении все еще больше, чем в европе или индии… У нас просто некоторая деформация восприятия реальности, т.к. мы все время были окружены людьми из своей профессии, математиками (в моем случае), физиками, серьезными инженерами, причем, которые ввиду демографии, еще и сильно старше и сильно умнее, отсюда и сформировалось искаженное восприятие. А потом такой выходишь в мир, и понимаешь, что количество программистов с хорошей фундаментальной базой исчезающе мало, и ты со всеми знаком через два рукопожатия.

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

Непонятно только напуркуа - что это ему дало?

он же там объясняет:

Main ideas:

• Unsigned int overflow hashing: cheapest hash method possible.
• SIMD hashing
• SIMD for string comparison in hash table probing
• 99% of station names has length <= 16, use compiler hint + implement SIMD for this specific case. If length > 16, use a fallback => still meet requirements of MAX_KEY_LENGTH = 100
• -99.9 <= temperature <= 99.9 guaranteed, use branchless code using this property

2 секунды его код у меня считает этот миллиард (на прокаченном в кэш средствами ядра файле, разумеется). Кстати - практически как ClickHouse на уже готовой таблице MergeTree.

AntonI у нас не читатель, он у нас писатель. Щас вам тоже задачку выдаст на слабо )

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

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

вообще динамическая компиляция под заданные параметры уже давно общее место

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