我目前正在尝试更好地了解与内存/缓存相关的性能问题。我在某处读到，内存局部性对于读取比对写入更重要，因为在前一种情况下，CPU必须实际等待数据，而在后一种情况下，CPU可以将它们运送出去而忽略它们。
考虑到这一点，我进行了以下快速测试：我编写了一个脚本，该脚本创建了一个由N个随机浮点数和排列组成的数组，即一个以随机顺序包含数字0到N-1的数组。然后，它反复（1）线性读取数据数组，然后按排列给定的随机访问模式将其写回到新数组，或者（2）按排列顺序读取数据数组，然后将其线性写入新数组。
令我惊讶的是，（2）似乎始终比（1）快。但是，我的脚本有问题
该脚本是用python / numpy编写的。这是一种相当高级的语言，尚不清楚如何精确地实现读/写。
我可能没有适当地平衡这两种情况。
另外，下面的一些答案/评论表明我的最初期望不正确，并且根据cpu缓存的详细信息，这两种情况都可能更快。
我的问题是：
两者中的哪一个（如果有）应该更快？
什么是相对缓存概念？它们如何影响结果
初学者友好的解释将不胜感激。任何支持的代码都应该在C / cython / numpy / numba或python中。
可选地：
解释为什么绝对持续时间在问题规模上是非线性的（请参见下面的时序）。
解释我明显不足的python实验的行为。
供参考，我的平台是Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4。 Python版本是3.6.5。
这是我写的代码：
import numpy as np
from timeit import timeit
def setup():
global a, b, c
a = np.random.permutation(N)
b = np.random.random(N)
c = np.empty_like(b)
def fwd():
c = b[a]
def inv():
c[a] = b
N = 10_000
setup()
timeit(fwd, number=100_000)
# 1.4942631321027875
timeit(inv, number=100_000)
# 2.531870319042355
N = 100_000
setup()
timeit(fwd, number=10_000)
# 2.4054739447310567
timeit(inv, number=10_000)
# 3.2365565397776663
N = 1_000_000
setup()
timeit(fwd, number=1_000)
# 11.131387163884938
timeit(inv, number=1_000)
# 14.19817715883255
正如@Trilarion和@Yann Vernier指出的那样，我的代码片段未达到适当的平衡，因此我将其替换为
def fwd():
c[d] = b[a]
b[d] = c[a]
def inv():
c[a] = b[d]
b[a] = c[d]
d = np.arange(N)（我将两种方式都进行了混洗，以期减少试用缓存的影响）。我还用timeit替换了repeat，并将重复次数减少了10倍。
然后我得到
[0.6757169323973358, 0.6705542299896479, 0.6702114241197705] #fwd
[0.8183442652225494, 0.8382121799513698, 0.8173762648366392] #inv
[1.0969422250054777, 1.0725746559910476, 1.0892365919426084] #fwd
[1.0284497970715165, 1.025063106790185, 1.0247828317806125] #inv
[3.073981977067888, 3.077839042060077, 3.072118630632758] #fwd
[3.2967213969677687, 3.2996009718626738, 3.2817375687882304] #inv
因此，似乎仍然存在差异，但是它更加微妙，现在可以根据问题的大小来选择哪种方式。
参考方案
这是一个与现代处理器的体系结构功能密切相关的复杂问题，您的直觉是随机读取要比随机写入慢，因为CPU必须等待读取数据
未验证（大多数时间）。我将详细说明几个原因。
现代处理器非常有效地隐藏读取延迟
而内存写入比内存读取更昂贵
特别是在多核环境中
原因＃1现代处理器可以有效地隐藏读取延迟。
现代superscalar可以同时执行多条指令，并更改指令执行顺序（out of order execution）。
这些功能的首要原因是增加指令处理量，
最有趣的结果之一是处理器隐藏内存写入（或复杂运算符，分支等）的延迟的能力。
为了解释这一点，让我们考虑一个简单的代码，它将数组复制到另一个代码中。
for i in a:
c[i] = b[i]
处理器执行的一个已编译代码将以某种方式
#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc
（这太过简化了，实际代码更加复杂，必须处理循环管理，地址计算等，但是这种简单的模型目前就足够了）。
如问题所述，对于读取，处理器必须等待实际数据。实际上，1b需要1a提取的数据，并且只要1a未完成就无法执行。这样的约束称为依赖，可以说1b依赖于1a。依赖关系是现代处理器中的主要概念。依赖关系表示算法（例如，我将b写入c），必须绝对遵守。但是，如果指令之间不存在依赖关系，则处理器将尝试执行其他挂起的指令，以使操作管线始终保持活动状态。只要遵守依赖关系（类似于as-if规则），这可能会导致乱序执行。
对于所考虑的代码，高级指令2.和1.之间（或asm指令2a和2b与先前的指令之间）没有依赖性。实际上，最终结果甚至是相同的，是2.在1.之前执行，并且处理器将在1a和1b完成之前尝试执行2a和2b。 2a和2b之间仍然存在依赖关系，但是都可以发布。同样适用于3a。和3b。，依此类推。这是隐藏内存延迟的有力手段。如果出于某种原因2.，3和4.可以在1.加载其数据之前终止，则您甚至可能根本没有注意到任何减速。
该指令级并行性由处理器中的一组“队列”管理。
预留站RS中的待处理指令队列（最近的奔腾中的128型指令）。一旦指令所需的资源可用（例如指令1b的寄存器c1的值），该指令即可执行。
L1高速缓存之前的内存顺序缓冲区MOB中的未决内存访问队列。这是处理内存别名并确保在同一地址进行内存写入或加载时的顺序性所必需的（通常是64个加载，32个存储）
出于类似原因，在将结果写回寄存器（重排序缓冲区或168个条目的ROB）时，将强制执行序列的队列。
以及其他一些取指令处的队列，用于生成μop，缓存中的写入和未命中缓冲区等
在执行上一个程序的某一时刻，RS中将有许多待处理的存储指令，MOB中将有多个负载，而ROB中有待退役的指令。
一旦有数据可用（例如读取终止），就可以执行取决于指令的指令，从而释放队列中的位置。但是，如果没有终止发生，并且这些队列之一已满，则与此队列关联的功能单元将停顿（如果处理器缺少寄存器名称，则在发出指令时也会发生这种情况）。停顿是造成性能损失的原因，为了避免这种情况，必须限制队列填充。
这解释了线性和随机存储器访问之间的区别。
在线性访问中，由于更好的空间局部性，并且由于高速缓存可以使用常规模式预取访问以进一步减少访问次数，所以未命中的数量将减少；和//每当读取终止时，2 /将涉及一条完整的高速缓存行，并且可以释放几条待处理的加载指令，从而限制指令队列的填充。这样，处理器将一直处于忙碌状态，并且隐藏了内存延迟。
对于随机访问，未命中的次数会更高，并且在数据到达时只能处理一次加载。因此，指令队列将迅速饱和，处理器停顿，并且无法通过执行其他指令来隐藏内存等待时间。
为了避免队列饱和和停顿，必须在吞吐量方面平衡处理器体系结构。实际上，在处理器的某个执行阶段，通常会有数十条指令，而全局吞吐量（即，通过内存（或功能单元）满足指令请求的能力）是决定性能的主要因素。比其中一些待处理指令等待内存值的事实影响较小。
...除非您的依赖链较长。
当一条指令必须等待上一条指令的完成时，存在依赖性。使用读取结果是依赖项。当涉及到依赖链时，依赖可能是一个问题。
例如，考虑代码for i in range(1,100000): s += a[i]。所有的内存读取都是独立的，但是s中的累积有一个依赖链。在上一个终止之前，无法进行添加。这些依赖性将使保留站迅速填充并在管道中产生停顿。
但是读取很少涉及依赖链。仍然可以想象一下病理代码，其中所有读取都依赖于前一个读取（例如for i in range(1,100000): s = a[s]），但在实际代码中并不常见。问题出在依赖链，而不是事实，因为它是可读取的。对于像for i in range(1,100000): x = 1.0/x+1.0这样的与计算绑定相关的代码，情况将类似（甚至可能更糟）。
因此，除了在某些情况下之外，由于超标量输出或订单执行掩盖了延迟，因此计算时间与吞吐量的关系比与读取依赖性的关系更大。对于吞吐量，写比写要差。
原因2：内存写入（尤其是随机写入）比内存读取昂贵
这与caches的行为方式有关。高速缓存是快速内存，由处理器存储一部分内存（称为行）。高速缓存行目前为64个字节，并允许利用内存引用的空间局部性：一旦存储了一行，该行中的所有数据将立即可用。这里重要的方面是缓存和内存之间的所有传输都是行。
当处理器对数据执行读取时，缓存将检查数据所属的行是否在缓存中。如果不是，则从内存中获取该行，将其存储在缓存中，然后将所需的数据发送回处理器。
当处理器将数据写入内存时，高速缓存还会检查线路是否存在。如果该行不存在，则高速缓存无法将其数据发送到内存（因为所有传输都基于行），并且执行以下步骤：
高速缓存从内存中获取行并将其写入高速缓存行。
数据被写入高速缓存，并且整行被标记为已修改（脏）
当从高速缓存中禁止某行时，它将检查修改后的标志，如果该行已被修改，则将其写回到内存中（写回高速缓存）
因此，每次内存写入之前都必须先进行一次内存读取，以获取高速缓存中的行。这增加了一个额外的操作，但是对于线性写入来说并不是很昂贵。对于第一个写入的字，将发生高速缓存未命中和存储器读取，但是连续写入将仅涉及高速缓存并被命中。
但是，随机写入的情况则大不相同。如果未命中的次数很重要，则每个高速缓存未命中都意味着在从高速缓存中弹出该行之前先进行一次读取，然后执行少量写操作，这会大大增加写入成本。如果在单次写入后弹出一行，我们甚至可以认为一次写入是读取时间成本的两倍。
重要的是要注意，增加内存访问次数（读取或写入）会趋于使内存访问路径饱和，并全局减慢处理器与内存之间的所有传输速度。
无论哪种情况，写总是比读更昂贵。多核技术增强了这一方面。
原因3：随机写入会在多核中造成缓存未命中
不确定这是否真的适用于问题的情况。虽然numpy BLAS例程是多线程的，但我认为基本数组副本不是。但这是密切相关的，这也是写入成本更高的另一个原因。
多核的问题是要确保正确的cache coherence，以确保在每个核的高速缓存中正确更新由多个处理器共享的数据。这是通过诸如MESI之类的协议完成的，该协议会在写入之前更新缓存行，并使其他缓存副本无效（为所有权而读取）。
尽管问题的核心之间（或其并行版本）实际上没有共享任何数据，但请注意，该协议适用于高速缓存行。每当要修改高速缓存行时，都会从保存有最新副本的高速缓存行中复制它，在本地进行更新，并使所有其他副本无效。即使内核正在访问高速缓存行的不同部分。这种情况称为false sharing，它是多核编程的重要问题。
关于随机写入的问题，高速缓存行为64个字节，可以容纳8个int64，如果计算机具有8个内核，则每个内核将平均处理2个值。因此，存在重要的错误共享，这将减慢写入速度。
我们做了一些性能评估。它以C语言执行，以包括对并行化影响的评估。我们比较了5
处理大小为N的int64数组的函数。
只是b到c（c[i] = b[i]）的副本（由编译器使用memcpy()实现）
使用线性索引c[i] = b[d[i]]复制，其中d[i]==i（read_linear）
使用随机索引c[i] = b[a[i]]复制，其中a是随机索引
0..N-1的排列（read_random等同于原始问题中的fwd）
写线性c[d[i]] = b[i]其中d[i]==i（write_linear）
用c[a[i]] = b[i]随机写a
0..N-1的排列（write_random等同于问题中的inv）
代码已使用gcc -O3 -funroll-loops -march=native -malign-double编译
天空处理器。性能用_rdtsc()衡量，并且
每次迭代的周期数。该函数执行了几次（1000-20000个，具体取决于阵列大小），执行了10个实验，并保留了最短的时间。
数组大小从4000到1200000。所有代码均已通过openmp的顺序版本和并行版本进行了测量。
这是结果图。功能具有不同的颜色，顺序版本用粗线表示，而并行版本用细线表示。
直接复制（显然）最快，并且由gcc通过以下方式实现
高度优化的memcpy()。这是通过内存估算数据吞吐量的一种方法。它的范围从小矩阵的每次迭代0.8个周期（CPI）到大矩阵的2.0 CPI。
读取线性性能大约是memcpy的两倍，但是读取和写入有2次，而1次
读取和写入直接副本。更多的索引增加了一些依赖性。最小值为1.56 CPI，最大值为3.8 CPI。线性写入略长（5-10％）。
具有随机索引的读取和写入是原始问题的目的，应有较长的注释。这是结果。
size 4000 6000 9000 13496 20240 30360 45536 68304 102456 153680 230520 345776 518664 777992 1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785
小值（<10k）：L1缓存为32k，可以容纳4k uint64数组。请注意，由于索引的随机性，在大约1/8的迭代之后，L1高速缓存将完全填充随机索引数组的值（因为高速缓存行为64字节，并且可以容纳8个数组元素）。访问其他线性阵列时，我们将快速生成许多L1丢失，我们必须使用L2缓存。 L1缓存访问为5个周期，但它是流水线式的，每个周期可以提供几个值。 L2访问时间更长，需要12个周期。随机读取和写入的未命中量相似，但是我们发现，当数组大小较小时，我们将完全支付写入所需的两次访问。
中值（10k-100k）：L2缓存为256k，可以容纳32k int64数组。之后，我们需要转到L3缓存（12Mo）。随着大小的增加，L1和L2中的未命中数也会增加，因此计算时间也会相应增加。两种算法的未命中次数相似，这主要是由于随机读取或写入（其他访问是线性的，并且可以由缓存非常有效地预取）。我们检索了B.M.中已经提到的随机读取和写入之间的因子二。回答。写入的双重成本可以部分解释这一点。
大值（> 100k）：方法之间的差异逐渐减小。对于这些大小，大部分信息存储在L3缓存中。 L3大小足以容纳1.5M的整个阵列，并且不太可能弹出线。因此，对于写入而言，在初始读取之后，可以进行更多次写入而无需行弹出，并且减少了写入与读取的相对成本。对于这些大尺寸，还需要考虑许多其他因素。例如，缓存只能服务有限数量的未命中（典型值16），而当未命中的数量很大时，这可能是限制因素。
在并行omp版本上随机读取和写入一个字。除了较小的大小（随机索引数组分布在多个缓存中可能不是一个优势）之外，它们在系统上要快两倍左右。对于大尺寸文件，我们可以清楚地看到，由于错误共享，随机读取和写入之间的间隔增大了。
即使对于简单的代码，使用当前计算机体系结构的复杂性进行定量预测几乎是不可能的，甚至对行为的定性解释也很困难，并且必须考虑许多因素。如其他答案中所述，与python相关的软件方面也会产生影响。但是，尽管在某些情况下可能会发生这种情况，但在大多数情况下，人们不能认为由于数据相关性，读取会更昂贵。
Python sqlite3数据库已锁定 - python我在Windows上使用Python 3和sqlite3。我正在开发一个使用数据库存储联系人的小型应用程序。我注意到，如果应用程序被强制关闭（通过错误或通过任务管理器结束），则会收到sqlite3错误（sqlite3.OperationalError：数据库已锁定）。我想这是因为在应用程序关闭之前，我没有正确关闭数据库连接。我已经试过了： connectio…
Python:集群作业管理 - python我在具有两个阶段的计算群集（Slurm）上运行python脚本，它们是顺序的。我编写了两个python脚本，一个用于阶段1，另一个用于阶段2。每天早上，我检查所有第1阶段的工作是否都以视觉方式完成。只有这样，我才开始第二阶段。通过在单个python脚本中组合所有阶段和作业管理，是否有一种更优雅/自动化的方法？我如何知道工作是否完成？工作流程类似于以下内容：w…
numpy loadtxt单行/行作为列表 - python我只有一个数据文件，例如： 1.2 2.1 3.2 我使用numpy版本1.3.0 loadtxt加载它 a,b,c = loadtxt("data.dat", usecols(0,1,2), unpack=True) 输出是浮点数而不是数组 a = 1.2 我希望它将是： a = array([1.2]) 如果我读取了多行文件，则该文件…
Python-Excel导出 - python我有以下代码：import pandas as pd import requests from bs4 import BeautifulSoup res = requests.get("https://www.bankier.pl/gielda/notowania/akcje") soup = BeautifulSoup(res.cont…
Python:传递记录器是个好主意吗？ - python我的Web服务器的API日志如下：started started succeeded failed 那是同时收到的两个请求。很难说哪一个成功或失败。为了彼此分离请求，我为每个请求创建了一个随机数，并将其用作记录器的名称logger = logging.getLogger(random_number) 日志变成[111] started [222] start…