Why/where is SBCL consing memory?
in [Lisp]
|
From: Bob Felts on 19 Jun 2010 10:28 A small Lisp function when timed under Lispworks Personal edition on my Macbook Pro gives: User time = 0.146 System time = 0.000 Elapsed time = 0.205 Allocation = 6528 bytes On various runs, the allocation numbers are: 6528, 4532, 4460, 21412(???), 5300, 4696, 6296, ... bytes. The same code when timed with SBCL 1.0.39 results in: 0.095 seconds of real time 0.093463 seconds of total run time (0.087737 user, 0.005726 system) [ Run times consist of 0.017 seconds GC time, and 0.077 seconds non-GC time. ] 97.89% CPU 222,259,870 processor cycles 5,143,312 bytes consed SBCL is consistently in the 5 million range. 5 million vs. 6K bytes? The LispWork report matches what I think the code should be doing. How would one go about finding out where SBCL is using memory? Further subdivide the code with judicious placement of calls to (time)?
From: Tamas K Papp on 19 Jun 2010 10:46 On Sat, 19 Jun 2010 10:28:49 -0400, Bob Felts wrote: > The LispWork report matches what I think the code should be doing. How > would one go about finding out where SBCL is using memory? Further Check http://www.sbcl.org/manual/Statistical-Profiler.html , there is some support for allocation profiling (but it depends on your platform). You might want to ask on the SBCL dev mailing list too, preferably with some code. Tamas
From: D Herring on 19 Jun 2010 21:36 On 06/19/2010 10:28 AM, Bob Felts wrote: > A small Lisp function when timed under Lispworks Personal edition on my > Macbook Pro gives: .... > The LispWork report matches what I think the code should be doing. How > would one go about finding out where SBCL is using memory? Further > subdivide the code with judicious placement of calls to (time)? Could you share the code? Does the consing occur inside the function, or when its result is printed? Are you using a recent build of SBCL? - Daniel
From: Bob Felts on 20 Jun 2010 14:43 D Herring <dherring(a)at.tentpost.dot.com> wrote: > On 06/19/2010 10:28 AM, Bob Felts wrote: > > A small Lisp function when timed under Lispworks Personal edition on my > > Macbook Pro gives: > ... > > The LispWork report matches what I think the code should be doing. How > > would one go about finding out where SBCL is using memory? Further > > subdivide the code with judicious placement of calls to (time)? > > Could you share the code? Does the consing occur inside the function, > or when its result is printed? Are you using a recent build of SBCL? > 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. 2) Inside. The result is just a list of 23 elements. 3) The latest: 1.0.39 ;;; ;;; find path from start to finish which goes through ;;; each node only once ;;; (defparameter start '(a f l k s)) (defparameter a '(f b h d)) ; was '(start f (defparameter b '(a l m g)) (defparameter c '(d o i g)) (defparameter d '(a h c o j)) (defparameter e '(k p s)) (defparameter f '(a l)) (defparameter g '(b c h m n)) (defparameter h '(a d g)) (defparameter i '(c r n finish)) (defparameter j '(d o)) (defparameter k '(e)) (defparameter l '(f b p)) (defparameter m '(b g n p)) (defparameter n '(g i m u finish)) (defparameter o '(j d c r finish)) (defparameter p '(l m e v)) (defparameter q '(v p m n u)) (defparameter r '(i o)) (defparameter s '(e v finish)) (defparameter v '(s p u)) (defparameter u '(q v n finish)) (defparameter finish '()) (defparameter nodes '(start a b c d e f g h i j k l m n o p q r s v u finish)) (defun find-path (from to) (let* ((max-steps (length nodes)) (path (make-array max-steps)) (neighbors (make-array max-steps)) (steps 0)) (flet ((path-found-p () (and (= steps max-steps) (eql (aref path (1- max-steps)) to))) (next-viable-node (neighbors) (member-if #'(lambda (n) (not (find n path :end steps))) neighbors)) (add-to-path (node) (setf (aref path steps) node) (setf (aref neighbors steps) (symbol-value node)) (incf steps))) (add-to-path from) (loop while (and (> steps 0) (not (path-found-p))) for next = (next-viable-node (aref neighbors (1- steps))) do (if (null next) (decf steps) (progn (setf (aref neighbors (1- steps)) (rest next)) (add-to-path (first next))))) (if (= steps 0) nil (coerce path 'list)))))
From: Olof-Joachim Frahm on 20 Jun 2010 19:40
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))) -- The world is burning. Run. |