Python: Removing items from a list

While sitting on a plane from Santa Clara to Austin (more on that in another post), I finally sat down and wrote simple test program to determine "what's the fastest way to remove a known item from a list in Python?"

Python has some surprising performance behaviors, and removing items from a list is no exception. I came up with five methods that I thought someone might implement for removing stuff from a list, along with a bit of glue code to time everything (I used the timeit module for that, hooray for 'coming with batteries').

I've posted the code in a file, (you can get that here), including the removal functions. I'll assume if you keep reading that you've looked at the source code. We have to have some basis for communication, after all.

Here are the results of running the module on my MacBook Air, while sitting on the airplane. Your mileage may vary.

McJohn$ python listremove.py 1024 4096
name            min      max      mean     median   
ghetto_remove   0.011734 0.024060 0.015157 0.014703 
repeated_remove 0.004583 0.025112 0.012059 0.010892 
comp_remove     0.009502 0.020047 0.012323 0.011900 
old_remove      0.017689 0.035935 0.022772 0.022382 
hard_remove     0.005304 0.014384 0.007783 0.007205 

What's surprising to me about this isn't that the 'hard remove' is the fastest (on average), but that it's worst case is better than the average runtime for most of the other algorithms--except for the 'repeated remove' best case, which is staggeringly good. That's actually quite shocking in and of itself, but I suspect that it would get worse if there were more collisions in the list itsef. We can test this by reducing the number of random elements allowable in the list while maintaining the list length. Here are the results for that trial:

McJohn$ python listremove.py 16 4096
name            min      max      mean     median   
ghetto_remove   0.139576 0.214912 0.175577 0.177581 
repeated_remove 2.597167 4.307188 3.578634 3.592269 
comp_remove     0.090875 0.144086 0.116044 0.116585 
old_remove      0.168973 0.239456 0.206943 0.207778 
hard_remove     0.399565 0.668813 0.534192 0.542308 

It turns out that this approach makes the repeated_remove case staggeringly bad, causing a massive increase in runtime. I wasn't actually prepared for it to get this bad (I was fairly certain there was a hang in my code somewhere, the perf tanked so badly). Unfortunately, that wasn't the case--it was just that repeated_remove gets really slow in the case of massive collisions. That shouldn't be too surprising, though. In the face of an element appearing many times in the list, the repeated_remove code has an O(N^2) worst case performance. It effectively could have to traverse the list up to N times (where N is also the length of the list). Of course, each traversal in that case should be very fast, averaging 1 lookup before finding the element. Something definitely seems to be going wrong, though.

Also a bit surprising in this case is that the hard_remove performance gets quite bad. In fact, only the 'comp_remove' seems to get good performance

Python: Surprising performance characteristics

There are some interesting performance properties of python. One of those, that often surprises newbies to python and veterans alike is the relatively (okay very) poor performance of numbers, versus the excellent performance of lists.

This was actually something jra101 and I stumbled across at work, when implementing an xml writer (as it turns out, python doesn't already have one, which is a bit surprising). In any event, we discovered this fact while attempting to optimize our writer. Initially, we had an API that looked something like this:

class XMLWriter(object):
  def openTag(self, tagName, attributes=None):
    self._tagStack.append(tagName)
    # other stuff

  def closeTag(self, tagName):
    assert self._tagStack[-1] == tagName
    del self._tagStack[-1]
    # other stuff

Without profiling, jra and I both decided that we could optimize this at the expense of a little safety by replacing the safety code with something a little less safe. This also made it so we didn't have to make sure the code closing the tag knew who had opened it. That version looked something like this:

class XMLWriter(object):
  def openTag(self, tagName, attributes=None):
    self._openTagCount += 1
    # other stuff

  def closeTag(self, tagName):
    assert self._openTagCount > 1
    self._openTagCount -= 1
    # other stuff

Shockingly, this version wasn't any faster than the inital version! After I thought about this for a bit, I decided that this was actually intuitive with a bit of python knowledge, although it was a little scary. In Python, everything is an object. Everything. Everything. Even numbers. Moreover, python integers have infinite precision. The code below works correctly (although slowly, as you might expect):

pow(pow(2,136), 2)

In order to support this, python cannot take optimizations for numbers that would happen in C or C++. Moreover, python can never--even in the case of simple integers--treat integers as integers. It has to evaluate the mathemetical operation, determine the result, determine whether the result fits in the old type, then possibly create a new value, and finally overwrite the old value with the new. That's a lot of work, compared to what happens in (for example) C. In C, an add operation corresponds to a single ASM instruction. Hard to compete with.

Meanwhile, list code is almost universally dispatched to a C library that is exceedingly fast and efficient. The morale of the story is one that Olivier has covered in "Mutable Conclusions" before: profile early, profile often.

The cheapest code is the code that doesn't exist

We have a common idiom in software: the fastest code is the code that doesn't execute. For non-nerds, this basically means that you want to structure your code so that you don't execute unnecessary computations.

As a corollary, I'll propose that every line of code you write (or every line of code you generate through C++ template facilities) is a line that costs you something in maintenance. Thus, the cheapest code is the code that doesn't exist.

It seems obvious, and it should be. The problem (imho) is that programmers are drinking the kool-aid. There's this myth that programming is a really hard, complicated problem. For some classes of programming, it's true. It is hard. Most programming is not hard, though. You think about a problem, you think about how you would sove the problem by hand and you speak another language to solve the problem in a more automatic way.

Unfortunately, it seems that oftentimes programmers overthink problems. They solve problems that don't exist or they try to build scaffolding around an otherwise simple problem. And that results in an unmaintainable blob. This is often done in the name of 'code reuse.' Debunking the notion that code reuse is always a good idea is a subject for another post, though.

Cheers.

Python: Enforcing Interface Requirements

I write a moderate amount of Python code for work. Not necessarily as much as I'd like, but that's a topic for another post.

A short while back, one of my coworkers asked this question at lunch: "If I'm writing an interface that I want other people to be able to use with their own new types, how do I ensure that I write my code in such a way that they can clearly and easily understand the interface that they need to implement? As an additional problem, how do I ensure that I don't accidentally break my interface requirements?"

Now, if you've written much python code at all, you're probably familiar with the term 'duck typing', which basically exerts that "if it quacks like a duck and walks like a duck, it might as well be a duck." This is probably one of python's greatest strengths as it reduces the syntactic complexity of 'templated' code; by default all functions work with all types that match the implicit interface that is their implementation.

The unfortunate side effect of duck-typing is that in order to see the exact interface that you would need to implement for an API to work with, you'd have to pore through the entire codebase of the API (!!). Clearly, that wouldn't work at all. After a bit of discussion, we came up with the following solution:

• API Interfaces should begin by asserting that the arguments passed in match a specified, required Interface. This takes care of the first half of the problem, because a developer needs only to look just inside the function to determine which Interface class needs to be implemented (or derived from, if the developer so chooses).
• The objects passed in should be limited (for the duration of the function) to only expose the explicit members that the interface allows for. This solves the second half of the problem, because it makes it impossible to peek under the covers other than what the Interface allows for.

After some discussion (and mail on the topic), we came up with the following implementation:

class __frozen_iface (object):
    def __init__ (self, ifspec, instance):
        for member in inspect.getmembers(ifspec):         
            if member[0].startswith ("__"):
                continue

            if not inspect.ismethod (member[1]):
                continue

            instance_attr = getattr (instance, member[0])
            if instance_attr.im_func == member[1].im_func:
                raise AttributeError, "Class '%s' has interface class implementation of attribute '%s'" % (instance.__class__, member[0])

            # bypass our internal __setattr__ since that will raise an exception
            object.__setattr__ (self, attr_name, instance_attr)

    def __setattr__ (self, name, value):
        # prevent anyone from accidentally assigning new attributes
        raise AttributeError, "Attempt to set an attribute '%s' for frozen interface class '%s'" % (name, self)

def UseInterface(ifspec, instance):
    return __frozen_iface (ifspec, instance)

Then, client code would do something like this:

class Renderable(object):
    def Draw(self, context):
        abstract # Raises an execption if we get here.

def RenderObject(someRenderable):
    someRenderable = UseInterface(Renderable, someRenderable)
    dir(someRenderable) # Outputs only 'Draw'

This could also be trivially wrapped into a decorator so your code could look like this:

class Renderable(object):

    @Interface(Context)
    def Draw(self, context):
        abstract # Raises an execption if we get here.

PS: Thanks to JimR for the cool implementation of __frozen_iface.

Structured Cleanup: Avoiding gotos

I think everyone in our profession has to write code, at some point, that grabs multiple resources, then do something.

And unconditionally, that code needs to make sure to back out any resource acquisitions in cases of intermediate failure, and only back out the resources that are actually grabbed.

Normally, you see this kind of code for that purpose:

int doStuff(void) {
  char* a = (char*) malloc(100);
  if (!a) goto failure_a;

  char* b = (char*) malloc(100);
  if (!b) goto failure_b;

  // do some stuff

  // Want to keep a and b around.
  return 0;

  // Future proofing, for when we add c.
  free(b);
failure_b:
  free(a);
failure_a:
  return -1;
}

I have two problems with this code:

1. Updating this code requires updating both the allocation semantics and the 'free' semantics.
2. This doesn't lend itself towards any sort of 'pattern' which we can reuse for other things, like grabbing a mutex, semaphore, etc.

Instead of the above code, I propose that we use a system of Rollback objects. I haven't seen these in Design Patterns, but maybe they'll make their way into the next release of the book. :)

template <typename T>
class RollbackAllocator
{
  RollbackAllocator(int countToAlloc) : mAllocated(0) { mAllocated = new T[countToAlloc]; }
  ~RollbackAllocator() { if (mAllocated) delete [] mAllocated; }

  // For easy-to-read client code, no one should take ownership of allocated
  // objects until there are no further failure conditions possible. This same
  // technique can be used for 
  // ANY resource acquisition, whether it's an allocation of memory,
  // grabbing a socket, mutex, semaphore, reading a file, etc.
  T* TakeOwnership() { T* retVal = mAllocated; mAllocated = 0; return retVal; }

        T* mAllocated;
}

int doStuff(void)
{
  // If any fails, it'll throw an exception and the others will be cleaned up.
  RollbackAllocator<char> aAlloc(100);
  RollbackAllocator<char> bAlloc(100);

  // do additional things that could fail.            

  a = aAlloc.TakeOwnership();
  b = bAlloc.TakeOwnership();

  return 0;
}

The beauty of this code is its simplicity. By taking advantage of the guarantee that destructors will always be called upon exiting scope*, we ensure that a and b will always either be dealt with properly, or will be freed. Furthermore, while we do have to update the function in two places when we add a new resource acquisition, we do not have to worry about what order we TakeOwnership! Additionally, this pattern lends itself towards all sorts of resource acquisitions, whether they are mutex grabs, file reads, allocations as we've done above, etc. We can make this pattern fit virtually any resource acquisition pattern, and ensure that we have consistent, future-proof, goto-free code.

Don't get me wrong, gotos have their place. Just not in structured cleanup code.


* C++ doesn't always guarantee that destructors will be called. Any abnormal program termination, including explicit calls to exit, abort, terminate, pure virtual calls, exceptions thrown from exceptions (or destructors), or infinite loops will prevent destructors from being called.