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

Edge triggered I/O with libevent
by Adam Langley 05 Avr '13

05 Avr '13

Gambit uses the select call on POSIX systems to multiplex IO operations. This is fine for small numbers of file descriptors, but falls apart quickly with large numbers[1]. libevent[2] is a wrapper library around a number of modern IO multiplexing systems (epoll on Linux, kqueue on the BSDs as well as poll and select). Attached is a patch which converts Gambit to using edge triggered I/O with epoll and libevent. This also requires a patch (attached) of libevent since the standard distribution doesn't include edge triggering support and the upstream appears to be on holiday. (epoll is required because I don't have a BSD box on which to develop edge triggering support for kqueue) This patch (for Gambit) preprocesses away to nothing unless --enable-libevent is passed to the configure script. (Note that, since this patches the configure.ac script, you'll need to run autoconf to regenerate). I hope I've not broken anything, but at this stage I've only tested that the console and tcp ports work. This patch (in the future) should also allow people, who write programs which use socket calls directly, to integrate into the main event loop at some point. Testing is more than welcome and, if you find a form of IO which is broken, please email me. [1] http://monkey.org/~provos/libevent/libevent-benchmark2.jpg [2] http://monkey.org/~provos/libevent/ -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org (+44) (0)7906 332512 PGP: 9113 256A CC0F 71A6 4C84 5087 CDA5 52DF 2CB6 3D60

2 2

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

Re: [gambit-list] handling of macros
by Christian 14 Nov '05

14 Nov '05

I wrote: > Is there an eval to which I could give the current context (as a parameter)? but I was meaning to say, "(as an argument)?". I have yet to get used to use "parameter" only for those dynamic arguments created by make-parameter. Christian.

1 0

handling of macros
by Christian 14 Nov '05

14 Nov '05

Hello Some questions: (the first two of those may be rather general scheme philosophy questions) - why are DSSSL style argument declarations not allowed in define-macro? - why is there no (define-macro foo (lambda(...)...)) form? Is there a lowlevel variant for setting runtime and compiletime macro bindings to some lambda? - is there a way to get at the converter lambda from a (runtime-)macro definition? - I need a way to unset a macro definition, so that the corresponding name can be used as normal function/variable binding from there on. - I'd like to be able to scan a namespace for all bindings and macro bindings. For example for readline completion. (And to be able to remove all runtime macros.) - how can I macro-expand code with the original context? Until now I've used (caddr (##decompile (eval `(lambda() ,code)))) but code is eval'ed in a new lexical context of course. (I haven't understood how to use ##macro-expand. I would be grateful for any help for understanding the sources. How do the cte (=compile-time environment?) and such work? What's the exact concept?) I want macro expansion for writing macros which expand their arguments before working on them. For playing with optimizations (kind of like optimizing mini-compilers). - is there a way to preserve the line/column numbering of source code which is "wrapped" by macros? For something like for example (receive (a b) (code1) code2) it would be nice if when an error happens in code1 or code2, the error message didn't just mention the line/column of the opening paren of the receive form, but the line/column where the relevant part of code1 or code2 is in the original file. Thanks, Christian.

3 4

Bugs in gambit 4.15
by david rush 14 Nov '05

14 Nov '05

two problems I have noticed, but done little in the way of research or remediation: 1 - gsc & gsi when built for solaris 2.6 won't run in the xemacs shell window. No problems in an xterm 2 - (display '(foo bar)) comes out as foobar - I don't know if this is valid RnRS or not, but every scheme I've used has put spaces in between, including gambit 3.0 sorry for the lame bug report, but I figure it's better than nothing david rush -- DIsruptive Technology!

3 3