NEP 11 — 延迟的UFunc求值#

作者:

Mark Wiebe <mwwiebe@gmail.com>

Content-Type:

text/x-rst

创建时间:

2010-11-30

状态:

Deferred

摘要#

本NEP描述了一个为NumPy的UFuncs添加延迟求值的提案。这将允许Python表达式，例如“a[:] = b + c + d + e”，在所有变量的一次遍历中一次性求值，无需临时数组。由此产生的性能可能与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++ Library。一个最近创建的用于帮助编写表达式模板的库是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”（延迟使用计数变为一，NPY_DEFERRED_WASWRITEABLE **未**设置，因为“arr”是只读的）

  3. 销毁临时副本，导致“arr”变得可写

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

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

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

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

其他实现细节#

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

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

进一步优化#

与其保守地禁用延迟求值（当任何错误未设置为“ignore”时），不如让每个UFunc提供它可能生成的错误集合。然后，如果所有这些错误都被设置为“ignore”，即使其他错误未被设置为“ignore”，也可以使用延迟求值。

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

虽然我将延迟求值作为UFunc的特性来介绍，但它可以扩展到其他函数，例如dot()。例如，链式矩阵乘法可以重新排序以最小化中间结果的大小，或者类似“窥孔”优化器的传递可以搜索匹配优化BLAS/其他高性能库调用的模式。

对于非常大的数组操作，将LLVM等JIT集成到此系统中可能会带来巨大好处。UFuncs和其他操作将提供bitcode，这些bitcode可以内联并由LLVM优化器进行优化，然后执行。事实上，迭代器本身也可以用bitcode表示，允许LLVM在进行优化时考虑整个迭代。