为什么要把高机会子句放在嵌套的前面，否则会降低性能
本文关键字：前面 性能 嵌套 高机会 机会 子句 为什么 | 更新日期: 2023-09-27 18:30:57
这很奇怪，直到今天，我原以为我们应该总是把高机会子句放在嵌套的if-elses前面。
简要设置：
一个数组Zoo[]包含 5 个类的 10，000 个对象，基于权重，例如 4，3，2，1，0（表示 4000 只猫、3000 只狗、2000 只鸡、1000 只兔子、0 只猫头鹰），它可以被洗牌或不洗牌（完全按顺序）。
然后使用 if-else 检查每个数组成员。
结果：时间（毫秒）
Weights 43210 01234 22222 43210 01234 22222
Shuffle Yes Yes Yes No No No
Polymorphism 101 100 107 26 26 27
If Else 77 28 59 17 16 17
If Else Reverse 28 77 59 16 17 16
Switch 21 21 21 18 19 18
当我看到If-Else反向比if-else好得多时，它引起了我的注意。在这里if-else考试猫>狗>鸡>兔子>猫头鹰，反向版本以相反的顺序检查它们。
另外，有人可以在非随机版本中解释每种方法都获得很大的改进吗？（我会假设由于缓存或内存中更好的命中率？
更新
Weights 27 9 3 1 0 0 1 3 9 27 27 9 3 1 0 0 1 3 9 27
Shuffle Yes Yes No No
Polymorphism 84 82 27 27
If Else 61 20 17 16
If Else Reverse 20 60 16 17
Switch 21 21 18 18
代码如下：
class Animal : AnimalAction
{
public virtual int Bart { get; private set; }
public int Type { get; private set; }
public Animal(int animalType)
{
this.Type = animalType;
}
}
interface AnimalAction
{
int Bart { get; }
}
class Cat : Animal
{
public Cat()
: base(0)
{
}
public override int Bart
{
get
{
return 0;
}
}
}
class Dog : Animal
{
public Dog()
: base(1)
{
}
public override int Bart
{
get
{
return 1;
}
}
}
class Chicken : Animal
{
public Chicken()
: base(2)
{
}
public override int Bart
{
get
{
return 2;
}
}
}
class Rabbit : Animal
{
public Rabbit()
: base(3)
{
}
public override int Bart
{
get
{
return 3;
}
}
}
class Owl : Animal
{
public Owl()
: base(4)
{
}
public override int Bart
{
get
{
return 4;
}
}
}
class SingleDispatch
{
readonly Animal[] Zoo;
int totalSession;
SingleDispatch(int totalSession, int zooSize)
{
this.totalSession = totalSession;
Zoo = new Animal[zooSize];
int[] weights = new int[5] { 0, 1, 2, 3, 4 };
int totalWeights = weights.Sum();
int[] tiers = new int[4];
int accumulated = 0;
for (int i = 0; i < 4; i++)
{
accumulated += weights[i] * zooSize / totalWeights;
tiers[i] = accumulated;
}
for (int i = 0; i < tiers[0]; i++)
{
Animal nextAnimal = new Cat();
Zoo[i] = nextAnimal;
}
for (int i = tiers[0]; i < tiers[1]; i++)
{
Animal nextAnimal = new Dog();
Zoo[i] = nextAnimal;
}
for (int i = tiers[1]; i < tiers[2]; i++)
{
Animal nextAnimal = new Chicken();
Zoo[i] = nextAnimal;
}
for (int i = tiers[2]; i < tiers[3]; i++)
{
Animal nextAnimal = new Rabbit();
Zoo[i] = nextAnimal;
}
for (int i = tiers[3]; i < zooSize; i++)
{
Animal nextAnimal = new Owl();
Zoo[i] = nextAnimal;
}
Zoo.FisherYatesShuffle();
}
public static void Benchmark()
{
List<Tuple<string, double>> result = new List<Tuple<string, double>>();
SingleDispatch myBenchmark = new SingleDispatch(1000, 10000);
result.Add(TestContainer.RunTests(10, myBenchmark.SubClassPoly));
result.Add(TestContainer.RunTests(10, myBenchmark.Ifelse));
result.Add(TestContainer.RunTests(10, myBenchmark.IfelseReverse));
result.Add(TestContainer.RunTests(10, myBenchmark.Switch));
foreach (var item in result)
{
Console.WriteLine("{0,-30}{1:N0}", item.Item1, item.Item2);
}
Console.WriteLine();
}
void SubClassPoly()
{
long sum = 0;
for (int i = 0; i < totalSession; i++)
{
foreach (var myAnimal in Zoo)
{
sum += myAnimal.Bart;
}
}
}
void Ifelse()
{
long sum = 0;
for (int i = 0; i < totalSession; i++)
{
foreach (var myAnimal in Zoo)
{
if (myAnimal.Type == 0)
{
sum += 0;
}
else if (myAnimal.Type == 1)
{
sum += 1;
}
else if (myAnimal.Type == 2)
{
sum += 2;
}
else if (myAnimal.Type == 3)
{
sum += 3;
}
else
{
sum += 4;
}
}
}
}
void IfelseReverse()
{
long sum = 0;
for (int i = 0; i < totalSession; i++)
{
foreach (var myAnimal in Zoo)
{
if (myAnimal.Type == 4)
{
sum += 4;
}
else if (myAnimal.Type == 3)
{
sum += 3;
}
else if (myAnimal.Type == 2)
{
sum += 2;
}
else if (myAnimal.Type == 1)
{
sum += 1;
}
else
{
sum += 0;
}
}
}
}
void Switch()
{
long sum = 0;
for (int i = 0; i < totalSession; i++)
{
foreach (var myAnimal in Zoo)
{
switch (myAnimal.Type)
{
case 0:
sum += 0;
break;
case 1:
sum += 1;
break;
case 2:
sum += 2;
break;
case 3:
sum += 3;
break;
case 4:
sum += 4;
break;
default:
break;
}
}
}
}
}
分支预测。 http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/
对于非随机的情况，它更容易理解。假设我们有一个非常简单的预测因子，它猜测下一个结果将与上一个结果相同：
例如（c=猫，d=狗，o=猫头鹰）
动物：中国中交 DDDDD 呜
预测：*CCCC CDDDD DOOOO
正确：NYYY NYYY NYYYY
如您所见，只有当动物发生变化时，预测才是错误的。因此，对于每种类型的一千只动物，预测因子在 99% 以上的时间内是正确的。
但是，预测器并不是那样工作的，
真正发生的事情**是每个if分支都被预测为真或假。假设分布为 （40%、30%、20%、10%、0%），如您的示例所示：
如果 （Animal.Type == MostCommonType） 为 true，则不到一半的时间 （40%） 100 个中的 40 个 （40+30+20+10+0）否则如果（动物。类型 == 第二多常用类型）//true 50% 的时间，60 个中的 30 个 （30+20+10 + 0）否则如果（动物。类型 == 第三多常用类型）//真 66% 的时间 30 分中的 20 分 （20+10）否则如果（动物。类型 == FourtMostCommonType）//true 100% 时间 10 满分 10 （10 +0）
40%、50%和60%的几率不会给预测变量太多的用法，唯一好的预测（100%）是在最不常见的类型和最不常见的代码路径上。
但是，如果颠倒 if 顺序：
如果（动物。类型 == 第五大常型）//假 100% 的时间 0 满分 100 （40+30+20+10+0）否则如果（动物。类型 == FourtMostCommonType）//False 90% 的时间 10 满分 100 （40+30+20+10）else if （Animal.Type == MostCommonType）//False 77% 的時間 90 分中的 20 分 （40+30+20+）否则如果（动物。类型 == 第二多常用类型）//true 57 % 的时间，70 个中的 30 个 （40+30）否则如果（动物。类型 == 第三最常见类型）//100% 正确 40 满分 40 （40+）
几乎所有的比较都是高度可预测的。
预测下一种动物不会是最不常见的动物将比任何其他预测都更正确。
简而言之，在这种情况下，错过分支预测的总成本高于执行更多分支的成本（即 if 语句）
我希望这能澄清一点。如果有任何部分不清楚，请告诉我，我会尽力澄清。
**嗯，不是真的，但更接近真相。
编辑：
较新处理器中的分支预测器相当复杂，您可以在 http://en.wikipedia.org/wiki/Branch_predictor#Static_prediction
随机排序通过删除相似数据的组并使每个猜测或预测可能正确来混淆预测变量。想象一下一副全新的纸牌。朋友拿起每张卡片，让你猜猜它是红色还是黑色。
在这一点上，一个相当好的算法是猜测最后一张牌是什么。你几乎每次都会猜对。> 90%
然而，在洗牌后，该算法只能提供 50% 的准确率。事实上，没有算法会给你比50%好得多的算法。（据我所知，在这种情况下，计算剩下的红人和黑人数是唯一获得优势的方法。
编辑：重新子类化
我猜这是因为 CPU/L1/2/等缓存未命中。由于每个类都将返回值实现为常量，即返回 0，因此返回值是函数的一部分。我怀疑如果您重新实现如下所示的类，您将在每次调用时强制缓存未命中，并看到相同的（不良）性能是否被洗牌。
class Rabbit : Animal
{
int bartVal; // using a local int should force a call to memory for each instance of the class
public Rabbit():base(3)
{
bartVal = 3;
}
public override int Bart
{
get
{
return bartVal;
}
}
}