Gambit-list Septembre 2017

gambit-list@iro.umontreal.ca

11 participants
11 discussions

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

07 Avr '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

on macos: clang over gcc
by Ben 06 Oct '17

06 Oct '17

hi On macos sierra running the ./configure script gives me the following message: *** The clang compiler is being used. Please be aware that the build *** *** may take a very long time (over 30 minutes on a fairly fast *** *** machine with clang 3.0). Configuring with GNU GCC will give a *** *** faster build (1 min on the same machine with GNU GCC 4.2.1) and *** *** the executable will be faster. What can I do to enforce GCC? I cannot see any specific configure --options Attached you'll find the entire configure log. Thanks, Ben

3 6

More precise versioning of Gambit?
by Faré 25 Sep '17

25 Sep '17

Right now when I run gsi, it tells me I'm using gambit 4.8.8. But that's not quite right. If I use git describe --tags to ask git what I'm using it tells me v4.8.8-402-g300db59e, so some well-identified commit with 402 patchs on top of Gambit 4.8.8. I recently modified Gerbil to it remembers the exact version as identified by git describe --tags in its binaries. Basically, a file is generated during the build if git is available; when preparing a tarball for use without git, the file must be present. For release purposes, and so as to reuse github's builtin tarball capabilities, a release script creates and commits the magic version file before to tag the commit with the release version. Then to go back into development mode, the same script can "unrelease" the code and re-delete the file, adding it back to .gitignore, after the release was made. Are you interested in my porting the same mechanism to Gambit? —♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org A woman is not property, and husbands who think otherwise are living in a dreamworld. — Robert Heinlein, "Time Enough For Love"

3 4

Call for Participation: SLE 2017 (10th ACM SIGPLAN International Conference on Software Language Engineering)
by Andrei Chis 22 Sep '17

22 Sep '17

======================================================================== ** Call for Participation ** 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017) 23-24 October 2017, Vancouver, Canada (Collocated with SPLASH 2017) http://conf.researchr.org/track/sle-2017/sle-2017-papers http://www.sleconf.org/2017 Follow us on twitter: https://twitter.com/sleconf ======================================================================== Software Language Engineering (SLE) is the application of systematic, disciplined, and measurable approaches to the development, use, deployment, and maintenance of software languages. The term "software language" is used broadly, and includes: general-purpose programming languages; domain-specific languages (e.g. BPMN, Simulink, Modelica); modeling and metamodeling languages (e.g. SysML and UML); data models and ontologies (e.g. XML-based and OWL-based languages and vocabularies). ** REGISTRATION ** Friday, 22 September 2017 (Early Registration Deadline) Contact: info(a)splashcon.org http://2017.splashcon.org/attending/registration ** VENUE ** Hyatt Regency Vancouver Hotel reservations: https://2017.splashcon.org/venue/hyattregency ## Program Highlights ### Keynote - Peter D. Mosses Engineering meta-languages for specifying software languages https://conf.researchr.org/track/sle-2017/sle-2017-papers#Keynote-Peter-D-M… ### Awards During the conference, we will announce the following awards: - Distinguished paper. Award for most notable paper, as determined by the PC chairs based on the recommendations of the program committee. - Distinguished reviewer. Award for distinguished reviewer, as determined by the PC chairs using feedback from the authors. - Distinguished artefact. Award for the artifact most significantly exceeding expectations, as determined by the AEC chairs based on the recommendations of the artifact evaluation committee. Sponsored by Raincode. ### Accepted Papers - Metacasanova: an optimized meta-compiler for Domain-Specific Languages, Francesco Di Giacomo, Mohamed Abbadi, Agostino Cortesi, Pieter Spronck, Giuseppe Maggiore - Safe Modular Parsing, Haoyuan Zhang, Huang Li, Bruno C. d. S. Oliveira - Concrete Syntax: A Multi-Paradigm Approach, Yentl Van Tendeloo, Simon Van Mierlo, Bart Meyers, Hans Vangheluwe - A Domain-Specific Controlled English Language for Automated Regulatory Compliance, Suman Roychoudhury, Sagar Sunkle, Deepali Kholkar, Vinay Kulkarni - Debugging with Domain-Specific Events, Xiangqi Li, Matthew Flatt - Deep Priority Conflicts in the Wild - A Pilot Study, Luís Eduardo de Souza Amorim, Michael J. Steindorfer, Eelco Visser - Comparison of the Expressiveness and Performance of Template-based Code Generation Tools, Lechanceux Luhunu, Eugene Syriani - Incremental Packrat Parsing, Patrick Dubroy, Alessandro Warth - Ensuring Non-interference of Composable Language Extensions, Ted Kaminski, Eric Van Wyk - A Formalisation of Parameterised Reference Attribute Grammars, Scott Buckley, Anthony Sloane - A Symbol-based Extension of Parsing Expression Grammars and Context-Sensitive Packrat Parsing, Kimio Kuramitsu - Structural Model Subtyping with OCL Constraints, Artur Boronat - A Requirements Engineering Approach for Usability-Driven DSL Development, Ankica Barisic, Dominique Blouin, Vasco Amaral, Miguel Goulao - Tool Demonstration: A development environment for the Alf language within the MagicDraw UML tool, Ed Seidewitz - FlowSpec: Declarative Dataflow Analysis Specification, Jeff Smits, Eelco Visser - Robust Programs with Filtered Iterators, Jiasi Shen, Martin Rinard - Energy Efficiency across Programming Languages: How does energy, time, and memory relate?, Rui Pereira, Marco Couto, Francisco Ribeiro, Rui Rua, Jácome Cunha, João Paulo Fernandes, João Saraiva - Concurrent Circular Reference Attribute Grammars, Jesper Öqvist, Görel Hedin - Better Call the Crowd. Using Crowdsourcing to Shape your Domain-Specific Languages, Marco Brambilla, Jordi Cabot, Javier Luis Canovas Izquierdo, Andrea Mauri - Robust Projectional Editing, Friedrich Steimann, Marcus Frenkel, Markus Voelter - Towards a Taxonomy of Grammar Smells, Mats Stijlaart, Vadim Zaytsev - Red Shift: Procedural Shift-Reduce Parsing, Nicolas Laurent - Virtual Textual Model Composition for Supporting Maintenance and Aspect-Orientation, Robert Bill, Patrick Neubauer, Manuel Wimmer - A Chrestomathy of DSL implementations, Simon Schauss, Ralf Lämmel, Johannes Härtel, Marcel Heinz, Kevin Klein, Lukas Härtel, Thorsten Berger

1 0

Re --enable-auto-forcing: Scope, how/where implemented, how build (with) it properly?
by Adam 18 Sep '17

18 Sep '17

Hi Marc! Three questions regarding promise auto-forcing: 1) Scope If build correctly (e.g. per the instructions below), every single Scheme-world evaluation in the whole GVM will be included in the auto forcing scheme, right? E.g. (begin (declare (not safe)) (print (##string-append (delay "Hello world")) "\n")) and any other quirky Scheme code cases are also included. Do any declares affect auto-forcing behavior? 2) How/where is it implemented? I'm trying to follow the code path of the "--enable-auto-forcing" ./configure argument, but I cannot figure out how it is propagated as to affect anything in include/ , gsc/ , lib/ , anywhere. Also I can't find any logics in gsc/ , lib/ or include/ (that's where they should be I supposed) that pertain to automatic forcing of promises. Possibly the "macro-force-vars", which is used all over the runtime and compiler, would have something to do with this, but I don't find its definition anywhere. What am I missing, would you like to take a minute to describe where and how the auto-forcing logics are implemented? 3) How build Gambit with it enabled properly? Also, enabling auto-force requires a full recompile of Gambit's own sources (for *all* C files involved to be recompiled, including the runtime, e.g. including the repl, will auto-force, and not just user code and hence just a tiny part of the logics, which would lead to a totally uneven application of auto-forcing), right, so the following is how to properly switch it on right?: git clone https://github.com/gambit/gambit.git cd gambit ./configure --enable-auto-force make -j4 mv gsc/gsc gsc-boot make bootclean make -j4 sudo make install Or do you suggest any other sequence or way? Should I use "from-scratch" instead of "make bootclean" + "make"? Thanks!

3 15

--enable-single-host is sufficient for general use
by Bradley Lucier 18 Sep '17

18 Sep '17

There is a table at http://www.math.purdue.edu/~lucier/gambit-optimization-comparison.html benchmarking Gambit with various levels of optimization. I would conclude that for general purposes, one doesn't need --enable-c-opt or --enable-gcc-opts when configuring. Brad

7 14

Primitives & practices for paralellism such as work stealing, in SMP Gambit?
by Adam 18 Sep '17

18 Sep '17

Hi Marc, This is a general question on how to use SMP (and single-processor) Gambit: If you're running some algorithm or other code that requires fine-granularity work stealing or otherwise parallel execution and/or data structure access, how are you supposed to implement that, in a way that should have good performance and be effective? - Are mutex lock/unlock operations with zero-timeouts, and/or the use of condition variables, and/or the use of thread message passing with zero timeout, intended to satisfy these use cases, or do you propose other primitives or methods? Also, do you plan to implement any additional parallelism primitives now with SMP Gambit? Thanks!

2 3

Re: [gambit-list] Implementation of equal? for recursive structures
by Dimitris Vyzovitis 14 Sep '17

14 Sep '17

Thanks, that explains a lot! I think it makes sense to port the Chez version, i'll prepare a patch. -- vyzo On Thu, Sep 14, 2017 at 4:30 PM, Matthew Flatt <mflatt(a)cs.utah.edu> wrote: > At Thu, 14 Sep 2017 16:21:29 +0300, Dimitris Vyzovitis wrote: > > > Have you looked at how other implementations of Scheme do this? > > > > I looked at chibi which has a native C impl, and racket which is insanely > > complex. > > No definitive answer yet on how to resolve the edge case properly. > > Here's a paper about Chez Scheme's implementation: > > Efficient nondestructive equality checking for trees and graphs. > Adams & Dybvig, ICFP'08 > http://www.cs.indiana.edu/~dyb/pubs/equal.pdf > > I think the union-find aspect is probably what you're looking for. > > Here's the current implementation: > > https://github.com/cisco/ChezScheme/blob/master/s/5_1.ss#L31 > > Probably less interesting/useful, but Racket-on-Chez currently has its > own `equal?` to support chaperones and impersonators, and it has the > same union-find part: > > https://github.com/racket/racket7/blob/master/racket/ > src/cs/core/equal.ss > >

1 1

Implementation of equal? for recursive structures
by Dimitris Vyzovitis 14 Sep '17

14 Sep '17

Marc, Can we get an implementation of equal? that works for recursive structures per r7rs? It doesn't need to be called equal?, it can be called equal-shared? for instance. I have an initial implementation that works with shared structures, but there is an edge case: If there is a shared object in the structure (without recursion) it needs to be eq? to its counterpart. (def (r7rs-equal? obj1 obj2) (def ht (make-hash-table-eq)) (def (equal obj1 obj2) (cond ((##eq? obj1 obj2)) ((immediate? obj1) #f) ; should be eq? ((number? obj1) (##eqv? obj1 obj2)) ((##table-ref ht obj1 #f) => (cut ##eq? <> obj2)) ; edge case mentioned above ((##pair? obj1) (and (##pair? obj2) (begin (##table-set! ht obj1 obj2) (and (equal (##car obj1) (##car obj2)) (equal (##cdr obj1) (##cdr obj2)))))) ((##vector? obj1) (and (##vector? obj2) (let (len (##vector-length obj1)) (and (##fx= len (##vector-length obj2)) (begin (##table-set! ht obj1 obj2) (vector-equal obj1 obj2 0 len)))))) ((##string? obj2) (and (##string? obj2) (##string-equal? obj1 obj2))) ((##u8vector? obj1) (and (##u8vector? obj2) (##u8vector-equal? obj1 obj2))) ((##s8vector? obj1) (and (##s8vector? obj2) (##s8vector-equal? obj1 obj2))) ((##u16vector? obj1) (and (##u16vector? obj2) (##u16vector-equal? obj1 obj2))) ((##s16vector? obj1) (and (##s16vector? obj2) (##s16vector-equal? obj1 obj2))) ((##u32vector? obj1) (and (##u32vector? obj2) (##u32vector-equal? obj1 obj2))) ((##s32vector? obj1) (and (##s32vector? obj2) (##s32vector-equal? obj1 obj2))) ((##u64vector? obj1) (and (##u64vector? obj2) (##u64vector-equal? obj1 obj2))) ((##s64vector? obj1) (and (##s64vector? obj2) (##s64vector-equal? obj1 obj2))) ((##f32vector? obj1) (and (##f32vector? obj2) (##f32vector-equal? obj1 obj2))) ((##f64vector? obj1) (and (##f64vector? obj2) (##f64vector-equal? obj1 obj2))) ((table? obj1) (and (table? obj2) (begin (##table-set! ht obj1 obj2) (table-equal obj1 obj2)))) ((##structure? obj1) (and (##structure? obj2) (let* ((t1 (##structure-type obj1)) (t2 (##structure-type obj2)) (tid1 (##type-id t1)) (tid2 (##type-id t2))) (and (##eq? tid1 tid2) (let (len (##vector-length obj1)) (and (##fx= len (##vector-length obj2)) (##fx= (##fxand (##type-flags t1) 1) 0) ; not opaque (begin (##table-set! ht obj1 obj2) (vector-equal obj1 obj2 1 len)))))))) ((##box? obj1) (and (##box? obj2) (begin (##table-set! ht obj1 obj2) (equal (##unbox obj1) (##unbox obj2))))) (else #f))) (def (vector-equal obj1 obj2 i len) (let lp ((i i)) (if (##fx< i len) (and (equal (##vector-ref obj1 i) (##vector-ref obj2 i)) (lp (##fx+ i 1))) #t))) (def (table-equal obj1 obj2) (and (##fx= (##vector-ref obj1 1) ; flags (##vector-ref obj2 1)) (##eq? (##vector-ref obj1 2) ; test (##vector-ref obj2 2)) (##eq? (##vector-ref obj1 3) ; hash (##vector-ref obj2 3)) (##fx= (##table-length obj1) (##table-length obj2)) (not (##table-search (lambda (k1 v1) (let (v2 (##table-ref obj2 k1 nil)) (not (equal v1 v2)))) obj1)))) (equal obj1 obj2)) -- vyzo

4 4

Future of Scheme
by Bradley Lucier 07 Sep '17

07 Sep '17

Marc: You're listed a participant in a panel discussion of the "Future of Scheme" at the Scheme 2017 workshop at ICFP 2017. Did you make it? Any comments on the "Future of Scheme"? (Or from anyone else who'd like to comment.) Brad

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Gambit-list Septembre 2017