c# - 为什么将 High chance 子句放在嵌套 If else 的前面会降低性能？

Question

很奇怪，我一直认为我们应该总是将 high chance 子句放在嵌套 if-els 的前面，直到今天。

简要设置:

数组 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 检查 Cat->Dog->Chicken->Rabbit->Owl，反向版本以相反的顺序检查它们。

此外，有人可以解释一下在非 shuffle 版本中每个方法都有很大的改进吗？ (我假设是由于内存中的缓存或更好的命中率？)

更新

  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;
                }
            }
        }
    }

}

Answer 1

分支预测。 http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

对于非洗牌的情况，它更容易理解。假设我们有一个非常简单的预测器，它猜测下一个结果将与上一个结果相同:

例如(c=猫,d=狗,o=猫头鹰)

动物:CCCCC DDDDD OOOOO

预测:*CCCC CDDDD DOOOO

正确:NYYY NYYY NYYYY

如您所见，只有当动物发生变化时，预测才会出错。因此，对于每种类型的 1000 只动物，预测器在超过 99% 的时间里都是正确的。

但是，预测器并不是真的那样工作，

真正发生的事情**是每个 if 分支都被预测为真或假。假设您的示例中的 (40%,30%,20%,10%,0%) 分布:

if (Animal.Type == MostCommonType) true 不到一半的时间 (40%) 100 个中有 40 个 (40+30+20+10+0)else if (animal.Type == SecondMostCommonType)//50% 的时间为真，60 次中有 30 次 (30+20+10 + 0)else if (animal.Type == ThirdMostCommonType)//66% 的时间为真 30 次中有 20 次 (20+10)else if (animal.Type == FourtMostCommonType)//true 100% 的时间 10 out of 10 (10 +0)

40%、50% 和 60% 的几率并没有给预测器带来多少可操作的机会，唯一好的预测 (100%) 是在最不常见的类型和最不常见的代码路径上。

但是，如果您反转 if 顺序:

if (animal.Type == FifthMostCommonType)//100% 的错误 100 个中有 0 个 (40+30+20+10+0)else if (animal.Type == FourtMostCommonType)//90% 的时间错误 100 次中有 10 次 (40+30+20+10)else if (Animal.Type == MostCommonType)//错误 77% 的时间 20 out of 90 (40+30+20+)else if (animal.Type == SecondMostCommonType)//57% 的时间为真，70 次中有 30 次 (40+30)else if (animal.Type == ThirdMostCommonType)//100% 正确 40 out of 40 (40+)

几乎所有的比较都是高度可预测的。

预测下一个动物不会是最不常见的动物将比任何其他预测都更正确。

简而言之，在这种情况下错过分支预测的总成本高于进行更多分支(即 if 语句)的成本

我希望这能稍微澄清一下。如果有任何不清楚的地方，请告诉我，我会尽力澄清。

**不是真的，但更接近事实。

编辑:

较新处理器中的分支预测器相当复杂，您可以在 http://en.wikipedia.org/wiki/Branch_predictor#Static_prediction 查看更多详细信息

混洗通过移除相似数据组并使每个猜测或预测可能是正确的来混淆预测器。想象一副全新的纸牌。一个 friend 拿起每张牌，让你猜它是红色还是黑色。

在这一点上，一个相当好的算法是猜测最后一张牌是什么。你几乎每次都会猜对。 > 90%

然而，在洗牌后，该算法只能给出 50% 的准确率。事实上，没有任何算法会给您带来明显优于 50% 的效果。 (据我所知，计算剩下的红色和黑色的数量是在这种情况下获得优势的唯一方法。)

编辑:重新分类

我猜这是因为 CPU/L1/2/etc 缓存未命中。由于每个类都将返回值实现为常量，即 return 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;
        }
    }
}