Efficiency, Delayed Computation and Lambda

Discussion of Common Lisp
Post Reply
VincentToups
Posts: 9
Joined: Tue Jul 01, 2008 1:15 pm

Efficiency, Delayed Computation and Lambda

Post by VincentToups » Mon Oct 13, 2008 5:39 am

Hi Lispforum,

Suppose you have some Common Lisp code representing a game and you want to abstract drawing the game away from updating the game. For instance, you might have everything in your game "universe" represented in a big list CLOS objects which need to be updated and drawn once per turn.

Code: Select all

(defparameter *game* nil)
(push (make-instance 'bouncing-box :draw-layer 1) *game*)
(push (make-instance 'bouncing-box :draw-layer 2) *game*)

(loop while T do
    (map #'update *game*)
    (map #'draw *game*))
Everyone can imagine what the update method looks like for a bouncing box. The draw method is where the question arises. It might look something like this.

Code: Select all

(defclass bouncing-box ()
    ((color :initform 'blue :initarg :blue :accessor color-of)
      (x :initform 0 :initarg :x :accessor x-of)
	  (y :initform 0 :initarg :y :accessor y-of)
      (draw-layer :initform 0 :initarg :draw-layer :accessor :draw-layer-of)))

(defmethod draw ((bb bouncing-box))
     (draw-box-to-screen (x-of bb) (y-of bb) 4 4 (color-of bb)))
This almost accomplishes what we want. Unfortunately it doesn't respect the draw layer. In order to layer our drawings correctly, we need a way of sorting the drawing operations so that they happen in the right order, regardless of the order that the objects are updated or drawn in.

One approach is to implement layered drawing.

Code: Select all


(defparameter *nlayers* 6)
(defparameter *layers* (make-array (list *nlayers*)))

(defun push-layer (n lam)
	(push lam (aref *layers* n) ))
(defun clear-layers ()
  (loop for i from 0 below *nlayers*
	   do (setf (aref *layers* i) nil)))
(defun do-layers ()
  (loop for layer across *layers* do
	   (loop for lam in layer do
			(funcall lam)))
  (clear-layers))
		   
Then our draw method can become:

Code: Select all

(defmethod draw ((bb bouncing-box))
     (push-layer (draw-layer-of bb) (lambda () (draw-box-to-screen (x-of bb) (y-of bb) 4 4 (color-of bb)))))

And our game loop becomes:

Code: Select all

(loop while T do
    (map #'update *game*)
    (map #'draw *game*)
	(do-layers))
In my actual source code the objects are separated into models and views so that I can replace the renderer more easily (or even render to text, since I am working on a roguelike), but the principle is that demonstrated in the code above.

The question is that in a regular game you might have 20 or so objects on the screen at once, possibly more, and making a bunch of lambdas and deleting them every turn seems like the kind of inefficiency that could rapidly become unwieldy.

We are basically using lambda here as a smart quotation, delaying computation until an appropriate time (in fact it is the implementations of delay and force which inspired this method, for instance the one here http://common-lisp.net/project/clazy/).

Certain optimizations seem obvious. Use vectors instead of lists for each layer so you can recycle the storage, for instance. Clear each layer during the draw-pass. But no approach I can think of that follows this basic architecture seems to be able to avoid the cost of creating (and then freeing) all these arbitrary lambdas.

The only think I can think of is to formalize the drawing operations much more finely so that you only allow, for instance, drawing of geometric shapes and sprites and text, say. Then each drawing request can be sent as a simple data structure and not a delayed computation. But this seems like a big lose in terms of flexibility.

So I ask the Common Lispers, is it really so bad to make this many lambdas? Is there a more "lispy" or "common lispy" solution to the problem? Is there are more efficient way to represent delayed computations?

(Before anyone asks, I know it doesn't matter until I need the efficiency, but delayed computation is an interesting subject and a good way to emphasize the usefulness of lambda as a kind of smart quotation, so I think the discussion is useful, even if in this case there may be no point.)

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Efficiency, Delayed Computation and Lambda

Post by Jasper » Mon Oct 13, 2008 9:11 am

Why not just (defmethod draw-object ((object its-type) (layer fixnum) (env environment)...) Then you can make passes for each layer and objects can write to layers as they wish. You might of course also optimize to avoid some of the layers objects that do not draw to many layers, using an array for objects drawing to a single layer, perhaps also two layers.
Also, if you're using opengl, you could use a depth buffer, if you are drawing manually, you could add an index to each pixel.(But drawing manually stops you from using many of the libs.)

It doesn't entirely solve the problem of overlapping objects that draw to the same layer. They might flicker when they change order.
I had that with switching lists of a quadtree. Have not looked into fixing that yet. Made a quadtree with multiple layers per node, for speed :D, now to get the heightmap to work.(Coding that is a pain in the ass, need to match all the corners.)

I do not really know how bad making many lambdas is, probably in many cases lambdas just become constant things only made once (compile time) they probably can even be inlined. The way you are doing it won't do that, because they are actual objects that can change. So that might indeed sting a little. On the other hand, it might just position 3 pointers and two integers behind a function pointer and call it a function.

qbg
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

Re: Efficiency, Delayed Computation and Lambda

Post by qbg » Mon Oct 13, 2008 10:30 am

What will probably happen in most implementations is that the lambdas will become compiled closures, which a closure being simply a code vector and an environment. The code vector is going to be constant, so all what you are consing are the environments, which in most cases will probably not be too huge.

As a data point, trees of compiled closures have been used as a way of compiling a DSL much more efficiently than converting it to lisp and invoking the compiler at runtime. The speed of the resulting code is similar, but creating it is typically 100-1000 times faster. IIRC, this is what CL-PPCRE does.

Paul Donnelly
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Efficiency, Delayed Computation and Lambda

Post by Paul Donnelly » Mon Oct 13, 2008 1:03 pm

I realize your lambda question is independent of the code here... but why not just draw things in the right order to begin with?

Post Reply