Oberon space
General Category => Общий раздел => Тема начата: valexey_u от Ноябрь 28, 2016, 01:53:09 pm
-
Ну, простые тесты на производительность уже были, это уже скучно. Теперь давайте что-то более сложное, что-то более приближенное к реальности.
Если на некотором ЯП результаты этого теста будут очень плохи, значит скорее всего на этом ЯП и ядро СУБД нормально реализовать не получится (либо это потребует очень больших усилий). Т.е. этот тест для, так называемых, ЯП претендующих на звание системных. По сути, тест на профпригодность ЯП на звание системного.
Итак задача:
Есть файл 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: Текущие результаты (картинка обновляется при каждом прогоне тестов):
(https://github.com/valexey/bigbench/blob/master/results.png?raw=true)
-
Дополнение: решения будем складировать на github'e (создам для этого репозиторий), добавлять решения можно будет через пулреквесты. Тестирующая машина(машины) оттуда будут забирать периодически исходники и выкладывать результаты.
Таким образом смогут поучаствовать и те, кто на данном форуме не общается.
-
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).
-
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).
Это само по себе задача покруче оригинальной :) Оберонщики не поймут. Хотя може Zorko смогет...
-
можно ли перезаписывать исходный файл?
-
можно ли перезаписывать исходный файл?
Нет. Но одержимое скопировать в новый файл и уже с ним творить всё что хочется.
-
Есть ли повторяющиеся значения или все значения уникальны
-
Есть ли повторяющиеся значения или все значения уникальны
Повторяющиеся значения могут быть. Содержимое файла произвольно в рамках uint32_t little endian
-
Да, а для таких ЯП и сред, как AO и BB нужно что-то придумать с автоматической сборкой консольных stand alone приложений (собственно там stdin/out и не нужны, программа тут ведь работает только с файлами).
Это само по себе задача покруче оригинальной :) Оберонщики не поймут. Хотя може Zorko смогет...
Мне кажется ты немного сгущаешь краски. По краней мере мне казалось, что для ББ вопрос если не полностью в таком виде, то по крайней мере частично решен. Есть какой-то линуксовый консольный компилятор, можно оформлять stand alone приложения, есть подсистема Info21olimp - консольный компилятор для олимпиад. Наверняка из этого всего можно сварить нужную кашу.
Для A2/AO тоже что-то было вроде как.
-
Кстати, ходят легенды, что на Component Pascal / BlackBox задачи, подобные этой, решаются вообще влёгкую:
http://www.delphikingdom.com/asp/talktopic.asp?ID=339&ref=msg&msg=979#msg981
...
Хотя по-грубому алгоритм решения -- гауссовский, но возникает масса нюансов: как данные представлять, как их на диск свопить, какие алгоритмы (алгебраической) сортировки применять и т.п. Плюс некие особенности в структуре системы ур-й. Все это вместе завязывается: например, как сортировать и как на диск свопить. Промахнешься с одним -- в других местах сильно скажется.
Ну и ясно, структуры данных сильно динамические: точная арифметика, рациональные функции ...
Соответственно, я делал в чистом виде 3 месяца, конкурент (типичный цыплюсист, постдок из Польши) -- 3 года. Ясное дело, чем он три года занимался -- в основном указатели отлавливал, об алгоритме ему и думать особо некогда было.
А "новый уровень", на котором он загнулся -- это как раз когда система вместе с промежуточным решением и проч. перестает в память влезать. У меня на паре (обероновских) паттернов всё выстроено -- нужно было только добавить один небольшой модуль с конкректной (дисковой) реализацией ридеров-райтеров (такой вариант изначально в проекте предусматривался), основной алгоритм ничего и не заметил. А у него наверняка какие-то "супер-быстрые" хеш-алгоритмы для сортировки, которые слишком много знают про представление данных, и т.п. и т.д.
...
-
Странное сочетание: 128 Мб и 64 бита.
-
Странное сочетание: 128 Мб и 64 бита.
На виртуалках/VPS так частенько бывает. Плюс всякие разные ARMы такими бывают вполне.
-
А мапить файлы можно?
-
А мапить файлы можно?
Да. Но неплохо при этом помнить, что система внезапно может и 32битной оказаться. Ну и про нюансы мапинга на разных осях тоже лучше помнить. Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
-
Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Да просто тебе лень полноценное ТЗ составить, а потом ещё на Вирта бочку катишь из-за его 17 страниц ))
-
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.
-
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.
Файлы могут быть в несколько гигабайт, да. Большой файл это большой файл. Сейчас файлом в 300 Мб никого не удивишь :-)
PS. Я далеко не уверен, что mmap + qsort будет работать быстро и уложится в требования.
-
Т.е. тут у нас примерно как в жизни - мутненькое ТЗ.
Да просто тебе лень полноценное ТЗ составить, а потом ещё на Вирта бочку катишь из-за его 17 страниц ))
На самом деле эта задача есть уточненное и конкретизированное тестовое задание в одну компанию. В оригинале требования ещё более мутные были :-)
-
А что, файлы предполагаются многогигабватными? Ну, можно на вторую наминацию и не претендовать. А банальный mmap+qsort трудно будет переплюнуть.
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
-
Машина little-endian?
Куда класть исходник?
-
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.
-
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.
Да. Ладно, пусть valexey прояснит. Но я подозреваю, что оно все равно быстро не будет. Если только в частном случае - когда памяти в ОС реально дофига (под файловый кэш), а задче искуственно выставлено ограничение в размере хипа.
-
mmap противоречит ограничению по памяти (весь файл нельзя мэпнуть).
Не противоречит. Нужна ведь не память, а адресное пространство.
Да. Ладно, пусть valexey прояснит. Но я подозреваю, что оно все равно быстро не будет. Если только в частном случае - когда памяти в ОС реально дофига (под файловый кэш), а задче искуственно выставлено ограничение в размере хипа.
Проверить можно экспериментально :-) А так - использовать mmap/CreateFileMapping/etc можно. Обломится - ваши проблемы.
Моя имха на эту тему - на 32битной машине под файло не всегда адресного пространства хватит. На 64битной машине - должно хватить (кстати, реальное адресное пространство на 64битной машине не 64бита).
Если в задаче сказано что RAM у нас 128Мб, то и файловый кеш будет не более 128Мб. Тестовое окружение это дело смоделирует как надо.
Да, я подумал, тесты будут гоняться с разными размерами файла. Чтобы у ограниченных решений (говорят например в А2 нельзя работать с файлами больше 2 гиг) были хоть какие-то шансы хоть как-то показать себя.
Задача не только соревновательная, но и исследовательская.
-
Машина little-endian?
Да. Т.е. в самой исходной задаче (на которой базируется наша) это сказано не было, но по факту - да, little endian. Тем более что так просто найти машину с bigendian'ом не получится.
Куда класть исходник?
Пулреквестом в этот репозиторий: https://github.com/valexey/bigbench
Создаешь папку со своим username or nickname, в ней подкаталог с названием решения (вдруг у тебя будет несколько вариантов и захочется протестить их все), а в нём, кроме исходников, либо makefile либо build.sh чтобы собрать можно было.
Можно еще ридмишку - что в системе нужно иметь, чтобы собралось.
Как-то так.
-
Машина little-endian?
Да. Т.е. в самой исходной задаче (на которой базируется наша) это сказано не было, но по факту - да, little endian. Тем более что так просто найти машину с bigendian'ом не получится.
OK, т.е. можно сразу читать в 32-битный int.
Пулреквестом в этот репозиторий: https://github.com/valexey/bigbench
А как сделать pull request из CLI?
-
Машина 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 )
-
Народ предлагает пользоваться этим: https://hub.github.com/
( http://stackoverflow.com/questions/4037928/can-you-issue-pull-requests-from-the-command-line-on-github )
Не взлетело.
-
Народ предлагает пользоваться этим: https://hub.github.com/
( http://stackoverflow.com/questions/4037928/can-you-issue-pull-requests-from-the-command-line-on-github )
Не взлетело.
А через гитхаб-гуйню не вариант?
-
А через гитхаб-гуйню не вариант?
К меня старый еее PC с юбунтой. Может ты мне дашь доступ пушать?
-
А через гитхаб-гуйню не вариант?
К меня старый еее PC с юбунтой. Может ты мне дашь доступ пушать?
Там браузера кошерного совсем нема?
Так то конечно дам доступ.
-
Там браузера кошерного совсем нема?
Так то конечно дам доступ.
Под виндой у них была страшная поделка на .net. Сомневаюсь, что на юбунте будет лучше.
Спасибо.
-
Там браузера кошерного совсем нема?
Так то конечно дам доступ.
Под виндой у них была страшная поделка на .net. Сомневаюсь, что на юбунте будет лучше.
Спасибо.
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.
-
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.
Я нажимал эту кнопку и не понял чего от меня хотели. Похоже я должен был сначаоа бранч сделать или ХЗ что еще. А у меня на руках был просто clone твоего репозитория.
-
Не, там прямо через веб-морду в браузере можно нажать на кнопку "New pull request". Без установки и запуска каких-либо приложений десктопных.
Я нажимал эту кнопку и не понял чего от меня хотели. Похоже я должен был сначаоа бранч сделать или ХЗ что еще. А у меня на руках был просто clone твоего репозитория.
Да, скорее всего отбранчеваться а потом на кнопаку эту жать.
-
Нус, первое решение есть. На вскидку, работает корректно (пока запускал на своем десктопе, там тоже SSD, ограничение в 128Мб соблюдалось). На гигабайтном файле отработало за такое время:
real 2m25.166s
user 1m51.277s
sys 0m10.533s
Напоминаю, что складывать и смотреть исходники можно тут: https://github.com/valexey/bigbench
-
Ещё +2 решения на c++ прилетело.
-
- Третий этап - берем самую быструю реализацию из второго этапа и пытаемся её воспроизвести на своем ЯП дословно, т.е. максимально близко к оригиналу. В идеале - буква к букве, настолько, насколько это возможно
И как вот такое переводить буква к букве?
std::sort(block.begin(), block.end());
-
- Третий этап - берем самую быструю реализацию из второго этапа и пытаемся её воспроизвести на своем ЯП дословно, т.е. максимально близко к оригиналу. В идеале - буква к букве, настолько, насколько это возможно
И как вот такое переводить буква к букве?
std::sort(block.begin(), block.end());
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше. А шаблоны в рантайме роли не играют.
-
Кстати, я правильно понимаю, что 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битный знаковый.
-
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше.
А причем там итератор?
-
А в чем проблема? Итератор можно сделать в любом ЯП, только сахара будет меньше.
А причем там итератор?
Хм. А какие еще тут проблемы могут быть? Функцию аналогичную std::sort написать проблема?
-
Так задача в этом и состоит, не?
-
Так задача в этом и состоит, не?
У меня есть большие сомнения, что std::sort является идеальным алгоритмом для сортировке внутри большого файла (ну и тем более qsort таковым не является). Но, в принципе, если оно так и окажется, то да, надо будет реализовать этот алгоритм на своем любимом ЯП, а потом сравним что где как работает. Но это ж фазы 2 и 3, а мы пока на первой топчемся :-)
Первая фаза самая творческая и наименее занудная конечно.
-
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?
Насчет std::sort тоже не уверен в данных условиях (кстати, почему qsort тем более? Это же одно и то же практически). Но во времена, когда 640K хватало каждому, забавлялся с сортировкой. Лучшие результаты получались как раз с quicksort. Тогда приходилось сложную схему пейджинга городить, а сейчас можно просто замапить файл.
-
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?
Насчет std::sort тоже не уверен в данных условиях (кстати, почему qsort тем более? Это же одно и то же практически). Но во времена, когда 640K хватало каждому, забавлялся с сортировкой. Лучшие результаты получались как раз с quicksort. Тогда приходилось сложную схему пейджинга городить, а сейчас можно просто замапить файл.
Такие вопросы надо решать экспериментальным путем - пришли решение (можно даже сюда, но лучше таки обычным путем - на гитхаб) на си с qsort, затестим.
-
Так есть уже.
-
Так есть уже.
На сях и с qsort? Где? В репозитории нет такого решения.
-
На плюсах с std::sort.
-
На плюсах с std::sort.
Это разные языки и разные алгоритмы.
-
Языки разные но компилятор один. И алгоритм тот же.
-
Языки разные но компилятор один. И алгоритм тот же.
Ну, тогда и у них и с Адой компилятор один и алгоритм тот же.
Ещё раз - проверять надо экспериментально. То есть я может и сам сишный вариант такой сделаю, но не прямо сейчас - сейчас занят настройкой тестирующей платформы, первые кое-какие результаты будут минут через 30.
Поэтому если что-то утверждаешь - подтверди кодом. Проверим экспериментально насколько похоже сишное с mmap+qsort будет на плюсовое mmap+std::sort. Всё остальное - это просто переливание из пустого в порожнее.
-
Доступны первые результаты тестирования (пока это все на моем десктопе, но там тоже SSD и память тоже ограничивается как надо) в виде графика:
https://github.com/valexey/bigbench
(https://github.com/valexey/bigbench/blob/master/results.png?raw=true)
Картинка автоматически обновляется каждый раз как очередная итерация тестов завершается.
Также в каталоге с каждым решением появляются файлы типа res.txt, куда записаны результаты работы по времени (первая колонка - размер файла, вторая - время в секундах).
Методика тестирования пока не совершенна, надо делать больше прогонов, добавить нормальную верификацию результатов и детектирование крашей.
Предложения по оформлению выдачи результатов (графики там и так далее) принимаются и ведению тестирования принимаются.
-
Последний прогон показал, что c++ std::sort mmap решение падает с out of memory error на файле в 4Гб размером.
Также происходит что-то странное с file merge решением. Будем разбираться.
-
На 512 Мб и 2048 решение files metge отработало не верно. Завтра руками запущу и посмотрю дело в решении или же в тестовом окружении.
-
Добавил оптимизированный по скорости вариант, на больших файлах показывает прирост ~2.5 раза, исходник увеличился в 3 раза.
- буферизированные ввод/вывод (некрасиво, но быстро)
- модифицировал сам алгоритм - меньше байт читается/пишется
- заиспользовап boost - можно без него, но будет больше кода
https://github.com/valexey/bigbench/blob/master/vlad/fast/sort.cpp
-
Итоги последнего прогона:
- vlad fast - отработало быстрее всех, но вылетело с out of memory на файле в 1024 Мб (на всех других размерах отработало корректно)
- mmap решение, как обычно вылетело с out of memory error на файле в 4096 Мб
- merge file решение выдало неверный результат на размере 1024,
- vlad simple решение работает медленно (сложность похоже квадратичная), но верно
-
Вот в этих фазах, особенно в последней, смысла совсем не вижу.
Тут еще подумалось, вот в q есть встоенная функция, умеющая быстро сотрировать большие файлы. Если вдуг оказалось бы, что она быстрее всех представленных, как бы ее переписывалт буква в букву?
Если бы в q оказалась встроенная функция которая умела бы сортировать большие файлы, и эта функция была бы написана на самом q (т.е. входила бы с стандартную библиотеку, которая пишется на самом этом языке), то да остальные тоже реализовали бы такую функцию.
std::sort писан на С++, там нет никакой магии, а qsort писан на Си, и там магии тоже нет. Не вижу ни одной причины почему нельзя реализовать частные случаи (для целых чисел) на любом другом универсальном ЯП.
Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю.. Наверно этот язык для этого теста действительно не подходит.
-
Итоги последнего прогона:
- vlad fast - отработало быстрее всех, но вылетело с out of memory на файле в 1024 Мб (на всех других размерах отработало корректно)
Странно. Там есть линейная зависимость потребляемой памяти от размера файла, но совсем небольшая - порядка 2.5Mb на каждый Gb исходного файла. Возможно плюсовые потоки в какой-то момент отжирают сколько-то. Стек есть?
-
Итоги последнего прогона:
- vlad fast - отработало быстрее всех, но вылетело с out of memory на файле в 1024 Мб (на всех других размерах отработало корректно)
Странно. Там есть линейная зависимость потребляемой памяти от размера файла, но совсем небольшая - порядка 2.5Mb на каждый Gb исходного файла. Возможно плюсовые потоки в какой-то момент отжирают сколько-то. Стек есть?
Более странно, что на бОльших файлах оно отработало нормально. Никакой диагностической инфы больше нет пока что. Потом подробней гляну, может под gdb запущу.
-
Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю..
Почему нельзя? Можно.
sort:{x: |:'(-1 4)#6: `input; `output 6: ,/|:'x[<x]}
Только как это переписать на си :-\
-
Если на вашем языке нельзя написать функцию сортировки, ну тогда я не знаю..
Почему нельзя? Можно.
sort:{x: |:'(-1 4)#6: `input; `output 6: ,/|:'x[<x]}
Только как это переписать на си :-\
А это правда-правда будет работать для данной задачи? Т.е. этого точно будет достаточно?
Т.е. я с удовольствием включил бы и q в соревнование если бы было решение работоспособное хотя бы под *nix.
-
Не, не пойдет. 32-битная версия не справится, а 64-битная стоит невменяемых бабок.
-
Не, не пойдет. 32-битная версия не справится, а 64-битная стоит невменяемых бабок.
Может есть какие-то клоны/аналоги опенсурсные?
-
Есть, но они совсем слабенькие.
-
Да, а на модуле можно написать? В смысле, будет чем скомпилировать?
-
Кстати, я правильно понимаю, что BB не может файлы больше двух гигабайт?
Через Files нет. Но WinApi никто же не запрещает. А Files все равно для таких задач не стоит использовать.
-
Да, а на модуле можно написать? В смысле, будет чем скомпилировать?
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию). Теоретически можно еще попробовать GNU Modula-2 compiler ( http://nongnu.org/gm2 ), в репозиториях нет, вероятно придется собирать. Ну и еще вариант - Modula-3, надо глянуть что там как с компилятором сейчас.
Т.е. искаропки в репозитории системы модулу я не нашел, нужно руками пробовать вот эти вот варианты.
-
Кстати, я правильно понимаю, что BB не может файлы больше двух гигабайт?
Через Files нет. Но WinApi никто же не запрещает. А Files все равно для таких задач не стоит использовать.
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
-
Пока запустил сборку GNU Modula-2, вроде собирается. Могу и Modula-3 собрать попробовать. Modula-3 вроде как сейчас может 64битность. GNU Modula-2 видимо тоже, но я не уверен.
-
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
А Wine тогда что такое?
-
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
А Wine тогда что такое?
Костыль.
-
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
Так в *nix'ах и ББ нет официально. Но там же есть системные вызовы и libc.
А вместо Files обычно используют Files. :) Для обычной-то работы нормально.
-
Ну, WinAPI в *nix'ах нет :-) А что сейчас модно использовать вместо Files?
Так в *nix'ах и ББ нет официально. Но там же есть системные вызовы и libc.
А вместо Files обычно используют Files. :) Для обычной-то работы нормально.
Тут играем, тут не играем, а тут рыбу заворачиваем :-)
ББ нынче полный опенсорс, и понятие официоза стало весьма расплывчатым. Свободное ПО же. Исходники есть и доступны под правильной лицензией? Значит официально вполне. Пусть не релиз, а бета, но есть же. Тем более что нам не много надо - нам же даже гуя не надо. Так, компилятор консольный чтобы консольные приложения же лепить.
-
GNU Modula-2 compiler собрался. Hello world тоже собрался.
MODULE hello ;
FROM StrIO IMPORT WriteString, WriteLn ;
BEGIN
WriteString('hello world') ; WriteLn
END hello.
Таким образом, компилятор для модулы есть. С Modula-3 сложнее.
-
А, да, оно собралось и собирает под AMD64
-
А вот какие типы там есть: http://nongnu.org/gm2/type_compatibility.html
-
Modula-3 компилятор (64битный) тоже похоже будет работать. В общем, будут желающие на модулу - уточняйте что именно вам нужно.
-
Между тем, появилось решение использующее вот этот компилятор (компилирует в Си, насколько я понимаю): https://github.com/ComdivByZero/vostok
-
Новое решение работает корректно на всех размерах кроме 4Гб.
-
Теперь тестовые прогоны делаются на сервере. Результаты в абсолютных величинах могут измениться (и изменятся).
-
Поскольку из результатов прогона исчезли действительно большие файлы (временно или навсегда?), стало интересно самому сравнить решения на своей системе именно для больших файлов, благо у меня тоже стоит 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
-
Результат прогонов для 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
-
Поскольку из результатов прогона исчезли действительно большие файлы (временно или навсегда?), стало интересно самому сравнить решения на своей системе именно для больших файлов, благо у меня тоже стоит SSD.
Временно. Просто допиливал систему, переносил на сервер, тестировал - чтобы время не тратить, ограничил до 256 мб файлы.
Сейчас считается полный прогон.
-
Ага, временно - хорошо.
Создал 4-гигабайтный файл и сделал прогон для наиболее быстрых решений:
comdiv/hardcore
real 1m25.488s
md5sum = e6d6ad0bad107695536bf8bef475f9eb output
vlad/fast
real 4m9.742s
md5sum = e6d6ad0bad107695536bf8bef475f9eb output
Интересное кино получается
-
elena/linux_mmap работает быстро, но без искусственных ограничений отожрало 4гигабайта памяти
Адресного пространства. Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле. В ход идёт всё что доступно. Другое дело что скорость не самая запредельная получается да и проблемы бывают на очень больших файлах. Плюс у измерялок памяти (чекающих сколько программа памяти отожрала) возникают проблемы - они не знают как тут что трактовать.
PS. И да, память я ограничиваю.
-
Ага, временно - хорошо.
Создал 4-гигабайтный файл и сделал прогон для наиболее быстрых решений:
comdiv/hardcore
real 1m25.488s
md5sum = e6d6ad0bad107695536bf8bef475f9eb output
vlad/fast
real 4m9.742s
md5sum = e6d6ad0bad107695536bf8bef475f9eb output
Интересное кино получается
Вероятно кино может от многого зависеть :-) Через часок прогон закончится, глянем результат с сервака. Подозреваю, что там результаты будут иные.
-
Для этого и были созданы скрипты, чтобы каждый мог проверить ещё и проверяющего
-
Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле.
Не идеальная, потому что часто нужно ограничить ресурсы для конкретных программ, оставив их для более приоритетных.
-
Практически доступное ОЗУ при этом система сама использует под кэш диска. Ну, т.е. такая масштабируемость штука идеальная на самом деле.
Не идеальная, потому что часто нужно ограничить ресурсы для конкретных программ, оставив их для более приоритетных.
Ну дык ограничь. Файловый кеш также можно ограничить как и всё остальное.
-
Для конкретной программы? Тогда - да.
-
Ага, временно - хорошо.
Создал 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Гб системный кэш который просто засосёт весь файл целиком в ОЗУ.
-
Для конкретной программы? Тогда - да.
Да, для конкретной программы. Или группы программ, как угодно. Можно сказать что вот эта и эта программа делят общую делянку и им на всех 32Мб ОЗУ, вот столько ядер и процессорного времени, а вот этой программе отдельно 256 Мб ОЗУ. Ну и так далее. Ресурсы можно резать тонкими ломтиками и раздавать программам почти как угодно.
-
Ещё замечание 4 минуты да и 1 минута - это очень мало. Такое ощущение, что у тебя весь файл поместился в ОЗУ (в дисковый кэш системы).
Насколько можно судить, решения считывают огригинальный файл один раз, а делается это быстро, но есть, конечно, и временные файлы, это может сказываться.
-
Ещё замечание 4 минуты да и 1 минута - это очень мало. Такое ощущение, что у тебя весь файл поместился в ОЗУ (в дисковый кэш системы).
Насколько можно судить, решения считывают огригинальный файл один раз, а делается это быстро, но есть, конечно, и временные файлы, это может сказываться.
Ну да. Считали, сделали копию, система радостно копию всосала в кеш, а дальше идет уже просто сортировка в памяти, если файловый кеш никак не ограничен.
С ограничениями что у меня на десктопе что на серваке например comdov'овское решение файл размером в 1Гб жевало поряда 220 секунд, а файл в 4Гб обрабатывался за 900+ секунд.
-
Как Вы это ограничение выставляли?
-
Как Вы это ограничение выставляли?
Пока что через cgroups. Потом еще более сурово ограничу.
-
Поспели первые результаты прогона на сервере. См. гитхаб ( 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
-
Сейчас запущу в пять раз более длительный тест. Чтобы оценить разброс.
-
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию).
Попробовал сегодня, там надо просто удалить -lncurses из xc.tem - он его лепит ко всем программам.
Хотел написать переносимо, но оказывется в стандарте ISO нет функции удаления файла. :o
А еще между делом выяснилось, что FAT32 может быть в 2-4раза быстрее, чем NTFS.
-
Есть 32битный xds (но там надо победить ncurses либу - компилятор требует для работы какую-то древнющую версию).
Попробовал сегодня, там надо просто удалить -lncurses из xc.tem - он его лепит ко всем программам.
Дык у меня сам компилятор не запускается - ему тоже ncurses нужен...
Хотел написать переносимо, но оказывется в стандарте ISO нет функции удаления файла. :o
А еще между делом выяснилось, что FAT32 может быть в 2-4раза быстрее, чем NTFS.
Ну, файлы не обязательно удалять. Т,е. после себя все временные файлы можно оставить, тестирующая система их убьет. Ну а в ходе работы имеющиеся файлы (кроме input'a, который read only по сути своей) можно же переиспользовать.
Т.е. если в ходе работы программа создала output (размером с input) и ещё два временных файла с input размером - это норм. Ничего удалять не надо.
-
Запустил тестироваться уже по нормальному - то есть каждое решение для каждого размера входного файла будет запущено 5 раз. Сколько это времени суммарно займет - фиг знает. Полагаю несколько часов.
-
Дык у меня сам компилятор не запускается - ему тоже ncurses нужен...
Ктороый, xc или xm? У меня xc нормально запускается, а xm падает что-то там про COROUNITES пишет.
-
Дык у меня сам компилятор не запускается - ему тоже 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...
-
Теперь тестирование одного решения занимает порядка 2-3 часов. Сейчас у нас 5 различных решений. Короче, серверу есть чем заняться в ближайшие 10-15 часов.
-
$ ./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) попробовать, там компилятор статически слинкован.
-
Доступны результаты нового прогона тестов. Теперь можно оценить разброс времени исполнения каждого теста.
-
Ага. Вижу появилось решение на Modula-2.
-
А вот как выглядит процесс тестирования в плане загрузки CPU & Disk IO на сервере.
-
Следующий прогон тестов будет запущен через 24 часа.
Мне надо допилить сборку и тестирование новых решений.
-
Похоже, что решение на модуле-2 (merge_heap, merge_qs еще не пускал) выдает не верные результаты на файлах больше 128 Мб. Но надо еще потестить.
-
Похоже, что решение на модуле-2 (merge_heap, merge_qs еще не пускал) выдает не верные результаты на файлах больше 128 Мб. Но надо еще потестить.
Кстати, а как проверяешь корректоность? Отдельная прога?
-
Добавил еще одно решение - мультипоточное. Создал пулреквест - valexey, мерджни когда удобнее.
Как ни странно, получил хороший прирост (больше 30%) даже не моем дохлом нетбуке. Заодно убедился, что на оном нетбуке честных два ядра (раньше думал, что они бутафорские, какие-нибудь хипертрединговые).
Еще из интересных наблюдений - прирост есть даже если сортировать в единственном потоке, но отдельно от чтения. Т.е., если скорость чтения с диска сопоставима со скоростью сортировки в памяти, то за счет мультипоточности можно получить выигрыш даже на одноядерном железе.
-
>Как ни странно, получил хороший прирост (больше 30%) даже не моем дохлом нетбуке.
А как это узнать? Разве ещё остались машины с одним ядром?
А прирост производительности даже на одном ядре будет потому, что с диска в память копирование осуществляет не процессор, а DMA.
-
Кстати, тоже интересен способ проверки решений.
В голову приходит только вариант читать последовательно все числа и убеждаться, что каждое последующее число не меньше предыдущего.
-
Кстати, тоже интересен способ проверки решений.
В голову приходит только вариант читать последовательно все числа и убеждаться, что каждое последующее число не меньше предыдущего.
Этот вариант не катит просто в силу того, что уже было в практике, когда на выходе была неправильная неубывающая последовательность чисел. Проверку оно проходило, но результат был не правильным.
Пока проверка довольно тупая - через md5 суммы файлов ответов, исходим из того, что верные ответы у всех должны быть одинаковые, а вот ошибаются программисты в разных алгоритмах на разных языках, реализованных независимо друг от друга - по разному. Исходя из этого были выбраны вероятно правильные md5 суммы и теперь с ними сравниваются ответы.
-
Не понятно... Почему неубывающая последовательность неправильна?
И почему равенство значений подменяется равенством хэшей?
-
Не понятно... Почему неубывающая последовательность неправильна?
И почему равенство значений подменяется равенством хэшей?
Потому, что вот псевдокод который пройдет твой тест:
in := open("input");
out := create("output");
for i:=0; i<in.size/4; ++i {
out.write(i);
}
При этом он ничего сортировать не будет. Ему вообще плевать на входные данные, ему важно только сколько этих данных.
-
Этот вариант не катит просто в силу того, что уже было в практике, когда на выходе была неправильная неубывающая последовательность чисел. Проверку оно проходило, но результат был не правильным.
Что за фигня? Это же простейший цикл, как он может дать неверный результат?
Пока проверка довольно тупая - через md5 суммы файлов ответов, исходим из того, что верные ответы у всех должны быть одинаковые, а вот ошибаются программисты в разных алгоритмах на разных языках, реализованных независимо друг от друга - по разному. Исходя из этого были выбраны вероятно правильные md5 суммы и теперь с ними сравниваются ответы.
"вероятно правильные md5 суммы" -- порадовало ))) вот она, партизанщина ))
-
Не понятно... Почему неубывающая последовательность неправильна?
И почему равенство значений подменяется равенством хэшей?
Потому, что вот псевдокод который пройдет твой тест:
in := open("input");
out := create("output");
for i:=0; i<in.size/4; ++i {
out.write(i);
}
При этом он ничего сортировать не будет. Ему вообще плевать на входные данные, ему важно только сколько этих данных.
В таком случае надо добавить проверку статистики файла -- сколько тех или иных чисел в обоих файлах ))
-
Я сравнивал суммы чисел - такая упрощенная статистика.
-
Я сравнивал суммы чисел - такая упрощенная статистика.
Ну, сумма чисел -- это упрощённая контрольная сумма, тогда уж лучше сразу хеш делать, например SHA-2, а не MD5...
-
Я сравнивал суммы чисел - такая упрощенная статистика.
Ну, сумма чисел -- это упрощённая контрольная сумма, тогда уж лучше сразу хеш делать, например SHA-2, а не MD5...
Тут есть нюанс суммы чисел можно посчитать имея input и не сортируя его, а вот md5 и sha2 уже не выйдет - чтобы их сравнивать с корректными нужно иметь сортированный корректный output. Т.е. чтобы проверить сортировку нужно реализовать сортировку.
-
Решение на modula-2 собранное gm2 шлепается с такой диагностикой:
this file (spill+0) has been opened for writing but is now being read
Command terminated by signal 6
-
Вот тебе и стандарты ISO. :-( Сейчас еще обнаружил, что в xds CARD16, CARD32..., а в gm2 CARDINAL16, CARDINAL32...
Пробовал gm2 из пакета поставить, вроде установилось, но не работает.
-
Вот тебе и стандарты ISO. :-( Сейчас еще обнаружил, что в xds CARD16, CARD32..., а в gm2 CARDINAL16, CARDINAL32...
Пробовал gm2 из пакета поставить, вроде установилось, но не работает.
Насколько я понимаю, проблема в чем-то вроде, что файл был открыт c флагом O_WRONLY а надо было с O_RDWR. Это если на позиксно-сишный язык переводить.
-
Вот тебе и стандарты 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
-
Насколько я понимаю, проблема в чем-то вроде, что файл был открыт c флагом O_WRONLY а надо было с O_RDWR. Это если на позиксно-сишный язык переводить.
[/quote]
Ну да. Но там же написано
SeqFile.OpenWrite(spill[spno], name, SeqFile.raw+SeqFile.read+SeqFile.old, res);
-
Ну да. Но там же написано
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.
-
Да! Еще надо поставить либу pth - если система дебианоподобная, то так: apt-get install libpth-dev
О! Поставил и заработало, даже собирать не пришлось.
Некоторые особенности сразу вылезли. Например, строку-константу нельзя индексировать.
-
Могу пока пользоваться xds для прогонов тестов, но уже на файле в 256Мб merge_heap выдает не правильный ответ. Поэтому, думаю, его в тесты пока не включу. merge_qs работает вроде бы корректно (на всех файлах еще не гонял).
-
Так, с ограничениями по памяти merge_qs падает:
Command exited with non-zero status 48
-
Так, с ограничениями по памяти merge_qs падает:
Command exited with non-zero status 48
Но при этом, как ни странно, выдает правильный ответ. Что ломает нафиг мои скрипты.
Какие-то чудеса с этой модулой.
-
Поправил скрипты, чтобы нормально отрабатывалось и модуловское решение (merge_qs), запустил быстрый прогон (каждый файл один раз будет прогнан). Так что часов через 5 наверно прогон будет закончен, результаты автоматически опубликуются.
-
Готовы новые результаты. Есть новый самый быстрый алгоритм - от 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
-
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.
-
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.
Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
-
То есть выходит, что чтобы и читать и писать, нужно использовать openedforrandom. Т.е., вероятно, использовать не SeqFile, а RndFile.
Я надеялся, что SeqFile как-то оптимизирван для последовательного чтения. Но похоже, там банально вызывается какой-нибудь fread/fwrite без буфферизации. Попробовал еще на аде. Там та же петрушка, только ещё медленнее раза в 2-3.
-
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.
Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
Для внешней сортировки всегда полезнее иметь несколько дисков, чем несколько процессоров.
-
Да, а многопоточное решение по производительности не отличимо в этом тесте от однопоточного.
Что очень странно. Единственное объяснение, которое я могу придумать - все уперлось в диск. А наблюдаемая разница на моем нетбуке - это потому что проц совсем дохлый.
Открыта тайна третьей планеты!
В смысле, я нашел в чем была засада - многопоточное решение не смогло слинковаться, в итоге вместо него тестировалось обычное fast (да, скрипты тестирования писал я, и у меня крайне кривые руки). Сейчас пофикшу.
-
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).
-
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).
Фикснул. Как я и предполагал - непрваильно поток прибивался, до того как он успел файлик записать :)
С памятью интереснее - у меня не получилось выставить ограничение (процесс не прибивается, если много отжирает).
-
А после того как собрали, многопоточка выходила за ограничения по памяти, а после фикса этого выдает не верный результат (размер файла не верен).
Фикснул. Как я и предполагал - непрваильно поток прибивался, до того как он успел файлик записать :)
С памятью интереснее - у меня не получилось выставить ограничение (процесс не прибивается, если много отжирает).
Через час-два будут результаты очередного быстрого прогона.
-
Результаты готовы.
-
Интересно, а срди тестов есть распределения с малой дисперсией?
-
Интересно, а срди тестов есть распределения с малой дисперсией?
скорее всего пока что нет. но всё будет :-) если для вашего алгоритма существует наихудший набор данных, то он будет среди тестов. :-)
-
Это не для моего :-). Мне кажется bucketsort с фиксированными корзинами должен на таких задачах страдать.
-
Это не для моего :-). Мне кажется bucketsort с фиксированными корзинами должен на таких задачах страдать.
Ну, это я отвлеченно говорил :-)
-
Ну вот тест на 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
-
В общем, дальше планы такие: я сейчас запущу пятикратный прогон теста. Потом, если кто-то будет обновлять/исправлять/добавлять решения я буду делать новые прогоны. С системе тестирования по крайней мере до понедельника никаких изменений не будет, не будет и каких-то решений от меня.
На следующей неделе (а если не уложусь, то и через неделю) я хочу допилить визуализацию результатов тестирования (очевидно, что текущий вариант не достаточно нагляден для случая когда у нас много разных решений), плюс добавлю дополнительные тесты а также модифицирую своё решение и добавлю ещё одно своё.
Потом хочу попробовать так или иначе найти ещё участников соревнования :-) Если никого больше не найдется, то будет финальное тестирование и подготовка к фазе 2.
-
А как насчёт сделать показ не абсолютных значений, а относительных?
Самый быстрый вариант - это 100%, а все остальные больше (или меньше) этой величины.
В таком случае можно будет прм обновлении одного варианта прогонять только самый быстрый и обновлённый варианты. Полный прогон, конечно, можно считать более точным, но его не обязательно делать ежедневно: нам же интересен порядок величин для оценки работы алгоритмов. То есть, если одно решение быстрее другого, то этого будет достаточно.
И ещё: сильно ли различаются результаты тестов, проведённых над одними и теми же алгоритмами в разные дни? Есть ли смысл перезапускать уже проведённые тесты?
-
Оказывается, xds под линуксом не умеет работать с файлами > 2GB :-(. Программы просто падают при первой же попытке чтения.
И у gm2 такая же фича, по крайней мере с библиотеками ISO.
-
Оказывается, xds под линуксом не умеет работать с файлами > 2GB :-(. Программы просто падают при первой же попытке чтения.
И у gm2 такая же фича, по крайней мере с библиотеками ISO.
А как они падают? Говорят что? Судя по всему оно не умеет работать с файлами >=2Gb - тесты же проваливаются начиная с 2Гб файлов.
-
Пишут
#RTS: unhandled exception #1: IOException.notAvailable Read
или
EXCEPTIONS.mod:57:3:IOChan: ChanId specified is invalid in RAISE
-
Попробовал через FIO, получил
this file (input) was not successfully opened
.
-
Попробовал через FIO, получил
this file (input) was not successfully opened
.
Стоп. А у тебя какая система с gm2? 32 или 64 бита?
Ибо по коду FIO.mod выходит, что такое может быть только если юниксовый open вернул -1.
-
32 бита.
Я уже дошел до си и fopen. Там тоже -1 и гуглить "Value too large for defined data type".
-
32 бита.
Я уже дошел до си и fopen. Там тоже -1 и гуглить "Value too large for defined data type".
Насколько я понимаю, этой проблемы не должно быть в 64битах (на 32битных системах у линукса были проблемы с файлами больше 2Гиг). Можешь простой пример на модуле через FIO накидать, чтобы я протестил?
-
Хм, на FAT32 все работает, даже XDS.
-
Хм, на FAT32 все работает, даже XDS.
Через FIO али как?
-
По-всякому. А на Ext4 ничего не открывает.
-
Тест для 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
-
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
-
Тест для 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? А то мы с компилятором фрустрируем и ругаемся, ибо не можем понять что это такое и где искать.
-
Блин, скопировал не оттуда. locsRead должно быть вместо n, или наоборот.
-
А это для 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
-
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Зато можно от 2 до 4.
На NTFS тоже работает, только медленно.
-
Ничего никуда не падает. Получается как-то так:
$ ./tulm
1023
$ ./tpim
4096
Сейчас ещё на сервака попробую.
-
Протестил, результат идентичный. Т.е., если я правильно понимаю, всё работает.
-
Значит, дело в системе. Ну да, у меня же и си не открывает. Но почему тогда моя прога на xds валилась? Потому, что 32-битный?
-
Значит, дело в системе. Ну да, у меня же и си не открывает. Но почему тогда моя прога на xds валилась? Потому, что 32-битный?
Либо так, либо у xds те же либы иначе реализованы. Кроме того, мы же сейчас попробовали ulm и pim, но не пробовали iso.
-
А можно ещё 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.
-
# ./tiso
4100
# ls -l input
-rw-r--r-- 1 root root 4294967296 Dec 11 14:29 input
-
Но чтобы быть уверенным до конца, я бы таки в тестах пробежался бы до конца файла.
-
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Это если размер кластера не менять. Но если его увеличить, то и размер файла может быть гораздо больше, чем 4 ГБ.
-
Хм, на FAT32 все работает, даже XDS.
На FAT32 же нельзя делать файлы объёмом даже в 4 гигабайта ровно -- только меньше...
Это если размер кластера не менять. Но если его увеличить, то и размер файла может быть гораздо больше, чем 4 ГБ.
И как это сделать? Вот я взял и отформатировал флешку 32 ГБт в FAT32, указав максимальный размер кластера -- 64 кБт, но файл размером 4.3 ГБт всё равно не записывается -- запись прерывается на 91% файла. Выходит, что не работает этот рецепт...
-
Размер файла так не увеличить, он ограничен структурой записи в каталоге. Только размер тома можно.
-
из вики:
Максимально возможный размер файла для тома FAT32 — ~ 4 ГБ — 4 294 967 295 байт (в FAT32 под размер файла отведено 4 байта. 4 байта - это 32 бита. 232-1 — 4 294 967 295 байт. Поэтому размер файла не может быть больше этого значения, иначе не получится указать его длину. Хотя цепочку в FAT таблице можно продолжать и дальше, но тогда для определения размера файла придется каждый раз пробегать по всей цепочке, а это будет занимать много времени.
Таким образом, файл может быть большим, но, похоже, его не создать стандартными средствами.
-
Почитал я TFM. Большие файлы в 32-битных системах рекомендуется открывать через fopen64 или open64, которые делают системный вызов open со специальным флагом. В gm2 все пути ведут к open, в xds - к fopen.
Подозреваю, что все, собранное с gcc -m32 и на 64-битной системе не сможет открыть 2GB файл.
-
А почему mege_rs не попал в тесты?
-
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
-
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
Особенно интересно в этом плане число 163 840 004 -- это 4*(80^4+1)...
-
А почему mege_rs не попал в тесты?
Потому что я криворукий рукожоп. Скоро будут результаты с merge_rs.
-
Предлагаю добавить в тесты файлы с нестандартными размерами, например 119 946 308 байт или 163 840 004 байт (достаточно большое простое число, умноженное на 4). Идея в том, что бы файл не делился на блоки равных размеров -- это может выявить ошибки в алгоритмах сортировки.
Да вроде никто не делит на равные блоки.
-
Смотрю на SSD ввод/вывод намного дешевле, чем на HDD. Эффект от сжатия слабее.
-
Прогон готов. На этот раз что-то сервер подтормозил и почти все алгоитмы отработали медленней процентов на 10-20.
-
Не удается запустить 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битной машине :-) Так что решение всё равно нужно!
-
Да, сейчас сервак перезагрузится, и я запущу полный прогон тестов.
-
Смотрю на SSD ввод/вывод намного дешевле, чем на HDD. Эффект от сжатия слабее.
Идея, в целом, верная, но не доведена до конца. Если увеличить до упора размер входного буфера, это может изменить расклад.
-
Да там особенно и увеличивать некуда, уже 100MB.
Интересно ещё, у меня merge_rs почти вдвое быстрее, чем merge_qs, а здесь немного медленнее.
-
Да, я не обратил внимание, что длина указана для массива 32 разрядных чисел, а не для байт. Тогда странно, что сортировка не самая быстрая, возможно, что это слабость компилятора или недочёт в библиотеках.
Поразрядная сортировка работает быстрей быстрой, поэтому на закэшированных файлах оказывается лучше, но из-за удвоенных требований по памяти приводит к увеличению временных файлов, что, по видимому, и приводит к перевесу быстрой в условиях ограниченной памяти.
-
Тогда странно, что сортировка не самая быстрая, возможно, что это слабость компилятора или недочёт в библиотеках.
Самая быстрая ( 256-buckets) - сортировка подсчетом. Там, правда, есть недостаток. На файлах от 8ГБ уже может возникнуть переполнение счетчиков, а если увеличить разрядность до 64 бит, они не влезут в ограничения.
-
Доступны новые, довольно странные результаты :-)
-
Ну, мы уже знаем, в чём причина таких результатов -- в чьей-то криворукости )))
-
Ну, мы уже знаем, в чём причина таких результатов -- в чьей-то криворукости )))
При том, что ничего не менялось (кроме добавления нового файла, ога), то возможно на этот раз криворукость уже не моя ;-)
-
А сколько занимает копирование файла?
-
А сколько занимает копирование файла?
Разово, или статистику хочется?
-
Можно и разово, порядок оценить. У меня сортировка ~ 1.5-2 копирования.
-
Можно и разово, порядок оценить. У меня сортировка ~ 1.5-2 копирования.
4Gb - 15 секунд.
-
Меж тем появилось решение на Аде.
-
Выглядит сурово, но судя по названию, это простое решение. Хотелось бы поглядеть на сложное.
-
Доступны результаты прогона, теперь и с адским решением: https://github.com/valexey/bigbench
-
Тем временем у нас новый прогон, новое решение на модуле-2 и новый рекорд :-)
-
А текущего адского решения любопытный баг - он проявляется только на нашем 4Гб тестовом файле. Ловим.
-
Новые результаты для пофикшенного решение на Аде.
-
Полгода прошло, какие выводы-то?
Сам я так и не осилил решение на Расте. Вроде на нём можно сделать вполне шустрый код, но выглядит он как говно, смотреть страшно, аж глаза кровоточат...
-
Какие выводы? Умение писать алгоритмы позволяет писать более эффективные решения, чем умение пользоваться стандартными библиотеками. В некоторых случаях сложность использования библиотек может быть на уровне или превышать сложность написания алгоритмов.