What's going on with rom?

This post will talk about the open source Redis object mapper that I've released called rom. I will talk about what it is, why I wrote it, and what I'm planning on doing with it. I've posted several articles about Redis in the past, and you can buy my book, Redis in Action, now (hard copy will be available on/around June 10, 2013 - about a week from now) - enter the code dotd0601au at checkout for half off!

What is rom?

Rom is an "active record"-style object mapper intended as an interface between somewhat-intelligent Python objects and behavior, and data stored in Redis. Early versions (everything available now, and available for the coming few months) are purposefully simplified with respect to what is possible with Redis so that rom's capabilities can grow into what is necessary/desired, rather than trying to build functionality to support any/all possible use-cases up front.

An example use for storing users* can be seen below.

from hashlib import sha256
import os

import rom

def hash_pw(password, salt=None):
    salt = salt or os.urandom(16)
    hash = sha256(salt + password).digest()
    for i in xrange(32768):
        hash = sha256(hash + password).digest()
    return salt, hash

class User(rom.Model):
    name = rom.String(indexed=True)
    email = rom.String(required=True, unique=True, indexed=True)
    salt = rom.String()
    hash = rom.String()

    def update_password(self, password):
        self.salt, self.hash = hash_pw(password)

    def check_password(self, password):
        hash = hash_pw(password, self.salt)[1]
        pairs = zip(map(ord, hash), map(ord, self.hash or ''))
        p1 = sum(x ^ y for x, y in pairs)
        p2 = (len(hash) ^ len(self.hash))
        if p1 | p2:
            raise Exception("passwords don't match")

    @property
    def contact(self):
        return '"%s" <%s>'%(self.name, self.email)

Aside from the coding overhead of handling the hashing of passwords in a somewhat secure manner, setting up attributes and adding simple behaviors on top of models is pretty much what you should expect in an object mapper used in Python.

Why did I write rom?

As is the case with many things I build, it was meant to scratch an itch. I was working on an as-of-yet unreleased personal project and I needed a database. This database would only ever need to hold a few megabytes of data (maybe up to the tens of megabytes), but it also may need to perform several thousand reads/second and several hundred writes/second on an under-powered machine, and would need to persist any updated data. Those requirements eliminated a standard database in a typical configuration. However, a relational database instructed to store data in-memory would work, except for the persisting to disk part (and Postgres with some fsync tuning wouldn't be unreasonable, except maybe for the read volume). Given that I have a lot of experience with Redis, and my requirements fit with many of the typical use-cases for Redis, my project seemed to be begging to use Redis.

But after deciding to use Redis for my project, then what? I've built ad-hoc data storage methods on Redis before (roughly 2 dozen different mechanisms that are or have run in production, never mind the dozens that I've advised others to use), and I feel bad every time I do it. So I started by looking through several of the object mappers for Redis in Python (some of which call themselves 'object Redis mappers' to stick with the 'orm' theme), but I didn't like the way they either exposed or hid the Redis internals. In particular, most of the time, users shouldn't care what some database is doing under the covers, and they shouldn't need to change the way they think about the world to get the job done.

Now, I know what you are thinking. You're thinking: "Josiah, Redis is a database that requires that you change the way you think about the world in order to make it work." Ahh, but that's where you are wrong. The purpose of rom is to abstract away about 90% of the strangeness of Redis to a new user (at least on the Python side). Almost everything works the way most users of SQLAlchemy, Django's ORM, or Appengine's datastore would expect. About the only thing that rom doesn't do that those other libraries offer on top of relational databases is: 1) composite indices and 2) ordered indices on string columns.

With Redis and the way rom handles its indices, there might be some advantages to offering composite indices on the performance side of things for certain queries. But those queries are very limited, and there is just under 64 bits of usable space in any index entry. Ordered indices on string columns is also tough, running into a limit of just under 64 bits to offer ordering there.

There is a method that would increase the limit beyond 64 bits, but that method would be incompatible with the other indices that rom already uses. So, long story short, don't expect composite indices, and don't expect ordered indices on strings that play nicely with other rom indices.

What is in rom's future?

If you've read everything above, you know that composite indices and sorted indices on strings that play nicely with the other indices is not going to happen. But what if you don't care about playing nicely with other indices? Well, that is a whole other story.

With ordered indices on strings, one really nice feature is that you can perform prefix lookups on strings - which makes autocomplete-like problems very easy. Expect that in the future.

At some point I'll also be switching to using Lua scripting to handle updating the data in Redis. That will offer fast and easy support for multiple unique index columns, while simultaneously offering point-in-time atomic updates without retries. All of the major logic would be on the Python side, leaving simple updates to be done by Lua. I haven't done it yet because the performance and feature advantages are not drastically better to necessitate it at this point. With a little work, it would even be possible to implement "check and update" behavior to ensure that data hasn't been manipulated by other clients.

I've also been thinking about deferring attribute validation until just before data is serialized and sent to Redis, as it can be a significant performance advantage. The only reason I didn't do that from the start is because a TypeError on commit() can be a nightmare. Hunting down the answer to, "how did that data get there?" some time after the write occurred can be an exercise in futility. By performing the validation on attribute write (and on data load from Redis), you can at least know when you are writing the wrong data, you will be notified of it right away. As such, deferring validation until commit() may be a documented but discouraged feature in the future.

Redis-native structure access

I know that by now, some of you are looking at your screen asking, "When can I get raw access to lists, sets, hashes, and sorted sets? Those are really what my application needs!" And my answer to that is: at some point down the line. I know, that is a wishy-washy answer. And it's wishy-washy because there are three ways of building the functionality: 1) copy data out of Redis, manipulate in Python, then write changes back on commit(), 2) create objects that manipulate the in-Redis data directly, or 3) offer smart objects like #2, but write data back on commit().

If we keep with the database-style, then #1 is the right answer, as it allows us to perform all writes at commit() time. But if people have large lists, sets, hashes, or sorted sets in Redis, then #1 is definitely not the right answer, as applications might be copying out a lot of information. But with #2, updates to other structures step outside the somewhat expected commit() behavior (this entity and all related data have been written). Really, the right answer is #3. Direct access to reading, but masking write operations until commit().

Talking about building native access is easy, but actually building it to be robust is no small task. For now, you're probably better suited writing manual commands against your structures if you need native structure access.

How can you help?

Try rom out. Use it. If you find bugs, report them at Github. If you have fixes for bugs, post the bug with a pull request. If you have a feature request, ask. If your feature request is in the range of things that are reasonable to do and which fit in with what I want rom to be, I'll build it (possibly with a delay). Tell your colleagues about it. And if you are feeling really generous, buy my book: Redis in Action. If you are feeling really generous (or lost), I also do phone consultations.

Thank you for taking the time to read, and I hope that rom helps you.

* Whether or not you should store users in rom and Redis is a question related to whether Redis is suitable for storing such data in your use-case. This is used as a sample scenario that most people that have developed an application with users should be able to recognize (though not necessarily use).

Steganography in Python

Book Deal:

As a pre-article bonus, you can enter code dotd0511au during checkout to get 50% off of my book Redis in Action. If you want to keep seeing articles like this, please buy my book and give me positive reviews on Amazon ;)

See me speak:

LA Web Speed is hosting me for a talk at 7PM at Yahoo's offices in Santa Monica. Hit this page for meetup information: http://www.meetup.com/LAWebSpeed/events/115663212/ . I hope to see some of you there!

Steganography in Python

In this post I am going to talk about some code that I wrote to offer steganographic functionality in Python source files. This code was written for a lightning talk given at the April 1 Southern California Python Interest Group meeup (aka So-cal Piggies), hosted over at Mucker Labs in Santa Monica.

What is "steganography"?

Basically, steganography is the hiding information within other information. There have been countless examples of steganography used over the centuries, and I'll leave it to you to click on that Wikipedia link to learn about all of them.

Where did the idea come from?

At the February 28 So-cal piggies meetup, a few of us were chatting about programming languages. I mentioned whitespace, a programming language that only uses whitespace for expressing syntax. When it was announced that April 1 would be a meetup of lightning talks that would discuss things to do/not to do in Python, I thought about revisiting last year's revisit of Gotos in Python to make my case statement loopable and not reliant on the internal debugging mechanisms. Then I thought a bit more, and an idea sparked from our earlier discussion of whitespace... Python's tabs and spaces.

How can you hide information in Python's tabs and spaces?

As most of you know, Python's syntax requires the use of tabs and/or spaces in order to define multi-line block structures. You can use all tabs, all spaces, or you can mix tabs and spaces, where a tab counts as 8 spaces (though mixing tabs and spaces is considered bad form). The idea was to use mixed tabs and spaces for indentation in order to hide information.

Basically, for each line with leading spaces that is not inside a triple-quoted string, consider the indentation. Break the indentation into blocks of 8 spaces (discarding any partial block). If a block is a tab, it is considered a 1 bit. If the block is 8 spaces, consider it a 0 bit.

With this semantic, we can define a protocol for embedding information inside a Python source file fairly easily. The first 8 bits of the file will define how many 4-bit hexidecimal digits will be available in the file, with 8 '0' bits meaning 1 digit. So a file consisting of all spaces will return a single '0' as its data. This allows for up to 10-28 bits to be stored per file (on average from the stdlib).

Expanding the idea

After building the above and calculating the amount of bits that are available in a variety of source files, I discovered that using only indents wouldn't offer much in the way of data storage density. Knowing a bit about Unicode, and how there are characters that behave quite a bit like a space character, but aren't, I started looking at zero-width and standard-width non-printed characters to replace *all* space characters with other characters (which would offer many more bits). After discovering about a dozen of them, and trying to inject them into Python source files, I discovered that Python is *very* strict about what it considers syntactically valid whitespace: tab, space, and form-feed.

I briefly toyed with the idea of re-formatting Python code to be PEP 8 compliant (PEP 8 is the Python enhancement proposal that defines how properly formatted Python code should look), then using extra spaces in odd places (in violation of PEP-8, like putting a space between a function name and the parenthesis calling it like foo () for both function definitions and calls) in order to represent 1 bits (the lack of an oddly-placed space would be a 0). I also considered the use of LF vs. CRLF line endings to represent data, but CRLF pairs result in ^M being shown in 'diff' calls. I also considered adding a spare trailing space on lines, but most 'diff' calls show ugly red highlights for extra spaces.

One that I was very tempted to consider was one that inserted zero-width spaces conditionally in unicode strings (aka strings in Python 3.x). Because they don't print, you wouldn't notice anything strange about them, unless you output them on the web and inspected them, wrote them to a file, or tried to calculate a hash and saw the result wasn't what you expected. But, you could combine the string manipulation with an import hook with some ctypes hackery that examined all strings loaded from the module, and replaced the strings with ones that didn't have those zero-width spaces.

I may revisit these ideas in the future, but I found a simpler and easier way to not mangle beautiful source code or needing to write an import hook that involved ctypes: spaces in comments.

Because most code has at least a handful of comments, and because you can put just anything between a # and the newline (assuming a proper bom or coding: declaration), I started conditionally replacing space characters with a different space character. I considered optionally using zero-width spaces as well, or using one of a few different space characters (for more than one bit per space replaced), but simplicity is the name of the game. The more complicated it gets, the more likely your data will be discovered. For most source files, conditionally replacing spaces in comments resulted in a 3-5x increase in the number of bits that can be hidden in a Python source file, making my super-secret plan possible: store the sha1 or sha256 hmac of a file *inside* the file itself for self-verifying code.

The result

Ultimately, I ended up writing a module/command line tool that allows you to count the number of bits that can be hidden in a file, fetch stored bits from a file, clean the bits out of a file, write bits to a file, store the sha1 or sha256 hmac in a file (you are prompted for a password), or verify that a file has its proper sha1 or sha256 hmac embedded inside it (there's a password prompt here too). It uses the tokenize module to do all of the syntactical heavy-lifting for reading and writing, and *may* only work in Python 2.6.

This module uses both the comment space trick as well as the tabs/spaces indent trick. I'm not terribly proud of the quality of the code, as I only had 2 afternoons to work on it leading up to the talk. But it works, and could be reasonably expanded to support all of the tricks I mentioned above, and more.

If you'd like to take a look at the code, you can read and/or download it from this Github Gist.


One of my favorite ideas for storing data is actually to hide passwords inside your source files. More specifically, it is generally considered to be bad form to store passwords inside files stored in your source code repository, especially when that repository is hosted by a 3rd party. Well, you could store your password in some arbitrary source file in your repository (perhaps encrypted with the private key half of a public/private key pair), then when setting up your machine for the first time, download my gist, extract your password (decrypting with your public key, which could also be in your repository - it's public), then delete my gist. You then have your password available, few people would think to look at a poorly-formatted Python source file.

This becomes really nefarious if you store the password in an initial commit as a sort of "committing what I've got, this is crap" (where formatting can sometimes be broken) along with a collection of other files with garbage data. Subsequent commits can clean up the bad formatting incrementally, and part of your "get password" mechanism can perform a checkout of the first commit of the repo before trying to extract the data (or a second commit, or looking for a specific comment inside a commit message, ...).


It's getting late, so I'm going to call this post done and head to bed. I hope that this has sparked some ideas for how you can hide and manipulate data.

Keep your eyes peeled, in the coming week or two I'll be posting about what is going on with rom, my Redis object mapper for Python. And don't forget to pick up your copy of Redis in Action, where you can learn how to use Redis in ways it was and was not intended.

Want to get a deal on Redis in Action?

As we come into the home stretch of the release of Redis in Action, a lot of work has been going on behind the scenes. Easily 3-4 complete read-throughs over the last few months, a crew of editors poking and prodding, countless major and minor edits, and for those of you who have already downloaded version 11 of the MEAP (released last week), you will notice that it has taken a pass through the typesetters. This pass has resulted in a level of spit and polish that I couldn't imagine a year ago when the first MEAP went live.

There are still a few issues to be fixed in the week since version 11 of the MEAP was released, but they are getting cleaned up as I type this.

To commemorate this final push and to give everyone a chance to learn more about their data, Manning is offering 50% off Redis in Action, Lucene in Action 2nd Edition, and Machine Learning in Action. How do you get 50% off? Follow those links and enter dotd0501au on checkout.


When I find time in the coming weeks, you can look forward to two blog posts. The first on Steganography in Python, which I presented as a lightning talk on April 1 at the Southern California Python Interest Group meetup. And in the second, I'll talk about the whys, whats, and hows of building rom, a Redis Object Mapper in Python.

If you want to see more posts like this, you can buy my book, Redis in Action from Manning Publications today!

I'm tired

It may come as a surprise (or not) to those of you who see me posting on the Redis mailing list, or who've been involved in the writing of Redis in Action, or that work with me on a daily basis, or that I give technical advice to, or those that I would call friends, ... but I am tired. Actually no, I'm fucking exhausted.

In the last year and four months, I've played the architect and lead engineering role in the rewriting of an entire online meal ordering platform, I've advised 3 startups on how to scale/re-architect their backend (one of which grew from 50k users to 380k users in 1 month, still growing just as fast), I've advised countless Redis users how to use Redis, I spent one year of my evenings and weekends writing my book, I've worked on several of my own open-source projects, several personal projects that may turn into side-businesses, I was invited to and spoke at 4 conferences in 4 months (a different talk for each one), I've spent the last 2 months part-time working from home to help take care of my first child, and for the 5-6 months before that, doing my best to take care of my pregnant wife.

I used to joke that I was a machine; that the act of helping people, giving advice, writing software, all of it, was rewarding and invigorating, and that I didn't need to take a rest from it. I was wrong. Aside from a couple long weekends in the last year, and 2 weeks after my daughter was born (during all of which where I replied to work email, still worked from home on occasion, and took phone calls), I've been running at full speed the entire time with only the occasional movie/video game night or spending time with friends.

I need a vacation. Somewhere with a beach, warm water, good snorkeling, and decent waves for body-boarding and/or surfing.

When and how I will take a break, I have no idea.

Take care of yourselves out there, it's all too easy to push yourself to the limit for too long, and to deny that you need to take a break.

Why "right to work" is bullshit

Today is going to be a different sort of blog post. Normally I talk about technology, but helping to run a startup, finishing a book, and preparing for the imminent birth of my first child have all prevented me from posting for a while. But recently I've heard a lot of obvious bullshit about an issue that pushed me to the point of writing about it.


A little back story before I get to the purpose of this post, and my point. Tonight I attended the Southern California Python Interest Group Meetup, where one of the speakers discussed continuing education. More specifically on how online education courses, free online resources, and social interaction have grown and become very effective at teaching new programmers. One of the topics that was brought up was a relative lack of shared cultural context (history, literature, politics, etc.) that can be missed when only relying on online resources. This is because when you are interested in something, you learn as much as you can about that one topic, but you don't necessarily learn very much about the world of stuff that is out there. My contribution was to say that if you are in the position of being an educator or peer to someone who is missing some of this education/context, that you should suggest literature, movies, or other media that can offer information about the context of these things, as context is important in everything.

The "right" to work

Recently, the state of Michigan passed a law that essentially says that if you are working in an otherwise "union workplace", you no longer have to pay union dues in order to gain the benefits of the union bargaining process.
I'm going to ignore a lot of the arguments for and against these so-called "right to work" laws, because almost all of them miss the purpose behind the laws actually being passed, miss the context in which unions were created, and completely forget the reasons why unions are still important today.

Power

In the industries in which most individuals are employed, the employer has the power. Make no mistake, aside from a few specific highly-educated, highly-trained, or high-demand careers, the employee has very little power. The employer decides wages, can say yes or no to vacation scheduling, can lay off or fire employees for little to no reason, can require salaried employees to work evenings or weekends (through explicit or implied threats of reduced bonuses, demotions, no raises, etc.), ... Unless your social circle is very limited, you will know someone who is worried about whether they will have a job in the future.

Unions exist to balance power. They were created literally from the blood, sweat, and tears of people who had suffered from the power inequity inherent in the employer - employee relationship. Unions in the United States sprung from a society where people injured on the job would be fired because they could no longer do the job. Where an employee who questioned their boss could be fired and blacklisted from an entire industry. And in some industries, talking about collective bargaining could get you fired or even killed.

While some of the many issues that caused the spread of unions in the United States have been addressed through laws (anti-blacklisting, workers compensation, anti-monopoly...), workers in the United States (and all over the world), still need to be protected.

Confusing the issue

One of the many methods that proponents of these laws use is to confuse the issue with bullshit. These "right to work" laws are not about letting everyone get a fair shake at getting and keeping a job (in fact it reduces the protections that employees have from employers). It is about removing the only effective check to rising corporate power in the United States. You should find it damning that the same people who say that unions shouldn't exist (either explicitly or through right to work laws) are the exact same people who think that corporations should be allowed to spend unlimited money on political campaigns, and that unions shouldn't be able to spend union dues on politics at all. Political figures who are advocating for right to work are trying to take away the worker's right to be represented in politics through organizations who are actively looking out for them - their unions.

I've also heard accounts of "last-hired, first-fired" in education being an example where union contracts have gone bad, and that this is why unions need to be stopped. But this is just an argument to confuse the real issue. Those contracts were agreed upon to protect career teachers that wouldn't have other employment opportunities outside the school that they'd been teaching at for decades (in some cases), because despite attempts to address the issue, ageism exists in the United States, just as surely as racism, sexism, glass ceilings, and homophobia do. To the point, the issue isn't who should be hired or fired, depending on the budget. The issue is that we are not spending enough on education.

Summing up

If there are just a two things that you take away from this (in addition to wanting to learn more about the history of unions and union creation in the United States), they should be:

1. Arguments that use one or two example contracts as reasons why unions don't work are confusing the issue - there are millions of union-negotiated contracts that don't have those clauses
2. "Right to work" laws are an attempt to reduce employee power, to reduce low/mid-level employee wages, to provide more short-term corporate profits, to ultimately increase pay to executives (union labor workers generally earn 10-30% higher wages compared to non-union labor [reference])

Python bytecode hacks, gotos revisited

Some 8 years ago today, two April fool's jokes appeared on python-list and its mirror newsgroup, comp.lang.python. At the time, I was too young or too much of an idiot to appreciate them.
The first was a pronouncement of Guido's having decided that instead of the tab vs. space wars, that we would use the unicode character u'\x08' and our editors/IDEs could be told how wide to display the character. Even better, almost all editors/IDEs already supported the functionality. Like the wet blanket that I was at the time, I of course pointed out that PEP 8, which defines "the standard" to be 4 space indents, no tabs, hadn't been updated and that no discussion of the kind had occurred in python-dev at any time over the weeks prior. In a nutshell, I was a jerk. Sadly, I can't find the original thread in Google Groups. I still feel bad about being the guy who rained on that parade. So, whomever wrote it, I'm sorry.

The second bit of awesome that I remember was Richie Hindle's Goto in Python. If you've not seen it, or you haven't tried it out, you are missing something. The miracle of it all is that it worked. The details are very cute, it hooks the system trace function, and mangles the next line number to be executed. Now, I don't believe that I said anything negative about it at the time, but I certainly wasn't terribly enthusiastic about it. Having recently been reminded of Richie's goto, it dawned on me how brilliant of an idea the joke was. While I'm sure someone may have thought it was a good idea in the early days of Python, and Guido would have rightfully rejected it. But that Richie came back some 12+ years after Python's creation with a working implementation that didn't alter the underlying syntax? Genius.

Getting to the point

Why am I writing this post? Surely it can't just be to pontificate on the history of Python. Oh no. It's time that I give something back for not being able to appreciate a joke all those years ago, and I'd like to make an effort to commemorate the 8th anniversary of Richie and the unknown 'tab indent' poster's brilliance. Recently, it has come to my attention that Carl Cerecke re-implemented goto in Python by hacking bytecodes (way back in November of 2009, I know, I'm a little late to the party). Why didn't I see it before? Why didn't Richie see it before? It's an evolutionary step in the right direction! It's starting with a non-practical but great joke, and taking it to it's logical conclusion: make it practical. Now, Carl didn't see it as being a joke, and reasonably so. And after seeing that it could be practical, I agree that it's no longer a joke (I will explain this later). But sadly, the recipe has bugs. My contribution is to get rid of the bugs, and add experimental features.

Gotos in Python

First, let's look at the syntax based on one of the examples listed as part of Carl's recipe.

@goto
def test1(n):

    s = 0

    label .myLoop

    if n <= 0:
        return s
    s += n
    n -= 1

    goto .myLoop

assert test1(10) == 55

You define a label using 'label.<labelname>', optionally adding a space between 'label' and the '.' to make it easier to read. Similarly, gotos are defined via 'goto.<labelname>'. Perfectly reasonable and valid Python syntax, just an attribute reference. The magic lies in the decorator up front, which translates those attribute references into bytecode that either turns a label into a sequence of no-ops, or a jump to the label. But, as I mentioned before, there are bugs.

The recipe as listed suffers from 3 major bugs, 2 of which are similar in cause. In the decorator written by Carl, he uses a dictionary as a mapping of goto labels to bytecode offsets where that label occurs. Because of this, you can't have two gotos leading to the same label. And when the translation occurs, it leaves all but the last goto leading to that label unchanged, so the more useful example below that uses gotos for error handling, wouldn't work.

@goto
def handler(data):
    if testA(data):
        if testB(data):
            if testC(data):
                ...
                if testD(data):
                    goto .error
            ...
        
        else:
            goto .error
    ...
    
    return "success"

    label .error
    # do something complicated that you don't want
    # to duplicate in every error condition
    return "error"

Only the last goto would have been translated into a jump, but the other one will sit around and not cause an error until it is hit, at which point you will get an AttributeError. The solution, of course, is to map gotos names to a list of bytecode offsets for that label. An easy fix.

Remember earlier when I mentioned that I no longer think that gotos in Python are a joke? Well, if you dig through the CPython source code, you will come to find that gotos are used in the C parts of CPython for error handling. In Python, you can implement much of the same control flow with loops and 'break/continue' statements, but it's legitimately less elegant than a goto. I recently found myself writing code for work where using gotos for error handling would have simplified our code significantly. Ultimately, I ended up not using gotos, only because our requirements changed and I could gut the function to remove all of the strange corner cases. But I now recognize how useful gotos can be.

The second bug is that if you happen to include the same label twice, the decorator won't warn you, and will again just use the last label as the destination for jumps, leaving earlier labels as AttributeError potholes. This is also an easy fix, we can just check to see if it the label has been seen during the bytecode manipulation already, and if so, raise an exception.

The last bug is caused by the earlier decorator creating a new function that didn't preserve existing attributes. To fix this bug, we'll bypass creating a new function by just replacing the code object on the function. This is, by the way, one of my favorite ways to monkey-patch libraries and running systems; you don't need to replace every reference to a function or method, you just need to replace it's code object. But I digress, let's add a feature.

Computed gotos

Richie's library also supported computed gotos, but Carl didn't want to include them because they are not Pythonic. I suspect a different reason, and that is because computed gotos are a huge pain in the ass. Python's underlying bytecode doesn't support jumping to an arbitrarily computed offset, and because Python's code objects are immutable, you can't even write self-modifying code without mucking about with the ctypes module. How frustrating ;) . But don't fret, because Richie has the answer: trace functions. Now, since this is a post about bytecode hacking, of course we've got to keep hacking on bytecodes. Also, in C/C++, computed gotos aren't really bare like Richie was using, no, they are actually switch/case statements. Ah hah! All we need is a syntax in Python that gives us enough room to do all of the shenanigans that we need to do for switch/case statements in Python. First, the syntax. See the following (very ugly) code listing for the syntax that we are going to use.

@switch
def test2():
    a = 1
    while switch *a:
        case[0]
        # not taken
        goto .end

        case[1]
        # taken

        case[2]
        # there is fallthrough like C/C++!

    # default code goes here

    label .end
    # this is after the switch/case

Now, don't let that syntax fool you, the while loop is just to set up a block using at least the 12 bytecodes we need for the hack. A with statement would have been sufficient, but it has a lot of setup and teardown that is annoying to replace (a total of 24 bytecodes), and the other non-looping block in Python, 'if', only offers 11 bytecodes. You are probably wondering why we didn't just re-use "continue" and "break" to jump back to the switch or jump out of the switch. The short reason is because I didn't want to have to rewrite the entire bytecode of the function to adjust offsets (because continue/break are 1 bytecode, and jumps are 3 bytecodes), and the longer reason is just that I was being lazy :P

Okay, so we've got a syntax, but how do we jump to arbitrary case statements? Well, we set up a helper function that will handle jumping to arbitrary line numbers, then we replace the while loop bytecode with alternate bytecode that fetches the destination line number from a dictionary that we packed away in the locals array (defaulting to a line just after the while loop, so the "default" is just outside the while block), and we call the helper to jump to the proper line number instead of looping.

The function that actually handles jumping to arbitrary line numbers will set up the system trace function to a necessary level to induce the line number change, then allow the trace to clean itself up. With this method, we can get switch/case statement handling to execute fairly quickly, aside from the trace function overhead.

The sad truth

I know what you are thinking, you're thinking, "Holy crap, switch/case in Python with a bytecode hack? We can totally use that to optimize some types of parsing!" Well, it's not that simple. Because of the stuff we did with the trace function, we actually can't even put the switch/case within a loop because it causes a segfault with the Python interpreter due to the way trace functions are manipulated. I have not dug too deeply into this, nor have I tried to fix it, primarily because I've been too busy. Heck, I'm writing this blog post on my birthday, because it's the first spare time I've had in weeks.

Even worse, because of the way that Python handles loops and with statements, jumping in and out of them can lead to some pretty nasty results, potentially leading to a segfault. Those issues are still there, though an intrepid hacker could continue down this path to add checks to the hack to detect loop starts/ends, and check how deep into blocks the goto/labels are. If someone doesn't beat me to it, maybe I'll get to it in a couple months, but I'm not going to make promises.

Now, with the sad truth comes a bit of sunlight to brighten your day: there is a way to fix the segfault. Rather than abusing the system trace function, we can instead set up a sequence of if-statements in a tree structure to find the correct case, in O(log(number of case statements)). This actually wouldn't be all that unreasonable, except that there isn't room inside the existing bytecode to make it happen, so we would need to add extra bytecode to the end of the existing bytecode, or inject the bytecode and adjust the offsets in the bytecode and line number table. Maybe I'll get around to it some day.

Conclusion

You can see, download, and fork gotos in Python at this Github gist. Keep making cool stuff, and don't let party poopers like me get you down.

Why we didn't use a bloom filter

After having been featured on the High Scalability blog, there has been renewed interest in my 6 month old post about Improving Performance by 1000x.

Occasionally I've received a few questions and/or comments about that post in other forums, but today I got a couple posts from two well-intentioned commentators that highlighted some very interesting misunderstandings about how modern computers and compilers work, misunderstandings that are actually very common. Unfortunately, a couple of the author's comments have been removed (I didn't remove them; I only remove obvious spam comments), so I will summarize the questions after I briefly describe what I built.

What I built

Using C, I wrote a handful of lines of C code that took a sorted sequence of 4-byte integers that represented a Twitter user's followers, and I intersected that sequence against thousands of other similar sequences for other Twitter users. By being careful, we went from taking roughly 7 seconds to intersect that data in Redis, to taking 6 milliseconds to intersect it with our custom software. On the memory side of things, we reduced our memory requirements by roughly 20x with our method over the standard Redis method.

Let me be clear on this, Redis is a great tool. I still use it every day (even though I've left Adly for ChowNow, and I'm writing Redis in Action for Manning Publications (I should be working on it now, but I wanted to blog on a Friday night). But for some problems, like the one we had, custom software can be a huge win. On with the questions!

Question: Why not use the high-performance C++ STL set intersection code?

Updated Answer: The STL is a pain to work with, and my experience on the C++ side of things (6 months professionally), told me that I would find neither performance nor simplicity by using it.

On top of all of that, we didn't actually need the list, we only needed the count, so even if we had spent the pain of writing it in C++, we'd get a result that was unnecessary, and have to write our own intersection code in the end anyway.

I originally started with code very similar to the C++ STL set intersection code and was dissatisfied with the results. By observing that the longer sequences will skip more items than the shorter sequences, I wrote a 2-level loop that skips over items in the longer sequence before performing comparisons with the shorter sequence. That got me roughly a 2x performance advantage over the STL variant.

There have been a few comments about my STL concerns about performance, which I wanted to respond to.

My original post mentioned performance issues with using vtables in modern C++. My experience from ~4 years ago was using a combination of the STL and other C++ classes. I may have been incorrectly attributing the relative low performance of some operations to method dispatch, instead of some of the quality of containers we were using. Let me explain.

In 2004-2005, I had built a hash table as part of a search engine in C, which was used as a set (no values, only keys). It used 64 bit hashes and 64 bit values on a 32 bit machine. Using this hash set, I was able to add/update/remove items at a rate of 8 million items/second on a mobile 1.2 ghz Intel Core Solo.

In 2007-2008, I had used std::hash_set to store a set of 64 bit integers, and I was surprised to find that it could only add/update/remove 3 million items/second, despite running on a 3.0 ghz Intel P4 (hyperthreading enabled/disabled only affected performance by 5-10% on that problem). I had shrugged it off and called it a vtable problem*, which was a naive decision that I'd not revisited until now. Rethinking it, it was more likely the combination of both the efficiency of the P4 architecture (specifically with respect to pipeline depths; 11-13 with core solo vs. 20+ with P4) and the specifics of the hash table itself.

* I had been willing to quickly jump to the conclusion that it was the language/compiler because I was used to that on the Python side of things. No really. Why is standard Python slow compared to C/C++/Java? It's simply a matter of time and money not having been spent to research and implement JIT and/or static compilers. Look at Boo (which uses static types), PyPy (which uses a restricted version of Python), or Unladen Swallow (which uses an LLVM backed JIT); once time and money has been spent in an effort to improve Python performance, it happens. Incidentally, that's also the only reason why the JVM is so fast: $Billions have been spent on making it faster in the last 20 years.

Probably mostly wrong portion of the original answer:

Have you ever used the STL? I did for about 6 months professionally, and I'm glad that I could go back to C and Python. More seriously, object orientation in C++ doesn't come for free. Aside from the pain of the syntax of using C++ templates (and difficult to parse error messages), all of that object orientation hides the complexity of method dispatch in what are known as vtables. If your system has to call them to dispatch, you are wasting time in that processing when you could be doing something else. For most software, that doesn't matter. But when we are talking about nanoseconds (and we will shortly), every bit of work costs you.

Even ignoring the vtable cost, we'll pretend that all of the set code was inlined. But now, all of your manipulation and boundary checking is in your core intersection loop, which will introduce more branches, more branch mispredictions, which will ultimately slow down the intersection code.

Question: Why not use a bloom filter?

Answer: Bloom filters are slower and use more memory.

DRAM is actually really slow. When you make a request to read DRAM, it returns a 64 byte cache line from that region in about 15 nanoseconds (in the best case). That's around 4.3 gigs/second random access. If you are accessing memory in a predictable pattern, the second block you request is returned in about 10 nanoseconds, and subsequent blocks can be returned in as fast as 3-4 nanoseconds. So, after the first few "slow" requests, you can read at a peak rate of roughly 21.3 gigs/second for predictable access patterns on high end machines.

Back to our case. We intersected a set of 5 million items against a set of 7.5 million items in 6 milliseconds. Doing the math... 4 bytes * (5m + 7.5m) / 6ms -> 8.3 gigs/second. So, we were within a factor of ~2-2.5x of maxing out the memory bandwidth available to the entire system with our 6ms intersection.

Let's pretend that we had already built a bloom filter, and let's even say that the math said that we only need 7 probes (the reality would probably be closer to 16 or so). At 15ns per probe, because bloom filters have unpredictably random access patterns, 7 probes per 5 million users in our input set, my math says that the intersection would take 525 milliseconds, which is 87 times slower than our intersection method.

But here's the other nasty bit of reality; constructing the bloom filter for that 5 million entry set (because we need to have bloom filter for all sets) takes at least twice as long as querying it. Why? Because to update 1 bit in the filter, you first need to read the cache line, then you need to update the bit in the register, then you need to write the data back. I know what you are thinking, you are thinking that your write-through cache will help you. But you are wrong. Because you are writing randomly to your bloom filter, you run out of cache very quickly, and the caching layers within your processor will quickly start blocking the processor from reading or writing to memory, because it's got a backlog of data to flush to memory that is limited to 15ns per random write. So with a (lower-bounded) 525ms to intersect, that's roughly 1.05 seconds to construct the bloom filter in the best case.

Meanwhile, the slow O(nlogn) standard C sort() finishes in 1.2 seconds, which is within spitting distance of the theoretically optimal bloom filter we just described. We also only sort once, but intersect thousands of times, so even if it did offer a modest performance advantage, it wouldn't be worth the performance penalty during intersection.

Another drawback with the bloom filter is memory. I know what you are thinking, you are thinking "well, with a 7 probe bloom filter, maybe you only need 2-3 bytes per user, instead of the 4 bytes per user". But in order to perform the intersection, you still need your list of users (sorted or not) in addition to the bloom filter, leaving you with 6-7 bytes per user.

Conclusion: bloom filters would be (80-160 times) slower to intersect, would use more memory, don't offer a significant construction time performance advantage (probably closer to 2x slower for a 16 probe bloom filter), and are only approximately correct.

The lesson you should learn

The reason why our custom solution was so much faster than Redis is primarily the memory access patterns and memory efficiency. Large sets in Redis have roughly a 60-80 byte/entry overhead on a 64 bit machine, most of which needs to be read to intersect one item with another. And because of the bucket + linked list (which is how Redis builds sets), intersection in Redis could read more than 60-80 bytes to intersect one item with another. Ours did so well because we reduced our space to 4 bytes per user (from 60-80), only ever read that 4 bytes, and ensured that all of our memory access patterns were sequential. With the practical realities of modern processors and memory, there is no faster way for single-processor set intersections.

If you want to see more posts like this, you can buy my book, Redis in Action from Manning Publications today!