col*_*ang 1 c# performance if-statement
这很奇怪,我以为我们应该总是把高机会条款放到嵌套if-elses的前面,直到今天.
简要设置:
一个数组Zoo[]包含10,000个5类的对象,基于权重,例如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考试Cat-> Dog-> Chicken-> Rabbit-> Owl,反向版本以相反的顺序检查它们.
还有,有人可以在非洗牌版本中解释每种方法都有很大改进吗？(我会假设由于内存中的缓存或更高的命中率？)
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 = cat,d = dog,o = owl)
动物:CCCCC DDDDD OOOOO
预测:*CCCC CDDDD DOOOO
正确:NYYY NYYY NYYYY
正如您所看到的,当动物发生变化时,预测才会出错.因此,每种类型的一千只动物的预测因子超过99%的时间.
但是,预测器并没有真正起作用,
真正发生的是**每个if分支被预测为真或假.假设(例如,40%,30%,20%,10%,0%)分布如下:
if(Animal.Type == MostCommonType)true不到一半的时间(40%)40 out of 100(40 + 30 + 20 + 10 + 0)否则if(animal.Type == SecondMostCommonType)// true 50%of时间,60中的30(30 + 20 + 10 + 0)否则if(animal.Type == ThirdMostCommonType)//真66%的时间20中30(20 + 10)否则if(animal.Type = = FourtMostCommonType)//真100%的时间10(10 +0)
40%,50%和60%的几率不会给预测器带来太大的影响,唯一好的预测(100%)是最不常见的类型和最不常见的代码路径.
但是,如果您颠倒if顺序:
if(animal.Type == FifthMostCommonType)// False 100%的时间0 out of 100(40 + 30 + 20 + 10 + 0)否则if(animal.Type == FourtMostCommonType)// False 90%的时间100(100 + 30 + 20 + 10)其他如果(Animal.Type == MostCommonType)// False 77%的时间20 90(40 + 30 + 20 +)否则if(animal.Type = = SecondMostCommonType)//真实57%的时间,70中的30(40 + 30)其他if(animal.Type == ThirdMostCommonType)//真100%40中40(40+)
几乎所有的比较都是高度可预测的.
预测下一只动物将不是最不常见的动物将比任何其他预测更正确.
简而言之,在这种情况下,错过的分支预测的总成本高于做更多分支的成本(即if语句)
我希望能稍微清理一下.如果有任何部分不清楚,请告诉我,我会尽量澄清.
**真的不是真的,但更接近真相.
编辑:
新处理器中的分支预测器相当复杂,您可以在http://en.wikipedia.org/wiki/Branch_predictor#Static_prediction上查看更多详细信息.
改组通过删除相似数据组并使每个猜测或预测可能正确来混淆预测器.想象一下全新的牌组.朋友拿起每张卡片,并要求您猜测它是红色还是黑色.
在这一点上,一个相当不错的算法是猜测最后一张卡是什么.你几乎每次都会猜对了.> 90%
然而,在对牌组进行洗牌之后,该算法仅提供50%的准确度.事实上,没有任何算法可以显着优于50%.(据我所知,计算剩下的红色和黑色数量是在这种情况下获得优势的唯一方法.)
编辑:重新分类
我猜这是因为CPU/L1/2/etc缓存未命中.由于每个类都将返回值实现为常量,即返回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;
}
}
}