Valued Lessons

Decorators in python are very powerful, but are often a pain to get right, especially when you want to pass arguments to the decorator. Typically, it involves defining a function in a function in a function, etc, up to 4 layers deep. Can we make it easier? What if we even made a decorator to make decorators?

Perhaps we could use it catch and log errors:

@decorator
def log_error(func, *args, **kargs):
 try:
 return func(*args, **kargs)
 except Exception, error:
 print "error occurred: %r" % error
@log_error
def blowup():
 raise Exception("blew up")
blowup() # this gets caught and prints the error

Or maybe we'd like to synchronize a function to make it thread-safe:

@decorator
def synchronized(lock, func, *args, **kargs):
 lock.acquire()
 try:
 return func(self, *args, **kargs)
 finally:
 lock.release()
missle_lock = thread.RLock()
@synchronized(missle_lock)
def launch_missiles():
 pass

Or we could even use arguments to do do some object __init__ trickery (something I've had to do when working with wxpython):

@decorator
def inherits_format(method, *args, **kargs):
 self, parent = args[:2]
 self.format = parent.format
 return method(*args, **kargs)
class Child:
 @inherits_format
 def __init__(self, parent):
 pass
class Parent:
 def __init__(self, format):
 self.format = format
format = object()
child = Child(Parent(format))
assert child.format is format

If you've never worked python decorators, these are few examples of how powerful they are. But you'll probably never want to write your own because it can be a pain. If that's the case, then the decorator decorator is for you! Here's the code for it. It's a little tricky, but all you have to do is import it, slap @decorator before your decorator, make sure you call func(*args, **kargs), and you're all set. This is as easy as decorators can get.

Update: Dave left a comment and notified me that there is another, much more complete, implementation of the same idea at http://www.phyast.pitt.edu/~micheles/python/documentation.html. So, if you want a very complete module, go there. If you want something small and simple to cut and paste into your own code, use the following.

def decorator(decorator_func):
 decorator_expected_arg_count = decorator_func.func_code.co_argcount - 1
 if decorator_expected_arg_count:
 def decorator_maker(*decorator_args):
 assert len(decorator_args) == decorator_expected_arg_count, "%s expects %d args" % (decorator_func.__name__, decorator_expected_arg_count)
 def _decorator(func):
 assert callable(func), "Decorator not given a function. Did you forget to give %r arguments?" % (decorator_func.__name__)
 def decorated_func(*args, **kargs):
 full_args = decorator_args + (func,) + args
 return decorator_func(*full_args, **kargs)
 decorated_func.__name__ = func.__name__
 return decorated_func
 return _decorator
 return decorator_maker
 else:
 def _decorator(func):
 def decorated_func(*args, **kargs):
 return decorator_func(func, *args, **kargs)
 decorated_func.__name__ = func.__name__
 return decorated_func
 return _decorator
 

69 comments

Labels: decorator, programming, python

For many months, perhaps years, we as programmers have realized our trouble ahead coming with the "manycore era". The attitude seems to be "someday we're really going to have to figure this concurrency thing out". But this month I have been hit with a terrible realization: the manycore era is already upon us. Technically, it's the "multicore", not "manycore", but I think that's a small distinction.

Why the sudden epiphany? A few weeks ago, I built my self a new computer and put in an Intel quad-core CPU. My computer is much faster now, and I'm very happy with it, but after a few weeks I have realized something: I never use more than 1/4 of my CPU. I have a little graph on my screen at all times showing me the CPU usage. It goes up to 25% all of the time, but I have never seen it go higher. Ever.

On one hand this is a good thing. The new computer is so fast that everything I do is instant, and only uses a tiny bit of power. If it isn't instant, it's usually disk or network bound, not CPU bound.

On the other hand, even my own software isn't using more than 25%, and it is CPU bound at times. I'd like to fix it, but it's written in python, and the short version of a long, boring story is that python has a thing called The GIL which makes it so python as currently implemented cannot use more than 25% of the CPU except under very rare circumstances.

It seems that programming languages takes a long time to be adopted, but I think concurrency is a big enough rule changer to shake up which programming languages are dominant. In my specific case, if python doesn't fix it's concurrency problems soon, I'm going to have to stop considering it because I'll never be able to get it to use more than 1 little piece of the CPU. Right now, that's 25%, but in a few years, it will be only 3%. Either python is going to have to change, or I'm going to have to change programming languages (or use something like Jython or IronPython, I suppose).

A few weeks ago, sitting behind my single core computer, I was in the "someday, we'll have to tackle concurrency" camp. Now, sitting in front of my quad core machine, never using more than 25% of its power, everything has changed. Concurrency is no longer a question of if or when, it's here right now. If you don't believe me, get yourself a quad-core machine and watch the CPU usage graph. I think you'll be surprised.

56 comments

Labels: concurrency, manycore, python

DTrace is an incredible tool. It basically lets you do profiling of a live application with no performance penatly. I'm writing a Python that needed some profiling, and I found the "normal" techniques like the profile/cProfile module very lacking. Luckily, Mac OSX comes with DTrace and it even works with Python. The only snag is that it's hard to find how to use the darn thing. I finally figured it out, so I figured it pass on the knowledge.

So, here's how you use dtrace on your python application in Mac OSX:

1. Get DTraceToolkit.
2. Edit Python/py_cputime.d by replacing "function-entry" with "entry" and "function-return" with "exit".
3. Call "sudo dtrace -s Python/py_cputime.d"
4. Let it sit there a while and hit ctrl-c.
5. Enjoy the results

I can only assume you have to edit the file because of some difference between Solaris and OSX. You can try files other than py_cputime.d, but you might have to edit them too. Not all of them work, but most do.

The last thing to know is that you have to use the python that comes with OSX. A custom-built python doesn't seem to work.

Hope that helps!

41 comments

Labels: dtrace, osx, programming, python

Python seems to use a lot of memory. So what exactly is the overhead of each type of value? Short answer:

I measured these by running a simple program that loaded up 1,000,000 values in a list and then did time.sleep(1000). I ran that for different value types and then ran "top" to see how much memory was being used. I took that value, substracted the memory usage for a list of all the same value (14 bytes each), subtracted the value of a child value (usually an int, 24 bytes each), and then divided by 1,000,000. I'll include the code I ran at the end if you want to cut and paste. So what lessons do we learn from this?

• Python objects are very expensive at over 300 bytes each.
• Tuples have 1/5 as much overhead.
• Records are almost as good as tuples, even when a mixin is added.

So, if you want to have lots of values in memory without using lots of memory, use Record .

If you want to run the test for yourself, here's the code. Just comment out the "make_val" that you want to test.

import time
from Record import Record
class TupleClass(tuple):
 pass
class RecordClass(Record("val")):
 pass
class OldClass:
 def __init__(self, val):
 self.val = val
 def method(self):
 pass
class NewClass(object):
 def __init__(self, val):
 self.val = val
 def method(self):
 pass
class RecordWithOldClass(Record("val"), OldClass):
 pass
class RecordWithNewClass(Record("val"), NewClass):
 pass
make_val = lambda i : 1 #nothing (base overhead)
#make_val = lambda i : i 
#make_val = float 
#make_val = lambda i : (i,) 
#make_val = lambda i : [i] 
#make_val = lambda i : {i:i}
#make_val = TupleClass
#make_val = RecordClass
#make_val = OldClass
#make_val = NewClass
#make_val = RecordWithOldClass
#make_val = RecordWithNewClass
count = 1000000
lst = [make_val(i) for i in xrange(count)]
time.sleep(100000)

41 comments

Labels: programming, python

As I wrote previously, I'm a fan of message-passing concurrency. But to use it in python, I had to write my own infrastructure. It's far from perfect, but it's working for me. I've simplified it a bit and prepared some code to share with you.

The basic idea of my framework is to be and simple and easy to use as possible. There's no Erlang-style pattern matching or process linking. There isn't even any built-in error handling. But, there's a lot of support for the typical "react loop" style of message handling.

The architecture is very simple. There's one thread per actor. An actor is just an object you can send a message to. The actor receives the messages in the order they were sent. You always know the sender of the message; it's built right in. There's also "Bridge" that allows you to interact with actors from non-actor code.

The only tricky thing you'll see is a "handles" decorator. This is used to help you identify how you want an actor to handle a given message type. It helps you avoid re-creating a message loop and dispatcher yourself for every actor.

I've included a little example of how to use the framework. It obviously quite simple, but keep in mind that I used little more for the foundation of a rather complex file synchronization application. A little bit goes a long way.

So, here it is. Cut, paste, and run.

from threading import Thread, Event
from Queue import Queue, Empty
class IActor:
 pass
 # send(message, sender)
class HandlerRegistry(dict):
 # should be used as a decorator
 def __call__(self, typ):
 def register(func):
 self[typ] = func
 return func
 return register
OtherMessage = "Other Message"
class Stop(Exception):
 def __repr__(self):
 return "Stop()"
class Stopped:
 def __repr__(self):
 return "Stopped()"
class ActorNotStartedError(Exception):
 def __init__(self):
 Exception.__init__(self, "actor not started")
class Actor(IActor):
 @classmethod
 def spawn(cls, *args, **kargs):
 self = cls(*args, **kargs)
 self.mailbox = Mailbox()
 start_thread(target = self.act, as_daemon = True)
 return self
 def send(self, message, sender):
 if self.mailbox is None:
 raise ActorNotStartedError()
 else:
 self.mailbox.send(message, sender)
 def receive(self):
 if self.mailbox is None:
 raise ActorNotStartedError()
 else:
 return self.mailbox.receive()
 # override if necessary
 def act(self):
 self.handleMessages()
 handles = HandlerRegistry()
 @classmethod
 def makeHandles(*classes):
 return HandlerRegistry((typ, handler) for cls in classes for (typ, handler) in cls.handles.iteritems())
 def handleMessages(self):
 try:
 while True:
 message, sender = self.receive()
 self.handleMessageWithRegistry(message, sender)
 except Stop:
 pass
 def handleMessageWithRegistry(self, message, sender):
 registry = self.__class__.handles
 handler = registry.get(message.__class__) or registry.get(OtherMessage)
 if handler is not None:
 handler(self, message, sender)
 @handles(OtherMessage)
 def onOther(self, message, sender):
 pass
 @handles(Stop)
 def onStop(self, message, sender):
 sender.send(Stopped(), self)
 raise message
def start_thread(target, as_daemon, name = None):
 thread = Thread(target = target)
 if name:
 thread.setName(name)
 thread.setDaemon(as_daemon) 
 thread.start()
 return thread
class Mailbox:
 def __init__(self):
 self.mailbox = Queue()
 def send(self, message, sender):
 self.mailbox.put((message, sender), block = False)
 def receive(self, timeout = None):
 return self.mailbox.get(block = True, timeout = timeout)
class Bridge(IActor):
 def __init__(self):
 self.mailbox = Mailbox()
 def send(self, message, sender):
 self.mailbox.send(message, sender)
 def call(self, target, request, timeout, default = None):
 self.sendRequest(target, request)
 return self.receiveResponse(timeout, default)
 # targeted_requests can be an iterator
 def multiCall(self, targeted_requests, timeout, default = None):
 count = 0
 for target, request in targeted_requests:
 self.sendRequest(target, request)
 count += 1
 
 for _ in xrange(count):
 yield self.receiveResponse(timeout, default)
 def stop(self, actors, timeout):
 stop = Stop()
 return list(self.multiCall(((actor, stop) for actor in actors), timeout, default = None))
 def sendRequest(self, target, request):
 target.send(request, self)
 def receiveResponse(self, timeout, default):
 try:
 message, sender = self.mailbox.receive(timeout = timeout)
 return message
 except Empty:
 return default
 
if __name__ == "__main__":
 import time
 class GetInventory:
 pass
 class Task:
 def __init__(self, input, destination):
 self.input = input
 self.destination = destination
 class Worker(Actor):
 handles = Actor.makeHandles()
 def __init__(self, skill):
 self.skill = skill
 @handles(Task)
 def onTask(self, task, sender):
 output = self.skill(task.input)
 task.destination.send(output, self)
 class Warehouse(Actor):
 handles = Actor.makeHandles()
 def __init__(self):
 self.inventory = []
 @handles(GetInventory)
 def onGetInventory(self, message, sender):
 # copy the inventory to avoid anyone mutating it
 sender.send(list(self.inventory), self)
 
 @handles(OtherMessage)
 def onTaskResult(self, result, sender):
 self.inventory.append(result)
 worker = Worker.spawn(lambda x : x * 2)
 positives = Warehouse.spawn()
 negatives = Warehouse.spawn()
 bridge = Bridge()
 for val in [1, 2, 3, -2, -4, -6]:
 warehouse = positives if val>= 0 else negatives
 worker.send(Task(val, warehouse), sender = None)
 print bridge.call(positives, GetInventory(), 1.0) #should be [ 2, 4, 6]
 print bridge.call(negatives, GetInventory(), 1.0) #should be [-4, -8, -12]
 print bridge.stop([worker, positives, negatives], 1.0) #should be [Stopped(), Stopped(), Stopped()]
 
 class Start:
 def __init__(self, target):
 self.target = target
 class Ping:
 def __repr__(self):
 return "Ping()"
 class Pong:
 def __repr__(self):
 return "Pong()"
 class Pinger(Actor):
 handles = Actor.makeHandles()
 @handles(Start)
 def onStart(self, start, sender):
 start.target.send(Ping(), self)
 @handles(Pong)
 def onPong(self, pong, sender):
 print "-",
 sender.send(Ping(), self)
 
 class Ponger(Actor):
 handles = Actor.makeHandles()
 @handles(Ping)
 def onPing(self, ping, sender):
 print "+",
 sender.send(Pong(), self)
 # should print lots of +-+-+-
 pinger = Pinger.spawn()
 ponger = Ponger.spawn()
 pinger.send(Start(ponger), sender = None)
 time.sleep(0.1)
 bridge.stop([pinger, ponger], 1.0)

70 comments

Labels: actor, concurrency, message-passing, python

I'm working on a peer-to-peer file synchronization program. It's really concurrent and distributed, and it's forced me to learn a thing or two about the concurrency models that we use as programmers. Over the past few years, I've tried both the shared-state model common to C, C++, Java, C#, Python, etc, and the message-passing model unique to Erlang and Scala. In my experience, the message-passing model (aka Actor Model) is far superior to the shared-state model for writing distributed applications. After having used both extensively, I'd go so far as to say that for distributed programming, shared-state concurrency is upside down and backwards.

Here's my informal proof that message-passing concurrency is necessary in a distributed system:

1. Since the system in distributed, real shared state is impossible.
2. The only way for the distributed components of an application to communicate is by sending a message from one to another.
3. Everything else is an abstraction on top of message passing.

See a pattern?

Not only are all of these abstractions, but they are leaky abstractions. Just about all RPC (Remote Procedure Call) frameworks try to pretend that remote objects or local. But the facade is impossible to keep from leaking. Calls to a remote object might fail or take arbitrarily long. If you want to make the same call to two different remote nodes, those calls must be made synchronously and sequentially; in order to call them in parallel on the remote nodes, they most be called in parallel on the local node. If a call to a remote node triggers a call back to the local node, which may trigger a call to a third node, you end up with a huge spaghetti mess of calls and threads.

I've been down that road. It wasn't pretty. There is a better way.

I think AJAX has opened our eyes a bit. It's a lot closer to message-passing than it is to RPC. In a REST architecture, you "send" messages by POSTing to a URL and you "receive" messages by GETing a URL. All messages are clearly local copies that were serialized and deserialized from the remote data. There isn't any leaky abstraction of data or classes pretending to be in two places at once. Data, timeouts, and failures are in your face and you have to deal with them. So, AJAX is a lot less leaky.

But AJAX is far from perfect. I can't help but think of the Greenspun's Tenth Rule of Programming with a twist on distributed programming: "Any sufficiently complicated distributed platform contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of a message-passing system (Erlang)". Once you get message-passing in your head, you can't help but think of AJAX in that way.

I've been down a better road. It was much more pleasant.

About six months ago, I rewrote major portions of our application with message-passing concurrency. I took a long time. It was tricky. It hurt my head. But it worked. It's a success. It's capable of things that the shared-state system could never do.

Having done it, I can emphatically say that if I could start all over, I would go with message-passing. Most of the work was building the infrastructure and wrapping my head around a new way of thinking. But now that I've done both of those, I've paid the costs and I'm reaping the rewards. We're moving the application in directions that would have been nearly in possible with the old concurrency model.

In my experience, message-passing concurrency is the best way to write distributed applications. But it isn't an easy road to go down. Support for it just isn't there in most programming languages and environments. So far, Erlang has been the pioneer. I would humbly agree that the way I've implemented message-passing in Python, compared to Erlang, looks like an ad-hoc, bug-ridden half-implementation. But for various reasons, I can't use Erlang. I'm hoping for someone to create Erlang++ or E# or Eython or something that combines the concurrency model of Erlang with a modern programming language. Until then, I'll just keep on cobbling together what I can onto the programming language I happen to be using.

More on that in another article.

37 comments

Labels: actor, concurrency, erlang, message-passing, programming, python, shareever

I'm a huge fan of the Actor Model . I think that for most applications, it's the best way to do concurrency. As CPUs get more cores, concurrency becomes more important for programmers, and I think the Actor Model will become more important, too.

But, sometimes you need something more light-weight for handling "events". For example, imagine you have some code listening for file changes in a particular directory. What you'd like to do is make an "event" that is "fired" whenever a file change is detected. When fired, there may be a "handler" or "listener" which is notified of the event. That "handler" is ultimately just some code which is executed when the event occurs.

A while ago, I wanted an event system like this for Python. I didn't see anything builtin or any library available, so I decided to write my own. I'd like to share what I created with you.

But first, I want to follow an example through other programming languages to give you an idea of what I was trying to accomplish and how it compares with what's out there. After that, I'll give you my implemenation in Python. Our example will be listening for changes on the file system. We want to keep the "watcher" code decoupled from the rest of the code, so we use events.

The best implementation of events that I've used is in C#, so we'll start there. In C# 1.0, our file watcher would looks something like this:

public delegate void FileChangeHandler(string source_path);
class FileWatcher
{
 public event FileChangeHandler FileChanged;
 public void WatchForChanges()
 {
 ...
 if(FileChanged != null)
 {
 FileChanged(source_path);
 }
 ...
 }
}
class FileChangeLogger
{
 public void OnFileChanged(string source_path)
 {
 Console.WriteLine(String.Format("{0} changed.", source_path));
 }
}
watcher = FileWatcher();
logger = FileChangeLogger();
watcher.FileChanged += new FileChangeHandler(logger.OnFileChanged);
watcher.WatchForChanges();

watcher.FileChanged += delegate(string source_path)
{
 Console.WriteLine(String.Format("{0} changed.", source_path));
}

watcher.FileChanged += (source_path => Console.WriteLine(String.Format("{0} changed.", source_path)));

Actually, there is one thing. If there's no handler registered with the event, calling "FileChanged()" will blow up because it sees FileChanged == null until a handler is registered. This means that you have to write "if(Event != null){Event(...):}" every single time you fire the event. Every single time. If you forget, your code will seem to work fine until there's no handler, in which case it will blow up and you'll smack your forhead because you forgot that you have to repeat that line of code every single time you fire an event. I really mean every single time. It's by far the worst wart on an otherwise elgant system. I have no idea why the designers of C# thought this was a good idea. When would you ever want to fire and event and have it blow up in your face?

Anyway, let's try a different programming language, perhaps Java. It has the worst implementation of events I've ever seen. Here's our FileWatcher example:

...

...

Ok, nevermind, I don't have the heart. I can imagine the code full of IListeners, and implementations, and keeping an array of them, and iterating over them, etc, and I just can't do it. I got seriously upset at one useless line in C#. In Java, it's at least 10 times worse. If you really have the stomach for it, go look at http://java.sun.com/docs/books/tutorial/uiswing/events/index.html. To me, it appears that in Java, events are one giant hack around the lack of first-class functions. If Java had first-class functions, none of that nonsense would be necessary.

Now that we've seen a good implementation of events in C# and avoided a bad one in Java, let's make one for Python. I'd rather it be like the C# event system, so let's see what our example would look like:

from Event import Event
class FileWatcher:
 def __init__(self):
 self.fileChanged = Event()
 def watchFiles(self):
 ...
 self.fileChanged(source_path)
 ...
def log_file_change(source_path):
 print "%r changed." % (source_path,)
watcher = FileWatcher()
watcher.fileChanged += log_file_change

class Event(IEvent):
 def __init__(self):
 self.handlers = set()
 def handle(self, handler):
 self.handler.add(handler)
 return self
 def unhandle(self, handler):
 try:
 self.handlers.remove(handler)
 except:
 raise ValueError("Handler is not handling this event, so cannot unhandle it.")
 return self
 def fire(self, *args, **kargs):
 for handler in self.handlers:
 handler(*args, **kargs)
 def getHandlerCount(self):
 return len(self.handlers)
 __iadd__ = handle
 __isub__ = unhandle
 __call__ = fire
 __len__ = getHandlerCount

For all of you how like full examples that you can cut and paste, here is one that you can run. Enjoy!

class Event:
 def __init__(self):
 self.handlers = set()
 def handle(self, handler):
 self.handlers.add(handler)
 return self
 def unhandle(self, handler):
 try:
 self.handlers.remove(handler)
 except:
 raise ValueError("Handler is not handling this event, so cannot unhandle it.")
 return self
 def fire(self, *args, **kargs):
 for handler in self.handlers:
 handler(*args, **kargs)
 def getHandlerCount(self):
 return len(self.handlers)
 __iadd__ = handle
 __isub__ = unhandle
 __call__ = fire
 __len__ = getHandlerCount
class MockFileWatcher:
 def __init__(self):
 self.fileChanged = Event()
 def watchFiles(self):
 source_path = "foo"
 self.fileChanged(source_path)
def log_file_change(source_path):
 print "%r changed." % (source_path,)
def log_file_change2(source_path):
 print "%r changed!" % (source_path,)
watcher = MockFileWatcher()
watcher.fileChanged += log_file_change2
watcher.fileChanged += log_file_change
watcher.fileChanged -= log_file_change2
watcher.watchFiles()

148 comments

Labels: events, programming, python

Even though Pysec (and functional programming in python in general) turned out to be 2-3x slower, monadic parsing is still great for certain tasks. After I wrote about Pysec the first time, I received comments regarding pyparsing, which is a great parsing library that looks very similar. Today, I'd like to show you a very simple example where monadic parsing really shines above all other parsing techniques, including pyparsing. This is a real-world need that I had, not just an academic thought-experiment.

The situation is that I'm writing a peer-to-peer file synchronizer and I need to serialize binary data in an efficient way. I've choosen to use what I call "sized binary", which is basically netstrings without the comma or bencode's byte string. The byte-string "ABC", for example, would be encoded as "3:ABC", or "Hello World!" would be "12:Hello World!". This is very efficient because "ABC" or "Hello World!" can be any bytes \x00-\xFF, without any sort of encoding or decoding like uuencode.

Stop and think for a minute how you would define a grammer to parse "3:ABC". It's so simple, right? Well, try and write a grammar for it. Try using BNF, EBNF, yacc/bison, pyparsing, SimpleParse, or any parsing libarary you know of, in any programming language. If you manage, please write me an email and let me know how you did it, because I'm not so sure it's even possible. Maybe it is in the Perl6 grammars; they're throwing the kitchen sink into that thing :). The best I've seen is that the creator of pyparsing hacked a grammar object to change how it parses the "ABC" part after a different object parsed the "3" part. This basically uses the grammar object as a global variable. It works in a single-core world, but it won't work in the many-core world we're headed for.

But now you're getting bored with me because it's silly ringing my hands over such a simple format. I bet you could parse this format in just 4 lines of code:

def parse_sized_binary(stream):
 size_bytes, stream = stream.readUntil(":")
 size = int(size_bytes)
 bytes, stream = stream.read(size)
 return bytes, stream

Congratulations, you just invented monadic parsing. The function you wrote, parse_sized_binary, of the form stream -> (bytes, stream), is a Parser Monad. Monadic parsing is just combining lots of these little parsers together. And so, it's incredibly easy to insert arbitrary parsing code, like parse_sized_binary, into any parser.

As a complete example, using Pysec, here's a full parser for a language just like bencode but with support for floats and unicode. Notice that our parse_size_binary is renamed to bencode_sized and is given a more functional definition.

from Pysec import Stub, until, lift, read, many_until, branch
bencode_any = Stub()
bencode_sized = until(":")>> lift(int)>> read
bencode_unsized = until("e")
bencode_list = many_until(bencode_any, "e")
bencode_any.set(branch({"s" : bencode_sized,
 "u" : bencode_sized>> lift(lambda bytes : bytes.decode("utf8")),
 "i" : bencode_unsized>> lift(int),
 "f" : bencode_unsized>> lift(float),
 "l" : bencode_list,
 "d" : bencode_list>> lift(dict)}))

63 comments

Labels: monad, parsing, programming, python

If you've read the last few posts, you know that I choose to use monadic parsing for some application code I am writing. At an abstract level, it turned out beautifully. I was able to write the parser very elgantly and compactly despite the serialization format having some unique requirements. But at a practical level, it failed pretty miserably. It was horribly slow. With a deadline looming, I had to abandon my monadic parser and go back to using an older serialization format. But not content to give up so easily, I decided to figure out why are my monads so slow? I hope that my investigation may be of help to you if you choose to use similar techniques in your code.

First, I tried running a profiler like cProfile. While such profilers normally work quite well, they don't work so well with lots of first-class functions. And since monadic code is full of first-class functions, the profiler didn't give much valuable information.

So, I had to do optimizing the "old fashioned" way. I wrote a benchmark and ran both of my serializers against it. To start, I had two data points: one in traditional imperitave code and one in fully monadic code, and this is what I got:

imperative: 0.465 seconds
monadic: 3.893 seconds

imperative: 0.465 seconds
functional with stream: 1.018 seconds
almost monadic with state: 2.450 seconds
monadic: 3.893 seconds

imperative: 0.465 seconds
functional with stream: 1.018 seconds
almost monadic with state: 1.098 seconds
monadic: 1.283 seconds

That's a nice 3x improvement. What things were I able to do? By far the biggest cost that I was able to eliminate was object creation. I flattened two layers of abstraction into one, and thus split the number of objects created in half. The second thing I did was I created a "read until" operation that could be used more efficiently in the "grammar" of the parser. This is a form of pushing performance-critical code down the layers of abstraction. Finally, I didn't used decorators, for some often-called functions.

In the end, it looks like monadic code is about 2-3x slower in Python. Almost all of that is actually the result of just doing things in a functional/immutable way. In particular, creating data structures appears to be the main bottleneck. In functional languagues, these types of operations are very common and optimized heavily, and so are typically very fast. It looks like it's not the same in Python. Just like you have to avoid recursion because there's no tail recursion, it looks like you have to avoid a functional/immutable coding style if you care about performance because object creation is so slow. On the other hand, if you don't mind the peformance hit, it makes the code much more elegant, just like recursion usually does.

One thing of interest is that there is essentially no performance penatly for using monads over using a functional/immutable code style. The 20% penatly seen between "almost monadic" and "monadic" is only because I'm wrapping the monad in a Parser class which allows nice operator overloading.

Here's a summary of what you can do to speed up any functional/immutable-style code, including monadic code when writing in Python:

• Make object creation as fast as possible. Don't do anything fancy in __init__.
• Use as few layers of abstraction as possible, especially when there is an object created in each layer.
• Push common or expensive operations down the layers of abstaction, especially if it avoids creating objects.
• Avoid using decorators for heavily used functions.
• Don't use wrapper classes if you don't have to.

As a final thought, I'd like to mention that while there's currently a substantial performance penalty for using immutable data structures, that style is going to become increasingly important as we enter the many-core era. No matter what style of concurrency you like, immutable data is always easier to work with when concurrency is involved. Concurrency and mutable data are just a bad combo. I think that it's going to be very important for language designers to address this when working on the peformance of their languages. I certainly hope future versions Python are much faster with immutable data. If they are, then the peformance penatly of using Monads will almost disappear.

27 comments

Labels: monad, parsing, programming, python

Update: It turns out that there's a similar technique being used by pyparsing. I hadn't seen it before and when I first saw it I thought had reinvted the wheel and wasted my time. But upon further inspection, Pysec does a few things a much better than pyparsing, which happen to be the exact things that I need. There's no coincedence, of course, that Pysec matches my needs well. I'll be covering this in more detail in a future article.

Update 2: I got @do syntax to work! Again, stay tuned for another article on how.

I've talked about monads in the past, but I never really covered what purpose they serve. I covered the "how" in Python and Ruby, but I doubt I'll ever full cover the "why" because it's simply too big of a subject. But today, I'd like to share with you one example of how monads are useful. In fact, it's the example that motivated me to do all of the monad stuff in the first place: parsing.

Parsing is a topic that's been around pretty much forever in computer science and most people thing it's pretty much "solved". My experience is that we've still got a long way to go. Specifically, I'm writing an application with lots of distributed concurrency, which requires lots of data serialization and deserialization (aka parsing). There are very few good serialization libraries out there, and I've been through three or four versions of various techniques. Finally, I think I have found a parsing technique that works well: monadic combinatoric parsing. And it's in Python.

What the heck does that mean? "monadic" means we're using monads. "combinatoric" means we can take monad parsers and combine them to make new monad parsers, which is extremly powerful. I call it Pysec. The design is a copy of Parsec brought to Python. Notice how I said "design"; I didn't bother looking at any of their code; The design described on their web page was good enough guidance for me. But, I'm sure that their implementation is WAY better than mine. If you want to see real monadic parsing, look at Parsec. If you're interested in monadic parsing for Python, keep reading.

Here's an example of Pysec for parsing a subset of JSON:

from Pysec import Parser, choice, quoted_chars, group_chars, option_chars, digits, between, pair, spaces, match, quoted_collection
# json_choices is a hack to get around mutual recursion 
# a json is value is one of text, number, mapping, and collection
# text is any characters between quotes
# a number is like the regular expression -?[0-9]+(\.[0-9]+)?
# "parser>> Parser.lift(func)" means "pass the parsed value into func and return a new Parser"
# quoted_collection(start, space, inner, joiner, end)
# means "a list of inner separated by joiner surrounded by start and end"
# we have to put a lot of "spaces" in since JSON allows lot of optional whitespace
json_choices = []
json = choice(json_choices)
text = quoted_chars("'", "'")
number = group_chars([option_chars(["-"]), digits, option_chars([".", digits])])>> Parser.lift(float)
joiner = between(spaces, match(","), spaces)
mapping_pair = pair(text, spaces & match(":") & spaces & json)
collection = quoted_collection("[", spaces, json, joiner, "]")>> Parser.lift(list)
mapping = quoted_collection("{", spaces, mapping_pair, joiner, "}")>> Parser.lift(dict)
json_choices.extend([text, number, mapping, collection])
print json.parseString("{'a' : -1.0, 'b' : 2.0, 'z' : {'c' : [1.0, [2.0, [3.0]]]}}")

Like most monadic or functional code, it's pretty dense, so don't feel bad if you go cross-eyed looking at it the first time. Realize that most of the code is building a Parser monad called "json", which parses the test string at the end. I tried to comment each individual part to explain what's going on.

You may be thinking "why would I want to write code like this?". One response is to look at the code: it's the bulk of JSON parsing in 15 lines that look like a grammar definition! Another response I can give is a challange: go write a parser to parse that string and then compare your code to this code. Which is shorter? Which is easier to read? Which is more elegant? While in college, I had a team project to write a compiler for a subset of Pascal. We were smart enough to use Python, but dumb enough to use Yacc and Flex. I'm sure the parser portion was pretty fast, but it was incredibly painful to get it right. Once we did, we dared not touch it for fear of breaking it. I really wish I had Parse/Pysec back then (ok, Parsec was around back then, but I hadn't even heard of Haskell or monads).

But monadic combinatoric parsing isn't just about making your code look like a grammar definition. It makes it possible to combine parsers in incredibly flexible ways. For example, let's say that on a differnt project, you wrote a simplified CSV parser for numbers like this one:

def line(cell):
 return sep_end_by(cell, match(","))
def csv(cell):
 return sep_end_by(line(cell), match("\n"))
print csv(number).parseString("1,2,3\n4,5,6")

And now you realize you'd really like to put whole JSON values in your simplified CSV. In other words, you want to combine the CVS and JSON parsers. I think that you'll find that doing so really isn't as easy as it sounds. Imagine trying to combine two Yacc grammars. It hurts just thinking about that. Luckily, monadic combinatoric parsers make this incredibly easy:

print csv(json).parseString("{'a' : 'A'},[1, 2, 3],'zzz'\n-1.0,2.0,-3.0")

While this is a slighly contrived example, you must understand that with this technique you can combine any two parsers in a similar fasion. I don't know about you, but that really feels right to me. I haven't seen any parsing techniques as elegant as that.

Everything it's perfect of course, especially since making this work in Python is a bit of a hack. Here are some downsides to this approach:

• It's hard to debug when you do something wrong.
• It's annoying to import so many things from Pysec.
• You have to hack around mutual recursion of values in a strict language like python.
• There's probably a performance hit.

Most of these can be either fixed or worked around, though, so I think long-term monadic parsing is good bet. I'd like to see what you can do with it or to make it better.

I know how much you all like a working example, so here's some code that you can just cut, paste, and run (in Python 2.5; older versions of Python may require some tweaking). Please ignore the top half. It's mostly stuff I've covered in other articles, like Immutable Records and monad base classes. The meat starts where it says "Parser Monad".

I'd like to talk about it in more detail, but I'll save that for another article. For now, please play around with it and see what you think.

##### Base Libraries included here for convenience ###########
def Record(*props):
 class cls(RecordBase):
 pass
 cls.setProps(props)
 return cls
class RecordBase(tuple):
 PROPS = ()
 def __new__(cls, *values):
 if cls.prepare != RecordBase.prepare:
 values = cls.prepare(*values)
 return cls.fromValues(values)
 @classmethod
 def fromValues(cls, values):
 return tuple.__new__(cls, values)
 def __repr__(self):
 return self.__class__.__name__ + tuple.__repr__(self)
 ## overridable
 @classmethod
 def prepare(cls, *args):
 return args
 ## setting up getters and setters
 @classmethod
 def setProps(cls, props):
 for index, prop in enumerate(props):
 cls.setProp(index, prop)
 cls.PROPS = props
 @classmethod
 def setProp(cls, index, prop):
 getter_name = prop
 setter_name = "set" + prop[0].upper() + prop[1:]
 setattr(cls, getter_name, cls.makeGetter(index, prop))
 setattr(cls, setter_name, cls.makeSetter(index, prop))
 @classmethod
 def makeGetter(cls, index, prop):
 return property(fget = lambda self : self[index])
 @classmethod
 def makeSetter(cls, index, prop):
 def setter(self, value):
 values = (value if current_index == index
 else current_value
 for current_index, current_value
 in enumerate(self))
 return self.fromValues(values)
 return setter
class ByteStream(Record("bytes", "index")):
 @classmethod
 def prepare(cls, bytes, index = 0):
 return (bytes, index)
 def get(self, count):
 start = self.index
 end = start + count
 bytes = self.bytes[start : end]
 return bytes, (self.setIndex(end) if bytes else self)
def make_decorator(func, *dec_args):
 def decorator(undecorated):
 def decorated(*args, **kargs):
 return func(undecorated, args, kargs, *dec_args) 
 
 decorated.__name__ = undecorated.__name__
 return decorated
 
 decorator.__name__ = func.__name__
 return decorator
decorator = make_decorator
class Monad:
 ## Must be overridden
 def bind(self, func):
 raise NotImplementedError
 @classmethod
 def unit(cls, val):
 raise NotImplementedError
 @classmethod
 def lift(cls, func):
 return (lambda val : cls.unit(func(val)))
 ## useful defaults that should probably NOT be overridden
 def __rshift__(self, bindee):
 return self.bind(bindee)
 def __and__(self, monad):
 return self.shove(monad)
 
 ## could be overridden if useful or if more efficient
 def shove(self, monad):
 return self.bind(lambda _ : monad)
class StateChanger(Record("changer", "bindees"), Monad):
 @classmethod
 def prepare(cls, changer, bindees = ()):
 return (changer, bindees)
 # binding can be slow since it happens at bind time rather than at run time
 def bind(self, bindee):
 return self.setBindees(self.bindees + (bindee,))
 def __call__(self, state):
 return self.run(state)
 def run(self, state0):
 value, state = self.changer(state0) if callable(self.changer) else self.changer
 state = state0 if state is None else state
 for bindee in self.bindees:
 value, state = bindee(value).run(state)
 return (value, state)
 @classmethod
 def unit(cls, value):
 return cls((value, None))
######## Parser Monad ###########
class ParserState(Record("stream", "position")):
 @classmethod
 def prepare(cls, stream, position = 0):
 return (stream, position)
 def read(self, count):
 collection, stream = self.stream.get(count)
 return collection, self.fromValues((stream, self.position + count))
class Parser(StateChanger):
 def parseString(self, bytes):
 return self.parseStream(ByteStream(bytes))
 
 def parseStream(self, stream):
 state = ParserState(stream)
 value, state = self.run(state)
 return value
class ParseFailed(Exception):
 def __init__(self, message, state):
 self.message = message
 self.state = state
 Exception.__init__(self, message)
@decorator
def parser(func, func_args, func_kargs):
 def changer(state):
 return func(state, *func_args, **func_kargs)
 changer.__name__ = func.__name__
 return Parser(changer)
##### combinatoric functions #########
@parser
def tokens(state0, count, process):
 tokens, state1 = state0.read(count)
 passed, value = process(tokens)
 if passed:
 return (value, state1)
 else:
 raise ParseFailed(value, state0)
 
def read(count):
 return tokens(count, lambda values : (True, values))
@parser
def skip(state0, parser):
 value, state1 = parser(state0)
 return (None, state1)
@parser
def option(state, default_value, parser):
 try:
 return parser(state)
 except ParseFailed, failure:
 if failure.state == state:
 return (default_value, state)
 else:
 raise
 
@parser
def choice(state, parsers):
 for parser in parsers:
 try:
 return parser(state)
 except ParseFailed, failure:
 if failure.state != state:
 raise failure
 raise ParseFailed("no choices were found", state)
@parser
def match(state0, expected):
 actual, state1 = read(len(expected))(state0)
 if actual == expected:
 return actual, state1
 else:
 raise ParseFailed("expected %r" % (expected,), state0)
def between(before, inner, after):
 return before & inner>> (lambda value : after & Parser.unit(value))
def quoted(before, inner, after):
 return between(match(before), inner, match(after))
def quoted_collection(start, space, inner, joiner, end):
 return quoted(start, space & sep_end_by(inner, joiner), end)
@parser
def many(state, parser, min_count = 0):
 values = []
 try:
 while True:
 value, state = parser(state)
 values.append(value)
 except ParseFailed:
 if len(values) < min_count: raise return values, state @parser def group(state, parsers): values = [] for parser in parsers: value, state = parser(state) values.append(value) return values, state def pair(parser1, parser2): # return group((parser1, parser2)) return parser1>> (lambda value1 : parser2>> (lambda value2 : Parser.unit((value1, value2))))
@parser
def skip_many(state, parser):
 try:
 while True:
 value, state = parser(state)
 except ParseFailed:
 return (None, state)
def skip_before(before, parser):
 return skip(before) & parser
@parser
def skip_after(state0, parser, after):
 value, state1 = parser(state0)
 _, state2 = after(state1)
 return value, state2
@parser
def option_many(state0, first, repeated, min_count = 0):
 try:
 first_value, state1 = first(state0)
 except ParseFailed:
 if min_count> 0:
 raise
 else:
 return [], state0
 else:
 values, state2 = many(repeated, min_count-1)(state1)
 values.insert(0, first_value)
 return values, state2
# parser separated and ended by sep
def end_by(parser, sep_parser, min_count = 0):
 return many(skip_after(parser, sep_parser), min_count)
# parser separated by sep
def sep_by(parser, sep_parser, min_count = 0):
 return option_many(parser, skip_before(sep_parser, parser), min_count)
 
# parser separated and optionally ended by sep
def sep_end_by(parser, sep_parser, min_count = 0):
 return skip_after(sep_by(parser, sep_parser, min_count), option(None, sep_parser))
##### char-specific parsing ###########
def satisfy(name, passes):
 return tokens(1, lambda char : (True, char) if passes(char) else (False, "not " + name))
def one_of(chars):
 char_set = frozenset(chars)
 return satisfy("one of %r" % chars, lambda char : char in char_set)
def none_of(chars):
 char_set = frozenset(chars)
 return satisfy("not one of %r" % chars, lambda char : char and char not in char_set)
def maybe_match_parser(parser):
 return match(parser) if isinstance(parser, str) else parser
def maybe_match_parsers(parsers):
 return tuple(maybe_match_parser(parser) for parser in parsers)
def many_chars(parser, min_count = 0):
 return join_chars(many(parser, min_count))
def option_chars(parsers):
 return option("", group_chars(parsers))
def group_chars(parsers):
 return join_chars(group(maybe_match_parsers(parsers)))
 #return join_chars(group(parsers))
def join_chars(parser):
 return parser>> Parser.lift("".join)
def while_one_of(chars, min_count = 0):
 return many_chars(one_of(chars), min_count)
def until_one_of(chars, min_count = 0):
 return many_chars(none_of(chars), min_count)
def char_range(begin, end):
 return "".join(chr(num) for num in xrange(ord(begin), ord(end)))
def quoted_chars(start, end):
 assert len(end) == 1, "end string must be exactly 1 character"
 return quoted(start, many_chars(none_of(end)), end)
digit = one_of(char_range("0", "9"))
digits = many_chars(digit, min_count = 1)
space = one_of(" \v\f\t\r\n")
spaces = skip_many(space)
############# simplified JSON ########################
#from Pysec import Parser, choice, quoted_chars, group_chars, option_chars, digits, between, pair, spaces, match, quoted_collection, sep_end_by
#HACK: json_choices is used to get around mutual recursion 
#a json is value is one of text, number, mapping, and collection, which we define later 
json_choices = []
json = choice(json_choices)
#text is any characters between quotes
text = quoted_chars("'", "'")
#sort of like the regular expression -?[0-9]+(\.[0-9]+)?
#in case you're unfamiliar with monads, "parser>> Parser.lift(func)" means "pass the parsed value into func but give me a new Parser back"
number = group_chars([option_chars(["-"]), digits, option_chars([".", digits])])>> Parser.lift(float)
#quoted_collection(start, space, inner, joiner, end) means "a list of inner separated by joiner surrounded by start and end"
#also, we have to put a lot of spaces in there since JSON allows lot of optional whitespace
joiner = between(spaces, match(","), spaces)
mapping_pair = pair(text, spaces & match(":") & spaces & json)
collection = quoted_collection("[", spaces, json, joiner, "]")>> Parser.lift(list)
mapping = quoted_collection("{", spaces, mapping_pair, joiner, "}")>> Parser.lift(dict)
#HACK: finish the work around mutual recursion
json_choices.extend([text, number, mapping, collection])
############# simplified CSV ########################
def line(cell):
 return sep_end_by(cell, match(","))
def csv(cell):
 return sep_end_by(line(cell), match("\n"))
############# testing ####################
print json.parseString("{'a' : -1.0, 'b' : 2.0, 'z' : {'c' : [1.0, [2.0, [3.0]]]}}")
print csv(number).parseString("1,2,3\n4,5,6")
print csv(json).parseString("{'a' : 'A'},[1, 2, 3],'zzz'\n-1.0,2.0,-3.0")

237 comments

Labels: monad, parsing, python