Fast Fourier transform in x86 assembly
I always cringe when developers compare compiler-optimized C to &#x27;hand rolled&#x27; assembly. In the dawning age of SAT-based program synthesis and vectorization-aware superoptimizers, it&#x27;s extremely anachronistic. It only shows a lack of awareness that in reality your job as a programmer is not to give instructions to a machine, but to provide enough help that a machine can create its own instructions better than you can.<p>For example, let&#x27;s take one critical function here: bit reversal. The C code provided (renamed variables so it&#x27;s easy to consistently compare) has an impressive speedup just going from -O1 to higher optimization levels. And then, on top of that speedup with a decent optimizer, we can again halve the amount of time spent in this function by providing better intentions to the compiler which allow it to perform automatic vectorization. Note this is all in standard C, and makes the code simpler to understand (and maintain) by humans as well.<p><pre><code>    uint64_t reverse_slow(uint64_t n, uint64_t k)
    {
            uint64_t r, i;
            for (r = 0, i = 0; i &lt; k; ++i, n &gt;&gt;= 1)
                    r = (r &lt;&lt; 1) | (n &amp; 1);
            return r;
    }

    uint64_t reverse_fast(const uint64_t n, const uint64_t k)
    {
            uint64_t r, i;
            for (r = 0, i = 0; i &lt; k; ++i)
                    r |= ((n &gt;&gt; i) &amp; 1) &lt;&lt; (k - i - 1);
            return r;
    }
</code></pre>
Lesson: do your job as a human and provide guidance, let the machines do their job at taking your advice and running wild with creativity. It helps you both become more effective.