Now *this* is interesting


I needed to compare some images for something at work and have been trying a few different approaches.  Since I wrote the application that’s using it in Go, and since this was going to be called tens of thousands of times, I was looking for a Go library rather than something I’d have to fork off a bunch.  I ended up implementing a couple of libraries, and one of these was a near-line-for-line clone of the pdiff application. Anyway, this is all just backdrop; the real craziness is this:

Here’s my code.  Again, I’ve done almost nothing to this except perform the nearly trivial translation from Yee’s clearly-written C code to Go.  I introduced minimal Go idioms.  I am using Go’s standard image library rather than Yee’s custom one that uses the FreeImage library.

1199)src/autocompare % time ../../bin/pdiff a.png c.png
images are visually different; 49949 pixels differ
../../bin/pdiff a.png c.png  20.32s user 0.28s system 100% cpu 20.429 total
 Here’s the original:
1200)src/autocompare % time ~/pdiff/perceptualdiff a.png c.png
FAIL: Images are visibly different
49948 pixels are different
~/pdiff/perceptualdiff a.png c.png  18.88s user 0.06s system 99% cpu 18.941 total
That’s a 7.3% difference. I am surprised at how close to the C version the Go version is.  My code is here, and you can compare it yourself to the original (link above).

The algorithm is effectively allocating a bunch of big-ish arrays and iterates over one of them performing a fair amount of calculations. There are a fair number of function calls, and the math is limited to logs, powers, tan, and the regular suspects +-/*.  I make no claims, and a whole bunch of caveats: I didn’t do rigorous benchmarking (although, the results are consistent across several runs), and I’ve already said I did minimal Go-ification.  I did no additional optimization on my code.  I didn’t even break it up to take advantage of Go’s awesome goroutines.  I am using Go 1.0.2.

If I had to guess, I’d say there are three probable explanations:
  1. The FreeImage library is horribly inefficient (or way less efficient than Go’s standard image library)
  2. Despite the fact that the code looks mostly like calculations, most of the time is spent in allocating arrays and this is normalizing the times (although, I’d expect to see more time in system in that case)
  3. Go 1.0.2 is actually pretty close to C these days, for some tasks
That said, caveat lector.  I’m just reporting an observation; I haven’t spent any real time analyzing this.

Copyright © Sean Elliott Russell

comments powered by Disqus