Mr-Dave/motion — pull request #42 by aklomp (2014-10-06 21:55:13+00:00)
Title: Add optimized SSE2 routines for bottleneck functions

This pull request provides SSE2 vectorized implementations of `alg_update_reference_frame()` and `alg_noise_tune()`. Profiling with Callgrind on my Atom server showed that the first was the most expensive single function call. Rewriting it in branchless SSE2 code cuts Motion's load average roughly in half for me. Per-function benchmarking shows a speedup of around 2× for `alg_update_reference_frame()`, and around 4× for `alg_noise_tune()`. Results differ across hardware and compilers, but always show significant speedup.

The plain functions have been lifted out of `alg.c` and placed in the new `alg/` subdirectory, along with their SSE2 versions. In `alg.c`, the preprocessor chooses between including plain or SSE2 functions at compile time. This is perhaps not in line with the rest of the codebase, but made it possible to build a test harness around the functions that checks their correctness and does performance benchmarks. This harness can be found in alg/tests.

My website has a [writeup](http://www.alfredklomp.com/programming/sse-motion) of how I converted `alg_update_reference_frame()` to branchless code. It demonstrates how to derive the logic step by step, and is a kind of giant comment on the code. Hopefully it will help in reviewing the code for correctness.

This code took quite some time to write, but probably deserves more real-world testing than it's had so far. All comments welcome!