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

Эталонно простодырая реализация на кложе, без никаких намёков на оптимизацию

(ns dev.1brc
  (:require [clojure.java.io :as io]
            [clojure.string :as s]))

(def scsv-split-regex
  "A regex to split the semicolon-separated line to fields."
  #";")

(defn read-file
  "Returns a lazy sequence of lines in the file."
  [filename]
  (line-seq (io/reader filename)))

(defn read-scsv-file
  "Returns a lazy sequence of measurements read from the file. A
  measurement is a vector of a station name and a floating-point
  measured value."
  [filename]
  (->> (read-file filename)
       (map #(s/split % scsv-split-regex))
       (map #(update % 1 parse-double))))

(defn moving-average
  "Returns cumulative moving average given previous average, the count
  of values used to compute it, and the new value. See
  https://en.wikipedia.org/wiki/Moving_average#Cumulative_moving_average"
  [average count value]
  (/ (+ value (* average count)) (inc count)))

(defn update-station-stats
  "Returns the map containing stats of some station updated with the
  given measured value."
  [{:keys [count minimum maximum average]} value]
  {:count   (inc count)
   :minimum (min minimum value)
   :maximum (max maximum value)
   :average (moving-average average count value)})

(defn update-total-stats
  "Returns the map of station stats updated with the result of updating
  the stats of the given station with the given measured value."
  ([] {})
  ([acc] acc)
  ([acc [key value]]
   (update acc key (fnil update-station-stats
                         {:count 0 :minimum value :maximum value :average value}) value)))

(defn stats
  "Returns the map of station stats keyed by station names, obtained by
  reducing the sequence of measurements."
  [measurements]
  (reduce update-total-stats {} measurements))

(defn format-stats
  "Returns the map of station stats, sorted lexicographically by key."
  [stats]
  (into (sorted-map) stats))

(comment

  ;; 10^6 lines: 1.2 sec 
  (time (format-stats (stats (read-scsv-file "dev/resources/measurements1M.txt"))))

  ;; 10^9 lines: 1300 sec (~20 min)
  (time (format-stats (stats (read-scsv-file "dev/resources/measurements.txt"))))

)

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

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

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

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

Хорошая задача, но я - пас) Хешмап не подойдёт?

1300 sec

Неплохо. Лайк 👍️

Можно лучше чем хэшмап (кажется).

Хотя да, нафига там хешмап, если можно просто массив вершин со связями. Удалённые в какой-нибудь стек можно складывать)

Там перемеряли на новом проце

32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM

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

Единственное, что пока более-менее помогло — это трансдьюсеры для разбора строк вместо threading macros (процентов на 15-20, с 20 мин до 17):

;; using transducers

(def line->measurement
  "Transforms a reducing function to coerce its input values from
  strings to measurements (vectors of a station name and a
  floating-point value)."
  (comp
   (map #(s/split % scsv-split-regex))
   (map #(update % 1 parse-double))))

(defn transducing-stats
  "Returns the map of station stats keyed by station names, obtained by
  transducing (reducing with transformation of the reducing function)
  the sequence of lines."
  [lines]
  (transduce line->measurement update-total-stats lines))


(comment

  ;; 10^6 lines: ~1 sec
  (time (format-stats (transducing-stats (read-file "dev/resources/measurements1M.txt"))))

  ;; 10^9 lines: ~1000 sec (~17 min)
  (time (format-stats (transducing-stats (read-file "dev/resources/measurements.txt"))))

)

Кстати, на этой задаче можно реально ощутить разницу в производительности между компилируемой кложей и интерпретируемой бабашкой — 5-8 раз не в пользу бабашки.

Кстати, на этой задаче можно реально ощутить разницу в производительности между компилируемой кложей и интерпретируемой бабашкой — 5-8 раз не в пользу бабашки.

Если мы действительно в CPU упираемся: первое что бы я сделал - от’size’ил бы hash-табличку адекватно дабы re-hash не происходило. Я думаю - «в разы» отыграли бы «on the spot», не трогая ничего больше.

3 и 4 абзацы

https://www.bell-labs.com/usr/dmr/www/qed.html

а именно on the fly compiling

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

«суперкомпиляции»

Употребление магического слова без понимания detected. Partial evaluation давно никакая не магия. WPO где только нет, в том числе и под С++.

может завершится успехом раньше чем универсальное решение

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

В общем-то за меня ответил господин anonymous.

от’size’ил бы hash-табличку адекватно дабы re-hash не происходило

Там мапы иммутабельные, для них это вроде как не актуально.

Впрочем, замена на мутабельные жабные хэшмапы всё равно пользы не приносит:

;; using mutable Java hashmaps

(def default-hashmap-load-factor
  "Load factor value used by default to create Java hashmaps."
  0.75)

(def station-stats-map-capacity
  "Initial capacity of a hashmap that holds station stats (always 4 keys).
  Should be high enough to avoid rehashing."
  (int (Math/ceil (/ 4 default-hashmap-load-factor))))

(def total-stats-map-capacity
  "Initial capacity of a hashmap that holds total stats (number of keys
  is the number of stations --- 413). Should be high enough to avoid
  rehashing."
  (int (Math/ceil (/ 413 default-hashmap-load-factor))))

(defn update-station-stats-mutable!
  "Returns the mutable Java hashmap containing stats of some station
  updated with the given measured value."
  [{:keys [count minimum maximum average] :as station-stats} value]
  (doto ^java.util.HashMap station-stats
    (.put :count (inc count))
    (.put :minimum (min minimum value))
    (.put :maximum (max maximum value))
    (.put :average (moving-average average count value))))

(defn update-total-stats-mutable!
  "Returns the mutable Java hashmap containing total stats updated with
  the result of updating the stats of the given station with the given
  measured value."
  ([] (java.util.HashMap. ^int total-stats-map-capacity))
  ([acc] acc)
  ([acc [key value]]
   (doto ^java.util.HashMap acc
     (.put key
           ((fnil update-station-stats-mutable!
                  (doto (java.util.HashMap. ^int station-stats-map-capacity)
                    (.put :count 0)
                    (.put :minimum value)
                    (.put :maximum value)
                    (.put :average value)))
            (.get ^java.util.HashMap acc key)
            value)))))

(defn transducing-stats-mutable!
  "Returns the map of station stats keyed by station names, obtained by
  transducing (reducing with transformation of the reducing function)
  the sequence of lines."
  [lines]
  (transduce line->measurement update-total-stats-mutable! lines))

(comment

  ;; ~1 sec; the same as the simple transducing variant with Clojure's immutable maps

  (time (format-stats
         (transducing-stats-mutable! (read-file "dev/resources/measurements1M.txt"))))

)

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

;; using transients and arrays of primitives

;; profiler shows that updating stats maps (station and total) consumes most
;; of the time

;; - representing total stats as a transient map and updating it in-place
;; - representing station stats as an array of doubles and updating it in-place
;; - using type hints to avoid slow reflection calls

(defn update-station-stats!
  "Returns an array of doubles containing stats of some station updated
  with the given measured value."
  [^doubles [count minimum maximum average :as station-stats] ^double value]
  (doto ^doubles station-stats
    (aset 0 ^double (unchecked-inc count))
    (aset 1 ^double (min minimum value))
    (aset 2 ^double (max maximum value))
    (aset 3 ^double (moving-average average count value))))

(defn update-total-stats!
  "Returns the (transient) map of station stats updated with the result
  of updating the stats of the given station with the given measured
  value."
  ([] (transient {}))
  ([acc] acc)
  ([acc [key value]]
   (assoc! acc
           key
           ((fnil update-station-stats!
                  (double-array [0.0 value value value]))
            (acc key)
            value))))

(defn transducing-stats!
  "Returns the map of station stats keyed by station names, obtained by
  transducing (reducing with transformation of the reducing function)
  the sequence of lines."
  [lines]
  (persistent! (transduce line->measurement update-total-stats! lines)))

(defn format-stats-1
  "Returns the map of station stats (converted to maps from arrays of doubles),
  sorted lexicographically by key."
  [stats]
  (into (sorted-map) (map (fn [[key [count minimum maximum average]]]
                            [key {:count   count
                                  :minimum minimum
                                  :maximum maximum
                                  :average average}]) stats)))

(comment

  ;; the same as the baseline (or slightly worse), worse than the simple
  ;; transducing variant by ~30%

  ;; ~1.3 sec
  (time (format-stats-1
         (transducing-stats! (read-file "dev/resources/measurements1M.txt"))))

)

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

Впрочем, замена на мутабельные жабные хэшмапы всё равно пользы не приносит

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

который?

Пацаны с Оракла залезли на первую строчку с 3.044 секундами.

Там между твоим и моим сообщениямм два сообщения от одного юзера.

натянуть мутабельность на жадную итерацию

Действительно слегка быстрее.

;; using manual looping and mutable hashmaps

(defn looping-stats-mutable!
  "Returns the map of station stats keyed by station names.
  Reads a semicolon-separated file with measurement records eagerly
  line by line, parses each line into a measurement (station name and
  measured value) and updates the corresponding station's stats using
  the value. Uses mutable hashmaps to store total and station stats."
  [filename]
  (let [rdr (io/reader filename)]
    (loop [stats (java.util.HashMap.)]
      (if-let [line (.readLine ^java.io.BufferedReader rdr)]
        (let [[key string-value] (s/split line scsv-split-regex)
              value              (parse-double string-value)
              {:keys [count minimum maximum average] :as key-stats}
              (or (.get ^java.util.HashMap stats key)
                  (doto (java.util.HashMap.)
                    (.put :count 0)
                    (.put :maximum value)
                    (.put :minimum value)
                    (.put :average value)))
              updated-key-stats
              (doto ^java.util.HashMap key-stats
                (.put :count (inc count))
                (.put :minimum (min minimum value))
                (.put :maximum (max maximum value))
                (.put :average (moving-average average count value)))]
          (recur (doto stats (.put key updated-key-stats))))
        stats))))

(comment

  ;; ~50% better than baseline (and ~30% better than the transducing variant)

  ;; ~0.7 sec
  (time (format-stats (looping-stats-mutable! "dev/resources/measurements1M.txt")))

  ;; ~750 sec (~12 min)
  (time (format-stats (looping-stats-mutable! "dev/resources/measurements.txt")))

)

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

Большую долю прироста дает отказ от String как такого. Среднее можно не считать на каждой итерации.

Большую долю прироста дает отказ от String как такого.

Похоже на то. Когда я попытался полностью прочитать 14-гигабайтный файл в память (в последовательность строк), 64 Гб памяти жабе не хватило.

Среднее можно не считать на каждой итерации.

Но тогда ведь придётся хранить всю последовательность измеренных значений для каждой станции в памяти, чтобы посчитать среднее в конце? Ах вот зачем им 128 Гб памяти понадобилось %)

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

Но тогда ведь придётся хранить всю последовательность измеренных значений для каждой станции в памяти, чтобы посчитать среднее в конце? Ах вот зачем им 128 Гб памяти понадобилось %)

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

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

Может и так.

Страсти-то какие. Это же не наш метод! Я предлагаю зайти с другой стороны:

1. Не превращать наш прекрасный лиспик в убогое подобие С++. И элегантность растеряем и по скорости всё равно отстанем.
2. По возможности не напрягаться и использовать стандартные компоненты.
3. Просто распаралелить по данным, а каждый поток данных считать последовательно. Потом слить результаты.
4. Читать файл кусочками, искать там переводы строк и следить, чтобы нигде не продолбаться с индексами уныло и скучно. Но всеблагой Господь послал нам утилиту split, которая заранее нам разрежет исходный большой файл на тысячу маленьких. После чего

(ns ubrc.simple
  (:require
   [clojure.string :as str]))

(defn merge-two-stations [station1 station2]
  {:min (min (:min station1) (:min station2))
   :max (max (:max station1) (:max station2))
   :n (+ (:n station1) (:n station2))
   :t (/ (+ (* (:n station1) (:t station1)) (* (:n station2) (:t station2)))
         (+ (:n station1) (:n station2)))})

(defn update-station [station temperature]
  (let [n (:n station)
        n1 (inc n)
        average-temperature (:t station)
        new-average (/ (+ temperature (* n average-temperature)) n1)]
    {:min (min (:min station) temperature)
     :max (max (:max station) temperature)
     :n n1 :t new-average}))

(defn new-station [temperature]
  {:min temperature
   :max temperature
   :n 1 :t temperature})

(defn get-new-station [station temperature]
  (if station (update-station station temperature)
               (new-station temperature)))

;; stations example    -- {:Test {:min -4, :max 32, :n 2, :t 2.2} :Milan {:min 2, :max 22, :n 1, :t 8.7}}
;; new-station example -- {:Test 3.3}
(defn add-station [stations new-station]
  (let [name (first (keys new-station))
        temperature (get new-station name)
        station (get stations name)
        new-station (get-new-station station temperature)]
    (assoc stations name new-station)))

(defn parse-station [station]
  (let [arr (str/split station #";")
        name (first arr)
        t (read-string (second arr))]
    {(keyword name) t}))

(defn read-file [file-name]
  (str/split (slurp file-name) #"\n"))

(defn iter [file-name]
  (let [seq (read-file file-name)]
    (reduce add-station {} (map parse-station seq))))

(defn run [files]
  (let [dbs (pmap iter files)]
    (reduce #(merge-with merge-two-stations %1 %2)
            dbs)))

(print-result (simple/run dataFiles))

Результат выходит на уровне

java -jar /home/ig/tmp/ubrc/target/uberjar/ubrc-0.1.0-SNAPSHOT-standalone.jar  4887.45s user 77.95s system 933% cpu 8:52.01 total

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

На эту тему есть популярный ролик - просвещайтесь!

На эту тему есть популярный ролик - просвещайтесь!

О чем просвещаться? Я в курсе про M1076ES, а также про то почему он не взлетел.

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

Т.е. YOLOv3, ResNet-18 или Body25 он потянет, что-то более серьезное - нет. Этот чип позволяет использовать до 80 миллионов параметров. Тот же YOLOv3 в базе работает с разрешением 416×416 пикселей и имеет около 65 миллионов параметров.

1920x1080 никак не умещается в 80 миллионов. Какой бы он там аналоговый не был.

То что показано в ролике это OpenPose Body25 - сеть распознающая человеческую позу, но не человека. Машите ветками и она будет распознавать их как руки. Ей уже лет 7 если не ошибаюсь, если не больше.

Они попытались сделать более простой аналог китайских Hailo-15 которые могут переваривать видео в 4К, но там и обвязка и выделение тепла больше.

64 Гб памяти жабе не хватило.

Я не удивлён. Если я ничего не путаю - стринги в джаве юникодные, не (даже без учёта других накладных расходов, коих предостаточно)?

посчитать среднее в конце?

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

Господь послал нам утилиту split, которая заранее нам разрежет исходный большой файл на тысячу маленьких.

Даже если отбросить моё отношение к конкретно этой идее как довольно маразматичной (по многим причинам), мы так можем договориться до того что весь math будет двинут в условный prep-stage, и тулзня сведётся к «cat results.txt». И выше я уже озвучивал что как по мне так даже многократное чтение при benchmarking (не говоря даже о предварительном двигании данных на более быстрый носитель, типа tmpfs как предлагали до этого) - уже чит.

распаралелить по данным

Мне тоже думается, что pmap/reduce тут должен довольно сильно помочь, но предварительный сплит вроде как слегка не по правилам получается. Вот если бы найти способ на лету быстро разбить файл на эн сегментов (да ещё и с учётом строк, чтобы границы сегментов не оказывались посреди строки)…

[seq (str/split (slurp file-name) #«\n»)]

Может ведь получиться, что весь 14-гигабайтный файл будет в какой-то момент времени находиться в памяти? По идее, (line-seq (clojure.java.io/reader file-name)) должно быть помилосерднее по потреблению памяти — а может, и по скорости.

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

Там на Go вариант у товарища.
https://github.com/jkroepke/1brc-go/tree/main/go

Он там пилит куски по потокам как-то так:

	    data = data[workerSize*workerID : last]
	    data = data[bytes.IndexByte(data, '\n')+1 : bytes.LastIndexByte(data, '\n')+1]

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

Вполне прилично получается. В районе тех же 3 секунд на прокаченном в кэш файле и около 6 секунд после echo 3 > /proc/sys/vm/drop_caches

можем договориться до того что весь math будет двинут в условный prep-stage

Просто не делайте этого.

Там на Go вариант у товарища.
https://github.com/jkroepke/1brc-go/tree/main/go

Обычно, для определения размера сегмента там делают:

while (segment[size - 1] != '\n') {
    size--;
}

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

Тем не менее, это нарушает условия конкурса.

это нарушает условия конкурса.

Так всё, что не на Java, сразу нарушает условия конкурса по определению.

Забавно же смотреть какие штуки народ придумывает всё равно )

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

Безусловно. Мы же можем читать файл в произвольном месте. Так что можем сделать первый проход, в котором прыгать в середину файла и искать ближайший конец строки, после чего возвращать размеченные области для паралельной обработки. Но даже словами это писать дольше, нежели выполнить split -l N BigFile.txt.

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

(line-seq (clojure.java.io/reader file-name))

Имеет смысл попробовать, да.

Забавно же смотреть какие штуки народ придумывает всё равно )

В решении Шипилева целый флаг есть, который подобные читы включает. :)

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

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

цифры и их «честность» безразличны, всё равно я ни с кем не соревнуюсь

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

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

В репу конкурса ещё неделю назад добавили новый генератор, который выдаёт 10000 рандомных имён станций (изначально станций было всего 413), размером от 1 до 100 байт, комбинируя 41343 уникальных имени или их части из файла weather_stations.csv.

// Use a 7th-order curve to simulate the name length distribution.
// It gives us mostly short names, but with large outliers.

Алгоритм генерации температур тоже изменился.

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

время на сплит надо тоже включить в общее время работы.

Непонятно как учесть, что split кроме нахождения границ разбиения ещё и создаёт тысячу файлов по 14Мб. Проще использовать готовый набор файлов и сравнивать разные подходы при работе с ними. Вот, к слову, решил реализовать тот же алгоритм на SBCL

(ql:quickload "uiop")
(ql:quickload :parse-float)
(ql:quickload "alexandria")
(ql:quickload "lparallel")

(defpackage :blc-challenge
  (:use :cl :lparallel :lparallel.queue)
  (:export #:main))

(in-package :blc-challenge)

(defun init ()
  (setf *kernel* (make-kernel 8 :name "channel-queue-kernel")))

(init)


(declaim (optimize (speed 3) (safety 0)))

(defparameter dataDir "~/src/github.com/gunnarmorling/1brc/data")
(defparameter dataFiles (remove-if-not #'(lambda (path) (uiop:string-prefix-p "x" (file-namestring path))) (uiop:directory-files dataDir)))

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

(defun parse-station (l)
  (let ((station (uiop:split-string l :max 2 :separator ";")))
    (cons (intern (car station))
	  (parse-float:parse-float (cadr station)))))

(defun new-avg (temperature n average-temperature)
  (/ (+ temperature (* n average-temperature)) (1+ n)))

(defun updated-station (station temperature)
  (make-station :min (min temperature (station-min station))
		:max (max temperature (station-max station))
		:n (1+ (station-n station))
		:avg (new-avg temperature (station-n station) (station-avg station))))


(defun add-station (db station)
  (let* ((station-name (car station))
	 (temperature (cdr station))
	 (old-station (gethash station-name db)))
    (setf (gethash station-name db)
	  (if old-station (updated-station old-station temperature)
	      (make-station :min temperature
			    :max temperature
			    :n 1
			    :avg temperature)))))

(defun iter (file-name)
  (let ((db (make-hash-table :size 413)))
    (with-open-file (in file-name)
	    (loop for l = (read-line in nil nil)
		  while l
		  do (add-station db (parse-station l))))
    db))

(defun merge-two-stations (db1 db2)
  (maphash #'(lambda (name station2)
		    (let* ((station1 (gethash name db1))
			   (new-station
			     (make-station :min (min (station-min station1)
						     (station-min station2))
					   :max (max (station-max station1)
						     (station-max station2))
					   :n (+ (station-n station1) (station-n station2))
					   :avg (/ (+ (* (station-n station1) (station-avg station1))
						      (* (station-n station2) (station-avg station2)))
						   (+ (station-n station1) (station-n station2))))))
		      (setf (gethash name db1) new-station)))
	   db2)
  db1)

(defun merge-stations (stations)
  (reduce #'merge-two-stations stations))

(defun print-station (name station)
  (format nil "~a=~,1F/~,1F/~,1F"
	  name (station-min station) (station-avg station) (station-max station)))

(defun print-stations (stations)
  (let* ((names (sort
		(mapcar #'string
			(alexandria:hash-table-keys stations))
		#'string-lessp))
	 (statistics (loop for name in names
			   collect (print-station name (gethash (intern name "COMMON-LISP-USER") stations)))))
    (format t "{~{~A~^ ~}}~%" statistics)))

(defun run (files)
  (merge-stations (pmapcar #'iter files)))

(defun main ()
  (print-stations (run dataFiles)))

(time (main))
;; лишние строки не показаны
Evaluation took:
  219.599 seconds of real time
  1690.001351 seconds of total run time (1675.769479 user, 14.231872 system)
  [ Real times consist of 5.983 seconds GC time, and 213.616 seconds non-GC time. ]
  [ Run times consist of 5.861 seconds GC time, and 1684.141 seconds non-GC time. ]
  769.59% CPU
  569,191,774,868 processor cycles
  51 page faults
  349,112,268,000 bytes consed

Три с половиной минуты против почти 9 у Clojure. Может надо с JVM как-то пошаманить?

Я тут это … заморочился и написал на фортране. Страдал 3 дня; вроде как имею неплохой опыт с фортраном, но много подводных камней. Одна из вишенок на торте: чтобы перевести температуру в число сначала использовал стандартную процедуру типа readstr. Считало минуты на 100М-файле. Переписал руками, время сократилось кратно.

В итоге ммаплю файл, параллельность за счет OpenMP. Результат таков:

ergeis@sergeis-pc1850:~/Projects/fortran_file_mmap$ time ./test_mmap 
Storage sizes for char, int(1), int(2), int, int(4), real [bits]: 
                    8     8      16      64    32     32
 File 'measurements.txt' has size           13795786022  bytes

real	0m18.171s
user	4m11.398s
sys	0m0.988s

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

На моем компе С-программа от anonymous (1 поток; но несколько старая версия) на холодном старте дает real 0m22.901s

Три с половиной минуты против почти 9 у Clojure. Может надо с JVM как-то пошаманить?

Я тут слепил на коленке разбиение файла на эн логических сегментов (без физического деления на несколько файлов) и скармливание их pmapу для обработки (пока без объединения результатов). Ревело кулером, нагрело проц до 72 градусов, зато отработало за 4.5 минуты %)

Надо будет допилить да off-by-one ошибки повыловить.

Это без всяких мутабельных ухищрений и жадных итераций — иммутабельные мапы, ленивые последовательности, всё как мы любим.

Уф, круто! 👍️ На 32 тредах попал бы в топ-30, мне кажется.

Кстати, мой вариант, кроме того, что написан не на Java, не соблюдает ещё вот такое условие конкурса:

Input value ranges are as follows: Station name: non null UTF-8 string of min length 1 character and max length 100 bytes, containing neither ; nor \n characters. (i.e. this could be 100 one-byte characters, or 50 two-byte characters, etc.)

Q: Can I make assumptions on the names of the weather stations showing up in the data set?

A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no ; or \n characters).

То есть, по условиям, имена станций могут быть любыми, до 100 байтов длиной. У меня же там хеш без коллизий подобран под конкретный набор станций из create_measurements.sh. Читер, что ещё сказать)

У меня же там хеш без коллизий подобран под конкретный набор станций из create_measurements.sh. Читер, что ещё сказать)

На самом деле, ничего плохого в подборе hasher’а на representable sample я не вижу, до тех пор пока benchmark run делается на другом заранее неизвестном dataset. Более того - самому приходилось этим заниматься, скажем так - более одного раза. Ну, и с размером таблички, как по мне, тоже жадничать не стоит: один из способов бороться с коллизиями это её раздвинуть - load factor of 75% is too much, imho.

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

наглядно показал, что на кложуре только прототипировать хорошо такие задачи

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

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

Самое интересное начнётся, когда (не если, а когда) требования изменятся. Тогда станет ясно (кому-то в первый раз), в чём преимущество понятных, общих, поддающихся доработке решений перед write-only узкоспециализированными байтодробилками, целиком построенными на допущениях, сделанных для конкретных требований или даже для конкретного набора данных. Общее решение можно доработать, дробилку придётся постоянно переписывать заново.

Конечно, к олимпиадно-развлекательным задачам это практически не относится, но жызнь ведь состоит не только из развлечений, правда? %)

пока benchmark run делается на другом заранее неизвестном dataset

Ну так выходит, что заранее-то датасет для провереки и не определён. Это может быть любая UTF-8 последовательность от 1 до 100 байт. Я бы посмотрел как затрещали бы хеши, если бы авторы челенджа стали полным рандомом генерировать имена станций. Условия этого не запрещают:

any solution should work with arbitrary UTF-8 station names

Попробуй-ка эффективно запихни 50 гигов рандома в какую-нибудь хеш табличку)

А, не, всё нормально, затрещал пока что лишь мой камент)

There is a maximum of 10,000 unique station names

И ещё вот такое уточнение:

Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant), using 8 cores of the machine.

То есть запускают лишь на 8 ядрах из 32.

Попробуй-ка эффективно запихни 50 гигов рандома в какую-нибудь хеш табличку)

Опасно! Не заметишь, как половину MySQL реализуешь (как обычно кривую, тормозную и недокументированную).

Это может быть любая UTF-8 последовательность от 1 до 100 байт.

Вовсе не обязательно их разбирать как UTF-8, можно к этому относится как к массиву байт. Максимум нормализовать в конце.

Попробуй-ка эффективно запихни 50 гигов рандома в какую-нибудь хеш табличку)

Я бы посмотрел как затрещали бы хеши

Это всё мелочи. Бывает гораздо хуже. Если поток который нужно прожевать в real-time в гигабитах измеряется (после всех сглаживаний) - всё реально становится весело.

чё будет с именами станций в юникоде?

Сортировка может пострадать походу.

Из стандарта Unicode, страница 38:

A binary sort of UTF-8 strings gives the same ordering as a binary sort of Unicode code points.

Вовсе не обязательно их разбирать как UTF-8, можно к этому относится как к массиву байт.

Полностью согласен. Даже не уверен в необходимости нормализации. В условиях конкурса значится «sorted alphabetically». Нужно ли перед алфавитной сортировкой нормализовывать Юникод?

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