This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code. This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler. It allowed me to test the performance of the global property jump optimization I proposed. Two versions were tested: proto1 = optimization of global property calls keeping the argument count setup and check in all cases proto2 = optimization of global property calls without the argument count setup and check when the number of parameters matches the number of arguments The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times: relative time to proto2 Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0) Please examine the x86 code generated by proto2. Note that it performs all the expected dynamic type checks, and also the stack overflow checks. The optimization in proto2 will replace the code of the global property jump: call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler with the direct jump: jmp fib_7 The details are in the attached file. If you have any questions please let me know. Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code? Marc # notes: # # %ecx = context register # %eax = argument 1 of function and return value of function # %edi = return address # %ebp = stack pointer # # function fib(x) # { # if (x < 2) # return x; # else # return fib(x-1) + fib(x-2); # } fib_7: # main entry point of "fib" subb $1,%cl # check that arg_count = 1 jne _13 _14: testb $3,%al # check that x is a fixnum jne _17 cmpl $8,%eax # compare it to 2 jge else_16 then_15: jmp *%edi # return x (which is already in %eax) when x<2 _13: addb $1,%cl # handle arg_count != param_count pushl %ecx xorb %cl,%cl call *16(%ecx) jmp _14 _17: pushl %eax # handle generic "x < 2" pushl $8 call *28(%ecx) jl then_15 jmp else_16 else_16: movl %eax,-4(%ebp) # save x for later testb $3,%al # check that x is a fixnum jne _19 subl $8,%eax # "x - 2" jo _20 # check for overflow _21: # no overflow movl %edi,-8(%ebp) # save return address on stack addl $-8,%ebp # allocate frame on stack cmpl %ebp,(%ecx) # check for stack overflow ja _22 _23: # jump to global property "fib" movl $_18,%edi # setup return address movl 4(%ecx),%esi # setup "this" argument (= global object) call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler _20: addl $8,%eax # undo subtraction that overflowed _19: pushl %eax # handle generic "x - 2" pushl $8 call *28(%ecx) jmp _21 _22: call *12(%ecx) # handle stack overflow jmp _23 ALIGN_RET_POINT FRAME_DESCR .long RET_POINT_TYPE RET_POINT_HEADER_END _18: # return point of call fib(x-2) movl 4(%ebp),%ebx # get x testb $3,%bl # check that x is a fixnum jne _25 subl $4,%ebx # "x - 1" jo _26 # check for overflow _27: movl %eax,-4(%ebp) # save result of call fib(x-2) movl %ebx,%eax # prepare argument of call fib(x-1) addl $-4,%ebp # grow frame on stack cmpl %ebp,(%ecx) # check for stack overflow ja _28 _29: # jump to global property "fib" movl $_24,%edi # setup return address movl 4(%ecx),%esi # setup "this" argument (= global object) call jump_global_prop_handler # perform jump to global property .long 3 # fib .byte 1,0 # number of arguments and filler _26: addl $4,%ebx # undo subtraction that overflowed _25: pushl %ebx # handle generic "x - 1" pushl $4 call *28(%ecx) jmp _27 _28: call *12(%ecx) # handle stack overflow jmp _29 ALIGN_RET_POINT FRAME_DESCR .long RET_POINT_TYPE RET_POINT_HEADER_END _24: # return point of call fib(x-1) testb $3,%al # check that result of call fib(x-1) is a fixnum jne _30 testb $3,(%ebp) # check that result of call fib(x-2) is a fixnum jne _30 addl (%ebp),%eax # add result of calls fib(x-1) and fib(x-2) jo _31 # check for overflow _32: addl $12,%ebp # remove stack frame jmp *-8(%ebp) # jump to return address _31: subl (%ebp),%eax # undo addition that overflowed _30: pushl %eax # handle generic "fib(x-1) + fib(x-2)" pushl -12(%ebp) call *28(%ecx) jmp _32
Afficher les réponses par date
Le 11-05-15 23:36 , Marc Feeley a écrit :
This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code.
This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler. I would be interested in using it too, is it in scheme? Could you put it in our private repository?
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2 Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0) Those are great news, how does that compare to gcc? If you have any questions please let me know. You did not show how to handle closures. We would need to store the function object pointer in addition to the entry point of the code at the call site. It should only need a little modification of the patching code.
Also, what if the code or the function object is moved by the GC? Should we invalidate all the call site caches or should we patch them with the new addresses? I could see a similar mecanism used to lazily compile functions. The function could be stored in an AST, HIR or string representation. When jumping to the function the first time, the compiler would first compile the function and then replace the entry point in the function object by the compiled code. This would be complimentary to the global call optimization by delaying the global function call site patching until the entry point of the compiled code is known.
Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code?
Marc To follow your current design, we could introduce a global function call instruction in the IR that would take a string property, a this object and the arguments (instead of the function object, the this object and the arguments for a regular CallInstr). This part should be simple.
Additionnally, we would need to modify the global object layout to have a pointer to the call site list in addition to the value of a property. Again, that should be simple with the layout system. The tricky part, I think, is how to implement the different handlers. I would try to separate the implementation of those such that: 1. The layout of the call sites is known only to the backend 2. The patching code is done by the backend, including the list traversal to invalidate the call sites 3. The global object layout and property lookup is implemented using the layout and primitive system I would guess it could be done in a couple of days. Erick
On 2011-05-16, at 1:52 PM, Erick Lavoie wrote:
Le 11-05-15 23:36 , Marc Feeley a écrit :
This weekend I improved my prototype compiler which compiles JS to x86, using the global property jump optimization. The compiler is rather minimal and handles just enough to compile fib and similar simple code.
This prototype is mainly useful to explore various implementation approaches quickly, without the burden of the complete Tachyon compiler. I would be interested in using it too, is it in scheme? Could you put it in our private repository?
It is in JS and I just pushed it to the repo. It is in source/parser. The main part of the compiler is js86-compile.js . Just cd source/parser and do % ./js86 fib.js It will generate fib.js.S and fib.js.exe, and executes it. I've tested it on Mac OS X and Linux. The compiler accepts a bunch of options to enable/disable various code generation features (see the end of js86-compile.js). For example, to call handlers through the context do: % ./js86 -ctx-handlers fib.js On my MacBook Pro, calling the handlers through the context gives a 10% performance boost for fib (and generates shorter code).
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2 Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0) Those are great news, how does that compare to gcc?
You try it!
If you have any questions please let me know. You did not show how to handle closures. We would need to store the function object pointer in addition to the entry point of the code at the call site. It should only need a little modification of the patching code.
No modifications are necessary when closures are represented as a piece of code (see my paper "Closure generation based on viewing LAMBDA as EPSILON plus COMPILE" on my web page).
Also, what if the code or the function object is moved by the GC? Should we invalidate all the call site caches or should we patch them with the new addresses?
I don't know. That's the kind of thing that has to be tried to see what works best.
I could see a similar mecanism used to lazily compile functions. The function could be stored in an AST, HIR or string representation. When jumping to the function the first time, the compiler would first compile the function and then replace the entry point in the function object by the compiled code. This would be complimentary to the global call optimization by delaying the global function call site patching until the entry point of the compiled code is known.
Interesting idea.
Here's a question for Maxime and Erick... can you estimate the work needed to get Tachyon to generate similar x86 code?
Marc To follow your current design, we could introduce a global function call instruction in the IR that would take a string property, a this object and the arguments (instead of the function object, the this object and the arguments for a regular CallInstr). This part should be simple.
Additionnally, we would need to modify the global object layout to have a pointer to the call site list in addition to the value of a property. Again, that should be simple with the layout system.
The tricky part, I think, is how to implement the different handlers. I would try to separate the implementation of those such that: 1. The layout of the call sites is known only to the backend 2. The patching code is done by the backend, including the list traversal to invalidate the call sites 3. The global object layout and property lookup is implemented using the layout and primitive system
I would guess it could be done in a couple of days.
If it can be done quickly lets do it. Marc
On 2011-05-16, at 11:13 PM, chevalma@iro.umontreal.ca wrote:
On my MacBook Pro, calling the handlers through the context gives a 10% performance boost for fib (and generates shorter code).
Calling them through the context as opposed to static linking?
Yes. Here are the measurements on my MacBook Pro: bash-3.2$ ./js86 fib.js;fgrep -B 1 ".long 3 # fib" fib.js.S real 0m1.599s user 0m1.595s sys 0m0.002s call jump_global_prop_handler .long 3 # fib -- call deoptimize_global_prop_handler .long 3 # fib -- call jump_global_prop_handler .long 3 # fib -- call jump_global_prop_handler .long 3 # fib bash-3.2$ ./js86 -ctx-handlers fib.js;fgrep -B 1 ".long 3 # fib" fib.js.S real 0m1.448s user 0m1.446s sys 0m0.002s call *24(%ecx) .long 3 # fib -- call *20(%ecx) .long 3 # fib -- call *24(%ecx) .long 3 # fib -- call *24(%ecx) .long 3 # fib Note that a direct call takes 5 bytes to encode, and a call through the context takes 3 bytes. I'm not ready to generalize the performance to other programs. Fib is 10% faster with handlers in the context, but this may be due to changing the alignment of instructions in the cache leading to fewer cache misses. We need to average things over many programs to see if context handlers improve performance in general. Marc
On 2011-05-15, at 11:36 PM, Marc Feeley wrote:
The results are very good. On fib(40), proto2 generate faster code than V8 (1.5x) and SpiderMonkey (2.3x), and Tachyon (18x). There is a 1.2x difference between proto1 and proto2 (in other words, there is a 20% overhead to setup and check argument counts). Here are the detailed running times:
relative time to proto2 Tachyon 29.613 (18.3) SM 3.700 ( 2.3) V8 2.397 ( 1.5) proto1 2.000 ( 1.2) proto2 1.614 ( 1.0)
I have improved the code generation of my prototype compiler. fib(40) now takes 1.42 seconds, or 1.7 times faster than V8. The changes are on the repo. Marc
participants (3)
-
chevalma@iro.umontreal.ca -
Erick Lavoie -
Marc Feeley