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

Открой computer language benchmark (https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html)

Ну открыл, и что? Там предсказуемо java проигрывает. Все исходники я не открывал, но в некоторых simd не используется.

Вот кстати еще сравнение производительности, там есть сравнение производительности на 1 ядро, 2, 4. https://www.diva-portal.org/smash/get/diva2:1463855/FULLTEXT01.pdf

По графикам видно, что отставание java растет с ростом количества операций.

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

Могут, если знать что делаешь. JIT отчасти убирает «кучу проверок» на горячем коде. GraalVM Native Image генерирует машинный код как и компилятор Си. Влияние сборки мусора зависит от кривизны рук. При желании можно вручную управлять памятью вне хипа прямо как в Си. Подвезли в последние версии JVM официально.

Там предсказуемо java проигрывает

Эти тесты ни о чём. Я помнится смотрел их, так там при старте в Си аллоцируют память вручную перед работой с большими объемами данных, а в джаве тупо стартуют JVM без опции аллокации хипа на большой объем данных. По итогу JVM тратит время на перевыделение памяти.

Все исходники я не открывал, но в некоторых simd не используется

В джаву simd подвезли надеюсь позже добавят тесты. Посмотрел использование simd из джавы через FFI, так там результат с крестами сразу одинаковый.

Эти тесты сейчас по сути замеры simd операций против классических циклов.

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

При правильной реализации все упрется в диск. Лайфхак - если положить файло в /tmp/ все сильно ускорится (при достаточном количестве памяти):-)

Зависит от скорости процессора, и скорости источника данных. Если данные вынимаются, к примеру, из сети, со скоростью 64kbit/s., то однопоточной обработки на большинстве процессоров будет хватать с избытком…

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

интересный челендж, а обязательно на java?

Тут явно практическая задача, приближенная к реальной, а не квадратики и стрелочки. Отсюда и дополнительные пребования: нам мол надо только на джаве и без сторонних библиотек.

Требования самые обычные и понятные, ибо:
* организатор занимается Явой и именно она ему интересная
* задача состоит в том, помериться умениями/знаниями в конкретном инструменте, а не сравнить Яву с C++.

Q: Can I use Kotlin or other JVM languages other than Java?
A: No, this challenge is focussed on Java only. Feel free to inofficially share implementations significantly outperforming any listed results, though.

Q: Can I use non-JVM languages and/or tools?
A: No, this challenge is focussed on Java only. Feel free to inofficially share interesting implementations and results though. For instance it would be interesting to see how DuckDB fares with this task.

Q: I've got an implementation—but it's not in Java. Can I share it somewhere?
A: Whilst non-Java solutions cannot be formally submitted to the challenge, you are welcome to share them over in the Show and tell GitHub discussion area.

При правильной реализации все упрется в диск

Ещё можно сказать всё упрётся в скорость света. Но есть нюанс и не один.

Если Вам так хочется сказать глупость - скажите.

Обсчитал предыдущую порцию и встал.

Обсчитал предыдущую порцию и встал.

Пытался тут на GoLang колхозить в многопотоке - вообще нигде не останавливается. Тупо все ядра в 100%, потом сжирает всю память и убивается по OOM Killer. Смешно получилось.

Так это уже быстрей однопоточной реализации!

Вообще то там надо разобрать результаты по метеостанциям

И в питоне есть встроенные min/max, не надо их колхозить

Нет:-)

Законы Литтла, Амдала и Ко.

Главное - что именно параллелить собираетесь и как?

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

Я же писал об упреждающей буферизации. Но даже при её наличии всё, в конечном итоге, определяется скоростями передачи, и обработки. Даже при стремящейся к бесконечности скорости обработки, не полученные данные не могут быть обработаны, то есть время работы не может быть меньше времени требуемого для получения данных. С другой стороны, время работы не может быть меньше времени обработки всех данных. То есть, при использовании упреждающей буферизации (насколько я понял, именно её Вы имели ввиду в Вашем пояснении), упрощённая формула общего времени работы T = max(D, C) + max(d, c); Где:

• T - общее время работы;
• D - время получения всех порций данных;
• C - время обработки всех порций данных;
• d - время получения одной порции данных;
• c - время обработки одной порции данных;

Скорее max(D,C)-min(d,c), но в любом случае вторым слагаемым можно пренебречь.

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

Ну можешь послать свое однопоточное решение а то там все дураки, в многопоточку ударились. Show me the code, как говорил Линус. Присылай однопоточное решение и я сделаю его быстрее.

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

max(D,C)-min(d,c)

Вы правы, мой косяк. Первая порция данных не может быть обработана до её получения, и вся обработке не завершится до обработки последней порции. Предположим скорость получения данных ниже скорости их обработки, тогда общее время работы будет равняться сумме времени получения всех данных и времени обработки последней порции. При скорости обработки меньшей скорости получения, общее время работы будет суммой времени получения первой порции данных и времени обработки всех данных. Получается T = max(D, C) + min(d, c).

Погоди, ты какое утверждение пытаешься доказать? Что однопоточная реализация будет быстрей/равна многопоточной?

Поперхнётся ваш процессор https://3dnews.ru/1098350/teamgroup-nvmenakopiteli-tforce-ge-pro-pcie-50-so-skorostyu-chteniya-do-14-000-mbayts и запросит пощады

Шипилев уже хвастается, что его решение в 2 секунды укладывается на его железе.
https://twitter.com/shipilev/status/1743070955620983078

У меня, кстати, btrfs со сжатием и файл занимает по итогу не 14 ГБ, а 3.6 ГБ считай ещё работы процессору, а не диску.

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

Погоди, ты какое утверждение пытаешься доказать? Что однопоточная реализация будет быстрей/равна многопоточной?

Почему? Упрощённо, конвейер состоит из двух акторов (напомню актор - абстракция высшего порядка и на деле может быть представлена как одним потоком, так и кластером серверов). Первый актор получает данные и отправляет второму для обработки. И первый и второй акторы используют столько потоков для своего ускорения, сколько необходимо для достижения максимальной пропускной способности. Но первый актор никак не может увеличить, к примеру, пропускную способность сети. Второй актор, в свою очередь, не может ускорить первый, или превысить суммарно достижимую мощность процессора. Каждый из акторов может лишь привести к оптимуму скорость своей работы, при существующих ограничениях. Вот и получается, что хоть каждый из акторов многопоточный, хоть однопоточный, но всё определяется скоростями получения и обработки данных… Например, если скорость получения данных из сети 64kbit/s, то однопоточной обработки хватит, чтобы достичь оптимума, так как всё будет упираться именно в общее время получения данных. Если скорость получения данных превышает пропускную способность однопоточной обработки, но не суммарную мощность всех ядер, то для обработки будет целесообразно задействовать несколько потоков, но время работы будет равно сумме времени получения всего набора, и времени обработки одной минимальной порции. Если скорость получения превышает максимально доступную общую пропускную способность многопоточной обработки, то всё упрётся именно в последнюю, и дальнейшее увеличение числа потоков приведёт лишь к замедлению, так как переключение и согласование потоков тоже не бесплатны.

Как именно собираетесь параллелить обработку? Можно псевдокодом.

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

То то все «дураки» обсуждают compute bound/memory bound задачи и roofline model. Сфигали, «че тут думать - трясти параллелить надо!»

Присылай однопоточное решение и я сделаю его быстрее.

Вы сначала решите что и как Вы параллелить будете…

Ну это понятно. Но у нас есть конкретная задача с +- конкретным железом и условиями. Просто, товарищ AntonI утверждает что вообще обойдется одним потоком в данном случае. Если взять граничные случаи, как современный процессор и чтение файла со скоростью 64kbit/s, тогда да.

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

Я в третий раз спрашиваю, что именно и как именно Вы собрались тут паралелить?

А челендж в чем? 1 самое дорогое это чтение, 2 парсинг, 3 как хранить и накапливать результаты.

Привел ниже псевдокод. Можете глянуть уже присланные решения. Там это тоже есть.

Даже при стремящейся к бесконечности скорости обработки, не полученные данные не могут быть обработаны,

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

Треды как синхронизировать будете? Где то есть ассоциативный массив, ключ - название метеостанции, значение - 4 чиселки. Что будет с этой таблицей в многопотоке?

Ты бы еще спросил в чем вызов у бегунов/плавцов/стрельцов/биатлонистов — ну пробежал, и? Все передвигать так ногами могут.

Пропустили арифметику это тоже не бесплатно, особенно если в лоб будете миллиард флоатов считать. Чтение не факт, что самое дорогое на современных nvmе дисках и файловых системах со сжатием.

Треды как синхронизировать будете? Где то есть ассоциативный массив, ключ - название метеостанции, значение - 4 чиселки. Что будет с этой таблицей в многопотоке?

Надо подумать как расчеты сделать, чтобы обойтись без синхронизации. В конце-концов, там просто min/max/mean нужен и не важно в каком порядке считали.

Верно. Именно от таких деталей все и зависит. В этом и суть задачи. Повторюсь, предлагаю прислать на конкурс *однопоточное* решение.

Что будет с этой таблицей в многопотоке?

Решений много. Можно ведь каждому потоку считать локальную статистику и объединить их перед выводом. Я лишь показал то, что просили — распараллелить тут есть что.

То что далее скажу, может быть и поможет быстрее загрузить огромный CSV.

Размер файла нам известен.

Сюды:

Прочитали треть файла и запустили поток ...

goto Сюды;

распараллелить современное IO Шта?

Можно так, можно каждым тредом брать каждую n-ю строку. Второй вариант будет скорее всего шустрее.

Найти сдвиг n-ой строки без последовательного сканирования не получится. Так что...

Можно ведь каждому потоку считать локальную статистику и объединить их перед выводом

Можно. Но тогда по треду на чанк это фиговое решение, ну или число чанков должно быть равно числу тредов:-)

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

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

Ну и лайфхак - если положить файло в tmpfs и отмапировать readonly в память, то проблем с ИО уже не будет:-)

распараллелить современное IO

Шта?

Шта будет быстрей?

read10MFromFile(f, offset=0);
read10MFromFile(f, offset=10M);

new Thread(read10MFromFile(f, offset=0)).start();
new Thread(read10MFromFile(f, offset=10M)).start();
joinThreads();

Это не проблема, после ИО основной затык это работа с таблицей. На этом фоне пробежать кусок данные и посчитать свой очередной \n ничего не стоит.

Лучше чтобы данные были не в CSV.
Даже древний DBF много ускорит загрузку данных.

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

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

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

Такой роскоши у нас нет. По условиям на вход подается случайный файл.

Ну и лайфхак - если положить файло в tmpfs и отмапировать readonly в память, то проблем с ИО уже не будет:-)

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

А что собственно сложного в распараллеливании этой задачи? Тред получения данных режет весь поток на блоки по m записей, и сливает это всё в общую lock-free очередь. Одного потока для нарезки за глаза хватит, так как его задача, только записи по признаку конца строки подсчитывать. Воркеры, число которых не должно превышать число ядер, вылавливают блоки из очереди, парсят и локально накапливают результаты. Когда блоков уже не осталось, происходит обобщение локальных результатов. А обобщение, что тоже весьма просто, может произвести поток, закончивший последним. Только lock-free очередь, да атомарный счётчик числа активных потоков и понадобится.