2

对于我的一个项目,我使用了很多分支。思考:

if (foo) { do something } 
else if (bar) { do something } 
else if (bar2) { do something } 
... and so on

if (foo) { do something } 
if (bar) { do something } 
if (bar2) { do something } 
... and so on

我一直想知道的是,进行子表达式和/或逻辑消除以加快速度是否有意义。为了完整起见,您可以假设所有这些都在一个函数中。比如说,如果foobar有一个共同的子表达式,你可以这样写:

if (commonSubExpr) 
{
    if (foo without commonSubExpr) { do something }
    if (bar without commonSubExpr) { do something } 
}
if (bar2) { do something } 
... and so on

同样,您可以应用许多简单的布尔逻辑规则来优化规则。

我的问题是:这样做有意义吗?或者我可以期待 JIT'ter 来处理这个问题吗?

(根据Eric Lippert 的优秀文章,除了常量折叠之外,编译器不会对此进行优化——我认为情况仍然如此)。

更新+1

好吧,我不应该问这是否有意义,因为现在我有好心人试图向我解释什么是过早优化,这不是我所追求的……我的错误。请假设我知道过度设计、过早优化等——这正是我在这里试图避免的。

所以尝试 2... 我想知道事情是如何工作的,以及我可以从编译器/JIT'ter 中得到什么

我还注意到一些上下文可能在这里有所帮助,所以这里有一些关于应用程序的信息:

在这种情况下,应用程序是在运行时使用 Reflection.Emit 编译到 IL 的领域特定语言。我不能使用现有的语言或现有的编译器是有充分理由的。性能至关重要,编译后会执行很多操作(这就是为什么它首先编译为 IL 而不是简单地解释代码)。

我问这个的原因是因为我想知道我应该在编译器中设计优化器的程度。如果 JIT'ter 负责消除子表达式,我将设计优化器只做常量折叠等基本操作,如果 .NET 期望在编译器中发生这种情况,我将在编译器中设计它。根据我的预期,优化器将具有完全不同的设计。由于分支可能是最重要的性能消耗者,并且因为实现对我的软件设计有巨大影响,所以我特地决定问这个问题。

我不知道在实现编译器之前没有办法对此进行测试——这是一项相当多的工作——所以我想在开始实现之前直接了解我的基础知识。我不知道如何测试的原因是因为我不知道在什么情况下 JIT'ter 优化了哪些代码;我希望 .NET 运行时中的某些触发器会导致某些优化(使测试结果不可靠)...如果您知道解决此问题的方法,请告诉我。

表达式foo,bar等可以是您通常在代码中看到的任何形式,但您可以假设它是单个函数。所以,它可以是形式if (StartDate < EndDate),但不能是类似的东西if (method1() < method2())。解释一下:在后一种情况下,编译器不能简单地对方法的返回值做出假设(在优化之前你需要有关于返回值的信息),所以子表达式的消除一点也不简单。

因此,作为子表达式消除的示例:

if (int1 < int2 && int1 < int3) {
    //...
}
else if (int1 < int2 && int1 < int3) {
    //...
}

可以改写为:

if (int1 < int2)
{
    if (int1 < int3) {
        //...
    }
    else if (int1 < int3) {
        //...
    }
}

所以总结一下:我想知道的是这些类型的子表达式消除优化是否有意义 - 或者它们是否由 JIT'ter 处理。

4

2 回答 2

5

所以,它可以是 if (StartDate < EndDate)

不,它不能。您的编译器需要生成对该DateTime.op_LessThan()方法的调用。生成对方法的调用的问题在于,您无法 100% 确定该方法不会产生可观察到的副作用。DateTime.op_LessThan 没有,但这不是您的编译器可以自行找出的。您必须在编译器中对该规则进行硬编码。

然而,抖动可以,它确实知道该方法的代码是什么样的。而且它非常小,它会将方法内联到单个 CPU 指令中。它平均在不到一个 CPU 周期内执行。处理器中内置的分支预测逻辑确保分支不太可能使流水线停止。

很难让编译器中的优化器得到回报。它只能消除非常简单的代码的常见子表达式而没有副作用,但这样的代码已经运行得非常快。C# 编译器是一个很好的模型,它没有优化并且让工作变得不稳定。此答案中描述了由抖动执行的优化。是的,常见的子表达式消除就是它知道如何执行的一种优化。

然而,它是否应用优化是不可预测的,这取决于它需要在方法中生成哪些其他代码。我还没有检查过这个具体案例,我很怀疑它是否会由于分支。如果您还想为 && 和 || 提供短路评估,那么它的功能远不止这些。运营商。您可以找到的唯一方法是查看实际生成的机器代码。选择要使用平台目标设置验证的抖动。构建测试代码的发布配置。和Tools + Options,Debugging,General,取消勾选“Suppress JIT optimization”选项。并查看带有断点和 Debug + Windows + Disassembly 的机器代码。注意假的测试代码,如果抖动可以优化太多,它通常运行得不切实际。

于 2013-09-13T13:39:29.060 回答
3

正如评论中的许多人已经指出的那样,您似乎走错了方向。

如果你真的打算显着增加它,我会更担心这段代码的可管理性和清晰度。

如果您的foo, bar, bar2,commonSubExpr只是布尔值,这可能是您的应用程序中最快的部分,无论方法 1 还是 2。

如果foo, bar, bar2,commonSubExpr是可能很昂贵的评估函数,那么您应该优化函数本身,如果可能的话缓存结果。if/else但在那种情况下,它与从句的组成和结构无关。

更新:

如果你有这样的代码:

class Program
{
    static void Main(string[] args)
    {
        var int1 = 1;
        var int2 = 2;
        var int3 = 3;


        if (int1 < int2 && int1 < int3) {
            Console.WriteLine("Branch 1");
        }
        else if (int1 < int2 && int1 < int3) {
            Console.WriteLine("Branch 2");
        }
    }
}

优化后的 MSIL 将如下所示:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       44 (0x2c)
  .maxstack  2
  .locals init ([0] int32 int1,
           [1] int32 int2,
           [2] int32 int3)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.2
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.3
  IL_0005:  stloc.2
  IL_0006:  ldloc.0
  IL_0007:  ldloc.1
  IL_0008:  bge.s      IL_0019
  IL_000a:  ldloc.0
  IL_000b:  ldloc.2
  IL_000c:  bge.s      IL_0019
  IL_000e:  ldstr      "Branch 1"
  IL_0013:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_0018:  ret
  IL_0019:  ldloc.0
  IL_001a:  ldloc.1
  IL_001b:  bge.s      IL_002b
  IL_001d:  ldloc.0
  IL_001e:  ldloc.2
  IL_001f:  bge.s      IL_002b
  IL_0021:  ldstr      "Branch 2"
  IL_0026:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_002b:  ret
} // end of method Program::Main

然而,第二个例子:

static void Main(string[] args)
{
    var int1 = 1;
    var int2 = 2;
    var int3 = 3;

    if (int1 < int2)
    {
        if (int1 < int3)
        {
            Console.WriteLine("Branch 1");
        }
        else if (int1 < int3)
        {
            Console.WriteLine("Branch 2");
        }
    }
}

将减少 3 行代码:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       40 (0x28)
  .maxstack  2
  .locals init ([0] int32 int1,
           [1] int32 int2,
           [2] int32 int3)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.2
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.3
  IL_0005:  stloc.2
  IL_0006:  ldloc.0
  IL_0007:  ldloc.1
  IL_0008:  bge.s      IL_0027
  IL_000a:  ldloc.0
  IL_000b:  ldloc.2
  IL_000c:  bge.s      IL_0019
  IL_000e:  ldstr      "Branch 1"
  IL_0013:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_0018:  ret
  IL_0019:  ldloc.0
  IL_001a:  ldloc.2
  IL_001b:  bge.s      IL_0027
  IL_001d:  ldstr      "Branch 2"
  IL_0022:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_0027:  ret
} // end of method Program::Main

粗略地说,区别在于3 条指令

  IL_001a:  ldloc.1
  IL_001b:  bge.s      IL_002b
  IL_001d:  ldloc.0

根据其他来源(请阅读此处),JIT 不会进行这种类型的优化,但即使会,这在任何程度上都无法衡量。

于 2013-09-13T11:20:40.777 回答