python-pillow/Pillow — pull request #977 by homm (2014-10-26 17:06:55+00:00)
Title: Stretch optimization

This request speeds up main Pillow functional: image resizing. It also includes changes from #970.

## Main part

I've changed the traversal order of the pixels.

**Old**: There are two passes: horizontal and vertical stretch. In horizontal pass pixels are iterated from left to right first, then from top to bottom. That allows to calculate coefficients for each row only once, but is very inefficient for CPU cache. In vertical pass the order of traversal is changed: from top to bottom first, then from left to right, but calculation of each pixel of destination image requires pixels from different lines of source image.

**New**: Stretch always works in horizontal direction, pixels are iterated from top to bottom first, then from left to right. Calculation of each pixel in destination image requires only pixels from the same line of source image. CPU cache is used as efficiently as possible. Coefficients for each column are calculated in advance and stored separately, which prevents overheads. For vertical stretch image is transposed and stretched in horizontal direction again. Then it is transposed again to match the original image. Transposition is also made in effective for the CPU cache way: in block of 64 pixels (16kb).

## Other optimizations

Effective cache usage allows other optimizations. In common this is using of integer numbers insted of floats when possible. Also, huge boost was given by bands loop unrolling.

## Benchmarks

I've tested performance before and after this changes. Also i've tested GraphicsMagick 1.3.18 with following filters: `antialias ` = `lanczos`, `bicubic` = `catrom`, `bilinear` = `triangle`.

Source image: http://www.apple.com/imac-with-retina/5k.html

Filter | Destination size | GM | Before | After
-------|------------------|------|--------|-------
**Antialias** | 2048×1152 | 0.88 | 1.016 | 0.421
| 320×240 | 0.65 | 0.473 | 0.225
**Bicubic** | 2048×1152 | 0.64 | 0.840 | 0.326
| 320×240 | 0.37 | 0.326 | 0.154
**Bilinear** | 2048×1152 | 0.42 | 0.650 | 0.237
| 320×240 | 0.19 | 0.184 | 0.082