In September I wrote about my intention to develop a web application to share my photos. I made good progress on it throughout September and early October, but for various reasons I haven’t been able to work on it much in the past month or so. Last weekend, though, I was able to solve some blocking issues which were preventing me from doing an alpha release. Those being dealt with, I’ve now got a few of my albums up at photos.mlindgren.ca; take a look and leave a comment if you have any feedback.

I haven’t released the source code yet as there’s still a great deal of work to be done, and I’m generally of the belief that dumping a bunch of unfinished, messy code on Github with the hope that the community will sort it out is of little benefit to anyone. My goal at this point is to do a beta release in a two to three months or so and release the code at that point. That timeline is anything but firm, though. This project is turning out to be much more work than I expected (as projects are wont to do), and I expect to be fairly busy over the next couple months.

Anyway, with the alpha version up and running, this seems like a good opportunity to reflect on some of the issues I’ve faced that complicated the project, and on what remains to be done.

Wand and the OOM Killer

I mentioned in my post on Python imaging libraries that I’m using Wand to resize and transform uploaded photos. It’s very convenient and easy to use, and from a maintainability and ease of use perspective I much prefer using Python bindings for ImageMagick to shelling out to the ImageMagick executable. One of my goals for this project is that other people should be able to install it on their own servers with relative ease, and I suspect relying on ImageMagick executables for image processing would lead to cross-platform and configuration issues.

But, Wand is not yet a mature library and it has some significant issues of its own. First and foremost, when I started using it it had some major memory leaks. I found and fixed more than 10 leaks and submitted a pull request which was merged into the main repository—however, there hasn’t yet been an official release including my fixes yet, so pip installs and downloads from the Wand website will still include those leaks.

I’m not sure if I got all of the leaks or if more still remain. The ones I fixed were discovered mostly through ad-hoc testing and reading the code. I’ve been running my app for several days now and the memory consumption when it’s idle has stayed flat, so I believe I’ve removed at least the most common leaks, but I haven’t had a chance to sit down with Valgrind yet and run the Wand unit tests through it to make sure that I got all of the leaks. I’ll have to do that before I do any sort of public release of my software; I don’t want to rely on a leaky library.

Beyond the leaks, I ran into another memory issue which proved problematic: resizing photographs can use a great deal of memory, which is extremely limited on a reasonably-priced VPS. I have limited knowledge about image processing in general and ImageMagick in particular, but I’m not aware of any resizing algorithms which can operate directly on compressed image data, and if any such algorithms exist, ImageMagick doesn’t use them. That being the case, to resize an image, the entire image has to be loaded into memory decompressed. For an 8 megapixel photograph at 24 bits per pixel, that means allocating approximately 183MB of memory.

On a 512MB VPS, this means that trying to resize three images concurrently—or even sequentially in some cases, since Python isn’t guaranteed to immediately relinquish allocated memory to the operating system when objects resident in that memory are “deleted”—practically guarantees that the process will be killed by the OOM killer.

This goes hand in hand with another complication, which is that resizing images is too slow to be done in the same server thread that’s handling requests and generating responses. For each image that’s uploaded, I save several different sizes for different purposes, and due to the aforementioned memory constraints I can’t even resize them concurrently. Resizing each image several times in the responding thread drastically reduces throughput for the client since it incurs a significant wait time for the server to process each image after it’s uploaded.

Enter Subprocess

So here’s the solution I’ve come up with for the time being, and I’m very unsure whether or not it’s actually a good solution, so please do let me know in the comments if there’s a better way to do this. When a new image is uploaded, the responding thread saves the image in the appropriate directory and adds it to the database, but does not resize it. For each of the sizes that the image needs to be resized to, it adds a task to a synchronous queue. The queue is consumed by a different thread which runs throughout the lifetime of the application. That thread maintains a (thread-local) queue of subprocesses with a configurable maximum length. When a new resizing task is consumed, if there is room in the subprocess queue, a new subprocess is spawned to resize the image. Otherwise, the thread joins the subprocess at the front of the queue so as to block until there’s room to spawn a new subprocess. The exit code of completed processes is checked to ensure that the resize was successful; in case of failure, the task is re-added to the back of the task queue.

This guarantees that the application server itself will never be killed by the OOM killer since it uses minimal memory. It never has to load images into memory; all of that is done in the resizing subprocesses. By configuring the maximum number of concurrent subprocesses, one can scale this solution according to available resources: if you have plenty of RAM, you can resize many images concurrently and get through the queue faster, or if you have very little, you can limit the queue to one or two processes to minimize the chance that anything will be OOM killed.

The subprocess spawning notwithstanding, this is a pretty standard task queue model, so you might be wondering why I didn’t use something like Celery in conjunction with a real message queue. It comes down to minimizing the number of external dependencies and maximizing ease of use. My project already depends on a number of libraries which will have to be installed by users. To the greatest extent that I can do so without compromising on features, I want to avoid complicating the installation further by adding more dependencies. Celery is particularly difficult to install as it requires installing and configuring a broker and managing processes for both the broker and Celery itself. Were I writing a large-scale service and maintaining a single backend for hundreds of users, it would probably be the right choice, but as I am writing software for users to install on their own servers, it is probably not.

This method works fairly well and it’s the best I’ve come up with so far, but something about it makes it feel more like a hack than a well thought out and robust solution. I also wonder if it defeats the purpose of using Wand in the first place; I use it for very little other than resizing, and since I’m going to the trouble of spawning subprocesses to do that, perhaps it would actually be better to just directly invoke the ImageMagick binaries. As mentioned above, I have concerns about what impact that would have in different environments, but I haven’t really validated those concerns; they’re just hunches.

The Road Ahead

So I’ve got a workable, if not perfect, solution to one of the biggest problems I encountered… but as I mentioned previously, there’s still much work to be done. Here are a few (but not all) of the things I’d like to do before I release anything publicly:

• Lots of UI work. Right now the app works very poorly on phones and iPads. I also need to figure out how to make certain features more discoverable, and although I’m happy with how albums look right now, there are still some extra touches that I want to add which I haven’t yet been able to (because CSS and HTML suck.)
• Better administrative tools. Uploading works great, but I have very barebones interfaces for editing albums right now. There is currently no means of rotating a photo from the editing interface (although doing so should almost never be necessary since the app automatically rotates images which have EXIF orientation data.)
• Mirroring and proxying to cloud storage services such as Azure and S3. VPS resources are very expensive; extra disk space on some popular hosts runs around a dollar per gigabyte per month. That’s ten times the cost of disk space on the cloud storage services I’ve looked at. Cloud-hosted images might also improve load speeds for visitors.
• Comments. This one is pretty big, obviously, but I haven’t added it yet because I can’t decide on how best to handle it. I’d like to avoid writing my own comment system and requiring potential commenters to sign up for yet another account. (I’d use Persona for commenter identification and authentication just as I do for the admin login, but very few people currently have Persona accounts or even know what it is.) I like Disqus, but I’m not sure it would integrate well with the minimalist interface I’ve designed.
• Geotagging and maps. I’m already reading GPS data from EXIF tags where available, but now I need to do something with it. I’d like to add the ability to manually add locations to photos and albums, and to have a map that shows where photos were taken.

Those five items represent maybe a quarter to a third of the work I still have planned, so to repeat myself again, there’s a lot of work to do. But I’m very happy with the progress I’ve made so far, and I feel confident that I can get this finished. It’s just a matter of when.

I’m not usually much enamoured with interview-style programming puzzles because I find that a lot of them are actually more akin to math problems, trivial to implement once you figure out the salient mathematical property.  I think I have a decent intuition for math, and I certainly took enough math courses in high school and college to give me a solid foundation in the fundamentals of algebra, geometry, statistics, calculus, etc., but I’m not confident enough in my math skills to be entirely comfortable being judged by my ability to exercise them.

There are some programming puzzles I really enjoy, though.  This evening I happened across one such puzzle, via Eevee’s Twitter: ”implement a strlen() function in C that, when compiled, would not contain any conditional branches.”  (The page contains solutions, so don’t read the orange text if you want to try this yourself.)  This is exactly the kind of puzzle I like; it’s fun to think about, reasonably challenging, and requires knowledge of language features combined with creative thinking.

My solution is below, but I’d recommend that you go give this a try yourself before you read on.

Alright, ready? Here’s my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>

int mystrlen(char *str, int count);
int mystrlenret(char *str, int count);

int (*funcs[2])(char *, int) = {mystrlen, mystrlenret};

int mystrlen(char *str, int count)
{
  return funcs[(int)(!*str)](++str, ++count);
}

int mystrlenret(char *str, int count)
{
  return count - 1;
}

int main(int argc, char *argv[])
{
  printf("%i\n", mystrlen(argv[argc - 1], 0));
}

As you can see, the solution is actually very simple, but there are a couple of tricks necessary to make it work. First of all, you obviously can’t use a loop to count the characters because a loop requires a conditional jump to either terminate or continue. You could still use a loop-like construct such as goto, but that only reframes the problem; you still need to make a decision about when to jump out.

So, the problem can basically be reduced to this: how can you make a decision without using a conditional? Well, you can index into an array of possibilities using some property that you can derive from your input. In this case, the most important property is that the characters can be grouped into two sets: terminating characters (i.e. '\0') and non-terminating characters (all others). On that basis, our array of possibilites can consist of two function pointers, one which continues recursively and the other which terminates.

The only problem remaining is how to group the characters, again without using conditionals. My first thought here was actually to divide the character by itself, in which case all non-terminating characters would be 1, and the null terminator would be… oh, a divide-by-zero error. I quickly dismissed that thought and realized that binary not is a simpler way to map the characters. However, Eevee came up with what I think is a very clever and quite unorthodox solution involving division by handling the SIGFPE generated by the division by zero and using the handler to change an unconditional jump address.

I’d recommend also checking out the solutions provided in the original post; all three of them are a bit more elegant than mine, if perhaps a bit more difficult to understand. (In particular, the count parameter that I use is superfluous, although I don’t consider the difference particularly important since it can easily be hidden in my solution using a macro or helper function.)

Since my solution isn’t significantly different from those presented in the original post, I wanted to go a bit further and take a look at the performance implications of not using conditionals. Yeah, yeah, premature optimization is the root of all evil and all that—I’m just doing this out of curiosity; regardless of the results, I would never go this far out of my way to avoid a conditional jump in a real program, nor would I recommend doing so to anyone else. I decided to compare my solution above against a naïve implementation with a while loop; comparing it against strlen() from string.h would be pretty meaningless because it would be linked against a precompiled library which, for all I know, could be hand-optimized. So here’s the code I’m using instead:

1
2
3
4
5
6

int mystrlen(char *c)
{
  int len = 0;
  while(*c++ != 0) len++;
  return len;
}

And here’s how I’m timing the functions…

1
2
3
4
5
6
7
8
9
10
11
12

struct timeval start;
struct timeval end;
volatile int n;

gettimeofday(&start, NULL);
for(int i = 0; i < 100000; ++i)
  n = mystrlen(argv[argc - 1]);
gettimeofday(&end, NULL);

printf("Elapsed: %ld sec %ld usec\n",
       (long) end.tv_sec - start.tv_sec,
       (long) end.tv_usec - start.tv_usec);

I’m assigning the result to a volatile int to ensure that even when the code is optimized, the compiler won’t completely optimize out the function call. So, first, predictions: anyone who has taken a computer architecture course will tell you that conditional jumps can be very expensive because of the recovery the CPU has to do if the branch is mispredicted. However, branch predictors typically have very high accuracy, and there’s also a significant overhead involved in putting the parameters and return address on the stack when a function is called. Therefore, I predict that in that with no compiler optimization, the while loop will be faster.

…And, it is. Running each function in a loop 100,000 times on a 23-character string, the average over five trials was 28,699 µsec for the non-conditional version and 9,012 µsec for the while loop. Using a fixed string will cause the branch predictor to have near-perfect accuracy in the while loop version, so there might be a slight difference if I used a large array of strings of randomized lengths, but I doubt it would be significant.

But what if we let the compiler (llvm-gcc in this case) optimize it? I don’t know enough about compiler optimization in general or llvm-gcc in particular to predict what will happen here. The non-conditional strlen() is tail recursive so the compiler will optimize out the extra function calls at -O2 and above, but what will be optimized beyond that I really don’t know.

As it turns out, compiling at -O3 and running 100,000 times on the same 23-character string, the non-conditional function took an average of 11,182 µsec over five trials. That’s a significant improvement, but it’s still slower than the unoptimized while loop, so it obviously won’t beat that. And indeed, the optimized while loop takes only 3,072 µsec.

(With apologies to Eevee, of whom I am a great fan.)

So, I’m working on a photo album app written in Python.  I’m using Python because, well, I love it.  I think it’s the perfect language for web development; it’s simple and very readable, and ample syntactic sugar and just the right mix of procedural and functional features almost completely eliminate tedious boilerplate.  As a trivial example for those who have never used Python, consider:

1
2

db_tags = dict([(tag.name, tag) for tag in
                db.session.query(db.MetadataTag).filter_by(source = 'exif')])

What I’m doing here is grabbing all of the EXIF tags I know about out of my database with SQLAlchemy (also awesome, by the way), and creating a dictionary which maps each tag’s name to the corresponding ORM object; I can find the ORM object simply with db_tags[tag_name], which lets me easily and efficiently insert new tag values as I read EXIF data from a photo.  This isn’t particularly difficult to do in any other language; as I said, it’s a trivial example.  But consider how much more verbose the code would be: PHP, which is still the most popular language for web applications despite being an incorrigible pile of garbage, doesn’t have list comprehensions.  I don’t even want to think about how many lines of code this would take in Java; additionally, while I’m unfamiliar with them in general, I suspect Java ORMs require the use of generics to a painful extent (i.e. more than not at all).  In Python it only takes one SLOC, without sacrificing any readability.^{1, 2}

So, Python’s pretty great. But like all languages, it does have a few problems. The one I have had the most difficulty with in my current project is that third party library support is somewhat lacking in some important areas; specifically, there aren’t many good options for reading and manipulating images. The most popular library seems to be the Python Imaging Library, PIL. It’s easy enough to install and provides a passable set of core features, but doesn’t go much beyond that.  For instance, none of the various camera raw formats seem to be supported, which I consider a fairly important feature for my photo album; I’d very much like be able to upload original raws and have the application automatically convert them to JPEGs for me.  Additionally, it doesn’t provide much in the way of convenience methods for cropping and resizing images.  ImageMagick has a very nice means of specifying cropping and resizing geometry with various aspect ratio-preserving (or not) behaviour, and I wanted to be able to leverage something similar for my app so that I could quickly prototype with various size options.

Given that ImageMagick provides most of the functionality I want that PIL lacks, it seemed like a good option, but it’s a C library and Python doesn’t yet have mature bindings for it.  It’s getting there, though!  I decided to go with Wand, which is a fork of python-magickwand.  It has a nice high-level API, but also provides direct access to most of the low-level MagickWand APIs, making it fairly flexible.  When I first found it, it did not have support for the nice geometry specifications I wanted to use, but being an open source project I was able to patch that in.  Version 0.2.2 will include my patch, which provides the Image.transform method for easy cropping and resizing.  Eevee is also working on a Python imaging library, which is promising, but it’s still a work in progress.

Unfortunately Wand doesn’t yet support retrieving EXIF, IPTC or XMP metadata from images, which is another requirement for me.  ImageMagick does support EXIF at least, and that’s on the roadmap for Wand, but implementing a high-level interface for EXIF tags is a bigger task than I have time for at the moment.  That meant that I had to turn to another library to retrieve metadata.  pyexiv2, a Python binding for the exiv2 C++ library, initially looked promising.  Unfortunately I discovered that it’s not installable via any Python package manager; it must be built from source (via a build system I’ve never even heard of, and I’m familiar with more than a few build systems), unless a binary is provided for your platform by the project maintainers (i.e. you are on Debian, Ubuntu, Fedora or Windows).

My project already has more dependencies than I’m entirely comfortable with; one of the reasons that Python only has modest adoption as a web application platform despite being a great language for the task is that it doesn’t have a kitchen sink-style standard library, and third-party libraries require separate installation.  In general I consider that a good thing; I’d rather have a well-designed standard library than a gigantic mishmash of inconsistently named global functions.  However, it does make deployment a little more complex.  So far I’ve managed to stick to libraries which can be installed in one step using well-known package managers, so the setup procedure for my app should not be too arduous.  Adding pyexiv2 as a dependency and thereby including an entirely different build system in the process would likely have complicated the installation procedure to the point that no actual ordinary humans would ever use my application.  That’s something I want to avoid, if possible.

For now I have settled for exif-py.  It only handles EXIF tags, not IPTC or XMP, which is disappointing because I really wanted to support multiple metadata formats.  It’s a pure Python library in a single file, though, so I can just include with my distribution.  It’s easy to use and gets the job done, so it will have to do for now.  I’m hoping that pyexiv2 will show up in pip (a Python package manager) at some point, though.  [Updated September 16, 2012: I’ve discovered that exif-py is broken in at least a couple significant ways, so I’m kind of back at square one for handling metadata.  exif-py seems to be unable to detect EXIF data in some files that have it.  Additionally, the strings that it translates orientation codes to are not consistent with each other, so they’re basically wrong.  I’ve informed the maintainers of these issues, but I don’t have time to fix them myself.]

The process of trying to find a good imaging package for Python and ultimately settling for two separate libraries which still don’t quite do everything I want has made it clear to me that third party library support for Python still has a way to go.  Hopefully the situation will improve as adoption of the language increases.  I’m happy to do my part, both through contributions to open source libraries such as Wand, and by building apps using Python to bolster the ecosystem.  I hope that by demonstrating what’s possible with Python as a web application platform, I can help convince new web developers to build their applications using Python as well… which provides yet more reason for me to be diligent about finishing my photo album app!

¹ Okay, the dict function is perhaps not the most explicit. Check the docs once, though, and it’s very easy to understand.
² Ruby would doubtless be similarly concise, and it seems like a nice language in my limited experience, but I find its syntax and distinction between “symbols” and strings to not be to my taste.