Oberon space

General Category => Общий раздел => Тема начата: valexey_u от Ноябрь 28, 2016, 01:53:09 pm

Название: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 01:53:09 pm
Ну, простые тесты на производительность уже были, это уже скучно. Теперь давайте что-то более сложное, что-то более приближенное к реальности.

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

Итак задача:

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

Теперь детали:

Теперь следствия нюансов:
Решение может быть реализовано под наиболее вероятную конфигурацию машины (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: Текущие результаты (картинка обновляется при каждом прогоне тестов):
(https://github.com/valexey/bigbench/blob/master/results.png?raw=true)
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 01:59:43 pm
Дополнение: решения будем складировать на github'e (создам для этого репозиторий), добавлять решения можно будет через пулреквесты. Тестирующая машина(машины) оттуда будут забирать периодически исходники и выкладывать результаты.

Таким образом смогут поучаствовать и те, кто на данном форуме не общается.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 02:03:47 pm
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 28, 2016, 02:51:05 pm
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).

Это само по себе задача покруче оригинальной :) Оберонщики не поймут. Хотя може Zorko смогет...
Название: Re: Расширенный тест на производительность.
Отправлено: Kemet от Ноябрь 28, 2016, 04:14:49 pm
можно ли перезаписывать исходный файл?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 04:20:28 pm
можно ли перезаписывать исходный файл?
Нет. Но одержимое скопировать в новый файл и уже с ним творить всё что хочется.
Название: Re: Расширенный тест на производительность.
Отправлено: Kemet от Ноябрь 28, 2016, 04:23:08 pm
Есть ли повторяющиеся значения или все значения уникальны
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 04:24:22 pm
Есть ли повторяющиеся значения или все значения уникальны
Повторяющиеся значения могут быть. Содержимое файла произвольно в рамках uint32_t little endian
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 28, 2016, 04:25:52 pm
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).

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

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

Для A2/AO тоже что-то было вроде как.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 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 года. Ясное дело, чем он три года занимался -- в основном указатели отлавливал, об алгоритме ему и думать особо некогда было.

А "новый уровень", на котором он загнулся -- это как раз когда система вместе с промежуточным решением и проч. перестает в память влезать. У меня на паре (обероновских) паттернов всё выстроено -- нужно было только добавить один небольшой модуль с конкректной (дисковой) реализацией ридеров-райтеров (такой вариант изначально в проекте предусматривался), основной алгоритм ничего и не заметил. А у него наверняка какие-то "супер-быстрые" хеш-алгоритмы для сортировки, которые слишком много знают про представление данных, и т.п. и т.д.
...
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Ноябрь 29, 2016, 11:51:35 am
Странное сочетание: 128 Мб и 64 бита.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 29, 2016, 11:54:54 am
Странное сочетание: 128 Мб и 64 бита.
На виртуалках/VPS так частенько бывает. Плюс всякие разные ARMы такими бывают вполне.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Ноябрь 29, 2016, 12:17:18 pm
А мапить файлы можно?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 29, 2016, 12:33:04 pm
А мапить файлы можно?
Да. Но неплохо при этом помнить, что система внезапно может и 32битной оказаться.  Ну и про нюансы мапинга на разных осях тоже лучше помнить. Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Ноябрь 29, 2016, 05:44:48 pm
Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Да просто тебе лень полноценное ТЗ составить, а потом ещё на Вирта бочку катишь из-за его 17 страниц ))
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Ноябрь 29, 2016, 05:55:13 pm
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 29, 2016, 06:00:21 pm
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.
Файлы могут быть в несколько гигабайт, да. Большой файл это большой файл. Сейчас файлом в 300 Мб никого не удивишь :-)

PS. Я далеко не уверен, что mmap + qsort будет работать быстро и уложится в требования.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 29, 2016, 06:21:07 pm
Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Да просто тебе лень полноценное ТЗ составить, а потом ещё на Вирта бочку катишь из-за его 17 страниц ))
На самом деле эта задача есть уточненное и конкретизированное тестовое задание в одну компанию. В оригинале требования ещё более мутные были :-)
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 07:26:39 am
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.

mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 07:36:06 am
Машина little-endian?
Куда класть исходник?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Ноябрь 30, 2016, 09:13:00 am
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 12:49:05 pm
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.

Да. Ладно, пусть valexey прояснит. Но я подозреваю, что оно все равно быстро не будет. Если только в частном случае - когда памяти в ОС реально дофига (под файловый кэш), а задче искуственно выставлено ограничение в размере хипа.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 01:05:03 pm
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.

Да. Ладно, пусть valexey прояснит. Но я подозреваю, что оно все равно быстро не будет. Если только в частном случае - когда памяти в ОС реально дофига (под файловый кэш), а задче искуственно выставлено ограничение в размере хипа.
Проверить можно экспериментально :-) А так - использовать mmap/CreateFileMapping/etc можно. Обломится - ваши проблемы.

Моя имха на эту тему - на 32битной машине под файло не всегда адресного пространства хватит. На 64битной машине - должно хватить (кстати, реальное адресное пространство на 64битной машине не 64бита).

Если в задаче сказано что RAM у нас 128Мб, то и файловый кеш будет не более 128Мб. Тестовое окружение это дело смоделирует как надо.

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

Задача не только соревновательная, но и исследовательская.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 01:16:14 pm
Машина little-endian?
Да. Т.е. в самой исходной задаче (на которой базируется наша) это сказано не было, но по факту - да, little endian. Тем более что так просто найти машину с bigendian'ом не получится.

Куда класть исходник?
Пулреквестом в этот репозиторий: https://github.com/valexey/bigbench
Создаешь папку со своим username or nickname, в ней подкаталог с названием решения (вдруг у тебя будет несколько вариантов и захочется протестить их все), а в нём, кроме исходников, либо makefile либо build.sh чтобы собрать можно было.

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

Как-то так.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 02:08:31 pm
Машина little-endian?
Да. Т.е. в самой исходной задаче (на которой базируется наша) это сказано не было, но по факту - да, little endian. Тем более что так просто найти машину с bigendian'ом не получится.

OK, т.е. можно сразу читать в 32-битный int.

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

А как сделать pull request из CLI?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 02:22:14 pm
Машина little-endian?
Да. Т.е. в самой исходной задаче (на которой базируется наша) это сказано не было, но по факту - да, little endian. Тем более что так просто найти машину с bigendian'ом не получится.

OK, т.е. можно сразу читать в 32-битный int.
Угу. Точнее в uint32_t - беззнаковые чиселки ведь.

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

А как сделать pull request из CLI?
Народ предлагает пользоваться этим: https://hub.github.com/
( http://stackoverflow.com/questions/4037928/can-you-issue-pull-requests-from-the-command-line-on-github )
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 03:17:37 pm
Народ предлагает пользоваться этим: https://hub.github.com/
( http://stackoverflow.com/questions/4037928/can-you-issue-pull-requests-from-the-command-line-on-github )

Не взлетело.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 03:34:34 pm
Народ предлагает пользоваться этим: https://hub.github.com/
( http://stackoverflow.com/questions/4037928/can-you-issue-pull-requests-from-the-command-line-on-github )

Не взлетело.
А через гитхаб-гуйню не вариант?
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 04:10:36 pm
А через гитхаб-гуйню не вариант?

К меня старый еее PC с юбунтой. Может ты мне дашь доступ пушать?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 04:25:10 pm
А через гитхаб-гуйню не вариант?

К меня старый еее PC с юбунтой. Может ты мне дашь доступ пушать?
Там браузера кошерного совсем нема?
Так то конечно дам доступ.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 05:36:33 pm
Там браузера кошерного совсем нема?
Так то конечно дам доступ.

Под виндой у них была страшная поделка на .net. Сомневаюсь, что на юбунте будет лучше.
Спасибо.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 05:52:04 pm
Там браузера кошерного совсем нема?
Так то конечно дам доступ.

Под виндой у них была страшная поделка на .net. Сомневаюсь, что на юбунте будет лучше.
Спасибо.
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Ноябрь 30, 2016, 06:41:27 pm
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.

Я нажимал эту кнопку и не понял чего от меня хотели. Похоже я должен был сначаоа бранч сделать или ХЗ что еще. А у меня на руках был просто clone твоего репозитория.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 07:04:40 pm
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.

Я нажимал эту кнопку и не понял чего от меня хотели. Похоже я должен был сначаоа бранч сделать или ХЗ что еще. А у меня на руках был просто clone твоего репозитория.
Да, скорее всего отбранчеваться а потом на кнопаку эту жать.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 07:15:11 pm
Нус, первое решение есть. На вскидку, работает корректно (пока запускал на своем десктопе, там тоже SSD, ограничение в 128Мб соблюдалось). На гигабайтном файле отработало за такое время:

real 2m25.166s
user 1m51.277s
sys 0m10.533s

Напоминаю, что складывать и смотреть исходники можно тут: https://github.com/valexey/bigbench
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Ноябрь 30, 2016, 08:51:49 pm
Ещё +2 решения на c++ прилетело.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 12:07:08 pm
  • Третий этап - берем самую быструю реализацию из второго этапа и пытаемся её воспроизвести на своем ЯП дословно, т.е. максимально близко к оригиналу. В идеале - буква к букве, настолько, насколько это возможно
И как вот такое переводить буква к букве?
  std::sort(block.begin(), block.end());
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 12:28:49 pm
  • Третий этап - берем самую быструю реализацию из второго этапа и пытаемся её воспроизвести на своем ЯП дословно, т.е. максимально близко к оригиналу. В идеале - буква к букве, настолько, насколько это возможно
И как вот такое переводить буква к букве?
  std::sort(block.begin(), block.end());
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше. А шаблоны в рантайме роли не играют.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 02:47:07 pm
Кстати, я правильно понимаю, что BB не может файлы больше двух гигабайт?
FileInfo = POINTER TO RECORD
next: FileInfo;
name: Name;
length: INTEGER;
type: Type
modified: RECORD
year, month, day, hour, minute, second: INTEGER
END;
attr: SET
END;

Судя по полю length типа INTEGER коий 32битный знаковый.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 05:24:14 pm
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше.
А причем там итератор?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 05:36:44 pm
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше.
А причем там итератор?
Хм. А какие еще тут проблемы могут быть? Функцию аналогичную std::sort написать проблема?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 05:51:04 pm
Так задача в этом и состоит, не? 
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 06:04:58 pm
Так задача в этом и состоит, не?
У меня есть большие сомнения, что std::sort является идеальным алгоритмом для сортировке внутри большого файла (ну и тем более qsort таковым не является). Но, в принципе, если оно так и окажется, то да, надо будет реализовать этот алгоритм на своем любимом ЯП, а потом сравним что где как работает. Но это ж фазы 2 и 3, а мы пока на первой топчемся :-)

Первая фаза самая творческая и наименее занудная конечно.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 07:40:48 pm
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?

Насчет std::sort тоже не уверен в данных условиях (кстати, почему qsort тем более? Это же одно и то же практически). Но во времена, когда 640K хватало каждому, забавлялся с сортировкой. Лучшие результаты получались как раз с  quicksort. Тогда приходилось сложную схему пейджинга городить, а сейчас можно просто замапить файл.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 08:24:37 pm
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?

Насчет std::sort тоже не уверен в данных условиях (кстати, почему qsort тем более? Это же одно и то же практически). Но во времена, когда 640K хватало каждому, забавлялся с сортировкой. Лучшие результаты получались как раз с  quicksort. Тогда приходилось сложную схему пейджинга городить, а сейчас можно просто замапить файл.

Такие вопросы надо решать экспериментальным путем - пришли решение (можно даже сюда, но лучше таки обычным путем - на гитхаб) на си с qsort, затестим.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 08:30:07 pm
Так есть уже.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 08:34:36 pm
Так есть уже.

На сях и с qsort? Где? В репозитории нет такого решения.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 08:38:56 pm
На плюсах с std::sort.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 08:41:38 pm
На плюсах с std::sort.
Это разные языки и разные алгоритмы.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 01, 2016, 08:46:04 pm
Языки разные но компилятор один. И алгоритм тот же.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 08:50:35 pm
Языки разные но компилятор один. И алгоритм тот же.
Ну, тогда и у них и с Адой компилятор один и алгоритм тот же.

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

Поэтому если что-то утверждаешь - подтверди кодом. Проверим экспериментально насколько похоже сишное с mmap+qsort будет на плюсовое mmap+std::sort. Всё остальное - это просто переливание из пустого в порожнее.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 09:18:33 pm
Доступны первые результаты тестирования (пока это все на моем десктопе, но там тоже SSD и память тоже ограничивается как надо) в виде графика:
https://github.com/valexey/bigbench

(https://github.com/valexey/bigbench/blob/master/results.png?raw=true)

Картинка автоматически обновляется каждый раз как очередная итерация тестов завершается.
Также в каталоге с каждым решением появляются файлы типа res.txt, куда записаны результаты работы по времени (первая колонка - размер файла, вторая - время в секундах).

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

Предложения по оформлению выдачи результатов (графики там и так далее) принимаются и ведению тестирования принимаются.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 01, 2016, 10:50:27 pm
Последний прогон показал, что c++ std::sort mmap решение падает с out of memory error на файле в 4Гб размером.

Также происходит что-то странное с file merge решением. Будем разбираться.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 01:44:19 am
На 512 Мб и 2048 решение files metge отработало не верно. Завтра руками запущу и посмотрю дело в решении или же в тестовом окружении.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 02, 2016, 07:40:09 am
Добавил оптимизированный по скорости вариант, на больших файлах показывает прирост ~2.5 раза, исходник увеличился в 3 раза.
- буферизированные ввод/вывод (некрасиво, но быстро)
- модифицировал сам алгоритм - меньше байт читается/пишется
- заиспользовап boost - можно без него, но будет больше кода

https://github.com/valexey/bigbench/blob/master/vlad/fast/sort.cpp
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 01:34:20 pm
Итоги последнего прогона:

Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 02:03:20 pm
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?
Если бы в q оказалась встроенная функция которая умела бы сортировать большие файлы, и эта функция была бы написана на самом q (т.е. входила бы с стандартную библиотеку, которая пишется на самом этом языке), то да остальные тоже реализовали бы такую функцию.

std::sort писан на С++, там нет никакой магии, а qsort писан на Си, и там магии тоже нет. Не вижу ни одной причины почему нельзя реализовать частные случаи (для целых чисел) на любом другом универсальном ЯП.

Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю.. Наверно этот язык для этого теста действительно не подходит.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 02, 2016, 02:24:32 pm
Итоги последнего прогона:
  • vlad fast - отработало быстрее всех, но вылетело с out of memory на файле в 1024 Мб (на всех других размерах отработало корректно)

Странно. Там есть линейная зависимость потребляемой памяти от размера файла, но совсем небольшая - порядка 2.5Mb на каждый Gb исходного файла. Возможно плюсовые потоки в какой-то момент отжирают сколько-то. Стек есть?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 02:28:46 pm
Итоги последнего прогона:
  • vlad fast - отработало быстрее всех, но вылетело с out of memory на файле в 1024 Мб (на всех других размерах отработало корректно)

Странно. Там есть линейная зависимость потребляемой памяти от размера файла, но совсем небольшая - порядка 2.5Mb на каждый Gb исходного файла. Возможно плюсовые потоки в какой-то момент отжирают сколько-то. Стек есть?
Более странно, что на бОльших файлах оно отработало нормально. Никакой диагностической инфы больше нет пока что. Потом подробней гляну, может под gdb запущу.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 04:58:41 pm
Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю..
Почему нельзя? Можно.
sort:{x: |:'(-1 4)#6: `input; `output 6: ,/|:'x[<x]}Только как это переписать на си :-\
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 05:12:05 pm
Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю..
Почему нельзя? Можно.
sort:{x: |:'(-1 4)#6: `input; `output 6: ,/|:'x[<x]}Только как это переписать на си :-\
А это правда-правда будет работать для данной задачи? Т.е. этого точно будет достаточно?
Т.е. я с удовольствием включил бы и q в соревнование если бы было решение работоспособное хотя бы под *nix.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 06:24:04 pm
Не, не пойдет. 32-битная версия не справится, а 64-битная стоит невменяемых бабок.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 06:32:26 pm
Не, не пойдет. 32-битная версия не справится, а 64-битная стоит невменяемых бабок.
Может есть какие-то клоны/аналоги опенсурсные?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 06:39:44 pm
Есть, но они совсем слабенькие.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 06:40:54 pm
Да, а на модуле можно написать? В смысле, будет чем скомпилировать?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 06:50:24 pm
Кстати, я правильно понимаю, что BB не может файлы больше двух гигабайт?
Через Files нет. Но WinApi никто же не запрещает. А Files все равно для таких задач не стоит использовать.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 06:51:32 pm
Да, а на модуле можно написать? В смысле, будет чем скомпилировать?
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию). Теоретически можно еще попробовать GNU Modula-2 compiler ( http://nongnu.org/gm2 ), в репозиториях нет, вероятно придется собирать. Ну и еще вариант - Modula-3, надо глянуть что там как с компилятором сейчас.

Т.е. искаропки в репозитории системы модулу я не нашел, нужно руками пробовать вот эти вот варианты.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 06:52:10 pm
Кстати, я правильно понимаю, что BB не может файлы больше двух гигабайт?
Через Files нет. Но WinApi никто же не запрещает. А Files все равно для таких задач не стоит использовать.
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 07:20:25 pm
Пока запустил сборку GNU Modula-2, вроде собирается. Могу и Modula-3 собрать попробовать. Modula-3 вроде как сейчас может 64битность. GNU Modula-2 видимо тоже, но я не уверен.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 02, 2016, 07:45:58 pm
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
А Wine тогда что такое?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 08:02:43 pm
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
А Wine тогда что такое?
Костыль.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 02, 2016, 08:11:09 pm
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
Так в *nix'ах и ББ нет официально.  Но там же есть системные вызовы и libc.
А вместо Files обычно используют Files. :) Для обычной-то работы нормально.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 08:19:16 pm
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
Так в *nix'ах и ББ нет официально.  Но там же есть системные вызовы и libc.
А вместо Files обычно используют Files. :) Для обычной-то работы нормально.

Тут играем, тут не играем, а тут рыбу заворачиваем :-)

ББ нынче полный опенсорс, и понятие официоза стало весьма расплывчатым. Свободное ПО же. Исходники есть и доступны под правильной лицензией? Значит официально вполне. Пусть не релиз, а бета, но есть же. Тем более что нам не много надо - нам же даже гуя не надо. Так, компилятор консольный чтобы консольные приложения же лепить.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 08:49:26 pm
GNU Modula-2 compiler собрался. Hello world тоже собрался.

MODULE hello ;

FROM StrIO IMPORT WriteString, WriteLn ;

BEGIN
   WriteString('hello world') ; WriteLn
END hello.

Таким образом, компилятор для модулы есть. С Modula-3 сложнее.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 08:52:21 pm
А, да, оно собралось и собирает под AMD64
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 08:54:19 pm
А вот какие типы там есть: http://nongnu.org/gm2/type_compatibility.html
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 09:09:43 pm
Modula-3 компилятор (64битный) тоже похоже будет работать. В общем, будут желающие на модулу - уточняйте что именно вам нужно.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 02, 2016, 11:39:58 pm
Между тем, появилось решение использующее вот этот компилятор (компилирует в Си, насколько я понимаю): https://github.com/ComdivByZero/vostok
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 12:13:49 am
Новое решение работает корректно на всех размерах кроме 4Гб.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 02:28:48 pm
Теперь тестовые прогоны делаются на сервере. Результаты в абсолютных величинах могут измениться (и изменятся).
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:15:16 pm
Поскольку из результатов прогона исчезли действительно большие файлы (временно или навсегда?), стало интересно самому сравнить решения на своей системе именно для больших файлов, благо у меня тоже стоит SSD. Для автоматизации были написаны скрипты:

загрузка тестов:
git clone https://github.com/valexey/bigbench.git
cd bigbench
D=( comdiv/hardcore elena/files_merge elena/linux_mmap vlad/fast vlad/simple )
cd comdiv; make; mv vostok ../../; cd ..
for i in ${D[*]}
do
cd $i
./build.sh
cd ../..
done

создание input:
time dd if=/dev/urandom of=input bs=1M count=2048

прогон тестов:
D=( comdiv/hardcore elena/files_merge elena/linux_mmap vlad/fast vlad/simple )
for i in ${D[*]}
do
echo $i
time bigbench/$i/sort
md5sum output > `basename $i`.md5
echo -n "md5sum = "; cat `basename $i`.md5
rm -rf output swap.* *.TMP temp[12] output.temp
echo; echo
done
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:21:09 pm
Результат прогонов для 2-х гигабайтного входного файла
comdiv/hardcore
real 0m36.022s
output md5sum = fa1637b627029ab0566230d3ef11ac1e  output

elena/files_merge
real 5m4.276s
output md5sum = fa1637b627029ab0566230d3ef11ac1e  output

elena/linux_mmap
real 1m19.969s
output md5sum = fa1637b627029ab0566230d3ef11ac1e  output

vlad/fast
real 1m37.925s
output md5sum = fa1637b627029ab0566230d3ef11ac1e  output

vlad/simple
real 4m43.026s
output md5sum = fa1637b627029ab0566230d3ef11ac1e  output
elena/files_merge работает вроде бы медленно, но на самом деле весьма хорошо, потому что потребляет мизер памяти.
elena/linux_mmap работает быстро, но без искусственных ограничений отожрало 4гигабайта памяти

Отсеиваем медленные и прожорливые решения и делаем 2-й прогон:
comdiv/hardcore
real 0m33.318s
md5sum = fa1637b627029ab0566230d3ef11ac1e  output

vlad/fast
real 1m13.470s
md5sum = fa1637b627029ab0566230d3ef11ac1e  output

Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:21:34 pm
Поскольку из результатов прогона исчезли действительно большие файлы (временно или навсегда?), стало интересно самому сравнить решения на своей системе именно для больших файлов, благо у меня тоже стоит SSD.
Временно. Просто допиливал систему, переносил на сервер, тестировал - чтобы время не тратить, ограничил до 256 мб файлы.
Сейчас считается полный прогон.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:25:52 pm
Ага, временно - хорошо.

Создал 4-гигабайтный файл и сделал прогон для наиболее быстрых решений:
comdiv/hardcore
real 1m25.488s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

vlad/fast
real 4m9.742s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

Интересное кино получается
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:27:13 pm
elena/linux_mmap работает быстро, но без искусственных ограничений отожрало 4гигабайта памяти
Адресного пространства. Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле. В ход идёт всё что доступно. Другое дело что скорость не самая запредельная получается да и проблемы бывают на очень больших файлах. Плюс у измерялок памяти (чекающих сколько программа памяти отожрала) возникают проблемы - они не знают как тут что трактовать.

PS. И да, память я ограничиваю.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:28:52 pm
Ага, временно - хорошо.

Создал 4-гигабайтный файл и сделал прогон для наиболее быстрых решений:
comdiv/hardcore
real 1m25.488s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

vlad/fast
real 4m9.742s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

Интересное кино получается
Вероятно кино может от многого зависеть :-) Через часок прогон закончится, глянем результат с сервака. Подозреваю, что там результаты будут иные.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:30:56 pm
Для этого и были созданы скрипты, чтобы каждый мог проверить ещё и проверяющего
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:34:17 pm
Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле.
Не идеальная, потому что часто нужно ограничить ресурсы для конкретных программ, оставив их для более приоритетных.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:45:26 pm
Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле.
Не идеальная, потому что часто нужно ограничить ресурсы для конкретных программ, оставив их для более приоритетных.
Ну дык ограничь. Файловый кеш также можно ограничить как и всё остальное.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 03:47:02 pm
Для конкретной программы? Тогда - да.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:50:30 pm
Ага, временно - хорошо.

Создал 4-гигабайтный файл и сделал прогон для наиболее быстрых решений:
comdiv/hardcore
real 1m25.488s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

vlad/fast
real 4m9.742s
md5sum = e6d6ad0bad107695536bf8bef475f9eb  output

Интересное кино получается
Ещё замечание 4 минуты да и 1 минута - это очень мало. Такое ощущение, что у тебя весь файл поместился в ОЗУ (в дисковый кэш системы). И тут уже начинает играть роль состояние оного кэша (коий также неплохо бы полностью сбрасывать перед началом запуска каждого решения) и насколько алгоритм к нему дружественен. Например если решение самостоятельно кэширует (потому, что знает что у нас ограничение в 128 Мб ОЗУ, и системные алгоритмы кеширования будут работать хуже чем своя стратегия кеширования с учетом алгоритма сортировки), то в данном случае такое решение сольет решению которое отдает кеширование на откуп системе - у системы кеш будет во всё системное ОЗУ (4 Гб? 8? 16?) а собственный кеш программы будет всего 128. Даже если это умные 128, он не побьют на файле в 4Гб системный кэш который просто засосёт весь файл целиком в ОЗУ.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 03:52:24 pm
Для конкретной программы? Тогда - да.
Да, для конкретной программы. Или группы программ, как угодно. Можно сказать что вот эта и эта программа делят общую делянку и им на всех 32Мб ОЗУ, вот столько ядер и процессорного времени, а вот этой программе отдельно 256 Мб ОЗУ. Ну и так далее. Ресурсы можно резать тонкими ломтиками и раздавать программам почти как угодно.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 04:06:36 pm
Ещё замечание 4 минуты да и 1 минута - это очень мало. Такое ощущение, что у тебя весь файл поместился в ОЗУ (в дисковый кэш системы).
Насколько можно судить, решения считывают огригинальный файл один раз, а делается это быстро, но есть, конечно, и временные файлы, это может сказываться.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 04:14:29 pm
Ещё замечание 4 минуты да и 1 минута - это очень мало. Такое ощущение, что у тебя весь файл поместился в ОЗУ (в дисковый кэш системы).
Насколько можно судить, решения считывают огригинальный файл один раз, а делается это быстро, но есть, конечно, и временные файлы, это может сказываться.
Ну да. Считали, сделали копию, система радостно копию всосала в кеш, а дальше идет уже просто сортировка в памяти, если файловый кеш никак не ограничен.

С ограничениями что у меня на десктопе что на серваке например comdov'овское решение файл размером в 1Гб жевало поряда 220 секунд, а файл в 4Гб обрабатывался за 900+ секунд.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 03, 2016, 04:45:15 pm
Как Вы это ограничение выставляли?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 04:57:35 pm
Как Вы это ограничение выставляли?
Пока что через cgroups. Потом еще более сурово ограничу.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 05:18:05 pm
Поспели первые результаты прогона на сервере. См. гитхаб ( https://github.com/valexey/bigbench ).
Кроме картинки теперь есть файл под названием results.txt - лежит рядом с картинкой. Там такое:
Цитировать
comdiv hardcore:
128 29.29
256 56.55
512 110.70
1024 217.70
2048 453.05
4096 938.64
elena files_merge:
128 14.08
256 39.65
512 101.85
1024 256.89
2048 629.84
4096 1586.56
elena linux_mmap:
128 5.70
256 13.92
512 37.19
1024 87.95
2048 180.32
4096 404.89
vlad fast:
128 5.59
256 11.17
512 24.98
1024 52.99
2048 131.98
4096 345.50
vlad simple:
128 8.82
256 19.48
512 60.77
1024 177.82
2048 604.67
4096 2117.47
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 05:20:13 pm
Сейчас запущу в пять раз более длительный тест. Чтобы оценить разброс.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 03, 2016, 08:50:46 pm
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию).
Попробовал сегодня, там надо просто удалить -lncurses из xc.tem - он его лепит ко всем программам.

Хотел написать переносимо, но оказывется в стандарте ISO нет функции удаления файла.  :o

А еще между делом выяснилось, что FAT32 может быть в 2-4раза быстрее, чем NTFS.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 08:56:35 pm
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию).
Попробовал сегодня, там надо просто удалить -lncurses из xc.tem - он его лепит ко всем программам.
Дык у меня сам компилятор не запускается - ему тоже ncurses нужен...

Хотел написать переносимо, но оказывется в стандарте ISO нет функции удаления файла.  :o

А еще между делом выяснилось, что FAT32 может быть в 2-4раза быстрее, чем NTFS.
Ну, файлы не обязательно удалять. Т,е. после себя все временные файлы можно оставить, тестирующая система их убьет. Ну а в ходе работы имеющиеся файлы (кроме input'a, который read only по сути своей) можно же переиспользовать.

Т.е. если в ходе работы программа создала output (размером с input) и ещё два временных файла с input размером - это норм. Ничего удалять не надо.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 09:20:27 pm
Запустил тестироваться уже по нормальному - то есть каждое решение для каждого размера входного файла будет запущено 5 раз. Сколько это времени суммарно займет - фиг знает. Полагаю несколько часов.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 03, 2016, 10:06:35 pm
Дык у меня сам компилятор не запускается - ему тоже ncurses нужен...
Ктороый, xc или xm? У меня xc нормально запускается, а xm падает что-то там про COROUNITES пишет.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 10:11:58 pm
Дык у меня сам компилятор не запускается - ему тоже ncurses нужен...
Ктороый, xc или xm? У меня xc нормально запускается, а xm падает что-то там про COROUNITES пишет.

$ ./xc
./xc: error while loading shared libraries: libncurses.so.5: cannot open shared object file: No such file or directory
$ ./xm
#RTS: Coroutines initialization fault 3...

Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 03, 2016, 11:46:55 pm
Теперь тестирование одного решения занимает порядка 2-3 часов. Сейчас у нас 5 различных решений. Короче, серверу есть чем заняться в ближайшие 10-15 часов.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 04, 2016, 07:19:34 am
$ ./xc
./xc: error while loading shared libraries: libncurses.so.5: cannot open shared object file: No such file or directory
$ ./xm
#RTS: Coroutines initialization fault 3...
Ага, у меня 32-битная система. Видимо ncurses стоит по умолчанию, или  mc подтянул.
Можно предыдущую версию XDS (2.51) попробовать, там компилятор статически слинкован.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 04, 2016, 09:38:35 am
Доступны результаты нового прогона тестов. Теперь можно оценить разброс времени исполнения каждого теста.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 04, 2016, 02:48:37 pm
Ага. Вижу появилось решение на Modula-2.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 04, 2016, 06:54:15 pm
А вот как выглядит процесс тестирования в плане загрузки CPU & Disk IO на сервере.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 04, 2016, 10:25:00 pm
Следующий прогон тестов будет запущен через 24 часа.
Мне надо допилить сборку и тестирование новых решений.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 04, 2016, 10:28:15 pm
Похоже, что решение на модуле-2 (merge_heap, merge_qs еще не пускал) выдает не верные результаты на файлах больше 128 Мб. Но надо еще потестить.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 05, 2016, 12:15:33 am
Похоже, что решение на модуле-2 (merge_heap, merge_qs еще не пускал) выдает не верные результаты на файлах больше 128 Мб. Но надо еще потестить.

Кстати, а как проверяешь корректоность? Отдельная прога?
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 05, 2016, 07:38:14 am
Добавил еще одно решение - мультипоточное. Создал пулреквест - valexey, мерджни когда удобнее.

Как ни странно, получил хороший прирост (больше 30%) даже не моем дохлом нетбуке. Заодно убедился, что на оном нетбуке честных два ядра (раньше думал, что они бутафорские, какие-нибудь хипертрединговые).

Еще из интересных наблюдений - прирост есть даже если сортировать в единственном потоке, но отдельно от чтения. Т.е., если скорость чтения с диска сопоставима со скоростью сортировки в памяти, то за счет мультипоточности можно получить выигрыш даже на одноядерном железе.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 05, 2016, 08:46:17 pm
>Как ни странно, получил хороший прирост (больше 30%) даже не моем дохлом нетбуке.

А как это узнать? Разве ещё остались машины с одним ядром?

А прирост производительности даже на одном ядре будет потому, что с диска в память копирование осуществляет не процессор, а DMA.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 05, 2016, 08:51:09 pm
Кстати, тоже интересен способ проверки решений.

В голову приходит только вариант читать последовательно все числа и убеждаться, что каждое последующее число не меньше предыдущего.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 05, 2016, 09:02:49 pm
Кстати, тоже интересен способ проверки решений.

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

Пока проверка довольно тупая - через md5 суммы файлов ответов, исходим из того, что верные ответы у всех должны быть одинаковые, а вот ошибаются программисты в разных алгоритмах на разных языках, реализованных независимо друг от друга - по разному. Исходя из этого были выбраны вероятно правильные md5 суммы и теперь с ними сравниваются ответы.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 05, 2016, 10:27:22 pm
Не понятно... Почему неубывающая последовательность неправильна?

И почему равенство значений подменяется равенством хэшей?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 05, 2016, 10:40:34 pm
Не понятно... Почему неубывающая последовательность неправильна?

И почему равенство значений подменяется равенством хэшей?

Потому, что вот псевдокод который пройдет твой тест:
in := open("input");
out := create("output");
for i:=0; i<in.size/4; ++i {
    out.write(i);
}
При этом он ничего сортировать не будет. Ему вообще плевать на входные данные, ему важно только сколько этих данных.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 06, 2016, 04:23:55 am
Этот вариант не катит просто в силу того, что уже было в практике, когда на выходе была неправильная неубывающая последовательность чисел. Проверку оно проходило, но результат был не правильным.
Что за фигня? Это же простейший цикл, как он может дать неверный результат?

Пока проверка довольно тупая - через md5 суммы файлов ответов, исходим из того, что верные ответы у всех должны быть одинаковые, а вот ошибаются программисты в разных алгоритмах на разных языках, реализованных независимо друг от друга - по разному. Исходя из этого были выбраны вероятно правильные md5 суммы и теперь с ними сравниваются ответы.
"вероятно правильные md5 суммы" -- порадовало ))) вот она, партизанщина ))
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 06, 2016, 04:27:53 am
Не понятно... Почему неубывающая последовательность неправильна?

И почему равенство значений подменяется равенством хэшей?

Потому, что вот псевдокод который пройдет твой тест:
in := open("input");
out := create("output");
for i:=0; i<in.size/4; ++i {
    out.write(i);
}
При этом он ничего сортировать не будет. Ему вообще плевать на входные данные, ему важно только сколько этих данных.
В таком случае надо добавить проверку статистики файла -- сколько тех или иных чисел в обоих файлах ))
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 06, 2016, 06:54:36 am
Я сравнивал суммы чисел - такая упрощенная статистика.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 06, 2016, 08:28:08 am
Я сравнивал суммы чисел - такая упрощенная статистика.
Ну, сумма чисел -- это упрощённая контрольная сумма, тогда уж лучше сразу хеш делать, например SHA-2, а не MD5...
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 01:21:52 pm
Я сравнивал суммы чисел - такая упрощенная статистика.
Ну, сумма чисел -- это упрощённая контрольная сумма, тогда уж лучше сразу хеш делать, например SHA-2, а не MD5...
Тут есть нюанс суммы чисел можно посчитать имея input и не сортируя его, а вот md5 и sha2 уже не выйдет - чтобы их сравнивать с корректными нужно иметь сортированный корректный output. Т.е. чтобы проверить сортировку нужно реализовать сортировку.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 01:23:08 pm
Решение на modula-2 собранное gm2 шлепается с такой диагностикой:
this file (spill+0) has been opened for writing but is now being read
Command terminated by signal 6
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 06, 2016, 02:31:52 pm
Вот тебе и стандарты ISO. :-( Сейчас еще обнаружил, что в xds CARD16, CARD32..., а в gm2  CARDINAL16, CARDINAL32...
Пробовал gm2 из пакета поставить, вроде установилось, но не работает.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 02:44:42 pm
Вот тебе и стандарты ISO. :-( Сейчас еще обнаружил, что в xds CARD16, CARD32..., а в gm2  CARDINAL16, CARDINAL32...
Пробовал gm2 из пакета поставить, вроде установилось, но не работает.
Насколько я понимаю, проблема в чем-то вроде, что файл был открыт c флагом O_WRONLY а надо было с O_RDWR. Это если на позиксно-сишный язык переводить.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 03:01:46 pm
Вот тебе и стандарты ISO. :-( Сейчас еще обнаружил, что в xds CARD16, CARD32..., а в gm2  CARDINAL16, CARDINAL32...
Пробовал gm2 из пакета поставить, вроде установилось, но не работает.
Если что, я собирал прогу с помощью gm2 вот таким образом:
gm2 -O3 -flibs=iso,pim merge_heap.mod
Без этих опций (-flibs=iso,pim) оно не собирается.

Да! Еще надо поставить либу pth - если система дебианоподобная, то так: apt-get install  libpth-dev
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 06, 2016, 03:33:39 pm
Насколько я понимаю, проблема в чем-то вроде, что файл был открыт c флагом O_WRONLY а надо было с O_RDWR. Это если на позиксно-сишный язык переводить.
[/quote]
Ну да. Но там же написано
SeqFile.OpenWrite(spill[spno], name, SeqFile.raw+SeqFile.read+SeqFile.old, res);
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 03:44:05 pm
Ну да. Но там же написано
SeqFile.OpenWrite(spill[spno], name, SeqFile.raw+SeqFile.read+SeqFile.old, res);
Угу. Глянул в исходники либы. Там (в FIO.mod, где собственно это дело и проверяется и кидается HALT с этим текстом) написано следующее:
TYPE
    FileUsage         = (unused, openedforread, openedforwrite, openedforrandom) ;
...
PROCEDURE CheckAccess (f: File; use: FileUsage; towrite: BOOLEAN) ;
VAR
   fd: FileDescriptor ;
BEGIN
   IF f#Error
   THEN
      fd := GetIndice(FileInfo, f) ;
      IF fd=NIL
      THEN
         IF f#StdErr
         THEN
            FormatError('this file has probably been closed and not reopened successfully or alternatively never opened\n')
         END ;
         HALT
      ELSE
         WITH fd^ DO
            IF (use=openedforwrite) AND (usage=openedforread)
            THEN
               FormatError1('this file (%s) has been opened for reading but is now being written\n',
                            name.address) ;
               HALT
            ELSIF (use=openedforread) AND (usage=openedforwrite)
            THEN
               FormatError1('this file (%s) has been opened for writing but is now being read\n',
                            name.address) ;
               HALT
...

То есть выходит, что чтобы и читать и писать, нужно использовать openedforrandom. Т.е., вероятно, использовать не SeqFile, а RndFile.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 06, 2016, 04:33:20 pm
Да! Еще надо поставить либу pth - если система дебианоподобная, то так: apt-get install  libpth-dev
О! Поставил и заработало, даже собирать не пришлось.
Некоторые особенности сразу вылезли. Например, строку-константу  нельзя индексировать.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 05:08:19 pm
Могу пока пользоваться xds для прогонов тестов, но уже на файле в 256Мб merge_heap выдает не правильный ответ. Поэтому, думаю, его в тесты пока не включу. merge_qs работает вроде бы корректно (на всех файлах еще не гонял).
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 05:50:46 pm
Так, с ограничениями по памяти merge_qs падает:
Command exited with non-zero status 48
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 06:14:56 pm
Так, с ограничениями по памяти merge_qs падает:
Command exited with non-zero status 48
Но при этом, как ни странно, выдает правильный ответ. Что ломает нафиг мои скрипты.
Какие-то чудеса с этой модулой.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 06, 2016, 11:15:55 pm
Поправил скрипты, чтобы нормально отрабатывалось и модуловское решение (merge_qs), запустил быстрый прогон (каждый файл один раз будет прогнан). Так что часов через 5 наверно прогон будет закончен, результаты автоматически опубликуются.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 07, 2016, 03:21:25 am
Готовы новые результаты. Есть новый самый быстрый алгоритм - от comdiv'a (comdiv hardcore-single-temp) а алгоритм на modula-2 merge_qs выдал не верные результаты на больших файлах:
elektrybalt merge_qs:
128 18.30
256 38.12
512 76.50
1024 154.81
2048 failed
4096 failed
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 07, 2016, 03:26:51 am
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 07, 2016, 04:24:06 am
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.

Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 07, 2016, 05:24:34 am
То есть выходит, что чтобы и читать и писать, нужно использовать openedforrandom. Т.е., вероятно, использовать не SeqFile, а RndFile.
Я надеялся, что SeqFile как-то оптимизирван для последовательного чтения. Но похоже, там банально вызывается какой-нибудь fread/fwrite без буфферизации. Попробовал еще на аде. Там та же петрушка, только ещё медленнее раза в 2-3.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 07, 2016, 05:30:00 am
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.

Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
Для внешней сортировки всегда полезнее иметь несколько дисков, чем несколько процессоров.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 07, 2016, 01:48:13 pm
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.

Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
Открыта тайна третьей планеты!

В смысле, я нашел в чем была засада - многопоточное решение не смогло слинковаться, в итоге вместо него тестировалось обычное fast (да, скрипты тестирования писал я, и у меня крайне кривые руки). Сейчас пофикшу.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 07, 2016, 02:53:17 pm
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).
Название: Re: Расширенный тест на производительность.
Отправлено: vlad от Декабрь 08, 2016, 07:55:41 am
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).

Фикснул. Как я и предполагал - непрваильно поток прибивался, до того как он успел файлик записать :)
С памятью интереснее - у меня не получилось выставить ограничение (процесс не прибивается, если много отжирает).
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 02:17:48 pm
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).

Фикснул. Как я и предполагал - непрваильно поток прибивался, до того как он успел файлик записать :)
С памятью интереснее - у меня не получилось выставить ограничение (процесс не прибивается, если много отжирает).
Через час-два будут результаты очередного быстрого прогона.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 03:37:37 pm
Результаты готовы.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 08, 2016, 06:53:39 pm
Интересно, а срди тестов есть распределения с малой дисперсией?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 07:38:51 pm
Интересно, а срди тестов есть распределения с малой дисперсией?
скорее всего пока что нет. но всё будет :-) если для вашего алгоритма существует наихудший набор данных, то он будет среди тестов. :-)
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 08, 2016, 08:38:41 pm
Это не для моего :-). Мне кажется bucketsort с фиксированными корзинами должен на таких задачах страдать.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 08:57:44 pm
Это не для моего :-). Мне кажется bucketsort с фиксированными корзинами должен на таких задачах страдать.
Ну, это я отвлеченно говорил :-)
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 10:00:17 pm
Ну вот тест на 2Гб файле, первая колонка - с большой дисперсией, вторая колонка - с малой (массив одинаковых значений).

comdiv hardcore:
2048 458.21    32.54
comdiv hardcore-single-temp:
2048 127.72    74.92
elektrybalt merge_qs:
2048 failed    failed
elena files_merge:
2048 588.93    481.45
elena linux_mmap:
2048 194.04    104.73
valexey sortix:
2048 285.63    30.70
vlad fast:
2048 141.40    66.23
vlad simple:
2048 606.04    499.26
vlad multi-threaded:
2048 279.11    147.41
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 08, 2016, 11:17:15 pm
В общем, дальше планы такие: я сейчас запущу пятикратный прогон теста. Потом, если кто-то будет обновлять/исправлять/добавлять решения я буду делать новые прогоны. С системе тестирования по крайней мере до понедельника никаких изменений не будет, не будет и каких-то решений от меня.

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

Потом хочу попробовать так или иначе найти ещё участников соревнования :-) Если никого больше не найдется, то будет финальное тестирование и подготовка к фазе 2.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 09, 2016, 09:17:02 am
А как насчёт сделать показ не абсолютных значений, а относительных?
Самый быстрый вариант - это 100%, а все остальные больше (или меньше) этой величины.

В таком случае можно будет прм обновлении одного варианта прогонять только самый быстрый и обновлённый варианты. Полный прогон, конечно, можно считать более точным, но его не обязательно делать ежедневно: нам же интересен порядок величин для оценки работы алгоритмов. То есть, если одно решение быстрее другого, то этого будет достаточно.

И ещё: сильно ли различаются результаты тестов, проведённых над одними и теми же алгоритмами в разные дни? Есть ли смысл перезапускать уже проведённые тесты?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 02:52:35 pm
Оказывается, xds под линуксом не умеет работать с файлами > 2GB :-(. Программы просто падают при первой же попытке чтения.
И у gm2 такая же фича, по крайней мере с библиотеками ISO.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 03:01:05 pm
Оказывается, xds под линуксом не умеет работать с файлами > 2GB :-(. Программы просто падают при первой же попытке чтения.
И у gm2 такая же фича, по крайней мере с библиотеками ISO.
А как они падают? Говорят что? Судя по всему оно не умеет работать с файлами >=2Gb - тесты же проваливаются начиная с 2Гб файлов.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 05:10:53 pm
Пишут
#RTS: unhandled exception #1: IOException.notAvailable Readили
EXCEPTIONS.mod:57:3:IOChan: ChanId specified is invalid in RAISE
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 06:41:29 pm
Попробовал через FIO, получил
this file (input) was not successfully opened.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 07:43:01 pm
Попробовал через FIO, получил
this file (input) was not successfully opened.
Стоп. А у тебя какая система с gm2? 32 или 64 бита?

Ибо по коду FIO.mod выходит, что такое может быть только если юниксовый open вернул -1.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 07:49:24 pm
32 бита.
Я уже дошел до си и fopen.  Там тоже  -1 и гуглить "Value too large for defined data type".

Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 07:51:48 pm
32 бита.
Я уже дошел до си и fopen.  Там тоже  -1 и гуглить "Value too large for defined data type".
Насколько я понимаю, этой проблемы не должно быть в 64битах (на 32битных системах у линукса были проблемы с файлами больше 2Гиг). Можешь простой пример на модуле через FIO накидать, чтобы я протестил?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 07:52:37 pm
Хм, на FAT32 все работает, даже XDS.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 07:54:59 pm
Хм, на FAT32 все работает, даже XDS.
Через FIO али как?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 07:59:07 pm
По-всякому. А на Ext4 ничего не открывает.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:01:41 pm
Тест для Ulm
MODULE tulm;
IMPORT SYSTEM, StdIO,InOut;
VAR
    inf:StdIO.FILE;
    inbuf: ARRAY [0..1023] OF CARDINAL;
VAR
n : CARDINAL;
ok:BOOLEAN;
BEGIN
ok := StdIO.Fopen(inf, "input", StdIO.read, FALSE);
IF ok THEN
locsRead := 1023;
ok := StdIO.Fread(SYSTEM.ADR(inbuf), 4, locsRead ,inf);
IF ok THEN
InOut.WriteCard(locsRead,8);   InOut.WriteLn;
END;
ok := StdIO.Fclose(inf);
ELSE
InOut.WriteString("open fail");   InOut.WriteLn;
  END;
END tulm.
gm2 tulm.mod -flibs=ulm,pim
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 12, 2016, 08:08:25 pm
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 08:09:09 pm
Тест для Ulm
MODULE tulm;
IMPORT SYSTEM, StdIO,InOut;
VAR
    inf:StdIO.FILE;
    inbuf: ARRAY [0..1023] OF CARDINAL;
VAR
n : CARDINAL;
ok:BOOLEAN;
BEGIN
ok := StdIO.Fopen(inf, "input", StdIO.read, FALSE);
IF ok THEN
locsRead := 1023;
ok := StdIO.Fread(SYSTEM.ADR(inbuf), 4, locsRead ,inf);
IF ok THEN
InOut.WriteCard(locsRead,8);   InOut.WriteLn;
END;
ok := StdIO.Fclose(inf);
ELSE
InOut.WriteString("open fail");   InOut.WriteLn;
  END;
END tulm.
gm2 tulm.mod -flibs=ulm,pim
А что такое тут locsRead? А то мы с компилятором фрустрируем и ругаемся, ибо не можем понять что это такое и где искать.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:13:54 pm
Блин, скопировал не оттуда. locsRead должно быть вместо n, или наоборот.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:15:31 pm
А это для pim
MODULE tpim;
IMPORT SYSTEM, FIO, StrIO,NumberIO;
VAR
    inf:FIO.File;
    inbuf: ARRAY [0..1023] OF CARDINAL;
VAR
  n : CARDINAL;
BEGIN
  inf := FIO.OpenToRead("input");
  IF FIO.IsNoError(inf) THEN
    n := FIO.ReadNBytes(inf,SIZE(inbuf),SYSTEM.ADR(inbuf));
    NumberIO.WriteCard(n, 8); StrIO.WriteLn;
  ELSE
    StrIO.WriteString("open fail"); StrIO.WriteLn;
  END;
END tpim.
gm2 tpim.mod -fpim
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:18:32 pm
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Зато можно от 2 до 4.
На NTFS тоже работает, только медленно.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 08:19:05 pm
Ничего никуда не падает. Получается как-то так:
$ ./tulm
    1023
$ ./tpim
    4096

Сейчас ещё на сервака попробую.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 08:21:26 pm
Протестил, результат идентичный. Т.е., если я правильно понимаю, всё работает.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:34:00 pm
Значит, дело в системе. Ну да, у меня же и си не открывает. Но почему тогда моя прога на xds валилась? Потому, что 32-битный?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 08:36:05 pm
Значит, дело в системе. Ну да, у меня же и си не открывает. Но почему тогда моя прога на xds валилась? Потому, что 32-битный?
Либо так, либо у xds те же либы иначе реализованы. Кроме того, мы же сейчас попробовали ulm и pim, но не пробовали iso.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 12, 2016, 08:44:58 pm
А можно ещё iso?

MODULE tiso;
IMPORT SYSTEM, IOChan, ChanConsts, IOConsts, RndFile;
IMPORT STextIO, SWholeIO;
VAR
    inbuf: ARRAY [0..1024] OF CARDINAL;
    locsRead : CARDINAL;
    inchn: IOChan.ChanId; 
    res: ChanConsts.OpenResults;
BEGIN
  RndFile.OpenOld(inchn, "input", RndFile.raw, res);
  IF res = ChanConsts.opened THEN
    IOChan.RawRead(inchn, SYSTEM.ADR(inbuf), SIZE(inbuf), locsRead);
    SWholeIO.WriteCard(locsRead,8);
    STextIO.WriteLn;
    RndFile.Close(inchn);
  ELSE
    STextIO.WriteString("open fail");
    STextIO.WriteLn
  END;
END tiso.

Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 08:54:29 pm
# ./tiso
    4100
# ls -l input
-rw-r--r-- 1 root root 4294967296 Dec 11 14:29 input
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 12, 2016, 09:06:44 pm
Но чтобы быть уверенным до конца, я бы таки в тестах пробежался бы до конца файла.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 12, 2016, 09:13:12 pm
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Это если размер кластера не менять. Но если его увеличить, то и размер файла может быть гораздо больше, чем 4 ГБ.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 13, 2016, 11:28:48 am
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Это если размер кластера не менять. Но если его увеличить, то и размер файла может быть гораздо больше, чем 4 ГБ.
И как это сделать? Вот я взял и отформатировал флешку 32 ГБт в FAT32, указав максимальный размер кластера -- 64 кБт, но файл размером 4.3 ГБт всё равно не записывается -- запись прерывается на 91% файла. Выходит, что не работает этот рецепт...
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 13, 2016, 01:00:13 pm
Размер файла так не увеличить, он ограничен структурой записи в каталоге. Только размер тома можно.
Название: Re: Расширенный тест на производительность.
Отправлено: Valery Solovey от Декабрь 13, 2016, 01:02:56 pm
из вики:
Цитировать
Максимально возможный размер файла для тома FAT32 — ~ 4 ГБ — 4 294 967 295 байт (в FAT32 под размер файла отведено 4 байта. 4 байта - это 32 бита. 232-1 — 4 294 967 295 байт. Поэтому размер файла не может быть больше этого значения, иначе не получится указать его длину. Хотя цепочку в FAT таблице можно продолжать и дальше, но тогда для определения размера файла придется каждый раз пробегать по всей цепочке, а это будет занимать много времени.
Таким образом, файл может быть большим, но, похоже, его не создать стандартными средствами.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 13, 2016, 05:36:55 pm
Почитал я TFM. Большие файлы в 32-битных системах рекомендуется открывать через fopen64 или open64, которые делают системный вызов open со специальным флагом. В gm2 все пути ведут к open, в xds - к fopen.
Подозреваю, что все, собранное  с gcc -m32 и на 64-битной системе не сможет открыть 2GB файл.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 15, 2016, 06:06:26 am
А почему mege_rs не попал в тесты?
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 15, 2016, 09:38:18 am
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 15, 2016, 09:43:21 am
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
Особенно интересно в этом плане число 163 840 004 -- это 4*(80^4+1)...
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 15, 2016, 10:45:17 am
А почему mege_rs не попал в тесты?
Потому что я криворукий рукожоп. Скоро будут результаты с merge_rs.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 15, 2016, 11:48:36 am
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
Да вроде никто не делит на равные блоки.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 15, 2016, 11:54:56 am
Смотрю на SSD ввод/вывод намного дешевле, чем на HDD. Эффект от сжатия слабее.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 15, 2016, 03:39:04 pm
Прогон готов. На этот раз что-то сервер подтормозил и почти все алгоитмы отработали медленней процентов на 10-20.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 15, 2016, 08:45:39 pm
Не удается запустить aos на серваке :-/ Не хочет.

Пишет, что Unix.Dlopen: loading library libc.so.6 failed а затем не вылетает и не выходит, а зацикливается со 100% загрузкой CPU.

Причем если удалить 32битную libc.so.6 то aos начинает вылетать с вот такой ошибкой:
./oberon: error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory

Т.е. оно после диагностики работу прекращает, не зацикливается. А если вернуть либу назад, то см. начало мессаги.

Но ничего-ничего, будет и на стороне aos праздник, когда запустим тесты на 32битной машине :-) Так что решение всё равно нужно!
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 15, 2016, 08:46:36 pm
Да, сейчас сервак перезагрузится, и я запущу полный прогон тестов.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 16, 2016, 12:38:27 pm
Смотрю на SSD ввод/вывод намного дешевле, чем на HDD. Эффект от сжатия слабее.
Идея, в целом, верная, но не доведена до конца. Если увеличить до упора размер входного буфера, это может изменить расклад.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 16, 2016, 04:29:15 pm
Да там особенно и увеличивать некуда, уже 100MB.
Интересно ещё, у меня merge_rs почти вдвое быстрее, чем merge_qs, а здесь немного медленнее.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 16, 2016, 05:24:33 pm
Да, я не обратил внимание, что длина указана для массива 32 разрядных чисел, а не для байт. Тогда странно, что сортировка не самая быстрая, возможно, что это слабость компилятора или недочёт в библиотеках.
Поразрядная сортировка работает быстрей быстрой, поэтому на закэшированных файлах оказывается лучше, но из-за удвоенных требований по памяти приводит к увеличению временных файлов, что, по видимому, и приводит к перевесу быстрой в условиях ограниченной памяти.
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 16, 2016, 05:52:45 pm
Тогда странно, что сортировка не самая быстрая, возможно, что это слабость компилятора или недочёт в библиотеках.
Самая быстрая ( 256-buckets) - сортировка подсчетом. Там, правда, есть недостаток. На файлах от 8ГБ уже может возникнуть переполнение счетчиков, а если увеличить разрядность до 64 бит, они не влезут в ограничения.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 17, 2016, 04:44:03 pm
Доступны новые, довольно странные результаты :-)
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Декабрь 17, 2016, 04:51:28 pm
Ну, мы уже знаем, в чём причина таких результатов -- в чьей-то криворукости )))
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 17, 2016, 05:27:48 pm
Ну, мы уже знаем, в чём причина таких результатов -- в чьей-то криворукости )))
При том, что ничего не менялось (кроме добавления нового файла, ога), то возможно на этот раз криворукость уже не моя ;-)
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 17, 2016, 08:46:47 pm
А сколько занимает копирование файла?
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 17, 2016, 08:57:58 pm
А сколько занимает копирование файла?
Разово, или статистику хочется?
Название: Re: Расширенный тест на производительность.
Отправлено: trurl от Декабрь 18, 2016, 07:26:15 am
Можно и разово, порядок оценить. У меня сортировка ~ 1.5-2 копирования.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 18, 2016, 08:22:04 pm
Можно и разово, порядок оценить. У меня сортировка ~ 1.5-2 копирования.
4Gb - 15 секунд.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 18, 2016, 08:22:19 pm
Меж тем появилось решение на Аде.
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Декабрь 19, 2016, 09:29:59 am
Выглядит сурово, но судя по названию, это простое решение. Хотелось бы поглядеть на сложное.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 20, 2016, 02:38:09 pm
Доступны результаты прогона, теперь и с адским решением: https://github.com/valexey/bigbench
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 23, 2016, 12:49:07 pm
Тем временем у нас новый прогон, новое решение на модуле-2 и новый рекорд :-)
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 25, 2016, 05:20:12 pm
А текущего адского решения любопытный баг - он проявляется только на нашем 4Гб тестовом файле. Ловим.
Название: Re: Расширенный тест на производительность.
Отправлено: valexey_u от Декабрь 29, 2016, 02:57:27 am
Новые результаты для пофикшенного решение на Аде.
Название: Re: Расширенный тест на производительность.
Отправлено: Geniepro от Май 12, 2017, 06:51:44 am
Полгода прошло, какие выводы-то?
Сам я так и не осилил решение на Расте. Вроде на нём можно сделать вполне шустрый код, но выглядит он как говно, смотреть страшно, аж глаза кровоточат...
Название: Re: Расширенный тест на производительность.
Отправлено: kkkk от Май 16, 2017, 09:38:10 am
Какие выводы? Умение писать алгоритмы позволяет писать более эффективные решения, чем умение пользоваться стандартными библиотеками. В некоторых случаях сложность использования библиотек может быть на уровне или превышать сложность написания алгоритмов.