论坛首页 编程语言技术论坛

提出结论,给出论据(一)

浏览 3545 次
精华帖 (11) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-07-14   最后修改:2009-07-14
相关链接:
提出结论,给出论据(二)

rainbow686同学在论坛发表了这么一帖,java比.net(C#)慢这么多么?,引来讨论。回帖中不乏抛出结论但未提供任何论据的。很多myth就是在这种一传十,十传百的无论据结论中产生的;这种现象还是尽量避免的好。

rainbow686同学实施了一组对比测试,产生了一组运行结果,并得出了“确实是.net(3.5)的效率比 java(5.0)要高出很多”的结论。运行结果是实际运行所观察到的,真实可信。但得出的结论却缺乏限定条件,带有误导性。原帖里提供的代码和运行结果数据,所能支持的唯一结论是:在所测试的机器上,所使用的程序的计时方法反映了被测试程序在.NET 3.5上运行录得的时间间隔比在Java 5运行的短。其它任何衍生结论都需要更多论据予以支持,否则难以让人信服。

许多人可能都知道这种micro-benchmark往往会引出有误导性的结论,但很少人准确去解释原因。原理上:大多micro-benchmark与实际有意义的程序的结构和运行特征相去甚远,无法反映实际有意义的程序的运行状况。
但这些micro-benchmark到底是如何失衡的呢?这里我想就事论事,分析原帖中代码的一些运行细节,来提供更多材料供大家讨论。为此,本系列帖子将稍微涉及微软的CLR与Sun的HotSpot VM的工作方式。

============================================================================

CLR执行托管代码的流程

微软的用于PC上运行的.NET Framework底下的运行时叫做“公共语言运行时”(Common Language Runtime,简称CLR)。CLR实现了ECMA-335公共语言基础结构(Common Language Infrastructure,CLI)标准,并额外实现了许多方面的库。
.NET Framework 1.0、1.1、2.0、4.0都分别都自己对应的CLR版本,而.NET Framework 3.0和3.5则仍是使用CLR 2.0,.NET Framework 3.5 SP1包含了.NET Framework 2.0 SP2,其中对CLR 2.0做了更新。

CLR在执行一个托管方法时,会先看该方法是否已经被编译为本地代码;是则直接执行,否则通过即时编译(Just-In-Time compilation,简称JIT compilation,或者直接简称JIT)将MSIL字节码编译为本地代码,然后再执行该方法。一般情况下,这意味着某托管方法第一次被调用时会先被JIT然后才执行,而后续调用则可以直接执行本地代码。(例外情况:可以通过NGEN在程序执行前就预先将托管代码都编译为本地代码,或者通过RuntimeHelpers.PrepareMethod()使某方法提前被JIT)

懒得自己画图,从《CLR via C#, 2nd Edition》引用两张示意图。注意这只是示意图,不准确反映实际工作流程的细节。例如CLR 2.0的JIT其实由mscorwks.dll和mscorjit.dll配合完成,而不是通过mscoree.dll。CLR 4.0中则是clr.dll和jit.dll。
托管方法被初次调用的工作流程:


托管方法被后续调用的工作流程:

注意这里不再涉及JIT了。

============================================================================

测试的源码的总体分析

原帖中,C#部分的测试代码如下(稍做整理):
using System;

namespace ConsoleApplication1 {
    class Program {
        static void Main( string[ ] args ) {
            long j = 1;
            Console.WriteLine( DateTime.Now.ToString( ) );
            for ( long i = 1; i < 10000000000; i++ ) {
                j = j + 1;
            }
            Console.WriteLine( DateTime.Now.ToString( ) );
        }
    }
}


这段代码有下列特征:
1、没有构造大量对象。因而不会因为分配空间与垃圾回收而影响结果。也就是说不考察GC相关;
2、没有复杂的控制流。整个Main()方法只有6个显式调用的方法(包括属性的访问器的调用),只有一个单层循环。也就是说不考察运行时对复杂控制流的优化能力。
3、用户代码中没有涉及对引用的赋值。显式使用的变量都是值类型的(包括两个long型和两个DateTime型)。这样在生成的代码里就不会出现write barrier。
4、没有复杂的数据依赖关系。注意观察,
  1) 变量j的相关计算是冗余代码,因为变量j只是重复被赋值,其已有的值没有被可见的副作用所依赖。
  在适当的优化下,j可以整个被消除而不影响程序的正确性。
  (注意这段代码里的算术运算都不是checked的,也就是说程序不关心是否发生了算术溢出;
  如果是checked的,则需要证明j的相关计算不会引发异常才可以消除掉j,因为异常是“可见的副作用”)
  2) 变量j与for循环中的循环控制变量i的值是步调一致的。在每轮for循环中,i与j的值都保持一致。
  这样j就被称为“归纳变量”(induction variable)。
  在适当的优化下,j的值不必单独计算,只要通过计算i的值即可得到,从而可以消除变量j的相关计算代码。

5、使用了超过机器字长的数据类型(对32位机器而言)。x86指令集中没有针对64位(QWORD)数据的算术运算指令,所以代码中long型的运算都得想办法映射到32位运算上。在x64、IA-64、SPARC V9之类的64位机器上则不会有这样的问题。
6、在两次计时之间有一次对标准输出流的写操作(第一个Console.WriteLine())。显然楼主的本意只想测试循环累加的速度,这个写操作对计时带来了干扰。调用DateTime.ToString()同理,也造成了干扰。

上述测试代码的Main()方法由微软的C# 3.0编译器编译得到的MSIL如下:
.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       79 (0x4f)
  .maxstack  2
  .locals init ([0] int64 j,
           [1] int64 i,
           [2] valuetype [mscorlib]System.DateTime CS$0$0000,
           [3] valuetype [mscorlib]System.DateTime CS$0$0001)
  IL_0000:  ldc.i4.1
  IL_0001:  conv.i8
  IL_0002:  stloc.0
  IL_0003:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
  IL_0008:  stloc.2
  IL_0009:  ldloca.s   CS$0$0000
  IL_000b:  constrained. [mscorlib]System.DateTime
  IL_0011:  callvirt   instance string [mscorlib]System.Object::ToString()
  IL_0016:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_001b:  ldc.i4.1
  IL_001c:  conv.i8
  IL_001d:  stloc.1
  IL_001e:  br.s       IL_002a

  IL_0020:  ldloc.0
  IL_0021:  ldc.i4.1
  IL_0022:  conv.i8
  IL_0023:  add
  IL_0024:  stloc.0
  IL_0025:  ldloc.1
  IL_0026:  ldc.i4.1
  IL_0027:  conv.i8
  IL_0028:  add
  IL_0029:  stloc.1
  IL_002a:  ldloc.1
  IL_002b:  ldc.i8     0x2540BE400
  IL_0034:  blt.s      IL_0020

  IL_0036:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
  IL_003b:  stloc.3
  IL_003c:  ldloca.s   CS$0$0001
  IL_003e:  constrained. [mscorlib]System.DateTime
  IL_0044:  callvirt   instance string [mscorlib]System.Object::ToString()
  IL_0049:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_004e:  ret
}

与实际生成的x86目标代码相比较,可以发现IL并不反映实际运行的代码的特征。
我们可以确认C#编译器没有消除变量j,所以如果实际执行时变量j消失了,那肯定是CLR的功劳。

============================================================================

生成的目标代码的总体分析

首先要声明我的测试环境,以限定我提供的论据的适用范围。我测试的机器是2004年的HP nx9040笔记本。CPU是Pentium-M 715 "Dothan"(1.5 GHz, 2MB L2 cache, 400 MHz FSB),支持指令集有MMX、SSE、SSE2,注意它不支持Intel 64指令集(或称x86-64或者x64)。内存是1280MB的DDR-266 SDRAM。操作系统是32位的Windows XP SP3。.NET Framework是3.5 SP1。

通过SOS扩展来调试,可以看到JIT为ConsoleApplication1.Program.Main()方法对应生成的x86目标代码如下:
00E70070 push        ebp
00E70071 mov         ebp,esp
00E70073 push        edi
00E70074 push        esi
00E70075 sub         esp,20h
00E70078 mov         esi,ecx
00E7007A lea         edi,[ebp-28h]
00E7007D mov         ecx,8
00E70082 xor         eax,eax
00E70084 rep stos    dword ptr es:[edi]
00E70086 mov         ecx,esi
00E70088 lea         edi,[ebp-20h]
00E7008B pxor        xmm0,xmm0
00E7008F movq        mmword ptr [edi],xmm0
00E70093 lea         ecx,[ebp-20h]
00E70096 call        792896D0
00E7009B call        792897B0
00E700A0 mov         ecx,eax
00E700A2 lea         eax,[ebp-20h]
00E700A5 sub         esp,8
00E700A8 movq        xmm0,mmword ptr [eax]
00E700AC movq        mmword ptr [esp],xmm0
00E700B1 lea         edx,[ebp-10h]
00E700B4 mov         eax,dword ptr [ecx]
00E700B6 call        dword ptr [eax+48h]
00E700B9 lea         eax,[ebp-10h]
00E700BC sub         esp,8
00E700BF movq        xmm0,mmword ptr [eax]
00E700C3 movq        mmword ptr [esp],xmm0
00E700C8 call        792DDBC0
00E700CD mov         edx,eax
00E700CF xor         ecx,ecx
00E700D1 call        792DDC30
00E700D6 mov         esi,eax
00E700D8 call        792ED2F0
00E700DD mov         ecx,eax
00E700DF mov         edx,esi
00E700E1 mov         eax,dword ptr [ecx]
00E700E3 call        dword ptr [eax+000000D8h]
00E700E9 mov         esi,1
00E700EE xor         edi,edi
00E700F0 add         esi,1
00E700F3 adc         edi,0
00E700F6 cmp         edi,2
00E700F9 jg          00E70105
00E700FB jl          00E700F0
00E700FD cmp         esi,540BE400h
00E70103 jb          00E700F0
00E70105 lea         edi,[ebp-28h]
00E70108 pxor        xmm0,xmm0
00E7010C movq        mmword ptr [edi],xmm0
00E70110 lea         ecx,[ebp-28h]
00E70113 call        792896D0
00E70118 call        792897B0
00E7011D mov         ecx,eax
00E7011F lea         eax,[ebp-28h]
00E70122 sub         esp,8
00E70125 movq        xmm0,mmword ptr [eax]
00E70129 movq        mmword ptr [esp],xmm0
00E7012E lea         edx,[ebp-18h]
00E70131 mov         eax,dword ptr [ecx]
00E70133 call        dword ptr [eax+48h]
00E70136 lea         eax,[ebp-18h]
00E70139 sub         esp,8
00E7013C movq        xmm0,mmword ptr [eax]
00E70140 movq        mmword ptr [esp],xmm0
00E70145 call        792DDBC0
00E7014A mov         edx,eax
00E7014C xor         ecx,ecx
00E7014E call        792DDC30
00E70153 mov         esi,eax
00E70155 call        792ED2F0
00E7015A mov         ecx,eax
00E7015C mov         edx,esi
00E7015E mov         eax,dword ptr [ecx]
00E70160 call        dword ptr [eax+000000D8h]
00E70166 lea         esp,[ebp-8]
00E70169 pop         esi
00E7016A pop         edi
00E7016B pop         ebp
00E7016C ret

变成了这么长一串看似混杂无章的x86代码,该如何理解呢?rainbow686同学想要测试的循环又在哪里呢?
下面我把这段代码加上注释再帖出来:
//// 代码块1:方法头
00E70070 push        ebp     // 保存帧指针
00E70071 mov         ebp,esp // 设置新的帧指针
00E70073 push        edi     // 这两句保护EDI和ESI寄存器
00E70074 push        esi
00E70075 sub         esp,20h // 分配局部变量空间
00E70078 mov         esi,ecx
00E7007A lea         edi,[ebp-28h]
00E7007D mov         ecx,8
00E70082 xor         eax,eax
00E70084 rep stos    dword ptr es:[edi]
00E70086 mov         ecx,esi
//// 代码块1结束

//// 代码块2:Program.Main()的方法体

// 内联开始,System.DateTime.get_Now()
00E70088 lea         edi,[ebp-20h]
00E7008B pxor        xmm0,xmm0
00E7008F movq        mmword ptr [edi],xmm0
00E70093 lea         ecx,[ebp-20h]
00E70096 call        792896D0 (System.DateTime.get_UtcNow(), mdToken: 060002d2)
00E7009B call        792897B0 (System.TimeZone.get_CurrentTimeZone(), mdToken: 06000942)
00E700A0 mov         ecx,eax
00E700A2 lea         eax,[ebp-20h]
00E700A5 sub         esp,8
00E700A8 movq        xmm0,mmword ptr [eax]
00E700AC movq        mmword ptr [esp],xmm0
00E700B1 lea         edx,[ebp-10h]
00E700B4 mov         eax,dword ptr [ecx]
00E700B6 call        dword ptr [eax+48h] (System.CurrentSystemTimeZone.ToLocalTime(System.DateTime), mdToken: 06000951)
// 内联结束,System.DateTime.get_Now()

// 内联开始,System.DateTime.ToString()
00E700B9 lea         eax,[ebp-10h]
00E700BC sub         esp,8
00E700BF movq        xmm0,mmword ptr [eax]
00E700C3 movq        mmword ptr [esp],xmm0
00E700C8 call        792DDBC0 (System.Globalization.DateTimeFormatInfo.get_CurrentInfo(), mdToken: 06002493)
00E700CD mov         edx,eax
00E700CF xor         ecx,ecx
00E700D1 call        792DDC30 (System.DateTimeFormat.Format(System.DateTime, System.String, System.Globalization.DateTimeFormatInfo), mdToken: 06002408)
// 内联结束,System.DateTime.ToString()

// 内联开始,System.Console.WriteLine(System.String)
00E700D6 mov         esi,eax
00E700D8 call        792ED2F0 (System.Console.get_Out(), mdToken: 06000772)
00E700DD mov         ecx,eax
00E700DF mov         edx,esi
00E700E1 mov         eax,dword ptr [ecx]
00E700E3 call        dword ptr [eax+000000D8h] (System.IO.TextWriter+SyncTextWriter.WriteLine(System.String), mdToken: 060036c5)
// 内联结束,System.Console.WriteLine(System.String)

//>> for循环初始段:对变量i赋初始值
00E700E9 mov         esi,1
00E700EE xor         edi,edi
//>> for循环体:空
//>> for循环增量段:对变量i累加
00E700F0 add         esi,1
00E700F3 adc         edi,0
//>> for循环条件ver1:
00E700F6 cmp         edi,2
00E700F9 jg          00E70105
00E700FB jl          00E700F0
//>> for循环条件ver2:
00E700FD cmp         esi,540BE400h
00E70103 jb          00E700F0
//>> for循环结束

// 内联开始,System.DateTime.get_Now()
00E70105 lea         edi,[ebp-28h]
00E70108 pxor        xmm0,xmm0
00E7010C movq        mmword ptr [edi],xmm0
00E70110 lea         ecx,[ebp-28h]
00E70113 call        792896D0 (System.DateTime.get_UtcNow(), mdToken: 060002d2)
00E70118 call        792897B0 (System.TimeZone.get_CurrentTimeZone(), mdToken: 06000942)
00E7011D mov         ecx,eax
00E7011F lea         eax,[ebp-28h]
00E70122 sub         esp,8
00E70125 movq        xmm0,mmword ptr [eax]
00E70129 movq        mmword ptr [esp],xmm0
00E7012E lea         edx,[ebp-18h]
00E70131 mov         eax,dword ptr [ecx]
00E70133 call        dword ptr [eax+48h] (System.CurrentSystemTimeZone.ToLocalTime(System.DateTime), mdToken: 06000951)
// 内联结束,System.DateTime.get_Now()

// 内联开始,System.DateTime.ToString()
00E70136 lea         eax,[ebp-18h]
00E70139 sub         esp,8
00E7013C movq        xmm0,mmword ptr [eax]
00E70140 movq        mmword ptr [esp],xmm0
00E70145 call        792DDBC0 (System.Globalization.DateTimeFormatInfo.get_CurrentInfo(), mdToken: 06002493)
00E7014A mov         edx,eax
00E7014C xor         ecx,ecx
00E7014E call        792DDC30 (System.DateTimeFormat.Format(System.DateTime, System.String, System.Globalization.DateTimeFormatInfo), mdToken: 06002408)
// 内联结束,System.DateTime.ToString()

// 内联开始,System.Console.WriteLine(System.String)
00E70153 mov         esi,eax
00E70155 call        792ED2F0 (System.Console.get_Out(), mdToken: 06000772)
00E7015A mov         ecx,eax
00E7015C mov         edx,esi
00E7015E mov         eax,dword ptr [ecx]
00E70160 call        dword ptr [eax+000000D8h] (System.IO.TextWriter+SyncTextWriter.WriteLine(System.String), mdToken: 060036c5)
// 内联结束,System.Console.WriteLine(System.String)

//// 代码块2结束

//// 代码块3:方法尾
00E70166 lea         esp,[ebp-8] // 撤销局部变量分配的空间
00E70169 pop         esi         // 恢复老的EDI和ESI
00E7016A pop         edi
00E7016B pop         ebp         // 恢复老的帧指针
00E7016C ret
//// 代码块3结束

//// Program.Main()方法结束


注意我在代码中以//>>注释的部分——那才是原帖中rainbow686同学关注的重点,for循环对应的目标代码。

============================================================================

观察方法调用的内联

方法内联(method inlining),就是用一个方法的拷贝来替代对该方法的调用。这是一种非常有效的优化:内联后程序所执行到的代码序列总是比内联前的短,因为减少了其中调用方法的相关开销;而且内联能暴露许多控制流和数据流的依赖关系,使优化器能够进行原本需要通过过程间分析才能进行的优化。其缺点是生成的目标代码体积会膨胀,会影响到指令的缓存。

注意CLR中,方法内联是如何逐层进行的。上面ConsoleApplication1.Program.Main()两次内联了System.DateTime.get_Now()。而观察后者的代码,可以发现它又内联了System.DateTime.ToLocalTime()。相关的C#源码大致如下:
public struct DateTime : IComparable, IFormattable, 
    IConvertible, ISerializable, IComparable<DateTime>, IEquatable<DateTime> {
    // ...
    public static DateTime Now {
        get {
            return DateTime.UtcNow.ToLocalTime();
        }
    }
    
    public DateTime ToLocalTime() {
        TimeZone.CurrentTimeZone().ToLocalTime(this);
    }
    // ...
}

相关的汇编代码,
System.DateTime.get_Now():
79298CA0 push        ebp
79298CA1 mov         ebp,esp
79298CA3 push        esi
79298CA4 sub         esp,8
79298CA7 xor         eax,eax
79298CA9 mov         dword ptr [ebp-0Ch],eax
79298CAC mov         dword ptr [ebp-8],eax
79298CAF mov         esi,ecx
79298CB1 lea         ecx,[ebp-0Ch]
79298CB4 call        792896D0 (System.DateTime.get_UtcNow(), mdToken: 060002d2)
// 这里以下内联自System.DateTime.ToLocalTime()
79298CB9 call        792897B0 (System.TimeZone.get_CurrentTimeZone(), mdToken: 06000942)
79298CBE mov         ecx,eax
79298CC0 lea         eax,[ebp-0Ch]
79298CC3 push        dword ptr [eax+4]
79298CC6 push        dword ptr [eax]
79298CC8 mov         edx,esi
79298CCA mov         eax,dword ptr [ecx]
79298CCC call        dword ptr [eax+48h] (System.CurrentSystemTimeZone.ToLocalTime(System.DateTime), mdToken: 06000951)
79298CCF lea         esp,[ebp-4]
79298CD2 pop         esi
79298CD3 pop         ebp
79298CD4 ret

System.DateTime.ToLocalTime():
79763DFC push        ebp
79763DFD mov         ebp,esp
79763DFF push        edi
79763E00 push        esi
79763E01 mov         esi,ecx
79763E03 mov         edi,edx
79763E05 call        792897B0 (System.TimeZone.get_CurrentTimeZone(), mdToken: 06000942)
79763E0A push        dword ptr [esi+4]
79763E0D push        dword ptr [esi]
79763E0F mov         ecx,eax
79763E11 mov         edx,edi
79763E13 mov         eax,dword ptr [ecx]
79763E15 call        dword ptr [eax+48h] (System.CurrentSystemTimeZone.ToLocalTime(System.DateTime), mdToken: 06000951)
79763E18 pop         esi
79763E19 pop         edi
79763E1A pop         ebp
79763E1B ret

放在一起对比看,能看出这两个方法生成的代码与前面的Main()方法中代码的关系吗?

============================================================================

观察for循环对应的目标代码

for循环对应的是这部分:
//>> for循环初始段:对变量i赋初始值
00E700E9 mov         esi,1
00E700EE xor         edi,edi
//>> for循环体:空
//>> for循环增量段:对变量i累加
00E700F0 add         esi,1
00E700F3 adc         edi,0
//>> for循环条件ver1:
00E700F6 cmp         edi,2
00E700F9 jg          00E70105
00E700FB jl          00E700F0
//>> for循环条件ver2:
00E700FD cmp         esi,540BE400h
00E70103 jb          00E700F0
//>> for循环结束

为什么简单的循环累加会看起来这么复杂呢?回忆起前面提到过的,这段代码使用了超过机器字长的数据类型,64位整型,long。既然机器没有合适的指令去执行long的算术运算,只能把它映射到32位运算上。

上面这段x86汇编,要是用C#来示意的话,类似这样:
// 把64位的i拆分为高32位的iUpper和低32位的iLower
uint iLower = 1;
int iUpper = 0;

LOOP:
iLower += 1; // 假设这个加法溢出了之后会将“carry”变量设为1,否则“carry”为0
iUpper += carry;
if (iUpper > 2) goto NEXT;
if (iUpper < 2) goto LOOP;
// 如果来到这里,则iUpper == 2
if (iLower < 0x540BE400) goto LOOP;

NEXT:

其中x86汇编里的esi对应iLower,edi对应iUpper。可以看出,esi与edi合在一起就组成了原测试代码中的i。对iLower的加法每次溢出,都意味着iUpper需要加一个进位(carry)。到这里还好理解,可是那么复杂的跳转指令是怎么回事?

想想看,10000000000 == 0x2540BE400,把它的高低32位拆开来的话,高32位就是0x2,低32位就是0x540BE400。看出这个数字与生成的汇编的关系了么?因为iUpper会记录变量i的高32位的值,无论iLower怎么变,只要iUpper还没达到2,循环就应该继续;当iUpper达到2时候,则关注点转换到iLower上,看看达到0x540BE400没有。
这段代码里,jg 00E70105(if (iUpper > 2) goto NEXT;)这句实际上是冗余的,不会影响程序的执行结果。

要是换一个数字,生成的代码还会一样吗?如果我们把原测试代码for循环部分的上限换成0x300000000,则对应生成的x86汇编是:
00E700E9 mov         esi,1
00E700EE xor         edi,edi
00E700F0 add         esi,1
00E700F3 adc         edi,0
00E700F6 cmp         edi,3    // 注意这个常量变了
00E700F9 jg          00E70101
00E700FB jl          00E700F0
00E700FD test        esi,esi  // 而这个测试条件的指令都变了
00E700FF jb          00E700F0

结构仍然是一样的,只是在与0作比较时,用TEST指令比用CMP指令更紧凑些而已。由于代码更短了,所以JG指令的跳转目标地址也与前面的版本不一样,不过这个不是我们的关注点。

好,for循环基本上分析清楚了,就是对变量i的累加和循环而已。那么变量j呢?
这里先给出结论:变量j从Main()方法中消失了。
为什么不能把j看成是与i当成同一个变量计算?如何确定它消失了?请看下回分解 ^ ^
  • 大小: 155.8 KB
  • 大小: 65.1 KB
   发表时间:2009-07-15   最后修改:2009-07-15
说到浮点数运算:

从Java 1.4开始,Sun引进了StrictMath这么个东西,其初衷就是不管在什么样的硬件平台上,什么样的OS下,Java的数值计算结果要保持高度的一致,都要符合所谓新的IEEE的标准。结果呢,Sun选择了自由软件fdlibm库函数来作为Java的native code。

将scimark2中较少调用的函数,比如pow, exp, sqrt, log等等单独算算,还是有区别的。
0 请登录后投票
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics