-
-
[原创]javascript、ruby和C性能一瞥(3) :上汇编
-
发表于: 2015-4-16 18:26 12319
-
在博文(1)和(2)里分别用了4中方式写一个素数筛选的算法,分别是javascript in browser、node.js、ruby和c;最终的结果是c最快,node.js其次,js in b虽然也不慢,但极不稳定,所以排在第三,ruby最慢。
现在我们在linux64中用汇编语言重写sieve算法,看看动用最终的武器:汇编语言,我们能不能进一步优化素数筛选算法。
如果忘了算法逻辑,不要紧,下面分别再次贴出node.js、ruby以及c的sieve代码:
首先是node.js:
然后是ruby:
最后是c的代码:
下面尝试用汇编重写sieve函数,需要注意的几点是:
1 可以不调用C库中的sqrtx标准函数,直接使用浮点fsqrt指令;
2 可以将绝大部分内存变量放到寄存器中以加速存取;
只关心sieve函数的算法,而用c代码调用汇编的sieve,这样可以发挥各自的长处;否则我还得写个读取输入参数的前导代码,不值当的;
3 注意汇编和c的调用接口:在linux64中,参数并不压栈传递;因为sieve只有一个参数,所以放在rdi中传递,返回值还是放在rax中。
4 需要调用mmap申请足够的内存以便做筛表。注意这里没有写足够详细的错误处理,更详细的操作请参考本猫的【linux下64位汇编的系统调用】系列博文。
5 最后要注意的是,代码优化和代码编写一定不要同时进行!这在所有编程语言中都适用,汇编中尤为重要!否则必成一锅粥鸟!因为谁都不可能上来就写优化后的代码,一定是先功能逻辑正常后在着手考虑优化的问题。本猫第一遍写的是最保守代码,全部变量放在内存中,随用随取,用完保存。在代码逻辑正确后(这时计算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:
汇编的sieve.s:
现在我们在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函数,需要注意的几点是:
1 可以不调用C库中的sqrtx标准函数,直接使用浮点fsqrt指令;
2 可以将绝大部分内存变量放到寄存器中以加速存取;
只关心sieve函数的算法,而用c代码调用汇编的sieve,这样可以发挥各自的长处;否则我还得写个读取输入参数的前导代码,不值当的;
3 注意汇编和c的调用接口:在linux64中,参数并不压栈传递;因为sieve只有一个参数,所以放在rdi中传递,返回值还是放在rax中。
4 需要调用mmap申请足够的内存以便做筛表。注意这里没有写足够详细的错误处理,更详细的操作请参考本猫的【linux下64位汇编的系统调用】系列博文。
5 最后要注意的是,代码优化和代码编写一定不要同时进行!这在所有编程语言中都适用,汇编中尤为重要!否则必成一锅粥鸟!因为谁都不可能上来就写优化后的代码,一定是先功能逻辑正常后在着手考虑优化的问题。本猫第一遍写的是最保守代码,全部变量放在内存中,随用随取,用完保存。在代码逻辑正确后(这时计算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
赞赏记录
参与人
雪币
留言
时间
飘零丶
为你点赞~
2024-5-31 04:54
shinratensei
为你点赞~
2024-5-31 04:44
一笑人间万事
为你点赞~
2023-2-27 02:25
赞赏
他的文章
看原图
赞赏
雪币:
留言: