Hacker News Reader

Comment by nostrademons | Hacker News Reader

Note that Chicken has a very interesting garbage-collection algorithm called "Cheney on the MTA". Basically, the stack is the heap, and no function ever returns. The compiler converts every program to continuation-passing style, where instead of a function returning, it tail-calls a continuation. When the stack exhausts its limit, the runtime longjmps back to a trampoline. Variables captured by the current continuation form the roots of a copying generational GC - the runtime traces every pointer from them and copies the live objects to the heap. The stack then unwinds, with every uncopied object being garbage that gets re-used the next time the stack grows.

It's pretty amazing that it works, particularly in relatively portable C. Also gets fairly decent performance, too: as Schemes go Chicken is one of the faster ones.

https://www.more-magic.net/posts/internals-gc.html

https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54....

View on HN

> as Schemes go Chicken is one of the faster ones.

If you believe ecraven's benchmarks it's pretty exactly middle of the pack. Chez Scheme, Racket, Gerbil, MIT, Bigloo Guile, Loko, Cyclone, and Bones all are more performant.

And the ones where it does better are almost all not very popular implementations.

I think its speed is totally fine and I like the language and community but I don't think it's relatively fast among Schemes.

https://ecraven.github.io/r7rs-benchmarks/

Cheney on the MTA is fundamantally a Tri-Color Mark and Sweep GC. Cyclone Scheme also has this same GC.

Real-world performance usually depends on the details of the implementation, not on the theoretical algorithmic equivalency.

No, Cheney on the MTA uses the stack as the nursery of a generational collector; the live objects are evacuated using Chris Cheney’s copying algorithm (developed for the Cambridge ALGOL 68 compiler).

Chicken’s last generation GC might be mark-sweep, but that isn’t the MTA part.

Here https://en.wikipedia.org/wiki/Cheney%27s_algorithm#Equivalen...

As a side effect it also allows very cheap continuations without stack copying (as activation frames heap allocated)

Well, I have a hunch the scheme world is moving towards delimited continuations, so virtually free call/cc isn't that interesting anymore.

And the continuations are only cheap in the chicken context. Other schemes with other GC strategies have continuations with a large overhead, but still manage to be faster than chicken in benchmarks that are very continuation heavy.

Chicken is a very nice scheme, with probably the nicest Devs of any open source project, but cheney on the MTA is not magic by any stretch.

To my knowledge nobody has recorded a version of the song about Cheney, but it may be enjoyable to listen the more popular version about Charlie: https://www.youtube.com/watch?v=7Tc1GUXxr2o

Great link! The name of Henry Baker's paper is a play-on-words that references that song:

> A Cheney queue is a garbage collection scheme originally described by J. C. Cheney. The MTA is a reference to a song recorded by The Kingston Trio.

https://wiki.c2.com/?CheneyOnTheMta

Reply on news.ycombinator.com