Thursday, March 29, 2007

Letting Go...


I've been really keen to get something together over the last few months for the Nullarbor Game compo, but I've had to let my entry slide. I've simply not had the time, real life commitments, and real life work kept getting in the way.

The venture was not entirely unproductive, however. A friend composed a great tune for my demo, which he called 'Under Sufferance'. If you like electronic stuff, it's worth a listen. (Try the download, as the stream uses Windows Media Player. Egh.)

Wednesday, March 28, 2007

Checking out Pylons

Over the last few days I've been evaluating Pylons, because I'm having some trouble making TurboGears behave with SQLAlchemy.

The first thing that I noticed, was the awesome thru-the-web-debugger which pops up in your browser when your code raises an uncaught exception. Wow. That's gonna come in handy.

The other great thing is that Pylons doesn't try to look after your database for you. You've got to handle all that yourself, which is great, because I want to be responsible for that code. The good news is that most of my TurboGears model could be copied straight over into Pylons, and it just worked.

One thing I don't really like about Pylons, is routes. I know I'm going against the grain here, but I prefer to override CherryPy's .default method rather than write a bunch of strange looking rules. In the end, thats probably what I'm going to do with routes. Just route every request to my own dispatch method, which, even though some may consider it hairy, provides a cleaner URL. I don't believe http methods belong in a RESTful URL, which is what routes seems to want to do.

Sunday, March 25, 2007

Scouta gets TechCrunched

Scouta was TechCrunched last Friday. So far, the TurboGears / lighttpd combination has been holding together quite well, no hiccups at all.

Wednesday, March 21, 2007

Particle Simulations


I've left the super-optimized, runtime-bytecode-compiling 3D engine project for a short while, so I can focus on a demo for the Nullarbor demoparty.

Competing in Nullarbor will be particularly challenging for me, simply because I'm using Python, and can't afford expensive CPU consuming algorithms.

I've decided to base the demo around particle system effects, mainly because Numpy is able to make these sorts of simulations relatively fast.

A couple of hints for would-be particle-system programmers: Use additive blending, use the GL point sprite extension, and turn off depth testing. If I had found these 3 hints spelled out in one sentence, I would have saved quite a few hours research. :-)

In other news, someone decided to debianize my FibraNet package. People actually _use_ this code? :-)

Sunday, March 18, 2007

Runtime Bytecode Assembly

Yesterday, I realized I could transform a Scenegraph DAG structure into a flat list, and iterate over that each frame.

Today, I realized I can do a lot better than that. I can actually generate bytecode from that structure, turn it into a function, and call that function for each frame.

Wow. This is really cool, fun stuff. It provides immediate, obvious optimizations. I've effectively unrolled a render loop and removed all the dispatch mechanisms from my inner loop.

Fortunately its quite easy to do, using the PEAK ByteCodeAssembler and the 'new' module in the standard library. This part of the PEAK documentation was the most helpful.

I'll post some code soon, I promise. :-)

Saturday, March 17, 2007

DAG finished, Interpreter next.

I've fixed up a problem or two with my DAG implementation, and uploaded it to the cheeseshop. It must be one of the smallest packages ever! :-)

While writing some tests to make sure my traversal function was processing nodes in the desired order, I realised that traversing the graph results in a 1D list of nodes (processing instructions) with a bunch of stack pops and pushes in the right places. Then I realised... this list is never going to change, unless I add or remove nodes, which in practice, rarely happens.

This makes the DAG really only one phase of process, which can be re-visited as needed, not on every processing pass. The DAG is used to produce a linear list of instructions, which I can feed into an interpreter.

This sounds like a good optimisation to me, and a fun diversion for a Saturday afternoon.

Friday, March 16, 2007

Walking a Graph

I must have written at least 10 different DAG implementations, but I feel I still haven't found the perfect, Pythonic implementation.

I use these things to build and experiment with scenegraph based graphics engines, so therefore, the requirements are, in order of priority:

  1. Speed.

  2. Flexibility.

  3. Elegance.


I need speed, because I'd like to experiment with graphics techniques which require multiple traversals over the graph for each frame before it gets displayed to the screen.

I've tried, and given up previously, but now, I'm trying to approach the problem from a different angle, armed with Python2.5.

So, who wants to help build a super fast depth first traversal algorithm? :-)


This is the code for building my graph, with some extra features I'll need later for talking to OpenGL.

class Node(object):
"""
A node in a graph.
"""
_instances = weakref.WeakValueDictionary()
_instance_count = 0
def __new__(cls, *args, **kw):
instance = object.__new__(cls, *args, **kw)
instance._id = Node._instance_count
Node._instances[instance._id] = instance
Node._instance_count += 1
return instance

@classmethod
def get(cls, id):
"""
Returns a node by its _id attribute.
"""
return cls._instances[id]

def __repr__(self):
return "<%s #%s object>" % (self.__class__.__name__, self._id)


class Composite(Node):
"""
A node in a graph, composed of other nodes.
"""
def __init__(self, *children):
self.children = list(children)

def add(self, *nodes):
self.children.extend(nodes)

def remove(self, *nodes):
self.children.extend(nodes)


... and this is the code I'll use to benchmark my algorithms... with a free naive recursive walker included!


if __name__ == "__main__":
import time

def dispatch(node):
pass

def walk(node, indent=0):
dispatch(node)
for child in getattr(node, 'children', []):
walk(child, indent+1)

def build_test(node, depth=0):
if depth > 5: return
n = Composite()
node.add(n)
for i in xrange(5):
n.add(*(Node() for x in xrange(5)))
build_test(n, depth+1)

root = Composite()
build_test(root)
t = time.clock()
walk(root)
print time.clock() - t


UPDATE:

This is the fastest traversal function so far. It runs 1.37 times faster than the recursive walk. On my machine it walks 289261 nodes in 0.378 seconds. I think I can forget about this now, and work on something else :-)


def stack_walk(root):
stack = deque([root])
stack_pop = stack.pop
stack_extendleft = stack.extendleft
while stack:
node = stack_pop()
dispatch(node)
if hasattr(node, 'children'):
stack_extendleft(node.children)



UPDATE UPDATE:

Of course, after writing a unit test to test the processing order of the traversal function, I discovered I got it wrong...

It should look like this:


def traverse(root, dispatch):
stack = deque([root])
stack_pop = stack.popleft
stack_extend = stack.extend
stack_rotate = stack.rotate
while stack:
node = stack_pop()
dispatch(node)
if hasattr(node, 'children'):
stack_extend(node.children)
stack_rotate(len(node.children))

Having TurboGears Problems

I'm using TurboGears with the SQLAlchemy ORM Library for a couple of large projects. SQLAlchemy is magic, and TurboGears has definitely provided a rapid development environment for both projects, however it is becoming clear that the second-class-citizen status of SQLAlchemy is becoming a problem in one of my applications, where I need greater control over database transactions and exception handling. In this case, TG is just getting in the way.

It looks like most of these SA integration problems are being addressed in some future TG release, but I can't really wait, and I'm not inclined to fix the TG code (all that multimethod RuleDispatch code makes my brain hurt). I'm going to write my own specialised expose/identity/validate decorators, and try a specialised CherryPy3/Genshi/SQLAlchemy combination without TG.

Sunday, March 11, 2007

Interviewing at Google

I had a preliminary phone interview with Google last Wednesday. Seems they are chasing Python programmers for positions at YouTube, and my name came up on their radar.

The interview went well (for what is was), but since then I've discovered it may be very difficult to get the required E-3 visa which is needed for Australians to do this kind of work in the US.

The problem is, I need to qualify as a 'skilled person', which requires a BSc, or equivalent (8 years) work experience. I have part of a degree, which I'm not likely to finish, and only 6 years of commercial work experience, which basically means I don't qualify for the visa.

Anyone else had to tackle this problem before?

Saturday, March 10, 2007

Nullarbor Approaches


The Nullabor Demoparty is approaching quickly. This year it is being held at the GO3 Conference at the end of March.

I've still not started my entry in the competition, simply due to a lack of available free time. I'm not too worried though, last year I wrote Krool Joolz over one week, and it was good enough to come second... though I do expect the quality of the competition to be much higher this year... hmmm.

I think I'd better start something. Soon.

Friday, March 09, 2007

Sometimes, you _need_ AJAX.

The latest version of Scouta went live this week, with a cool new feature.

An asynchronous commenting system.

Asynchronous comments are very important in Scouta, as we want discussions to sit right next to the media item, yet we don't want to interrupt the video or audio stream if the user decides to post a comment while the media item is playing. At the same time, we can't generate the conversation thread completely inside Javascript, because that would prevent conversations being spidered by search engines...

Anyhow, MochiKit and JSON came to the rescue, I ended up sending back the HTML fragment (which represents the comment) inside the POST request, which then gets dropped into the UL container. I think this is a pretty common technique, and it works well.

To achieve all this asynchronous magic, I have needed to write a _lot_ of Javascript, which has made me really appreciate and understand the benefit of multiline anonymous functions. It sure would be great to have these in Python, though I cannot imagine what the syntax might look like...

Popular Posts