Efficient Compilation of Tail Calls and Continuations to JavaScript
Eric Thivierge is in Copenhagen today, at the Scheme Workshop, presenting our latest paper: "Efficient Compilation of Tail Calls and Continuations to JavaScript" You can get the paper on the Scheme Worshop web page: http://users-cs.au.dk/danvy/sfp12/programme-sfp12.html It describes the implementation of tail calls and continuations in Gambit-JS and evaluates its performance. Even if you are not specifically interested in the JavaScript back-end the paper may be interesting to read as it provides a brief explanation of the Gambit Virtual Machine (GVM) and compiler front-end, and a complete example of compilation from Scheme, to GVM, to JavaScript. The performance evaluation (see attached tables) shows that the approach used by Gambit-JS is consistently faster than Scheme2JS and Spock. Marc Execution times using V8 (Chrome 21.0.1180.89): Gambit-JS Scheme2JS Spock fib35 .80 1.54 1.9x 2.40 3.0x nqueens12 .72 .76 1.1x 2.33 3.3x oddeven .83 1.92 2.3x 5.62 6.8x ctak .18 17.64 95.9x .59 3.2x contfib30 1.17 106.01 90.9x 3.38 2.9x btsearch2000 1.35 25.40 18.8x 7.93 5.9x threads10 1.34 24.68 18.5x 4.40 3.3x Execution times using JagerMonkey (Firefox 15.0.1): Gambit-JS Scheme2JS Spock fib35 1.07 7.66 7.2x 20.73 19.4x nqueens12 1.49 2.62 1.8x 12.97 8.7x oddeven 1.09 1.93 1.8x 33.91 31.1x ctak 1.25 30.38 24.3x 1.86 1.5x contfib30 5.88 156.79 26.7x 10.61 1.8x btsearch2000 11.19 27.16 2.4x 16.54 1.5x threads10 6.97 34.36 4.9x 22.11 3.2x Execution times using Nitro (Safari 6.0): Gambit-JS Scheme2JS Spock fib35 1.32 6.53 4.9x 84.69 64.2x nqueens12 1.31 1.89 1.4x 45.15 34.4x oddeven 2.52 1.55 .6x 143.97 57.1x ctak .30 52.88 177.4x 4.18 14.0x contfib30 1.60 2311.69 1443.0x 25.98 16.2x btsearch2000 3.46 102.98 29.7x 92.02 26.6x threads10 3.03 74.21 24.5x 74.88 24.7x
Awesome. For reference, is the implementation of Gambit2JS available anywhere? Best regards, Mikael 2012/9/9 Marc Feeley <feeley@iro.umontreal.ca>
Eric Thivierge is in Copenhagen today, at the Scheme Workshop, presenting our latest paper:
"Efficient Compilation of Tail Calls and Continuations to JavaScript"
You can get the paper on the Scheme Worshop web page: http://users-cs.au.dk/danvy/sfp12/programme-sfp12.html
It describes the implementation of tail calls and continuations in Gambit-JS and evaluates its performance.
Even if you are not specifically interested in the JavaScript back-end the paper may be interesting to read as it provides a brief explanation of the Gambit Virtual Machine (GVM) and compiler front-end, and a complete example of compilation from Scheme, to GVM, to JavaScript.
The performance evaluation (see attached tables) shows that the approach used by Gambit-JS is consistently faster than Scheme2JS and Spock.
Marc
Execution times using V8 (Chrome 21.0.1180.89):
Gambit-JS Scheme2JS Spock fib35 .80 1.54 1.9x 2.40 3.0x nqueens12 .72 .76 1.1x 2.33 3.3x oddeven .83 1.92 2.3x 5.62 6.8x ctak .18 17.64 95.9x .59 3.2x contfib30 1.17 106.01 90.9x 3.38 2.9x btsearch2000 1.35 25.40 18.8x 7.93 5.9x threads10 1.34 24.68 18.5x 4.40 3.3x
Execution times using JagerMonkey (Firefox 15.0.1):
Gambit-JS Scheme2JS Spock fib35 1.07 7.66 7.2x 20.73 19.4x nqueens12 1.49 2.62 1.8x 12.97 8.7x oddeven 1.09 1.93 1.8x 33.91 31.1x ctak 1.25 30.38 24.3x 1.86 1.5x contfib30 5.88 156.79 26.7x 10.61 1.8x btsearch2000 11.19 27.16 2.4x 16.54 1.5x threads10 6.97 34.36 4.9x 22.11 3.2x
Execution times using Nitro (Safari 6.0):
Gambit-JS Scheme2JS Spock fib35 1.32 6.53 4.9x 84.69 64.2x nqueens12 1.31 1.89 1.4x 45.15 34.4x oddeven 2.52 1.55 .6x 143.97 57.1x ctak .30 52.88 177.4x 4.18 14.0x contfib30 1.60 2311.69 1443.0x 25.98 16.2x btsearch2000 3.46 102.98 29.7x 92.02 26.6x threads10 3.03 74.21 24.5x 74.88 24.7x
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 2013-09-09, at 9:33 AM, Mikael <mikael.rcv@gmail.com> wrote:
Awesome.
For reference, is the implementation of Gambit2JS available anywhere?
Yes. It is in the standard release of Gambit. You need to use the option "-target js" to gsc. For example: % cat fib.scm (declare (standard-bindings) (extended-bindings) (not safe) (fixnum) (block) ) (define (fib n) (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib n)) (define start (real-time-milliseconds)) (println (fib 30)) (define end (real-time-milliseconds)) (println (- end start)) % gsc -c -target js fib.scm % js fib.js 832040 2035 Marc
Marc, Thanks for the example. When I ran it, I got the following: steve@steve-Satellite-L555D ~ $ js fib.js js: uncaught JavaScript runtime exception: TypeError: Cannot find function real-time-milliseconds in object [object Object]. I'm running Gambit 4.6.7 on a 64-bit Linux Mint 14. Steve ________________________________ From: Marc Feeley <feeley@iro.umontreal.ca> To: Mikael <mikael.rcv@gmail.com> Cc: gambit-list@iro.umontreal.ca Sent: Monday, September 16, 2013 9:29 PM Subject: Re: [gambit-list] Efficient Compilation of Tail Calls and Continuations to JavaScript On 2013-09-09, at 9:33 AM, Mikael <mikael.rcv@gmail.com> wrote:
Awesome.
For reference, is the implementation of Gambit2JS available anywhere?
Yes. It is in the standard release of Gambit. You need to use the option "-target js" to gsc. For example: % cat fib.scm (declare (standard-bindings) (extended-bindings) (not safe) (fixnum) (block) ) (define (fib n) (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib n)) (define start (real-time-milliseconds)) (println (fib 30)) (define end (real-time-milliseconds)) (println (- end start)) % gsc -c -target js fib.scm % js fib.js 832040 2035 Marc _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Hallo, On Tue, Sep 17, 2013 at 5:09 PM, Steve Graham <jsgrahamus@yahoo.com> wrote:
steve@steve-Satellite-L555D ~ $ js fib.js js: uncaught JavaScript runtime exception: TypeError: Cannot find function real-time-milliseconds in object [object Object].
I'm running Gambit 4.6.7 on a 64-bit Linux Mint 14.
FWIW, the example worked for me with Gambit-C 4.7.0 on OS X 10.8.5 compiled with GCC 4.8.1. Cheers, -- -alex http://unendli.ch/
On 2013-09-17, at 11:09 AM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Marc,
Thanks for the example.
When I ran it, I got the following:
steve@steve-Satellite-L555D ~ $ js fib.js js: uncaught JavaScript runtime exception: TypeError: Cannot find function real-time-milliseconds in object [object Object].
I'm running Gambit 4.6.7 on a 64-bit Linux Mint 14.
The JS backend is in constant evolution (and is currently incomplete). You need to try with the latest Gambit version. Marc
Where do I find instructions for building Gambit from source code? Thanks, Steve ________________________________ From: Marc Feeley <feeley@iro.umontreal.ca> To: Steve Graham <jsgrahamus@yahoo.com> Cc: "gambit-list@iro.umontreal.ca" <gambit-list@iro.umontreal.ca> Sent: Tuesday, September 17, 2013 9:48 AM Subject: Re: [gambit-list] Efficient Compilation of Tail Calls and Continuations to JavaScript On 2013-09-17, at 11:09 AM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Marc,
Thanks for the example.
When I ran it, I got the following:
steve@steve-Satellite-L555D ~ $ js fib.js js: uncaught JavaScript runtime exception: TypeError: Cannot find function real-time-milliseconds in object [object Object].
I'm running Gambit 4.6.7 on a 64-bit Linux Mint 14.
The JS backend is in constant evolution (and is currently incomplete). You need to try with the latest Gambit version. Marc
On 2013-09-17, at 2:17 PM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Where do I find instructions for building Gambit from source code?
Read the README at https://github.com/feeley/gambit Marc Quick-install instructions for a typical installation ----------------------------------------------------- git clone https://github.com/feeley/gambit.git cd gambit ./configure --enable-single-host make -j4 bootstrap make -j4 bootclean make -j4 bootstrap make -j4 bootclean make -j4 make check sudo make install Detailed installation instructions are given in the file "INSTALL.txt".
Found it. Thanks. Why did you define fib twice? Steve ________________________________ From: Marc Feeley <feeley@iro.umontreal.ca> To: Steve Graham <jsgrahamus@yahoo.com> Cc: "gambit-list@iro.umontreal.ca" <gambit-list@iro.umontreal.ca> Sent: Tuesday, September 17, 2013 12:54 PM Subject: Re: [gambit-list] Efficient Compilation of Tail Calls and Continuations to JavaScript On 2013-09-17, at 2:17 PM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Where do I find instructions for building Gambit from source code?
Read the README at https://github.com/feeley/gambit Marc Quick-install instructions for a typical installation ----------------------------------------------------- git clone https://github.com/feeley/gambit.git cd gambit ./configure --enable-single-host make -j4 bootstrap make -j4 bootclean make -j4 bootstrap make -j4 bootclean make -j4 make check sudo make install Detailed installation instructions are given in the file "INSTALL.txt".
On 2013-09-17, at 3:02 PM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Found it. Thanks.
Why did you define fib twice?
The definition is: (define (fib n) (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib n)) So there is a global function called fib, in which is defined an internal function called fib. This allows the compiler to call the internal fib more efficiently, without refering to a global variable. The semantics of Scheme are such that if the fib global variable is redefined, a recursion on the global variable fib would have to call the new definition. Such a redefinition is actually what happens when you do (trace fib). I notice that in the code there is a (declare (block)) which actually makes the internal definition trick needless. The bottom line is that I did this for performance reasons. Marc
Works great on 4.7.0. Thanks, Marc Steve ________________________________ From: Marc Feeley <feeley@iro.umontreal.ca> To: Steve Graham <jsgrahamus@yahoo.com> Cc: "gambit-list@iro.umontreal.ca" <gambit-list@iro.umontreal.ca> Sent: Tuesday, September 17, 2013 9:48 AM Subject: Re: [gambit-list] Efficient Compilation of Tail Calls and Continuations to JavaScript On 2013-09-17, at 11:09 AM, Steve Graham <jsgrahamus@yahoo.com> wrote:
Marc,
Thanks for the example.
When I ran it, I got the following:
steve@steve-Satellite-L555D ~ $ js fib.js js: uncaught JavaScript runtime exception: TypeError: Cannot find function real-time-milliseconds in object [object Object].
I'm running Gambit 4.6.7 on a 64-bit Linux Mint 14.
The JS backend is in constant evolution (and is currently incomplete). You need to try with the latest Gambit version. Marc
participants (4)
-
Alex Queiroz -
Marc Feeley -
Mikael -
Steve Graham