January 2015 - Gambit-list - mailman.iro.umontreal.ca

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

08 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

object->u8vector as tree shaker?
by Bradley Lucier 29 Mar '15

29 Mar '15

Marc: It's not quite clear to me what object->u8vector does with procedures. I was thinking that if it pulled in all the functions not in system libraries, then it could be used as a tree-shaker. This is only a vague thought, but I find its interesting. Brad

3 6

New builtins in upcoming gcc 5.0.0 that may speed up bignum arithmetic
by Bradley Lucier 23 Feb '15

23 Feb '15

I just noticed this in https://gcc.gnu.org/gcc-5/changes.html # A new set of built-in functions for arithmetics with overflow checking has been added: |__builtin_add_overflow|, |__builtin_sub_overflow| and |__builtin_mul_overflow| and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, |+|, |-| or |*| is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return |false|, otherwise |true|. The type of the integer variable that will hold the result can be different from the types of the first two arguments. The following snippet demonstrates how this can be used in computing the size for the |calloc| function: void * calloc (size_t x, size_t y) { size_t sz; if (__builtin_mul_overflow (x, y, &sz)) return NULL; void *ret = malloc (sz); if (ret) memset (res, 0, sz); return ret; } On e.g. i?86 or x86-64 the above will result in a |mul| instruction followed by a jump on overflow. Maybe we can exploit this to improve the speed of bignum arithmetic. Brad

2 2

Using the JavaScript back-end
by Blake McBride 03 Feb '15

03 Feb '15

Dear Mark, Thanks for your pointers regarding scheme back-ends for JavaScript. I starting using Gambit but ran into a few problems as follows: 1. The -target compiler option is undocumented. I think Gambit is more capabilities than the public is aware of - i.e. JavaScript back-end. 2. When I compile anything into JS and run it in node I get: pc = pc(); ^ TypeError: undefined is not a function If I change the definition of gambit_trampoline to: function gambit_trampoline(pc) { while (pc !== false && pc !== undefined) { pc = pc(); } } it fixes the problem. 3. I'd like to print results to the console so I can see what is going on. I'd prefer to use (print) or (display) but I can't get (console.log) to work either. I even tried: (define (console.log x) ;; Note: the parameter x will be in variable Gambit_r1 (##inline-host-code "console.log(Gambit_r1);\n") #f) but that didn't work either. I checked, console.log seems to be a JS standard. Perhaps your compiler can convert print and display to console.log. How can I display something? Thanks. Blake McBride

4 8

Question for os_tty.c:1063 to solve closed-TTY input Gambit zombie+CPU hogging bug
by Mikael 25 Jan '15

25 Jan '15

Dear Marc, I've tracked down a TTY IO bug here, https://github.com/feeley/gambit/issues/100 . On os_tty.c:1062 which is "if ((n = read (d->fd, buf, len)) < 0)", the < should be changed to <= because a 0 return value *always* means EOF in the sense that the TTY has been closed, see issue for more info. Then, os_tty.c:1063 needs to be updated from: "return err_code_from_errno ();" to something like "return n == 0 ? ___FIX([EOF-ERROR-VALUE]) : err_code_from_errno ();". The purpose of ___FIX([EOF-ERROR-VALUE]) is to signal to the underlying logic, which is the Gambit C VTBL IO abstraction, that the TTY is closed so that the REPL's input will be #!eof and Gambit supposedly will shut down, instead of repeating the read() infinitely, as is the case now. You know best which value is suitable in the place of [EOF-ERROR-VALUE] here - can you please suggest so a patch can be produced? Thanks, Mikael

1 1

[2nd CfP] European Lisp Symposium 2015, April 20-21, London
by Didier Verna 24 Jan '15

24 Jan '15

ELS'15 - 8th European Lisp Symposium Goldsmiths College, London, UK April 20-21, 2015 http://www.european-lisp-symposium.org/ Sponsored by EPITA, Franz Inc. and Lispworks Ltd. Recent news: - Submission deadline in less than a month now! - Programme committee has been announced (see below) - Venue information now available on the web site The purpose of the European Lisp Symposium is to provide a forum for the discussion and dissemination of all aspects of design, implementation and application of any of the Lisp and Lisp-inspired dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, Hop and so on. We encourage everyone interested in Lisp to participate. The 8th European Lisp Symposium invites high quality papers about novel research results, insights and lessons learned from practical applications and educational perspectives. We also encourage submissions about known ideas as long as they are presented in a new setting and/or in a highly elegant way. Topics include but are not limited to: - Context-, aspect-, domain-oriented and generative programming - Macro-, reflective-, meta- and/or rule-based development approaches - Language design and implementation - Language integration, inter-operation and deployment - Development methodologies, support and environments - Educational approaches and perspectives - Experience reports and case studies We invite submissions in the following forms: Papers: Technical papers of up to 8 pages that describe original results or explain known ideas in new and elegant ways. Demonstrations: Abstracts of up to 2 pages for demonstrations of tools, libraries, and applications. Tutorials: Abstracts of up to 4 pages for in-depth presentations about topics of special interest for at least 90 minutes and up to 180 minutes. The symposium will also provide slots for lightning talks, to be registered on-site every day. All submissions should be formatted following the ACM SIGS guidelines and include ACM classification categories and terms. For more information on the submission guidelines and the ACM keywords, see: http://www.acm.org/sigs/publications/proceedings-templates and http://www.acm.org/about/class/1998. Important dates: - 22 Feb 2015: Submission deadline - 15 Mar 2015: Notification of acceptance - 29 Mar 2015: Early registration deadline - 05 Apr 2015: Final papers - 20-21 Apr 2015: Symposium Programme chair: Julian Padget, University of Bath, UK Local chair: Christophe Rhodes, Goldsmiths, University of London, UK Programme committee: Sacha Chua — Toronto, Canada Edmund Weitz — University of Applied Scicences, Hamburg, Germany Rainer Joswig — Hamburg, Germany Henry Lieberman — MIT, USA Matthew Flatt — University of Utah, USA Christian Queinnec — University Pierre et Marie Curie, Paris 6, France Giuseppe Attardi — University of Pisa, Italy Marc Feeley — University of Montreal, Canada Stephen Eglen — University of Cambridge, UK Robert Strandh — University of Bordeaux, France Nick Levine — RavenPack, Spain Search Keywords: #els2015, ELS 2015, ELS '15, European Lisp Symposium 2015, European Lisp Symposium '15, 8th ELS, 8th European Lisp Symposium, European Lisp Conference 2015, European Lisp Conference '15 -- My new Jazz CD entitled "Roots and Leaves" is out! Check it out: http://didierverna.com/records/roots-and-leaves.php Didier Verna <didier(a)elsaa.org> ELSAA, President

1 0

How to define "set-macro-character" like in Gambit.
by Ryuho Yokoyama 23 Jan '15

23 Jan '15

Hello, For example, in Common Lisp --- (defvar *Data* '((aa 11) (bb 22) (cc 33))) (set-macro-character #\^ #'(lambda (stream char) `(cadr (assoc ',(read stream t nil t) *Data*)))) (print ^bb) ; => 22 --- in Gambit I tried like --- (define *Data* '((aa 11) (bb 22) (cc 33))) (##readtable-char-handler-set! (##current-readtable) #\^ (lambda (stm ch) `(cadr (assoc ',(##read stm) *Data*)) ; ^^^^^^^^^^^^ ?? )) (pp ^bb) ; => #!unbound --- and I faild. Could you please teach me how to define "set-macro-character" like in Gambit. Thanks in advance.

2 3

Want to contribute
by HARSHIL GOEL 23 Jan '15

23 Jan '15

Hi my name is harshil goel and i was looking forward to contribute to your open source through your Organisation. Can anyone help me in getting started?

1 0

How can built a small as 5 Kbytes "Hello World" program ?
by Ryuho Yokoyama 20 Jan '15

20 Jan '15

I built a "Hello World" program as follows, >type h.scm (display "Hello ") >type w.scm (display "World") >gsc -link h w >gsc -obj h.c w.c w_.c >gcc -o w.exe h.o w.o w_.o C:/Gambit-C_64bit/v4.7.3/lib/libgambc.a -lws2_32 >w.exe Hello World > This way, the size of the "w.exe" is 4.61MB. In Gambit-C manual documents 3. The Gambit Scheme compiler 3.4 Link files ... A "Hello World" program built this way can be as small as 5 Kbytes. ... Could you please teach me how to built program as small as 5 Kbytes one. Thanks in advance.

4 7

Building Gambit on OS X
by Marc Feeley 16 Jan '15

16 Jan '15

Xcode 6.1.1 was released a little over a month ago, so I decided to do some benchmarking to see how well its C compilers (Apple clang 6.0 and Apple gcc 6.0) compare against GNU gcc 4.9.2 when compiling Gambit. I configured and built Gambit with ./configure --enable-single-host CC="<C_COMPILER>" make -j8 I report the build time for each compiler and the execution time of test 4 (which measures the speed of the interpreter, which is indicative of the relative speed of the code generated by Gambit). Here are the numbers: Build test4 C compiler (secs) (secs) 60.31 1.30 GNU gcc 4.9.2 2042.98 (34x) 3.05 (2.3x) Apple clang 6.0 1875.56 (31x) 3.08 (2.4x) Apple gcc 6.0 As can be seen, the Apple C compilers build Gambit in roughly 30 minutes, which is about 30x slower than when using GNU gcc 4.9.2 . The execution time is also better for GNU gcc, about 2.3x faster. So on OS X it is clearly advantageous to install GNU gcc when using Gambit. This can easily be achieved with the homebrew system with the command brew install gcc49 Marc P.S. here is the version information of the compilers: ============================================================================== GNU gcc 4.9.2: % /usr/local/Cellar/gcc49/4.9.2/bin/gcc-4.9 -v Using built-in specs. COLLECT_GCC=/usr/local/Cellar/gcc49/4.9.2/bin/gcc-4.9 COLLECT_LTO_WRAPPER=/usr/local/Cellar/gcc49/4.9.2/libexec/gcc/x86_64-apple-darwin14.0.0/4.9.2/lto-wrapper Target: x86_64-apple-darwin14.0.0 Configured with: ../configure --build=x86_64-apple-darwin14.0.0 --prefix=/usr/local/Cellar/gcc49/4.9.2 --enable-languages=c,c++,objc,obj-c++ --program-suffix=-4.9 --with-gmp=/usr/local/opt/gmp4 --with-mpfr=/usr/local/opt/mpfr2 --with-mpc=/usr/local/opt/libmpc08 --with-cloog=/usr/local/opt/cloog018 --with-isl=/usr/local/opt/isl011 --with-system-zlib --enable-version-specific-runtime-libs --enable-libstdcxx-time=yes --enable-stage1-checking --enable-checking=release --enable-lto --disable-werror --with-pkgversion='Homebrew gcc49 4.9.2' --with-bugurl=https://github.com/Homebrew/homebrew-versions/issues --enable-plugin --disable-nls --enable-multilib Thread model: posix gcc version 4.9.2 (Homebrew gcc49 4.9.2) ============================================================================== Apple clang 6.0: % /usr/bin/clang -v Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn) Target: x86_64-apple-darwin14.0.0 Thread model: posix ============================================================================== Apple gcc 6.0: % /usr/bin/gcc -v Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn) Target: x86_64-apple-darwin14.0.0 Thread model: posix ==============================================================================

2 2