The New C: It All Began with FORTRAN

The New C: It All Began with FORTRAN
by Randy Meyers
原文：http://www.ddj.com/cpp/184401313

本文详细介绍了C99标准引入restrict关键字的来龙去脉，译者非常谨慎地将它翻译成中文，希望更多国内的C语言开发者看到这篇非常精采的文章。

“有时候改进一种编程语言的最佳方式是让它看起来更像它在30年前的老样子”

一切从FORTRAN开始。

我说这句话，并不是想说FORTRAN是第一个编程语言。而是想说一段有趣的往事，60年代出现的一场关于在FORTRAN中如何实现参数传递的争论，以及最终的解决办法，意外地使FORTRAN在70年代的超级计算机上发挥出巨大的性能优势，并最终导致90年代的C99标准引入一个新特性，这就是restrict指针。因此，要理解为什么引入restrict指针，最好的办法就是回顾FORTRAN的这段历史。

FORTRAN和C语言不同，如果在函数中改变了某个参数（形参）的值，那么当函数返回后，调用者也能看到它传递的参数（实参）被改变了。比如例1的FORTRAN代码，如果你调用F时传一个变量Y做参数，当F返回后，Y将等于6。

例1:

SUBROUTINE F(X)
INTEGER X
X = 6
END

这就引起争论了：实现FORTRAN传参的语义有两种不同的方法，各种FORTRAN编译器会选择两者之一。第一种实现方法称为按引用（by reference）传参，就像我们通常在C程序中所采用的方法，要通过一个函数改变调用者的变量，可以传这个变量的地址（或指针）给函数，函数通过这个地址间接地访问和修改调用者的变量。假设FORTRAN编译器将FORTRAN代码翻译成C代码，例1的代码可能会翻译成例2这样：

例2:

void f(int *x)
{
   *x = 6;
}

这种实现方法的缺点是，某些体系结构的计算机实现间接访问的效率较低，不如直接访问局部变量来得快。因而产生了第二种实现FORTRAN传参的方法：传给函数的仍然是实参的地址，但在函数开头把实参的值复制了一份保存在局部变量中，然后在整个函数体中访问的都是这个局部拷贝，最后在函数返回前再把局部拷贝的值保存到原来的实参中。采用这种方法的FORTRAN编译器可能会把例1的代码翻译成例3这样。尽管这种拷进拷出（copy in/copy out）的方法需要在函数的开头和结尾拷贝参数，增加了额外的负担，但如果在函数体中这个参数用到了好几次，每次都只需要访问局部变量而不必做间接访问，那么在某些间接访问效率较低的体系结构上总的来说性能还是会得到改善。

例3:

void f(int *x)
{
   int xcopy = *x;
   xcopy = 6;
   *x = xcopy;
}

编译器如何实现一个语法特性通常属于“实现细节”的范畴，程序员写的程序不管用哪种编译器编译，语义都应该是一样的，所以编程语言的标准委员会通常允许编译器在几种实现方法中自由选择。然而，FORTRAN函数传参的这两种实现方法却有可能导致不同的语义。下面的例子说明了一个FORTRAN程序用两种不同方法编译的结果。

例4:

SUBROUTINE G(X, Y)
INTEGER X, Y
X = 1 + X
Y = 5 + Y
END

// Translation using "by reference"
void g(int *x, int *y)
{
   *x = 1 + *x;
   *y = 5 + *y;
}

// Translation using
// "copy in/copy out"
void g(int *x, int *y)
{
   int xcopy = *x;
   int ycopy = *y;
   xcopy = 1 + xcopy;
   ycopy = 5 + ycopy;
   *x = xcopy;
   *y = ycopy;
}

函数G给它的两个参数分别增加了不同的常数。如果你传两个变量A和B给函数G，假设在调用G之前A的值是1，B的值是10，那么在调用G之后A的值将变成2，B的值将变成15，不管用上述哪种方法实现传参结果都是这样。

但如果你传给函数G的两个参数都是变量A会怎么样呢？按第一种实现方法（by reference），在调用之后A的值是7，A在函数中被加了两次，因为*x和*y指的都是A。如果用第二种实现方法（copy in/copy out），在调用之后A的值是6。因为变量A在函数G里被拷贝成了两个不同的局部变量，它们分别加上一个常数，再先后拷贝回变量A，最后一个拷贝回A的值成为A的最终值。

这两种传参实现方法是一个典型的例子，任何编程语言标准的制定者都要面对一些需要取舍和折衷的问题。是否应该规定FORTRAN编译器必须采用上述两种实现方法中的某一种，即使这样规定会牺牲一些性能？或者是否应该修改某些语法规则以消除这种歧义？FORTRAN标准的制定者最终决定优先考虑性能，采取后一种折衷策略，因而两种传参的实现方法都被允许，编译器的实现可以根据目标平台的特点自由选择。这样规定了之后，某些代码就变得不可移植了，例如调用上面的函数G不能传两个变量A给它，否则在不同的平台上有不同的结果，这种调用代码被标准定义为非法的。

为了消除这种歧义，FORTRAN 66标准在语法上规定了许多条条框框，限制了程序员的自由。调用函数时，任何变量只能在参数列表中出现一次。如果你传一个全局变量给函数，那么函数就只能通过参数使用这个变量，而不能直接使用这个全局变量。如果你传一个变量给函数，那么和它的存储空间重叠的其它变量就不能同时传给这个函数，这个函数也不能直接使用和它重叠的存储空间。只要写程序时严格遵守了这些规则，那么无论编译器采用哪种方法实现传参，程序的语义都是一样的。

大约十年后，在Cray 1超级计算机项目中需要开发一种高度优化的编译器，使以前的FORTRAN程序在编译后可以充分利用该计算机的向量寄存器，以便充分发挥计算机的性能。比如例5所示的程序，最高效率的做法是把x所指向的数组加载到一组向量寄存器，把y所指向数组加载到另一组向量寄存器，然后执行一条向加法指令把两组向量寄存器加到一起。如果编译器可以生成向量指令，而不是在循环中每次加一个数组元素，那么这段代码的运行速度要快一个数量级。

例5:

void
vector_add(float *x, float *y,
   float *result)
{
   int i;
   for (i = 0; i < 64; ++i)
      result[i] = x[i] + y[i];
}

开发这样一个编译器，读取的代码是循环，生成的却是向量指令，这并不难实现，问题是生成的向量指令和原来的循环是否真的等价呢？前提是你要事先知道result数组与x和y都不重叠（x与y重叠对于这个例子倒没什么影响），那么把计算步骤改成先把x和y数组加载到向量寄存器，计算之后再存到result数组中，这显然是等价的。如果这个前提不成立呢？比如result和x是部分重叠的，result[0]其实是x[1]，result[i]其实是x[i+1]，会怎么样？如果按循环的计算步骤，每次循环的计算结果都会在下次循环中用到。如果改变计算步骤，先把x数组全部读到向量寄存器里，计算完之后再全部写到result数组，结果就完全不同了。这时候人们意外地发现，FORTRAN的语法规则使得程序正好适合了这种编译优化。为了避免不同的传参实现方法导致的歧义，FORTRAN标准定义的语法规则要求x、y和result必须是互不重叠的数组，这正好适合了向量机上的编译优化。因此FORTRAN程序在向量机上重新编译之后性能得到大幅度的提升。

后来有了并行处理器的计算机，这种性能优势再次显现出来。针对并行处理器优化的编译器会把一个循环拆成几个较小的循环，使它们可以同时在多个处理器上独立运行。以上面的vector_add函数为例，可以拆成两个循环，一个处理器计算i取值从0到31的循环，另一个处理器计算i取值从32到63的循环。前提是在一个处理器上做的计算并不需要另一个处理器上的计算结果，两个处理器可以各自独立地做自己的计算。对于上面的程序来说，显然也要求result数组与x和y不重叠。所以，FORTRAN的语法规则再一次适合了编译器的要求，使得编译器很容易把代码优化成并行的。

FORTRAN的性能优势最初在超级计算机上才能表现出来，而如今却已经可以在普通的通用微处理器上表现出来了。当今的通用微处理器大都具有超标量设计：

    * 每条指令的执行周期分成几个独立的阶段
    * 流水线使多条指令可以同时执行，每条指令处于不同的执行阶段
    * 处理器中的多个功能单元允许多个独立的操作并行执行，例如并行做加法和乘法
    * 处理器的运算速度比访问内存快很多倍，而且通常也比访问高速缓存要快
    * 甚至访问寄存器的速度也不及处理器的运算速度快。如果一条指令保存一个值到寄存器，下一条指令就需要取这个寄存器的值做操作数，那么处理器就不得不干等着前一条指令的结果保存到寄存器之后再执行后一条指令

针对超标量处理器优化的编译器必须仔细安排指令的顺序，把参与不同计算的指令交错起来执行，以达到最佳性能。例如，把内存中的数据读到寄存器需要很长时间，如果下一条指令就要取这个寄存器的值做计算，处理器就只有干等着了。所以编译器尽可能优化指令的顺序，先执行一条读内存指令，随后执行几条和第一条指令的结果无关的其它指令，使处理器在等待读内存的时候有别的事情可干，然后才执行需要第一条指令结果的指令。

仍然以上面的vector_add函数为例。针对超标量处理器常见的优化方法是这样的，在第i次循环开始时首先执行加载x[i+1]和y[i+1]到寄存器的指令，在等待读内存的时候计算x[i]+y[i]（它们在上次循环中已经读到寄存器了，可以直接拿来计算），这样当第i+1次循环开始时，两个操作数x[i+1]和y[i+1]已经加载到寄存器了，可以直接拿来计算了。显然，有一个前提是这一次循环的计算结果不会影响到下一次循环的操作数，保证了这个前提才可以先把下一次循环的操作数预取上来再做这一次循环的计算。这也要求每次循环所访问的存储空间是互不重叠的。

C编译器在优化方面和FORTRAN相比没什么优势，所以必须做出改进。C编译器的优化比FORTRAN难做的一个最主要原因是C语言使用指针而FORTRAN没有。如果C编译器能够看出各变量在程序中是如何访问的，当然能够做出适当的优化。问题在于变量往往是通过指针来间接访问的，编译器很难看出哪个指针指向哪个变量，也就无法判断两个指针所指的存储空间是否重叠。

目前有些编译器提供了一种解决办法，在正常的优化级别之上提供一种“不安全”的优化级别，用不用由程序员决定。如果编译时启用了不安全优化的选项，编译器就假定所有的指针指向不同的存储空间，然后基于这个假定做优化，得到的程序往往运行得更快。但如果在程序中存在多个指针指向同一存储空间的情况，优化得到的程序有可能是错误的。

更好的解决办法是让程序员自己指出哪些指针指向不同的存储空间，编译器就可以利用程序员提供的这些信息做优化。这就是C99引入的新特性restrict指针。（有些C++编译器也支持restrict指针，但没有成为C++标准。）restrict是C99引入的新关键字，在语法中做类型限定符，和const、volatile在语法中的位置相同。但是从语义上来说，restrict必须限定指针类型而不是别的类型，因此restrict应该出现在指针声明的*号之后。以下是几个例子。

例6:

int *restrict p1;    // OK, p1 is a restricted pointer to int
restrict int *p2;    // invalid: pointer to restricted int
typedef int *intptr;
restrict intptr p3;  //OK, p3 is a restricted pointer to int

C99定义了一个新的语法位置可以放类型限定符：在数组参数声明的[后面。数组参数其实就是指针参数，所以写在数组参数[后面的限定符相当于改写成指针参数时放在*后面的限定符。因此，

int f(float array[const restrict]);

等价于：

int f(float *const restrict array);

C99标准有一个Bug，仅当数组参数是命名参数时才允许在[后面加限定符。未命名的数组参数也应该允许在[后面加限定符的，希望在C标准被修正之前各种C编译器会把这一点当作标准的一个扩展来实现：

int f(float [restrict]);  // common extension

restrict指针的大致含义是说它提供了访问某一块存储空间的唯一途径。restrict指针可以改变指向的位置，但是在它的整个生存期中，每次所指向的存储空间都只有通过这个指针才能访问到，并且和其它可访问的存储空间都不重叠。编译器根据这个信息就可以放心地做上面讨论的各种优化了，此外还有一些优化也可以做，例如避免重复计算多个表达式中和指针访问有关的公共子表达式。

有一种例外情况，如果一块存储空间在restrict指针的整个生存期中没有做任何修改，也可以不必严格遵守restrict指针的唯一性限制，既可以通过restrict指针访问也可以同时通过其它途径访问，编译器优化不会影响这种代码的正确性。

为了理解restrict指针的这种唯一性限制，你可以把它想像成FORTRAN的copy in/copy out语义。当你把一个地址赋给一个restrict指针时，可以想像成把该地址处的变量做了一个拷贝。之后restrict指针就用来访问这个拷贝，但它同时也记得原来的地址，一旦这个restrict指针被指向别处了，或者它的生存期结束了，这时拷贝就被写回原地址。如果你的程序使用了restrict指针却不遵守唯一性限制，这种假想的copy in/copy out变换就会改变程序的语义而导致错误的结果。

例如，如果在restrict指针的生存期中未经过restrict指针而是直接修改原始变量，那么通过restrict指针访问到的很可能仍是未经修改的变量（因为访问到的是一个拷贝）。或者如果通过restrict指针修改了一个变量（修改的是一个拷贝），那么不经过restrict指针而直接访问原始变量时会发现它并没有被修改。如果你的程序通过了这种copy in/copy out检验，那么使用restrict指针就是安全的，并且这么做会使编译器更好地优化代码。

restrict指针的生存期定义为指针本身的存储空间从分配到释放的这段时间。如果指针是一个自动型变量，那么生存期就是声明它的语句块执行的这段时间。如果指针是一个参数，那么生存期就是从进入函数体直到返回的这段时间。如果指针是文件作用域的变量，那么生存期一直到main函数返回为止。

restrict指针的这种唯一性限制只针对通过指针所访问到的那部分存储空间。例如，在例5的vector_add函数中把三个参数声明都加上restrict，然后这么调用：

float data[192];
vector_add(&data[0], &data[64], &data[128]);

vector_add的三个指针各自访问data数组中的64个元素，这个数组实际上被当作三个互不重叠的子数组来使用，这样调用是没问题的，但如果第二个参数改成&data[63]，x和y参数所访问的存储空间就重叠了，这样调用就违背了restrict指针的唯一性限制。

restrict指针最好是用在像vector_add函数这种一目了然的情况下，如果你为了用restrict指针还要费力跟踪一下哪个指针指向哪个变量，有没有重叠，那么用restrict指针是很危险的，你很可能一不小心就直接访问了restrict指针所指的变量而没有通过该指针来访问（以下称为aliasing问题）。

现在我们来说说调试。如果你的程序出了问题，并且你用了restrict指针，你可能会怀疑是不是有aliasing问题。有些编译器提供选项可以忽略restrict关键字，以便调试是不是存在aliasing问题。如果你用的编译器没有提供忽略restrict关键字的选项，你可以把restrict写成一个空的宏定义。restrict的存在只为了方便编译器优化，把它去掉应该不改变程序的语义。

除了方便编译器优化之外，在函数原型中使用restrict关键字还有一个作用，就是警告调用者不要传两个指向重叠的存储空间的指针进来，否则这个函数不能正常工作。例如，在C89标准的库函数一节开头提到，本节描述的所有函数，除非特别说明，都不应该接收两个指针参数指向重叠的存储空间。例如调用sprintf时传进来的格式化字符串和结果字符串的首地址相同，诸如此类的调用都是非法的。在C99标准中仍然提到了这句话，但是更严格地体现在每个函数原型的restrict关键字上，使得这条规则更形式化地定义了，比单纯用一句话来规定要好。

总结一下：30年的编程语言发展历史和一个新的C语言关键字。

作者简介：Randy Meyers是一位C、C++和Java技术顾问。目前是ANSI C委员会J11工作组主席，以前是ANSI C++委员会J16工作组成员和ISO Java工作组成员。他在DEC公司工作了16年，是DEC C和C++编译器项目的架构师。可以通过[e-mail]联系到他。

评论

3 楼 djkings 2008-09-21  

你说得没错。It sucks
可是javaeye的bb code就只支持这么几种:java, ruby, js, xml , html, python, c, c++, C#, sql
框起来总比不框起来好看，凑合着看吧:)

2 楼 wuliupo 2008-09-21  

C代码
SUBROUTINE F(X) 
INTEGER X 
X = 6 
END 

这是C代码吗？是不是写错了，是Fortran代码呀？！

1 楼 ShiningRay 2008-09-20  

非常好的文章！