LINUX.ORG.RU
Форум — Development  

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

 ,


2

4

Даётся CSV файл с температурой от метеостанции и названием локации. Таких записей миллиард. Нужно найти максимальную, минимальную и среднюю температуру по каждой локации за минимальное время. Подробнее https://www.morling.dev/blog/one-billion-row-challenge/

  • Срок до 31 января

  • Пишем на джаве (но там вроде и другие ЯП участвовали)

  • Приз имя на доске почёта

Предоставленные реализации на текущий момент https://github.com/gunnarmorling/1brc?tab=readme-ov-file#results

Реализации и челленджи на других ЯП https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell

★★★★★

Последнее исправление: foror (всего исправлений: 1)

 ← 1 2 3 4 5 6 7 8 9 10 11 →
Ответ на: комментарий от Toxo2

dask_cudf.read_csv() - оно по сути ничем не отличается от clickhouse.read_csv() или duckdb.read_csv() или ДругаяЧорнаяКоробочка.read_csv(), плюс еще и спец.оборудование требует.

Да какое спецоборудование? CUDA ядра? есть во всех RTX картах. В моей карте просто памяти больше для создания и обучения больших нейронок. В данной задаче это вообще не важно, та же RTX 4090 будет чуть быстрее.

dask_cudf.read_csv() это просто обертка read_csv() для Pandas dataframes. За параллельность отвечает сам dask, за работу с видеокартой - libcudf.

Это не программирование, это пользование.

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

Тем не менее - по мотивам вашего кода, но без CUDA

Поймите меня правильно, я решил сделать пример на видеокарте т.к. все упоролись на проце оптимизировать. Понятно, что голый С с каким-нибудь SIMD запущенный в 128 потоках уделает всех и выйдет из 0.5 сек. Это скучно.

Python взял только потому что под него сразу были нужные биндинги по CUDA в виде cudf и можно было написать реализацию БЫСТРО, а не терять несколько вечеров на колупание в С. Мне было интересно посмотреть как на этой задаче покажут себя структуры данных от Apache Arrow которые и используются в dask, потому выбор пал на dask_cudf.

Говорит Total time: 111.76471519470215 sec, что точно лучше прошлых 13ти минут на Python

Попробуйте поиграться с blocksize=«64MB». Например, blocksize=«128MB» и увеличивайте пока ошибку сыпать не начнет. Возможно, сможете выйти из 100 сек.

Obezyan
()
Ответ на: комментарий от Obezyan

Покажите в условиях конкурса требование реализовать все алгоритмы самому, с нуля

No external library dependencies may be used
Implementations must be provided as a single source file

Попробуйте поиграться с blocksize=«64MB»

Поставил 1GB - Питон мне сказал «Убито».

Ровно такое же «убито» у меня на Го в многопотоке вышло )

Так-то из всего этого веселья - интересно было посмотреть почему ClikHouse не подошёл, ну и посмотреть на финты ушами от серьезных PhD-дядек из любопытства.

Toxo2 ★★★★
()
Последнее исправление: Toxo2 (всего исправлений: 2)
Ответ на: комментарий от Toxo2

No external library dependencies may be used Implementations must be provided as a single source file

А само решение должно быть на Java. Что не мешает нам пробовать свои варианты. То что вы называете «не программирование, а использование» во всем остальном мире называется Data Sсience.

Поставил 1GB - Питон мне сказал «Убито».

Вы не совсем понимаете суть параметра, сильно больше не значит сильно быстрее, попробуйте 128MB. Блоки по 1GB и у меня не запустятся.

Obezyan
()
Ответ на: комментарий от Obezyan

Почему вам так важно быть всегда правым, а всем вокруг вас не понимать какую-нибудь суть? Вы тех.директор?

Да на здоровье - вы правы, я не прав.

Первое что в голову пришло самое простое: 

time clickhouse-client --query "SELECT x.c1, min(x.c2), avg(x.c2), max(x.c2) FROM (SELECT c1, c2 FROM file('measurements.txt', CSV)) x GROUP BY x.c1 SETTINGS format_csv_delimiter = ';';"

real	0m20,175s
лично меня - точно бы устроило.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2

Почему вам так важно быть всегда правым, а всем вокруг вас не понимать какую-нибудь суть? Вы тех.директор?

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

Ваш вариант на моем проце (Threadripper 3970X) выдал:

Total time: 94.62445759773254 sec
Obezyan
()
Последнее исправление: Obezyan (всего исправлений: 1)
Ответ на: комментарий от sshestov

Неплохо. Ускорение больше, чем в 2 раза!

стандартная функция считывания строки в число жутко медленная

В Си то же самое. Вообще glibc отличается своей тормознутостью. Меняешь printf на ручное форматирование и сискол write - и твоя программа ускорилась в 10 раз, даже без буфера. А с буфером так вовсе вывод почти бесплатный получается.

anonymous
()
Ответ на: комментарий от Toxo2

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

iDesperado
()
Ответ на: комментарий от anonymous

@anonymous подсоби пожалуйста: я пытался твой хеш реализовать, и видимо коллизии (?так называется?). У тебя

/* hash compute, unroll part of the loop /* hash compute, unroll part of the loop */
    #define ROL(x, n)  (x<<n | x>>(16-n))     
    id = ROL(id, 2) ^ *p++;                   
    id = ROL(id, 2) ^ *p++;
    id = ROL(id, 2) ^ *p++;
    while (*p != ';') {
        id = ROL(id, 2) ^ *p++;    }

ты делаешь id для трех первых символов явно, и дальше в цикле. При этом id каждый раз сдвигается (не циклически) на 2 бита влево и на 14 вправо, между ними OR, а дальше XOR со следующим символом? Так?

Какие значения может принимать id? Я это всё попытался реализовать на фортране, в целом работает на были отрицательные числа. Я ему дополнительно 3-4 бита стирал слева (показалось замедление если массив имен большим делать).

Так то я уж из 3-х секунд выхожу. Раньше основной массив как char рассматривал. Оказалось что 8-ми битный int сильно быстрее.

sshestov ★★
()
Ответ на: комментарий от sshestov

id имеет тип uint16_t и операция ROL не сдвигает, а проворачивает 16 бит влево на 2 бита, то есть те биты, которые сдвинулись из 16 бит задвигаются обратно справа. Важно, чтобы размер регистра или переменной был 16 бит. Можно добавить & 0xffff после ROL. Я не знаю фортран, поэтому что-то конкретное не смогу подсказать. Ещё важно начальное значение id.

Какие значения может принимать id?

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

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

Так то я уж из 3-х секунд выхожу.

Догоняешь лидеров на Джаве, получается) Сейчас там 2.5 секунды на 8 ядрах.

Раньше основной массив как char рассматривал. Оказалось что 8-ми битный int сильно быстрее.

Посмотрел, пишут, что в фортране character - для строк, которые ещё содержат значение длины. То есть это не то же самое, что сишный char.

anonymous
()

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

BEGIN {
    FS=";"
    ORS=""
    PROCINFO["sorted_in"] = "@ind_str_asc"
}
{
    name=$1
    temperature=$2
    if(db[name]["n"]) { # station exists
	min_t=db[name]["min"]
	max_t=db[name]["max"]
	n=db[name]["n"]
	avg=db[name]["avg"]
	db[name]["n"]=n+1
	if (min_t < temperature) { db[name]["min"]=min_t } else { db[name]["min"]=temperature }
	if (max_t > temperature) { db[name]["max"]=max_t } else { db[name]["max"]=temperature }
	db[name]["avg"]=avg + temperature
    } else { # new station
	db[name]["min"]=temperature
	db[name]["max"]=temperature
	db[name]["n"]=1
	db[name]["average"]=temperature
    }
}
END {
    print "{"
    for(station in db){
	min_t=db[station]["min"]
	max_t=db[name]["max"]
	avg=db[name]["avg"] / db[name]["n"]
	printf "%s=%s/%.1f/%s;", station,  min_t, avg, max_t
    }
    print "}\n"
}

отработало за 16 минут. Приемлимо.

957.19user 8.17system 16:05.43elapsed 99%CPU (0avgtext+0avgdata 3584maxresident)k
26044096inputs+0outputs (3major+360minor)pagefaults 0swaps
ugoday ★★★★★
()
Ответ на: комментарий от anonymous

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

Что касается character, то просто массив character (это не строка, а именно массив) определяется как character, dimension(500) :: my_char_array и таки действительно является однобайтовым (уж я наконвертировался туда-сюда). А строка определяется как character(len=80) :: my_string и оно знает про длину. Я долго ковырял именно массив символов, который прямо конвертируется в массив 8bit int.

Мое заднее слово - 3.22 с

sshestov ★★
()
Ответ на: комментарий от anonymous

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

$ ./one-billion-row-challenge
total: 4.25s

пока ничего быстрее, чем тот С++ от LeHuyDuc'а не видел 

real	0m1,523s
но вообще-то тот интересный кусок кода про парсинг float'ов - lehuyduc именно у этого Rust'а взял.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2

real 0m1,523s

Забавно, что это ещё и от ядра Linux зависит похоже.

На одной и той же машине - две ОС: ArchLinux и VoidLinux(musl)
Собираю одним и тем же gcc12
Запускаю под одним и тем же 6.6

Под ArchLinux десять вызовов подряд ~1.5s все
Под VoidLinux(musl) стабильно ~1.7s

Причем даже если chroot из Arch в Void (т.е. от Arch остается только ядро, библиотеки-то Void'ские) - получаю «арчевские» 1.5 уже на бинарнике Void'а.

Пытался сравнивать config их ядер - ни бельмеса не понял в чем именно там разница. Она точно есть, но что конкретно? (с)

Интересная игра.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2

Под ArchLinux десять вызовов подряд ~1.5s все
Под VoidLinux(musl) стабильно ~1.7s

Кажется понял. В Arch ядро такое: 

CONFIG_TRANSPARENT_HUGEPAGE_ALWAYS=y
# CONFIG_TRANSPARENT_HUGEPAGE_MADVISE is not set
А в Void наоборот.

Соответственно Void не использует Huge Page при mmap того файла на 13ГБ.

В Arch после каждого вызова увеличивается счётчик thp_file_mapped в /proc/vmstat, а в Void там всё по нулям.

Toxo2 ★★★★
()

Без извращений получается достигнуть скорости в 72 секунды

(defpackage #:bcl
  (:use #:cl :lparallel :str)
  (:export #:main))

(in-package #:bcl)

;; Немножко оптимизации
(declaim (optimize (speed 3) (safety 0) (debug 0)))

(defun list-of-int-p (list)
  "Return t if LIST is non nil and contains only ints."
  (and (consp list)
       (every #'integerp list)))

(deftype name ()
  `(satisfies list-of-ints-p))

(defun measure-p (measure)
  "Return t if meausre is a pair (name . single-float)"
  (and (consp measure)
       (list-of-int-p (car measure))
       (floatp (cdr measure))))
(deftype measure ()
  `(satisfies measure-p))

;; станция и операции с нею

(defstruct station
  (min 0.0 :type single-float)
  (max 0.0 :type single-float)
  (n 1 :type fixnum)
  (avg 0.0 :type single-float))

(declaim (inline update-station))
(defun update-station (station temperature)
  (declare (type station station))
  (declare (type single-float temperature))
  (make-station :min (min temperature (station-min station))
		:max (max temperature (station-max station))
		:n (1+ (station-n station))
		:avg (+ (station-avg station) temperature)))

(declaim (inline add-measure))
(defun add-measure (stations measure)
  (declare (type hash-table stations))
  (declare (type measure measure))
  (let* ((name (car measure))
	 (temperature (cdr measure))
	 (old-station (gethash name stations)))
    (setf (gethash name stations)
	  (if old-station (update-station old-station temperature)
	      (make-station :min temperature
			    :max temperature
			    :n 1
			    :avg temperature)))))

(defun add-station (stations name new-station)
    (let ((old-station (gethash name stations)))
      (setf (gethash name stations)
	    (if (not old-station) new-station
		(make-station
		 :min (min (station-min new-station) (station-min old-station))
		 :max (max (station-max new-station) (station-max old-station))
		 :n (+ (station-n new-station) (station-n old-station))
		 :avg (+ (station-avg new-station) (station-avg old-station)))))))

(defun merge-two-stations (stations1 stations2)
  (maphash
   #'(lambda (name station)
       (add-station stations1 name station))
   stations2)
  stations1)

;; вспомогайки для mmap
(defun mmap-file (path)
  (let ((fd (osicat-posix:open path (logior osicat-posix:o-rdonly))))
    (unwind-protect
         (let* ((size (osicat-posix:stat-size (osicat-posix:fstat fd)))
                (addr (osicat-posix:mmap (cffi:null-pointer) size
                                         (logior osicat-posix:prot-read)
                                         (logior osicat-posix:map-private)
                                         fd 0)))
           (values addr size))
      (osicat-posix:close fd))))

(defun munmap-file (addr size)
  (osicat-posix:munmap addr size))

(defmacro with-mmapped-file ((file addr size) &body body)
  (let ((original-addr (gensym "ADDR-"))
        (original-size (gensym "SIZE-")))
    `(multiple-value-bind (,addr ,size)
         (mmap-file ,file)
       (let ((,original-addr ,addr)
             (,original-size ,size))
         (unwind-protect
              (progn ,@body)
           (munmap-file ,original-addr ,original-size))))))

;; читаем байты, обновляем словарь, когда встречаем конец строки
(defun parse-chunk (addr start end)
  (let ((stations (make-hash-table :test 'equal))
	(temperature 0)
	(sign 0.1)
	(is-name t)
	is-not-begin
	name)
    (loop for idx = start then (1+ idx)
	  while (<= idx end)
	  do (let ((c (cffi:mem-aref addr :char idx)))
	       (cond
		 ((= c (char-code #\Newline)) ; конец числа, время собирать камни
		  (when is-not-begin	      ; проверка, вдруг отрезок начинается с \n
		      (add-measure stations (cons name (* sign temperature))))
		  (setf is-name t name nil temperature 0 sign 0.1)) ; обнуленіе
		 ((= c (char-code #\;))	; конец имени, дальше число
		  (setf is-name nil))
		 (is-name (push c name)) ; имя — список байтов
		 ((= c (char-code #\-)) ; встретили минус
		  (setf sign -0.1))
		 ((= c (char-code #\.)) ; точку пропускаем
		  (setf is-not-begin t)) ; вот, теперь мы точно не в начале
		 (t (setf temperature (+ (* 10 temperature) (- c 48)))))))
    stations))

;; нарезаем файл на примерно равные части, чтобы конец отрезка совпадал с концом строки
(defun next-newline (addr size start-idx)
  (if (> start-idx size) size
      (loop for idx = start-idx then (1+ idx)
	when (or (= 10 (cffi:mem-aref addr :char idx))
		 (>= idx size))
	  return (min idx size))))

(defun marker-begins (addr size step)
  (loop for idx = 0 then (next-newline addr size (+ idx step))
	until (>= idx size)
	collect idx))

(defun marker (addr size step)
  (let* ((begins (marker-begins addr size step))
	 (ends (append (cdr begins) (list size))))
    (mapcar #'cons begins ends)))


;; один поток для отладки, получаем список ((начало . конец)) и обрабатываем его
(defun run-single (path &key (step 16384))
  (with-mmapped-file (path addr size)
    (let ((pos (marker addr size step)))
      (mapcar #'(lambda (beg-end)
		  (let ((begin (car beg-end))
			(end (cdr beg-end)))
		    (parse-chunk addr begin end)
		    ))
	      pos))))


;; вспомогайки для lparallel
(defun init ()
  (setf *kernel* (make-kernel 8 :name "channel-queue-kernel")))
(defun shutdown ()
  (end-kernel :wait t))

;; обрабатываем отрезки паралельно, потом объединяем
(defun run (path &key (step 16384))
  (with-mmapped-file (path addr size)
    (let ((pos (marker addr size step)))
      (pmap-reduce
       #'(lambda (beg-end)
	   (parse-chunk addr (car beg-end) (cdr beg-end)))
       #'merge-two-stations
       pos))))

;; побайтовое чтение портит юникод, для красивой печати приходится восстанавливать
(defun bytes2name (b-list)
  (fix-unicode-string
   (coerce
    (reverse (mapcar #'code-char b-list))
    'string)))

(defun print-stations (stations)
  (let* ((raw-keys (alexandria:hash-table-keys stations))
	 (keys (mapcar
		#'(lambda (seq)
		    (cons seq (flexi-streams:octets-to-string (reverse seq) :external-format :utf-8)))
		raw-keys))
	 (sorted-keys (sort keys #'(lambda (s1 s2) (string-lessp (cdr s1) (cdr s2))))))
    (format t "{")
    (mapcar #'(lambda (name)
		(let* ((key (car name))
		       (correct-name (cdr name))
		       (station (gethash key stations))
		       (min-t (station-min station))
		       (max-t (station-max station))
		       (avg-t (/ (station-avg station) (station-n station))))
		  (format t "~a=~,1F/~,1F/~,1F " correct-name min-t avg-t max-t)))
	    sorted-keys)
    (format t "}~%")))

;; майн он и есть майн
(defun main ()
  (init)
  (print-stations
   (run (cadr sb-ext:*posix-argv*)
	:step (parse-integer (caddr sb-ext:*posix-argv*))))
  (shutdown))

Чтобы как-то улучшить нужно вместо нормального hash-map какое-нибудь трюкачество придумать. Это можно, но уже в следующей серии.

ugoday ★★★★★
()
Ответ на: комментарий от anonymous

Там внезапно другой лидер появился:
https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/one...

Вот его вариант, действительно, даже на моей слабенькой машинке 2 секунды делает.

Но внеконкурсный вариант С++:
https://github.com/lehuyduc/1brc-simd/blob/main/main.cpp

На этой же машинке всё равно в два раза быстрее. 1 секунда.

----

Крутые перцы. Вот те, кто такое может писать - те могут стоить >$10K в месяц. Те, кто хотя бы понимает всё, что там написано - >$1K в месяц. Остальным наблюдателям, как мне, просто не надо хотеть много денег. ИМХО.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2

Вот те, кто такое может писать - те могут стоить >$10K в месяц.

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

Status Feb 1: The challenge has been closed for new submissions … The final leader board will be published by Monday Feb 5.

Конкурс завершился, кстати. Результаты опубликуют 5 февраля, в понедельник.

anonymous
()
Ответ на: комментарий от Toxo2

import dask.dataframe as dd

Кстати, обнаружил тут давеча, что в nushell есть встроенная работа с dataframe. Так что в теории - можно даже без Питона. И на маленьком файле это даже работает в nu: 

let df = (dfr open --type 'csv' --delimiter ';' --no-header --lazy /home/Sources/1brc/measurements_10K.txt)

$df
	| dfr into-lazy
	| dfr group-by column_1
	| dfr agg [
		(dfr col column_2 | dfr max | dfr as "max"),
		(dfr col column_2 | dfr min | dfr as "min"),
		(dfr col column_2 | dfr mean | dfr as "mean"),
	]
	| dfr collect
только вот настоящий, большой, 13ти гигабайтный файл с данными оно даже открыть не может, закрывается с «Убито».

Но всё равно забавно. Ни про nushell, ни про dataframe ничего не слышал до этой игры.

Toxo2 ★★★★
()
Ответ на: комментарий от urxvt

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

alysnix ★★★
()
Ответ на: комментарий от urxvt

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

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

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

foror ★★★★★
() автор топика
Ответ на: комментарий от foror

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

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

alysnix ★★★
()
 ← 1 2 3 4 5 6 7 8 9 10 11 →
Development