4

我正在创建一个处理线性代数的 python 扩展，并希望它尽可能快。

我有一个简单的 Vector 结构，我想在其中执行操作：

cdef struct Vec3:
    double x, y, z

目前，我的模块中的函数分为两种签名，第一种仅将输入作为参数并返回一个新向量，另一种将修改后的数据返回给一个名为out

cdef inline Vec3 vadd(Vec3* a, Vec3* b) nogil:
    cdef Vec3 out
    out.x = a.x + b.x
    out.y = a.y + b.y
    out.z = a.z + b.z
    return out

cdef inline void vadd(Vec3* a, Vec3* b, Vec3* out) nogil:
    out.x = a.x + b.x
    out.y = a.y + b.y
    out.z = a.z + b.z

我在许多示例中都看到了这两种方式，但不知道哪一种在速度方面更好。

它们是相同的还是在某些情况下使用一个比另一个有优势？

4

2 回答 2

2

无需过多详细说明，答案是：为代码的可读性或代码（或相关函数）的逻辑做最好的事情。

说它没有区别，这并不完全诚实 - 可能在某些情况下可以测量运行时间的不可忽略的差异 - 但很可能对您而言并非如此。

如果您期望，该函数将被内联 - 最后将完全没有区别：内联后优化器会将代码转换为相同的二进制文件（我在帖子末尾添加了一个示例来说明这一点）。内联是在这种情况下应该尝试实现的：它不仅可以节省调用开销，而且还可以进行其他方式无法实现的优化（这是一个简单的示例，内联的运行时间从O(n)到O(1)）。

如果代码不会被内联，那么结果取决于使用的 ABI - 但很可能，第二个版本将导致性能稍微更高的二进制文件 - 但在大多数情况下，优势是可以忽略不计的。

在这里，我看一下 64bit-Linux（它使用System V AMD64 - ABI）。Cython 会将您的示例转换为有效地遵循 C 代码：

struct Vec3{
    double x, y, z;
};

struct Vec3 vadd_v1(struct Vec3* a, struct Vec3* b){
    struct Vec3 out;
    out.x = a->x + b->x;
    out.y = a->y + b->y;
    out.z = a->z + b->z;
    return out;
}

void vadd_v2(struct Vec3* a, struct Vec3* b, struct Vec3* out){
    out->x = a->x + b->x;
    out->y = a->y + b->y;
    out->z = a->z + b->z;
}

当对其进行优化编译时，将导致以下汇编程序（这里稍微采取了一些措施以便能够更好地进行比较）：

vadd_v1:                     vadd_v2:
;out.x = a->x + b->x;        ;out.x = a->x + b->x;
  movsd   (%rsi), %xmm2        movsd   (%rdi), %xmm0
  addsd   (%rdx), %xmm2        addsd   (%rsi), %xmm0
  movsd   %xmm2, (%rdi)        movsd   %xmm0, (%rdx)

;out.y = a->y + b->y;        ;out.y = a->y + b->y;
  movsd   8(%rsi), %xmm1       movsd   8(%rdi), %xmm0
  addsd   8(%rdx), %xmm1       addsd   8(%rsi), %xmm0
  movsd   %xmm1, 8(%rdi)       movsd   %xmm0, 8(%rdx)

;out.z = a->z + b->z;        ;out.z = a->z + b->z;
  movsd   16(%rsi), %xmm0      movsd   16(%rdi), %xmm0
  addsd   16(%rdx), %xmm0      addsd   16(%rsi), %xmm0
  movsd   %xmm0, 16(%rdi)      movsd   %xmm0, 16(%rdx)

;return                      ;return
  movq    %rdi, %rax
  ret                          ret

类型的对象Vec3是 MEMORY 类型，因为它有 3 个双值（整个算法可以在 ABI 中查找）。因此，在第一个版本中，调用者负责为返回值分配内存并在“隐藏指针”中传递其地址%rdi

如您所见，第一个版本有一个额外movq %rdi, %rax的，因为返回对象的指针必须在 中返回，如ABI%rax所指定：

  1. 如果该类型具有 MEMORY 类，则调用者为返回值提供空间并将此存储的地址传递到 %rdi 中，就好像它是函数的第一个参数一样。实际上，这个地址变成了一个“隐藏的”第一个参数。此存储不得与通过此参数以外的其他名称对被调用者可见的任何数据重叠。

    返回时 %rax 将包含调用者在 %rdi 中传入的地址。

显然，第二个版本效率更高，但这条指令真的重要吗？

但是，也有一些示例，其中第一个版本会更有效。

如果我们使用两个双精度结构而不是三个结构 - 第一个版本将需要更少的指令：结果不再是 MEMORY 类型，并将在寄存器中传递（再次进行比较）：

vadd_v1:                       vadd_v2:
 ;out.y = a->y + b->y;           ;out.y = a->y + b->y;
   movsd   (%rdi), %xmm0            movsd   (%rdi), %xmm0
   addsd   (%rsi), %xmm0            addsd   (%rsi), %xmm0
                                    movsd   %xmm0, (%rdx)

 ;out.y = a->y + b->y;           ;out.y = a->y + b->y;
   movsd   8(%rdi), %xmm1           movsd   8(%rdi), %xmm0
   addsd   8(%rsi), %xmm1           addsd   8(%rsi), %xmm0
                                    movsd   %xmm0, 8(%rdx)

 ;return                         ;return
   ret                              ret

但是，可能会产生额外费用，具体取决于调用相关函数的方式。当一个人返回值而不是传递一个指针时——应该坚持下去：

struct Vec3 use_v1(struct Vec3 *in){
        return vadd_v1(in, in);
}

导致汇编器不复制返回的数据：

use_v1:
        pushq   %r12
        movq    %rsi, %rdx
        movq    %rdi, %r12
        call    vadd_v1
        movq    %r12, %rax
        popq    %r12
        ret

尽管

void use_v2(struct Vec3 *in, struct Vec3 *out){
    *out = vadd_v1(in, in);
}

会导致 

use_v2:
        pushq   %rbx
        movq    %rdi, %rdx
        movq    %rsi, %rbx
        movq    %rdi, %rsi
        subq    $32, %rsp
        movq    %rsp, %rdi
        call    vadd_v1
        movdqu  (%rsp), %xmm0       ;copying
        movq    16(%rsp), %rax      ;copying
        movups  %xmm0, (%rbx)       ;copying
        movq    %rax, 16(%rbx)      ;copying
        addq    $32, %rsp
        popq    %rbx
        ret

的结果vadd_v1在堆栈上创建，然后复制到指针out。必须这样做，因为out不能作为“隐藏指针”传递给vadd_v1，因为编译器不知道是否out在某处使用vadd_v1（例如作为全局变量）。有一个SO-question，它更详细地查看了上述功能。

除非存在编译器错误，否则使用指针版本的优势：您可以非常确定没有发生复制。

这是一个示例，当内联时，两个版本都会导致相同的二进制文件：

double sum_v1(struct Vec3* a){
    struct Vec3 d = vadd_v1(a,a);
    return d.x;
}

double sum_v2(struct Vec3* a){
    struct Vec3 d;
    vadd_v2(a, a, &d);
    return d.x;
}

编译到同一个汇编程序时会导致：

sum_v1/sum_v2:
        movsd   (%rdi), %xmm0
        addsd   %xmm0, %xmm0
        ret
于 2019-08-02T23:40:35.573 回答
1

@ead 已经写了一个很好的答案，它触及了您展示的两个示例功能的程序集的复杂性（从来不知道 Godbolt，必须记住那个网站！）。在返回结构（选项 A）和对传入的结构指针（选项 B ）进行操作之间进行选择时，可以考虑一些其他方面。

从可用性的角度来看，选项 A 具有潜在的好处，因为您可以将操作链接在一起。想象一下，如果您想将Vec3 a,Vec3 b和加Vec3 c在一起并将结果存储在Vec3 d. 以下是每个选项的外观：

#Assume these have some values
cdef Vec3 a, b, c, d

#Option A
d = vadd(&vadd(&a, &b), &c)

#Option B
vadd(&a, &b, &d)
vadd(&d, &c, &d)

但是，由于函数不是属于对象类的方法，因此这种链接的大部分视觉优势都丢失了，因此您不会获得类似d = a.add(b).add(c).

支持选项 B的另一个考虑因素是，如果您在循环中进行数千次计算并且在计算中有一些临时Vec3结构，您可以在循环之外创建这些结构一次并在循环中重用它们，而不是每次在vadd函数调用中重新创建临时结构并复制结果。

要考虑的第三个问题是如何在 python 中包装这些 cython 操作。如果您对选项 A使用类似的方法来cdef class PyVec3代替对象，那么现在的挑战是您现在需要返回一个 python 对象。PyVec3因此，每次调用此包装函数时，您都必须在返回时创建对象时与 GIL 进行交互。在循环中执行此类操作变得非常昂贵。对于对象的选项 B ，仅对cdef class此类对象进行操作不会调用 GIL。当然，您可以将 python 包装器的结构与底层 cython/C 代码不同，但包装中的良好对称性会丢失。由于这些原因，我选择了选项Bmath3d我的pyorama图书馆的一部分。

于 2019-08-03T02:51:09.467 回答