Есть 2 функции, первая без сайд-эффектов генерирует новый список, вторая — деструктивно меняет значение одного из своих аргументов:
(defun f (a)
(mapcar #'1+ a))
(defun f2 (a b)
(map-into b #'1+ a))
Вторая функция, насколько я понимаю, должна быть и быстрей и меньше использовать память, за счет того, не происходит дополнительного выделения памяти при каждом вызове.
Но тестовые запуски показывают обратное — мало того, что f2 работает почти на 2 порядка медленней, так еще и памяти. как будто, больше потребляет:
CL-USER> (let ((xs (make-list 1000 :initial-element 0)))
(time
(dotimes (i 100)
(reduce #'+ (f xs)))))
Evaluation took:
0.01 seconds of real time
0.008999 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
2,399,464 bytes consed.
NIL
CL-USER> (let ((xs (make-list 1000 :initial-element 0)))
(let ((ys (make-list 1000)))
(time
(dotimes (i 100)
(reduce #'+ (f2 xs ys))))))
Evaluation took:
0.647 seconds of real time
0.646902 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
3,202,280 bytes consed.
При использовании вектора вместо списка разница в скорости уменьшается до 2 раз: с использованием f — 0.012, с f2 — 0.022.
И я не могу понять, чем объясняется большая скорость функции f? И прав ли я, что функция f по логике должна больше выделять памяти?
И может быть, кого-нибудь не затруднит попробовать такой тест на haskell'е?
Здравствуйте, Аноним, Вы писали:
А>И я не могу понять, чем объясняется большая скорость функции f? И прав ли я, что функция f по логике должна больше выделять памяти? А>И может быть, кого-нибудь не затруднит попробовать такой тест на haskell'е?
А ничего, что у тебя первая функция оперирует одним списком, а вторая двумя?
Re[2]: [lisp]деструктивность и выделение памяти
От:
Аноним
Дата:
21.04.08 11:35
Оценка:
Здравствуйте, Turtle.BAZON.Group, Вы писали: TBG>А ничего, что у тебя первая функция оперирует одним списком, а вторая двумя?
так и первая оперирует двумя списками — второй-то она создает и записывает туда результат. разве нет?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Turtle.BAZON.Group, Вы писали: TBG>>А ничего, что у тебя первая функция оперирует одним списком, а вторая двумя? А>так и первая оперирует двумя списками — второй-то она создает и записывает туда результат. разве нет?
Хм... Да, действительно. А у тебя что за лисп то?
CLISP:
[6]> (let ((xs (make-list 1000 :initial-element 0)))
(time
(dotimes (i 100)
(reduce #'+ (f xs)))))
Real time: 0.036111 sec.
Run time: 0.036002 sec.
Space: 800752 Bytes
GC: 1, GC time: 0.004001 sec.
NIL
[7]> (let ((xs (make-list 1000 :initial-element 0)))
(let ((ys (make-list 1000)))
(time
(dotimes (i 100)
(reduce #'+ (f2 xs ys))))))
Real time: 0.051273 sec.
Run time: 0.052003 sec.
Space: 752 Bytes
NIL
Re[4]: [lisp]деструктивность и выделение памяти
От:
Аноним
Дата:
22.04.08 14:17
Оценка:
TBG>Хм... Да, действительно. А у тебя что за лисп то?
SBCL 1.0.12 под linux
Здравствуйте, Аноним, Вы писали:
TBG>>Хм... Да, действительно. А у тебя что за лисп то? А>SBCL 1.0.12 под linux
Да, под SBCL такие же результаты как и у тебя. Ещё не разбирался, но, видимо, деструктивная опреация замены элемента в списке выполняется следующим образом:
создаётся новая cons-пара;
разрываются связи в списке и указывают на новую пару, а cdr старой на вторую часть списка;
старая cons-пара уходит в GC и занимает память.
TBG>Да, под SBCL такие же результаты как и у тебя. Ещё не разбирался, но, видимо, деструктивная опреация замены элемента в списке выполняется следующим образом:
TBG>
TBG> создаётся новая cons-пара; TBG> разрываются связи в списке и указывают на новую пару, а cdr старой на вторую часть списка; TBG> старая cons-пара уходит в GC и занимает память. TBG>
TBG>Пока только такое объяснение.
Наврядли это даст разницу в 600 раз по производительности. А оптимизация там случаем не выполняется ? Оптимизатор функцию без сайд-эффектов может меморизовать. Тем более в данном случае целесообразность меморизации очевидна, поскольку f1 всегда вызывается с одним и тем же аргументом. Для чисоты експеримента надо вызывать с разными аргументами
Здравствуйте, chukichuki, Вы писали:
C>Наврядли это даст разницу в 600 раз по производительности. А оптимизация там случаем не выполняется ? Оптимизатор функцию без сайд-эффектов может меморизовать. Тем более в данном случае целесообразность меморизации очевидна, поскольку f1 всегда вызывается с одним и тем же аргументом. Для чисоты експеримента надо вызывать с разными аргументами
60. Ну чистота так чистота. Код и результаты ниже. Думаю, мемоизация тут не при чём.
(defun make-random-list (size &;optional initial-list)
(if (= size 0)
initial-list
(make-random-list (- size 1)
(cons (random size) initial-list))))
(defun f (a)
(mapcar#'1+ a))
(defun f2 (a b)
(map-into b #'1+ a))
(let ((xs (make-random-list 1000)))
(time
(dotimes (i 100)
(reduce#'+ (f xs)))))
(let ((xs (make-random-list 1000)))
(let ((ys (make-list 1000)))
(time
(dotimes (i 100)
(reduce#'+ (f2 xs ys))))))
CLISP
turtle@devel13:~/temp/_icons$ clisp test.lisp
Real time: 0.039339 sec.
Run time: 0.040002 sec.
Space: 800752 Bytes
GC: 1, GC time: 0.008001 sec.
Real time: 0.058397 sec.
Run time: 0.056003 sec.
Space: 752 Bytes
SBCL
Evaluation took:
0.012 seconds of real time
0.008001 seconds of user run time
0.004 seconds of system run time
0 calls to %EVAL
0 page faults and
2,399,464 bytes consed.
Evaluation took:
0.404 seconds of real time
0.388024 seconds of user run time
0.004 seconds of system run time
0 calls to %EVAL
0 page faults and
3,202,272 bytes consed.
Ничего по сути не поменялось. Вызов (f xs) в первом случае можно либо меморизовать, либо вынести за пределы цикла, посколку результат (f xs) неизменен на всех итерациях. Это достаточно прозрачно для компилятора — функция без сайд-эффектов вызывается с неизменным аргументом => ее можно вынести из цикла или меморизовать. Распознать неизметность (f2 xs ys) труднее. Вполне возможно что у компилятора просто нехватает на это "мозгов". f2 — функция с сайд-эффектом, одним из ее аргументов является значение, которое меняется от итерации к интерации => не факт что ее можно за пределы цикла вынести. Для уверенности надо анализировать внутренности f2, map-into и т.д. Возможно компилятор этого делать не умеет или не хочет без особого указания от пользователя
Здравствуйте, chukichuki, Вы писали:
C>Ничего по сути не поменялось. Вызов (f xs) в первом случае можно либо меморизовать, либо вынести за пределы цикла, посколку результат (f xs) неизменен на всех итерациях. Это достаточно прозрачно для компилятора — функция без сайд-эффектов вызывается с неизменным аргументом => ее можно вынести из цикла или меморизовать. Распознать неизметность (f2 xs ys) труднее. Вполне возможно что у компилятора просто нехватает на это "мозгов". f2 — функция с сайд-эффектом, одним из ее аргументов является значение, которое меняется от итерации к интерации => не факт что ее можно за пределы цикла вынести. Для уверенности надо анализировать внутренности f2, map-into и т.д. Возможно компилятор этого делать не умеет или не хочет без особого указания от пользователя
Да ну? И как же вынесется (f xs)? И как её можно так круто замемоизовать?
Здравствуйте, Turtle.BAZON.Group, Вы писали:
TBG>Здравствуйте, chukichuki, Вы писали:
TBG>Да ну? И как же вынесется (f xs)? И как её можно так круто замемоизовать?
Если я правильно понял твой код (мог и ошибиться, я практики в лиспе не имею), то хотябы так ...
Здравствуйте, Аноним, Вы писали:
А>Есть 2 функции, первая без сайд-эффектов генерирует новый список, вторая — деструктивно меняет значение одного из своих аргументов:
реализации ФП языков могут быть лучше тюнингованы под недеструктивные вычисления. в частности, в ghc (с лиспами дела не имел) GC куда лучше работает с необновляемыми значениями. в них ссылки могут быть только назад (понятно почему?) поэтому сбор мусора для них очень прост — обрабатываем последние 256кб распределённой памяти и освобождаем все ячейки, выделенные в этих 256кб, на которые нет ссылки здесь же. если же разрещить обнолвение данных, то каждый сбор мусора должен порсматривать всю кучу, что гораздо медленнее
C>Что вообщем то правильно, если я нигде не ошибся
А в таком случае следующие результаты (в общем то, ничего не изменилось):
turtle@devel13:~/temp/_icons$ clisp test.lisp
Real time: 3.69E-4 sec.
Run time: 0.0 sec.
Space: 8752 Bytes
Real time: 5.57E-4 sec.
Run time: 0.0 sec.
Space: 752 Bytes
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
24,576 bytes consed.
Evaluation took:
0.006 seconds of real time
0.008001 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
32,760 bytes consed.
BZ>реализации ФП языков могут быть лучше тюнингованы под недеструктивные вычисления. в частности, в ghc (с лиспами дела не имел) GC куда лучше работает с необновляемыми значениями. в них ссылки могут быть только назад (понятно почему?) поэтому сбор мусора для них очень прост — обрабатываем последние 256кб распределённой памяти и освобождаем все ячейки, выделенные в этих 256кб, на которые нет ссылки здесь же. если же разрещить обнолвение данных, то каждый сбор мусора должен порсматривать всю кучу, что гораздо медленнее
Прошу прощения, но то, что ты описал, подходит только для нергичных вычислений.
При ленивых вычислениях могут образовываться ссылки в любое место памяти.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
T>Прошу прощения, но то, что ты описал, подходит только для нергичных вычислений.
T>При ленивых вычислениях могут образовываться ссылки в любое место памяти.
