Tales of a Fourth Grade Nothing

Sure enough, when I profiled the base version using a fixed configuration, I found that it was losing most of its time to a series of deepcopy() calls. I changed the internal data structures to use a dictionary instead of a more complex set of arrays and, presto, the run time went down from 7.55s to 1.76s and the function call count went down from 398,359 to 53,678.

But when I re-profiled, I found a couple of other nasties: an N by N array that was being needlessly regenerated for every loop trip and a whole host of calls to has_key(). After adding caching to the main loop to prevent recalculation and replacing all the has_keys() with try ... execpt KeyError ... constructs, I managed to get the time down to 0.97s and a mere 11,236 function calls.

And here's proof of my success: a plot showing how the raw and optimised versions of the program scale as the number of items increases:

So it looks like the big wins were, in order of effectiveness: (a) to use a more efficient algorithm and data structures; (b) to replace has_keys() with exceptions in order to avoid the overhead of the extra subroutine calls and to exploit the (relatively) fast performance of exception handling; (c) to avoid unnecessary work by caching results, trading memory for CPU. Of these, (a) and (c) were obvious, while (b) was only apparent after a little bit of experimentation with the profiler.

( Adventure text... )

Astute readers will note that I've neglected to include any actual adventure elements. Well, fear not. In version 0.2, I plan to make it possible to water the potted plants and obtain free coffee from the vending machines. It's going to be a right roller coaster of a game once it's finished...

I've got an object called a Request. This represents a single instance of job in the batch system. Each Request has properties such as queue and state which change depending on what the batch system is doing and which need to be kept up to date. Rather than simply caching the static data in a struct I've chosen to solve the problem by creating a routine that queries the batch server every time a __getattr__ is called on the object.

Essentially, I set up a very simple structure with a pair of buffers:

  typedef struct {
    int int_buffer;
    char *char_buffer;
  } Request;

  void Request_query(Request *r, int property);

  %extend Request {

    void query(int property); 

  }

  %pythoncode {

  get_attrs = { "queue": ( QUEUE, "char_buffer"),
                "state": ( STATE, "int_buffer") }

  def _Request_getattr(self, class_type, name):
    try:
      self.query(get_attrs[name][0])
      name = get_attrs[name][1]
    except KeyError:
      pass

    return _swig_getattr(self, class_type, name)

  Request.__getattr__ = lambda self, name: \
    _Request_getattr(self, Request, name)

  }

The upshot of this is that any attempt to get a property will result in the dictionary get_attrs being checked for an entry. If an entry is found, the appropriate buffers are updated using query() and the value of name is changed to point to the buffer. Once this work has been done, the builtin _swig_getattr() routine is called as normal to extract a value from the object — either the buffer set by query() or, in the case of a simple static value which lacks a dictionary entry, the contents of the variable in the struct.

A similar method can be used to reverse the process, allowing changes to properties to be passed back to the API by replacing __setattr__. For example:

  %pythoncode {
  
  def _Request_setattr(self, class_type, name, value):
    if name == "queue":
      self.setQueue(value)
    else:
      _swig_setattr(self, class_type, name, value)

  Request.__setattr__ = lambda self, name, value: \
    _Request_getattr(self, Request, name, value)

  }

Whilst none of this seems to be terribly well documented, it's possible to grok how it's supposed to work by skimming through the SWIG generated module file.

for line in open("input").readlines(): if m = re.match("foo(\\d+)", line): print m.group(1) elif m = re.match("bar([a-z]+)", line): print m.group(1)