为什么处理排序数组比处理未排序数组快?

java c++ performance optimization branch-prediction 匿名 | 2020-02-02 19:53:46

这是一段C++代码,显示了一些非常奇怪的行为。出于某种奇怪的原因,对数据进行排序神奇地使代码几乎快了6倍:

#include 
#include
#include
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}

如果没有
std::sort(data, data + arraySize);
,代码将在11.54秒内运行。
对于排序后的数据,代码将在1.93秒内运行。

最初,我认为这可能只是语言或编译器的异常,所以我尝试了Java:
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}

并得到了一个类似但不那么极端的结果。
我的第一个想法是排序会将数据带到缓存中,但后来我觉得这有多傻,因为数组是刚刚生成的。
发生了什么?
为什么处理排序数组比处理未排序数组快?
代码正在总结一些独立的术语,因此顺序应该无关紧要。


本站提供【Linux疑难问题解决】50元起 ,【爬虫开发】200元起。欢迎咨询QQ:376667689 点击这里给我发消息



26 回答


31296


你是分支预测失败的受害者。
什么是分支预测?
考虑一个铁路枢纽:
图片由Mecanismo,通过Wikimedia Commons。根据CC By SA 3.0许可证使用。
现在为了便于讨论,假设这是在19世纪-在长途或无线通信之前。
您是一个路口的操作员,听到一列火车来了。你不知道该走哪条路。你让火车停下来问司机他们要往哪个方向走。然后适当地设置开关。
列车很重,惯性很大。所以他们需要永远的启动和减速。
有更好的方法吗?你猜火车会朝哪个方向开!
如果你猜对了,它就会继续。
如果你猜错了,船长会停下来,后退,冲你大叫,让你把开关打开。然后它可以沿着另一条路重新启动。
如果你每次都猜对了,火车就永远不必停下来。
如果你经常猜错,列车将花费大量时间停止、备份和重新启动。
考虑一个If语句:在处理器级别,它是一个分支指令:
你是一个处理器,你看到一个分支。你不知道它会朝哪个方向发展。你是做什么的?停止执行并等待前面的指令完成。然后你继续沿着正确的路径前进。
现代处理器很复杂,而且有很长的流水线。所以他们需要永远的“热身”和“减速”。
有更好的方法吗?你猜树枝会朝哪个方向走!
如果您猜对了,则继续执行。
如果您猜错了,则需要刷新管道并回滚到分支。然后你可以沿着另一条路径重新启动。
如果你每次都猜对了,执行将永远不会停止。
如果你经常猜错,你会花很多时间拖延、回滚和重新启动。
这是分支预测。我承认这不是最好的类比,因为火车可以用旗子指示方向。但在计算机中,处理器直到最后一刻才知道一个分支将朝哪个方向移动。
那么,如何策略性地猜测,以尽量减少列车必须后退并沿另一条路径移动的次数?你看看过去的历史!如果火车99%的时间是左行的,那么你猜是左行。如果它交替出现,那么你就交替猜测。如果它每三次走一条路,你猜也是一样的……
换句话说,你试着识别一个模式并遵循它。这或多或少是分支预测器的工作方式。
大多数应用程序都有性能良好的分支。所以现代的分支预测通常会达到90%以上的命中率。但当面对无法识别模式的不可预测分支时,分支预测实际上是无用的。
进一步阅读Wikipedia上的“分支预测”文章。
正如上面暗示的,罪魁祸首是if语句:
if (data[c] >= 128)
sum += data[c];

请注意,数据平均分布在0和255之间。当数据被排序时,大约前半个迭代将不会进入if语句。之后,它们都将进入if语句。
这对分支预测器非常友好,因为分支连续多次沿着同一方向运行。即使是一个简单的饱和计数器也能正确地预测分支,除了它切换方向后的几次迭代。
快速可视化:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)

但是,当数据完全随机时,分支预测器就变得无用,因为它不能预测随机数据。因此,可能会有大约50%的预测失误(不比随机猜测好)。
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)

那么可以做些什么呢?
如果编译器无法将分支优化为条件移动,如果您愿意牺牲可读性来提高性能,可以尝试一些黑客操作。
用:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

替换为:
[4]

这将删除分支并用一些按位操作替换它。
(请注意,此黑客操作是不完全等同于原始if语句。但在这种情况下,所有的输入值都适用于 < 920】@ 3.5 GHz,BR> C++Visual Studio 2010 -X64版本
< PRE> >代码>(6) Brave- NETBea7.1.1 JDK 7 -X64
< PRE> >代码> [Cult>
观察:
与分支:分类和未排序之间存在巨大差异。在BCK中,排序和未排序数据之间没有区别。
在C++的情况下,当数据被排序时,HACK实际上比分支要慢一些。
一般的经验法则是避免在临界循环中(例如在这个例子中)依赖于数据的分支。x64上的
-ftree-vectorize
能够生成条件移动。因此,排序后的数据和未排序的数据没有区别-两者都很快。
(或者说有点快:对于已排序的情况,
cmov
可能会更慢,特别是如果GCC将其放在关键路径上,而不仅仅是
add
,尤其是在BuldWrand之前的英特尔中, >代码>(12) /Prime>有2个循环延迟:GCC优化标志-O3使代码比-O2慢)
VC++ 2010即使在代码> [13 ] < /Code > 之前,也不能为该分支生成条件移动。
英特尔C++编译器(ICC)11做了一些奇迹。它将两个回路互换,从而将不可预知的分支提升到外回路。因此,它不仅免疫错误预测,它也比VC++和GCC产生的速度快两倍!换言之,ICC利用测试循环来击败基准……
如果给英特尔编译器无分支代码,它会直接将其矢量化。。。它的速度和分支(循环交换)一样快。
这表明即使是成熟的现代编译器在优化代码的能力上也会有很大的差异……

2020-02-02 19:25:41
Cayman

4016


分支预测。
对于排序数组,先对一系列值设置
data[c] >= 128
条件,然后对所有后续值设置
true
。这很容易预测。对于未排序的数组,您需要支付分支成本。

2020-02-02 19:35:18
白色喷泉蜀黍

3251


当对数据进行排序时,性能显著提高的原因是删除了分支预测惩罚,这在Mystical的答案中得到了很好的解释。
现在,如果我们查看代码
if (data[c] >= 128)
sum += data[c];

我们可以发现,当条件满足。在
x86
系统中,这种类型的分支可以很容易地转换为条件移动语句,该语句将被编译为条件移动指令:
cmovl
。在
C
中,语句将直接编译(无需优化)到
x86
中的条件移动指令中,它是三元运算符
... ? ... : ...
。因此,我们将上述语句重写为等效语句:
sum += data[c] >=128 ? data[c] : 0;

在保持可读性的同时,我们可以检查加速因子。
在Intel Core i7-2600K@3.4GHz和Visual Studio 2010发布模式下,基准是(从Mystical复制的格式):
x86
//  Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.71

x64
//  Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737

结果在多个测试中是可靠的。当分支结果不可预测时,我们会得到很大的加速,但当分支结果可预测时,我们会受到一些影响。事实上,使用条件移动时,无论数据模式如何,性能都是相同的。
现在让我们通过研究它们生成的
x86
程序集来更仔细地研究一下。上的pre>int max2(int a, int b) {
return a > b ? a : b;
}

x86-64机器,
GCC -S
生成下面的程序集。
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret

max2
由于使用了指令
cmovge
而使用的代码要少得多。但真正的好处是,不涉及分支跳转,
max2
,如果预测的结果不正确,分支跳转会带来很大的性能损失。
那么,为什么条件移动的性能会更好呢?
在典型的x86处理器中,指令的执行分为几个阶段。大致上,我们有不同的硬件来处理不同的阶段。因此,我们不必等到一个指令完成后才开始新的指令。这称为流水线。
在分支情况下,下面的指令由前面的指令决定,因此我们不能进行流水线。我们必须等待或预测。
在条件移动的情况下,执行条件移动指令分为几个阶段,但之前的阶段,如
Fetch
Decode
并不依赖于前一个指令的结果;只有后一个阶段需要结果。因此,我们只等待一条指令执行时间的一小部分。这就是为什么当预测容易时,条件移动版本比分支慢的原因。
计算机系统:程序员的观点,第二版详细解释了这一点。您可以查看第3.6.6节中的条件移动指令,查看整个第4章中的处理器体系结构,查看第5.11.2节中有关分支预测和预测失误惩罚的特殊处理。
有时,一些现代编译器可以优化我们的代码,使其具有更好的性能,有时,一些编译器不能(所讨论的代码正在使用Visual Studio的本机编译器)。在不可预知的情况下了解分支和条件移动之间的性能差异,可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写性能更好的代码。

2020-02-02 19:35:18
神诚

2232


如果您希望对该代码进行更多优化,请考虑以下情况:
从原始循环开始:
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
sum += data[j];
}
}

使用循环交换,我们可以安全地将该循环更改为:
for (unsigned j = 0; j < arraySize; ++j)
{
for (unsigned i = 0; i < 100000; ++i)
{
if (data[j] >= 128)
sum += data[j];
}
}

,然后,您可以看到
if
条件在
i
循环的整个执行过程中是恒定的,因此您可以提升
if
输出:
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
for (unsigned i = 0; i < 100000; ++i)
{
sum += data[j];
}
}
}

然后,您可以看到内部循环可以折叠为一个表达式,假设浮点模型允许它(
/fp:fast
被抛出,例如)
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
sum += data[j] * 100000;
}
}

那一个比以前快100000倍。

2020-02-02 19:35:18
MicroWings

1854


毫无疑问,我们中的一些人会对识别CPU分支预测器有问题的代码的方法感兴趣。Valgrind tool
cachegrind
有一个分支预测模拟器,通过使用
--branch-sim=yes
标志启用。在这个问题的例子中运行它,外循环的数量减少到10000,并用
g++
编译,得到以下结果:
排序:
==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind)
==32551== Mispred rate: 0.0% ( 0.0% + 1.2% )

未排序:
==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind)
==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )

深入到由
cg_annotate
生成的逐行输出有问题的循环:
已排序:
          Bc    Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 10,006 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }

未排序:
          Bc         Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 164,050,007 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }

这使您可以轻松识别有问题的行-在未排序的版本中,
if (data[c] >= 128)
行导致164050,007 cachegrind的分支预测模型下预测失误的条件分支(
Bcm
),而在排序版本中只会导致10006。
或者,在Linux上,可以使用性能计数器子系统来完成相同的任务,但在使用CPU计数器的本机性能中,
perf stat ./sumtest_sorted

排序:
 Performance counter stats for './sumtest_sorted':
11808.095776 task-clock # 0.998 CPUs utilized
1,062 context-switches # 0.090 K/sec
14 CPU-migrations # 0.001 K/sec
337 page-faults # 0.029 K/sec
26,487,882,764 cycles # 2.243 GHz
41,025,654,322 instructions # 1.55 insns per cycle
6,558,871,379 branches # 555.455 M/sec
567,204 branch-misses # 0.01% of all branches
11.827228330 seconds time elapsed

未排序:
 Performance counter stats for './sumtest_unsorted':
28877.954344 task-clock # 0.998 CPUs utilized
2,584 context-switches # 0.089 K/sec
18 CPU-migrations # 0.001 K/sec
335 page-faults # 0.012 K/sec
65,076,127,595 cycles # 2.253 GHz
41,032,528,741 instructions # 0.63 insns per cycle
6,560,579,013 branches # 227.183 M/sec
1,646,394,749 branch-misses # 25.10% of all branches
28.935500947 seconds time elapsed

它还可以使用disassembly进行源代码注释。
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted

 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
: sum += data[c];
0.00 : 400a1a: mov -0x14(%rbp),%eax
39.97 : 400a1d: mov %eax,%eax
5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax
4.60 : 400a26: cltq
0.00 : 400a28: add %rax,-0x30(%rbp)
...

有关详细信息,请参阅性能教程。

2020-02-02 19:35:18
HinanaiTokiko

1313


我刚刚读了这个问题和它的答案,我觉得缺少了答案。
消除分支预测的一种常见方法是表查找,而不是使用分支(尽管我没有在这种情况下测试过它)。
这种方法通常在以下情况下工作:
它是一个小表,并且很可能被缓存在处理器中,并且
您正在非常紧密的循环中运行,并且/或者处理器可以预加载数据。
背景和原因从处理器的角度来看,您的内存很慢。为了补偿速度上的差异,在处理器中构建了两个缓存(一级/二级缓存)。所以想象一下你正在做你的漂亮的计算,并且发现你需要一块内存。处理器将执行“加载”操作并将内存加载到缓存中,然后使用缓存执行其余计算。由于内存相对较慢,此“加载”将减慢程序速度。
与分支预测一样,此功能在奔腾处理器中得到了优化:处理器预测需要加载一段数据,并尝试在操作实际命中缓存之前将其加载到缓存中。正如我们已经看到的,分支预测有时会出现可怕的错误——在最坏的情况下,您需要返回并实际等待内存负载,这将需要永远(换句话说:失败的分支预测是糟糕的,分支预测失败后的内存负载是可怕的!)。
幸运的是,如果内存访问模式是可预测的,处理器会将其加载到其快速缓存中,一切正常。
我们首先需要知道的是什么是小的?虽然通常较小更好,但经验法则是坚持使用大小小于等于4096字节的查找表。作为上限:如果查找表大于64K,则可能值得重新考虑。
构造一个表
以便我们可以创建一个小表。下一步要做的是在适当的地方得到一个查找函数。查找函数通常是使用两个基本整数操作(和、或、异或、移位、添加、删除或乘法)的小函数。您想让lookup函数将您的输入转换为表中的某种“唯一键”,然后简单地给出您想要它做的所有工作的答案。
在这种情况下:>=128表示我们可以保留该值,<128表示我们可以去掉它。最简单的方法是使用“AND”:如果保留它,则使用7FFFFFFF;如果要删除它,则使用0。还要注意,128是2的幂,所以我们可以制作一个32768/128整数的表,并用一个零和许多7FFFFFFFF整数填充它。
托管语言
您可能想知道为什么它在托管语言中工作得很好。毕竟,托管语言用分支检查数组的边界,以确保不会弄乱……
嗯,不完全是。。。:-)
在消除托管语言的此分支方面已经做了相当多的工作。例如:
for (int i = 0; i < array.Length; ++i)
{
// Use array[i]
}

在这种情况下,编译器很明显,边界条件永远不会被击中。至少Microsoft JIT编译器(但我希望Java也会做类似的事情)会注意到这一点并完全删除检查。哇,那意味着没有分支。类似地,它将处理其他明显的情况。
如果在托管语言中查找遇到问题——关键是在查找函数中添加一个
& 0x[something]FFF
,以使边界检查可预测,并使其运行得更快。
此情况的结果
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
data[c] = random.Next(256);
}
/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c)
{
lookup[c] = (c >= 128) ? c : 0;
}
// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int j = 0; j < arraySize; ++j)
{
/* Here you basically want to use simple operations - so no
random branches, but things like &, |, *, -, +, etc. are fine. */
sum += lookup[data[j]];
}
}
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

2020-02-02 19:35:18
鏡歌

1177


当数组排序时,数据分布在0到255之间,在前半个迭代过程中,不会输入
if
-语句(下面共享
if
语句)。
if (data[c] >= 128)
sum += data[c];

问题是:是什么使得上述语句在某些情况下不能执行,就像在排序数据的情况下一样?这里是“分支预测器”。分支预测器是一种数字电路,它试图猜测分支(例如
if-then-else
结构)的走向,然后才能确定。分支预测器的目的是改善指令管道中的流。分支预测在实现高效性能方面起着关键作用!
让我们做一些基准测试来更好地理解它
一个
if
-语句的性能取决于它的条件是否具有可预测的模式。如果条件总是真或总是假,处理器中的分支预测逻辑将获取模式。另一方面,这种模式是不可预测的,
if
-语句将要昂贵得多。
让我们在不同条件下测量此循环的性能:
for (int i = 0; i < max; i++)
if (condition)
sum++;

下面是具有不同真-假模式的循环的计时:
Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0 T repeated 322
(i & 0xffffffff) == 0 F repeated 276
(i & 1) == 0 TF alternating 760
(i & 3) == 0 TFFFTFFF… 513
(i & 2) == 0 TTFFTTFF… 1675
(i & 4) == 0 TTTTFFFFTTTTFFFF… 1275
(i & 8) == 0 8T 8F 8T 8F … 752
(i & 16) == 0 16T 16F 16T 16F … 490

一个“坏”的真-假模式可以使
if
-语句比“好”模式慢6倍!当然,哪种模式是好的,哪种模式是坏的取决于编译器和特定处理器生成的确切指令。
因此分支预测对性能的影响毫无疑问!

2020-02-02 19:35:18
深蓝的审判

1103


避免分支预测错误的一种方法是构建一个查找表,并使用数据对其进行索引。Stefan de Bruijn在他的回答中讨论了这个问题。
但是在这个例子中,我们知道值在[0,255]范围内,我们只关心值>=128。这意味着我们可以很容易地提取一个位来告诉我们是否需要一个值:通过将数据放在右边的7位,我们只剩下0位或1位,我们只想在有1位的情况下添加这个值。让我们将这个位称为“决策位”。
通过使用决策位的0/1值作为数组的索引,我们可以生成同样快速的代码,无论数据是否排序。我们的代码总是会增加一个值,但是当决策位为0时,我们会在不关心的地方增加这个值。代码如下:
// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
int j = (data[c] >> 7);
a[j] += data[c];
}
}
double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;
sum = alut;

此代码浪费了添加的一半,但从未发生分支预测失败。在随机数据上,它比实际的if语句的版本快得多。
但是在我的测试中,显式查找表比这个稍微快一点,可能是因为索引查找表比比特移位快一些。这显示了我的代码如何设置和使用查找表(对于代码中的“查找表”来说,这是难以想象的
[1]
)。这里是C++代码:
代码> [2 ] BR>,在这种情况下,查找表只有256字节,所以它在缓存中很好地匹配,而且都很快。如果数据是24位的,我们只需要其中的一半。。。查找表太大,不实用。另一方面,我们可以结合上面所示的两种技术:首先将位移过去,然后索引一个查找表。对于只需要上半部分值的24位值,我们可能会将数据右移12位,并为表索引保留12位值。一个12位表索引意味着一个4096个值的表,这可能是实用的。
使用数组索引,而不是使用< PRE> >代码>如果 语句,可以用来决定使用哪一个指针。我看到一个实现了二进制树的库,它没有两个命名指针(
pLeft
pRight
或其他什么),而是有一个长度为2的指针数组,并使用“决策位”技术来决定要遵循哪个指针。例如,该库将执行如下操作:
if (x < node->value)
node = node->pLeft;
else
node = node->pRight;

此库将执行以下操作:
i = (x < node->value);
node = node->link[i];

以下是指向此代码的链接:红黑树,永远混淆

2020-02-02 19:35:18
noaaaaa

999


在排序的情况下,您可以比依赖成功的分支预测或任何无分支比较技巧做得更好:完全删除分支。
事实上,阵列是在一个连续区域中用
data < 128
和另一个用
data >= 128
进行分区的。因此,您应该使用两分搜索(使用
Lg(arraySize) = 15
比较)来找到分区点,然后从该点开始直接累加,给出了排序或未排序的近似解:< Prime>代码> [5 ] < /代码> < /PRE>(假设一个真正均匀的分布,16384个具有期望值的样本):-BR>

2020-02-02 19:35:18
strayer

813


上述行为是由于分支预测而发生的。
要了解分支预测,必须首先了解指令管道:
任何指令都被分解成一系列步骤,以便可以并行地同时执行不同的步骤。这种技术被称为指令管道,用于提高现代处理器的吞吐量。要更好地理解这一点,请参阅维基百科上的示例。
通常,现代处理器有相当长的流水线,但为了方便起见,我们只考虑这4个步骤。
IF--从内存中获取指令
ID--解码指令
EX--执行指令
WB--写回CPU寄存器
2条指令的4级流水线。
回到上面的问题让我们考虑以下问题指令:
                        A) if (data[c] >= 128)
/\
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) sum += data[c]; C) for loop or print().

如果没有分支预测,则会发生以下情况:
要执行指令B或指令C,处理器必须等到指令A到达流水线的前级,因为转到指令B或指令C的决定取决于指令A的结果,因此管道将如下所示。
当if condition返回true时:
当if condition返回false时:
由于等待指令a的结果,在上述情况下(不进行分支预测;对于true和false)所花费的CPU总周期为7。
那么什么是分支预测?
分支预测器将尝试猜测分支(if-then-else结构)将以何种方式进行,然后才能确定这一点。它不会等待指令A到达管道的前级,但它会猜测决策并转到该指令(在我们的示例中为B或C)。
如果猜测正确,管道看起来是这样的:
如果后来检测到猜测错误,则丢弃部分执行的指令,并使用正确的分支重新开始管道,从而导致延迟。
在分支预测失误的情况下浪费的时间等于从获取阶段到执行阶段的管道中的阶段数。现代微处理器往往有相当长的流水线,因此预测失误延迟在10到20个时钟周期之间。管道越长,就越需要一个好的分支预测器。
在操作码中,第一次有条件时,分支预测器没有任何信息来建立预测,因此第一次它将随机选择下一条指令。在后面的for循环中,它可以基于历史进行预测。
对于按升序排序的数组,有三种可能:
所有元素都小于128
所有元素都大于128
一些开始的新元素小于128,然后它变得大于128
让我们假设,在第一次运行时,预测器将始终假定为真分支。
因此在第一次运行时因为历史上所有的预测都是正确的,所以它总是取真分支。
在第二种情况下,它最初预测是错误的,但经过几次迭代后,它将正确预测。
在第三种情况下,它将最初正确预测,直到元素小于128。在这之后,当它看到历史上的分支预测失败时,它将在一段时间内失败,并纠正它自己。
在所有这些情况下,失败的次数都会太少,因此,只需要放弃部分执行的指令并使用正确的分支重新启动几次,就可以减少CPU周期。
但在随机未排序数组的情况下,预测将需要丢弃部分执行的指令,并在大部分时间重新开始使用正确的分支,与排序数组相比,将导致更多的CPU周期。

2020-02-02 19:35:18
redeva

711


一个官方的答案是:英特尔-避免分支预测失误的成本英特尔-分支和循环重组以防止预测失误科学论文-分支预测计算机体系结构书籍:J.L.轩尼诗,D、 A.帕特森:计算机体系结构:一种定量方法
科学出版物中的文章:T.Y.Yeh,Y、 N.Patt做了很多关于分支的预测。
你也可以从这个可爱的图表中看出分支预测因子被混淆的原因。
原始代码中的每个元素都是一个随机值,因此预测因子会随着“pre>std::rand()的打击而改变方向。
另一方面,一旦它被排序,预测器将首先进入“强烈不接受”状态,当值更改为“高”值时,预测器将在三次运行中从“强烈不接受”一直更改为“强烈接受”。

2020-02-02 19:35:18
多米Ka

679


在同一行中(我认为没有任何答案强调这一点),有必要指出,有时(特别是在性能很重要的软件中,如Linux内核中),您可以找到如下if语句:
if (likely( everything_is_ok ))
{
/* Do something */
}

或类似的:
if (unlikely(very_improbable_condition))
{
/* Do something */
}

两者
likely()
unlikely()
实际上是通过使用类似于GCC的
__builtin_expect
的宏来定义的,以帮助编译器插入预测代码以支持用户提供的信息。GCC支持其他可能改变正在运行的程序的行为或发出诸如清除缓存等低级指令的内置函数。请参阅本文档,其中包含了可用的GCC内置函数。
通常,这种优化主要出现在执行时间很重要的硬实时应用程序或嵌入式系统中这很关键。例如,如果要检查仅发生1/10000000次的错误条件,为什么不通知编译器?这样,默认情况下,分支预测将假定条件为false。

2020-02-02 19:35:18
雾雨油库里

657

< [〔25〕3〕>C++中常用的布尔[〔29〕2〕n op[ 22 ]项在编译程序中产生M[39 ] NY[23 ] R[47 ] NCHE。如果这些b牧场都在圈内,很难预测它们会显著减缓执行速度。布尔变量b存储为8-b个整数,值为

[0]
表示
[1
1
表示
true

布尔变量是超定的,即所有将布尔变量作为输入的运算符都检查输入是否有任何其他值比
0
1
更重要,但以布尔值作为输出的运算符只能产生
[[11]0
1
的值。这使得使用布尔变量作为输入的操作的效率比需要的要低。
考虑一下示例:
bool a, b, c, d;
c = a && b;
d = a || b;

编译器通常以以下方式实现:
bool a, b, c, d;
if (a != 0) {
if (b != 0) {
c = 1;
}
else {
goto CFALSE;
}
}
else {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
else {
goto DTRUE;
}
}
else {
DTRUE:
d = 1;
}

此代码远远不是最佳的。如果预测失误,分支可能需要很长时间。如果确信操作数除了
0
1
之外没有其他值,那么布尔运算的效率会大大提高。编译器不做这种假设的原因是,如果变量未初始化或来自未知源,则它们可能有其他值。如果
a
b
已初始化为有效值,或者它们来自生成布尔输出的运算符,则可以优化上述代码。优化后的代码看起来是这样的:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char
被使用而不是
bool
以便能够使用按位运算符(
&
|
)而不是布尔运算符(
&&
[20]
)。按位运算符是只占用一个时钟周期的单个指令。OR运算符(
|
)即使
a
b
的值不是
0
1
也可以工作。如果操作数的值不是
0
<1

~
不能用于not,则AND运算符(
&
和EXCLUSIVE OR运算符(
^
)可能会产生不一致的结果。相反,/code>如果
b
是一个表达式,如果
a
false
&&
将不计算
b
&
将)。同样地,
a || b
不能替换为
a | b
如果
b
是一个表达式,如果
a
true

使用按位运算符比操作数是变量时更有利比较:
bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下是最佳的(除非您希望
&&
表达式生成许多分支预测失误)。

2020-02-02 19:35:18
夜襲紅魔館

322


那是肯定的!…
由于代码中发生的切换,分支预测使逻辑运行速度变慢!就像你走的是一条直的街道或是一条有很多转弯的街道,肯定直的会更快!…
如果对数组进行排序,则第一步的条件为false:
data[c] >= 128
,然后成为整条路到街道尽头的true值。这就是你如何更快地到达逻辑的终点。另一方面,使用一个未排序的数组,您需要进行大量的旋转和处理,这无疑会使您的代码运行速度变慢……
请看下面我为您创建的图像。哪条街道要快点完工?
所以从程序上讲,分支预测会导致进程变慢…
最后,我们很高兴知道有两种分支预测,每种预测都会对代码产生不同的影响:
1。静态
2。动态分支预测是微处理器在第一次遇到条件分支时使用的,而动态分支预测是用于条件分支代码的后续执行。
为了有效地编写代码以利用这些规则,在编写if else或switch语句时,请先检查最常见的情况,然后逐步减少到最不常见的情况。
循环不一定需要对静态分支预测进行任何特殊的代码排序,因为通常只使用循环迭代器的条件。

2020-02-02 19:35:18
Athtamis

290


这个问题已经多次得到很好的回答。不过,我还是想提请大家注意另一个有趣的分析。
最近,这个示例(稍作修改)也被用作演示如何在Windows上对程序本身中的一段代码进行分析的方法。在此过程中,作者还展示了如何使用结果来确定代码在排序和未排序情况下的大部分时间都花在了哪里。最后,本文还展示了如何使用HAL(硬件抽象层)的一个鲜为人知的特性来确定在未排序的情况下发生了多少分支预测失误。
链接如下:
http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

2020-02-02 19:35:18
不可以的

233


正如其他人已经提到的,神秘的背后是分支预测。
我不是想补充什么,而是想用另一种方式解释这个概念。
wiki上有一个包含文本和图表的简明介绍。
我确实喜欢下面的解释,它使用图表直观地阐述分支预测器。
在计算机体系结构中,分支预测器是一个数字电路,它试图猜测分支(例如,如果是其他结构,则为
结构)的前进方向这是众所周知的。分支预测器的目的是改善
指令管道中的流。在许多现代流水线微处理器体系结构(如x86)中,分支预测器在实现高效性能方面起着关键作用。
双向分支通常使用条件跳转指令实现。条件跳转既可以是“不执行”并在条件跳转后紧接着的第一个代码分支继续执行,也可以是“执行”并跳转到程序内存中存储第二个代码分支的不同位置。在计算条件并且条件跳转已通过指令管道中的执行阶段之前,不知道是否会执行条件跳转(参见图1)。

基于所描述的场景,我编写了一个动画演示来演示如何在中执行指令不同情况下的管道。
没有分支预测。

如果没有分支预测,处理器将不得不等到
条件跳转指令通过执行阶段,然后
下一条指令才能进入管道中的获取阶段。
示例包含三条指令,第一条是条件跳转指令。后两条指令可以进入管道,直到执行条件跳转指令。
完成3条指令需要9个时钟周期。
使用分支预测器,不要进行条件跳转。假设预测不执行条件跳转。

完成3条指令需要7个时钟周期。
使用分支预测并执行条件跳转。假设predict不接受条件跳转。

完成3条指令需要9个时钟周期。
如果发生分支预测失误,则浪费的时间等于
从fetch stage到
execute stage的管道中的阶段数。现代微处理器往往有相当长的
流水线,因此预测失误延迟在10到20个时钟
周期之间。因此,延长管道长度会增加对更高级分支预测器的需求。
如您所见,我们似乎没有理由不使用分支预测器。
这是一个非常简单的演示,阐明了分支预测器的基本部分。如果那些gif很烦人,请随时从答案中删除它们,访问者也可以从branchpreditordemo获得演示

2020-02-02 19:35:18
圣徒亚瑟

197


分支预测增益!
重要的是要了解分支预测失误不会减慢程序的速度。缺失预测的代价是:(3)分支预测不存在,并且等待表达式的计算来决定要运行什么代码(下一段进一步解释)。
< >代码> [ 0 ] < /PRE> > BR>每当有一个
  [代码> < /PRE> > PRE> >代码>(2)< /代码> /PRE>语句时,表达式必须是计算以确定应执行哪个块。在编译器生成的汇编代码中,插入了条件分支指令。
分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即,如果表达式为false,程序根据某些条件跳过
if
块的代码,在我们的例子中,这是表达式求值。
也就是说,编译器试图在实际求值之前预测结果。它将从
if
块获取指令,如果表达式是真的,那就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果没有,那么我们运行的是错误的代码,则刷新管道,并运行正确的块。
可视化:
假设您需要选择路由1或路由2。等你的搭档检查地图,你已经在####停下来等了,或者你可以选择路线1,如果你幸运的话(路线1是正确的路线),那么你就不用等你的搭档检查地图了(你节省了他检查地图的时间),否则你会掉头回去。
虽然冲洗管道的速度非常快,但现在冒这个险是值得的。预测已排序的数据或变化缓慢的数据总是比预测快速变化更容易和更好。
 O      Route 1  /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------

2020-02-02 19:35:18

135


关于分支预测。这是怎么一回事?
分支预测器是一种古老的性能改进技术,它仍然适用于现代建筑。虽然简单的预测技术提供快速查找和功率效率,但它们的预测失误率很高。
另一方面,复杂的分支预测(基于神经或两级分支预测的变体)提供了更好的预测精度,但是它们消耗更多的能量,复杂性也呈指数增长。在复杂的预测技术中,预测分支所需的时间本身就非常高,从2到5个周期不等,与实际分支的执行时间相当。
分支预测本质上是一个优化(最小化)问题,其重点是实现最低的可能未命中率、低功耗,具有最小资源的低复杂度。
确实有三种不同的分支:
正向条件分支-基于运行时条件,PC(程序计数器)被更改为指向指令流中的前向地址。
后向条件分支-PC被更改为指向指令流中的后向地址。分支基于某些条件,例如当循环末尾的测试声明循环应再次执行时,向后分支到程序循环的开头。
无条件分支-这包括没有特定条件的跳转、过程调用和返回。例如,无条件跳转指令可以用汇编语言简单地编码为“jmp”,并且指令流必须立即定向到跳转指令指向的目标位置,而可能编码为“jmpne”的条件跳转只有在比较前面“比较”指令中的两个值显示值不相等。(x86架构使用的分段寻址方案增加了额外的复杂性,因为跳跃可以是“接近”(在段内)或“远”(在段之外)。每种类型对分支预测算法都有不同的影响。)
静态/动态分支预测:微处理器在第一次遇到条件分支时使用静态分支预测,动态分支预测用于条件分支代码的后续执行。
参考文献:
分支预测器
自剖析的演示
分支预测综述
分支预测

2020-02-02 19:35:18
熊猫眼的老陈

132


在ARM上,不需要分支,因为每个指令都有一个4位的条件字段,它是以零成本测试的。这消除了对短分支的需要,并且不会出现分支预测命中。因此,由于排序的额外开销,排序后的版本将比ARM上未排序的版本运行得慢。内部循环如下:
MOV R0, #0     // R0 = sum = 0
MOV R1, #0 // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop // Inner loop branch label
LDRB R3, [R2, R1] // R3 = data[c]
CMP R3, #128 // compare R3 to 128
ADDGE R0, R0, R3 // if R3 >= 128, then sum += data[c] -- no branch needed!
ADD R1, R1, #1 // c++
CMP R1, #arraySize // compare c to arraySize
BLT inner_loop // Branch to inner_loop if c < arraySize

2020-02-02 19:35:18
卡哇伊的风

132


除了分支预测可能会减慢速度之外,排序数组还有另一个优点:
您可以有一个停止条件,而不只是检查值,这样您只循环相关数据,而忽略其余数据。
分支预测只会错过一次。
 // sort backwards (higher values first), may be in some other part of the code
std::sort(data, data + arraySize, std::greater());
for (unsigned c = 0; c < arraySize; ++c) {
if (data[c] < 128) {
break;
}
sum += data[c];
}

2020-02-02 19:35:18
车牌

122


由于一种称为分支预测的现象,排序数组的处理速度比未排序数组快。
分支预测器是一个数字电路(在计算机体系结构中),它试图预测分支将走哪条路,从而改进指令管道中的流。电路/计算机预测并执行下一步。
错误的预测会导致返回上一步,并用另一个预测执行。假设预测正确,代码将继续下一步。错误的预测会导致重复相同的步骤,直到出现正确的预测。
问题的答案非常简单。
在未排序的数组中,计算机进行多次预测,从而增加出错的机会。
而在排序的数组中,计算机进行的预测较少,乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌乌tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt
未排序数组:弯曲的道路
______   ________
| |__|

分支预测:猜测/预测哪个道路是直的,并在不检查
___________________________________________ Straight road
|_________________________________________|Longer road
的情况下跟踪它一个短一个长。如果你错误地选择了另一条路,就没有回头路了,所以如果你选择较长的路,你会浪费一些额外的时间。这与计算机中发生的情况类似,我希望这有助于您更好地理解。
此外,我想从评论中引用@Simon_Weaver:
它不会做出更少的预测-它会做出更少的错误预测。它仍然必须通过循环预测每次…

2020-02-02 19:35:18
blackzero

114


我用我的MacBook Pro(Intel i7,64位,2.4 GHz)在MATLAB 2011b中尝试了相同的代码,用于以下MATLAB代码:
% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);

%Sort the data
data1= sort(data); % data1= data when no sorting done

%Start a stopwatch timer to measure the execution time
tic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128
sum=sum + data1(j);
end
end
end
toc;
ExeTimeWithSorting = toc - tic;

以上MATLAB代码的结果如下:
  a: Elapsed time (without sorting) = 3479.880861 seconds.
b: Elapsed time (with sorting ) = 2377.873098 seconds.

C代码的结果与@GManNickG I get中的结果相同:
  a: Elapsed time (without sorting) = 19.8761 sec.
b: Elapsed time (with sorting ) = 7.37778 sec.

基于此,看起来,在没有排序的情况下,MATLAB的速度几乎是C实现的175倍,在排序的情况下,MATLAB的速度是C实现的350倍。换句话说,对于MATLAB实现,分支预测的效果是1.46x,对于C实现,效果是2.7x。

2020-02-02 19:35:18
以澤

43


其他人认为需要对数据进行排序的假设是不正确的。
下面的代码不会对整个数组进行排序,而只对其中的200个元素段进行排序,因此运行速度最快。
仅对k元素段排序可在线性时间内完成预处理,
O(n)
,而不是排序整个数组所需的
O(n.log(n))
时间。
#include 
#include
#include
int main() {
int data[32768]; const int l = sizeof data / sizeof data[0];
for (unsigned c = 0; c < l; ++c)
data[c] = std::rand() % 256;
// sort 200-element segments, not the whole array
for (unsigned c = 0; c + 200 <= l; c += 200)
std::sort(&data[c], &data[c + 200]);
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i) {
for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
if (data[c] >= 128)
sum += data[c];
}
}
std::cout << static_cast(clock() - start) / CLOCKS_PER_SEC << std::endl;
std::cout << "sum = " << sum << std::endl;
}

这也“证明”它与排序顺序等任何算法问题无关,它确实是分支预测。

2020-02-02 19:35:18
wazxy

24


比亚恩·斯特劳斯特罗普对这个问题的回答是:
听起来像是一个面试问题。是真的吗?你怎么知道?不先做一些测量就回答效率的问题是个坏主意,所以知道如何测量是很重要的。
因此,我尝试了一百万个整数的向量,得到了:
Already sorted    32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds

我运行了几次以确定。是的,这种现象是真的。我的关键代码是:
void run(vector& v, const string& label)
{
auto t0 = system_clock::now();
sort(v.begin(), v.end());
auto t1 = system_clock::now();
cout << label
<< duration_cast(t1 — t0).count()
<< " milliseconds\n";
}
void tst()
{
vector v(1'000'000);
iota(v.begin(), v.end(), 0);
run(v, "already sorted ");
std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
run(v, "shuffled ");
}

至少这种现象在编译器、标准库和优化器设置中是真实存在的。不同的实现可以而且确实会给出不同的答案。事实上,有人做了一个更系统的研究(快速的web搜索会发现它),大多数实现都显示了这种效果。
一个原因是分支预测:排序算法的关键操作是
“if(v[i] < pivot]) …”
或等效操作。对于排序序列,测试总是正确的,而对于随机序列,选择的分支是随机变化的。
另一个原因是,当向量已经排序时,我们不需要将元素移动到它们的正确位置。这些小细节的影响是我们所看到的五六个因素。
快速排序(通常是排序)是一项复杂的研究,吸引了计算机科学中一些最伟大的思想。一个好的排序函数是选择一个好的算法并在实现过程中注意硬件性能的结果。
如果你想编写高效的代码,你需要了解一些机器结构。

2020-02-02 19:35:18
嘉嘉喵喵

15


这个问题源于CPU上的分支预测模型。我建议您阅读这篇文章:
通过多分支预测和分支地址缓存提高指令获取率
当您对元素进行排序后,IR不必费心去获取所有的CPU指令,它会一次又一次地从缓存中获取它们。

2020-02-02 19:35:18
霜月しぐれ


避免分支预测错误的一种方法是构建一个查找表,并使用数据对其进行索引。Stefan de Bruijn在他的回答中讨论了这个问题。
但是在这个例子中,我们知道值在[0,255]范围内,我们只关心值>=128。这意味着我们可以很容易地提取一个位来告诉我们是否需要一个值:通过将数据移到右边的7位,我们剩下的是0位或1位,我们只想在有1位的情况下添加这个值。让我们将这个位称为“决策位”。
通过使用决策位的0/1值作为数组的索引,我们可以生成同样快速的代码,无论数据是否排序。我们的代码总是会增加一个值,但是当决策位为0时,我们会在不关心的地方增加这个值。下面是代码:
//Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
int j = (data[c] >> 7);
a[j] += data[c];
}
}
double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;
sum = aint lut[256];
for (unsigned c = 0; c < 256; ++c)
lut[c] = (c >= 128) ? c : 0;
// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += lut[data[c]];
}
}
;

此代码浪费了添加的一半,但从未发生分支预测失败。在随机数据上,它比实际的if语句的版本快得多。
但是在我的测试中,显式查找表比这个稍微快一点,可能是因为索引查找表比比特移位快一些。这显示了我的代码是如何设置和使用查找表的(代码中的“查找表”称为lut)。这里是C++代码:
//声明,然后填写查找表
 (1)< /代码> /PRE> > BR>在此情况下,查找表只有256字节,因此它在缓存中很好地匹配,而且都很快。如果数据是24位的,我们只需要其中的一半。。。查找表太大,不实用。另一方面,我们可以结合上面所示的两种技术:首先将位移过去,然后索引一个查找表。对于只需要上半部分值的24位值,我们可能会将数据右移12位,并为表索引保留12位值。一个12位表索引意味着一个4096个值的表,这可能是实用的。
可以使用数组索引,而不是使用if语句来决定使用哪一个指针。我看到了一个实现二叉树的库,它没有使用两个命名指针(pLeft和pRight或其他什么),而是使用一个长度为2的指针数组,并使用“决策位”技术来决定要遵循哪个指针。例如,代替:
if (x < node->value)
node = node->pLeft;
else
node = node->pRight;
this library would do something like:
i = (x < node->value);
node = node->link[i];

这是一个很好的解决方案,也许它会起作用

2020-02-02 19:35:18
Fortunemsg



Copyright © 2019-2020 zimt8.com
备案号:湘ICP备19012068号