与最后一个索引相比,numpy数组的访问时间受到最后一个索引的影响更大

Question

这是对我之前的问题的回答的后续跟进将数千个图像读入一个大的numpy数组的最快方法.

在第2.3章"ndarray的内存分配"中,Travis Oliphant写了以下关于如何在内存中访问C-ordered numpy数组的索引.

...按顺序移动计算机内存,最后一个索引首先递增,然后是倒数第二个索引,依此类推.

这可以通过对两个第一个或最后两个索引的二维数组的访问时间进行基准测试来确认(对于我的目的,这是加载500个大小为512x512像素的图像的模拟):

import numpy as np

N = 512
n = 500
a = np.random.randint(0,255,(N,N))

def last_and_second_last():
    '''Store along the two last indexes'''
    imgs = np.empty((n,N,N), dtype='uint16')
    for num in range(n):
        imgs[num,:,:] = a
    return imgs

def second_and_third_last():
    '''Store along the two first indexes'''
    imgs = np.empty((N,N,n), dtype='uint16')
    for num in range(n):
        imgs[:,:,num] = a
    return imgs

基准

In [2]: %timeit last_and_second_last()
136 ms ± 2.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %timeit second_and_third_last()
1.56 s ± 10.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

到现在为止还挺好.但是,当我沿最后一个和最后一个维度加载数组时,这几乎和将它们加载到最后两个维度一样快.

def last_and_third_last():
    '''Store along the last and first indexes'''
    imgs = np.empty((N,n,N), dtype='uint16')
    for num in range(n):    
        imgs[:,num,:] = a
    return imgs

基准

In [4]: %timeit last_and_third_last()
149 ms ± 227 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

• 为什么last_and_third_last()我的速度last_and_second_last()比较接近second_and third_last()？
• 有什么方法可视化最后一个索引在访问速度方面比最后一个索引更重要的原因？

Answer 1

我将尝试说明索引，而不涉及处理器缓存等的细节。

让我们创建一个具有独特元素值的小型 3d 数组：

In [473]: X = np.mgrid[100:300:100,10:30:10,1:4:1].sum(axis=0)
In [474]: X
Out[474]: 
array([[[111, 112, 113],
        [121, 122, 123]],

       [[211, 212, 213],
        [221, 222, 223]]])
In [475]: X.shape
Out[475]: (2, 2, 3)

ravel将其视为一维数组，并向我们展示这些值在内存中的布局方式。（顺便说一下，这是默认C顺序）

In [476]: X.ravel()
Out[476]: array([111, 112, 113, 121, 122, 123, 211, 212, 213, 221, 222, 223])

当我在第一个维度上建立索引时，我得到 2*3 个值，这是上面列表的一个连续块：

In [477]: X[0,:,:].ravel()
Out[477]: array([111, 112, 113, 121, 122, 123])

索引而不是在最后给出 4 个值，从数组中选择 - 我已经添加..以突出显示

In [478]: X[:,:,0].ravel()
Out[478]: array([111,.. 121,.. 211,.. 221])

中间的索引给了我 2 个连续的子块，即X.

In [479]: X[:,0,:].ravel()
Out[479]: array([111, 112, 113,.. 211, 212, 213])

用stridesandshape计算numpy可以同时访问Xin（大约）中的任何一个元素。在这种X[:,:,i]情况下，这就是它必须做的。这 4 个值“分散”在数据缓冲区中。

但是如果它可以访问连续的块，例如 in X[i,:,:]，它可以将更多的操作委托给低级编译和处理器代码。随着X[:,i,:]这些块不太大，但仍可能大到可以有很大的不同。

在您的测试用例中，[n,:,:]在 512*512 元素块上迭代 500 次。

[:,n,:] 必须将该访问划分为 512 个块，每个块 512 个。

[:,:,n] 必须进行 500 x 512 x 512 次单独访问。

我想知道使用 with 是否会uint16夸大效果。在另一个问题中，我们刚刚展示了计算float16速度要慢得多（高达 10 倍），因为处理器（和编译器）已调整为可以处理 32 位和 64 位数字。如果处理器被调整为移动 64 位数字块，那么移动一个孤立的 16 位数字可能需要大量额外的处理。这就像从文档中逐字复制粘贴一样，当逐行复制时，每个副本需要更少的击键。

确切的细节隐藏在处理器、操作系统和编译器以及numpy代码中，但希望这能让您了解为什么中间情况更接近最佳情况而不是最坏情况。

在测试中 - 设置imgs为a.dtype在所有情况下都会稍微减慢速度。所以'uint16'不会引起任何特殊问题。

为什么 `numpy.einsum` 使用 `float32` 比使用 `float16` 或 `uint16` 运行得更快？