NEP 11 — 延遲 UFunc 評估#

作者:

Mark Wiebe <mwwiebe@gmail.com>

內容類型:

text/x-rst

建立時間:

30-Nov-2010

狀態:

已延遲

摘要#

此 NEP 描述一項提案，旨在將延遲評估新增至 NumPy 的 UFuncs。這將允許像「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 而導致的意外情況，例如稍後使用延遲表達式時在令人驚訝的時間出現浮點警告或例外狀況。透過建議這種方法，希望可以避免使用者提出諸如「為什麼我的 print 陳述式會拋出除以零錯誤？」之類的問題。

提議的延遲評估 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 時，首先計算最新的延遲陣列。這可能會釋放對延遲表達式樹狀結構中包含的其他延遲陣列的參考，而這些陣列永遠不必計算。

進一步最佳化#

與其在未將任何錯誤設定為「ignore」時保守地停用延遲評估，不如讓每個 UFunc 提供一組它可能產生的錯誤。然後，如果所有這些錯誤都設定為「ignore」，即使其他錯誤未設定為「ignore」，也可以使用延遲評估。

一旦明確儲存表達式樹狀結構，就可以對其進行轉換。例如，add(add(a,b),c) 可以轉換為 add3(a,b,c)，或者 add(multiply(a,b),c) 可以使用 CPU 融合乘加指令在可用的情況下變成 fma(a,b,c)。

雖然我將延遲評估框定為僅適用於 UFuncs，但它可以擴展到其他函式，例如 dot()。例如，可以重新排序鏈式矩陣乘法以最小化中間值的大小，或者窺孔式最佳化器傳遞可以搜尋與最佳化 BLAS/其他高效能函式庫呼叫相符的模式。

對於真正大型陣列的操作，將 JIT（例如 LLVM）整合到此系統中可能會帶來很大的好處。UFuncs 和其他操作將提供位元碼，這些位元碼可以內聯在一起並由 LLVM 最佳化器最佳化，然後執行。實際上，迭代器本身也可以用位元碼表示，允許 LLVM 在執行最佳化時考慮整個迭代。