Автор | Сообщение |
misha![]()
1275 сообщений |
#4593 2011-08-01 14:43 GMT+3 часа(ов) |
ЦитатаИ где тут сайд-эффекты? Я увидел лишь четкое разделение фаз по времени выполнения.Цитата ЦитатаВ трех строчках кода разобраться не можете?Цитата ![]() (setq $call/cc ЦитатаКто создал ToyLisp, я или вы? Зачем вы неправильно комментируете?Цитата ЦитатаТолько хорошие реализации следуют требованиям стандарта. Что в этом не понятно? Да и оптимизация хвостовых вызовов довольно примитивная задача. |
|
Kergan
300 сообщений |
#4594 2011-08-01 16:48 GMT+3 часа(ов) |
Цитата Я там даже подписал, где сайдэффекты ![]() Цитата Ну да, которое в CL невозможно. О чем и речь. Цитата Да нет, как реализуется call/cc на основе cps-преобразования я в курсе, вы мне реализацию _своего_ call/cc покажите, то есть того, которое используется в функции factorial, а не в функции $factorial. Кроме того, не ясно, какое отношение к скорости вызова продолжений/функций имеет ваш пример. Во-первых, продолжение в вашем примере вызывается лишь однажды (в обоих случаях), для сравнения надо вызвать его, ну, хотя бы 1000000 раз. Далее, поскольку вы используете умножение, в вашем примере 99% времени исполнения уходит на работу с бигнумами. Чтобы получить коректные результаты, нужно нечто вроде этого:
ну и далее вызываем 1000000+ раз f и cont. Сравниваем результаты. |
|
Kergan
300 сообщений |
#4595 2011-08-01 16:53 GMT+3 часа(ов) |
Цитата прошу прощения, а при чем тут ваш ToyLisp? Мы говорили в общем о реализации продолжений, если _у вас_ в вашем ToyLisp функциональный вызов сделан _настолько_ медленно, что даже вызов продолжения работает быстрее - то это проблемы вашего ToyLisp. При человеческой реализации вызова ф-й (как во всех нормальных диалектах) сделать вызов продолжения быстрее вызова ф-и просто невозможно, потому что вызов продолжения включает в себя вызов ф-и. Цитата требованиям стандарта следуют _все_ реализации, если же какая-то в чем-то не следует - то это уже не реализация схемы, это реализация другого языка. Тем более если речь идет о такой вещи, как оптимизация хвостовых вызовов (это одна из ключевых особенностей схемы). Цитата ДА, но в той же жабке ее реализовать невозможно. с чего, собственно, и начался разговор. |
|
misha![]()
1275 сообщений |
#4596 2011-08-01 18:04 GMT+3 часа(ов) |
Цитата Это не сайд-эффекты! Цитата Кому нужно тот реализует ![]() Цитата Не похоже ![]() Цитата Это встроенная функция. Цитата Никакого ![]() ЦитатаНу и как же я это сделаю без вмешательства в исходники ToyLisp-а? ![]() |
|
misha![]()
1275 сообщений |
#4597 2011-08-01 18:16 GMT+3 часа(ов) |
Цитата А что уже и пример привести нельзя? ![]() Цитата С чего вы взяли, что функциональный вызов обязан быть быстрее вызова продолжения? ![]() Цитата "потому что вызов продолжения включает в себя вызов ф-и" - вот тут вы ошибаетесь. ЦитатаЭто вы им расскажите ![]() Цитата Нет так нет ![]() отредактировал(а) misha: 2011-08-01 18:23 GMT+3 часа(ов) |
|
Kergan
300 сообщений |
#4598 2011-08-01 21:28 GMT+3 часа(ов) |
Цитата Конечно же, это сайд-эффекты. Любой вызов ио-функций - сайд-эффект. Цитата Это нужно, очень нужно, хотя бы ради раздельной компиляции (и для возможности писать корректные макросы, конечно же) - вот нету в CL раздельной компиляции и приходится велосипедить всякие tree шейкеры, да и те в проприетарных реализациях, но в CL это сделать нельзя в принципе - придется менять модель вычислений CL. То есть это уже будет не CL. А, ну еще можно всегда написать на CL racket vm ![]() Цитата Наверное, я лучше знаю, что имел в виду? ![]() Цитата это относилось как раз к call/cc из factorial - чего толку сравнивать, если не известно, как она работает? Цитата ну значит реализацию этой встрокенной функции. И реализацию замыканий ![]() Цитата Ну вы показали, что у вас функции-замыкания вызываются медленнее, чем обычные функции - в чем нету ничего странного. Однако, на практике рекурсия с 10000 вложенностью бывает не часто. Цитата Yу вы замените по крайней мере (* n ...) на (+ 1 ...) Цитатану, обычно потому, что стараются уменьшить оверхед на функциональный вызов. Цитата вызов функции - кладем аргументы на стек, делаем джамп вызов продолжения - кладем аргументы на стек, делаем джамп. но, конечно, в ToyLisp все можэет быть иначе ![]() Тогда перефразируем "вызов продолжения не может быть быстрее номарльно реализованного функционального вызова". Цитатакому им? вы знаете реализацию схемы без оптимизации хвостовых вызовов? |
|
misha![]()
1275 сообщений |
#4599 2011-08-02 01:02 GMT+3 часа(ов) |
Цитата Каждая фаза имеет свое пространство имен, которое совмещается с таким же во время экспанда. Цитата В принципе, согласен ![]() Цитата Шуток не понимаете ![]() Цитата Создает продолжение и передает его функции в качестве аргумента. Цитата Я всего лишь хотел показать, что классическое cps-преобразование не самое эффективное решение. Есть и другие подходы (варианты) continuation-passing. Цитата Я сегодня сравнил скорости фрагментов кода отвечающих за вызовы. Ну в общем как я и предсказывал, т.е.они практически не различаются. |
|
misha![]()
1275 сообщений |
#4600 2011-08-02 02:04 GMT+3 часа(ов) |
Цитата Где заменить? Не думаю, что это что-нибудь даст, потому что продолжение ... Цитата Если бы я реализовал компиляцию в native код, то продолжения были бы реализованы как класс (с публичным методом). Цитата Но пред этим для не хвостового вызова сохраняем состояние ![]() Цитата У меня вместо джампа вызывается встроенная функция ![]() Цитата У меня интерпретатор байткода, а вы говорите о реализациях компилирующих в native код. Т.к. там lambda, continuation можно считать как производные классы от какого-нибудь базового класса, например, procedure. Цитата Студенческих поделок навалом. |
|
Kergan
300 сообщений |
#4601 2011-08-02 07:52 GMT+3 часа(ов) |
Цитата К чему вы это сказали? Сайд-эффекты от этого перестают быть сайд-эффектами? Цитата ну так ка именно? очевидно, если мы хотим нормально сравнить А и В, то надо знаьт, чот это за А и В. Цитата Но не показали ![]() и не покажите, потому что не взможно. Вызов продолжения при cps-преобразовании - это просо вызов замыкания, а вызов продолжения всегда медленее вызова замыкания. Если, конечно, в вашем диалекте вызов замыкания изначально не реализован сверхнеэфективно. Цитатав factorial и $factorial Цитата А при чем тут вообще продолжения? У вас там нигде скорость работы продолжений не анализируется - у вас там в одном случае вызывается цепочка замыканий, в другом случае - цепочка обычный функций. Соответственно, скорость таких вызовов вы и сравниваете... сравнивали _бы_ если бы у вас была дешевая функция, а не умножение бигнумов. Цитата Не надо ничего сохранять. Зачем? А вот с хвостовыми вызовами, наоборот, ситуация гораздо веселее - не при любом хвостовом вызове оптимизацию можно применить, так что следует следиь за этим фактом. Цитата ну то есть с моим последним утверждением вы спорить не станете? ) Цитата ну и кому они нужны? кто-то всерьез рассматривает такие студенческие поделки? |
|
misha![]()
1275 сообщений |
#4602 2011-08-02 16:49 GMT+3 часа(ов) |
Цитата Фазы были созданы для того, чтобы избавить вас от сайд-эффектов. Цитата Передает как и в $call/cc, т.е. > (disassemble (lambda() (call/cc (lambda(r) (r 1))))) А как создает я уже описывал ранее. Цитата Статей на эту тему навалом. Цитата По вашему вызов замыкания медленнее вызова замыкания? ![]() Цитата Вы вообще читаете мои посты? У меня скорости вызовов замыкания и продолжения практически равны. Цитата Это ничего не даст. Цитата Я сравниваю методы реализации continuation-passing. Цитата Джамп - это безусловный переход. Как возврат осуществлять будете для не хвостового вызова. Цитата Все зависит от выбранной модели реализации лиспа. Цитата А вы не сравнивайте козу с бараном ![]() Цитата Ну MzScheme(Racket) тоже начинался как студенческая поделка ![]() |
|
Kergan
300 сообщений |
#4603 2011-08-02 21:54 GMT+3 часа(ов) |
Цитата фазы были созданы для того, чтобы дать возможность контролировать сайд-эффекты. Избавить от сайд-эффектов нельзя - вот я написал (display "phase") и вот он сайд-эффект. Как вы собираетесь от него "избавить"? Цитата У продолжений, реализованных через cps, есть свои недостатки, да. Но по скорости вызова такая реализация наиболее эффективна. Альтернативные реализации обычно медленнее раз эдак в сотню-тысячу (наиболее быстрые из альтернативных, ессно, для медленных все еще печальнее). Цитата Просто обычно продолжение в вызову не сводится - приходится при вызове продолжения проводить еще некоторую доп. работу. Цитата Ну я и говорю - у вас вызов замыкания сделан настолько неэффективно, что вызов продолжения равен ему по скорости. При эффективной реализации замыканий продолжения будут вызываться медленнее (сто-тысяча раз, как я выше указал) Цитата Конечно даст, если вы сделаете подобную замену, то тогда ваш тест будет измерять то, что надо (скорость работы ззамыканий). На данный же момент он измеряет скорость работы бигнумов. Цитата В функции factorial нету никакого continuation-passing, не врите. Цитата Вызов функции - это и есть безусловный переход. Возврат из функции - еще один безусловный переход. Вы не знали? Цитата У Маттиаса к моменту создания PLT уже было несколько публикаций, как-то не тянет на "студенческую поделку" |
|
misha![]()
1275 сообщений |
#4604 2011-08-02 22:45 GMT+3 часа(ов) |
Цитата Это не сайд-эффект! Читайте мануалы. Цитата Читайте оригинальные статьи, пытайтесь реализовать описанные в них модели. Цитата Вы путаете скорость вызова с восстановлением состояния. У меня остаточные вычисления нигде не сохраняются, но у меня есть стек данных, стек возвратов и указатель на код функции, которые я копирую во время создания продолжения, и восстанавливаю их во время вызова продолжения. Это гораздо эффективнее, чем тянуть за собой хвост из сотен замыканий. Цитата Я не понимаю о чем идет речь. Что вы подразумеваете под вызовом замыкания? Скорость операции CALL или скорость вычисления функции. Цитата Какой дурак вам это сказал? |
|
misha![]()
1275 сообщений |
#4605 2011-08-02 22:59 GMT+3 часа(ов) |
Цитата Зачем вам это нужно? У меня создание продолжения требует определенного времени (зависит от величины стеков), а его вызов (восстановление состояния) происходит за линейное время (Вы хотите его измерить?). Цитата Вы вообще читаете о чем я пишу? Цитата Как происходит операция CALL? Цитата А вы их читали? |
|
Kergan
300 сообщений |
#4606 2011-08-03 00:56 GMT+3 часа(ов) |
Цитата Я вижу, что ваше определение понятия "сайд-эффекта" отличается от общепринятого. вы уж скажите, что под ним подразумеваете. Цитата Это вы к чему? Цитата Эьто вы путаете. я говорю именно о скорости вызова - который может как включать так и не включать восстановление состояния, в зависимости от реализации. ЦитатаЭто выгоднее только в одном случае - если вызов замыкания реализован неэффективно. Если же вызов замыкания пренебрежимо мало отличается по скорости от вызова функции не-замыкания, то никакого преимущества перед "хвостом из замыканий" ваша модель не дает. Зато имеет кучу недостатков, вот например вы пишете: "но у меня есть стек данных, стек возвратов и указатель на код функции, которые я копирую во время создания продолжения", а во время вызова замыкания ничего этого копировать не надо. Цитата Под вызовом я понимаю вызов - то есть, конечно же, операцию call. Скорость вычисления функции и та всегда одинакова - хоть внутри замыкания ее вычисляй, хоть как. Цитата Никто не говорил, это имперический результат. Можете для интереса сами взять и потестировать производительность продолжений в наиболее известных реализациях. Вы, видимо, просто не совсем понимаете, что продолжения не существуют сами по себе, в отрыве от рантайма, и по-этому на практике при вызове продолжения необходимы очень большие накладные расходы в сравнении с обычным функциональным вызовом. Продолжения (в отличии от функции) нельзя реализовать простым джампом - вам в любом случае придется проводить весьма нетривиальные преобразования над стеком, да еще и аллоцировать память в хипе, если вы хотите, чтобы все это работало. Именно по-этому реализация продолжений на основе cps-преобразования считается самой эффективной, причем настолько эффективной, что никакие другие реализации не подходят даже близко. Цитата Мне? Незачем. Это вам нужно. Вы хотели померить скорость работы замыканий/продолжений, а зачем-то меряете скорость работы арифметических операций над бигнумами. Я на это и указал. Цитата За линейное от чего? Цитата Конечно читаю, другое дело, что вы очень часто отвечаете невпопад и скачете с одной темы на другую, вот ка сейчас. Вы писали: "Я сравниваю методы реализации continuation-passing." Я и указал на то, что это не правда - у вас там нету никакого continuation-passing. А как вы можете сравнивать то, чего нет? Цитата кладем на стек адрес возврата и делаем джамп на тело функции Цитата Нет, настолько старые публикации я не читал. Но можно найти и посмотреть, что там, при желании. |
|
misha![]()
1275 сообщений |
#4608 2011-08-03 15:14 GMT+3 часа(ов) |
Цитата В вашем примере я не увидел ни одного сайд-эффекта - все в соответствии с документацией. Цитата Мне ваши голословные заявления уже надоели. Цитата Ну так пишете понятнее. Цитата Это слишком простая операция ![]() Цитата Как раз у меня "вызов замыкания пренебрежимо мало отличается по скорости от вызова функции не-замыкания". Цитата Не надо, потому что уже все "скопировано". Цитата Наиболее известные реализации используют сложные стеки, так что там и захват, и вызов происходят очень быстро. Конечно, медленнее чем вызов функции, но не в сотни раз. Цитата "аллоцировать память в хипе" - если и приходится, то это в крайнем случае. Копипаст сегментов происходит очень быстро. Тогда почему до сих пор используются стеки? ![]() Цитата Я измерял время работы двух подходов на примере вычисления факториала. Цитата Пардон, за константное. Цитата Там нету cps, но создание продолжения присутствует. Цитата Так что это не только джамп. отредактировал(а) misha: 2011-08-03 15:26 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#4609 2011-08-04 00:08 GMT+3 часа(ов) |
Цитата Приведите мне ваши тесты, и главное прокомментируйте во сколько раз хуже. Не надо мне говорить что-то типа "смотрите и делайте выводы сами". |
|
Kergan
300 сообщений |
#4611 2011-08-04 10:12 GMT+3 часа(ов) |
Цитата Ну да, в соответствии с документацией. Я где-то говорил иное? Еще раз - напишите, что вы понимаете под термином "сайд-эффект". явно не то, что понимают все остальные, но мне интересно - что? Цитата Укажите хоть одно. Но это не важно, еще раз - к чему вы сказали-то процитированную фразу? Цитата Я сразу четко и понятно написал - "скорость вызова". не моя вина, что вы все время прыгаете с одного на другое и трактуете все термины по-своему. Цитата Ну вы же умудрились реализовать в своем диалекте эту простую операцию та неэффективно, что она не быстрее вызова продолжения ![]() Цитата Вы имеете в виду оверхед самого преобразования? Не так велик. Цитата Вот именно. ЦитатаЗахват - это вообще охренительно долгая операция, потому что при захвате надо скопировать весь стек в хип. Именно по этой причине, кстати, нету способа реализовать в scheme аналог return'a - сделать то его на продолжениях можно, но поскольку при каждом функциональном вызове надо делать захват продолжения, производительность падает на порядки. При чем это даже при использовании escape continuations, которые в среднем в десятки раз быстрее обычных. Вообще, вы забываете одну простую вещь - с эффективной реализацией продолжений хорошо в теории, но на практике, когда эти продолжения должны работать с тредами и ffi, начинаются проблемы. Цитата Вы про какое именно использование? Цитата А зачем сравнивать время работы операций на бигнумах с таким же временем работы таких же операций на таких же бигнумах? ![]() Цитата Ок, это push и jump. Велика разница? Цитата Именно так и скажу. |
|
misha![]()
1275 сообщений |
#4612 2011-08-04 13:30 GMT+3 часа(ов) |
Цитата Сайд-эффект - побочный эффект. Цитата Без доказательства это чушь: "Именно по-этому реализация продолжений на основе cps-преобразования считается самой эффективной, причем настолько эффективной, что никакие другие реализации не подходят даже близко." ЦитатаЦитата Вы не понимаете почему у меня cps хуже копирования стека, объяснить? Цитата Это у меня копируется весь стек, но все равно это быстрее использования замыканий. Кстати, можете запустить мои факториалы в Chez Scheme (у Racket gc шалит, но в общем результаты похожи на Chez Scheme) и представить свои результаты. По моим результатам cps ничем не лучше встроенного механизма. Цитата Это уже проблема разработчиков. Цитата Использование для создания продолжений. Цитата Я вам представил средние результаты. Цитата Конечно ![]() Цитата Не можете справиться с такой примитивной задачей? отредактировал(а) misha: 2011-08-04 13:42 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#4613 2011-08-04 16:13 GMT+3 часа(ов) |
Цитата Сегодня наконец таки закончил переписывание ToyLisp. Я исправил старые ошибки, избавился от стека возвратов, а также сменил порядок вычисления аргументов при вызове функции на стандартное (LR). > (disassemble (lambda() (+ 1 2 (- 3 4) 5))) Решил повторить тест.
Это средние значения. Если сменить умножение на сложение, то gc не даст получить нормальные результаты. отредактировал(а) misha: 2011-08-04 16:30 GMT+3 часа(ов) |
|
Kergan
300 сообщений |
#4614 2011-08-04 19:51 GMT+3 часа(ов) |
Цитата Ну тогда чего же вы говорите, что побочных эффектов нет? Там в примере вызывалась функция displayln, побочный эффект которой - вывод строки. Цитата Я вас уже это доказал. При вызове продолжения надо сделать _как минимум_ столько же работы, как и при вызове замыкания. При использовании cps-преобразования этот минимум достигается, при использовании другой реализации возникает ряд накладных расходов,, которые в случае cps-преобразования просто отсутствуют как класс. Цитата А он хуже? Вы этого пока не показали. Цитата Стек копируется практически во всех реализациях. Можно только тем или иным способ оптимизировать этот процесс, но от аллокаций на хипе вы никуда не уйдете в любом случае. Цитата Но приведенные вами тесты не имеют никакого отношения к производительности продолжений и cps-преобразования. Что вы хотите доказать на основе этих тестов? Я не могу понять. Цитата Принадлежность проблем их наличия не отменяет. Цитата А почему стек для этого не должны использовать? Цитата Вы невнимательно читаете вопрос. Я повторюсь: "А зачем сравнивать время работы операций на бигнумах с таким же временем работы таких же операций на таких же бигнумах?" или. Переиначив - ЗАЧЕМ вообще вы проводили эти тесты? Что вы ими хотели показать? Цитата Это уже становится смешно. итак, в ваших тестах во время вополнения происходит три вещи: 1. арифметические операции над бигнумами 2. гц 3. полезная нагрузка (вызов продолжений и т.п.) я вам указал, что вы (по невнимательности, видимо) не учли, что операции над бигнумами в данном случае занимают 99% времени вашего теста. т.о. производительность полезной нагрузки вы этими тестами не измерите. И что же? Оказывается у вас даже без учета бигнумов гц жрет столько процессорного времени, что нормальных результатов получить нельзя, и что вы сделали, чтобы исключить этот фактор7 просто добавили длинные бесполезные операции, которые будут весомы на фоне гц! Ну вы с такой же радостью могли реализовать свой факториал так:
и получили бы в точности те же результаты. |
|
misha![]()
1275 сообщений |
#4615 2011-08-04 21:49 GMT+3 часа(ов) |
ЦитатаЯ не думаю, что принт стоит относить к сайд-эффектам. Цитата В cps продолжения создаются всегда, а при их вызове приходится осуществлять цепочку хвостовых вызовов. Во время хвостового вызова приходится удалять точку возврата. При использовании стека продолжение создается когда это необходимо. При вызове приходится копировать массив, но эта операция происходит довольно быстро. Поэтому для меня прямое взаимодействие со стеком предпочтительней. Цитата Он не хуже, по скорости эти два подхода практически эквивалентны. Но все таки стеки чуть быстрее (на 2%-3% в зависимости от реализации), да и не приходится постоянно создавать дополнительные замыкания. Цитата Вы имеете в виду, что требуется скопировать фреймы? Ну так старые удалятся. Цитата Просто сравнил два подхода, что тут не понятного? Цитата Вы же писали, что cps лучше ![]() |
|
misha![]()
1275 сообщений |
#4616 2011-08-04 22:42 GMT+3 часа(ов) |
Цитата Попробуйте произвести измерения на Racket, там gc подключается еще чаще, чем у меня. Но в этом нет ничего необычного. Как вы предлагаете произвести измерения? Ведь даже у меня эти два подхода практически эквивалентны по скорости, если учитывать не средние, а минимальные значения, полученные в результате теста. отредактировал(а) misha: 2011-08-05 00:26 GMT+3 часа(ов) |
|
Kergan
300 сообщений |
#4617 2011-08-05 12:21 GMT+3 часа(ов) |
Цитата Что значит "стоит" или "не стоит"? по факту любой ио-эффект является побочным, это не вопрос личных пристрастий ![]() Цитата Во время хвостового вызова точка возврата просто _не создается_. Соответственно, и удалять ее не надо ![]() Цитата Наоборот - довольно медленно в сравнении с обычным вызовом (на порядки медленнее). Вообще, тут два разных аспекта - при cps-преобразовании вызов продолжения очень быстр (в сотни раз быстрее, чем при других реализациях), но исполнение продолжения будет медленнее, т.к. вместо обычного выполнения вызывается цепочка замыканий. Т.о. если мы вызываем множество "маленьких" продолжений (и важна скорость вызова) предпочтительнее cps-вариант. Если же вызываются "большие" продолжения и редко - предпочтительнее вариант со стеком. Есть и еще один аспект - оверхед по памяти. У стековых продолжений он реально огромен, вам при аллокации нескольких тысяч продолжений и то может выжрать весь хип и уронить гц. При cps-реализации у нас продолжение представляется одним единственным фреймом стека, по-этому даже миллион продолжений вполне можно будет переварить. Короче, оптимальным вариантом являлась бы возможность выбирать нужную реализацию продолжений в зависимости от того, какова наша задача. Что в сущности, стековый вариант и делает - для cps-продолжений поддержка рантайма не нужна, и их, если надо, всегда можно сделать руками. Цитата Чуть быстрее _что именно_? У вас там в тестах создание продолжение и его вызов - это пара миллисекунд максимум, остальное время у вас бигнумы умножаются. Цитата Я никогда не писал, что он лучше, я писал, что операции создания/вызова продолжений в cps-реализации на порядок быстрее. Цитата Правильно! Ведь у вас почти все время работы - это перемножение бигнумов, которое и там и там работает с одинаковой скоростью ![]() И gc, кстати, подключается именно из-за бигнумов - если бы операции не выходили за пределы фикснумов, то гц бы практически не работал. Вот скорость вызова можно померять, например, как-то так:
результаты:
вот скорость создания продолжения:
результат:
|
|
Kergan
300 сообщений |
#4618 2011-08-05 12:25 GMT+3 часа(ов) |
вот еще escape continuations для сравнения:
результат:
|
|
misha![]()
1275 сообщений |
#4620 2011-08-05 13:50 GMT+3 часа(ов) |
Цитата По какому факту? Цитата В теории ![]() Цитата Да кто бы спорил ![]() Цитата Зависит от реализации. Можете в этом убедиться. Цитата При cps-реализации продолжения хранятся в замыкании, поэтому там также при аллокации нескольких тысяч несвязанных между собой продолжений может выжрать весь хип и уронить гц. ЦитатаПридется реализовывать собственный интерпретатор. Цитата Я уже указал, что именно. Ведь я сравниваю не вызовы, а два подхода на примере вычисления факториала. Цитата Быстрее вызов, но не его создание. Пройдитесь по цепочке вычислений необходимых для создания продолжения. Цитата А вы представьте какое количество элементов ложится и удаляется со стека. Цитата Скорость вызова меня в данный момент не интересует, т.к. она зависит от реализации. Мне было важно сравнить два подхода к реализации продолжений для ToyLisp-а, что я и сделал. Кстати, ваши же тесты на Chez Scheme: > (time (test2 100000)) Цитата Этот тест не учитывает дополнительные расходы вызванные использованием for и вызовом лямбды. отредактировал(а) misha: 2011-08-05 13:59 GMT+3 часа(ов) |
|
Kergan
300 сообщений |
#4621 2011-08-05 18:17 GMT+3 часа(ов) |
Цитата По определению понятия "побочного эффекта": [url]http://en.wikipedia.org/wiki/Side_effect_(computer_science)[/url] Цитата "Подтирать" - всмысле сдвигать указатель на вершину? Цитата Если у вас стек копируется (что происходит в большинстве реализаций), то оверхед по памяти линеен по размеру стека (то есть линеен по размер фрейма*количество фреймов), в cps-реализации оверхед по памяти линеен от размера текущего фрейма. Цитата Угу, но в cps-реализации ничего _не копируется_. Другими словами, любой фрейм существует в единственном экземпляре. В реализации со стеком у вас может быть сотня копий одного фрейма, в зависимости от того, сколько вы продолжений наплодите. Цитата Зачем же? во-первых, можно сделать преобразование автоматически (как, например, в #lang web-server в racket), а если нужно в паре отдельных мест - можно напрямую руками переписать. Цитата Хорошо, я перефразирую вопрос - _по каким критериям_ вы сравнивали эти два подхода7 как вы утверждаете не по скорости. Тогда по каким? Цитата Ничего подобного, при создании продолжения выигрыш еще более очевиден. В реализации со стеком вы копируете стек (за счет аллокаций на хипе это _уже_ более дорого, чем любой другой метод аллокаций не требующий), а тут - просто передаете в ф-ю один дополнительный аргумент. Другими словами, опять же, создание продолжения в реализации со стеком _строго включает_ в себя cps-реализацию, т.к. нам надо на каждый функциональный вызов скопировать адрес возврата, что уже дольше передачи 1 аргумента (который тоже делается на каждый вызов). Цитата Где и когда? Цитата Я так и не понял, что вы сравнивали. Вы написали два куска кода, которые ничем не отличаются и получали закономерный результат, что эти два куска кода выполняются за одинаковое время. Смысл? Цитата я как понял это Petit? Ну это же интерпретатор, какой смысл сравнивать? |
|
misha![]()
1275 сообщений |
#4622 2011-08-06 17:00 GMT+3 часа(ов) |
Цитата Притн может быть сайд-эффектом когда отсутствует терминал(консоль), происходит запись в файл, печать со сдвигом каретки и др. Кстати, Racket создает консоль, когда она отсутствует. Цитата Да. Цитата У меня копируется не стек, а ссылки на объекты. > (factorial 10) stack-size - размер массива объектов. Цитата cps-реализации создаются замыкания и копируются ссылки на продолжения. В хорошей реализации со стеком полностью копируется только то, что необходимо, а в основном копируются ссылки. Если бы вы провели исследование, то узнали бы, что cps-продолжение и копия стека у большинства хороших реализаций занимают практически одинаковое количество памяти. Цитата Руками вы ничего не будите делать ![]() Цитата Я сравнивал их сугубо для того, чтобы выяснить какой из них лучше подходит для ToyLisp-а. Вариант со стеком оказался проще и он более гибкий, кстати, на реализацию escape-continuations у меня ушло всего 15 минут ![]() Цитата Попробуйте проверить на других реализациях кроме Racket. Цитата Во время вычисления функции наподобие факториала. ЦитатаА Racket что? |
|
Kergan
300 сообщений |
#4623 2011-08-07 09:39 GMT+3 часа(ов) |
Цитата Он не "может быть" сайд-эффектом, он _всегда_ сайд-эффект по определению сайд-эффекта. Любое ИО - всегда сайд-эффект. И при чем тут терминал? Цитата Ну это и подразумевается под копированием стека. Цитата Замыкания _ не надо_ создавать, замыкание - это просто пара из указателя на функцию и указателя на фрейм стека. Фрейм создается сразу, как только вы вызвали функцию. Всегда. Боьше ничего копировать и создавать не надо. Цитата Ну а копия стека - занимает очень много памяти, по сравнению с замыканием. Цитата При "ручной" реализации продолжений нет никаких сайд-эффектов. Цитата Так я еще раз спрашиваю - по каким критериям сравнивали? ![]() Цитата Теперь прикрутите треды с ffi и расскажите про гибкость еще раз ![]() Цитата Я ж повторюсь - это на любой реализации. которая копирует стек. Цитата А, ну практически нисколько, операции со стеком на фикснумах в сотни раз быстрее, чем аллокация бигнумов в хипе. Цитата Ну компилятор же. |
|
misha![]()
1275 сообщений |
#4624 2011-08-07 16:22 GMT+3 часа(ов) |
Цитата В вашем случае сайд-эффект невозможен. Цитата Замыкание - это объект. Где вы предполагаете хранить переменные унаследованные замыканием? Вам нужно еще одно дополнительное поле или поля. Цитата С "цепочкой" замыканий! Все они хранятся в памяти. И тут уж все зависит от реализации, поэтому не стоит описывать сферического коня в вакууме. Цитата "а если нужно в паре отдельных мест - можно напрямую руками переписать." - в какой же это паре отдельных мест? Допустим, мне нужен ретурн из замыкания. Цитата Легкость реализации, возможность оптимизации, производительность. Цитата Вы про green threads? Цитата Как вы проверяли? Ах, да вы же не проверяли ![]() Цитата Не спорю ![]() > (define (f n) Цитата И Chez Scheme тоже компилятор. И ToyLisp компилятор ![]() |
|
Kergan
300 сообщений |
#4632 2011-08-09 13:56 GMT+3 часа(ов) |
Цитата Если он невозможен - как я его сделал? еще раз - вывод сообщения на экран является сайд-эффектом по определению сайд-эффекта. я вывел сообщения на экран. Следовательно - сделал сайд-эффект. Цитата Так, ну то, что вы од сайд-эффектом что-то свое личное понимаете мы уже выяснили, так еще и определение "объекта" у вас нестандартное? Цитата Что это за переменные такие? Цитата Конечно, не нужно. Еще раз, кода вы вызываете функцию, то создается фрейм стека. Что такое замыкание? Это указатель на функцию + указатель на фрейм стека ф-и, в которой это замыкание было создано. Когда вы создаете замыкание, то никаких переменных не создается не копируется, они УЖЕ есть, как только вызвана функция. Цитата Да, но они в любом случае хранятся. То есть в не-cps форме в рекурсивной функции все те же переменные будут храниться на том же самом стеке и занимать ровно только же памяти. И cps-пребразование расхода памяти фактически не добавляет - добавляется только по 1 переменой на фрейм (указатель на замыкание). Цитата Ну делайте раз нужен, сайд-эффектов то все равно не будет. Цитата Ну легкость реализации и возможность оптимизации по тестам явно не определить, а вот производительность вы тестами не измерили. Цитата да Цитата вам если скажут, что 2+2=4, то вы будете это проверять? (выкладывать палочки или считать на пальцах, например) Цитата Угу. Но если неиспользуемых объектов нет (как в случае с фикснумами), и память в процессе не аллоцировалась, то гц и делать нечего ![]() Цитата Это бигнум, бигнумы аллоцируются на хипе. Фикснумы - не аллоцируются, соответственно и гц не требуют. Цитата а на сайте Chez Scheme написано, что Petit - интерпретатор. |
|