Автор Тема: Расширенный тест на производительность.  (Прочитано 105885 раз)

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Ну, простые тесты на производительность уже были, это уже скучно. Теперь давайте что-то более сложное, что-то более приближенное к реальности.

Если на некотором ЯП результаты этого теста будут очень плохи, значит скорее всего на этом ЯП и ядро СУБД нормально реализовать не получится (либо это потребует очень больших усилий). Т.е. этот тест для, так называемых, ЯП претендующих на звание системных. По сути, тест на профпригодность ЯП на звание системного.

Итак задача:

Есть файл input в нем содержится массив целых беззнаковых 32битных чисел (ака uint32_t) в бинарном little endian виде. После завершения выполения приложения, должен быть файл output где в том же формате был бы записан отсортированный по возрастанию этот массив.

Теперь детали:
  • На машине 128 Мб памяти (и нет свопа).
  • Файл большой - в ОЗУ точно не поместится
  • На диске есть место для временных файлов
  • Операционная система - скорее всего какой-то *nix.
  • Диск SSD, не HDD
  • Машина скорее всего 64битная, но может быть и 32битной
  • Машина двуядерная

Теперь следствия нюансов:
Решение может быть реализовано под наиболее вероятную конфигурацию машины (64 bit'ный *nix). Но возможность писать кроссплатформенно также ценится, поэтому будет две номинации:
  • Самое быстрое решение
  • Самое быстрое кроссплатформенное решение

В данном случае кроссплатформенность означает, что программа должна собираться и работать как минимум под *nix и windows (в крайнем случае - под linux и windows).

Теперь про сборку: должна быть возможность собирать программу автоматически, то есть из bash/bat-скрипта либо через makefile. Если программа кроссплатформенная, то она должна под обоими платформами собираться без правки исходников руками, то есть тоже просто запуском скрипта/make. Естественно при этом на систему можно руками поставить весь, необходимый для сборки, дополнительный софт.

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

Этапы
Поскольку задача сложнее обычных тестов, и не очевидно какой алгоритм тут будет самый лучший, и какое решение самое замечательное (т.е. задача требует исследований и тестов), проходить всё будет в три этапа (на каждом этапе свои победители):
  • Первый этап - на этом этапе каждый делает на своем любимом ЯП как может и как хочет. Любые алгоритмы, любые реализации, любые идеи. По итогам первого этапа выбираем самый быстрый алгоритм/идею.
  • Второй этап - реализуем на разных ЯП (ну или разными руками на том же ЯП - без разницы) тот алгоритм и идею, что победила на первом этапе. Тут не обязательно соответствие буква к букве, просто берем за основу идею победителя и пытаемся её реализовать самостоятельно. По итогам этого этапа выбираем самую быструю реализацию реализацию идеи.
  • Третий этап - берем самую быструю реализацию из второго этапа и пытаемся её воспроизвести на своем ЯП дословно, т.е. максимально близко к оригиналу. В идеале - буква к букве, настолько, насколько это возможно

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

PS. У меня пока есть кривенькое решение на C++. Максимум что я еще смогу самостоятельно реализовать - ocaml и go. При этом за OCaml я не поручусь.
PPS. Правила проведения тестов вероятно будут дополняться.

UPD: Исходники решений слать и смотреть можно тут: https://github.com/valexey/bigbench
Правила засылки исходники такие:

Делаем бранч репозитория

Создаем папку со своим username or nickname, в ней подкаталог с названием решения (вдруг у будет несколько вариантов и захочется протестить их все), а в нём, кроме исходников, либо makefile либо build.sh чтобы собрать решение можно было в автоматическом режиме.

Затем засылаем пулреквестом в этот репозиторий: https://github.com/valexey/bigbench

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

UPD 2: Текущие результаты (картинка обновляется при каждом прогоне тестов):
« Последнее редактирование: Декабрь 01, 2016, 09:32:10 pm от valexey »
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #1 : Ноябрь 28, 2016, 01:59:43 pm »
Дополнение: решения будем складировать на github'e (создам для этого репозиторий), добавлять решения можно будет через пулреквесты. Тестирующая машина(машины) оттуда будут забирать периодически исходники и выкладывать результаты.

Таким образом смогут поучаствовать и те, кто на данном форуме не общается.
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #2 : Ноябрь 28, 2016, 02:03:47 pm »
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).
Y = λf.(λx.f (x x)) (λx.f (x x))

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #3 : Ноябрь 28, 2016, 02:51:05 pm »
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).

Это само по себе задача покруче оригинальной :) Оберонщики не поймут. Хотя може Zorko смогет...

Kemet

  • Hero Member
  • *****
  • Сообщений: 587
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #4 : Ноябрь 28, 2016, 04:14:49 pm »
можно ли перезаписывать исходный файл?

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #5 : Ноябрь 28, 2016, 04:20:28 pm »
можно ли перезаписывать исходный файл?
Нет. Но одержимое скопировать в новый файл и уже с ним творить всё что хочется.
Y = λf.(λx.f (x x)) (λx.f (x x))

Kemet

  • Hero Member
  • *****
  • Сообщений: 587
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #6 : Ноябрь 28, 2016, 04:23:08 pm »
Есть ли повторяющиеся значения или все значения уникальны

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #7 : Ноябрь 28, 2016, 04:24:22 pm »
Есть ли повторяющиеся значения или все значения уникальны
Повторяющиеся значения могут быть. Содержимое файла произвольно в рамках uint32_t little endian
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #8 : Ноябрь 28, 2016, 04:25:52 pm »
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).

Это само по себе задача покруче оригинальной :) Оберонщики не поймут. Хотя може Zorko смогет...

Мне кажется ты немного сгущаешь краски. По краней мере мне казалось, что для ББ вопрос если не полностью в таком виде, то по крайней мере частично решен. Есть какой-то линуксовый консольный компилятор, можно оформлять stand alone приложения, есть подсистема Info21olimp - консольный компилятор для олимпиад. Наверняка из этого всего можно сварить нужную кашу.

Для A2/AO тоже что-то было вроде как.
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #9 : Ноябрь 29, 2016, 12:17:32 am »
Кстати, ходят легенды, что на Component Pascal / BlackBox задачи, подобные этой, решаются вообще влёгкую:

http://www.delphikingdom.com/asp/talktopic.asp?ID=339&ref=msg&msg=979#msg981
Цитировать
...
Хотя по-грубому алгоритм решения -- гауссовский, но возникает масса нюансов: как данные представлять, как их на диск свопить, какие алгоритмы (алгебраической) сортировки применять и т.п. Плюс некие особенности в структуре системы ур-й. Все это вместе завязывается: например, как сортировать и как на диск свопить. Промахнешься с одним -- в других местах сильно скажется.
Ну и ясно, структуры данных сильно динамические: точная арифметика, рациональные функции ...

Соответственно, я делал в чистом виде 3 месяца, конкурент (типичный цыплюсист, постдок из Польши) -- 3 года. Ясное дело, чем он три года занимался -- в основном указатели отлавливал, об алгоритме ему и думать особо некогда было.

А "новый уровень", на котором он загнулся -- это как раз когда система вместе с промежуточным решением и проч. перестает в память влезать. У меня на паре (обероновских) паттернов всё выстроено -- нужно было только добавить один небольшой модуль с конкректной (дисковой) реализацией ридеров-райтеров (такой вариант изначально в проекте предусматривался), основной алгоритм ничего и не заметил. А у него наверняка какие-то "супер-быстрые" хеш-алгоритмы для сортировки, которые слишком много знают про представление данных, и т.п. и т.д.
...
Y = λf.(λx.f (x x)) (λx.f (x x))

trurl

  • Full Member
  • ***
  • Сообщений: 133
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #10 : Ноябрь 29, 2016, 11:51:35 am »
Странное сочетание: 128 Мб и 64 бита.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #11 : Ноябрь 29, 2016, 11:54:54 am »
Странное сочетание: 128 Мб и 64 бита.
На виртуалках/VPS так частенько бывает. Плюс всякие разные ARMы такими бывают вполне.
Y = λf.(λx.f (x x)) (λx.f (x x))

trurl

  • Full Member
  • ***
  • Сообщений: 133
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #12 : Ноябрь 29, 2016, 12:17:18 pm »
А мапить файлы можно?

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #13 : Ноябрь 29, 2016, 12:33:04 pm »
А мапить файлы можно?
Да. Но неплохо при этом помнить, что система внезапно может и 32битной оказаться.  Ну и про нюансы мапинга на разных осях тоже лучше помнить. Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Y = λf.(λx.f (x x)) (λx.f (x x))

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Расширенный тест на производительность.
« Ответ #14 : Ноябрь 29, 2016, 05:44:48 pm »
Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Да просто тебе лень полноценное ТЗ составить, а потом ещё на Вирта бочку катишь из-за его 17 страниц ))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…