Wandering Thoughts archives

Are Python dictionaries necessarily constant-time data structures?

The general view of all forms of hash tables, Python's dictionaries included, is that they are essentially constant-time data structures under normal circumstances. This is not quite true under sufficiently perverse conditions where you have a high degree of collisions in the hashes of the keys, but let's assume that you don't have that for the moment. Ignoring hash collisions, can you treat dictionaries as fast constant-time data structures?

The answer is 'not always', and the path to it has some interesting and perhaps surprising consequences. The potential problem is custom hash functions. If the objects you're using as dictionary keys have a __hash__ method, this method must be called to return the object hash. This is Python code, so it's not necessarily going to be fast by comparison with regular dictionary operations. It may also take a visibly non-constant amount of time, depending on just how it's computing the hash.

(For instance, hashing even Python strings is actually not a constant time operation; it's linear with the length of the string. It's just that all of the code is in C, so by normal standards you're never going to notice the time differences.)

One of the things that you may want to consider as a result of this is memoizing the results of any expensive __hash__ method. This is what Python strings do; if you call hash() on a string, the actual hash computation is done only once and afterwards the already computed (and saved) hash value is just repeated back to you. This only works for things with immutable hash values, but then if your objects have hash values at all they should be immutable ones.

The real answer is that all of this is relatively theoretical. I'm pretty sure that almost no one uses complex custom __hash__ functions for objects defined in Python, although it seems relatively common to define simple ones that just delegate to the hash of another object (probably mostly or always a primitive object with a fast C level hash function). And if you do have objects with complex __hash__ functions that take noticeable amounts of time, you're probably not going to be using them as dictionary keys or set members very often because if you do, well, you'll notice.

On the other hand, the amount of work that the standard library's decimal.Decimal does in its __hash__ function is a little alarming (especially in Python 2.7). Having looked, I wouldn't encourage using them as dictionary keys or set members any time soon, at least not in high-volume dictionaries or sets. The Python 3 version of datetime is another potentially interesting case, since it does a certain amount of grinding away in Python __hash__ functions.

(In Python 2.7, datetime is a C-level module so all of its hashing operations presumably go really fast in general.)

Sidebar: Custom hashes and the Global Interpreter Lock

Let's ask another question: is adding a new key and value to a dictionary an atomic operation that's inherently protected by the GIL? After all, the key might have a custom __hash__ function that runs Python code (and thus bytecode) during any dictionary operation. As far as I can tell from peering at the CPython code, the answer is more or less yes. Although dictionary or set operations may require calling Python code for __hash__ (and for that matter for custom __eq__ methods as well), this is all done conceptually 'before' the actual dictionary modification takes place. The actual modification happens all at once, so you'll never see a dictionary with eg a key set but not its corresponding value.

This does mean that writing 'dct[ky] = val' may involve much more Python bytecode running than you expect (and thus a much higher chance that Python switches to another thread before the new key and value are added to the dictionary). But it's always been the case that Python might switch to another thread at almost any bytecode, so this hasn't created a new race, just widened the time window of an existing one you already had.

The simple way CPython does constant folding

When I looked into CPython's constant folding as part of writing yesterday's entry, I expected to find something clever and perhaps intricate, involving examining the types of constants and knowing about special combinations and so on. It turns out that CPython doesn't bother with all of this and it has a much simpler approach.

To do constant folding, CPython basically just calls the same general code that it would call to do, say, '+' on built in types during execution. There is no attempt to recognize certain type combinations or operation combinations and handle them specially; any binary operation on any suitable constant will get tried. This includes combinations that will fail (such as '1 + "a"') and combinations that you might not expect to succeed, such as '"foo %d" % 10'.

(Note that there are some limits on what will get stored as a new folded constant, including that it's not too long. '"a" * 1000' won't be constant folded, for example, although '"a" * 5' will.)

What is a suitable constant is both easy and hard to define. The easy definition is that a suitable constant is anything that winds up in func_code.co_consts and so is accessed with a LOAD_CONST bytecode instruction. Roughly speaking this is any immutable basic type, which I believe currently is essentially integers, strings, and floating point numbers. In Python 3, tuples of these types will also be candidates for taking part in constant folding.

At first this approach to constant folding seemed alarming to me, since CPython is calling general purpose evaluation code, code that's normally used much later during bytecode execution. But then I realized that CPython is only doing this in very restricted circumstances; since it's only doing this with a very few types of immutable objects, it knows a lot about what C code is actually getting called here (and this code is part of the core interpreter). The code for these basic types has an implicit requirement that it can also be called as bytecode is being optimized, and the Python authors can make sure this is respected when things change. This would be unreasonable for arbitrary types, even arbitrary C level types, but is perfectly rational here and is beautifully simple.

In short, CPython has avoided the need to write special constant folding evaluation code by making sure that its regular evaluation code for certain basic types can also be used in this situation and then just doing so. In the process it opened up some surprising constant folding opportunities.

(And it can automatically open up more in the future, since anything that winds up in co_consts is immediately a candidate for constant folding.)

Sidebar: What happens with tuples in Python 2

In the compiled bytecode, tuples of constant values do not actually start out as constants; instead they start out as a series of 'load constant' bytecodes followed by a BUILD_TUPLE instruction. Part of CPython's peephole optimizations is to transform this sequence into a new prebuilt constant tuple (and a LOAD_CONST instruction to access it).

In Python 2, the whole peephole optimizer apparently effectively doesn't reconsider the instruction stream after doing this optimization. So if you have '(1, 2) + (3, 4)' you get a first transformation to turn the two tuples into constants, but CPython never goes on to do constant folding for the + operation itself; by the time + actually has two constant operands, it's apparently too late. In Python 3, this limitation is gone and so the + will be constant folded as well.

(Examining __code__.co_consts in Python 3 shows that the intermediate step still happens; the co_consts for a function that just has a 'return' of this is '(None, 1, 2, 3, 4, (1, 2), (3, 4), (1, 2, 3, 4))', where we see the intermediate tuples being built before we wind up with the final version. In general constant folding appears to leave intermediate results around, eg for '10 + 20 + 30 + 40' you get several intermediate constants as well as 100.)

An interesting excursion with Python strings and is

Let's start with the following surprising interactive example from @xlerb's tweet:

>>> "foo" is ("fo" + "o")
True
>>> "foo" is ("fo".__add__("o"))
False
>>> "foo" == ("fo".__add__("o"))
True

The last two case aren't surprising at all; they demonstrate that equality is bigger than mere object identity, which is what is tests (as I described in my entry on Python's two versions of equality). The surprising case is the first one; why do the two sides of that result in exactly the same object? There turn out to be two things going on here, both of them quite interesting.

The first thing going on is that CPython does constant folding on string concatenation as part of creating bytecode. This means that the '"fo" + "o"' turns into a literal "foo" in the actual bytecodes that are executed. On the surface, this is enough to explain the check succeeding in some contexts. To make life simpler while simultaneously going further down the rabbit hole, consider a function like the following:

def f():
  return "foo" is ("fo"+"o")

Compiled functions have (among other things) a table of strings and other constants used in the function. Given constant folding and an obvious optimization, you would expect "foo" to appear in this table exactly once. Well, actually, that's wrong; here's what func_code.co_consts is for this function in Python 2:

(None, 'foo', 'fo', 'o', 'foo')

(It's the same in Python 3, but now it's in __code__.co_consts.)

Given this we can sort of see what happened. Probably the bytecode was originally compiled without constant folding and then a later pass optimized the string concatenation away and added the folded version to co_consts, operating on the entirely rational assumption that it didn't duplicate anything already there. This would be a natural fit for a simple peephole optimizer, which is in fact exactly what we find in Python/peephole.c in the CPython 2 source code.

But how does this give us object identity? The answer has to be that CPython interns at least some of the literal strings used in CPython code. In fact, if we check func_code.co_consts for our function up above, we can see that both "foo" strings are in fact already the same object even though there's two entries in co_consts. The effect is actually fairly strong; for example, the same literal string as in two different modules can be interned to be the same object. I haven't been able to find the CPython code that actually does this, so I can't tell you what the exact conditions are.

(Whether or not a literal string is interned appears to depend partly on whether or not it has spaces in it. This rabbit hole goes a long way down.)

PS: I believe that this means I was wrong about some things I said in my entry on instance dictionaries and attribute names, in that more things get interned than I thought back then. Or maybe CPython grew more string interning optimizations since then.

Exploiting Python metaclasses to forbid subclassing and where it fails

Suppose, entirely hypothetically and purely for illustration, that you want to create a class that cannot be subclassed. Python is normally a very permissive language, but as I mentioned in passing yesterday you can abuse some metaclass features to do this. Well, to more or less do this; as it happens there is a way around it because Python allows callables to be specified as your metaclass.

While there are complex approaches with a single metaclass that has a sophisticated __new__, it's easier to illustrate the whole idea like this (in Python 3 for once):

class Block(type):
  def __new__(meta, cname, bases, cdict):
    raise TypeError("cannot subclass")

def metacls(cname, bases, cdict):
  return type.__new__(Block, cname, bases, cdict)

class A(metaclass=metacls):
  pass

This works basically by cheating; our callable metaclass gives the newly created class a different metaclass that blocks the creation of further classes in its __new__. So let's try to get tricky to get around this. Our first attempt is to give our new subclass a different metaclass that doesn't block class creation:

class MNothing(type):
  pass

class B(A, metaclass=MNothing):
  pass

This will fail:

TypeError: metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases

But wait, we don't actually need a new class here. We just need something that allows class creation but gives the new class the metaclass it needs in order to not have a metaclass conflict. As it happens we already have that:

class B(A, metaclass=metacls):
  pass

(note that if we didn't have metacls(), creating it is trivial. type(A) will give us the metaclass class we need to shim in.)

This not only works, this is the simple and more or less ultimate bypass for anything that tries to block __new__ because using a callable as the metaclass splits apart what happens to a class as it's being created from the class's metaclass class. The new class's official post-creation metaclass gets no chance to intervene during creation; it just winds up being the metaclass of a new class by fiat, with nothing to say about it. Since the metaclass's __init__ (if any) doesn't get called here, the first our Block metaclass can possibly know about the new class is when the new class is used for something (attribute lookup, instance creation, or subclassing).

All of which goes to show that Python is permissive after all if you know the right tricks, even if it looks restrictive initially.

(Well, at least here.)

I wish Python didn't allow any callable to be a 'metaclass'

One of the things that any number of discussions of metaclasses will tell you is that any callable object can be a metaclass, not just a class. This is literally and technically true, in that you can set any callable object (such as a function) as a class's metaclass and it will be invoked on class creation so that it can modify the class being created (which is one of the classical uses of metaclasses).

The problem is that modifying classes as they are being created is the least of what metaclasses can do. Using a callable as your 'metaclass' means that you get none of those other things (all of which require being a real metaclass class). And even your ability to modify classes as they're being created is incomplete; using a callable as your metaclass means that any subclasses of your class will not get your special metaclass processing. This may surprise you, the users of your code and your 'metaclass', or both at once. Unfortunately it's easy to miss this if you don't know metaclasses well and you don't subclass your classes (either in testing or in real code).

I understand why Python has allowed any callable to be specified as the metaclass of a class; it's plain convenient. In the simple case it gives you a minimal way of processing a class (or several classes) as they're being created; you can just write a function that fiddles around with things and be done with it; you don't need the indirection and extra code of a class that inherits from type() and has a __new__ function and all of that. It also at least looks more general than restricting metaclasses to be actual classes.

The problem is that this convenience is a trap lying in wait for the unwary. It works only in one place and one way and doesn't in others, failing in non-obvious ways. And if you need to convert your callable into a real metaclass because now you need some additional features of a real metaclass class, suddenly the behavior of subclasses of the original class may change.

So on the whole I wish Python had not done this. I feel it's one of the rare places where Python has prioritized surface convenience and generality a little too much. Unfortunately we're stuck with this decision, since setting metaclass to any callable is fully documented in Python 3 and probably can't ever be deprecated.

PS: Note that Python is actually inconsistent here between real metaclass classes and other callables, since a metaclass that is a class will have its __new__ invoked, not its __call__, even if it has the latter and thus is callable in general. This is absolutely necessary to get metaclass classes working right, but that this inconsistency exists is another sign that this whole 'any callable' thing shouldn't be there in the first place.

Sidebar: the arguments to your metaclass callable

The arguments for a general callable are slightly difference from the arguments a real metaclass __new__ receives. You get called as:

def metacls(cname, bases, cdict):
    return type(cname, bases, cdict)

If you want to call type.__new__ directly, you must provide a valid metaclass as the first argument. type itself will do, of course. Using a metacls() function that shims in an actual class as the real metaclass is beautifully twisted but is going to confuse everyone. Especially if your real metaclass has a __new__.

(If your real metaclass has a __new__, this will get called for any subclasses of what you set the metaclass function on. I suppose you could abuse this to more or less block subclassing a class if you wanted to. Note that this turns out to not be a complete block, at least in Python 3, but that's another entry.)

The technical side of Python metaclasses (a pointer)

I recently read Ionel Cristian Mărieș' Understanding Python metaclasses (via Planet Python), which is a great but deeply technical explanation of what is going on with them in Python 3. To give you the flavour, Ionel goes right down to the CPython interpreter source code to explain some aspects of attribute lookup. If nothing else, this is probably the most thorough documentation I've ever seen of the steps and order in Python's attribute lookups. There are even very useful decision tree diagrams. I'll probably be using this as a reference for some time, and if you're interested in this stuff I highly recommend reading it.

I'm personally biased, of course, so I prefer my own series on using and then understanding Python metaclasses. Ionel has a much more thorough explanation of the deep technical details (and it's for Python 3, where mine is for Python 2), but I think it would have lacked context and made my eyes glaze over had I read it before I wrote my series and wound up with my own understanding of metaclasses. But Ionel's writeup is a great reference that's more thorough than, for example, my writeup on attribute lookup order.

(But the curse (and blessing) of writing the entries myself is that I can no longer look at metaclass explanations with a normal person's eyes; I simply know too much and that influences me even if I try to adopt a theoretical outsider view.)

I do disagree with Ionel on one aspect, which is that I don't consider general callable objects to be real metaclasses. General callable objects can only hook __new__ in order to mutate the class being created; true metaclasses do much more and work through what is a fundamentally different mechanism. But this is really a Python documentation issue, since the official documentation is the original source of this story and I can hardly blame people for repeating it or taking it at its word.

PS: I continue to be surprised that Python lacks official documentation of its attribute lookup order. Yes, I know, the Python language specification is not actually a specification, it's an informal description.

I've come to believe Django's way of defining database tables is wrong

Django defines both database tables and HTML forms in the same way, a way that seems to be extremely common in web frameworks across several languages (and which I think first surfaced in Rails, although I may well be wrong there):

class AForm(...):
   login = forms.CharField(...)
   email = forms.EmailField(...)
   ...

This is very appealing initially and Django goes well out of its way to make it all work. But over time I've come around to feeling that this is in fact the wrong way to do forms, database tables, and so on in Python. Why not boils down to one famous sentence from 'import this' (aka the zen of Python):

Explicit is better than implicit.

Django form classes and database classes are full to the brim of implicit magic. They're essentially an illusion. Worse, they're not really a very Pythonic illusion. We accept the illusion because it's convenient and this way of defining forms and tables has become more or less standard, but that doesn't mean that it's right in Python.

(My view is that the initial Rails version was a reasonably natural looking DSL that happened to also be valid Ruby code with the right mangling. The Python version is clearly not something you can read as a DSL, so I think that the seems show much more; it looks like Python but it's kind of bizarre Python.)

Given the Tim Peters remark I led with, I think a more Pythonic way would make explicit various things that are currently implicit. I don't have a good handle on what that would look like, though. Doing the setup in class __init__? Defining the table or form layout by calling code instead of defining a class? Either would be (or at least could be) more explicit and less magical.

(Part of the issue is that Python has decided that structures with named fields are only really available as classes. Once you have classes, all sorts of temptations start materializing and looking at least partly natural.)

PS: It's my view that the magical, illusory nature of Django form and table definitions starts showing through very distinctly once you want to do more complex things with them. Like much magic, it works best if you don't touch it at all.

A gotcha with Python tuples

Here's a little somewhat subtle Python syntax issue that I recently got to relearn (or be reminded of) by stubbing my toe on it. Let's start with an example, taken from our Django configuration:

# Tuple of directories to find templates
TEMPLATE_DIRS = (
    "/some/project/directory"
)

This looks good (and used to be accepted by Django), but it's wrong. I'm being tripped up by the critical difference in Python between '(A)' and '(A,)'. While I intended to define a one-element tuple, what I've actually done is set TEMPLATE_DIRS to a single string, which I happened to write in parentheses for no good reason (as far as the Python language is concerned, at least). This is still the case even though I've split the parenthesized expression over three lines; Python doesn't care about how many lines I use (or even how I indent them).

(Although it is not defined explicitly in the not a specification, this behavior is embedded in CPython; CPython silently ignores almost all newlines and whitespace inside ('s, ['s, and {'s.)

I used to be very conscious of this difference and very careful about putting a , at the end of my single-element tuples. I think I got into the habit of doing so when I at least thought that the % string formatting operation only took a tuple and would die if given a single element. At some point % started accepting bare single elements (or at least I noticed it did) and after that I got increasing casual about "..." % (a,) versus "..." % (a) (which I soon changed to "..." % a, of course). Somewhere along this the reflexive add-a-comma behavior fell out of my habits and, well, I wound up writing the example above.

(And Django accepted it for years, probably because any number of people wrote it like I did so why not be a bit friendly and magically assume things. Note that I don't blame Django for tightening up their rules here; it's probably a good idea as well as being clearly correct. Django already has enough intrinsic magic without adding more.)

As a side note, I think Python really has to do things this way. Given that () is used for two purposes, '(A)' for a plain A value is at least ambiguous. Adopting a heuristic that people really wanted a single element tuple instead of a uselessly parenthesized expression strikes me as too much magic for a predictable language, especially when you can force the tuple behavior with a ','.

A retrospective on my one Django web application

Looking back, it's been almost four years since I started writing our first and so far only Django web application, a system for automating much of our new Unix account requests. Since retrospectives are relatively uncommon, today I want to do one for what has been a really faithful web app.

I suppose that's a good summary of the whole situation: after I wrote it, the application has been trouble-free. Over the years I've done a few tuneups to make it a bit more convenient to use for some tasks and to reduce the possibility of accidents while people use it (and there was one interesting bug), but that's it as far as code revisions have gone. This does means that I haven't had to face things like schema migrations; the schema we started with is the schema we still have, and it'll probably last all the way to end of life with this application (which is not going to be any time soon, since we'll probably always need something to do this job).

(Okay, I'll admit it; we have little enough data stored in the system that I might not even try a schema migration but instead just do a database dump, edit the dump a bit, and load it into a new database.)

I'm still pretty happy with our choice of Django, SQLite as the underlying database, and mod_wsgi for deployment. All of them work and I don't see any obviously better alternative, either then or now. Django does a bunch of magic with database models, but I'm a pragmatist; the magic works.

My one real regret about the structure of the web application is that it has (gasp, shock) no tests at all. The core reason for this is that learning Django testing at the same time that I was learning Django was just too much work, and of course there has never been either the time, the energy, or the clear need to go back afterwards to figure out how to do it and add tests. This doesn't make much of a difference for development since there isn't much development, but it does make a difference for upgrading Django itself. And frankly that's one area I've been weak on; we're behind in both our Django versions and jQuery and part of that is because testing new versions is not drop in and go but instead manual.

We're behind on Django versions primarily because we rolled our own; when we built the application initially, the version of Django packaged on the Ubuntu version we were using wasn't advanced enough. These days I would use the Ubuntu 14.04 Django version and be done with it for four years or so (ie I'd be counting on the Ubuntu people to feed me non-breaking security updates that we could install without any particular testing). I don't think we're actively at risk, but it's something I do worry about.

What I don't like about Django boils down to two things, both relatively minor. First, with SQLite we've found that Django's internal 'id' primary key field can reuse ID numbers if and when old records are deleted. We use and expose these ID numbers in a few places (for example, in audit records) and it would be slightly nicer if they didn't get reused. The most annoying (and potentially dangerous) place is that they appear in the URLs exposed to administrative users, which means that an old URL can go to a completely different account request in six months instead of just being invalid.

(These unguarded URLs are not exposed to non-administrative users and operations on them do have specific security checks, so you can only touch entries you have authorization for.)

Second, I have historically found it hard to find release announcements and changes for new Django versions, which I have to do because I need to read over them as we update from version to version. If I closely followed Django and updated on every version change I think I'd be fine, but as it is now I wind up ignoring Django version shifts for months at a time and then have to grubbing through the site to find all of the release announcements for every version between where we are and where the state of the art is.

(In fact I just went through the Django website and couldn't immediately locate even a 'what is new in the latest version' page, much less ones for previous releases. And I know the information is somewhere, because I've found it before.)

PS: that we have only one Django web app is not because we've grown disenchanted with it, it's just that we haven't had a combination of time and need to write any more (and we do have a second one somewhere quite far down the priority list). Well, for me to write any more; my co-workers don't do Django so far.

Update: It turns out that Django release notes are all available in one spot here. They're even conveniently all linked to each other so you can go back and forth (although this is not necessarily the chronological order, since point updates may be made to older versions even after a new version has been released).

There are two parts to making your code work with Python 3

In my not terribly extensive experience so far, in the general case porting your code to Python 3 is really two steps in one, not a single process. First, you need to revise your code so that it runs on Python 3 at all; it uses print(), it imports modules under their new names, and so on. Some amount of this can be automated by 2to3 and similar tools, although not all of it. As I discovered, a great deal of this is basically synonymous with modernizing your code to the current best practice for Python 2.7. I believe that almost all of the necessary changes will still work on Python 2.7 without hacks (certainly things like print() will with the right imports from __future__).

After your code will theoretically run at all, you need to revise your code so that it handles strings in Unicode, and it means that calling this process 'porting' is not really a good label. The moment you deal with Unicode you need to consider both character encoding conversion points and what you do on errors. Dealing with Unicode is extra work and confronting it may well require at least a thorough exploration of your code and perhaps a deep rethink of your design. This is not at all like the effort to revise your code to Python 3 idioms.

(And some people will have serious problems, although future Python 3 versions are dealing with some of the problems.)

Code that has already been written to the latest Python 2.7 idioms will need relatively little revision for Python 3's basic requirements, although I think it always needs some just to cope with renamed modules. Code that was already dealing very carefully with Unicode on Python 2.7 will need little or no revision to deal with Python 3's more forced Unicode model, because it's already effectively operating in that model anyways (although possibly imperfectly in ways that were camouflaged by Python 2.7's handling of this issue).

The direct corollary is that both the amount and type of work you need to do to get your code running under Python 3 depends very much on what it does today with strings and Unicode on Python 2. 'Clean' code that already lives in a Unicode world will have one experience; 'sloppy' code will have an entirely different one. This means that the process and experience of making code work on Python 3 is not at all monolithic. Different people with different code bases will have very different experiences, depending on what their code does (and on how much they need to consider corner cases and encoding errors).

(I think that Python 3 basically just works for almost all string handling if your system locale is a UTF-8 one and you never deal with any input that isn't UTF-8 and so never are confronted with decoding errors. Since this describes a great many people's environments and assumptions, simplistic Python 3 code can get very far. If you're in such a simple environment, the second step of Python 3 porting also disappears; your code works on Python 3 the moment it runs, possibly better than it did on Python 2.)