From: Bob Felts on 20 Jun 2010 20:37 Olof-Joachim Frahm <Olof.Frahm(a)web.de> wrote: > wrf3(a)stablecross.com (Bob Felts) writes: > > > 1) Sure. It's a variation on the maze traversal algorithm "right > > if you can, left if you must." The graph can be seen here: > > http://stablecross.com/files/Static_Code_Analysis.html. In > > this blog post, I kinda bad-mouthed C, so I wrote C style code > > that didn't require dynamic memory allocations to solve the > > problem. I then coded the same algorithm in Lisp and was stunned > > to find that it cons'd so much memory. I had to double-check > > things with LispWorks. > > Well, never trust the default implementation. Although I can't see > where this allocations come from (could someone explain?), if you > replace the MEMBER-IF call with a custom loop, no more than the return > value from COERCE is allocated: > > ;; ... > (next-viable-node (neighbors) > (loop > for neighbor on neighbors > unless (find (car neighbor) path :end steps :test #'eq) > do (return neighbor))) That sure seems to be it. But (defun foo ( ) (let ((path (make-array 23 :initial-contents '(start a b c d e f g h i j l m n o p q r s t nil nil nil)))) (member-if #'(lambda (n) (not (find n path :end 20))) '(a b c d e f v q r s)))) (time (foo)) says that nothing was consed.
From: Bob Felts on 20 Jun 2010 20:49 Bob Felts <wrf3(a)stablecross.com> wrote: > Olof-Joachim Frahm <Olof.Frahm(a)web.de> wrote: > > > wrf3(a)stablecross.com (Bob Felts) writes: > > > > > 1) Sure. It's a variation on the maze traversal algorithm "right > > > if you can, left if you must." The graph can be seen here: > > > http://stablecross.com/files/Static_Code_Analysis.html. In > > > this blog post, I kinda bad-mouthed C, so I wrote C style code > > > that didn't require dynamic memory allocations to solve the > > > problem. I then coded the same algorithm in Lisp and was stunned > > > to find that it cons'd so much memory. I had to double-check > > > things with LispWorks. > > > > Well, never trust the default implementation. Although I can't see > > where this allocations come from (could someone explain?), if you > > replace the MEMBER-IF call with a custom loop, no more than the return > > value from COERCE is allocated: > > > > ;; ... > > (next-viable-node (neighbors) > > (loop > > for neighbor on neighbors > > unless (find (car neighbor) path :end steps :test #'eq) > > do (return neighbor))) > > That sure seems to be it. But > > (defun foo ( ) > (let ((path (make-array 23 :initial-contents > '(start a b c d e f g h i j l m n o p q r s t nil nil nil)))) > (member-if #'(lambda (n) (not (find n path :end 20))) > '(a b c d e f v q r s)))) > > (time (foo)) > > says that nothing was consed. It's the lambda in the member-if that's doing it. If I change the flet to labels and create the function foo: (foo (n) (not (find n path :end steps))) (next-viable-node (neighbors) (member-if #'foo neighbors)) then nothing is consed.
From: alien_guy on 21 Jun 2010 04:14
On Sun, 20 Jun 2010 20:37:23 -0400, Bob Felts wrote: > Olof-Joachim Frahm <Olof.Frahm(a)web.de> wrote: > >> wrf3(a)stablecross.com (Bob Felts) writes: >> >> > 1) Sure. It's a variation on the maze traversal algorithm "right >> > if you can, left if you must." The graph can be seen here: >> > http://stablecross.com/files/Static_Code_Analysis.html. In this >> > blog post, I kinda bad-mouthed C, so I wrote C style code that >> > didn't require dynamic memory allocations to solve the problem. >> > I then coded the same algorithm in Lisp and was stunned to find >> > that it cons'd so much memory. I had to double-check things with >> > LispWorks. >> >> Well, never trust the default implementation. Although I can't see >> where this allocations come from (could someone explain?), if you >> replace the MEMBER-IF call with a custom loop, no more than the return >> value from COERCE is allocated: >> >> ;; ... >> (next-viable-node (neighbors) >> (loop >> for neighbor on neighbors >> unless (find (car neighbor) path :end steps :test #'eq) do >> (return neighbor))) > > That sure seems to be it. But > > (defun foo ( ) > (let ((path (make-array 23 :initial-contents > '(start a b c d e f g h i j l m n o p q r s t nil nil nil)))) > (member-if #'(lambda (n) (not (find n path :end 20))) > '(a b c d e f v q r s)))) > > (time (foo)) SBCL's TIME typically returns 0 if the allocated amount of memory was less than one GC page CL-USER> (time (loop repeat 1000 do (foo))) Evaluation took: 0.006 seconds of real time 0.003333 seconds of total run time (0.003333 user, 0.000000 system) 50.00% CPU 8,046,939 processor cycles 105,472 bytes consed |