In a previous post I talked about some optimization I needed to do to get PCA to run on a corpus of images. In that post, I tended to blur the lines between fast and memory efficient. The relationship between speed of execution and memory usage is more complicated, but for the specific problem I was running into, swap space usage caused a decrease in computation speed. With heavy use of swap space, the memory pipeline grows in length. Reducing memory usage shortens the memory pipeline and has a clear impact on computation speed. In the jargon, this involved turning an IO bound process back into a CPU bound process.
There are other possible relationships between speed and memory efficiency. For example, you can trade memory for speed, or speed for memory. Lookup tables of precomputed values, for instance, trade away memory for speed (a lookup is faster than a value recomputation). The reverse, where values are recomputed as necessary, trades CPU cycles for memory.
Every time I read stories like this (http://news.ycombinator.com/item?id=3929507) I can’t help but wonder. I mean, it seems like the technology already exists for simple encrypted friend-2-friend email/chat/voice. If not, I’m sure a smart programmer with basic crypto knowledge and access to existing toolsets could put one together in something like one weekend and poof goes the entire law enforcement wiretap agenda.
But I suppose the issue is not that smart criminals can avoid wiretaps, it’s that dumb criminals can’t. There’s a more disturbing option, which is that criminals aren’t really the target at all…
Yesterday I spent some time trying to optimize a rather large PCA-type transformation for some images. The task was such that if I wasn’t careful, I’d run out of physical memory and end up using swap space (where the physical disk is used for memory).
I found out that numpy dot products can, for some reason I don’t yet understand, blow up the memory usage. So can pickle and/or bz2 file compression. Eventually I found a reasonably memory/time efficient approach using Cython + memmap and a few other tricks.
Ultimately, this entire problem was sort of a side show. If my data didn’t fit in memory (with little to spare) to start with I would have considered some sort of sub-sampling approach. But the fact that the data did fit in memory, and a careful consideration of the linear algebra I needed to do led me to believe I could do what I needed to do in the remaining memory, made for a compelling optimization problem.
It’s hard to turn away from an interesting problem, even if there are simpler solutions that take less time and avoid the issue entirely.
You can find my updated PCA code here: https://github.com/stober/pca.