Gambit-list Avril 2021

gambit-list@iro.umontreal.ca

3 participants
5 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

georgjz/functional-geometry-gambit-scheme: A simple implementation based in Peter Henderson's paper "Functional Geometry"
by Bradley Lucier 09 Mai '21

09 Mai '21

https://github.com/georgjz/functional-geometry-gambit-scheme This appeared on Scheme Reddit, but I thought it may be of interest to some people on this list. Brad

2 1

How to bind future-based API (FoundationDB)
by Amirouche Boubekki 30 Avr '21

30 Avr '21

I want to bind Gambit with the future-based API of FoundationDB client driver. FoundationDB is a database, most of the time distributed, supported by an OKVS interface, that I used as inspiration for SRFI-167. Client side, there is a C library that implements the network protocol, that exposes a Future based API. There is really two things to that happens in chronological order at runtime in a FoundationDB application: # select API version found.api_version(620) # Create the database handle db = await found.open() Inside `open()` some POSIX threads trickery happens, it will run the foundationdb client network thread with something like: class NetworkThread(threading.Thread): def run(self): check(lib.fdb_run_network()) Where fdb_run_network is bound to the C function [0] with the same name. Its documentation says: > Must be called after fdb_setup_network() before any asynchronous functions in this API can be expected to complete. Unless your program is entirely event-driven based on results of asynchronous functions in this API and has no event loop of its own, you will want to invoke this function on an auxiliary thread (which it is your responsibility to create). > This function will not return until fdb_stop_network() is called by you or a serious error occurs. It is not possible to run more than one network thread, and the network thread cannot be restarted once it has been stopped. This means that once fdb_run_network has been called, it is not legal to call it again for the lifetime of the running program. [0] https://apple.github.io/foundationdb/api-c.html#c.fdb_run_network In particular I am not in the case described with the following sentence: > Unless your program is entirely event-driven based on results of asynchronous functions in this API and has no event loop of its own Because my program is also a HTTP server. Once the network is setup, and running, one can use the provided functions to access the database such as: [1] https://github.com/amirouche/asyncio-foundationdb/blob/85cdb183f92af421d9c3… and the callback is here: [2] https://github.com/amirouche/asyncio-foundationdb/blob/85cdb183f92af421d9c3… To summarize how I implemented it with Python asyncio (inspired from the official bindings): - Call the C function that returns a FDB Future - Create a python asyncio future, - Pass the Python future as the data of the FDB future callback - When the FDB Future is complete, the future will trigger the above callback defined at [2] - The callback at [2], is executed in FDB network thread, will retrieve the result, and resolve the Python future with it, in a way that is POSIX thread safe - The code that is waiting on the Python Future, will proceed at [3] [3] https://github.com/amirouche/asyncio-foundationdb/blob/85cdb183f92af421d9c3… That is a description of the async approach. The FDB Future API, also allow a synchronous approach that still involves a network thread: [4] https://apple.github.io/foundationdb/api-c.html#future I think the easiest path is using the FDB Future synchronous API aka. blocking API, but that would still require to spin a network thread in a POSIX thread. Any help will be greatly appreciated. ref: https://github.com/apple/foundationdb

2 1

Re: [gambit-list] R: Contributing to Gambit
by Amirouche Boubekki 30 Avr '21

30 Avr '21

Le ven. 29 janv. 2021 à 16:58, luca regini <luca.regini(a)gmail.com> a écrit : > > I would also be willing to contribute more to Gambit but the hard fact is that this requires a big investment of time upfront. > > Getting into the internals without specific documentation probably requires to invest at least 2 weeks full-time upfront. > > Which is not impossible if one is fully dedicated to this project ( as a student can be ) but for people with a job and a family this is impossible. I can dedicate time in bursts of 1 hours maybe 2 hours max. > > An idea that I could suggest is to write a commercial book describing the implementation so to sponsor some additional work on Gambit. I would be willing to buy such a book but have no idea how many other would be willing to spend money on that. I agree I would buy a book about gambit compiler, and other internal aspects (like how macro works). FWIW, my plan WAS to build my own scheme that targets javascript with Chez as host. Among other things because it is difficult, but also because gambit is great, and I want to take part in something bigger than myself. I do my best to document what I am doing with gambit (https://github.com/pre-srfi/webui/), and try to workaround some behaviors that are not perfect or at least could be improved upon. I can work around those. But more important than all of the above. I agree that the compiler or compilers must be documented. It might be the first and most important priority to help gambit grow as a community. nanopass is overrated. It seems to me based on a few couple hours of hacking that it is possible to build something simpler and easier to use. Again, I am not a compiler specialist. Maybe a nanopass is a dead end for gambit, or maybe gambit approach is better. Who knows? Marc, you are in the best position to describe the compiler.

2 2

Moving a ___SCMOBJ that is ___STILL from Scm to C to Scm is fine?
by Phillip Suero 27 Avr '21

27 Avr '21

Dear Marc, I ran this code: (c-declare "___SCMOBJ storage;") (define store! (c-lambda (scheme-object) void "storage = ___arg1;")) (define get (c-lambda () scheme-object "___return(storage);")) (define (gen-c) (let ((abc #f)) (##still-copy (lambda (v) (define o v) (set! abc v) o)))) (define gen-i (eval '(lambda () (let ((abc #f)) (##still-copy (lambda (v) (define o v) (set! abc v) o)))))) To test the hypothesis that a ____STILL closure can be successfully passed as a ___SCMOBJ from Scheme to C, stay in C for a while and then be moved back to Scheme anytime. A normal closure will not work, since it changes memory address. However, thanks to ##still-copy , I can get a closure that has a fixed memory address all up to collection, and such a closure's ___SCMOBJ can then be kept in C for as long as desired. Also, this ___STILL closure will still be collected, so there is no memory leak problem. The code above outputs: > (load "test") "/path/to/test.o1" > (define x (gen-c)) (print x " ") (store! x) (##gc) (print (get) "\n") > #<procedure #2 x> > > > #<procedure #2 x> > (define x (gen-i)) (print x " ") (store! x) (##gc) (print (get) "\n") > #<procedure #3 x> > > > #<procedure #3 x> The only operational requirement for the transfer of a ___SCMOBJ from C to Scheme is that the object is still alive. In the example code above, that is guaranteed by that a strong reference to the closure is kept in |x| up to that (get) has made the transfer from C to Scheme, which then produces a new strong reference to the closure, which is sufficient in itself. Example to illustrate clean transfer of the strong reference: (define x (gen-c)) ; Generate closure (print x " ") (store! x) ; Store closure in C world, however still keep strong reference in |x| (##gc) ; All non-___STILL/___FIXED allocated objects will change ___SCMOBJ, thus invalidating them (define y (get)) ; We pick up the ___SCMOBJ from the C world and assign it to |y|. |x| above must be maintained as a strong reference up to the completion of this step. ; |x| is no longer needed for (get) to work, here, since we have a separate strong reference to the object now, in |y|. (set! x #f) (##gc) ; All fine. (print y "\n") The above example breaks, if the (##still-copy part is removed, in which case the closure will be ___MOVABLE, the ___SCMOBJ will be invalidated at GC, and therefore accessing the result of (get) produces SIGSEGV or similar unknown behavior, in my test it would print out #<unknown>. Marc please confirm that what I do above here is a best practice and is all correct. Phil

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 Avril 2021