Несколько лет назад Тим Брей организовал свой собственный бенчмарк на одной простенькой задачке – парсинге большого объема лог-файлов на многопроцессорной машине. И назвал это соревнование WideFinder.
Долгое время этот бенчмарк использовался в спорах функциональщиков со всем остальным миром как доказательство преимущества ФП в написании быстрых и которых программ. Поскольку на первых местах в начале были реализации на OCaml от Маурисио Фернандеза. Но потом подтянулись C++ники и всех порвали (по крайней мере по скорости работы) :)
А потом пришел Дмитрий Вьюков (aka remark) и порвал вааще всех, включая C++ников :) На чистом C ;)
Текущую таблицу результатов (со ссылками на исходники всех реализаций) можно посмотреть здесь: http://wikis.sun.com/display/WideFinder/Results
А вот как выглядит ее верхняя часть сейчас (Smart-Finder – это и есть вариант Димы):
К моему сожалению о рекорде, который был установлен еще в марте, я узнал только сейчас. Поэтому хоть и с опозданием, но с удовольствием поздравляю Диму с этим замечательным достижением!
Спасибо-спасибо!
ОтветитьУдалитьКстати, машина однопроцессорная, просто с 4 ядрами по 8 потоков.
Я думаю, если бы это был не UltraSPARC T2, а Intel Xeon, то можно было бы достичь такой же скорости на 1 потоке. Вот это бы было бы совсем весело и для интерпретации других результатов, и для осмысления многоядерности/многопоточности в целом.
ОтветитьУдалитьТам диск выдаёт ~150MB/sec. Однопоточная версия выдаёт ~80MB/sec. Многопоточная ~230MB/sec (это из-за того, что 2/3 файла были закэшированы в RAM).
>Спасибо-спасибо!
ОтветитьУдалитьДа ты только твори, а мы не устанем освещать твои успехи! :)
Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-) .
ОтветитьУдалитьМолодец Дмитрий, так держать :)
ОтветитьУдалить> Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-)
ОтветитьУдалитьПридётся защищаться :)
Во-первых, тут скорость ограничена IO, ставь больше дисков моя версия будет быстрее, большинство остальных - нет.
Как следствие, на 10% это смотря по какому параметру мерить. По затраченному процессорному времени: с С++ разница 350%, с OCaml - >600%. Моя программа оставляет процессор практически не загруженным, т.е. параллельно можно делеать другую полезную работу. Другие программы пыжат процессор по полной, и тебе не останется ничего другово кроме как
на эти 10 минут пойти пить чай.
Да и по скорости у меня получается 47% со следующим конкурентом.
Да и помимо LOC так же есть время разработки, а вот тут программа, которая в 3 раза короче, пишется отнюдь не в 3 раза быстрее. На Ocaml и Clojure программы писались дольше, т.к. им приходилось сражаться с ветряными мельницами, а то время как я мог просто реализовывать то, что мне нужно.
@Dmitry Vyukov & Mastro Ombroj:
ОтветитьУдалитьЯ слышал про две прикладные ниши, в которых выигрыш в скорости всего в несколько процентов уже велик. Первая -- это вычисления на суперкомпьютерах, которы сдаются в аренду и стоимость одной минуты машинного времени исчисляется тысячами долларов. Чем быстрее проходит вычислительный эксперимент, тем выгоднее это арендаторам.
Вторая -- это автоматическая биржевая торговля. Там идут даже на то, чтобы размещать компьютеры прямо на площадках биржи, чтобы не иметь временных задержек на передачу данных даже на несколько киллометров.
В таких условиях количество строк уже не так существенно, как выигрыш в производительности, который они могут дать.
> Вторая -- это автоматическая биржевая торговля.
ОтветитьУдалитьОни идут не только на размещение. Они идут на использзование ПЛИС, хаков с драйверами и ОС, и т.д.
Ещё третья мне кажется это игры. Прям за проценты там наверное не борятся, но 10-20% это уже весомо, значит можно увеличить фпс, сделать лучше эффекты или умнее интеллект. Не говоря уже о 50%.
>Ещё третья мне кажется это игры.
ОтветитьУдалитьНа счет игр я совсем не копенгаген.
Наверное еще одна ниша -- это телеком (всякие гигабайтные свичи и роутеры).
MO>Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-) .
ОтветитьУдалитьждем вашей версии, которая даст больший прирост.
непонятно причем тут языки :)
ОтветитьУдалитьобычная IO-bound задача. Табличка рекордов четко прослеживает:
naive IO -> block IO -> async IO -> custom driver
> обычная IO-bound задача
ОтветитьУдалитьКаким образом это IO-bound задача? Она IO-bound только для 3 топ результатов <=5 min (45GB/150MB/s=5min). Для остальных же она отнюдь не IO-bound. Да и там где она получается IO-bound, она IO-bound только после распараллеливания, т.к. 150MB/s там в одном потоке обрабатывать не получается.
to DV
ОтветитьУдалитьок необычная но таки мы оба согласны что IO-bound :)
мое личное фэ к таким задачам в том что мне надо кроссплатформа. Про драйверы я молчу, но async эти вендоро-редиски могли бы и подумать.
Про распараллеливание я конечно говорить могу но слушать это не надо :D
Кстати, забыл сказать. Я исследовал несколько вариантов: mmap, read, aio. Для однопоточной версии быстрее всего оказался aio. Однако для многопоточной версии я перешёл на обычный блокирующий read(). Кто-то там вроде и mmap использовал. Т.ч. прямо такой чёткой иерархии там нет. Дьявол как всегда в деталях. Возможно сыграло роль то, что на zfs нет нормальной поддержки для aio, т.ч. он просто создаёт 10 вспомогательных потоков, которым оффлоадит блокирующие операции.
ОтветитьУдалитьto DV:
ОтветитьУдалитьстало любопытно какая у кода лицензия :) чтобы знать как баловаться. А то там таких слов нет. Я когда fannkuch-redux нагибал лицензию не забыл.
а aio это печаль да.
зы респект.
Я тоже не забыл - полный копирайт :) Зачем спешить?
ОтветитьУдалитьНу под GPL мне точно не жалко перевыложить, а дальше уже зависит.
Тоже поздравляю. Вообще удивительно что во всех этих небольших (это важно :) ) тестах не всегда C/C++ на первых местах стоят :)
ОтветитьУдалить@Dmitry Vyukov
ОтветитьУдалитьДа и помимо LOC так же есть время разработки, а вот тут программа, которая в 3 раза короче, пишется отнюдь не в 3 раза быстрее. На Ocaml и Clojure программы писались дольше, т.к. им приходилось сражаться с ветряными мельницами, а то время как я мог просто реализовывать то, что мне нужно.
Ну реально в подобных задачах часто оптимальным по трудозатратам оказывается низкоуровневый код на С/C++ + логика на том же OCaml например. Я на такой смеси писал утилитки (требующие NT Native API) и по времени разработки и по потреблению ресурсов было лучше чем сплошной C++.
кстати забыл сказать спасибо за пост :)
ОтветитьУдалитьжаль что я прозевал этот бенчмарк - настолько красочно показать яму в которой умерла сановская платформа - это надо уметь.
To Rustam:
как уже выше было сказано задача не простая IO-bound чтобы добраться до потолка IO нужны потоки. Когда я проверял это в последний раз это был showstopper для Ocaml ;) Спорить о новых ненаписанных MLях я не буду так что можете не стараться.
@Myroslav Rubanets
ОтветитьУдалитьСпорить не о чем. Тут доказать можно только написанием. У меня такого желания сейчас нет. Но потоки для OCaml не всегда showstopper, несколько процессов + разделяемая память часто спасают. Ну и я привык делать гибридные приложения в них еще меньше ограничений.
Сделал описание этого дела:
ОтветитьУдалитьhttp://www.1024cores.net/home/scalable-architecture/wide-finder-2