Arc Forumnew | comments | leaders | submitlogin
Alleged real-time Schemes (schemewiki.org)
4 points by waterhouse 1550 days ago | 2 comments


4 points by waterhouse 1550 days ago | link

RScheme looked like the most promising of these. It uses the terminology of "hard real-time" and "soft real-time" garbage collectors, and claims to have both, working from Wilson and Johnstone's algorithm [1]; also it claims to have threads and a C library interface, and implement nearly everything in R4RS and R5RS. The only warning sign is that nothing much seems to have been done with it since 2005.

However, I am cautiously pessimistic about RScheme for the moment, because I have created a fairly simple test case at which the (default, soft real-time) garbage collector appears to fail horribly (not collecting any garbage at all). I've emailed the developer, and we'll see if he can figure out what's happening and fix it. (Also the hard real-time GC doesn't build; he said he wasn't surprised at that.)

My test case is this loop--all on one line for command line convenience:

(let nub ((n 1000)) (if (= n 0) 0 (let ((h (let loop ((x 10000) (xs '())) (if (= x 0) (length xs) (loop (- x 1) (cons x xs)))))) (if (= 0 (modulo n 100)) (begin (display h) (newline)) 'meh) (nub (- n 1)))))

This does the following 1000 times: cons up a list of 10k elements, compute the length, maybe print the length, and proceed to the next iteration, by which time those 10k cons cells are now garbage. At any point during this computation, the entire set of live objects should be at most 10k cons cells plus the overhead of the loop (and of the RScheme runtime). A properly working Scheme with garbage collection should thus be able to run this in basically constant space; racket, for example, will slightly increase its memory use the first few times you run it, but it reaches a stable state quickly (60-70 MB on my machine here).

However, in RScheme, this causes the "rs" process to consume about 600 MB of memory (300 on a 32-bit system), and running the loop again makes it eat another ~600 (~300) MB; I've tested this on 64-bit Mac OS X as well as several 64- and 32-bit Linuxes across several machines. If we imagine that a cons cell is the size of eight pointers (which might be acceptable overhead for easy implementation), and therefore is 64 bytes on a 64-bit system (32 on 32-bit), and if we suppose that the garbage collector never succeeds in deleting anything, then running the above loop will create 10 million cons cells --> 640 million bytes (320 on 32-bit) = 610.3 MiB (305 MiB on 32-bit), which fits my results very closely.

So... Feel free to try to verify or disprove these results yourself. For convenience, here is a bash command that will download, build, and run RScheme all at once [if you have rlwrap, replace the last bit with "rlwrap ./build/bin/rs" to make things nicer]:

wget http://www.rscheme.org/rs/b/0.7.3.4/7/rs-0.7.3.4-b7.tar.gz && tar xvf rs-0.7.3.4-b7.tar.gz && cd rs-0.7.3.4-b7 && make stage1 && cd src && mkdir build && ./configure --prefix=$(pwd)/build && make all && ./build/bin/rs

I will post any good or bad news I hear from the developer. Meanwhile, with respect to RScheme, I suppose people could attempt to learn to fix it themselves, or learn things from reading the source (or the [1] paper).

Next, Ypsilon seems to build by extracting the source and typing "make" on Linux, and I have gotten it to present a working REPL (which, incidentally, runs my test case in roughly 10 MB of space). Typing "make" on my Mac makes it fail:

  ffi_stub_darwin.s:83:suffix or operands invalid for `push'
  pushl   %ebp #this is a line of code in question
It might be possible to get these things to work, either by figuring out the right build incantations or complaining to the Ypsilon developers (or, again, fixing things ourselves). And then I can see whether it's actually real-time enough for my demands. (My demands: never have to worry about GC for certain projects I at least fantasize about doing, which include implementing real-time games like Starcraft in Lisp.)

Feel free to help evaluate these options. If one of them works, it probably wouldn't be very hard to port any of our various Arc->Racket compilers to it.

[1] "Real-Time Non-Copying Garbage Collection", Wilson and Johnstone 1993: http://www.cs.utexas.edu/ftp/garbage/GC93/wilson.ps

-----

1 point by akkartik 1550 days ago | link

Yeah, rs crashed when I tried to run the loop a second time. Looks like nothing is being reclaimed.

Update: It's hard to debug because linux kills the process when it OOMs http://linuxdevcenter.com/pub/a/linux/2006/11/30/linux-out-o...

-----