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

Лайк, конечно, но мне кажется, что это не будет эффективнее, так как

Для этого надо их пронализировать и мб лексикографическое дерево построить…

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

Это сложнее, чем хеш, вычисляющийся в среднем за (4 инструкции * 8 букв) = 32 инструкции (у меня), плюс мгновенная индексация массива по значению хеша.

У Le Huy Duc’а вообще

Unsigned int overflow hashing: cheapest hash method possible. SIMD hashing

Ну вот после чтения это и будет основной затык. Скорее всего так.

Есть ещё парсинг - найти ;, найти конец строки, строку в число перегнать…

От глубины дерева зависит, да и дерево можно плоским сделать (всю древовоидность загнать в индексную артфметику) - будет тот же хэшмэп.

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

Ну вот после чтения это и будет основной затык.

Что значит «после»?? Если чтение само по себе не занимает больше времени чем обсчёт любых hash - что-то совсем не так.

Согласен. Было бы круто, если бы какой-то гений придумал другой способ)

NVMe может выдавать 8Гб/с, tmpfs так вообще…?

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

А, не, 6 инструкций на букву. То есть в среднем 48)

могу предложить взять бинарный формат

Утверждение следующее - если число метео-станций ограниченное и «разумное» - то скорость обработки должна упираться в чтение. Если это не так - что-то очень неправильно.

Под чтением ты понимаешь только загрузку или загрузку+парсинг?

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

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

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

Примерные характеристики железа даны.

Гляньте roofline model.
Время работы = max(время загрузки данных, время обработки данных).
Если время обработки в один поток меньше времени загрузки, тот тут параллель-не параллель…

Мая твая не панимать. Давайте рассмотрим пример. Пускай у нас есть файл 100Мб. Чтение его занимает 1с. Обработка этих данных из памяти тоже 1с. По вашему, однопоточная программа загрузит и обработает файл с диска за одну секунду?

Если время работы уменьшается незначительно (влупили 64 потока, стало на 10% быстрее) то непонятно нафига параллелили то?!

Повторюсь в 38-й раз: условие задачи выиграть миллисекунды.

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

Первая реакция у мну была такая же как у тебя - не майтесь дурью, все упрется в ИО:-)
Сейчас, хорошо подумав- на ssd/tmpfs все упрется в хэшмэп, это уже параллелится.

Посмотрел другие ваши сообщения. Там уже другое говорите.

По вашему, однопоточная программа загрузит и обработает файл с диска за одну секунду?

При правильной реализации да.

А можно тогда описать правильную реализацию? Я себе ее представить не могу.

.

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

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

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

если угорать

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

дробная часть одно цифро-знакоместо

очевидно utf-8

суммировать байты цифр разрядов отдельно с последующим вычитанием (counted <<5+counted<<4) для получения количества не нормализованного в рязряде

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

Уже давно есть PGO которая дает все нужные подсказки компилятору.

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

В теории да, и это особо обещали например во время зарождения C# и NET, но на практике тот же PGO все такие системы бьет без проблем.

со времён древних:

дка у регулярок Томсона

процедура маски в bitblt - пример в Ораме(& Уилсон)

и много тому подобного

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

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

pgo это более общее - и предполагающее в общем случае тот или иной рантайм со своими накладными

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

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

Да епжеш. Все это - красивые термины и рекламные лозунги. Хватит ими сыпать, как доказательством бОльшей производительности джава по сравнению с C/C++. Вот когда большинство бенчей в сети будут сходится в заключении о том, что действительно джава быстрее C/C++ (это мы еще потребление памяти не обсуждали), вот тогда и вспомните эти ваши «размазанные компиляции» и т.п.

О то сейчас это выглядит так:

Умный рантайм Размазанная компиляция Рефлексия Кэширование кода Подмена там чего-то на лету хер знает сколько там еще всего Вопрос: А, простите что-то там с бенчмарками? Ну умный рантайм же!!! Зачем вам эти бенчмарки?

:-)

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

Каких проверок то в C коде? Расставленных специально для замедления С кода, чтобы код джава на этом фоне точно выиграл?

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

Забавно, что бенчмарки тоже так считают, заблуждаются наверное

при любых условиях

В большинстве случаев, не подменяй утверждения

Если секунда при чтении обусловлена пропускной способностью hdd, то система сама прекрасно умеет в упреждающее чтение, не надо ей мешать. 21й век на дворе…

Ну и мапирование никто не отменял.

Есть спецчипы которые делают тоже самое, но жрут 3 вата , а не 600.

Тоже самое не получится, никак. Спецчип с выделением 3 Вт может распознать контрастную цель в ИК диапазоне на матрице 64х64 пикселя в головке наведения. Но он не справится с распознаванием на 1920х1080, не сможет в seq2seq и тд. Законы физики не позволяют.

Я не общаюсь со студентами, но постоянно сталкиваюсь с тем о чем вы пишите. После долгих размышлений и поисков информации по этой теме пришел к тому что проблема появилась после того как предмет «Логика» перестал быть обязателен. 4 закона логики тут большинство без гугла не озвучат. В итоге имеем то что в дискуссиях большинство озвучивает не свои выводы (для выводов логика нужна), а просто осуществляют апелляцию к авторитету.

А можно тогда описать правильную реализацию? Я себе ее представить не могу.

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

Если чтение файла асинхронное.

Вася с Катей хотят подсчитать в «Анне Карениной» количество употребления фразы «антидилювиальные мысли».

Вася читает от корки до корки вслух. Катя записывает.

Так что ли?

Разве это может быть быстрее, чем если бы они каждый по своей половине книги читали и считали одновременно?

Так что ли?

В контексте вопрос был такой:

Мая твая не панимать. Давайте рассмотрим пример. Пускай у нас есть файл 100Мб. Чтение его занимает 1с. Обработка этих данных из памяти тоже 1с. По вашему, однопоточная программа загрузит и обработает файл с диска за одну секунду?

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

Не так. Вася слоупок, он очень медленно листает страницы, но нонстопом. Катя смотрит ему через плечо, быстро просматривает страницу и записывает число интересующих фраз.

Второй поток это вторая Катя, Вася с книгой это hdd и он один. Вторая Катя процесс не ускорит, наоборот - Васе придётся листать книгу в двух местах.

Вася слоупок

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

Ладно, спасибо, мысль понял.

Не знал, что есть readahead(2). Соглашусь, что такое решение при описанных мной условиях будет стремиться к 1 сек.

Вот здесь можно почитать https://arxiv.org/pdf/1902.08318.pdf

Смотрим алгоритм.

1. Вместо обычно применяемого однократного прохождения по всем данным, авторы проходят два раза.

Результатом первого прохода является разметка элементов json формата, т.е. они получают массив указателей на начало каждого элемента.

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

2. Они предполагают, что целые числа лежат в диапазоне -2^63 до 2^63.

В базах данных ID часто это uint64_t, т.е. от 0 до 2^64.

3. Вещественные числа у них лежат в диапазоне от -1 * 10^309 до +1 * 10^309.

Может и приемлимо, но обычно на 64bit системах double лежит в большем диапазоне. Про количество значащих знаков в тексте ничего не сказано.

4. В результатом их парсинга является массив 64 битных слов, в котором:

• целые числа кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет целое число в обычном формате (int64_t, как я понял).

• вещественные числа тоже кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет вещественное число (binary64 формат).

• массив в этой ленте хранится как спец. символ (первые 64bit) и индекс последнего элемента массива (64bit)

• строки хранятся в отдельном массиве, в основной ленте хранится номер (указатель) строки.

===

В целом ускорение получено за счет:

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

2. некоторых предположений о входных данных

3. специальный выходной формат (парсинг идет не в дерево)

===

С т.з. алгоритма ничего нового нет.

• Есть микро модификация обычного парсинга с целью использования SIMD инструкций процессора.

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

===

В целом, на мой взгляд работа по ускорению парсинга JSON бессмыслена. В HPC никто JSON данными обмениваться на скорость не будет. Огромные объемы JSON могут получатся или из-за тупости разработчика (проф беседа, повышение квалификации, замена разработчика), или из-за исторически накопленных данных (тут скорость обработки не принципиальна), или из-за того, что данные стырены (скорость обработки не принципиальна).

Сам JSON задумывался как очень простой и читаемый формат для обмена небольшим объемом данных. Он не предназначен для пересылки мегабайтов doulbe, так его использовать это идиотизм, как и для бэкапа объемных баз данных.

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

===

И еще раз повторюсь: написать программу, которая раскроет весь потенциал процессора даже для простых задач это очень нетривиально. Поэтому почти для всего, что есть можно получить очень значительное ускорение просто поправив код (написанный на системном языке, например, на С или С++), даже не алгоритм.

Спасибо за резюме, оч поучительно.

Вот вы такие тут все SIMD обсуждаете, а я потратил почти два дня чтобы в фортране сделать mmap файла. Удалось. Но лучше, как говорится, день потерпеть, чтобы за 5 минут долететь :)

да дело не в джабе

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

пример реализации bitblt в windows 1.0

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

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

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

Даже если вы действительно научились в MQ (снимаю шляпу) - идея остаётся той-же: пока читается следующий chunk нужно успеть обработать предыдущий. С SSD при любом раскладе времени остаётся меньше, но, кмк, его предостаточно для данной задачи.

Положили файл в tmpfs, это в RAM.

Как говорил небезызвестный Шарик (или это был Матроскин?): чтобы продать что-нибудь ненужное нужно сначала купить что-нибудь ненужное. Файл как-то на tmpfs должен появиться (умолчим об ограничениях на размер), что довольно быстро приводит нас к одному из моих предыдущих посылов: «или читят».

суммировать байты цифр разрядов отдельно с последующим вычитанием (counted <<5+counted<<4) для получения количества не нормализованного в рязряде

Можно пояснить эту магию, как-то не доходит идея

да дело не в джабе

В ней.

речь о моменте когда

У кого речь? У тебя и еще кого?

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

И что это доказывает?

0x30 '0' ... 0x39 '9'

'1'+'3' =>4

'1'+'3' -2*'0' == 4

вычитание делать в оконцове домножив код нуля на количество слагаемых

складывать raw байты содержащие коды символов цифр в отдельных разрядах

long64 всяко хватит

не факт что это ваще даст экономию даже спичек

см гл 8 Идеальный код Орам Уилсон

давай

в частности [системой c «рефлексией»] - является в том числе linux c бортовым сс(gcc|clang|pcc ...) c возможностью на ходу выполнения основного процесса перекомпиляции(в фоне на свободных мощьностях) тех или иных подключаемых либ али полностью каких либо бинарных сущностей

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

ты остался при своём мнении

Файл как-то на tmpfs должен появиться

$ man cp
CP(1)                                                            User Commands                                                           CP(1)

NAME
       cp - copy files and directories

(умолчим об ограничениях на размер)

$ cat /proc/meminfo 
MemTotal:       131602796 kB
MemFree:        116456936 kB
MemAvailable:   127604128 kB

;-)

или читят

не мы такие - жизнь такая… (с)

‘1’+‘3’ -2*‘0’ == 4 вычитание делать в оконцове

Числа-строки в задаче могут быть либо двухзначные, либо трёхзначные, знаковые. Например: "1.2", "-3.4", "56.7" и "-89.0". От этих чисел нужно высчитать среднее и определить минимальное и максимальное значение.

В принципе идея хорошая, но, мне кажется, что «не окупится». Я сходу даже не знаю как бы её можно было применить.

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

Я пробовал кастовать строки чисел без знака к интам (после каждого числа всегда стоит '\n') и смотреть значение в LUT, что, по идее, должно быть достаточно быстро, но, к сожалению, такой вариант получился медленнее простого парсинга чисел с умножением разрядов на 10.

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

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

The time program is used for measuring execution times, i.e. end-to-end times are measured. Each contender will be run five times in a row. The slowest and the fastest runs are discarded. The mean value of the remaining three runs is the result for that contender

То есть замеряют время работы программы 5 раз, отбрасывают самый медленный и самый быстрый запуски и из оставшихся трёх высчитывают среднее. После первого запуска файл закешируется и все последующие разы IO практически не будет влиять на время выполнения.

Великоват файл для полного кэширования - гигов на 8 как мин должен тянуть, если там 1e9 по 8 символов на запись…

Да, около 13 ГБ. Там же кроме названий городов ещё значения температур, получается в среднем где-то по 13.8 байт на запись, включая символ перевода строки.

Но ведь у кого сколько памяти. На тестовой машине изначально было 32 ГБ, теперь значится 128.

$ wc -c measurements.txt
13795998875

Сильно сомневаюсь что система по умолчанию его весь в кэш засунет.

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

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

Изначально граф имеет 10^3…9 вершин, по 6…12 связей на вершину (отвечает кристаллической решетке).

Язык С++;-)

Сорри за оффтопик, но новый тред делать не хочу - это просто пример актуальной задачи из HPC а не вот это вот убожество с CSV на яве;-(

задачка искусственная … После первого запуска файл закешируется и все последующие разы IO практически не будет влиять на время выполнения.

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