C语言来袭

好吧，现在让我们用C来实现，看看再能榨取多少性能。

注意我没有改变算法，C的算法和之前的3种都是基本相同的：

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <unistd.h>

typedef unsigned long long ULL;

//if failed return 0

ULL sieve(ULL n)

{

char *a = malloc(n+1);

if(!a) return 0;

memset(a,0,n+1);

ULL max = sqrtl(n);

ULL p = 2;

while(p <= max){

for(ULL i=2*p;i<=n;i+=p)

a[i] = 1;

while(a[++p]); /* empty */

}

while(a[n]) n--;

return n;

}

int main(int argc,char **argv)

{

ULL n = 0;

if(argc < 2){

printf("usage %s n\n",argv[0]);

return 1;

}

sscanf(argv[1],"%llu",&n);

if(n == 0){

puts("wrong number format");

return 2;

}

else if(n < 0){

puts("must + number");

return 3;

}

int start = clock();

ULL result = sieve(n);

if(!result){

puts("sieve calc failed!");

return 4;

}

double end = ((1.0 * (clock() - start)) / CLOCKS_PER_SEC) * 1000.0;

printf("max p is %llu (take %f ms)\n",result,end);

return 0;

}

结果只比浏览器版的js稍快一点，可见浏览器js优化的效果之好。不过C的计算非常稳定，不像浏览器中的js多次计算后性能急剧下降。

铛铛铛！大BOSS汇编语言出场

前面我们分别用4种语言写一个素数筛选的算法，分别是

javascript in browser、node.js、ruby和c；

最终的结果是c最快，node.js其次,js in browser虽然也不慢，但极不稳定，所以排在第三，ruby最慢。

现在我们在linux64中用汇编语言重写sieve算法，看看动用最终的武器：汇编语言，我们能不能进一步优化素数筛选算法呢？

如果忘了算法逻辑，不要紧，下面分别再次贴出node.js、ruby以及c的sieve代码：

首先是node.js：

function sieve(n){

var a = new Int8Array(n+1);

var max = Math.floor(Math.sqrt(n));

var p = 2;

while(p <= max){

for(var i=2*p;i<=n;i+=p)

a[i] = 1;

while(a[++p]); /* empty */

}

while(a[n]) n--;

return n;

}

然后是ruby:

def sieve(n)

a = Array.new(n+1);

max = Math.sqrt(n).to_i;

p = 2;

while p<=max do

i = 2*p

while i<=n do

a[i] = 1

i+=p

end

while a[p+=1] == 1 do end

end

while a[n] do n-=1 end

n

end

最后是c的代码：

ULL sieve(ULL n)

{

char *a = malloc(n+1);

if(!a) return 0;

memset(a,0,n+1);

ULL max = sqrtl(n);

ULL p = 2;

while(p <= max){

for(ULL i=2*p;i<=n;i+=p)

a[i] = 1;

while(a[++p]); /* empty */

}

while(a[n]) n--;

return n;

}

下面尝试用汇编重写sieve函数，需要注意的几点是：

• 可以不调用C库中的sqrtx标准函数，直接使用浮点fsqrt指令；
• 可以将绝大部分内存变量放到寄存器中以加速存取；
• 只关心sieve函数的算法，而用c代码调用汇编的sieve，这样可以发挥各自的长处；否则我还得写个读取输入参数的前导代码，不值当的；
• 注意汇编和c的调用接口：在linux64中，参数并不压栈传递；因为sieve只有一个参数，所以放在rdi中传递，返回值还是放在rax中。
• 需要调用mmap申请足够的内存以便做筛表。注意这里没有写足够详细的错误处理，更详细的操作请参考本猫的【linux下64位汇编的系统调用】系列博文。

最后要注意的是，代码优化和代码编写一定不要同时进行！这在所有编程语言中都适用，汇编中尤为重要！否则必成一锅粥鸟！因为谁都不可能上来就写优化后的代码，一定是先功能逻辑正常后在着手考虑优化的问题。本猫第一遍写的是最保守代码，全部变量放在内存中，随用随取，用完保存。在代码逻辑正确后（这时计算sieve 100000000所花时间为4xxx ms）,在逐步将内存变量转放到寄存器中。

要说明的是该段代码肯定还可以进一步优化，但本猫就到这里为止了，希望能够抛砖引玉。先把结果说一下吧：

用汇编写的sieve版本是最快的，超过了c代码，在本猫 Intel(R) Core(TM)2 Duo CPU T7100 @ 1.80GHz上跑出了最快的37xx毫秒，比c版的平均要快100-200毫秒，而且非常稳定。

最后贴出C的main.c和汇编的sieve.s代码:

main.c:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <string.h>

#include <time.h>

#include <unistd.h>

typedef unsigned long long ULL;

ULL sieve(ULL n);

int main(int argc,char **argv){

ULL n = 0;

if(argc < 2){

printf("usage %s n\n",argv[0]);

return 1;

}

sscanf(argv[1],"%llu",&n);

if(n == 0){

puts("wrong number format");

return 2;

}

else if(n < 0){

puts("must + number");

return 3;

}

int start = clock();

ULL result = sieve(n);

if(result == -1){

puts("sieve calc failed!");

return 4;

}

double end = ((1.0 * (clock() - start)) / CLOCKS_PER_SEC) * 1000.0;

printf("max p is %llu (take %f ms)\n",result,end);

return 0;

}

汇编的sieve.s:

section .data

n:dq 0

len:dq 0

addr: dq 0

p:dq 2

max:dq 0

i:dq 2

section .text

global sieve

sieve:

push rbp

push rbx

push rcx

mov rbp,rsp

mov [n],rdi ;save 1st arg to n

inc rdi

mov [len],rdi ;mmap len = n + 1

mov eax,9 ;call syscall mmap

mov rdi,0

mov rsi,[len]

mov rdx,3

mov r10,33

mov r8,-1

mov r9,0

syscall

cmp rax,0xfffffffffffff001 ;mmap error

jb next

mov rax,-1 ;return -1

jmp quit

next: ;save mmap return addr

;FIXME:mmap space always 0 ???

fild qword [n] ;calc sqrt(n) and save result to max

fsqrt

fistp qword [max]

mov r15,[p] ;r15 = p

mov r14,[max] ;r14 = max

mov r13,[n] ;r13 = n

mov r12,[i] ;r12 = i

enter_while:

cmp r15,r14 ;if p<=max

ja quit_while

mov rbx,r15

shl rbx,1

mov r12,rbx

enter_for:

cmp r12,r13

ja quit_for

mov byte [rax + r12],1

add r12,r15

jmp enter_for

quit_for:

inc r15

mov cl,byte [rax + r15]

test cl,cl

jnz quit_for

jmp enter_while

quit_while:

mov cl,byte [rax + r13]

test cl,cl

jz pre_quit

dec r13

jmp quit_while

pre_quit:

mov rax,r13

quit:

mov rsp,rbp

pop rcx

pop rbx

pop rbp

ret

结尾

以上就是JavaScript、Ruby、C和汇编4种语言的速度比较。这只是本猫即兴之作，大家也不必太过较真哦。

希望上面内容可以娱乐到各位程序员和各位吃瓜群众们

最后请称呼我：会4种语言的喵！