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

Implementation of read-ieee-float64
by Bradley Lucier 11 Déc '05

11 Déc '05

In the implementation of the withdrawn SRFI-56, read-ieee-float64 has the following code (define (mantissa expn b2 b3 b4 b5 b6 b7 b8) (case expn ; recognize special literal exponents ((255) #f) ; won't handle NaN and +/- Inf ((0) ; denormalized (exact->inexact (* (expt 2.0 (- 1 (+ 1023 52))) (combine b2 b3 b4 b5 b6 b7 b8)))) (else (exact->inexact (* (expt 2.0 (- expn (+ 1023 52))) (combine (+ b2 16) b3 b4 b5 b6 b7 b8)))))) Gambit 4.0b15 fails some srfi-56 tests because the first instance of 2.0 is not 2; unfortunately, Gambit-C calculates (expt 2.0 -1074) as (/ (expt 2.0 1074)) Since the exponent range of IEEE arithmetic is not symmetric, (expt 2.0 1074) is +inf.0, yet (expt 2.0 -1074) is not 0. If both instances of 2.0 are changed to 2, then Gambit passes all the tests. I think that this is what you may have meant in the first place, because you take the trouble to call exact->inexact on what is already an inexact number. Brad

3 8

Re: simple unoptimized gsc nontail recursion
by Christian 08 Déc '05

08 Déc '05

Hello Bill You did address Marc, but I think I can reply something to your questions as well. At 0:51 Uhr -0600 05.12.2005, Bill Richter wrote: > So the tip is this: try to use tail-calls for deep recursions (say > more than 1000 deep). Shallow recursions can be done either with > tail-calls or non-tail-calls. There is a graceful degradation, so > if you happen to do a non-tail-call recursion that is 10000 deep it > will not be a big mistake. Gambit was designed to allow > arbitrarily deep non-tail-call recursions (up to the size of your > heap) which I think is the right thing to do (certainly better than > the core dump that C gives). If you want to limit the depth of > recursion for testing your code, you can add the -:hNNNN runtime > option when you start gsi. > >Marc, I finally realized you gave me a tip, and tried to debug my >program accordingly. So I set a maximum heap size of 100MB: > >export GAMBCOPT=d-,h100000 > > % gsi Curtis-algorithm & > % fg >*** ERROR IN ##make-vector -- Heap overflow > > % gsc Curtis-algorithm > % gcc -O2 -L. -I. Curtis-algorithm.c Curtis-algorithm_.c -lgambc > % ./a.out & >*** ERROR IN Poly->Tree -- Heap overflow > >Can I get the debugger to tell me what's happening when it crashes >here? If you run code from the repl (start gsc without arguments), using compile-file and load, like (compile-file "Curtis-algorithm" '(debug)) (load "Curtis-algorithm") then when running out of memory the debugger is entered. (I haven't used batch compilation for such a long time that I don't remember if the resulting executables should enter the debugger as well.) >Note I get 2 different answers, and the compiled answer makes >more sense to me: Might just be coincidence. To see the place in your code where it happens, enter ",b" in the debugger. (Read the fine manual!) > I'm trying to build a huge tree. It's a dumb >question, because if I thought about my code, I might figure something >out. Well, what is your question then? Maybe you want single step your code: use the interpreter, switch tail-call optimization off (read about proper-tail-calls-set! in the manual), then insert (step) statements into your code (or before running it from the repl). >Also, I have no idea how to relate the recursion depth to the >heap size, but 100MB is 5% of the available memory (2 GB). What does "available memory" mean? Hardware RAM, or a resource limit enforced by your OS? That's probably irrelevant anyway if you set a heap limit using gambit options. What's your question? If you want to know how much memory a particular recursion depth takes, why not insert a recursion depth count in your code and stop recursion at a particular depth to let you see at memory usage, or regularly print the current depth? You probably took Marc Feeley's reply literally ("If you want to limit the depth of recursion for testing your code, you can add the -:hNNNN option"), but this option limits the heap size, not the recursion depth per se (read the help, gsc -:h), and since recursion is only limited by the heap size, this of course also limits recursion depth. >BTW both gsi & gcc crash at the same place: (I don't understand anything in the following output.) Christian.

3 4

Suggest new option: -track-expanded-scheme
by Bradley Lucier 08 Déc '05

08 Déc '05

Marc: In a recent project I've been doing a lot of work debugging and trying to make sure that all code is covered by my tests. -track-scheme is great when combined with options "-ftest-coverage - fprofile-arcs" given to gcc, and then post-processing with gcov. But, of course, it doesn't report on the execution of code generated by macros, which my current project has a fair amount of. Since gsc is already set up to output the macro-expanded source code when it is given the -expansion option, I'd like to have an option -track-expanded-scheme that ties -track-scheme to -expansion, i.e., when compiling foo.scm, it would output foo.scm.exp and insert into foo.c line number directives for foo.scm.exp, and not for foo.scm as -track-scheme does now. This would really help people do test coverage of applications that have a lot of macro-generated code. Brad

1 0

Re: [gambit-list] Installing Gambit on Win32
by Bob McIsaac 07 Déc '05

07 Déc '05

Hi: Yes, I know about the vctoolkit but it has a lot of baggage which prevents install on win98. I am thinking that Scheme distributions should not depend upon some proprietary, free-for-download compiler which is not maintained and may disappear tomorrow. Instead, a "reference implementation" compiler should be bundled. Makefiles for other compilers would only be provided as incidentals. Bundling MSYS with Scheme would make installation simpler and more reliable for both Linux and Win32. -Bob- ---------------------------------- Newcombe, Chris wrote: >Did you know that you can get the Microsoft command-line compiler for free too? > >http://msdn.microsoft.com/visualc/vctoolkit2003/ > >But sorry, I don't have a project file for Gambit. > >regards, > >Chris > >-----Original Message----- >From: gambit-list-bounces(a)iro.umontreal.ca [mailto:gambit-list-bounces@iro.umontreal.ca] On Behalf Of Bob McIsaac >Sent: Tuesday, December 06, 2005 9:25 AM >Cc: Gambit-list(a)iro.umontreal.ca >Subject: [gambit-list] Installing Gambit on Win32 > >Hi Schemers: > >I would like to use Scheme with FFI in my work on embedded >systems. Gambit is appealing because it specifically mentions >serial ports and the code distribution is cleanly organized. > >It installs easily on Linux but not on win98 which is my main >target. There are options for various compilers in /misc. I >don't have the MKS toolkit so I tried the IDE builds for >Watcom and VC++ 4. Neither worked since they look for >files gsi.c and _back.c which don't exist. I also got compile >failures on MSYS/MinGW (but not sure it is installed correctly). > >I suspect these IDE projects may have worked at some time >for a particular release but have not been kept current. This >is a general problem for open-source, cross-platform projects >where the project manager may not have the resources to >recheck the legacy mail-ins from contributors. > >I would like to use one of these win32 compilers:- >* OpenWatcom >* Borland C++ (the free one) >* BloodShed Dev-Cpp > >If someone could provide a project file or simple Makefile, >I would be delighted and eternally grateful. > >regards, >-Bob- > >"Everything should be as simple as possible, but no simpler" >-- Albert Einstein > > > >_______________________________________________ >Gambit-list mailing list >Gambit-list(a)iro.umontreal.ca >http://mailman.iro.umontreal.ca/mailman/listinfo/gambit-list > > > > >

1 0

Re: simple unoptimized gsc nontail recursion
by Marc Feeley 05 Déc '05

05 Déc '05

Simply put: non-tail-calls allocate space and tail-calls don't allocate space. If you have many non-tail-calls in a deep recursion you will allocate a lot (look at the report from the "time" macro to see how much) and this will cause a large garbage-collection time and even thrashing if you don't have enough physical memory. If the recursion is relatively shallow, then Gambit can manage to reclaim the frames without help from the garbage collector, so you will see little difference compared to a tail-call recursion. So the tip is this: try to use tail-calls for deep recursions (say more than 1000 deep). Shallow recursions can be done either with tail-calls or non-tail-calls. There is a graceful degradation, so if you happen to do a non-tail-call recursion that is 10000 deep it will not be a big mistake. Gambit was designed to allow arbitrarily deep non-tail-call recursions (up to the size of your heap) which I think is the right thing to do (certainly better than the core dump that C gives). If you want to limit the depth of recursion for testing your code, you can add the -:hNNNN runtime option when you start gsi. The declarations you mention have two effects 1) they make operations like (- n 1) faster because they are inlined 2) they partly unroll the recursion so that a few of the original recursive calls are performed per actual recursive call (due to the (inlining-limit 1000) declaration) The second point has an impact on the size of the stack frames that are generated. They make the recursion take less total stack space than without the inlining-limit declaration. Here's an example: original code: (declare (not run-time-bindings) (block) (inlining-limit 1000)) (define (f n) (if (= n 0) 0 (+ 1 (f (- n 1))))) is transformed by the inliner into: (define (f n) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (let ((n (- n 1))) (if (= n 0) 0 (+ 1 (f (- n 1))))))))))))))))) By examining the C code generated I see that the original code allocates 4 words per stack frame. The transformed code also allocates 4 words per stack frame, but each stack frame represents 5 original recursive calls. So the transformed code takes only 20% of the stack space. This can (and in your case did) make a big difference in GC time when you are filling your memory with stack frames. I suspect that in the first case the size of the stack was 2000 MB and thus exceeded your physical memory and caused thrashing, and in the second case the stack was 400 MB and fit in physical memory with no thrashing. Marc On 15-Nov-05, at 1:28 AM, Bill Richter wrote: > I have a question about tail recursion, which a mathematician here > explained to me over the weekend. I have a simple program gsc/gcc > didn't optimize as I expected, until I used the declarations > > (declare (standard-bindings) (fixnum) (not safe) (inline) > (inlining-limit 1000) (block)) > > Prior to that, it took gsc/gcc 15 minutes to add up 50 million 1s, and > as John said, the non-tail-recursive program used up way too much > memory. Toward the end of the calculation, I was taking 85% of the > memory of a 1GB machine, and only 4% of its 2.8 Ghz CPU: > > % ps aux |grep a.out > richter 22120 4.1 84.7 3143368 869084 pts/1 D+ 00:04 0:24 ./a.out > > But with these magic declarations, it went down to 6 seconds. Perhaps > someone can offer a tip about when it's necessary to use > tail-recursion, considering Gambit's blinding speed. Code + output: > > ******************************* > > (declare > (standard-bindings) > (fixnum) > (not safe) > ; (run-time-bindings) > (inline) > (inlining-limit 1000) > (block)) > > (define (sub1 x) (- x 1)) > > (define (addones n) > (if (< n 1) > 0 > (+ 1 (addones (sub1 n))))) > > (define (tail_addones n) > (let loop ([n n] > [accum 0]) > (if (< n 1) > accum > (loop (sub1 n) (+ 1 accum))))) > > (display (tail_addones 50)) > (newline) > (display (addones 50)) > (newline) > (time (display (tail_addones 5000000))) > (newline) > (time (display (addones 5000000))) > > (time (display (tail_addones 50000000))) > (newline) > (time (display (addones 50000000))) > > ******************************* > > % gsc tail-john.scm > % gcc -O2 -L. -I. tail-john_.c tail-john.c -lgambc > % ./a.out > > 50 > 50 > 5000000(time (display (tail_addones 5000000))) > 54 ms real time > 4 ms cpu time (4 user, 0 system) > no collections > 152 bytes allocated > 5 minor faults > no major faults > > 5000000(time (display (addones 5000000))) > 483 ms real time > 281 ms cpu time (225 user, 56 system) > 7 collections accounting for 205 ms real time (87 user, 20 system) > 39917112 bytes allocated > 8092 minor faults > no major faults > 50000000(time (display (tail_addones 50000000))) > 137 ms real time > 37 ms cpu time (37 user, 0 system) > no collections > 160 bytes allocated > no minor faults > no major faults > > 50000000(time (display (addones 50000000))) > 5993 ms real time > 2984 ms cpu time (2581 user, 403 system) > 7 collections accounting for 2342 ms real time (1058 user, 181 > system) > 400087168 bytes allocated > 84606 minor faults > no major faults

2 1

bitwise operations
by Bradley Lucier 30 Nov '05

30 Nov '05

Marc: There seems to be a disconnect between the documentation and the implementation of the following procedures in gambc40b15. Perhaps I should document more of the low-level details of the bignum operations so people could contribute faster implementation of some of the bitwise operations. BTW, do you happen to have the implementation of the bitset operations (rather than bitwise operations, including destructive operations) I sent you in gambc40a4.tar.gz on December 16, 2000? I can't seem to find it on my machine. ;-) Brad procedure: any-bits-set? n1 n2 This procedure returns a boolean indicating if the bitwise and of n1 and n2 is different from zero or not. This procedure is implemented more efficiently than the naive definition: (define (any-bits-set? n1 n2) (not (zero? (bitwise-and n1 n2)))) (define-prim (##any-bits-set? x y) (cond ((##not (macro-exact-int? x)) (##fail-check-exact-integer 1 any-bits-set? x y)) ((##not (macro-exact-int? y)) (##fail-check-exact-integer 2 any-bits-set? x y)) (else (##not (##eq? (##bitwise-and x y) 0))))) procedure: all-bits-set? n1 n2 This procedure returns a boolean indicating if the bitwise and of n1 and n2 is equal to n1 or not. This procedure is implemented more efficiently than the naive definition: (define (all-bits-set? n1 n2) (= n1 (bitwise-and n1 n2))) (define-prim (##all-bits-set? x y) (cond ((##not (macro-exact-int? x)) (##fail-check-exact-integer 1 all-bits-set? x y)) ((##not (macro-exact-int? y)) (##fail-check-exact-integer 2 all-bits-set? x y)) (else (##= x (##bitwise-and x y)))))

1 0

small garbage collection issue?
by Christian 29 Nov '05

29 Nov '05

Hello I've noticed that gambc40b14 and gambc40b15 don't collect memory while evaluating this statement in the repl (this is using chjmodule -- ask me if you want a smaller test case): > (build-recursively/import 'cj-stream) > (stream-length (stream-iota)) *** ERROR IN ##cons -- Heap overflow 1> stream-iota creates an infinite lazily evaluated list, so the above is of course essentially an endless loop. Since the head of the stream is not stored anywhere, I expected it to be garbage collected. In fact, the following all work as expected: > (define (f) (stream-length (stream-iota))) > (f) ;;runs forever > (time (stream-length (stream-iota))) ;;runs forever I don't know whether the behaviour of the first case might lead to a problem relevant in practice. Note that leaving the exception handler and running (##gc) still reclaims the space allocated in that case. Christian.

1 0

New intermediate chjmodule release
by Christian 29 Nov '05

29 Nov '05

Hello I've put up a new release of chjmodule and bundled modules. The essence: - some rounded edges during installation, but still no missing-reimports-on-reload bugfix. (I'm too lazy, or rather still pondering the future direction: copying bindings breaks compiler optimizations, and causes slow module loading as long as there is no faster copy implementation, so I'm thinking about using (##namespace ("" foo)) directions under the hood instead, if chjmodule can't see any code in the module mutating a particular imported binding. Note that you could move your (export ...) items to (globals ...) to get the same behaviour (short of mutation checks) with the current chjmodule.) - 13 new modules (most notably a stream library), and a few changes. http://scheme.mine.nu/gambit/chjmodule/ Cheers, Christian.

1 0

libgambc.so.4.15?
by david rush 14 Nov '05

14 Nov '05

Hi All, Another minor annoyance I'm having while porting my world from Gambit 3.0 to 4.0 is the versioning of libgambc.so. Would it be possible to include a version number on the .so along the lines of libc and so many others? This would really help in using my existing tools while I port to the new version. david rush -- DIsruptive Technology!

1 0

Why is flonum arithmetic so slow?
by TJay 14 Nov '05

14 Nov '05

Hi :) I'm curious as to why flonum atrihmetic is so much slower than fixnum arithmetic. For example, the following naive benchmark runs in .8 seconds (as fast as C code!) when declare'd as fixnum, but takes 99 seconds(!) to run in flonum mode. (define iterate-till-zero (lambda (n) (if (> n 0) (iterate-till-zero (- n 1))))) (time (let loop ((n 1000)) (iterateTillZero 1000000) (if (> n 0) (loop (- n 1))))) Does Gambit do some special mojo when dealing with "flonum"s? If so, is there a way to disable said mojo's? I just need fast inexact floating point arithmetic. (C style float or double numbers meet my needs just fine.) ~ TJay ~

2 2