July 2013 - Gambit-list - mailman.iro.umontreal.ca

Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi
by Bradley Lucier 07 Apr '22

07 Apr '22

Bakul Shah wrote a particularly elegant Scheme program for Chudnovskys' algorithm for pi based on the Common Lisp program here: https://bitbucket.org/tarballs_are_good/numericl/src/5fe8fe7089f48ab1c8a388… Nick Craig-Wood wrote a Python program using the GMP multiprecision library that appears to use exactly the same algorithm here: http://www.craig-wood.com/nick/articles/pi-chudnovsky/ I modified both programs a bit and include them here. They time the calculation of $10^n$ digits of pi for $n=1,2,3,4,5,6,7$. The results are heine:~/programs/gambiteer/gambit> !py python pi_chudnovsky_bs_gmpy.py 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 ('chudnovsky_gmpy_mpz_bs: digits', 10, 'time', 1.0967254638671875e-05) ('chudnovsky_gmpy_mpz_bs: digits', 100, 'time', 3.0040740966796875e-05) Last 5 digits 70679 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000, 'time', 0.00025582313537597656) Last 5 digits 01989 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000, 'time', 0.00386810302734375) Last 5 digits 75678 OK ('chudnovsky_gmpy_mpz_bs: digits', 100000, 'time', 0.0834801197052002) Last 5 digits 24646 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000000, 'time', 1.655979871749878) Last 5 digits 58151 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000000, 'time', 30.67442488670349) Last 5 digits 55897 OK heine:~/programs/gambiteer/gambit> gsi chud1.scm Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10, CPU time: 0.. Last 5 digits 26535. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100, CPU time: 0.. Last 5 digits 70679. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000, CPU time: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897. So it appears that for this algorithm applied to large integers, GMP's bignum routines are about 3-4 times as fast as Gambit's bignum routines. Not so bad. For smaller bignums, GMP has a bigger advantage. The C program gmp-chudnovsky.c includes certain optimizations to this basic algorithm: http://gmplib.org/pi-with-gmp.html ftp://ftp.gmplib.org/pub/misc/gmp-chudnovsky.c On my machine, compiled with gcc -O3 -march=native -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm the CPU times for 1,000,000 and 10,000,000 digits are 1.064 and 18.200 seconds, respectively. This is with a somewhat older machine model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz running Ubuntu 13.04 with heine:~/programs/gambiteer/gambit> gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.7.3-1ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) heine:~/programs/gambiteer/gambit> gsi -v v4.6.9 20130607151908 x86_64-unknown-linux-gnu "./configure '--enable-single-host' '--enable-multiple-versions' '--enable-shared'" and the Ubuntu-provided GMP 5.0.5. (I'm sure the GMP folks have a better way to build GMP on my machine than the "generic" 64-bit version provided by Ubuntu.) Brad

7 18

Efficient Compilation of Tail Calls and Continuations to JavaScript
by Marc Feeley 17 Sep '13

17 Sep '13

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

4 10

Gambit-C cross-platform framework
by Petersen, Chris 03 Aug '13

03 Aug '13

It may be of interest to some on the list that we have open-sourced (BSD licenced) our core Gambit-C based development framework for producing cross-platform applications on Android, iOS, OS X, Linux, Windows and OpenBSD. The GUI is OpenGL based with a widget system written in Scheme. The framework can also be used for cross-platform console/embedded applications. The source code, including examples, is here: https://github.com/part-cw/lambdanative A paper describing the framework and its use for various medical applications on smartphones and embedded devices will be presented at ICFP'13 in Boston in September. Chris

5 8

##thread-status proposal
by Mikael 01 Aug '13

01 Aug '13

(dump-threads) uses ##thread-continuation-capture to get the current continuation of a target thread. This presumes that the target thread has been started, if it has not ##thread-continuation-capture causes SIGSEGV. Checking for if it has been started requires access to thread object fields that are not exported currently, and thus to do this right now you need to make a hack consisting of copying out the thread structure's definition into your code and doing the check there - this is not version safe. I propose the introduction in Gambit of a procedure (##thread-status thread) => list ('created) = The thread has not yet been started list ('starting) = The thread has been started but execution has not yet begun list ('running) = The thread is running list ('ended result) = The thread terminated ordinarily, with the return value result list ('ended/exception exception) = The thread terminated with the exception exception as the definition is quite short and its presence enables the programmer to without hacks reliably dump threads, which is like a core thing for debug. Here follows a definition for inclusion into Gambit, based on an email Marc sent 2011-12-16, quoted below: (define (##thread-status thread #!optional capture-continuation-if-running?) (let loop () ; Make snapshot of thread state ; Quantum manipulation just to ensure get a consistent snapshot (define quantum-pre (thread-quantum (current-thread))) (thread-quantum-set! (current-thread) +inf.0) (let* ((end-condvar (macro-thread-end-condvar thread)) (exception? (macro-thread-exception? thread)) (result (macro-thread-result thread))) (thread-quantum-set! (current-thread) quantum-pre) ; Generate return value (cond ((not end-condvar) ;; Thread has terminated (if exception? ;; Thread has terminated with exception (list 'ended/exception result) ;; Thread has terminated with result (list 'ended result))) (exception? ;; Thread has never run and is not terminated (if (not result) ;; Thread is not yet started (list 'created) ;; Thread is started but has not yet run (list 'starting))) (else (if capture-continuation-if-running? (let ((continuation (with-exception-catcher (lambda (e) (loop)) (lambda () (capture-continuation-if-running? thread))))) (list 'running continuation) (list 'running)))))))) Use would look something like: > (define t (make-thread (lambda () (thread-sleep! 5)))) > (##thread-status t) (created) > (thread-start! t) > (##thread-status t) (running) > (thread-sleep! 5) > (##thread-status t) (ended #!void) With such a definition, a (dump-threads) could be defined as easy as: (define (dump-threads #!key threads thread-group thread #!rest display-continuation-backtrace-args) (map (lambda (thread) (let loop () (let ((status (##thread-status thread #t))) (if (eq? (car status) 'running) (list 'running (call-with-output-string '() (lambda (port) (apply display-continuation-backtrace `(,(cadr status) ; = continuation ,port .,display-continuation-backtrace-args))))) status)))) (or threads (thread-group->thread-list (or thread-group (thread-thread-group (or thread (current-thread)))))))) Please feel free to provide feedback. Brgds, Mikael 2011/12/16 Marc Feeley > > On 2011-12-15, at 6:22 PM, Mikael wrote: > > [..] > > Aha, that is good to be aware of - before running > ##thread-continuation-capture on a thread, how can i check it's started (as > to safeguard from this)? > > The attached code checks for all possible states of a thread. Please try > to dump the state of your threads with it to see if the segmentation fault > goes away. > > (##include "~~lib/_gambit#.scm") > > (define (dump-thread thread) > > (write thread) > > (let* ((end-condvar (macro-thread-end-condvar thread)) > (exception? (macro-thread-exception? thread)) > (result (macro-thread-result thread))) > (cond ((not end-condvar) > ;; thread has terminated > (if exception? > (begin > ;; thread has terminated with exception > (display " is terminated with exception:\n") > (display-exception result)) > (begin > ;; thread has terminated with result > (display " is terminated with result:\n") > (pretty-print result)))) > (exception? > ;; thread has never run and is not terminated > (if (not result) > (begin > ;; thread is not yet started > (display " is not yet started\n")) > (begin > ;; thread is started but has not yet run > (display " is started but has not yet run\n")))) > (else > ;; thread is started and has run > (let ((c (##thread-continuation-capture thread))) > (display " is running with continuation:\n") > (display-continuation-backtrace c))))) > > (newline)) > > (define t2 (make-thread (lambda () 222))) > (define t3 (make-thread (lambda () 333))) > (define t4 (make-thread (lambda () (/ 1 0)))) > (define t5 (make-thread (lambda () 555))) > > (thread-start! t3) > (thread-start! t4) > > (thread-sleep! 0.01) > > (dump-thread (current-thread)) > (dump-thread t2) > (dump-thread t3) > (dump-thread t4) > (thread-start! t5) > (dump-thread t5) > > ;; % gsi dump-thread.scm > ;; #<thread #1 primordial> is running with continuation: > ;; 0 dump-thread "dump-thread.scm"@32:21 > (##thread-continuation... > ;; 1 (interaction) "dump-thread.scm"@48:1 (dump-thread > (current-... > ;; 2 ##load > ;; 3 ##load > ;; 4 ##main > ;; > ;; #<thread #2> is not yet started > ;; > ;; #<thread #3> is terminated with result: > ;; 333 > ;; > ;; #<thread #4> is terminated with exception: > ;; Divide by zero > ;; (/ 1 0) > ;; > ;; #<thread #5> is started but has not yet run > >

2 3

eof-object port property, what do you think?
by Mikael 01 Aug '13

01 Aug '13

Hi, What would you say about introducing an eof-object property to the ports, that is #!eof by default? I suggested there be a way to wrap both IO error and EOF to custom IO primitive return values in January ( https://mercure.iro.umontreal.ca/pipermail/gambit-list/2013-January/006322.…) and Marc gave ports error handler thunks through the io-exception-handler slot, in the convo from 10 March ( https://mercure.iro.umontreal.ca/pipermail/gambit-list/2013-March/006486.ht…) to 4 April ( https://mercure.iro.umontreal.ca/pipermail/gambit-list/2013-April/006576.ht…) so that the user can wrap IO exception into a custom return value or other behavior. Now the ordinary EOF handling remains: in ~12 places over Gambit's sourcecode, there's an #!eof return value hardcoded. ~2 of these are in C, though channeled through Scheme code of course. Adding an eof-object should mean an addition of ~~6 lines of code to Gambit, and modification of ~~12 lines. The reason I propose the eof-object property is basically that, if it's set to #f, IO primitive results can be applied to boolean operators (or and if cond etc.) directly to get a differentiated behavior between success and failure, and this really supports code conciseness. I'm willing to implement this. Just wanted to ask if you have any thoughts/comments on it? ( For context, in the longer run, with the IO system, I find * finding a way to increase single-byte/char read/write:s from the present 350KB/sec to something much higher, and * a way to implement application-level ports (SSL/GZIP/etc.) really relevant developments, and those are also the only ones I have on my mind. Zooming out further, the reason I care about this is because it's struck me that Gambit's IO system needs to be the facility used for pretty much any IO or IO stream operations; any approaches with the user implementing an own streams, 'io primitives' or similar facility will end up severely limited in comparison with channeling the same functionality through Gambit's IO system, so therefore the clean solution is to make Gambit's IO system support these things well too. Jeff Read who implemented GamSock appears to have had a related take on it, when he proposed in https://mercure.iro.umontreal.ca/pipermail/gambit-list/2012-October/006138.… that with "`##open-predefined' I will look into the possibility of creating an "upper layer" for Gamsock that uses port I/O". ) Best regards, Mikael

2 2

compiling libgambit.a for android
by tcl super dude 31 Jul '13

31 Jul '13

I added a small bash script on github https://github.com/dmalves/compile-gambit-for-android to help on the compilation of gambit for android. Using gambit 4.7.0 there are no errors, and it does compile to x86, arm and mips, creating a directory for each of the architectures. I tested using the emulator and it worked for all architectures. I loved alvatar's scheme sphere project on github. Maybe I could help a little, coz I am (when time is on my side) developing an app using gambit on android. Anyway, I'll be making that script better, it is a mess now. Maybe it should have some command line arguments to tell what version to compile, what optimizations to use or maybe download gambit source if not available in current directory.

3 8

Line numbers in custom reader
by Hendrik Boom 31 Jul '13

31 Jul '13

So I'm writing a custom parser so that I can read in code written in another language and translate it into Gambit (of course, not to textual S-expression, but consing together a data structure to feed to the Gambit interpreter or compiler). How to I attach line numbers to the consed code so that the interpreter will be able to write line numbers from the original source code in error messages? -- hendrik

3 5

A proxy server log collector written in Gambit-C Scheme
by Paul Wolneykien 31 Jul '13

31 Jul '13

Hi, I've just put on the GitHub a small proxy server log collector written in Gambit-C: https://github.com/wolneykien/squidmill It uses some shared libraries also written in Gambit-C. One of them is the sqlite3 interface originally published on the Dumping Grounds. The other two are the general UNIX signal and domain socket libraries. Thought these might be interesting/useful for the readers of this mailing list. The code is released under GNU GPL v3+. Paul.

2 1

my nick name
by tcl super dude 31 Jul '13

31 Jul '13

is it possible to change my nick name on the mail list? Gmail tells me it changes, but I still see the same nick.

2 1

Gambit in the browser
by Marc Feeley 31 Jul '13

31 Jul '13

I have been experimenting with the emscripten C to JavaScript compiler. I have used it to compile the Gambit interpreter into JavaScript. This allows the Gambit interpreter to run in the browser! Just direct your browser to http://feeley.github.io/gambit-in-the-browser Be patient... it can take 30 seconds to a minute to load the page (there's about 11 MB of JavaScript code). Use a fast JIT based browser if possible (Firefox or Chrome have been tested). Marc

5 7