测试成绩。仅供大家参考。

panda · #1 (**permalink**) 2003-05-19

panda: 25s
zweilu: 31s
pora: 18s
wolf: 26s
splash: 40s
magmng: 21s
Elmister: 19s
本人平台：
CPU: PIII-700MHz * 2
RAM: 512M
OS: Win2K
Compiler: VS.net

zweily · #2 (**permalink**) 2003-05-19

不完全测试版？ :P
P.S. 老兄，我的名字错了

magmng · #3 (**permalink**) 2003-05-19

zweily's code 12
codinggirl's code 29
pora's code 7
wolf's code 16
splash's code 10
panda's code 16
magmng's code 10
Innocentius' code 3
Elmister's code 10
ajoo's code 11

Innocentius 在我的机器上的结果让人吃惊

P4赛扬1.7G
512M Rom
Windows 2000 SP2
Norton close

Innocentius · #4 (**permalink**) 2003-05-19

如果pora没有提供示范程序，或许这次竞赛的结果还有更大的不同，建议以后不要给出示范程序，但是要给出测试用的数据（例如这次就是编码前与编码后的数据是什么），或者给出一个校验程序，用于帮助我们检验程序的正确性，但是不要提供源代码。

一旦给出了示范，很容易限制了思维。

Innocentius · #5 (**permalink**) 2003-05-19

panda怎么没有给出我的程序的速度？

panda · #6 (**permalink**) 2003-05-19

我机器上编译通不过，因为有事没仔细查就skip了。

polyrandom · #7 (**permalink**) 2003-05-19

Inno的程序有两个constant没有定义，所以不能编译。

zweily · #8 (**permalink**) 2003-05-19

似乎在不同的机器上，排名也不一样

Innocentius · #9 (**permalink**) 2003-05-19

有两个变量的位置最后做了一点调整，然后就出现这样的问题了

我把代码重新贴了一下，再试试咯

abp · #10 (**permalink**) 2003-05-19

我找了台P4，Inno的代码（5秒）比pora的（9秒）快4秒左右。因为Inno每次执行前没有把output resize成0，我帮他加了一句后，时间变为8秒，还是比pora快一秒。
这些区别与处理器的架构有关，具体原因，我暂时也不知道。等待Inno和pora的文章。

顺便说一句，这次Inno和pora的代码都不是完全正确的，pora的边界判断有问题，Inno在最后四个输出字节上有问题。不过瑕不掩瑜，整体的优化过程都是很清晰的，只是时间匆忙，不及测试而已。（甚至可能是优化是改错的。）

Innocentius · #11 (**permalink**) 2003-05-20

由于我自己使用的是P4和汇编，因此就P4和汇编这两个角度对我和pora的程序进行一些分析。

我将pora的程序通过VC.NET的汇编输出(编译器命令行 /O2 /Ob1 /Oy /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /GF /FD /EHsc /ML /GS /Gy /FAcs /Fa"Release/" /Fo"Release/" /Fd"Release/vc70.pdb" /W3 /nologo /c /Wp64 /Zi /TP)，然后进行下面的比较：

将算法分为三个部分：主循环以及循环内的主要编码部分（S1），主循环内的行分割处理部分（S2），以及最后四个字节的处理部分。由于最后一部分对性能的影响极小，因此仅讨论前两部分。

不考虑算法，从汇编的角度上看，有以下数据：

　　　　　指令数　　指令长度　　平均指令长度　　循环数
Inno S1:　21　　　 67　　　　　3.2　　　　　　19
Inno S2:　5　　　　11　　　　　2.2　　　　　　1
pora S1:　22　　　 83　　　　　3.8　　　　　　19
pora S2:　3　　　　13　　　　　4.3　　　　　　1

注：
1、上面指令长度和平均指令长度的单位都是字节
2、循环数是指相对而言的循环次数比例。
3、关于pora的S2部分见下文的说明

下面对所用到的指令进行一下统计：

　　　　　MOV　ADD　SHL　CMP　Jcc　INC　BSWAP
Inno S1:　6　　6　　　4　　2　　　2　　　　 1
Inno S2:　1　　1　　　　　　　　　1　　2
pora S1:　15　 2　　　3　　1　　　1
pora S2:　2　　1

注：
ADD指令包括：ADD，AND，XOR
SHL指令包括：SHL，SHR
Jcc指令包括：JMP以及JGE、JLE等
INC指令包括：INC/DEC

下面是各指令的周期时间（根据Intel的Optimization Reference Manual）：

　　　　　　　　　潜伏期　　指令时间　合计时间
MOV　　　　　　　0.5　　　0.5　　　1
ADD/AND/XOR　　0.5　　　0.5　　　1
SHL/SHR　　　　　4 or 1　1　　　　5
CMP　　　　　　　0.5　　　0.5　　　1
Jcc/JMP　　　　　　-　　　 0.5　　　0.5
INC/DEC　　　　　1　　　 0.5　　　1.5
BSWAP　　　　　　7　　　 1　　　　8

注：
1、上表中单位均为指令周期
2、由于P4以乱序方式执行指令，对于SHL/SHR指令，其指令潜伏期可能最少为1

可以认为，一个指令的执行时间是潜伏期和指令执行时间之和，因此由上面两个表，可以得出“纯”编码循环在P4上的执行时间比例：

　　　　　合计指令周期　　总循环花费时间周期
Inno S1: 43　　　　　　　817
Inno S2: 5.5　　　　　　　5.5
pora S1: 33.5　　　　　　636.5
pora S2: 3　　　　　　　　3

这样得出理论时间为（每19个循环，单位是指令周期）：

Inno: 822.5
pora: 639.5

比值为：1.29

而在我自己计算机上实测的结果为（单位为毫秒）：

Inno: 335
pora: 305

比值为：1.10

从这点看，结果还是基本符合的。然而对于abp以及其他朋友测出来我的比pora的程序快100％以上，似乎有些问题。

对于这个分析结果看，有几点很有意思：

1、pora的代码中，MOV指令使用率为68％，而MOV指令是P4中最快的指令之一，因此使得速度有很大的提高；

2、移位指令花费的时间远比MOV、ADD等指令多，而我使用了BSWAP指令则更是最大的失败（但是就这个算法来说并没有别的指令可以代替这个功能）；其实我原先用C++实现的这段算法中采用了更多的移位指令和逻辑指令，使得这个程序花费的时间是我现在实现的5倍以上！

3、pora将我们通常用的for(i=0; i+3＜size; i=+3)用指针的比较(real_input==real_input_end)来代替，少了好几条指令；

3、前面诸位讨论的读4个CHAR和读1个DWORD的事情，就从指令周期来看显然是读取1个DWORD更加快，因为前者需要四条MOV指令；

4、VC对pora的程序进行了一个很有意思的优化，将循环展开：

代码:


优化前：

   for(;;) 
   { 
      real_output[0]=BASE64_CODE_SHIFT4[real_input[0]]; 
      real_output[1]=BASE64_CODE[real_input[0]*16+real_input[1]/16]; 
      real_output[2]=BASE64_CODE[real_input[1]*4+real_input[2]/64]; 
      real_output[3]=BASE64_CODE[real_input[2]]; 
      real_input+=INPUT_CELL; 
      real_output+=OUTPUT_CELL; 
      if(real_input==real_input_end) 
         break; 
      --ticks; 
      if(!ticks) 
      { 
         ticks=LINE_COUNT/OUTPUT_CELL; 
         *(unsigned short*)real_output='\r\n'; 
         real_output+=sizeof(unsigned short); 
      } 
   }

成为这样的代码：

代码:


优化后：

   real_output[0]=BASE64_CODE_SHIFT4[real_input[0]]; 
   real_output[1]=BASE64_CODE[real_input[0]*16+real_input[1]/16]; 
   real_output[2]=BASE64_CODE[real_input[1]*4+real_input[2]/64]; 
   real_output[3]=BASE64_CODE[real_input[2]]; 
   real_input+=INPUT_CELL; 
   real_output+=OUTPUT_CELL; 
   if(real_input==real_input_end) 
      break; 
l1:
   --ticks; 
   if(!ticks) 
   { 
      ticks=LINE_COUNT/OUTPUT_CELL; 
      *(unsigned short*)real_output='\r\n'; 
      real_output+=sizeof(unsigned short); 
   } 
   real_output[0]=BASE64_CODE_SHIFT4[real_input[0]]; 
   real_output[1]=BASE64_CODE[real_input[0]*16+real_input[1]/16]; 
   real_output[2]=BASE64_CODE[real_input[1]*4+real_input[2]/64]; 
   real_output[3]=BASE64_CODE[real_input[2]]; 
   real_input+=INPUT_CELL; 
   real_output+=OUTPUT_CELL; 
   if(real_input==real_input_end) 
      break; 
   goto l1;

如何评价这个优化呢？我看不出这个优化有什么作用，最多省略一次比较而已，但是要增加一倍的代码，似乎有些得不偿失。

上次pora和我说，或许这个程序还能更加快一点，不过我现在认为已经不会更快了，因为VC的优化实际上已经很彻底了。

由于我手边没有AMD CPU的资料，因此暂时不能分析在AMD机器上的情况。

abp · #12 (**permalink**) 2003-05-20

引用:

作者: Innocentius

从这点看，结果还是基本符合的。然而对于abp以及其他朋友测出来我的比pora的程序快100％以上，似乎有些问题。

这个是因为你原先的代码里面没有加output.resize(0)，而pora加了。如果不考虑这个，pora的每100遍比你慢1秒左右，和你估计的差不多。

Innocentius · #13 (**permalink**) 2003-05-20

然而在我自己的P4上却是pora的快，我上面文章里有数据。

polyrandom · #14 (**permalink**) 2003-05-20

我在我的P4上测试，也是你的快10%。什么时候我到我的本本上试试看，看看是什么结果。
我估计我们的代码其实都优化的差不多了，关键是各个cpu的流水线和cache大小不一样。
其实谁快谁慢不重要，重要的是学到方法。看到你把整个指令线的速度分析出来，非常佩服！

Innocentius · #15 (**permalink**) 2003-05-20

更正：

关于指令时间，有两个词：

Latency（潜伏期），Intel对这个词的解释是指完成指令要求的所有微操作的时间。

Throughput（吞吐量），Intel对这个词的解释是指在释放特定端口以便继续执行相同指令之前要等待的时间。

我将Throughput错误理解为指令执行时间了。

Elminster · #16 (**permalink**) 2003-05-20

精彩精彩！

我自己也做了一些简单的测试。在我的 Athlon XP 1600+ 上面，500 次运行，Inno 的代码耗时 36sec，Pora 的代码耗时 42sec，我自己的代码 40sec。有趣的是，当我把 Pora 程序中编码一个24bit组的代码移到我的代码中后，我的程序的运行时间变为 43sec。

似乎可以得出这样一个结论：用查表来代替移位对效率的影响是依赖于机器的。

另外一方面，CPU 结构越来越复杂，编译器越来越复杂，以前很多行之有效的优化手段现在已经不再适用，效果已经变得模糊。我试了一下把编码一行的循环展开：

代码:

// encode 1 line. number of encoded groups is given by template parameter "G"
template<size_t G>
inline void encode_line(const unsigned char* in, unsigned char* out)
{
	encode_group(in, out);
	encode_line<G-1>(in+3, out+4);
}

template<>
inline void encode_line<1>(const unsigned char* in, unsigned char* out)
{
	encode_group(in, out);
}

... ...

for(; line>1; --line)
{
	encode_line<line_group>(&input[i], &output[j]);
	i+=in_line_len; j+=line_len;
	*( (unsigned short*)&output[j] ) = crlf;
}

然而对程序的性能基本没有影响。看来程序大小、数据大小、时间空间之间的折衷关系是越来越复杂了呀。

Elminster · #17 (**permalink**) 2003-05-20

补充一下环境：xp 1600+、256M DDR、w2k sp3、vs.net 2003、最大速度优化。

polyrandom · #18 (**permalink**) 2003-05-20

我也试过展开，这样就可以不用ticks。但是发觉在我的机器上反而慢了。
我曾经用过全展开表，但是很慢，耗时多一倍。
其实这个小程序的基本算法很确定（我的第一个实现，什么都没优化过，用位移的，只比我最后的实现慢25%。）
大型算法/结构/数据流的优化往往比这种非常小的局部优化有效得多。

Innocentius · #19 (**permalink**) 2003-05-20

pora说的全展开表是不是指那个16M的表？如果是的话，那么我觉得速度变慢是因为这个表太大，以至于引起操作系统的内存换页，而换页操作的代价是很大的。

移位操作花费的时间变化很大，Intel的资料中就说，其指令周期从1～4都是可能的。

polyrandom · #20 (**permalink**) 2003-05-20

那个表64M，不是因为操作系统换页，是因为cache missing。

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式