c - x86汇编中用于Mandelbrot循环的高效复杂算术

Question

考虑以下程序:

for i=1 to 10000000 do
  z <- z*z + c

其中 z和 c是复数。

使用x87 vs SSE和单精度vs double 算法，此程序的有效x86汇编器实现是什么？

编辑我知道我可以用另一种语言编写并相信编译器可以为我生成最佳的机器代码，但是我这样做是为了学习如何自己编写最佳的x86汇编程序。我已经看过 gcc -O2生成的代码了，我猜想还有很多改进的余地，但是我不擅长亲自编写最佳的x86汇编程序，因此我在这里寻求帮助。

Answer 1

您本身不需要在汇编程序中执行此操作-您可以通过内部函数使用SSE来实现高效的实现，尤其是如果您可以使用单精度的话。

temp.re = z.re * z.re - z.im * z.im;
temp.im = 2.0 * z.re * z.im;
z.re = temp.re + c.re;
z.im = temp.im + c.im;

如果适本地对输入 vector 进行混洗，则可以在一条指令( _mm_mul_ps)中获得所有乘法，而在第二条指令( _mm_hadd_ps)中获得加法。
如果需要 double ，则可以应用相同的通用原理，但是需要两个乘法和两个水平加法。
请注意，大多数现代x86 CPU都有两个标量FPU，因此在SSE中获得 double 的好处可能不值得-单精度绝对可以取胜。

这是一个使用SSE的初始工作实现-我认为现在或多或少已经调试-性能并没有比用gcc -O3编译的标量代码好得多，因为gcc很好地为此生成了SSE代码:

static Complex loop_simd(const Complex z0, const Complex c, const int n)
{
    __m128 vz = _mm_set_ps(z0.im, z0.re, z0.im, z0.re);
    const __m128 vc = _mm_set_ps(0.0f, 0.0f, c.im, c.re);
    const __m128 vs = _mm_set_ps(0.0f, 0.0f, -0.0f, 0.0f);
    Complex z[2];
    int i;

    for (i = 0; i < n; ++i)
    {
        __m128 vtemp;

        vtemp = _mm_shuffle_ps(vz, vz, 0x16); // temp = { z.re, z.im, z.im, z.re }
        vtemp = _mm_xor_ps(vtemp, vs);        // temp = { z.re, -z.im, z.im, z.re }
        vtemp = _mm_mul_ps(vtemp, vz);        // temp = { z.re * z.re, - z.im * z.im, z.re * z.im, z.im * z.re }
        vtemp = _mm_hadd_ps(vtemp, vtemp);    // temp = { z.re * z.re - z.im * z.im, 2 * z.re * z.im, ... }
        vz = _mm_add_ps(vtemp, vc);           // temp = { z.re * z.re - z.im * z.im + c.re, 2 * z.re * z.im + c.im, ... }
    }
    _mm_storeu_ps(&z[0].re, vz);
    return z[0];
}

请注意，内部循环仅是6条SSE指令(实际上应该是5条)+循环本身的一些内务处理:

L4:
    movaps  %xmm0, %xmm1
    shufps  $22, %xmm0, %xmm1
    xorps   %xmm3, %xmm1
    mulps   %xmm1, %xmm0
    haddps  %xmm0, %xmm0
    addps   %xmm2, %xmm0
    incl    %eax
    cmpl    %edi, %eax
    jne L4
L2: