JIT Loop Invariant Hoisting

在上一篇文章中,我们已经对 Loop Invariant 概念有一个简单的了解,在文章的最后提到的 Loop Invariant 将在这篇文章做一个简单的介绍。

在我们开始之前

如果你了解 C# 程序的运行,应该知道 C# 代码先被编译器编译为 MSIL 中间代码,在实际运行的时候才通过 JIT 编译器将 MSIL 代码编译成机器代码并运行。因此,编译器有两个时段可以对代码进行优化:

  • C# -> MSIL
  • MSIL -> MACHINE CODE
阅读更多

Loop Hoisting

上篇文章中,提到 Loop Hoisting ,这是一个常见的编译器优化项。我们总是能通过汇编代码等低级语言来“窥探”代码实际是怎么“指示”硬件运行的(这边文章不会涉及到详细的汇编内容,但是会用C#反编译后得到的汇编代码来辅助说明)。如果你看过我前面的几篇文章,会发现我用了大量反编译后的汇编代码来辅助说明,毕竟,千言不如实际的“证据”有说服力。

阅读更多

C# 内存模型

在 C# 的语言规范中 ECMA-334,对于Volatile关键字的描述:

15.5.4 Volatile fields
When a field-declaration includes a volatile modifier, the fields introduced by that declaration are volatile fields. For non-volatile fields, optimization techniques that reorder instructions can lead to unexpected and unpredictable results in multi-threaded programs that access fields without synchronization such as that provided by the lock-statement (§13.13). These optimizations can be
performed by the compiler, by the run-time system, or by hardware. For volatile fields, such reordering optimizations are restricted:

  • A read of a volatile field is called a volatile read. A volatile read has “acquire semantics”; that is, it is guaranteed to occur prior to any references to memory that occur after it in the instruction sequence.
  • A write of a volatile field is called a volatile write. A volatile write has “release semantics”; that is, it is guaranteed to happen after any memory references prior to the write instruction in the instruction sequence.

简单来说,对于常规字段,由于代码优化而导致指令顺序改变,如果没有进行一定的同步控制,在多线程应用中可能会导致意想不到的结果,而造成这种意外的原因可能是编译器优化、运行时系统的优化或者因为硬件的原因(即CPU和主存储器的通信模型)。可变(volatile)字段会限制这种优化的发生,在这里引入两个定义:

  • 可变读: 对于可变字段的读操作会获取语义。即,其可以保证对于可变字段的内存读取操作一定发生在其后内存操作指令的前面。进一步解释,与 Thread.MemoryBarrier 类似,获取语义会保证在读取可变字段指令前的指令可以跨越它出现在它后面,但是相反地,在它后面的指令不能跨越它出现在它的前面。例子:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Volatile_class
    {
    private int _a;
    private volatile int _b;
    private int _c;

    private void Call()
    {
    int temp=_a;
    //由于_b是可变字段,这样可以保证编译器不会将temp2=_c的指令提前到其之前
    //但是,可以将temp=_a提到其之后
    int temp1=_b;
    int temp2=_c;

    ...
    }

    private void OtherCall(){...}
    }
  • 可变写: 对于可变字段的写操作会释放语义。即,其可以保证对于可变字段的写操作发生在其前面指令执行之后,但是在它之后的指令可以跨域它提前执行。
阅读更多

C# 尾递归优化

何为尾递归

有时候我们使用递归来解决一些特定的问题,但是使用递归需要注意不要导致栈溢出,这是使用递归的一个常见问题,对于规模足够大的问题,使用递归必定会导致栈溢出。通常,我们可以通过尾递归进行优化,尾递归可以避免栈溢出的问题(暂且这样认为)。
尾递归并不是什么新奇的东西,理解起来很简单,对于递归,如果上层调用的返回结果不依赖子调用的结果,那么,这就是一个尾递归。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
///这是一个简单的尾递归例子
namespace tail
{
class Program
{
static void Main(string[] args)
{
var test=RetrieveData(100000000000000);
}

static long RetrieveData(long unit)
{
if (unit == 0)
return unit;
return RetrieveData(--unit);
}
}
}

等等,好像有什么地方不对

从上面的例子分析,代码依旧会导致栈溢出,不是吗?是的,聪明的你答对了。那为什么说尾递归可以避免栈溢出问题?当然,从刚才的结论看,这个问题提的并不准确,尾递归并不能避免栈溢出问题。
仔细想想,尾递归结构和循环结构是类似的,上面的尾递归可以写成:

阅读更多