Deferred UFunc Evaluation

作者:Mark Wiebe <mwwiebe@gmail.com>
内容类型:text / x-rst
创建:2010年11月30日

Abstract

该NEP描述了对NumPy的UFuncs添加延迟评估的建议。这将允许像“a [:] = b + c + d + e”这样的Python表达式在一次性通过所有变量的过程中求值,没有临时数组。生成的性能可能与numexpr库相当,但具有更自然的语法。

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

Motivation

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来即时评估。

Example Python Code

这里是如何可能在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.

我相信在文档中应该推荐的用法是将deferred状态保留为默认值,除非在评估可以从中受益的大型表达式时。

# calculations

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

# more calculations

这将避免由于始终保持延迟使用True而导致的意外情况,例如浮动点警告或异常在令人惊讶的时间,稍后使用延迟表达式。用户问题,如“为什么我的打印语句抛出一个除以零的错误?”希望可以通过推荐这种方法来避免。

Proposed Deferred Evaluation API

对于延迟评估工作,C API需要知道它的存在,并且能够在必要时触发评估。ndarray将获得两个新的标志。

NPY_ISDEFERRED

表示此ndarray实例的表达式求值已推迟。

NPY_DEFERRED_WASWRITEABLE

只能在PyArray_GetDeferredUsageCount(arr) &gt; 0时设置。它表明当arr在延迟表达式中第一次使用时,它是一个可写数组。如果设置了这个标志,调用PyArray_CalculateAllDeferred()会使arr可写。

注意

如果NPY_DEFERRED和NPY_DEFERRED_WASWRITEABLE对于Python是可见的,或者应该访问来自python触发器的标志触发PyArray_CalculateAllDeferred如果必要?

API将扩展一些功能。

int PyArray_CalculateAllDeferred()

此函数强制所有当前的延迟计算发生。

例如,如果错误状态设置为ignore all,并且np.seterr({all ='raise'}),这将改变已经延迟的表达式发生的情况。因此,在改变错误状态之前,应该评估所有现有的延迟数组。

int PyArray_CalculateDeferred(PyArrayObject * arr)

如果'arr'是延迟数组,为其分配内存并评估延迟表达式。如果'arr'不是延迟数组,只返回成功。返回NPY_SUCCESS或NPY_FAILURE。

int PyArray_CalculateDeferredAssignment(PyArrayObject * arr, PyArrayObject * out) / t0>

如果'arr'是延迟数组,将延迟表达式计算为'out',并且'arr'仍然是延迟数组。如果'arr'不是延迟数组,将其值复制到输出中。返回NPY_SUCCESS或NPY_FAILURE。

int PyArray_GetDeferredUsageCount(PyArrayObject * arr)

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

Python API将扩展如下。

numpy.setdeferred(state)

启用或禁用延迟评估。True意味着总是使用延迟评估。False表示不使用延迟评估。无意味着如果错误处理状态设置为忽略所有内容,则使用延迟评估。在NumPy初始化时,延迟状态为None。

返回先前的延迟状态。

numpy.getdeferred()

返回当前的延迟状态。

numpy.deferredstate(state)

用于延迟状态处理的上下文管理器,类似于numpy.errstate

Error Handling

错误处理是延迟评估的棘手问题。如果NumPy错误状态是{all ='ignore'},可能会合理地引入延迟评估作为默认值,但是如果一个UFunc可以引发一个错误,对于后来的'print'语句抛出异常而不是导致错误的实际操作。

什么可能是一个好的办法是默认情况下启用延迟评估只有当错误状态设置为忽略所有,但允许用户控制与'setdeferred'和'getdeferred'函数。True意味着总是使用延迟评估,False意味着永远不使用它,None意味着仅在安全时使用它(即错误状态设置为忽略所有)。

Interaction With UPDATEIFCOPY

NPY_UPDATEIFCOPY文档说明:

数据区表示一个(行为良好的)副本,当删除此数组时,该副本的信息应该传回原始。

这是一个特殊的标志,如果这个数组表示一个拷贝,因为用户在PyArray_FromAny中需要某些标志,并且拷贝必须由其他数组组成(并且用户要求在这种情况下设置这个标志) 。base属性然后指向“misbehaved”数组(设置为read_only)。当具有此标志集的数组被解除分配时,它将其内容复制回“错误的”数组(如果必要的话),并将“错误的”数组重置为NPY_WRITEABLE。如果“misbehaved”数组不是NPY_WRITEABLE开始,则PyArray_FromAny将返回一个错误,因为NPY_UPDATEIFCOPY是不可能的。

UPDATEIFCOPY的当前实现假定它是以这种方式使可写标志。the的唯一机制。这些机制必须意识到彼此才能正常工作。这里有一个例子,它们可能会出错:

  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,表示数组将被更新,并在将来的某个时刻写入。如果延迟评估机制在任何操作数中看到此标志,则触发立即评估。

Other Implementation Details

当创建一个延迟数组时,它获得对UFunc的所有操作数的引用,以及UFunc本身。“DeferredUsageCount”对于每个操作数递增,并且随后在计算延迟表达式或延迟数组被销毁时递减。

将按创建顺序跟踪对所有延迟数组的弱引用的全局列表。当调用PyArray_CalculateAllDeferred时,将首先计算最新的延迟数组。这可能会释放对包含在延迟表达式树中的其他延迟数组的引用,然后不必计算。

Further Optimization

当任何错误未设置为“忽略”时,不是保守地​​禁用延迟评估,每个UFunc可以给出它生成的一组可能的错误。然后,如果所有这些错误都设置为“忽略”,则可以使用延迟评估,即使其他错误未设置为忽略。

一旦表达式树被显式地存储,就可以对其进行变换。例如,使用(a,b,c)可以将add(add(a,b),c)转换为add3(a,b,c) CPU融合乘法指令(如果可用)。

虽然我已经将延迟评估框架化为UFuncs,但它可以扩展到其他函数,如dot()。例如,链式矩阵乘法可以被重新排序以最小化中间体的大小,或窥视孔样式优化器通路可以搜索匹配优化的BLAS /其他高性能库调用的模式。

对于真正大型数组的操作,将类似LLVM的JIT集成到此系统中可能是一个很大的好处。UFunc和其他操作将提供位码,它们可以内联在一起并由LLVM优化器优化,然后执行。事实上,迭代器本身也可以用bitcode表示,允许LLVM在做优化时考虑整个迭代。