Предыдущая страница [1] [2] [3] [4] [5] > 6 <

Автор Сообщение

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4593   2011-08-01 14:43 GMT+3 часа(ов)      
Цитата
Цитата
Доказательства чего именно? Того, что в CL скомпилированный код не делится по фазам, а в Racket - делится? Ну, собственно, спецификация CL и Racket соответственно

Цитата
и прсотой примерчик:

И где тут сайд-эффекты? Я увидел лишь четкое разделение фаз по времени выполнения.
Цитата
Цитата
Это и называется cps-преобразование
Цитата
Ну а где реализация вашего call/cc? У вас какая-то странная мания сравнивать непонять что

В трех строчках кода разобраться не можете?
(setq $call/cc
(lambda(k t)
(t k (lambda(k1 v) (k v)))))
(setq $factorial
(lambda (cont a)
($zero? (lambda (b)
(if b
($call/cc cont
(lambda (k cont)
(cont k (begin
(setq fact/cont cont)
1))))
($- (lambda (c)
($factorial (lambda (d)
($* cont a d))
c))
a 1)))
a)))
> ($factorial halt 20)
2432902008176640000
> (fact/cont halt 1)
2432902008176640000
Цитата
Цитата
Зачем? ведь на самом деле это и есть передача аргументов, а никакое ни создание объекта.

Цитата
Если аругменты не передаете - не создается. если передаете - создается (помним, что создание environment = передача аргументов).

Кто создал ToyLisp, я или вы? Зачем вы неправильно комментируете?
Цитата
разработчик тут не при чем, proper tail-call optimisation - требование стандарта любой схемы. еще с самой первой - той самой, которая для SICP.
Только хорошие реализации следуют требованиям стандарта. Что в этом не понятно? Да и оптимизация хвостовых вызовов довольно примитивная задача.

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4594   2011-08-01 16:48 GMT+3 часа(ов)      
Цитата
И где тут сайд-эффекты?

Я там даже подписал, где сайдэффекты

Цитата
Я увидел лишь четкое разделение фаз по времени выполнения.

Ну да, которое в CL невозможно. О чем и речь.

Цитата
В трех строчках кода разобраться не можете?

Да нет, как реализуется call/cc на основе cps-преобразования я в курсе, вы мне реализацию _своего_ call/cc покажите, то есть того, которое используется в функции factorial, а не в функции $factorial. Кроме того, не ясно, какое отношение к скорости вызова продолжений/функций имеет ваш пример. Во-первых, продолжение в вашем примере вызывается лишь однажды (в обоих случаях), для сравнения надо вызвать его, ну, хотя бы 1000000 раз. Далее, поскольку вы используете умножение, в вашем примере 99% времени исполнения уходит на работу с бигнумами. Чтобы получить коректные результаты, нужно нечто вроде этого:

 
(define (f x) (add1 x))
(define cont #f)
(add1 (let/cc k (begin (set! cont k) 0)))
 

ну и далее вызываем 1000000+ раз f и cont. Сравниваем результаты.

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4595   2011-08-01 16:53 GMT+3 часа(ов)      
Цитата
Кто создал ToyLisp, я или вы?

прошу прощения, а при чем тут ваш ToyLisp? Мы говорили в общем о реализации продолжений, если _у вас_ в вашем ToyLisp функциональный вызов сделан _настолько_ медленно, что даже вызов продолжения работает быстрее - то это проблемы вашего ToyLisp. При человеческой реализации вызова ф-й (как во всех нормальных диалектах) сделать вызов продолжения быстрее вызова ф-и просто невозможно, потому что вызов продолжения включает в себя вызов ф-и.

Цитата
Только хорошие реализации следуют требованиям стандарта. Что в этом не понятно?

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

Цитата
Да и оптимизация хвостовых вызовов довольно примитивная задача.

ДА, но в той же жабке ее реализовать невозможно. с чего, собственно, и начался разговор.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4596   2011-08-01 18:04 GMT+3 часа(ов)      
Цитата
Я там даже подписал, где сайдэффекты

Это не сайд-эффекты!
Цитата
Ну да, которое в CL невозможно. О чем и речь.

Кому нужно тот реализует
Цитата
Да нет, как реализуется call/cc на основе cps-преобразования я в курсе

Не похоже А иначе б вы не писали: "У вас какая-то странная мания сравнивать непонять что".
Цитата
вы мне реализацию _своего_ call/cc покажите, то есть того, которое используется в функции factorial, а не в функции $factorial.

Это встроенная функция.
Цитата
Кроме того, не ясно, какое отношение к скорости вызова продолжений/функций имеет ваш пример.

Никакого Я не собирался сравнивать скорости вызовов. Читайте внимательно о чем я писал ранее.
Цитата
Во-первых, продолжение в вашем примере вызывается лишь однажды (в обоих случаях), для сравнения надо вызвать его, ну, хотя бы 1000000 раз. Далее, поскольку вы используете умножение, в вашем примере 99% времени исполнения уходит на работу с бигнумами. Чтобы получить коректные результаты, нужно нечто вроде этого:



(define (f x) (add1 x))

(define cont #f)

(add1 (let/cc k (begin (set! cont k) 0)))




ну и далее вызываем 1000000+ раз f и cont. Сравниваем результаты.
Ну и как же я это сделаю без вмешательства в исходники ToyLisp-а?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4597   2011-08-01 18:16 GMT+3 часа(ов)      
Цитата
прошу прощения, а при чем тут ваш ToyLisp? Мы говорили в общем о реализации продолжений

А что уже и пример привести нельзя?
Цитата
если _у вас_ в вашем ToyLisp функциональный вызов сделан _настолько_ медленно, что даже вызов продолжения работает быстрее - то это проблемы вашего ToyLisp.

С чего вы взяли, что функциональный вызов обязан быть быстрее вызова продолжения? На самом деле если он у меня медленнее, то скорее на 0,05%.
Цитата
При человеческой реализации вызова ф-й (как во всех нормальных диалектах) сделать вызов продолжения быстрее вызова ф-и просто невозможно, потому что вызов продолжения включает в себя вызов ф-и.

"потому что вызов продолжения включает в себя вызов ф-и" - вот тут вы ошибаетесь.
Цитата

требованиям стандарта следуют _все_ реализации, если же какая-то в чем-то не следует - то это уже не реализация схемы, это реализация другого языка. Тем более если речь идет о такой вещи, как оптимизация хвостовых вызовов (это одна из ключевых особенностей схемы).
Это вы им расскажите
Цитата

ДА, но в той же жабке ее реализовать невозможно. с чего, собственно, и начался разговор.

Нет так нет

отредактировал(а) misha: 2011-08-01 18:23 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4598   2011-08-01 21:28 GMT+3 часа(ов)      
Цитата
Это не сайд-эффекты!

Конечно же, это сайд-эффекты. Любой вызов ио-функций - сайд-эффект.

Цитата
Кому нужно тот реализует

Это нужно, очень нужно, хотя бы ради раздельной компиляции (и для возможности писать корректные макросы, конечно же) - вот нету в CL раздельной компиляции и приходится велосипедить всякие tree шейкеры, да и те в проприетарных реализациях, но в CL это сделать нельзя в принципе - придется менять модель вычислений CL. То есть это уже будет не CL. А, ну еще можно всегда написать на CL racket vm

Цитата
Не похоже

Наверное, я лучше знаю, что имел в виду?

Цитата
А иначе б вы не писали: "У вас какая-то странная мания сравнивать непонять что".

это относилось как раз к call/cc из factorial - чего толку сравнивать, если не известно, как она работает?

Цитата
Это встроенная функция.

ну значит реализацию этой встрокенной функции. И реализацию замыканий

Цитата
Никакого Я не собирался сравнивать скорости вызовов.

Ну вы показали, что у вас функции-замыкания вызываются медленнее, чем обычные функции - в чем нету ничего странного. Однако, на практике рекурсия с 10000 вложенностью бывает не часто.

Цитата
Ну и как же я это сделаю без вмешательства в исходники ToyLisp-а?

Yу вы замените по крайней мере (* n ...) на (+ 1 ...)

Цитата
С чего вы взяли, что функциональный вызов обязан быть быстрее вызова продолжения?
ну, обычно потому, что стараются уменьшить оверхед на функциональный вызов.

Цитата
"потому что вызов продолжения включает в себя вызов ф-и" - вот тут вы ошибаетесь.

вызов функции - кладем аргументы на стек, делаем джамп
вызов продолжения - кладем аргументы на стек, делаем джамп. но, конечно, в ToyLisp все можэет быть иначе
Тогда перефразируем "вызов продолжения не может быть быстрее номарльно реализованного функционального вызова".

Цитата
Это вы им расскажите
кому им? вы знаете реализацию схемы без оптимизации хвостовых вызовов?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4599   2011-08-02 01:02 GMT+3 часа(ов)      
Цитата
Конечно же, это сайд-эффекты. Любой вызов ио-функций - сайд-эффект.

Каждая фаза имеет свое пространство имен, которое совмещается с таким же во время экспанда.
Цитата
Это нужно, очень нужно, хотя бы ради раздельной компиляции (и для возможности писать корректные макросы, конечно же) - вот нету в CL раздельной компиляции и приходится велосипедить всякие tree шейкеры, да и те в проприетарных реализациях, но в CL это сделать нельзя в принципе - придется менять модель вычислений CL. То есть это уже будет не CL. А, ну еще можно всегда написать на CL racket vm

В принципе, согласен
Цитата
Наверное, я лучше знаю, что имел в виду?

Шуток не понимаете
Цитата
это относилось как раз к call/cc из factorial - чего толку сравнивать, если не известно, как она работает?

Создает продолжение и передает его функции в качестве аргумента.
Цитата
Ну вы показали, что у вас функции-замыкания вызываются медленнее, чем обычные функции - в чем нету ничего странного. Однако, на практике рекурсия с 10000 вложенностью бывает не часто.

Я всего лишь хотел показать, что классическое cps-преобразование не самое эффективное решение. Есть и другие подходы (варианты) continuation-passing.
Цитата
ну значит реализацию этой встрокенной функции. И реализацию замыканий

Я сегодня сравнил скорости фрагментов кода отвечающих за вызовы. Ну в общем как я и предсказывал, т.е.они практически не различаются.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4600   2011-08-02 02:04 GMT+3 часа(ов)      
Цитата
Yу вы замените по крайней мере (* n ...) на (+ 1 ...)

Где заменить? Не думаю, что это что-нибудь даст, потому что продолжение ...
Цитата
ну, обычно потому, что стараются уменьшить оверхед на функциональный вызов.

Если бы я реализовал компиляцию в native код, то продолжения были бы реализованы как класс (с публичным методом).
Цитата
вызов функции - кладем аргументы на стек, делаем джамп

Но пред этим для не хвостового вызова сохраняем состояние
Цитата
вызов продолжения - кладем аргументы на стек, делаем джамп.

У меня вместо джампа вызывается встроенная функция
Цитата
Тогда перефразируем "вызов продолжения не может быть быстрее номарльно реализованного функционального вызова".

У меня интерпретатор байткода, а вы говорите о реализациях компилирующих в native код. Т.к. там lambda, continuation можно считать как производные классы от какого-нибудь базового класса, например, procedure.
Цитата
кому им? вы знаете реализацию схемы без оптимизации хвостовых вызовов?

Студенческих поделок навалом.

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4601   2011-08-02 07:52 GMT+3 часа(ов)      
Цитата
Каждая фаза имеет свое пространство имен, которое совмещается с таким же во время экспанда.

К чему вы это сказали? Сайд-эффекты от этого перестают быть сайд-эффектами?

Цитата
Создает продолжение и передает его функции в качестве аргумента.

ну так ка именно? очевидно, если мы хотим нормально сравнить А и В, то надо знаьт, чот это за А и В.

Цитата
Я всего лишь хотел показать, что классическое cps-преобразование не самое эффективное решение.

Но не показали
и не покажите, потому что не взможно. Вызов продолжения при cps-преобразовании - это просо вызов замыкания, а вызов продолжения всегда медленее вызова замыкания. Если, конечно, в вашем диалекте вызов замыкания изначально не реализован сверхнеэфективно.

Цитата
Где заменить?
в factorial и $factorial

Цитата
Не думаю, что это что-нибудь даст потому что продолжение ...

А при чем тут вообще продолжения? У вас там нигде скорость работы продолжений не анализируется - у вас там в одном случае вызывается цепочка замыканий, в другом случае - цепочка обычный функций. Соответственно, скорость таких вызовов вы и сравниваете... сравнивали _бы_ если бы у вас была дешевая функция, а не умножение бигнумов.

Цитата
Но пред этим для не хвостового вызова сохраняем состояние

Не надо ничего сохранять. Зачем? А вот с хвостовыми вызовами, наоборот, ситуация гораздо веселее - не при любом хвостовом вызове оптимизацию можно применить, так что следует следиь за этим фактом.

Цитата
У меня интерпретатор байткода, а вы говорите о реализациях компилирующих в native код.

ну то есть с моим последним утверждением вы спорить не станете? )

Цитата
Студенческих поделок навалом.

ну и кому они нужны? кто-то всерьез рассматривает такие студенческие поделки?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4602   2011-08-02 16:49 GMT+3 часа(ов)      
Цитата
К чему вы это сказали? Сайд-эффекты от этого перестают быть сайд-эффектами?

Фазы были созданы для того, чтобы избавить вас от сайд-эффектов.
Цитата
ну так ка именно? очевидно, если мы хотим нормально сравнить А и В, то надо знаьт, чот это за А и В.

Передает как и в $call/cc, т.е.
> (disassemble (lambda() (call/cc (lambda(r) (r 1)))))
(#<procedure id:12289376>
(CHECK-ZERO-ARGUMENTS)
(LOAD-CLOSURE #(#<procedure LOAD-ARGUMENTS> #(0 ) #<procedure PUSH> 1 #
<procedure LOAD-LOCAL-VARIABLE> 0 #<procedure CALL1-TAIL> #<procedure RET>))
(LOAD-GLOBAL-VARIABLE 85) ; наш call/cc
(CALL1-TAIL)
(RET))

А как создает я уже описывал ранее.
Цитата
Но не показали
и не покажите, потому что не взможно.

Статей на эту тему навалом.
Цитата
Вызов продолжения при cps-преобразовании - это просо вызов замыкания, а вызов продолжения всегда медленее вызова замыкания.

По вашему вызов замыкания медленнее вызова замыкания?
Цитата
Если, конечно, в вашем диалекте вызов замыкания изначально не реализован сверхнеэфективно.

Вы вообще читаете мои посты? У меня скорости вызовов замыкания и продолжения практически равны.
Цитата
в factorial и $factorial

Это ничего не даст.
Цитата
А при чем тут вообще продолжения? У вас там нигде скорость работы продолжений не анализируется - у вас там в одном случае вызывается цепочка замыканий, в другом случае - цепочка обычный функций. Соответственно, скорость таких вызовов вы и сравниваете... сравнивали _бы_ если бы у вас была дешевая функция, а не умножение бигнумов.

Я сравниваю методы реализации continuation-passing.
Цитата
Не надо ничего сохранять. Зачем?

Джамп - это безусловный переход. Как возврат осуществлять будете для не хвостового вызова.
Цитата
А вот с хвостовыми вызовами, наоборот, ситуация гораздо веселее - не при любом хвостовом вызове оптимизацию можно применить, так что следует следиь за этим фактом.


Все зависит от выбранной модели реализации лиспа.
Цитата

ну то есть с моим последним утверждением вы спорить не станете? )

А вы не сравнивайте козу с бараном Нельзя сравнивать подходы применяемые в компилирующем интерпретаторе и интерпретаторе байткода.
Цитата
ну и кому они нужны? кто-то всерьез рассматривает такие студенческие поделки?

Ну MzScheme(Racket) тоже начинался как студенческая поделка

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4603   2011-08-02 21:54 GMT+3 часа(ов)      
Цитата
Фазы были созданы для того, чтобы избавить вас от сайд-эффектов.

фазы были созданы для того, чтобы дать возможность контролировать сайд-эффекты. Избавить от сайд-эффектов нельзя - вот я написал (display "phase") и вот он сайд-эффект. Как вы собираетесь от него "избавить"?

Цитата
Статей на эту тему навалом.

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

Цитата
По вашему вызов замыкания медленнее вызова замыкания?

Просто обычно продолжение в вызову не сводится - приходится при вызове продолжения проводить еще некоторую доп. работу.

Цитата
Вы вообще читаете мои посты? У меня скорости вызовов замыкания и продолжения практически равны.

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

Цитата
Это ничего не даст.

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

Цитата
Я сравниваю методы реализации continuation-passing.

В функции factorial нету никакого continuation-passing, не врите.

Цитата
Джамп - это безусловный переход. Как возврат осуществлять будете для не хвостового вызова.

Вызов функции - это и есть безусловный переход. Возврат из функции - еще один безусловный переход. Вы не знали?

Цитата
Ну MzScheme(Racket) тоже начинался как студенческая поделка

У Маттиаса к моменту создания PLT уже было несколько публикаций, как-то не тянет на "студенческую поделку"

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4604   2011-08-02 22:45 GMT+3 часа(ов)      
Цитата
Избавить от сайд-эффектов нельзя - вот я написал (display "phase") и вот он сайд-эффект. Как вы собираетесь от него "избавить"?

Это не сайд-эффект! Читайте мануалы.
Цитата
У продолжений, реализованных через cps, есть свои недостатки, да. Но по скорости вызова такая реализация наиболее эффективна. Альтернативные реализации обычно медленнее раз эдак в сотню-тысячу (наиболее быстрые из альтернативных, ессно, для медленных все еще печальнее).

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

Вы путаете скорость вызова с восстановлением состояния. У меня остаточные вычисления нигде не сохраняются, но у меня есть стек данных, стек возвратов и указатель на код функции, которые я копирую во время создания продолжения, и восстанавливаю их во время вызова продолжения. Это гораздо эффективнее, чем тянуть за собой хвост из сотен замыканий.
Цитата
Ну я и говорю - у вас вызов замыкания сделан настолько неэффективно, что вызов продолжения равен ему по скорости.

Я не понимаю о чем идет речь. Что вы подразумеваете под вызовом замыкания? Скорость операции CALL или скорость вычисления функции.
Цитата
При эффективной реализации замыканий продолжения будут вызываться медленнее (сто-тысяча раз, как я выше указал)

Какой дурак вам это сказал?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4605   2011-08-02 22:59 GMT+3 часа(ов)      
Цитата
Конечно даст, если вы сделаете подобную замену, то тогда ваш тест будет измерять то, что надо (скорость работы ззамыканий). На данный же момент он измеряет скорость работы бигнумов.

Зачем вам это нужно? У меня создание продолжения требует определенного времени (зависит от величины стеков), а его вызов (восстановление состояния) происходит за линейное время (Вы хотите его измерить?).
Цитата
В функции factorial нету никакого continuation-passing, не врите.

Вы вообще читаете о чем я пишу?
Цитата
Вызов функции - это и есть безусловный переход. Возврат из функции - еще один безусловный переход. Вы не знали?

Как происходит операция CALL?
Цитата
У Маттиаса к моменту создания PLT уже было несколько публикаций, как-то не тянет на "студенческую поделку"

А вы их читали?

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4606   2011-08-03 00:56 GMT+3 часа(ов)      
Цитата
Это не сайд-эффект! Читайте мануалы.

Я вижу, что ваше определение понятия "сайд-эффекта" отличается от общепринятого. вы уж скажите, что под ним подразумеваете.

Цитата
Читайте оригинальные статьи, пытайтесь реализовать описанные в них модели.

Это вы к чему?

Цитата
Вы путаете скорость вызова с восстановлением состояния.

Эьто вы путаете. я говорю именно о скорости вызова - который может как включать так и не включать восстановление состояния, в зависимости от реализации.

Цитата
но у меня есть стек данных, стек возвратов и указатель на код функции, которые я копирую во время создания продолжения, и восстанавливаю их во время вызова продолжения. Это гораздо эффективнее, чем тянуть за собой хвост из сотен замыканий.
Это выгоднее только в одном случае - если вызов замыкания реализован неэффективно. Если же вызов замыкания пренебрежимо мало отличается по скорости от вызова функции не-замыкания, то никакого преимущества перед "хвостом из замыканий" ваша модель не дает. Зато имеет кучу недостатков, вот например вы пишете: "но у меня есть стек данных, стек возвратов и указатель на код функции, которые я копирую во время создания продолжения", а во время вызова замыкания ничего этого копировать не надо.

Цитата
Я не понимаю о чем идет речь. Что вы подразумеваете под вызовом замыкания?

Под вызовом я понимаю вызов - то есть, конечно же, операцию call. Скорость вычисления функции и та всегда одинакова - хоть внутри замыкания ее вычисляй, хоть как.

Цитата
Какой дурак вам это сказал?

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

Цитата
Зачем вам это нужно?

Мне? Незачем. Это вам нужно. Вы хотели померить скорость работы замыканий/продолжений, а зачем-то меряете скорость работы арифметических операций над бигнумами. Я на это и указал.

Цитата
а его вызов (восстановление состояния) происходит за линейное время

За линейное от чего?

Цитата
Вы вообще читаете о чем я пишу?

Конечно читаю, другое дело, что вы очень часто отвечаете невпопад и скачете с одной темы на другую, вот ка сейчас. Вы писали:
"Я сравниваю методы реализации continuation-passing."
Я и указал на то, что это не правда - у вас там нету никакого continuation-passing. А как вы можете сравнивать то, чего нет?

Цитата
Как происходит операция CALL?

кладем на стек адрес возврата и делаем джамп на тело функции

Цитата
А вы их читали?

Нет, настолько старые публикации я не читал. Но можно найти и посмотреть, что там, при желании.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4608   2011-08-03 15:14 GMT+3 часа(ов)      
Цитата
Я вижу, что ваше определение понятия "сайд-эффекта" отличается от общепринятого. вы уж скажите, что под ним подразумеваете.

В вашем примере я не увидел ни одного сайд-эффекта - все в соответствии с документацией.
Цитата
Это вы к чему?

Мне ваши голословные заявления уже надоели.
Цитата
Эьто вы путаете. я говорю именно о скорости вызова - который может как включать так и не включать восстановление состояния, в зависимости от реализации.

Ну так пишете понятнее.
Цитата
Это выгоднее только в одном случае - если вызов замыкания реализован неэффективно.

Это слишком простая операция Вы лучше подсчитайте накладные расходы вызванные cps.
Цитата
Если же вызов замыкания пренебрежимо мало отличается по скорости от вызова функции не-замыкания, то никакого преимущества перед "хвостом из замыканий" ваша модель не дает.

Как раз у меня "вызов замыкания пренебрежимо мало отличается по скорости от вызова функции не-замыкания".
Цитата
а во время вызова замыкания ничего этого копировать не надо.

Не надо, потому что уже все "скопировано".
Цитата
Никто не говорил, это имперический результат. Можете для интереса сами взять и потестировать производительность продолжений в наиболее известных реализациях.

Наиболее известные реализации используют сложные стеки, так что там и захват, и вызов происходят очень быстро. Конечно, медленнее чем вызов функции, но не в сотни раз.
Цитата
Вы, видимо, просто не совсем понимаете, что продолжения не существуют сами по себе, в отрыве от рантайма, и по-этому на практике при вызове продолжения необходимы очень большие накладные расходы в сравнении с обычным функциональным вызовом. Продолжения (в отличии от функции) нельзя реализовать простым джампом - вам в любом случае придется проводить весьма нетривиальные преобразования над стеком, да еще и аллоцировать память в хипе, если вы хотите, чтобы все это работало. Именно по-этому реализация продолжений на основе cps-преобразования считается самой эффективной, причем настолько эффективной, что никакие другие реализации не подходят даже близко.


"аллоцировать память в хипе" - если и приходится, то это в крайнем случае. Копипаст сегментов происходит очень быстро.
Тогда почему до сих пор используются стеки? В хороших реализациях вызов продолжения обычно довольно дешевая операция, т.к. используется segmented stack model.
Цитата
Вы хотели померить скорость работы замыканий/продолжений, а зачем-то меряете скорость работы арифметических операций над бигнумами. Я на это и указал.

Я измерял время работы двух подходов на примере вычисления факториала.
Цитата
За линейное от чего?

Пардон, за константное.
Цитата
Я и указал на то, что это не правда - у вас там нету никакого continuation-passing. А как вы можете сравнивать то, чего нет?


Там нету cps, но создание продолжения присутствует.
Цитата

кладем на стек адрес возврата и делаем джамп на тело функции


Так что это не только джамп.

отредактировал(а) misha: 2011-08-03 15:26 GMT+3 часа(ов)

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4609   2011-08-04 00:08 GMT+3 часа(ов)      
Цитата
Можете для интереса сами взять и потестировать производительность продолжений в наиболее известных реализациях.

Приведите мне ваши тесты, и главное прокомментируйте во сколько раз хуже. Не надо мне говорить что-то типа "смотрите и делайте выводы сами".

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4611   2011-08-04 10:12 GMT+3 часа(ов)      
Цитата
В вашем примере я не увидел ни одного сайд-эффекта - все в соответствии с документацией.

Ну да, в соответствии с документацией. Я где-то говорил иное? Еще раз - напишите, что вы понимаете под термином "сайд-эффект". явно не то, что понимают все остальные, но мне интересно - что?

Цитата
Мне ваши голословные заявления уже надоели.

Укажите хоть одно. Но это не важно, еще раз - к чему вы сказали-то процитированную фразу?

Цитата
Ну так пишете понятнее.

Я сразу четко и понятно написал - "скорость вызова". не моя вина, что вы все время прыгаете с одного на другое и трактуете все термины по-своему.

Цитата
Это слишком простая операция

Ну вы же умудрились реализовать в своем диалекте эту простую операцию та неэффективно, что она не быстрее вызова продолжения

Цитата
Вы лучше подсчитайте накладные расходы вызванные cps.

Вы имеете в виду оверхед самого преобразования? Не так велик.

Цитата
Не надо, потому что уже все "скопировано".

Вот именно.

Цитата
Наиболее известные реализации используют сложные стеки, так что там и захват, и вызов происходят очень быстро.
Захват - это вообще охренительно долгая операция, потому что при захвате надо скопировать весь стек в хип. Именно по этой причине, кстати, нету способа реализовать в scheme аналог return'a - сделать то его на продолжениях можно, но поскольку при каждом функциональном вызове надо делать захват продолжения, производительность падает на порядки. При чем это даже при использовании escape continuations, которые в среднем в десятки раз быстрее обычных. Вообще, вы забываете одну простую вещь - с эффективной реализацией продолжений хорошо в теории, но на практике, когда эти продолжения должны работать с тредами и ffi, начинаются проблемы.

Цитата
Тогда почему до сих пор используются стеки?

Вы про какое именно использование?

Цитата
Я измерял время работы двух подходов на примере вычисления факториала.

А зачем сравнивать время работы операций на бигнумах с таким же временем работы таких же операций на таких же бигнумах?

Цитата
Так что это не только джамп.

Ок, это push и jump. Велика разница?

Цитата
Не надо мне говорить что-то типа "смотрите и делайте выводы сами".

Именно так и скажу.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4612   2011-08-04 13:30 GMT+3 часа(ов)      
Цитата
ще раз - напишите, что вы понимаете под термином "сайд-эффект". явно не то, что понимают все остальные, но мне интересно - что?

Сайд-эффект - побочный эффект.
Цитата
Укажите хоть одно. Но это не важно, еще раз - к чему вы сказали-то процитированную фразу?


Без доказательства это чушь: "Именно по-этому реализация продолжений на основе cps-преобразования считается самой эффективной, причем настолько эффективной, что никакие другие реализации не подходят даже близко."
Цитата
Цитата
Ну вы же умудрились реализовать в своем диалекте эту простую операцию та неэффективно, что она не быстрее вызова продолжения
Цитата

Вы имеете в виду оверхед самого преобразования? Не так велик.



Вы не понимаете почему у меня cps хуже копирования стека, объяснить?
Цитата
Захват - это вообще охренительно долгая операция, потому что при захвате надо скопировать весь стек в хип.

Это у меня копируется весь стек, но все равно это быстрее использования замыканий. Кстати, можете запустить мои факториалы в Chez Scheme (у Racket gc шалит, но в общем результаты похожи на Chez Scheme) и представить свои результаты. По моим результатам cps ничем не лучше встроенного механизма.
Цитата
Вообще, вы забываете одну простую вещь - с эффективной реализацией продолжений хорошо в теории, но на практике, когда эти продолжения должны работать с тредами и ffi, начинаются проблемы.


Это уже проблема разработчиков.
Цитата

Вы про какое именно использование?

Использование для создания продолжений.
Цитата
А зачем сравнивать время работы операций на бигнумах с таким же временем работы таких же операций на таких же бигнумах?

Я вам представил средние результаты.
Цитата
Ок, это push и jump. Велика разница?


Конечно
Цитата
Именно так и скажу.

Не можете справиться с такой примитивной задачей?

отредактировал(а) misha: 2011-08-04 13:42 GMT+3 часа(ов)

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4613   2011-08-04 16:13 GMT+3 часа(ов)      
Цитата
Вы не понимаете почему у меня cps хуже копирования стека, объяснить?

Сегодня наконец таки закончил переписывание ToyLisp. Я исправил старые ошибки, избавился от стека возвратов, а также сменил порядок вычисления аргументов при вызове функции на стандартное (LR).
> (disassemble (lambda() (+ 1 2 (- 3 4) 5)))
(#<procedure id:30015890>
(CHECK-ZERO-ARGUMENTS)
(LOAD-GLOBAL-VARIABLE 1)
(PUSH 1)
(PUSH 2)
(LOAD-GLOBAL-VARIABLE 2)
(PUSH 3)
(PUSH 4)
(CALL2)
(PUSH 5)
(CALL4-TAIL)
(RET))

Решил повторить тест.
 
> (factorial 20)
2432902008176640000
> (fact/cont 1)
2432902008176640000
> ($factorial halt 20)
2432902008176640000
> ($fact/cont 1)
2432902008176640000
> (begin (factorial 10000) #f)
#f
На вычисление затрачено: 593,75 мс.
> (begin (fact/cont 1) #f)
#f
На вычисление затрачено: 562,5 мс.
> (begin ($factorial halt 10000) #f)
#f
На вычисление затрачено: 671,875 мс.
> (begin ($fact/cont 1) #f)
#f
На вычисление затрачено: 609,375 мс.

Это средние значения. Если сменить умножение на сложение, то gc не даст получить нормальные результаты.

отредактировал(а) misha: 2011-08-04 16:30 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4614   2011-08-04 19:51 GMT+3 часа(ов)      
Цитата
Сайд-эффект - побочный эффект.

Ну тогда чего же вы говорите, что побочных эффектов нет? Там в примере вызывалась функция displayln, побочный эффект которой - вывод строки.

Цитата
Без доказательства это чушь:

Я вас уже это доказал. При вызове продолжения надо сделать _как минимум_ столько же работы, как и при вызове замыкания. При использовании cps-преобразования этот минимум достигается, при использовании другой реализации возникает ряд накладных расходов,, которые в случае cps-преобразования просто отсутствуют как класс.

Цитата
Вы не понимаете почему у меня cps хуже копирования стека, объяснить?

А он хуже? Вы этого пока не показали.

Цитата
Это у меня копируется весь стек

Стек копируется практически во всех реализациях. Можно только тем или иным способ оптимизировать этот процесс, но от аллокаций на хипе вы никуда не уйдете в любом случае.

Цитата
По моим результатам cps ничем не лучше встроенного механизма.

Но приведенные вами тесты не имеют никакого отношения к производительности продолжений и cps-преобразования. Что вы хотите доказать на основе этих тестов? Я не могу понять.

Цитата
Это уже проблема разработчиков.

Принадлежность проблем их наличия не отменяет.

Цитата
Использование для создания продолжений.

А почему стек для этого не должны использовать?

Цитата
Я вам представил средние результаты.

Вы невнимательно читаете вопрос. Я повторюсь:
"А зачем сравнивать время работы операций на бигнумах с таким же временем работы таких же операций на таких же бигнумах?"
или. Переиначив - ЗАЧЕМ вообще вы проводили эти тесты? Что вы ими хотели показать?

Цитата
Это средние значения. Если сменить умножение на сложение, то gc не даст получить нормальные результаты.

Это уже становится смешно. итак, в ваших тестах во время вополнения происходит три вещи:
1. арифметические операции над бигнумами
2. гц
3. полезная нагрузка (вызов продолжений и т.п.)
я вам указал, что вы (по невнимательности, видимо) не учли, что операции над бигнумами в данном случае занимают 99% времени вашего теста. т.о. производительность полезной нагрузки вы этими тестами не измерите. И что же? Оказывается у вас даже без учета бигнумов гц жрет столько процессорного времени, что нормальных результатов получить нельзя, и что вы сделали, чтобы исключить этот фактор7 просто добавили длинные бесполезные операции, которые будут весомы на фоне гц! Ну вы с такой же радостью могли реализовать свой факториал так:
 
(define (fact n)
(sleep 10000)
(call/cc (lambda (cont) 0)))
 

и получили бы в точности те же результаты.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4615   2011-08-04 21:49 GMT+3 часа(ов)      
Цитата
Там в примере вызывалась функция displayln, побочный эффект которой - вывод строки.
Я не думаю, что принт стоит относить к сайд-эффектам.
Цитата
При вызове продолжения надо сделать _как минимум_ столько же работы, как и при вызове замыкания. При использовании cps-преобразования этот минимум достигается, при использовании другой реализации возникает ряд накладных расходов,, которые в случае cps-преобразования просто отсутствуют как класс.

В cps продолжения создаются всегда, а при их вызове приходится осуществлять цепочку хвостовых вызовов. Во время хвостового вызова приходится удалять точку возврата.
При использовании стека продолжение создается когда это необходимо. При вызове приходится копировать массив, но эта операция происходит довольно быстро. Поэтому для меня прямое взаимодействие со стеком предпочтительней.
Цитата
А он хуже? Вы этого пока не показали.

Он не хуже, по скорости эти два подхода практически эквивалентны. Но все таки стеки чуть быстрее (на 2%-3% в зависимости от реализации), да и не приходится постоянно создавать дополнительные замыкания.
Цитата
Стек копируется практически во всех реализациях. Можно только тем или иным способ оптимизировать этот процесс, но от аллокаций на хипе вы никуда не уйдете в любом случае.

Вы имеете в виду, что требуется скопировать фреймы? Ну так старые удалятся.
Цитата
Но приведенные вами тесты не имеют никакого отношения к производительности продолжений и cps-преобразования. Что вы хотите доказать на основе этих тестов? Я не могу понять.

Просто сравнил два подхода, что тут не понятного?
Цитата
А почему стек для этого не должны использовать?

Вы же писали, что cps лучше

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4616   2011-08-04 22:42 GMT+3 часа(ов)      
Цитата
Оказывается у вас даже без учета бигнумов гц жрет столько процессорного времени, что нормальных результатов получить нельзя, и что вы сделали, чтобы исключить этот фактор7 просто добавили длинные бесполезные операции, которые будут весомы на фоне гц!

Попробуйте произвести измерения на Racket, там gc подключается еще чаще, чем у меня. Но в этом нет ничего необычного. Как вы предлагаете произвести измерения? Ведь даже у меня эти два подхода практически эквивалентны по скорости, если учитывать не средние, а минимальные значения, полученные в результате теста.

отредактировал(а) misha: 2011-08-05 00:26 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4617   2011-08-05 12:21 GMT+3 часа(ов)      
Цитата
Я не думаю, что принт стоит относить к сайд-эффектам.

Что значит "стоит" или "не стоит"? по факту любой ио-эффект является побочным, это не вопрос личных пристрастий

Цитата
Во время хвостового вызова приходится удалять точку возврата.

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

Цитата
При вызове приходится копировать массив, но эта операция происходит довольно быстро.

Наоборот - довольно медленно в сравнении с обычным вызовом (на порядки медленнее). Вообще, тут два разных аспекта - при cps-преобразовании вызов продолжения очень быстр (в сотни раз быстрее, чем при других реализациях), но исполнение продолжения будет медленнее, т.к. вместо обычного выполнения вызывается цепочка замыканий. Т.о. если мы вызываем множество "маленьких" продолжений (и важна скорость вызова) предпочтительнее cps-вариант. Если же вызываются "большие" продолжения и редко - предпочтительнее вариант со стеком. Есть и еще один аспект - оверхед по памяти. У стековых продолжений он реально огромен, вам при аллокации нескольких тысяч продолжений и то может выжрать весь хип и уронить гц. При cps-реализации у нас продолжение представляется одним единственным фреймом стека, по-этому даже миллион продолжений вполне можно будет переварить. Короче, оптимальным вариантом являлась бы возможность выбирать нужную реализацию продолжений в зависимости от того, какова наша задача. Что в сущности, стековый вариант и делает - для cps-продолжений поддержка рантайма не нужна, и их, если надо, всегда можно сделать руками.

Цитата
Он не хуже, по скорости эти два подхода практически эквивалентны. Но все таки стеки чуть быстрее (на 2%-3% в зависимости от реализации)

Чуть быстрее _что именно_? У вас там в тестах создание продолжение и его вызов - это пара миллисекунд максимум, остальное время у вас бигнумы умножаются.

Цитата
Вы же писали, что cps лучше

Я никогда не писал, что он лучше, я писал, что операции создания/вызова продолжений в cps-реализации на порядок быстрее.

Цитата
Ведь даже у меня эти два подхода практически эквивалентны по скорости

Правильно! Ведь у вас почти все время работы - это перемножение бигнумов, которое и там и там работает с одинаковой скоростью
И gc, кстати, подключается именно из-за бигнумов - если бы операции не выходили за пределы фикснумов, то гц бы практически не работал. Вот скорость вызова можно померять, например, как-то так:
 
#lang racket
 
(define k #f)
 
(define (test n)
(call/cc (lambda (cont)
(set! k cont)))
(when (> n 0)
(set! n (sub1 n))
(k)))
 
(define (test2 n)
(set! k #f)
(let loop ()
(when (> n 0)
(set! n (sub1 n))
(loop))))
 

результаты:
 
Добро пожаловать в DrRacket, версия 5.1.2.3--2011-07-16(e4e1792/a) [3m].
Язык: racket [выбранный].
> (time (test 100000))
cpu time: 187 real time: 187 gc time: 0
> (time (test 100000))
cpu time: 188 real time: 203 gc time: 0
> (time (test 100000))
cpu time: 157 real time: 183 gc time: 0
> (time (test2 100000))
cpu time: 15 real time: 2 gc time: 0
> (time (test2 100000))
cpu time: 0 real time: 0 gc time: 0
> (time (test2 10000000))
cpu time: 78 real time: 75 gc time: 0
> (time (test2 10000000))
cpu time: 47 real time: 90 gc time: 0
> (time (test2 100000000))
cpu time: 875 real time: 918 gc time: 109
> (time (test2 100000000))
cpu time: 704 real time: 750 gc time: 0
 

вот скорость создания продолжения:
 
(define (create n)
(for ([i (in-range n)])
(call/cc (lambda (cont) 0))))
 

результат:
 
Добро пожаловать в DrRacket, версия 5.1.2.3--2011-07-16(e4e1792/a) [3m].
Язык: racket [выбранный].
> (time (create 10000))
cpu time: 32 real time: 47 gc time: 0
> (time (create 10000))
cpu time: 47 real time: 50 gc time: 0
> (time (create 100000))
cpu time: 750 real time: 804 gc time: 266
> (time (create 100000))
cpu time: 750 real time: 771 gc time: 234
>
 

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4618   2011-08-05 12:25 GMT+3 часа(ов)      
вот еще escape continuations для сравнения:
 
(define (escape n)
(for ([i (in-range n)])
(call/ec (lambda (cont) 0))))
 
(define (f n)
(for ([i (in-range n)])
(call/ec (lambda (cont) (cont)))))
 

результат:
 
Добро пожаловать в DrRacket, версия 5.1.2.3--2011-07-16(e4e1792/a) [3m].
Язык: racket [выбранный].
> (time (escape 100000))
cpu time: 62 real time: 63 gc time: 0
> (time (escape 1000000))
cpu time: 782 real time: 797 gc time: 78
> (time (escape 1000000))
cpu time: 766 real time: 828 gc time: 94
> (time (f 10000))
cpu time: 0 real time: 11 gc time: 0
> (time (f 100000))
cpu time: 109 real time: 98 gc time: 0
> (time (f 1000000))
cpu time: 1016 real time: 1076 gc time: 78
> (time (f 1000000))
cpu time: 1000 real time: 1124 gc time: 78
 

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4620   2011-08-05 13:50 GMT+3 часа(ов)      
Цитата
Что значит "стоит" или "не стоит"? по факту любой ио-эффект является побочным, это не вопрос личных пристрастий

По какому факту?
Цитата
Во время хвостового вызова точка возврата просто _не создается_. Соответственно, и удалять ее не надо

В теории У меня тоже не создается, но подтирать стек приходится.
Цитата
Наоборот - довольно медленно в сравнении с обычным вызовом (на порядки медленнее).

Да кто бы спорил
Цитата
Вообще, тут два разных аспекта - при cps-преобразовании вызов продолжения очень быстр (в сотни раз быстрее, чем при других реализациях), но исполнение продолжения будет медленнее, т.к. вместо обычного выполнения вызывается цепочка замыканий. Т.о. если мы вызываем множество "маленьких" продолжений (и важна скорость вызова) предпочтительнее cps-вариант. Если же вызываются "большие" продолжения и редко - предпочтительнее вариант со стеком.

Зависит от реализации. Можете в этом убедиться.
Цитата
Есть и еще один аспект - оверхед по памяти. У стековых продолжений он реально огромен, вам при аллокации нескольких тысяч продолжений и то может выжрать весь хип и уронить гц. При cps-реализации у нас продолжение представляется одним единственным фреймом стека, по-этому даже миллион продолжений вполне можно будет переварить.

При cps-реализации продолжения хранятся в замыкании, поэтому там также при аллокации нескольких тысяч несвязанных между собой продолжений может выжрать весь хип и уронить гц.
Цитата
Что в сущности, стековый вариант и делает - для cps-продолжений поддержка рантайма не нужна, и их, если надо, всегда можно сделать руками.

Придется реализовывать собственный интерпретатор.
Цитата
Чуть быстрее _что именно_? У вас там в тестах создание продолжение и его вызов - это пара миллисекунд максимум, остальное время у вас бигнумы умножаются.

Я уже указал, что именно. Ведь я сравниваю не вызовы, а два подхода на примере вычисления факториала.
Цитата
Я никогда не писал, что он лучше, я писал, что операции создания/вызова продолжений в cps-реализации на порядок быстрее.

Быстрее вызов, но не его создание. Пройдитесь по цепочке вычислений необходимых для создания продолжения.
Цитата
И gc, кстати, подключается именно из-за бигнумов - если бы операции не выходили за пределы фикснумов, то гц бы практически не работал.

А вы представьте какое количество элементов ложится и удаляется со стека.
Цитата
Вот скорость вызова можно померять, например, как-то так:

Скорость вызова меня в данный момент не интересует, т.к. она зависит от реализации. Мне было важно сравнить два подхода к реализации продолжений для ToyLisp-а, что я и сделал.
Кстати, ваши же тесты на Chez Scheme:
> (time (test2 100000))
(time (test2 100000))
no collections
16 ms elapsed cpu time
11 ms elapsed real time
80 bytes allocated
> (time (test2 100000))
(time (test2 100000))
no collections
15 ms elapsed cpu time
11 ms elapsed real time
80 bytes allocated
> (time (test 100000))
(time (test 100000))
no collections
15 ms elapsed cpu time
17 ms elapsed real time
48 bytes allocated
> (time (test 100000))
(time (test 100000))
no collections
16 ms elapsed cpu time
18 ms elapsed real time
48 bytes allocated
> (time (test 100000000))
(time (test 100000000))
no collections
17265 ms elapsed cpu time
17270 ms elapsed real time
48 bytes allocated
> (time (test 100000000))
(time (test 100000000))
no collections
17297 ms elapsed cpu time
17299 ms elapsed real time
48 bytes allocated
> (time (test2 100000000))
(time (test2 100000000))
no collections
11281 ms elapsed cpu time
11271 ms elapsed real time
80 bytes allocated
> (time (test2 100000000))
(time (test2 100000000))
no collections
11281 ms elapsed cpu time
11280 ms elapsed real time
80 bytes allocated

Цитата
вот скорость создания продолжения:

Этот тест не учитывает дополнительные расходы вызванные использованием for и вызовом лямбды.

отредактировал(а) misha: 2011-08-05 13:59 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4621   2011-08-05 18:17 GMT+3 часа(ов)      
Цитата
По какому факту?

По определению понятия "побочного эффекта":
[url]http://en.wikipedia.org/wiki/Side_effect_(computer_science)[/url]

Цитата
В теории У меня тоже не создается, но подтирать стек приходится.

"Подтирать" - всмысле сдвигать указатель на вершину?

Цитата
Зависит от реализации. Можете в этом убедиться.

Если у вас стек копируется (что происходит в большинстве реализаций), то оверхед по памяти линеен по размеру стека (то есть линеен по размер фрейма*количество фреймов), в cps-реализации оверхед по памяти линеен от размера текущего фрейма.

Цитата
При cps-реализации продолжения хранятся в замыкании, поэтому там также при аллокации нескольких тысяч несвязанных между собой продолжений может выжрать весь хип и уронить гц.

Угу, но в cps-реализации ничего _не копируется_. Другими словами, любой фрейм существует в единственном экземпляре. В реализации со стеком у вас может быть сотня копий одного фрейма, в зависимости от того, сколько вы продолжений наплодите.

Цитата
Придется реализовывать собственный интерпретатор.

Зачем же? во-первых, можно сделать преобразование автоматически (как, например, в #lang web-server в racket), а если нужно в паре отдельных мест - можно напрямую руками переписать.

Цитата
Я уже указал, что именно. Ведь я сравниваю не вызовы, а два подхода на примере вычисления факториала.

Хорошо, я перефразирую вопрос - _по каким критериям_ вы сравнивали эти два подхода7 как вы утверждаете не по скорости. Тогда по каким?

Цитата
Быстрее вызов, но не его создание.

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

Цитата
А вы представьте какое количество элементов ложится и удаляется со стека.

Где и когда?

Цитата
Мне было важно сравнить два подхода к реализации продолжений для ToyLisp-а, что я и сделал.

Я так и не понял, что вы сравнивали. Вы написали два куска кода, которые ничем не отличаются и получали закономерный результат, что эти два куска кода выполняются за одинаковое время. Смысл?

Цитата
на Chez Scheme


я как понял это Petit? Ну это же интерпретатор, какой смысл сравнивать?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4622   2011-08-06 17:00 GMT+3 часа(ов)      
Цитата
По определению понятия "побочного эффекта"

Притн может быть сайд-эффектом когда отсутствует терминал(консоль), происходит запись в файл, печать со сдвигом каретки и др. Кстати, Racket создает консоль, когда она отсутствует.
Цитата
"Подтирать" - всмысле сдвигать указатель на вершину?

Да.
Цитата
Если у вас стек копируется (что происходит в большинстве реализаций), то оверхед по памяти линеен по размеру стека (то есть линеен по размер фрейма*количество фреймов), в cps-реализации оверхед по памяти линеен от размера текущего фрейма.

У меня копируется не стек, а ссылки на объекты.
> (factorial 10)
3628800
> fact/cont
#<current-continuation stack-size: 32>
> (factorial 20)
2432902008176640000
> fact/cont
#<current-continuation stack-size: 62>

stack-size - размер массива объектов.
Цитата
Угу, но в cps-реализации ничего _не копируется_. Другими словами, любой фрейм существует в единственном экземпляре. В реализации со стеком у вас может быть сотня копий одного фрейма, в зависимости от того, сколько вы продолжений наплодите.


cps-реализации создаются замыкания и копируются ссылки на продолжения. В хорошей реализации со стеком полностью копируется только то, что необходимо, а в основном копируются ссылки. Если бы вы провели исследование, то узнали бы, что cps-продолжение и копия стека у большинства хороших реализаций занимают практически одинаковое количество памяти.
Цитата
Зачем же? во-первых, можно сделать преобразование автоматически (как, например, в #lang web-server в racket), а если нужно в паре отдельных мест - можно напрямую руками переписать.

Руками вы ничего не будите делать потому что нефиг плодить сайд-эффекты.
Цитата
Хорошо, я перефразирую вопрос - _по каким критериям_ вы сравнивали эти два подхода7 как вы утверждаете не по скорости. Тогда по каким?

Я сравнивал их сугубо для того, чтобы выяснить какой из них лучше подходит для ToyLisp-а. Вариант со стеком оказался проще и он более гибкий, кстати, на реализацию escape-continuations у меня ушло всего 15 минут
Цитата
Ничего подобного, при создании продолжения выигрыш еще более очевиден. В реализации со стеком вы копируете стек (за счет аллокаций на хипе это _уже_ более дорого, чем любой другой метод аллокаций не требующий), а тут - просто передаете в ф-ю один дополнительный аргумент. Другими словами, опять же, создание продолжения в реализации со стеком _строго включает_ в себя cps-реализацию, т.к. нам надо на каждый функциональный вызов скопировать адрес возврата, что уже дольше передачи 1 аргумента (который тоже делается на каждый вызов).

Попробуйте проверить на других реализациях кроме Racket.
Цитата
Где и когда?

Во время вычисления функции наподобие факториала.
Цитата
я как понял это Petit? Ну это же интерпретатор, какой смысл сравнивать?
А Racket что?

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4623   2011-08-07 09:39 GMT+3 часа(ов)      
Цитата
Притн может быть сайд-эффектом когда отсутствует терминал

Он не "может быть" сайд-эффектом, он _всегда_ сайд-эффект по определению сайд-эффекта. Любое ИО - всегда сайд-эффект. И при чем тут терминал?

Цитата
У меня копируется не стек, а ссылки на объекты.

Ну это и подразумевается под копированием стека.

Цитата
cps-реализации создаются замыкания и копируются ссылки на продолжения.

Замыкания _ не надо_ создавать, замыкание - это просто пара из указателя на функцию и указателя на фрейм стека. Фрейм создается сразу, как только вы вызвали функцию. Всегда. Боьше ничего копировать и создавать не надо.

Цитата
что cps-продолжение и копия стека у большинства хороших реализаций занимают практически одинаковое количество памяти.

Ну а копия стека - занимает очень много памяти, по сравнению с замыканием.

Цитата
Руками вы ничего не будите делать потому что нефиг плодить сайд-эффекты.

При "ручной" реализации продолжений нет никаких сайд-эффектов.

Цитата
Я сравнивал их сугубо для того, чтобы выяснить какой из них лучше подходит для ToyLisp-а.

Так я еще раз спрашиваю - по каким критериям сравнивали?

Цитата
Вариант со стеком оказался проще и он более гибкий

Теперь прикрутите треды с ffi и расскажите про гибкость еще раз

Цитата
Попробуйте проверить на других реализациях кроме Racket.

Я ж повторюсь - это на любой реализации. которая копирует стек.

Цитата
Во время вычисления функции наподобие факториала.

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

Цитата
А Racket что?

Ну компилятор же.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#4624   2011-08-07 16:22 GMT+3 часа(ов)      
Цитата
Он не "может быть" сайд-эффектом, он _всегда_ сайд-эффект по определению сайд-эффекта. Любое ИО - всегда сайд-эффект. И при чем тут терминал?

В вашем случае сайд-эффект невозможен.
Цитата
Замыкания _ не надо_ создавать, замыкание - это просто пара из указателя на функцию и указателя на фрейм стека. Фрейм создается сразу, как только вы вызвали функцию. Всегда. Боьше ничего копировать и создавать не надо.


Замыкание - это объект. Где вы предполагаете хранить переменные унаследованные замыканием? Вам нужно еще одно дополнительное поле или поля.
Цитата
Ну а копия стека - занимает очень много памяти, по сравнению с замыканием.

С "цепочкой" замыканий! Все они хранятся в памяти. И тут уж все зависит от реализации, поэтому не стоит описывать сферического коня в вакууме.
Цитата
При "ручной" реализации продолжений нет никаких сайд-эффектов.

"а если нужно в паре отдельных мест - можно напрямую руками переписать." - в какой же это паре отдельных мест? Допустим, мне нужен ретурн из замыкания.
Цитата
Так я еще раз спрашиваю - по каким критериям сравнивали?

Легкость реализации, возможность оптимизации, производительность.
Цитата
Теперь прикрутите треды с ffi и расскажите про гибкость еще раз

Вы про green threads?
Цитата
Я ж повторюсь - это на любой реализации. которая копирует стек.

Как вы проверяли? Ах, да вы же не проверяли
Цитата
А, ну практически нисколько, операции со стеком на фикснумах в сотни раз быстрее, чем аллокация бигнумов в хипе.

Не спорю Но gc обязан утилизировать неиспользуемые объекты.
> (define (f n)
(if (zero? n)
1
(+ n (f (- n 1)))))
500000500001
> (time (f 1000000))
(time (f 1000000))
9 collections
656 ms elapsed cpu time, including 140 ms collecting
654 ms elapsed real time, including 131 ms collecting
38018936 bytes allocated, including 41086064 bytes reclaimed
500000500001
> (time (f 1000000))
(time (f 1000000))
9 collections
641 ms elapsed cpu time, including 108 ms collecting
638 ms elapsed real time, including 115 ms collecting
38018936 bytes allocated, including 18686696 bytes reclaimed
500000500001


Цитата
Ну компилятор же.

И Chez Scheme тоже компилятор. И ToyLisp компилятор

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#4632   2011-08-09 13:56 GMT+3 часа(ов)      
Цитата
В вашем случае сайд-эффект невозможен.

Если он невозможен - как я его сделал? еще раз - вывод сообщения на экран является сайд-эффектом по определению сайд-эффекта. я вывел сообщения на экран. Следовательно - сделал сайд-эффект.

Цитата
Замыкание - это объект.

Так, ну то, что вы од сайд-эффектом что-то свое личное понимаете мы уже выяснили, так еще и определение "объекта" у вас нестандартное?

Цитата
Где вы предполагаете хранить переменные унаследованные замыканием?

Что это за переменные такие?

Цитата
Вам нужно еще одно дополнительное поле или поля.

Конечно, не нужно. Еще раз, кода вы вызываете функцию, то создается фрейм стека. Что такое замыкание? Это указатель на функцию + указатель на фрейм стека ф-и, в которой это замыкание было создано. Когда вы создаете замыкание, то никаких переменных не создается
не копируется, они УЖЕ есть, как только вызвана функция.

Цитата
С "цепочкой" замыканий!

Да, но они в любом случае хранятся. То есть в не-cps форме в рекурсивной функции все те же переменные будут храниться на том же самом стеке и занимать ровно только же памяти. И cps-пребразование расхода памяти фактически не добавляет - добавляется только по 1 переменой на фрейм (указатель на замыкание).

Цитата
"а если нужно в паре отдельных мест - можно напрямую руками переписать." - в какой же это паре отдельных мест? Допустим, мне нужен ретурн из замыкания.

Ну делайте раз нужен, сайд-эффектов то все равно не будет.

Цитата
Легкость реализации, возможность оптимизации, производительность.

Ну легкость реализации и возможность оптимизации по тестам явно не определить, а вот производительность вы тестами не измерили.

Цитата
Вы про green threads?

да

Цитата
Как вы проверяли? Ах, да вы же не проверяли

вам если скажут, что 2+2=4, то вы будете это проверять? (выкладывать палочки или считать на пальцах, например)

Цитата
Не спорю Но gc обязан утилизировать неиспользуемые объекты.

Угу. Но если неиспользуемых объектов нет (как в случае с фикснумами), и память в процессе не аллоцировалась, то гц и делать нечего

Цитата
500000500001

Это бигнум, бигнумы аллоцируются на хипе. Фикснумы - не аллоцируются, соответственно и гц не требуют.

Цитата
И Chez Scheme тоже компилятор.

а на сайте Chez Scheme написано, что Petit - интерпретатор.


Онлайн :

0 пользователь(ей), 24 гость(ей) :




Реклама на сайте: