четверг, 23 декабря 2010 г.

[prog.wow] Реализация от Дмитрия Вьюкова заняла первое место в конкурсе WideFinder!

Несколько лет назад Тим Брей организовал свой собственный бенчмарк на одной простенькой задачке – парсинге большого объема лог-файлов на многопроцессорной машине. И назвал это соревнование WideFinder.

Долгое время этот бенчмарк использовался в спорах функциональщиков со всем остальным миром как доказательство преимущества ФП в написании быстрых и которых программ. Поскольку на первых местах в начале были реализации на OCaml от Маурисио Фернандеза. Но потом подтянулись C++ники и всех порвали (по крайней мере по скорости работы) :)

А потом пришел Дмитрий Вьюков (aka remark) и порвал вааще всех, включая C++ников :) На чистом C ;)

Текущую таблицу результатов (со ссылками на исходники всех реализаций) можно посмотреть здесь: http://wikis.sun.com/display/WideFinder/Results

А вот как выглядит ее верхняя часть сейчас (Smart-Finder – это и есть вариант Димы):

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

21 комментарий:

Dmitry Vyukov комментирует...

Спасибо-спасибо!

Кстати, машина однопроцессорная, просто с 4 ядрами по 8 потоков.

Dmitry Vyukov комментирует...

Я думаю, если бы это был не UltraSPARC T2, а Intel Xeon, то можно было бы достичь такой же скорости на 1 потоке. Вот это бы было бы совсем весело и для интерпретации других результатов, и для осмысления многоядерности/многопоточности в целом.

Там диск выдаёт ~150MB/sec. Однопоточная версия выдаёт ~80MB/sec. Многопоточная ~230MB/sec (это из-за того, что 2/3 файла были закэшированы в RAM).

eao197 комментирует...

>Спасибо-спасибо!

Да ты только твори, а мы не устанем освещать твои успехи! :)

Unknown комментирует...

Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-) .

SAnty комментирует...

Молодец Дмитрий, так держать :)

Dmitry Vyukov комментирует...

> Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-)

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

Как следствие, на 10% это смотря по какому параметру мерить. По затраченному процессорному времени: с С++ разница 350%, с OCaml - >600%. Моя программа оставляет процессор практически не загруженным, т.е. параллельно можно делеать другую полезную работу. Другие программы пыжат процессор по полной, и тебе не останется ничего другово кроме как
на эти 10 минут пойти пить чай.

Да и по скорости у меня получается 47% со следующим конкурентом.

Да и помимо LOC так же есть время разработки, а вот тут программа, которая в 3 раза короче, пишется отнюдь не в 3 раза быстрее. На Ocaml и Clojure программы писались дольше, т.к. им приходилось сражаться с ветряными мельницами, а то время как я мог просто реализовывать то, что мне нужно.

eao197 комментирует...

@Dmitry Vyukov & Mastro Ombroj:

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

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

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

Dmitry Vyukov комментирует...

> Вторая -- это автоматическая биржевая торговля.

Они идут не только на размещение. Они идут на использзование ПЛИС, хаков с драйверами и ОС, и т.д.

Ещё третья мне кажется это игры. Прям за проценты там наверное не борятся, но 10-20% это уже весомо, значит можно увеличить фпс, сделать лучше эффекты или умнее интеллект. Не говоря уже о 50%.

eao197 комментирует...

>Ещё третья мне кажется это игры.

На счет игр я совсем не копенгаген.

Наверное еще одна ниша -- это телеком (всякие гигабайтные свичи и роутеры).

night beast комментирует...

MO>Ага, а размер кода отличается на порядок. При приросте скорости на десяток % :-) .

ждем вашей версии, которая даст больший прирост.

Miroslav комментирует...

непонятно причем тут языки :)
обычная IO-bound задача. Табличка рекордов четко прослеживает:
naive IO -> block IO -> async IO -> custom driver

Dmitry Vyukov комментирует...

> обычная IO-bound задача

Каким образом это IO-bound задача? Она IO-bound только для 3 топ результатов <=5 min (45GB/150MB/s=5min). Для остальных же она отнюдь не IO-bound. Да и там где она получается IO-bound, она IO-bound только после распараллеливания, т.к. 150MB/s там в одном потоке обрабатывать не получается.

Miroslav комментирует...

to DV
ок необычная но таки мы оба согласны что IO-bound :)

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

Про распараллеливание я конечно говорить могу но слушать это не надо :D

Dmitry Vyukov комментирует...

Кстати, забыл сказать. Я исследовал несколько вариантов: mmap, read, aio. Для однопоточной версии быстрее всего оказался aio. Однако для многопоточной версии я перешёл на обычный блокирующий read(). Кто-то там вроде и mmap использовал. Т.ч. прямо такой чёткой иерархии там нет. Дьявол как всегда в деталях. Возможно сыграло роль то, что на zfs нет нормальной поддержки для aio, т.ч. он просто создаёт 10 вспомогательных потоков, которым оффлоадит блокирующие операции.

Miroslav комментирует...

to DV:
стало любопытно какая у кода лицензия :) чтобы знать как баловаться. А то там таких слов нет. Я когда fannkuch-redux нагибал лицензию не забыл.

а aio это печаль да.

зы респект.

Dmitry Vyukov комментирует...

Я тоже не забыл - полный копирайт :) Зачем спешить?
Ну под GPL мне точно не жалко перевыложить, а дальше уже зависит.

Rustam комментирует...

Тоже поздравляю. Вообще удивительно что во всех этих небольших (это важно :) ) тестах не всегда C/C++ на первых местах стоят :)

Rustam комментирует...

@Dmitry Vyukov

Да и помимо LOC так же есть время разработки, а вот тут программа, которая в 3 раза короче, пишется отнюдь не в 3 раза быстрее. На Ocaml и Clojure программы писались дольше, т.к. им приходилось сражаться с ветряными мельницами, а то время как я мог просто реализовывать то, что мне нужно.

Ну реально в подобных задачах часто оптимальным по трудозатратам оказывается низкоуровневый код на С/C++ + логика на том же OCaml например. Я на такой смеси писал утилитки (требующие NT Native API) и по времени разработки и по потреблению ресурсов было лучше чем сплошной C++.

Miroslav комментирует...

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

To Rustam:
как уже выше было сказано задача не простая IO-bound чтобы добраться до потолка IO нужны потоки. Когда я проверял это в последний раз это был showstopper для Ocaml ;) Спорить о новых ненаписанных MLях я не буду так что можете не стараться.

Rustam комментирует...

@Myroslav Rubanets
Спорить не о чем. Тут доказать можно только написанием. У меня такого желания сейчас нет. Но потоки для OCaml не всегда showstopper, несколько процессов + разделяемая память часто спасают. Ну и я привык делать гибридные приложения в них еще меньше ограничений.

Dmitry Vyukov комментирует...

Сделал описание этого дела:
http://www.1024cores.net/home/scalable-architecture/wide-finder-2