Décembre 2013 - Gambit-list - mailman.iro.umontreal.ca

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

08 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] -target js
by Francois Magnan 02 Fév '14

02 Fév '14

Hi, Sorry to disturb you again on this. I continued my experiments with “-target js”. I reimplemented quasiquote, unquote… and I stumbled on a strange bug that mystifies me: now “cons” function is not known. I have sucessfully compiled programs using cons with -target js many times but now it just won’t compile it correctly. Here is a simplified version of the code just to illustrate what I see: ; File: Minimal-Ex1.scm (declare (standard-bindings) (extended-bindings) (fixnum) (not safe)) ; include Marc's code (include "obj2str.scm") ;;; ;;;; debugging utility ;;; (define (console.log x) ;; Note: the parameter x will be in variable Gambit_r1 (##inline-host-statement "console.log(Gambit_r1.toString());\n")) ;;; ;;;; list utilities I had to redefine ;;; (define (myreverse l) (define (iter a b) (if (null? a) b (iter (cdr a) (cons (car a) b)))) (iter l (list))) (define (iota n) (myreverse (riota n))) (define (riota n) (if (= n 0) (cons 0 '()) (cons n (riota (- n 1))))) (define (foldl func accum lst) (if (null? lst) accum (foldl func (func accum (car lst)) (cdr lst)))) (define (foldr func end lst) (if (null? lst) end (func (car lst) (foldr func end (cdr lst))))) (define (appendo . lists) (foldl append2 '() lists)) (define (append2 l1 l2) (foldr cons l2 l1)) (console.log (object->string (cons 1 2))) ; OK (1 . 2) (console.log (object->string (iota 5))) ; OK (0 1 2 3 4 5) (console.log (object->string (append2 (list 1 2 3) (list 'a 'b 'c)))) ; FAILS [Error] ReferenceError: Can't find variable: Gambit_bb1_cons —————————————————————————————————————- magnan$ gsc -c -target js Minimal-Ex1.scm magnan$ node Minimal-Ex1.js (1 . 2) (0 1 2 3 4 5) /Users/magnan/CDSCode/CDSProducts/Athena-Embedded/src/Athena-Embedded/Minimal-Ex1.js:5551 Gambit_r1 = (Gambit_bb1_cons); ^ ReferenceError: Gambit_bb1_cons is not defined You see that (cons 1 2) and (iota 5) compiles well but not (append2 … ). Can you explain this? Thank you, Francois Magnan On 2013-11-18, at 16:02, Francois Magnan <magnan(a)categoricaldesign.com> wrote: > Hi Marc, > > I was finally able to make a simplified version my program work when compiled to javascript but I am missing some crucial elements to complete the experiment: > > 1 - Variable number of parameters for functions: (define (function . args) …) > 2 - Quasiquote, unquote and unquote-splicing > > Without 1) I cannot get functions like “append” so I have a hard time trying to solve 2). > Can you give me hints for that or drop me an email when those features become available with the “-target js” option? > > Thank you, > François > > > > > > On 2013-11-14, at 17:06, Marc Feeley <feeley(a)iro.umontreal.ca> wrote: > >> >> On Nov 14, 2013, at 4:23 PM, Francois Magnan <magnan(a)categoricaldesign.com> wrote: >> >>> By the way ##inline-host-code doesn’t seem to work anymore. >>> >>> (define (console.log x) >>> ;; Note: the parameter x will be in variable Gambit_r1 >>> (##inline-host-code “console.log(Gambit_r1);\n”)) >>> >>> How can I inline javascript code now? >>> Thank you, >>> Francois >>> >> >> Recall that ##inline-host-code no longer exists... you have to use ##inline-host-statement and ##inline-host-expression depending on the nature of the code. For example, this works for me using node: >> >> (declare (extended-bindings) (not safe)) >> >> (define (show arg) >> (##inline-host-statement "console.log(Gambit_r1.toString());")) >> >> (show 'hello) >> >> (show "world") >> >> (show (##inline-host-expression "1+2+3")) >> >> Marc >> >

3 7

Gambit IOS- access to SDK
by Fuchs Ira 03 Jan '14

03 Jan '14

I've temporarily given up on using Gambit on Android as it seems to fail almost immediately. I have now downloaded the IOS version. Am I correct that there is no way to access any IOS SDK functions? For example, it appears that set-webView-content is not there (as it is in the Android version). I presume this is due to Apple's restrictions on apps. Perhap someone has a version for jailbroken devices? Also when I type (exit) in the REPL on IOS, I get: "To exit, press the sleep button for 5 seconds then the home button for 10 seconds." What is that all about?

5 10

Memory leak (?) using `c-define`d functions from foreign release functions.
by Estevo 01 Jan '14

01 Jan '14

Valgrind reports Gambit is leaking a "sfun stack marker" if I call, from a foreign release function, another function defined with `c-define`. The code below is about the most innocent looking thing I could come up with. Doesn't Gambit like c-define functions called within release functions, or is Valgrind giving me a false positive here (as it is wont to do quite often.) ; ~/gambit-dbg/bin/gsc -exe -cc-options -g test-c-define.scm && valgrind --leak-check=full ./test-c-define (c-declare #<<c-declare-end typedef struct { int x; int y; } point; void scm_release_point(unsigned long); ___SCMOBJ c_release_point(void *ptr) { scm_release_point((unsigned long)ptr); ___EXT(___release_rc)(ptr); return ___FIX(___NO_ERR); } c-declare-end ) (c-define (release-point ptr) (unsigned-long) void "scm_release_point" "" (println "release-point called")) (c-define-type point (pointer "point" (point*) "c_release_point")) (define p ((c-lambda () point "___result_voidstar = ___EXT(___alloc_rc)(sizeof(point));"))) (println "p is " p) (set! p #f) (##gc) ; for good measure... (##gc) (##gc) (println "Bye.") valgrind --leak-check=full ./test-c-define ==16301== Memcheck, a memory error detector ==16301== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al. ==16301== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info ==16301== Command: ./test-c-define ==16301== p is #<point* #2 0x5c04640> release-point called Bye. ==16301== ==16301== HEAP SUMMARY: ==16301== in use at exit: 71 bytes in 1 blocks ==16301== total heap usage: 153 allocs, 152 frees, 4,247,198 bytes allocated ==16301== ==16301== 71 bytes in 1 blocks are definitely lost in loss record 1 of 1 ==16301== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==16301== by 0x4C922E: ___alloc_mem (os_base.c:185) ==16301== by 0x4B7DB5: alloc_mem_aligned (mem.c:452) ==16301== by 0x4B8C57: alloc_scmobj_still (mem.c:1245) ==16301== by 0x4B8D61: ___alloc_scmobj (mem.c:1285) ==16301== by 0x4B8E44: ___make_vector (mem.c:1362) ==16301== by 0x4C677B: ___make_sfun_stack_marker (c_intf.c:6452) ==16301== by 0x4B359E: scm_release_point (test-c-define.c:139) ==16301== by 0x4B354B: c_release_point (test-c-define.c:130) ==16301== by 0x4C24D7: ___release_foreign (c_intf.c:1713) ==16301== by 0x4BC354: free_unmarked_still_objs (mem.c:3271) ==16301== by 0x4BE922: ___garbage_collect (mem.c:4698) ==16301== ==16301== LEAK SUMMARY: ==16301== definitely lost: 71 bytes in 1 blocks ==16301== indirectly lost: 0 bytes in 0 blocks ==16301== possibly lost: 0 bytes in 0 blocks ==16301== still reachable: 0 bytes in 0 blocks ==16301== suppressed: 0 bytes in 0 blocks ==16301== ==16301== For counts of detected and suppressed errors, rerun with: -v ==16301== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)

2 8

FFI types lib v0.1 out.
by Estevo 31 Déc '13

31 Déc '13

Find it at https://github.com/euccastro/gambit-ffi-types See the README there for what's offered and usage instructions. If anything is unclear please ask. I'll add it to the dumping grounds as soon as I get a wiki account (the captcha in the page that creates one is currently broken.) I could think of more functionality to add (e.g. pointers to primitive values, or array support). They shouldn't be hard to implement, but I'll do so only if and when someone asks for them. The same applies to any changes in the interface. For this version I have come back full circle to the approach that uses wills. So the caveat mentioned in other threads applies: *don't take weak references (wills or weak keys or values of tables) of foreign objects*. Or, to be more precise, don't try and access foreign objects obtained from this library that have ever been weakly reachable, unless you know what you're doing. But the stronger restriction is easier to follow. If this is a problem for you please let me know. And if it's not and you're totally fine with this, please let me know too! There are other ways to implement this, and I want to gauge whether there's a need for a different approach. Happy scheming!

1 0

Proposed patches: expt, install-gnu-gcc-osx, expt.scm
by Bradley Lucier 30 Déc '13

30 Déc '13

Marc: Here are some proposed patches: misc/install-gnu-gcc-osx: Update gcc to 4.8.2 (4.8.1 has a bug where it won't recognize my Core i7 4770 properly). Send error messages to build.log. Allow parallelism of 8. lib/_num.scm: Get (expt x y) correct when x is complex, y is an (odd) multiple of 1/2, and the answer is exact. Use ##sqrt for (expt x 1/2) for complex x. tests/unit-tests/03-number/expt.scm: Add tests for the new functionality, and for a bit of the old functionality. I just used misc/install-gnu-gcc-osx on my Ubuntu 13.10 box, and it works fine; perhaps it should be renamed to simply misc/install-gnu-gcc. Brad

1 0

Fwd: Anyone else working in a schemey wrapper for c structs/unions/types?
by Estevo 27 Déc '13

27 Déc '13

It's not true that the experiment below[1] runs valgrind-clean. I must have forgotten to compile with -g or something. Calling a `c-define`d function from a release functions gives me this: https://mercure.iro.umontreal.ca/pipermail/gambit-list/2013-December/007346… Anyway, I worked out a proof of concept where the 'table' is in C: https://github.com/euccastro/refcount-hacks I think this will do the trick. [1] (I sent the reply below only to Mikael, by mistake.) ---------- Forwarded message ---------- From: Estevo <euccastro(a)gmail.com> Date: Thu, Dec 26, 2013 at 2:53 PM Subject: Re: [gambit-list] Anyone else working in a schemey wrapper for c structs/unions/types? To: Mikael <mikael.rcv(a)gmail.com> https://github.com/feeley/gambit/pull/61 - for a quick proof of concept, > that's a very neat use of the ffi type!!! > Thanks! I tried the approach you suggested and the code is much simpler, at least for this particular purpose. There are some dangling questions left, that I explain below in more detail. So you tried to somehow use wills to force GC order? Without having studied > this, I guess that was not what they were intended for in the first place > and it makes good sense that that did not work out well. > I completely agree. > >> Once user code gets hold of A, pure Scheme code can't really know when >> it's OK to let go of that vector. It's the same problem. Of course you >> can keep a reference forever, but you don't want to hold on to unneeded >> memory either. >> > > You should be able to work that out and question is just how heavy it > would be implementation-wise to do, no?? > > If not why not? > There is no way in pure Scheme to detect when an object has been reclaimed. This follows from the unlimited extent semantics mandated in the Scheme Reports. From the perspective of Scheme code, objects are never deleted. Gambit doesn't violate this, and that is fine. > But these restrictions need not be showstoppers. A scheme that might work: >> - on initalization, create an ___alloc_rc'ed table[1] and assign a >> global C pointer to it >> - whenever you create a dependent foreign pointer F, store in the table >> a reference to its dependent object D, keyed by the address of the F's C >> pointer, and >> - set a release function for F that will clear that entry in the table. >> > > Why do you need a "table" (by table here you mean resizable vector)? > No, I mean the type of object that (make-table) returns. I need - to keep strong references to the original object in some place that the garbage collector will scan, - to be able to retrieve these references by key (in particular, by address of the C object to which they point), in order to remove them when the dependent pointer is finalized. > Nice! > > Gambit's builtin functionality for this is fully sufficient at Gambit's > level of abstraction over the underlying system, and indeed there's plenty > of space for higher-level abstractions that more in this area. > Indeed! I should add that I don't want to hide Gambit's standard ffi facilities. I want to hide my own hacks so what the user gets works seamlessly with those facilities, should they need more control than what my library provides. That's why I want to give the user bare foreign objects and no scheme wrappers over them. > So the totality of what you are looking to provide is > > a) the c-struct form which is analogous to define-type with > > b) Scheme-like automatic dependency GC-reference handling between c > structure instances as discussed here > > ? > Yes, at least in a first step. After that is working I'm thinking of doing something similar for arrays of structs/unions/types, perhaps with a vector-like interface. That is, if you allocate an array of structures the array will stick around for exactly as long as you hold a pointer to any of its members. Here's a proof of concept that runs valgrind-clean and prints the expected output in an unmodified Gambit: (c-declare "typedef struct { int x; int y; } point;") (define no-err ((c-lambda () scheme-object "___result = ___FIX(___NO_ERR);"))) (define dependencies (make-table)) (c-define (release-dependent p) ((pointer void)) scheme-object "release_dependent" "" (if p (begin (println "resetting " (foreign-address p)) (table-set! dependencies (foreign-address p))) (println "Null pointer?")) no-err) (c-define-type point (type "point" (point point*))) (c-define-type dependent-point (type "point" (point* point) "release_dependent")) (define (make-dependent-point dependency) (let ((p ((c-lambda () dependent-point "___result_voidstar = ___EXT(___alloc_rc)(sizeof(point)); /* I would really set these using accessors. */ ((point*)___result_voidstar)->x = 1; ((point*)___result_voidstar)->y = 2;")))) (println "setting " (foreign-address p)) (table-set! dependencies (foreign-address p) dependency) p)) (define point-x (c-lambda (point) int "___result = ((point*)___arg1_voidstar)->x;")) (define point-y (c-lambda (point) int "___result = ((point*)___arg1_voidstar)->y;")) (define (point->string p) (string-append "(point " (number->string (point-x p)) " " (number->string (point-y p)) ")")) (define d (cons 'depended 'upon)) (make-will d (lambda (x) (write x) (println " checking out"))) (define p (make-dependent-point d)) (println "p is " (point->string p)) (println "forgetting global d; its will should not get executed yet") (set! d #f) (##gc) (##gc) (##gc) (println "letting go of p; this should kill d in two garbage collections at most") (set! p #f) (println "first garbage collection") ; The first collection triggers the finalization of p, which deletes it from ; the table. But by the time that happens, the table has already been ; scanned, and d has been found there. (##gc) (println "second garbage collection") ; In the second collection d will not be reached anymore, so it's reclaimed. (##gc) (println "done.") This is not the end of the story, though. Some consideration must be added for transitive dependencies and for several foreign objects depending on the same root. I don't think there will be any blockers here. I'll give it a go this afternoon, and if I get something solid I'll withdraw my pull request. Thanks again for bouncing ideas!

1 1

Anyone else working in a schemey wrapper for c structs/unions/types?
by Estevo 26 Déc '13

26 Déc '13

I've experimented in the past with making a macro that would generate the appropriate ffi code to create and manage c structs/unions/types. The challenge was to handle references obtained from accessors to fields containing other structs/union/types within them in such a way that - no copying was necessary, and - the original structure wouldn't be released as long as derived references existed. For example, to handle events in SDL you create a SDL_Event union that you pass to functions to query for events. When the data for a particular event is populated, you query the type with evt.type and then access the fields of the specific type by accessing evt.key, a "view" on the same structure of type SDL_KeyboardEvent. There is no point in copying the structure when you do this. Also, you don't want the SDL_Event to be released while you're using (holding a reference to) the SDL_KeyboardEvent. While in this case it's not hard to manually keep the parent object alive, in the general case it feels more schemey to let the garbage collector take care of that. What I came up with at that time was not legible and I'm not proud of it. While it seemed to work in my x64 machine, I got a segmentation fault when running the tests in a x86 installation: https://github.com/euccastro/gambit-SDL2/blob/master/ffi-macro.scm (find struct-or-union-type) Usage examples: https://github.com/euccastro/gambit-SDL2/blob/master/test-ffi.scm https://github.com/euccastro/gambit-SDL2/blob/master/sdl.scm (see SDL_Event. |voidstar| is how we tell the macro that we want it to manage this as described above) The most straightforward way to do it would be to create, in addition to the macro, a library that maintains a table of weak keys --referring to derived ("child") structs-- to strong values --referring to the original ("parent") structs. In the module above I did just that, but I resorted to dubious tricks to avoid creating that library. In a new shot at this I'd just have the library. I'm also factoring that more nicely so the parts are easier to read and test separately. Another plausible approach would be to allocate a zero-size reference-counted object (with ___alloc_rc(0)), have its data point to the parent, and make a will with the child's foreign object as testator and with an action that kills the reference-counted object. I have tested that wills still execute after they themselves become unreachable, but I don't know whether that's behavior I should rely on. If that is not the case, then the reference-counted object's data could be a (cons parent-foreign will), so the will itself will be kept alive until it's executed. While I had lots of fun looking at the sources and coming up with this, I suspect the more straightforward table approach involves less overhead. If anyone else is interested in doing and/or using something like this, I'm happy to bounce ideas and take suggestions. I'm working on this mostly on weekends, but I'll try and be responsive during the week too. Thanks for reading and have some happy scheming!

4 17

How emulate #e using inexact->exact or something?
by Mikael 25 Déc '13

25 Déc '13

Dear Marc or Brad, First - Happy Holidays! :)) A Q: > #e0.3 3/10 > (inexact->exact 0.3) 5404319552844595/18014398509481984 > #e0.2 1/5 > (inexact->exact 0.2) 3602879701896397/18014398509481984 Why the different results? Is there any way to get the #e behavior in a more effective way than (string-append "#e" (number->string n))? The end goal here is to get decimal arithmetics with precision e.g. (float (* (- 0.3 0.2) 10)) != 0. Thanks, Mikael

4 6

Wills from beyond.
by Estevo 24 Déc '13

24 Déc '13

In gsi, a will that has become unreachable will still execute when its testator is about to become unreachable. What's more, if the will's action is a closure upon some other object, and if we make that other object unreachable too (such that a different will with that other object as a testator executes), when the action executes it will still be able to access that other object. This is probably clearer in code: > (define o1 (cons 'o 1)) > (define o2 (cons 'o 2)) > (define w1 (make-will o1 (let ((o2_ o2)) (lambda (x) (println "w1 says bye to " x " but it can still reach " o2_))))) > (define w2 (make-will o2 (lambda (x) (println "w2 says bye to o2")))) > (define w3 (make-will w1 (lambda (x) (println "w3 says bye to w1")))) > (set! w1 #f) > (gc) w3 says bye to w1 > (set! o2 #f) > (gc) w2 says bye to o2 > (set! o1 #f) > (gc) w1 says bye to o1 but it can still reach o2 > Is this expected semantics, or just accidental behavior that shouldn't be relied upon? If o2 was a foreign object with a finalizer, would it have been released by the time w1 executed, or would w1's closure reference have kept it alive?

2 8