列方式和V行明智总和:为什么我看不到使用NumPy的差异？

Question

我已经测试了一个使用numpy(第20/57页)在这个讲座 [pytables]中演示的示例.

据说,这a[:,1].sum()需要9.3毫秒,而a[1,:].sum()只需要72美元.

我试图重现它,但没有这样做.我错误地测量了吗？或者自2010年以来NumPy的情况发生了变化？

$ python2 -m timeit -n1000 --setup \ 
  'import numpy as np; a = np.random.randn(4000,4000);' 'a[:,1].sum()' 
1000 loops, best of 3: 16.5 usec per loop

$ python2 -m timeit -n1000 --setup \ 
  'import numpy as np; a = np.random.randn(4000,4000);' 'a[1,:].sum()' 
1000 loops, best of 3: 13.8 usec per loop

$ python2 --version
Python 2.7.7
$ python2 -c 'import numpy; print numpy.version.version'
1.8.1

虽然我可以测量第二个版本的好处(据说因为numpy使用C风格的行排序而减少了缓存未命中),但我没有看到pytables贡献者所说的那么大的差异.

此外,当使用列V行求和时,似乎我看不到更多缓存未命中.

---

编辑

• 到目前为止,我的洞察力是我timeit以错误的方式使用模块.使用相同数组(或数组的行/列)的重复运行几乎肯定会被缓存(我有32KiBL1数据缓存,所以一条线适合内部:) 4000 * 4 byte = 15k < 32k.

• 在@alim 的答案中使用单个循环(nloop=1)和十个试验的脚本nrep=10,并改变随机数组的大小(n x n)我正在测量

   n   row/us col/us    penalty col
   1k     90    100         1
   4k    100    210         2
  10k*   110    350         3.5
  20k*   120   1200        10
  

  *n=10k和更高版本不再适合L1d缓存.

我仍然不确定如何追踪原因,因为perf有关更快的行总和的缓存未命中率(有时甚至更高的速率).

Perf 数据:

nloop = 2并且nrep=2,所以我预计一些数据仍然在缓存中......对于第二次运行.

行总和 n=10k

 perf stat -B -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses,L1-dcache-prefetches,cycles,instructions,branches,faults,migrations ./answer1.py 2>&1 | sed 's/^/    /g'
row sum:    103.593 us
 Performance counter stats for './answer1.py':
          25850670      cache-references                                             [30.04%]
           1321945      cache-misses              #    5.114 % of all cache refs     [20.04%]
        5706371393      L1-dcache-loads                                              [20.00%]
          11733777      L1-dcache-load-misses     #    0.21% of all L1-dcache hits   [19.97%]
        2401264190      L1-dcache-stores                                             [20.04%]
         131964213      L1-dcache-store-misses                                       [20.03%]
           2007640      L1-dcache-prefetches                                         [20.04%]
       21894150686      cycles                    [20.02%]
       24582770606      instructions              #    1.12  insns per cycle         [30.06%]
        3534308182      branches                                                     [30.01%]
              3767      faults
                 6      migrations
       7.331092823 seconds time elapsed

列总和 n=10k

 perf stat -B -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses,L1-dcache-prefetches,cycles,instructions,branches,faults,migrations ./answer1.py 2>&1 | sed 's/^/    /g'
column sum: 377.059 us
 Performance counter stats for './answer1.py':
          26673628      cache-references                                             [30.02%]
           1409989      cache-misses              #    5.286 % of all cache refs     [20.07%]
        5676222625      L1-dcache-loads                                              [20.06%]
          11050999      L1-dcache-load-misses     #    0.19% of all L1-dcache hits   [19.99%]
        2405281776      L1-dcache-stores                                             [20.01%]
         126425747      L1-dcache-store-misses                                       [20.02%]
           2128076      L1-dcache-prefetches                                         [20.04%]
       21876671763      cycles                    [20.00%]
       24607897857      instructions              #    1.12  insns per cycle         [30.00%]
        3536753654      branches                                                     [29.98%]
              3763      faults
                 9      migrations
       7.327833360 seconds time elapsed

---

EDIT2 我想我已经了解了一些方面,但我认为这个问题尚未得到解答.目前我认为这个求和示例根本没有透露任何有关CPU缓存的信息.为了消除numpy/python的不确定性,我尝试用Cperf进行求和,结果在下面的答案中.

Answer 1

我不认为你的复制尝试有什么问题，但请记住这些幻灯片是 2010 年的，从那时起 numpy 已经发生了很大的变化。根据numpy 发布的日期，我猜测 Francesc 可能使用的是 v1.5。

使用此脚本对行 v 列总和进行基准测试：

#!python

import numpy as np
import timeit

print "numpy version == " + str(np.__version__)

setup = "import numpy as np; a = np.random.randn(4000, 4000)"

rsum = "a[1, :].sum()"
csum = "a[:, 1].sum()"

nloop = 1000
nrep = 3

print "row sum:\t%.3f us" % (
    min(timeit.repeat(rsum, setup, repeat=nrep, number=nloop)) / nloop * 1E6)
print "column sum:\t%.3f us" % (
    min(timeit.repeat(csum, setup, repeat=nrep, number=nloop)) / nloop * 1E6)

我发现 numpy v1.5 的列总和速度下降了约 50%：

$ python sum_benchmark.py 
numpy version == 1.5.0
row sum:        8.472 us
column sum:     12.759 us

与您正在使用的 v1.8.1 相比，速度减慢了约 30%：

$ python sum_benchmark.py 
numpy version == 1.8.1
row sum:        12.108 us
column sum:     15.768 us

有趣的是，在最近的 numpy 版本中，这两种类型的缩减实际上都变慢了一些。我必须更深入地研究 numpy 的源代码才能准确理解为什么会出现这种情况。

更新

• 根据记录，我在四核 i7-2630QM CPU @ 2.0GHz 上运行 Ubuntu 14.04（内核 v3.13.0-30）。两个版本的 numpy 均使用 GCC-4.8.1 进行 pip 安装和编译。
• 我意识到我原来的基准测试脚本并不完全是不言自明的 - 您需要将总时间除以循环数（1000）才能获得每次调用的时间。
• 取重复次数的最小值而不是平均值也可能更有意义，因为这更有可能代表执行时间的下限（在此基础上，您会因后台进程等而获得可变性）。

我已经相应地更新了上面的脚本和结果

我们还可以通过为每个调用创建一个全新的随机数组来消除跨调用缓存的任何影响（时间局部性） - 只需设置nloop为 1 和nrep一个相当小的数字（除非您真的喜欢观看油漆干燥），比如 10。

nloop=1，nreps=10在 4000x4000 阵列上：

numpy version == 1.5.0
row sum:        47.922 us
column sum:     103.235 us

numpy version == 1.8.1
row sum:        66.996 us
column sum:     125.885 us

这有点像，但我仍然无法真正复制弗朗西斯科幻灯片所显示的巨大效果。不过，也许这并不令人惊讶——效果可能非常依赖于编译器、体系结构和/或内核。