Gambit-list Janvier 2017

gambit-list@iro.umontreal.ca

10 participants
20 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

Re: [gambit-list] JavaScript backend
by Marc Feeley 13 Fév '17

13 Fév '17

First of all, this change is for the universal backend. It is more of a temporary kludge to experiment with dynamically loading files generated by the universal backend. Here’s how it works… At the end of the link file, the Gambit linker generates a table of the Scheme modules required by the program. The table is passed as a parameter to the g_module_registry_init function of the Gambit runtime system. For example, the link command: gsc -link -l lib/_gambit.js a.js b.js will generate at the end of the link file “b_.js”: g_module_registry_init([new G_ModLinkInfo("_gambit",0), new G_ModLinkInfo("a",1), new G_ModLinkInfo("b",2)]); At then end of a file generated for the compilation of a module there is a call to a runtime system function that registers the module in the module registry. For example, when “a.scm” is compiled with the command “gsc -target js -c a.scm”, the file “a.js” generated ends with: g_module_register([g_make_interned_symbol("a"),g_bb1__20_a,1,null,false]); The parameter of g_module_register is a “module descriptor” giving information on the module: name, main function (g_bb1__20_a), preload flag (1), module meta information (null), and a dummy field (false) that is only interesting for the C backend. So when the files of generated code are loaded (incrementally) by the JS VM, g_module_register accumulates the modules in a table. When all the modules required by the program have beed loaded (in the example, _gambit, a and b) the function g_module_register will call the main function of the first module. This will run the Scheme code at the toplevel of the first module. The first module contains a loop, in Scheme, that iterates over the module registry and calls the main function of each of the remaining modules in the registry (this information is available in Scheme in the global variable ##program-descr). Specifically, the first module is the Gambit universal library (lib/_univlib.scm), which ends with a call to ##load-vm (a procedure defined in lib/_kernel.scm that runs each module other than the first). What my most recent change does is extend g_module_register so that any subsequent module that is loaded by the JS VM causes its immediate execution by calling the module's main function. In the C backend the mechanism is slightly different (and more flexible): the ##load-object-file procedure of the Gambit runtime library constructs a vector of module descriptors and this vector is passed to ##register-module-descrs-and-load! (defined in lib/_kernel.scm) which then runs the modules. It is more flexible because the loaded object file can contain more than one module, and also control goes through Scheme before the module is executed. Marc > On Jan 3, 2016, at 2:54 AM, Adam <adam.mlmb(a)gmail.com> wrote: > > Marc, > > Wait, what's the point? > > That is effectively C modules' default behavior isn't it? (even if it's the runtime or linker-generated code that actually does the actual run command.) > > So this way you create symmetrical behavior but the actual run command is in the module file itself rather than in runtime/linker - > > Is there any disadvantage.. could be, no, like, I need more modules loaded at the same time and with this model you introduced now, the global namespace in JS files is evaluated at load time so could cause a problem? > > > 2016-01-03 14:10 GMT+08:00 Marc Feeley <feeley(a)iro.umontreal.ca>: > I’ve just pushed a small change to the module registration method. Now, loading the generated .js file will run that file. > > Marc > > > On Jan 2, 2016, at 11:39 PM, Blake McBride <blake(a)mcbride.name> wrote: > > > > Yes, and I use jQuery get and html methods to load the html part. > > > > > > On Sat, Jan 2, 2016 at 8:43 PM, Marc Feeley <feeley(a)iro.umontreal.ca> wrote: > > That’s an interesting app! > > > > As I said, it shouldn’t be hard to do. In your app, how do you load new JS code? Are you using jQuery and the getScript method? > > > > Marc > > > > > On Jan 2, 2016, at 8:42 PM, Blake McBride <blake(a)mcbride.name> wrote: > > > > > > Hi Marc, > > > > > > Thanks for the reply. > > > > > > I started development of a Web based business application in 2006. The app is in production use. The front-end is about 450 screens written in Flash. The back-end is written in Java (over 9,000 classes) on top of an SQL database with 250 tables accessed through Hibernate. The front-end and back-end communicate through SOAP web services. > > > > > > Since Flash is now dead, I need to re-write at least parts of the front-end in JS to support tablets and phones at least. I have front-end JS code that communicates with the back-end SOAP Web services so I theoretically wouldn't need to touch the back-end. > > > > > > I have a preference to utilize scheme if I can, but the back-end is already written and works. It doesn't make sense to mess with it given the investment. > > > > > > The problems I had with Gambit (as well as many other systems) is as follows: > > > > > > Once a user logs in, my app has a consistent visual / UI framework. Beyond this framework, there are 450 different screens that appear within the framework (like in one of the div's). > > > > > > A. I cannot load all 450 screen at system startup. I must lazy load them as they are called up. > > > > > > B. The initial UI framework code should contain all of the Gambit machinery and libraries so that each of the 450 screens can be small, light-weight, compiled separately yet have full access to the entire Gambit facility. > > > > > > With respect, my investigation into Gambit as a possible solution in the past led me to the conclusions at that time it was not possible to produce separately compiled modules that leveraged off of a single main module for the Gambit machinery and libraries. > > > > > > I suppose some time has passed and I wanted to see if the situation has changed. I can only use Gambit if: > > > > > > 1. I can compile and load each screen separately > > > > > > 2. I only have to have one copy of the Gambit machinery and library so that the separate screens are small. > > > > > > Thank you. > > > > > > Blake > > > > > > > > > On Sat, Jan 2, 2016 at 7:06 PM, Marc Feeley <feeley(a)iro.umontreal.ca> wrote: > > > asmjs is cool and Gambit has already been compiled to it thanks to emscripten (see “Gambit in the browser”: http://feeley.github.io/gambit-in-the-browser/). The performance is not bad, perhaps 10x to 20x slower than when Gambit is compiled by gcc to native code. The main problem is the size of the JS that is generated when compiling Gambit-C with emscripten to JS. The gsi interpreter yields roughly 10 MB of asmjs code. > > > > > > As far as code size is concerned, a better solution is to use Gambit's JS backend with the Gambit library. The code generated is roughly half the size when minimized (and it could be even less if some thought went into how identifiers are encoded). > > > > > > Even more savings can be had by doing away with the default Gambit library and writing a custom library specialized for the application. Gambit’s library has lots of functionality that is not normally needed by typical applications. For example, the predefined map procedure can handle an arbitrary number of list parameters. If the application only uses the single list version, then this definition would be sufficient: > > > > > > (define (map f lst) > > > (if (pair? lst) > > > (cons (f (car lst)) (map f (cdr lst))) > > > ‘())) > > > > > > That 4 line version is 1/20th the size of the map defined in the Gambit library (which handles multiple lists, has type checking, precise error messages, same list length checking and is safe for multithreading). > > > > > > So perhaps what’s needed for Gambit to be more successful for web dev is the creation of such a “slim” library for Gambit to replace the default feature-full library. Gambit’s “tree shaker” would also help to eliminate the unused procedures of the slim library (unfortunately this only works for “whole program” compilation, so separate compilation would only be used for the development phase). > > > > > > Anyway, if this interests you please let me know. > > > > > > Marc > > > > > > > On Jan 1, 2016, at 11:44 AM, Blake McBride <blake(a)mcbride.name> wrote: > > > > > > > > Just some opinions. > > > > > > > > asmjs.org defines a portable subset that allows JS platforms to compile into very fast code. Targeting that subset, and within their spec, is probably a good idea. > > > > > > > > JS has, and is becoming increasingly, a very, very important platform. With ajax and rest services, code increasingly independent from the back-end is being developed. So, in a very important sense, JS has become its own platform, just like X86, and X86_64, along with Linux, Windows, Mac, etc. > > > > > > > > Many apps consist of two major parts: the back-end processing, and the front-end human interface. While one can write the back-end processing in any of dozens of languages targeting X86 or a VM, and the OS, there is really only one target for the other half - the human interface - and that is JS. > > > > > > > > While many languages are now targeting the JS platform (I am using the word "platform" to mean X86, X86_64, either, plus the OS) including, believe it or not, Smalltalk, there are few that can, IMO, be used in a real world application for several reasons. But, these issues will likely be resolved soon. > > > > > > > > With respect, Gambit, at least in the past, was in many ways another toy solution - one with a functioning "Hello world" application but missing important features that make it usable in a real-world situation. I would love to be a part of that solution, but alas, life doesn't offer me that level of freedom. I am only capable of using a system that is reportedly working, reporting bugs, making small adjustments, and providing feedback. Regardless of my attitude, preferences, and intentions, I cannot provide more. > > > > > > > > Look at node (JS for the back-end) and its vastly increasing popularity. Since developers are being forced to use JS on the front-end, it's bleeding over to the back-end. I think solutions that take JS seriously at this stage will prosper greatly. > > > > > > > > Now, having said all that, I would love to see Gambit target JS as a high-priority, first-class target. If that were the case, I would be happy to contribute what I stated above. > > > > > > > > Thanks! > > > > > > > > Blake McBride > > > > > > > > _______________________________________________ > > > > Gambit-list mailing list > > > > Gambit-list(a)iro.umontreal.ca > > > > https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list > > > > > > > > > > > > _______________________________________________ > Gambit-list mailing list > Gambit-list(a)iro.umontreal.ca > https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list >

2 1

Computing pi with parallel gambit
by Bradley Lucier 06 Fév '17

06 Fév '17

Marc: Because of accumulated roundoff error in IEEE floating-point arithmetic, Gambit's FFT-based bignum multiplication algorithm is limited to multiplying two numbers each of which has <= 2^{29} bits (on a 64-bit machine). Multiplying larger numbers falls back on Karatsuba multiplication, which cuts the size of the multiplicands roughly in half in each step, until you get back down to numbers of <= 2^{29} bits again, in which case FFT is used again. So, in fact, to compute a billion decimal digits of pi, we rely on Karatsuba to do the largest multiplications (and divisions and square roots, since they all reduce to multiplication). On a machine with enough memory, all the "sub-multiplications" in Karatsuba can be done in parallel. I haven't figured out how much memory is needed; it takes a few GB of temporary RAM to multiply the largest numbers with the FFT algorithm. I believe it took about 16GB total to calculate a billion decimal digits of pi using the current serial algorithm. Once parallel gambit is usable, computing pi to a billion (or even 10 billion, who knows) digits by parallelizing the larger Karatsuba multiplications might be a good test of the system. Brad

3 20

Using snow to create gambit executable
by C K Kashyap 04 Fév '17

04 Fév '17

Hi, Could someone please tell me how I can create executables using snow - snow's documentation says snow --compile file.scm produces file.o1 How can I link file.o1? I found out about "bundle" only now so please excuse my ignorance. Regards, Kashyap

3 5

SMP Gambit
by Marc Feeley 29 Jan '17

29 Jan '17

I have just created the “smp” branch which contains a major refactoring of the thread scheduler to support parallel thread execution. Please note that this is an experimental branch that omits some of the thread features of Gambit (thread priorities, thread interruption, etc). So you should avoid those features in your experiments, and don’t use the smp branch for production code! I have done some quick testing on OS X and linux, on intel architecture. I’m interested in feedback on Windows and other processor architectures, ARM in particular. I have also only tried the GNU gcc C compiler. There are special steps needed to build the smp branch. Here are the commands starting with a git clone: git clone https://github.com/gambit/gambit.git cd gambit git checkout master ./configure make -j4 latest-release ./configure --enable-single-host make -j4 from-scratch git checkout smp cp gsc/_prims.scm gsc/_prims.scm-smp cp gsc/_t-c-2.scm gsc/_t-c-2.scm-smp git checkout master cp gsc/_prims.scm-smp gsc/_prims.scm cp gsc/_t-c-2.scm-smp gsc/_t-c-2.scm make -j4 make bootstrap git reset --hard git checkout smp make bootclean ./configure --enable-single-host --enable-multiple-threaded-vms make -j4 make check Preliminary performance testing on 4 and 64 core machines show good performance. Threaded fibonacci of 45, which creates 317810 threads and has a thread granularity of 0.2 ms, runs 7.96x faster when using 8 processors instead of 1, and it runs 30x faster when using 64 processors (see attached transcript). So please give it a try and report any issues! Marc % gsc/gsc -:=. tfib.scm % gsi/gsi -:p1 tfib (time (tfib 45)) 69957 ms real time 69983 ms cpu time (69249 user, 733 system) 9 collections accounting for 1811 ms real time (1577 user, 235 system) 521655584 bytes allocated 215447 minor faults no major faults 1836311903 % gsi/gsi -:p8 tfib (time (tfib 45)) 8794 ms real time 70097 ms cpu time (69745 user, 353 system) 14 collections accounting for 200 ms real time (1307 user, 107 system) 104214752 bytes allocated 69552 minor faults no major faults 1836311903 % gsi/gsi -:p64 tfib (time (tfib 45)) 2333 ms real time 143035 ms cpu time (141703 user, 1332 system) 8 collections accounting for 395 ms real time (18796 user, 992 system) 10612584 bytes allocated 29126 minor faults no major faults 1836311903 % cat tfib.scm (declare (standard-bindings) (not safe) (fixnum) (block)) (define (tfib n) (if (< n 2) 1 (if (< n 20) (+ (tfib (- n 1)) (tfib (- n 2))) (let ((x (make-thread (lambda () (tfib (- n 1)))))) (thread-start! x) (let ((y (tfib (- n 2)))) (+ (thread-join! x) y)))))) (pp (time (tfib 45)))

2 10

Question about compilation using gsc
by C K Kashyap 27 Jan '17

27 Jan '17

Hi, Here's an observation that I have - I have "f1.scm" that defines a function f1 and f2.scm that defines f2 (which calls f1) 1. If I do gsc -o out -exe f1.scm f2.scm - out gets generated but I get the error unbound2/operator not a procedure 2. However, if I do gsc -out f2.scm f1.scm, things work fine So my question is, is that expected as in, I must ensure that the list of files are in the right order (in terms of dependencies)? or am I missing some option? Also, I'd appreciate some pointers to using definitions from another file - I found (##include) - is that the way to go? Regards, Kashyap

2 2

Need help with getting started with lalr
by C K Kashyap 26 Jan '17

26 Jan '17

Hi, I downloaded lalr-v2_3_0.tgz from http://snow.iro.umontreal.ca/?viewpkg=lalr. I then copied lalr.scm and calc.scm from the tgz into a clean directory and tried to load lalr.scm in gsi and got this error - root@kashyap-desktop:~/explore# gsi Gambit v4.8.7 > (load "lalr.scm") *** ERROR IN "lalr.scm"@12.20 -- Ill-formed procedure call 1> (exit) Is there some resource I can use to get a headstart with parsing java/csharp like source files in gambit? Would a combinator-based (parsec like) parser be a good idea? Regards, Kashyap

2 9

Google brings AI to Raspberry Pi - BBC News
by Bradley Lucier 25 Jan '17

25 Jan '17

http://www.bbc.com/news/technology-38742762 Marc: When I think of AI, I still think of Lisp/Scheme (especially with high-performance implementations), so this article about AI and the Raspberry Pi made me think of the new parallel Gambit, which will be able to take advantage of all 4 processors on the RPi3. You're going to need a beta (alpha?) test program for Arm implementations. I volunteer! Brad

1 0

Trouble building on mac
by C K Kashyap 21 Jan '17

21 Jan '17

Hi, I tried to build gambit on my home mac mini (macOS Sierra, 10.12.2) first with xcode/gcc using ./configure --enable-gcc-opts --prefix=/Users/kashyap/Documents/dev/gambitInstall; make -j4 latest-release; ./configure --enable-single-host --enable-gcc-opts; make -j4 from-scratch; make check This resulted in ../gsc-boot -:~~bin=../bin,~~lib=../lib,~~include=../include -f -warnings -c -check _t-c-2.scm make: *** [_t-c-2.c] Segmentation fault: 11 I then installed gcc using brew and tried with CC=gcc-6 option ... this too resulted in the same error. I tried running gdb (after all the certificate drama), but was not able to get any more information ... (gdb) r -:~~bin=../bin,~~lib=../lib,~~include=../include -f -warnings -c -check _t-c-2.scm Starting program: /Users/kashyap/Documents/dev/gambit/gsc-boot -:~~bin=../bin,~~lib=../lib,~~include=../include -f -warnings -c -check _t-c-2.scm During startup program terminated with signal SIG113, Real-time event 113. Am I missing a something here? Regards, Kashyap

2 9

Gambit SMP... preliminary results
by Marc Feeley 21 Jan '17

21 Jan '17

I have some news concerning the multiple threaded version of Gambit with encouraging preliminary performance results for mutex based synchronization. The test program starts N threads that each increment a counter a million times. The incrementation is in a critical section implemented with a global mutex. So this is a scenario where there is intense contention for a single mutex by all the threads. I wrote the program in Scheme and also wrote a C version using pthreads. The Scheme program and the results are attached below. When the programs are run (on OS X) with more than one thread (I tried 1 to 7 threads on a 4 core machine), the Gambit program is up to 15x faster than the C program using pthreads. Not bad for a first experiment with *no* tuning of the implementation! I think Gambit is so much faster because suspending a thread, which happens frequently here, is very fast thanks to continuations. Marc (declare (standard-bindings) (extended-bindings) (fixnum) (not safe) (block)) (define count 0) (define mut (make-mutex)) (define (body) (let loop ((n 1000000)) (if (> n 0) (begin (mutex-lock! mut) (set! count (+ count 1)) (mutex-unlock! mut) (loop (- n 1)))))) (define (iota n) (let loop ((i (- n 1)) (lst '())) (if (>= i 0) (loop (- i 1) (cons i lst)) lst))) (define threads (map (lambda (id) (thread-start! (make-thread body))) (iota (##current-vm-processor-count)))) (map thread-join! threads) (pp count) % make gsc -exe test1.scm time ./test1 -:p1 1000000 0.08 real 0.08 user 0.00 sys time ./test1 -:p2 2000000 0.33 real 0.33 user 0.00 sys time ./test1 -:p4 4000000 0.82 real 0.91 user 0.06 sys time ./test1 -:p7 7000000 1.55 real 2.21 user 0.31 sys gcc -O pthread1.c -o test1-pthread time ./test1-pthread 1 count=1000000 0.02 real 0.02 user 0.00 sys time ./test1-pthread 2 count=2000000 5.49 real 0.56 user 5.42 sys time ./test1-pthread 4 count=4000000 12.77 real 1.11 user 12.10 sys time ./test1-pthread 7 count=7000000 22.71 real 2.32 user 21.25 sys

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Gambit-list Janvier 2017