Optimization

A while back I wrote a quick PHP script that, given the dimensions of an image and the target aspect ratio, it would compute a few dimensions in the target aspect ratio that required minimal cropping/editing to obtain. Content that it worked, I let it sit there and forgot about it until today when I found a low res image on /w/ that I wanted to make 4:3. (foreshadowing a wallpaper update?)

Looking at its code, I told myself there had to be a better way to calculate the nearest resolutions. In my haste to have a working solution I just took the easy way out and used loops that decremented/incrimented the width and height by one until it found something that fit the desired aspect ratio.

I figured it would be faster to rewrite it so it didn't use loops at all. Using the handy-dandy modulus operator, I rewrote the function so it just did straight calculations instead of stupidly looping. Since the most it ever has to incriment/decrement is within the modulus of the relevant portion of the aspect ratio, we can use the width modulus the aspect width to see exactly where we stand, the same for the height. In best-case, the modulus is zero and we just have to do one calculation. Worst-case it's nonzero and we have to do two.

The loop algorithm always calculated by increasing and decreasing both the height and the width, regardless of anything. By design it wouldn't loop if the value we started with was a multiple, but it didn't use any modulus to check. In fact, all the original algorithm got was the computed floating point representation of the aspect ratio, whereas the new one gets the separate width and height components of the aspect ratio and computes the floating point representation for ease of calculation later on. That and computing a value once and storing the result is faster than recomputing the same value four times.

Tested it with the new algorithm, and it works, with a bonus: It now does a minimal amount of redundant output elimination purely by design. Since we check to see if the modulus is zero, some but not all redundancy is eliminated. Perhaps I'll facepalm and realize how I can change it so that all redundant output is eliminated (without specifically checking post-calculation), but for now I'm satisfied.

Then I wondered just how much faster it really was. So I added in an option in the HTML form to let me select whether or not I wanted to compare the two algorithms, and wrote the code to calculate how long each one takes to execute. It's pretty simple, in PHP 5 you can just call microtime(true) before and after the function and then do a little math and call sprintf to format the result.

Here are the tests I did:

Best case test data:
Aspect ratio: 16:9
Width x Height: 1920x1080 (1920 / 1080 == 16 / 9)

Mixed case test data:
Aspect ratio: 16:9
Width x Height: 1920x720 (1920 % 16 == 0, 720 % 9 == 0, but 1920 / 720 != 16 / 9)

Worst case test data:
Aspect ratio: 16:9
Width x Height: 1928x725 (1928 % 16 == 8, 725 % 9 == 5, basically here the given dimensions are halfway between multiples of their relevant portions of the aspect ratio)

After running several tests it turns out my new algorithm is approximately 1.5-2x faster. I'll take that.

Oh and here's the script so you can play around with it.