NEP 11 — 延迟的 UFunc 评估#

作者:

Mark Wiebe <mwwiebe@gmail.com>

内容类型:

text/x-rst

创建日期:

2010年11月30日

状态:

已推迟

摘要#

本 NEP 描述了一个向 NumPy 的 UFunc 添加延迟评估的提案。这将允许像“a[:] = b + c + d + e”这样的 Python 表达式在一次遍历所有变量时进行单次评估，无需临时数组。由此产生的性能可能与 *numexpr* 库相当，但语法更自然。

这个想法与 UFunc 错误处理和 UPDATEIFCOPY 标志有一些交互，影响了设计和实现，但结果是允许 Python 用户以最小的努力使用延迟评估。

动机#

NumPy 的 UFunc 执行方式会导致大型表达式的性能不佳，因为会分配多个临时变量，并且输入会经过多次遍历。*numexpr* 库可以通过在小型的缓存友好块中执行，并按元素评估整个表达式，从而在此类大型表达式上超越 NumPy。这使得每个输入只需遍历一次，这对缓存来说显著更好。

为了了解如何在不更改 Python 代码的情况下在 NumPy 中获得这种行为，可以考虑 C++ 的表达式模板技术。这些技术可以相当随意地使用向量或其他数据结构重新排列表达式，例如

A = B + C + D;

可以转换为等价于

for(i = 0; i < A.size; ++i) {
    A[i] = B[i] + C[i] + D[i];
}

这是通过返回一个知道如何计算结果的代理对象而不是返回实际对象来完成的。对于现代 C++ 优化编译器，生成的机器代码通常与手写循环相同。有关此示例，请参阅 Blitz++ 库。一个更近期创建的用于帮助编写表达式模板的库是 Boost Proto。

通过在 Python 中使用返回代理对象的相同思想，我们可以动态地实现相同的功能。返回的对象是一个未分配缓冲区的 ndarray，并且拥有在需要时计算自身所需的所有知识。当一个“延迟数组”最终被评估时，我们可以使用由所有操作数延迟数组组成的表达式树，从而有效地即时创建一个新的 UFunc 进行评估。

Python 代码示例#

这可能在 NumPy 中使用的方式如下。

# a, b, c are large ndarrays

with np.deferredstate(True):

    d = a + b + c
    # Now d is a 'deferred array,' a, b, and c are marked READONLY
    # similar to the existing UPDATEIFCOPY mechanism.

    print d
    # Since the value of d was required, it is evaluated so d becomes
    # a regular ndarray and gets printed.

    d[:] = a*b*c
    # Here, the automatically combined "ufunc" that computes
    # a*b*c effectively gets an out= parameter, so no temporary
    # arrays are needed whatsoever.

    e = a+b+c*d
    # Now e is a 'deferred array,' a, b, c, and d are marked READONLY

    d[:] = a
    # d was marked readonly, but the assignment could see that
    # this was due to it being a deferred expression operand.
    # This triggered the deferred evaluation so it could assign
    # the value of a to d.

不过，可能会有一些令人惊讶的行为。

with np.deferredstate(True):

    d = a + b + c
    # d is deferred

    e[:] = d
    f[:] = d
    g[:] = d
    # d is still deferred, and its deferred expression
    # was evaluated three times, once for each assignment.
    # This could be detected, with d being converted to
    # a regular ndarray the second time it is evaluated.

我认为文档中应该推荐的用法是保持延迟状态为默认值，除非在评估可以从中受益的大型表达式时。

# calculations

with np.deferredstate(True):
    x = <big expression>

# more calculations

这将避免因始终保持延迟使用为 True 而导致的意外情况，例如在稍后使用延迟表达式时出现浮点警告或异常。希望通过推荐这种方法，可以避免用户提出“为什么我的打印语句会抛出除零错误？”之类的问题。

提议的延迟评估 API#

要使延迟评估正常工作，C API 需要了解其存在，并能够在必要时触发评估。ndarray 将获得两个新标志。

NPY_ISDEFERRED

指示此 ndarray 实例的表达式评估已延迟。

NPY_DEFERRED_WASWRITEABLE

仅当 PyArray_GetDeferredUsageCount(arr) > 0 时才能设置。它表明当 arr 首次在延迟表达式中使用时，它是一个可写数组。如果设置了此标志，调用 PyArray_CalculateAllDeferred() 将使 arr 再次可写。

注意

问题

NPY_DEFERRED 和 NPY_DEFERRED_WASWRITEABLE 是否应该对 Python 可见，或者从 Python 访问这些标志时是否应该在必要时触发 PyArray_CalculateAllDeferred？

API 将通过一些函数进行扩展。

int PyArray_CalculateAllDeferred()

此函数强制执行所有当前延迟的计算。

例如，如果错误状态设置为忽略所有错误，并且 np.seterr({all=’raise’})，这将改变已延迟表达式的行为。因此，在更改错误状态之前，应评估所有现有的延迟数组。

int PyArray_CalculateDeferred(PyArrayObject* arr)

如果“arr”是一个延迟数组，则为其分配内存并评估延迟表达式。如果“arr”不是延迟数组，则直接返回成功。返回 NPY_SUCCESS 或 NPY_FAILURE。

int PyArray_CalculateDeferredAssignment(PyArrayObject* arr, PyArrayObject* out)

如果“arr”是一个延迟数组，则将延迟表达式评估到“out”中，并且“arr”仍然是一个延迟数组。如果“arr”不是延迟数组，则将其值复制到 out 中。返回 NPY_SUCCESS 或 NPY_FAILURE。

int PyArray_GetDeferredUsageCount(PyArrayObject* arr)

返回有多少个延迟表达式使用此数组作为操作数的计数。

Python API 将扩展如下。

numpy.setdeferred(state)

启用或禁用延迟评估。True 表示始终使用延迟评估。False 表示从不使用延迟评估。None 表示如果错误处理状态设置为忽略所有错误，则使用延迟评估。在 NumPy 初始化时，延迟状态为 None。

返回先前的延迟状态。

numpy.getdeferred()

返回当前的延迟状态。

numpy.deferredstate(state)

一个用于延迟状态处理的上下文管理器，类似于 numpy.errstate。

错误处理#

错误处理是延迟评估的一个棘手问题。如果 NumPy 错误状态设置为 {all=’ignore’}，那么将延迟评估作为默认行为可能是合理的，但是如果一个 UFunc 能够引发错误，那么在后续的‘print’语句中抛出异常而不是导致错误的实际操作，将会非常奇怪。

一个好的方法是默认只在错误状态设置为忽略所有错误时启用延迟评估，但允许用户通过“setdeferred”和“getdeferred”函数进行控制。True 意味着始终使用延迟评估，False 意味着从不使用，而 None 意味着只在安全时（即错误状态设置为忽略所有错误时）使用。

与 UPDATEIFCOPY 的交互#

NPY_UPDATEIFCOPY 文档说明：

数据区域表示一个（行为良好的）副本，当此数组被删除时，其信息应被传回原数据。

这是一个特殊标志，如果此数组表示因用户在 PyArray_FromAny 中要求某些标志而创建的副本，并且必须对某些其他数组进行复制（并且用户要求在此类情况下设置此标志）时，则设置此标志。然后，base 属性指向“行为不当”的数组（该数组被设置为只读）。当设置了此标志的数组被释放时，它会将内容复制回“行为不当”的数组（如果需要则进行类型转换），并将“行为不当”的数组重置为 NPY_WRITEABLE。如果“行为不当”的数组最初不是 NPY_WRITEABLE，那么 PyArray_FromAny 将返回错误，因为 NPY_UPDATEIFCOPY 将不可能实现。

UPDATEIFCOPY 的当前实现假设它是唯一以这种方式操作可写标志的机制。这些机制必须相互感知才能正常工作。以下是一个它们可能出错的示例：

  1. 使用 UPDATEIFCOPY 创建“arr”的临时副本（“arr”变为只读）

  2. 在延迟表达式中使用“arr”（延迟使用计数变为 1，NPY_DEFERRED_WASWRITEABLE 未设置，因为“arr”是只读的）

  3. 销毁临时副本，使“arr”变为可写

  4. 写入“arr”会破坏延迟表达式的值

为了解决这个问题，我们使这两个状态互斥。

  • UPDATEIFCOPY 的使用会检查 NPY_DEFERRED_WASWRITEABLE 标志，如果设置了该标志，则在继续之前调用 PyArray_CalculateAllDeferred 以刷新所有延迟计算。

  • ndarray 获得一个新标志 NPY_UPDATEIFCOPY_TARGET，表示该数组将在未来某个时候被更新并变为可写。如果延迟评估机制在任何操作数中看到此标志，它将触发即时评估。

其他实现细节#

当创建延迟数组时，它会获取 UFunc 所有操作数以及 UFunc 本身的引用。“DeferredUsageCount”会为每个操作数递增，并在计算延迟表达式或销毁延迟数组时递减。

系统会跟踪所有延迟数组的弱引用全局列表，按创建顺序排列。当调用 PyArray_CalculateAllDeferred 时，最新创建的延迟数组会首先计算。这可能会释放延迟表达式树中包含的其他延迟数组的引用，这些数组随后就无需再计算。

进一步优化#

并非在任何错误未设置为“忽略”时保守地禁用延迟评估，每个 UFunc 可以提供其可能生成的一组错误。然后，如果所有这些错误都设置为“忽略”，即使其他错误未设置为忽略，也可以使用延迟评估。

一旦表达式树被明确存储，就可以对其进行转换。例如，add(add(a,b),c) 可以转换为 add3(a,b,c)，或者 add(multiply(a,b),c) 可以使用 CPU 的融合乘加指令（如果可用）变为 fma(a,b,c)。

虽然我将延迟评估仅限于 UFunc，但它可以扩展到其他函数，例如 dot()。例如，可以重新排序链式矩阵乘法以最小化中间体的大小，或者窥孔式优化器遍可以搜索与优化 BLAS/其他高性能库调用匹配的模式。

对于超大型数组的操作，将 LLVM 等 JIT 集成到该系统中可能会带来巨大的好处。UFunc 和其他操作将提供比特码，这些比特码可以一起内联并由 LLVM 优化器优化，然后执行。实际上，迭代器本身也可以用比特码表示，允许 LLVM 在进行优化时考虑整个迭代过程。