я обещал выложить реультаты, если получится что-то интересное. Хорошего не получилось, но мне лично всё равно интересно, так что выкладываю
Коротко о том, что я писал и что из этого вышло
Задача — автоматическое распараллеливание кода на Scheme. Подход — ленивые вычисления. Написан
компилятор в псевдокод и интерпретатор этого псевдокода. Все более-менее переносимо на
Windows/Linux/Unix/Mac OS. И даже работает на них (проверялось на Windows XP, Mac OS X, Ubundu).
Но вот эффективности добиться не удалось. На двухядерном ноуте с XP при добавлении многопоточности
удается получить повышение производительности на 10%, на двухядерном ноуте с Mac OS X — стабильное
понижение производительности в два раза А Ubundu у меня только в виртуалке стоит.
Но перед тем, как читать это, прочтите пару абзацев ниже
Извинения
Во-первых, текст оформлен на A5, 10-м Times-ом. Это у нас на факультете стандарт такой.
Чтобы нормально читать с экрана, нужно поставить 150%, тогда размер шрифта становится пристойным.
Во-вторых, почти нет шуток, совсем нет эпиграфов и мало картинок, а те, что есть — не цветные.
В прошлый раз (на бакалаворской) мне за особо удачный эпиграф поставили 3, с тех пор в
официальных документах не выпендриваюсь.
Во-третьих, соврешенно ужастное введение. Не читаейте. Точнее, прочтите, потому что всё —
правда, но учтите, что это один из тонких грязных трюков. Введение как-бы намекает, что
результатом работы будет (или хотябы может быть) увеличение производительности в 100 раз
Это совершенно не так. Но поскольку в прямую ничего подобного не обещалось, никто никому и не врал.
Нельзя так писать.
В-четвёртых, всё это — одна большая наглость с моей стороны. Чтобы нормально поднять такую тему
нужно на порядок больше знаний, чем у меня есть. Наглость прокатывает только потому,
что в этой области на моей кафедре никто не знает вообще ничего Я на их фоне выгляжу
корифеем.
Что читать
Введение — это такая агитка.
Первая глава — пожалуй, единственное, что есть интересного в тексте диплома.
Вторая глава — просто не читайте. Правда, она короткая
Третья глава — немного про архитектуру в целом.
Четвёртая глава — про реализацию компилятора. Интерес представляет нулевой раздел, остальное — только если вам вдруг правда интересно, как именно я писал компилятор.
Пятая глава — про реализацию интерпретатора. Аналогично четвёртой
Шестая глава — о! Целых три раздела Нулевой, 6.1.0, 6.2.0
Седьмая глава — пожалуй, вся, но она короткая
Заключение — ничего интересного.
Приложения 1,2 — только для фанатов, которые хотят продолжать моё дело
Поправки, ошибки, варианты, дополнения
* Много всего из стандарта не реализовано. Сразу предкпреждаю, чтобы не надеялись особо То, что реализовано, описано в приложении 1.
* Вопреки написанному в Приложении 1, не реализован or, and и cond. Компилятор их скомпилит, но интерпретатор — не поймёт. Это правда было очень просто, но чего-то лень было, да и ничего нового они не добавляют.
* Система оценок, конечно, слишком усложнена. Нужно было тупо считать ветки рекурсии, всё равно всё остальное игнорируется.
* На каждую ветку рекурсии нужно по потоку, иначе всё это работает плохо даже в теории. Но хотелось сначала добиться работоспособности от простой версии.
* Не реализован приоритет ожидающих исполнения заданий. Просто не придумал, на основвании чего этот приоритет устанавливать..
* make-файл работает на моём ubundu, но не сработал на Mac OS — там что-то с заголовочными файлами.. И ещё в Mac OS нет функции pthread_yield, но есть какой-то аналог.
* По-хорошему, нужно рассматривать всякие варианты, включая только частичную ленивость и разные стратегии вычисления спиков. Сложно, долго, не сделал.
В-пятых, за такое название нужно вешать на фонарном столбе. Что такое "система поддержки параллельного исполнения" не знает никто вообще Но ничего проще как-то не получилось...
Круто, честно.
Обидно, что для отличной оценки требуется красивое оформление, имхо по содержанию работа как раз тянет на научную разработку, в отличие от всяких там баз данных для какой-нибудь бухгалтерии.
Можно пару замечаний?
SH>
Что читать
SH>Первая глава — пожалуй, единственное, что есть интересного в тексте диплома.
По-моему, как раз тут ничего особо интересного нет. Таких статей я видел в интернете с десяток точно.
Обычный исторический анализ. Важно: тема параллелизма не раскрыта.
SH>Вторая глава — просто не читайте. Правда, она короткая
Как раз тут во многом (но не во всём) ответ на вопрос, почему не получился выигрыш в производительности.
SH>Третья глава — немного про архитектуру в целом.
Интересно, но мало. Тема параллелизма раскрыта, но хотелось бы по-подробнее.
SH>Четвёртая глава — про реализацию компилятора. Интерес представляет нулевой раздел, остальное — только если вам вдруг правда интересно, как именно я писал компилятор.
Хм... как программисту мне правда интересно.
SH>Пятая глава — про реализацию интерпретатора. Аналогично четвёртой
Я понял, ты издеваешься, самое интересное пропускаешь. Это я про пункт 5.4.
Полувопрос-полузамечание, у тебя везде при реализации красивый полиморфизм вместо условной логики, я ожидал, что и apply будет в том же духе.
SH>Шестая глава — о! Целых три раздела Нулевой, 6.1.0, 6.2.0
Вот самое интересное. Очень хотелось бы узнать про обоснвание собственного метода оценки, и его сравнение (практическое) с упомянутыми в работе.
Довольно сложно оценивать реализацию. Но подозреваю, что засада где-то в пуле потоков и синхронизации. Кстати, почему задачи для выполнения выбираются рандомом?
SH>Седьмая глава — пожалуй, вся, но она короткая SH>Заключение — ничего интересного. SH>Приложения 1,2 — только для фанатов, которые хотят продолжать моё дело
у каждого фаната своя реализация.
SH>Но вот эффективности добиться не удалось. На двухядерном ноуте с XP при добавлении многопоточности SH>удается получить повышение производительности на 10%, на двухядерном ноуте с Mac OS X — стабильное SH>понижение производительности в два раза А Ubundu у меня только в виртуалке стоит.
А на каких тестах ты это мерял? Одни простые числа можно считать чуть ли не десятью разными способами, которые могут очень сильно зависеть от гарбаджколлектора. Подсчёт ссылок может оказаться очень тормозным делом, особенно в многопотоковой программе.
Вот, получилось больше, чем пара замечаний, но это не умаляет твоей работы
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Можно пару замечаний?
За тем и писал
F>По-моему, как раз тут ничего особо интересного нет. Таких статей я видел в интернете с десяток точно. F>Обычный исторический анализ. Важно: тема параллелизма не раскрыта.
Ммм.. Может быть. Я ни одной не читал, всё из головы Так что, возможно, получилось как у всех.. То, что я писал "интересно" — это то, что стоит читать человеку, который не хочет погружаться в код по уши, а хочет приблизительно уловить суть.
Но просто эту главу мне самому интересно было писать. Какие-то идеи в голову пришли неожиданные, биографию фон Неймана почитал заодно Я же не знал, что эти идеи уже давно не новые.
F>Как раз тут во многом (но не во всём) ответ на вопрос, почему не получился выигрыш в производительности.
А можно озвучить? Я туда ответ не писал, если он там случайно оказался — мне правда интересно Если про потоки vs процессы, то легче бы не стало, им тоже требуется синхронизация. Один из вариантов реализации, который мне посоветовали, и который я не стал делать — сделать специальный поток-менеджер, который будет следить за пулом задач и раздавать их пулу потоков. В этом случае синхронизация не нужна. На windows я сделал бы это на сообщениях, с posix-системами сложнее, в принципе, можно сделать на событиях, но довольно громоздко получается (когда рабочий поток возвращает менеджеру результат — вот как он это делает без сообщений и синхронизации?)..
F>Хм... как программисту мне правда интересно.
Да, вот это я не учёл — не перестроился. До сих пор я всё это в основном непрограммистам втюхивал
F>Полувопрос-полузамечание, у тебя везде при реализации красивый полиморфизм вместо условной логики, я ожидал, что и apply будет в том же духе.
В смысле, сделать два объекта для лямбды — один с постоянным количеством параметров, другой — с переменным? Можно.. Не знаю, я так красиво пишу первый раз в жизни, честно говоря До сих пор таких понятных стройных иерархий не получалось. Но просто мне кажется, что создавать лишние сущности только для того, чтобы в одном месте не писать "if" это уже перебор. Сущность должна быть оправдана, и без того их много. Но это мне сейчас так кажется, большого опыта пока нет.
SH>>Шестая глава — о! Целых три раздела Нулевой, 6.1.0, 6.2.0
F>Вот самое интересное. Очень хотелось бы узнать про обоснвание собственного метода оценки, и его сравнение (практическое) с упомянутыми в работе.
Обоснование — хм. Могу идею описать, пойдёт?
Идея в том, что метод оценки сильно зависит от реализации. В смысле, если интерпретатор будет вычислять выражение лениво, то у выражения получится одна сложность, а если строго — то другая. Пример приведён в дипломе — сложность ленивого вычисления функции cons — 1, независимо от параметров. Сложность строгого может быть очень большой. И это должно быть учтено в оценке, даваемой компилятором, иначе оценка не будет иметь смысла.
У меня почти полностью ленивая реализация, поэтому и оценка должна быть соответствующая. Метод Мак-Кейба — это, практически, количество циклов. Я считаю те же циклы, но без учёта некоторых ветвей.
Другой вопрос, что обоснования эффективности такой реализации нет. Я думаю, что наиболее эффективным был бы полу-ленивый вариант, когда всё, кроме "длительных" операция выполняется сразу. А длительные — только когда их результат действительно нужен. Но для начала хотелось заставить работать более простой вариант.
F>Довольно сложно оценивать реализацию. Но подозреваю, что засада где-то в пуле потоков и синхронизации.
Я тоже так считаю. Нужно просто взять многоядерную машинку, поставить на неё Intel VTune и разобраться, что там происходит. К сожалению, все использованные в тестах ноутбуки — не мои По знакомым собирал..
F>Кстати, почему задачи для выполнения выбираются рандомом?
Это попытка обойти одну проблему.. Достаточно плоха ситуация, когда основному потоку потребовался результ вычисления выражения, которое только-только началось вычисляться. В этом случае он просто тупо стоит и ждёт. А такая ситуация возникает, например, в следующем коде:
Сначала основной поток вычислил map, создал список, а потом ему потребовалось значение первого элемента. Список создаётся быстро, если (func 1) вычисляется медленно, то основной поток будет довольно долго ждать и ничего не делать.
А при рандомном выборе задач, велика вероятность, что нужную задачу никто ещё и делать не начинал Тогда основной поток не простаивает, а выполняет её самостоятельно.
F>А на каких тестах ты это мерял? Одни простые числа можно считать чуть ли не десятью разными способами, которые могут очень сильно зависеть от гарбаджколлектора. Подсчёт ссылок может оказаться очень тормозным делом, особенно в многопотоковой программе.
Тесты простые:
(map fuct 1000 1000 1000 1000 1000).
fuct — это факториал Паралелится идеально, проблем никаких, но, блин, ускорения не видно.
Подсчёт ссылок — да, я даже прочитал в стандарте Scheme, что они советуют просто не удалять объекты Но я ведь сравниваю свою реализацию с ней же самой — только в одном случае всего один поток — основной, а во втором — много. Может быть, конечно, тормозит выделение памяти из разных потоков — это надо смотреть, смотреть, смотреть...
F>Вот, получилось больше, чем пара замечаний, но это не умаляет твоей работы
Спасибо что прочитал! Людей, которые читали мой диплом пока что настолько мало, что каждый дополнительный человек очень ценен
Здравствуйте, SergH, Вы писали:
SH>Ммм.. Может быть. Я ни одной не читал, всё из головы Так что, возможно, получилось как у всех.. То, что я писал "интересно" — это то, что стоит читать человеку, который не хочет погружаться в код по уши, а хочет приблизительно уловить суть.
Хм... для факультета кибернетики, по-моему, без погружения в код не обойтись.
SH>Но просто эту главу мне самому интересно было писать. Какие-то идеи в голову пришли неожиданные, биографию фон Неймана почитал заодно Я же не знал, что эти идеи уже давно не новые.
А вот это совсем зря. Когда я сдавал диплом (МИФИ, фак. кибернетики) у нас обязательно требовался обзор современных и не только методов в рассматриваемой области чтобы массово не изобретать велосипеды.
Кстати, что касается ФП и параллельности, то первое, что пишут во всех книгах/статьях — это, то, что в чистом виде все функции не имеют side-эффектов, поэтому всё параллелится на ура. У тебя, насколько я понял, нет фунций типа set_car! и тд.
F>>Как раз тут во многом (но не во всём) ответ на вопрос, почему не получился выигрыш в производительности.
SH>А можно озвучить? Я туда ответ не писал, если он там случайно оказался — мне правда интересно Если про потоки vs процессы, то легче бы не стало, им тоже требуется синхронизация. Один из вариантов реализации, который мне посоветовали, и который я не стал делать — сделать специальный поток-менеджер, который будет следить за пулом задач и раздавать их пулу потоков. В этом случае синхронизация не нужна. На windows я сделал бы это на сообщениях, с posix-системами сложнее, в принципе, можно сделать на событиях, но довольно громоздко получается (когда рабочий поток возвращает менеджеру результат — вот как он это делает без сообщений и синхронизации?)..
Там не ответ в чистом виде. Там причина — недостаточно исследован механизм реализации параллельности. Например, было бы интересно увидеть анализ того, сколько потоков должно быть в пуле для максимальной производительности, как они должны синхронизоваться и т.д. Имхо это очень важный вопрос. Есть же разные библиотеки для многопоточности, скорее всего их авторы оптимизировали, или по крайней мере описали грабли.
F>>Полувопрос-полузамечание, у тебя везде при реализации красивый полиморфизм вместо условной логики, я ожидал, что и apply будет в том же духе. SH>В смысле, сделать два объекта для лямбды — один с постоянным количеством параметров, другой — с переменным? Можно..
Имелась ввиду apply для стандартых функций. Логичней было бы вместо большого свитча сделать на худой конец map. Т.е. вместо
F>>Довольно сложно оценивать реализацию. Но подозреваю, что засада где-то в пуле потоков и синхронизации. SH>Я тоже так считаю. Нужно просто взять многоядерную машинку, поставить на неё Intel VTune и разобраться, что там происходит. К сожалению, все использованные в тестах ноутбуки — не мои По знакомым собирал..
F>>Кстати, почему задачи для выполнения выбираются рандомом? SH>Это попытка обойти одну проблему.. Достаточно плоха ситуация, когда основному потоку потребовался результ вычисления выражения, которое только-только началось вычисляться. В этом случае он просто тупо стоит и ждёт. А такая ситуация возникает, например, в следующем коде: SH>(map func 1 2 3 4) SH>Сначала основной поток вычислил map, создал список, а потом ему потребовалось значение первого элемента. Список создаётся быстро, если (func 1) вычисляется медленно, то основной поток будет довольно долго ждать и ничего не делать. SH>А при рандомном выборе задач, велика вероятность, что нужную задачу никто ещё и делать не начинал Тогда основной поток не простаивает, а выполняет её самостоятельно.
Вообще это очень похоже на теорию расписаний. Опять-таки есть много литературы на эту тему. Рандомный выбор — один из методов при вероятностной модели. Вообще, например, здесь, здесь... Гугл в помощь
F>>А на каких тестах ты это мерял? Одни простые числа можно считать чуть ли не десятью разными способами, которые могут очень сильно зависеть от гарбаджколлектора. Подсчёт ссылок может оказаться очень тормозным делом, особенно в многопотоковой программе. SH>Тесты простые: SH>(map fuct 1000 1000 1000 1000 1000). SH>fuct — это факториал Паралелится идеально, проблем никаких, но, блин, ускорения не видно.
Недавно здесь проскакивала забавная ссылка. Реализаций факториала может быть великое множество. Особенно большой выигрыш для твоего теста будет при мемоизации
SH>Подсчёт ссылок — да, я даже прочитал в стандарте Scheme, что они советуют просто не удалять объекты Но я ведь сравниваю свою реализацию с ней же самой — только в одном случае всего один поток — основной, а во втором — много. Может быть, конечно, тормозит выделение памяти из разных потоков — это надо смотреть, смотреть, смотреть...
Я как-то делал mark-scan GC. В зависимости от места его вызыва производительность изменялась на порядки.
SH>Спасибо что прочитал! Людей, которые читали мой диплом пока что настолько мало, что каждый дополнительный человек очень ценен
Да всегда пожалуйста Мне было интересно.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Кстати, что касается ФП и параллельности, то первое, что пишут во всех книгах/статьях — это, то, что в чистом виде все функции не имеют side-эффектов, поэтому всё параллелится на ура. У тебя, насколько я понял, нет фунций типа set_car! и тд.
Да. И там же обычно пишут, что реализаций почему-то до сих пор нет
F>Там не ответ в чистом виде. Там причина — недостаточно исследован механизм реализации параллельности. Например, было бы интересно увидеть анализ того, сколько потоков должно быть в пуле для максимальной производительности, как они должны синхронизоваться и т.д. Имхо это очень важный вопрос. Есть же разные библиотеки для многопоточности, скорее всего их авторы оптимизировали, или по крайней мере описали грабли.
Я же говорю — чтобы подномать эту тему по хорошему, нужно знать гораздо больше, чем знаю я. Ну не нашлось у меня знаний и времени для всего этого, и так то еле успел..
А какие, например, библиотеки имеются ввиду? Я до сих пор сталкивался только с родными потоками ОС, ну MPI ещё немного, но это не потоки. Мне бы подошла библиотека, просто реализующая пул потоков и пул заданий в некоторой форме
F>Имелась ввиду apply для стандартых функций. Логичней было бы вместо большого свитча сделать на худой конец map. Т.е. вместо F>
Я думал об этом. Но тогда где-то в коде было бы заполнение этого map-а, которое выглядело бы так же уродливо Я решил сделать непосредственно. Создавать на каждую стандартную функцию по классу.. Вообще-то эта идея просто не приходила мне в голову. Возможно, действительно получилось бы лучше. От switch-а никуда уйти всё равно не удалось бы, но могли появиться другие приемущества. Подумаю.
F>Вообще это очень похоже на теорию расписаний. Опять-таки есть много литературы на эту тему. Рандомный выбор — один из методов при вероятностной модели. Вообще, например, здесь, здесь... Гугл в помощь
Спасибо, посмотрю. Проблема в том, что я просто не знаю, которая задача когда понадобится, поэтому кроме простого FIFO и случайного выбора особо вариантов не вижу (LIFO конечно ещё есть, но он вроде ничем не оправдан). Тут нужно крепко думать... Если бы я знал приоритет, сделал бы очередь с приоритетами.
Вообще, по результатам диплома я решил заняться самообразованием — в области теории вычислений, теории компиляции, ну вот ты ещё подкинул пару тем
F>Недавно здесь проскакивала забавная ссылка. Реализаций факториала может быть великое множество. Особенно большой выигрыш для твоего теста будет при мемоизации
У меня то задача была нагрузить все ядра посильнее, чтобы время можно было замерять и разницу почуствовать между однопоточной версией и многопоточной. Если бы на этом простом примере многопоточная давала выигрыш, я бы начал усложнять модель и примеры.. Но до этого дело не дошло. Так что реализация самая тупая.
F>Я как-то делал mark-scan GC. В зависимости от места его вызыва производительность изменялась на порядки.
Ну сначала надо всё-таки посмотреть, что именно тормозит. Написание собственного менеджера памяти это очень интересно, но если тормоза где-то в другом месте, то и менеджер я буду писать в следующий раз
Да, уже нашёлся добрый человек с большим кластером под Linux, так что может ещё удастся что-то сделать
Здравствуйте, frogkiller, Вы писали:
SH>>Но просто эту главу мне самому интересно было писать. Какие-то идеи в голову пришли неожиданные, биографию фон Неймана почитал заодно Я же не знал, что эти идеи уже давно не новые.
F>А вот это совсем зря. Когда я сдавал диплом (МИФИ, фак. кибернетики) у нас обязательно требовался обзор современных и не только методов в рассматриваемой области чтобы массово не изобретать велосипеды.
Я имел ввиду не методы, тут я не открыл ничего нового. Я имел ввиду, что я наконец сам для себя действительно понял, в чём принциапиальная разница между императивным подходом и функциональным. И почему в функциональных языках не может быть циклов — во всяком случае, циклов в императивном понимании. Ну и прочие мелочи... Вот это было интересно.
А сам подход-и-метод укладывается в одну строчку — функциональный язык + параллельные ленивые вычисления
Здравствуйте, SergH, Вы писали:
F>>Кстати, что касается ФП и параллельности, то первое, что пишут во всех книгах/статьях — это, то, что в чистом виде все функции не имеют side-эффектов, поэтому всё параллелится на ура. У тебя, насколько я понял, нет фунций типа set_car! и тд. SH>Да. И там же обычно пишут, что реализаций почему-то до сих пор нет
думаю, что всё-таки есть, но у кого получилась удачная реализация, помалкивает в тряпочку и стрижёт баксы
SH>А какие, например, библиотеки имеются ввиду? Я до сих пор сталкивался только с родными потоками ОС, ну MPI ещё немного, но это не потоки. Мне бы подошла библиотека, просто реализующая пул потоков и пул заданий в некоторой форме
boost, например, чем плох?
Ещё я смотрел ACE. Но в своё время не смог вкусно его приготовить, и в конечном итоге написал довольно удачный (на мой взгляд ) велосипед, заточенный под конкретную задачу.
F>>Имелась ввиду apply для стандартых функций. Логичней было бы вместо большого свитча сделать на худой конец map. SH>Я думал об этом. Но тогда где-то в коде было бы заполнение этого map-а, которое выглядело бы так же уродливо Я решил сделать непосредственно. Создавать на каждую стандартную функцию по классу.. Вообще-то эта идея просто не приходила мне в голову. Возможно, действительно получилось бы лучше. От switch-а никуда уйти всё равно не удалось бы, но могли появиться другие приемущества. Подумаю.
Проще модифицировать и сопровождать классика ООП
SH>У меня то задача была нагрузить все ядра посильнее, чтобы время можно было замерять и разницу почуствовать между однопоточной версией и многопоточной. Если бы на этом простом примере многопоточная давала выигрыш, я бы начал усложнять модель и примеры.. Но до этого дело не дошло. Так что реализация самая тупая.
Я к тому, что по одному тесту трудно судить о методе и его преимуществах, ведь в конечном итоге нужен выигрыш в производительности на реальных промышленных и научных задачах. Может, на куче других тестов выигрыш будет значительнее?
SH>Да, уже нашёлся добрый человек с большим кластером под Linux, так что может ещё удастся что-то сделать
Удачи. Было бы интересно узнать, что из всего этого получится.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, SergH, Вы писали:
SH>Я имел ввиду не методы, тут я не открыл ничего нового. Я имел ввиду, что я наконец сам для себя действительно понял, в чём принциапиальная разница между императивным подходом и функциональным. И почему в функциональных языках не может быть циклов — во всяком случае, циклов в императивном понимании. Ну и прочие мелочи... Вот это было интересно.
Хм... А я прочитал в книке по хаскелю про монады и понял, что ничего не знаю ни про императивный, ни про функциональный подход. До сих пор не могу собрать разлетевшиеся мозги в кучку.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Я к тому, что по одному тесту трудно судить о методе и его преимуществах, ведь в конечном итоге нужен выигрыш в производительности на реальных промышленных и научных задачах. Может, на куче других тестов выигрыш будет значительнее?
На Mac OS наблюдается проигрыш
F>Удачи. Было бы интересно узнать, что из всего этого получится.
Если получится — я напишу.
Про хаскель — а я пока не читал про монады, поэтому понимаю
При этом тест выполнялся на Селероне Willamatte...
Никакой многоядерности, никакой многопоточности, правда и ленивости тоже никакой — включал оптимизацию в компиляторе.
Что бы вывод чисел не искажал результаты (чёрти сколько символов), я печатал не сами значения факториала 100000, а остаток от его деления на константу...
Мемоизации тут нет — все 4 функции выполнялись в отдельных запусках, да и списки совершенно разные...
Здравствуйте, deniok, Вы писали:
D> Но где-то эта линейность должна прекратиться, потому что в пределе будет D>
fac100000 = 1 * 2 * 3 * 4 * -- и так далее до 100000
D> Не может же это быть в 100000 раз быстрее product [1..n] ?
Ну да, ведь это — одно и тоже выражение, а значит и скорость выполнения должна быть одинаковой...
Рост скорости прекратится, когда перемножение промежуточных product'ов начнёт занимать время, сравнимое с вычислением самих product'ов. Если бы перемножались не числа от 1 до 100000, а сравнимые числа, то оптимально было бы вычислять около трёхсот промежуточных product'ов. Но так как там числа совершенно разные, то уже с несколькими десятками возникли бы чрезмерные накладные расходы...
Здравствуйте, geniepro, Вы писали:
G>Рост скорости прекратится, когда перемножение промежуточных product'ов начнёт занимать время, сравнимое с вычислением самих product'ов. Если бы перемножались не числа от 1 до 100000, а сравнимые числа, то оптимально было бы вычислять около трёхсот промежуточных product'ов. Но так как там числа совершенно разные, то уже с несколькими десятками возникли бы чрезмерные накладные расходы...
Мне кажется, не совсем так. Поскольку параллельности, нет, то от перемены мест сомножителей скорость не должна так радикально меняться. Наверное, пока мы не вылезаем за Int — умножение быстрое, а когда начинается Integer то оно становится гораздо медленнее, и чем больше — тем медленнее. Если это так, то оптимально набрать как можно больше product'ов в пределах Int, а потом уже перемножать то что получилось.
И ещё такой вопрос — что быстрее умножать x*10^90 на y*10^10 или z*10^50 на w*10^50? То есть на больших Integer'ах лучше держать сомножители "равномерными" или это уже не важно?
Здравствуйте, deniok, Вы писали:
D> Мне кажется, не совсем так. Поскольку параллельности, нет, то от перемены мест сомножителей скорость не должна так радикально меняться. Наверное, пока мы не вылезаем за Int — умножение быстрое, а когда начинается Integer то оно становится гораздо медленнее, и чем больше — тем медленнее. Если это так, то оптимально набрать как можно больше product'ов в пределах Int, а потом уже перемножать то что получилось.
В случае с факториалом мы вылетаем за пределы Int уже при 13! = 6 227 020 800, так что это роли практически не играет по сравнению с 100 000...
D> И ещё такой вопрос — что быстрее умножать x*10^90 на y*10^10 или z*10^50 на w*10^50? То есть на больших Integer'ах лучше держать сомножители "равномерными" или это уже не важно? у
ну, в данном конкретном случае Hugs говорит, что в первом случае (x*10^90 на y*10^10) расчёт и затраты памяти чуть меньше, чем во втором (z*10^50 на w*10^50)
Здравствуйте, deniok, Вы писали:
D> Но где-то эта линейность должна прекратиться...
Решил разобраться, когда начнёт падать скорость. Запустил вычисления факториала 100 000 с вычислением промежуточных product'ов количеством от 1 до 50:
import qualified Time
main = do let ff = product [1..num]
print ff
z <- sequence $ map (\x -> time x (print $ (parfact x num) == ff)) [1..50]
putStrLn $ unlines z
num = 100000
parfact :: Integer -> Integer -> Integer
parfact k n = pf k []
where
pf 0 w = product w
pf x w = pf (x-1) (product [x, (x+k)..n]:w)
time n f = do t1 <- Time.getClockTime
f
t2 <- Time.getClockTime
return $ show n ++ " " ++ show_TimeDif t2 t1
show_TimeDif ft st = show(Time.tdHour td) ++ ":" ++ show(Time.tdMin td) ++ ":"
++ show nsecs ++ "." ++ snms
where
td = ft `Time.diffClockTimes` st
secs = Time.tdSec td
ms = Time.tdPicosec td `div` 1000000000
(nsecs, nms) = if ms < 0 then (secs - 1, ms + 1000) else (secs, ms)
snms = reverse $ take 3 $ (reverse $ show nms) ++ "000"
Занятный результат: почти линейный рост скорости от 1 до 4 product'ов, затем рост скорости замедлился, после 13 product'ов прекратился вообще, а после 21 product'а время расчёта начало медленно, но верно расти:
Умц... Такое впечатление, что в первых версиях время тратится на какой-нибудь свопинг при последних тысячах 70 умножений. Не пробывал делать то же самое, но не для 100 000, а для 20 000, 30 000, 40 000, etc? По идее, если исходная посылка верна, оптимум разбиения на подпродукты должен наступать раньше.
Здравствуйте, deniok, Вы писали:
D> Такое впечатление, что в первых версиях время тратится на какой-нибудь
свопинг при последних тысячах 70 умножений. Не пробывал делать то же самое,
но не для 100 000, а для 20 000, 30 000, 40 000, etc?
Тут нужно учитывать погрешность измерений. Если для 10 000!,,50 000! я делал от трёх измерений и более, то от 60 000! — два-три. Ну там уже и флуктуации поменьше...
D> По идее, если исходная посылка верна, оптимум разбиения на подпродукты должен наступать раньше.
Да тут чёрт его знает... При малых значениях (10 000!..20 000!) действительно оптумум наступает при 7-8 product'ах, чем больше — тем он отодвигается дальше. Похоже, устаканивается где-то на 13-14 product'ах, что, кстати, не противоречит и малым значениям n!...
В общем, оптимально, похоже, всё-таки 13-14 product'ов...
Забавно, для малых факториалов такое разбиение на subproduct'ы даёт слабый выигрыш (до 3.5х), а вот чем дальше, тем выигрыш больше...
Интересно было бы попробовать действительно параллельное вычисление факториала на многоядерном процессоре. Жаль нет под рукой такого... :о(
Взять бы на восьмиядерном Mac'е запустить восемь потоков, а в них по 14 subproduct'ов. А учитывая, что одно ядро при оптимальном расположении команд может быть ещё и по два-три потока одновременно потянет... :о)
Я тут подумал, сделал оценки, и рост в два раза с продукта до произведения субпродуктов объяснить могу:
(1) Оцениваем по формуле Стирлинга
100 000! ~ 10^456 573
(2) Считаем "сложность" последних 9 умножений для умножения в лоб ("сложность" — это сумма степеней сомножителей — я почти уверен, что время умножения больших чисел растёт линейно по этому параметру)
456 573 * 9 = 4 109 157(*)
(сомножитель 10^5 не учитываю — его вклад мал)
(3) Оценим субпродукты
S1=1*3*5*...*99999
S2=2*4*6*...*100000
(3.1) Их произведение равно 100 000!=10^456 573
(3.2) Они практически одного порядка. Действительно рассмотрим
S3=3*5*...*100001
ясно, что
S1<S2<S3,
но при этом
S3/S1 = 100001
то есть отличие S1 и S3 — всего пять порядков, а S1 и S2 и того меньше.
(4) С точностью до +- несколько порядков
S1=S2
S1*S2=10^456 573
откуда
S1=S2=10^228 286
(5) Считаем "сложность" последних 9 умножений для субпродуктов
) велосипед, заточенный под конкретную задачу.
