5 ms·

CHICKEN internals: the garbage collector

68 points by qwertyuiop924 10y ago

sullyj3 10y ago
Imagine how that headline would look to non-programmers
- deleted 10y ago
  [deleted]
gpderetta 10y ago
The nice thing about a Cheney-On-The-MTA style collector, in addition to allowing for relatively cheap first class continuations, is that makes the whole stack vs heap allocation moot.
- zde 10y ago
  Indeed, they use stack as fast bump allocator. That's really smart but probably fairly inefficient, since all the return addresses, stack frames and saved registers are just write-only junk.
  - qwertyuiop924 10y ago
    ...But that's the part that allows for cheap first class continuations, because in Scheme, those stack frames can be part of a datastructure. Sort of. Continuations are confusing.
  - gpderetta 10y ago
    That's a problem when compiling via C (which admittedly is one of the major selling point of the technique), when targeting a lower level intermediate language or even assembly, custom calling conventions are an option.
  - KMag 10y ago
    GCC at least has an annotation that can be used to tell the compiler that a function call never returns. I don't have the details, but I presume it causes the compiler to omit any save/restore code, though I would guess that the return address is still pushed (x86 call instead of jmp) so that you get decent stack traces. 16-byte stack alignment across calls means that the average cost of pushing the return pointer is 8 bytes. It's not free, but it's cheap.
david-given 10y ago
Regarding the rant at the end about papers being behind paywalls (which, BTW, I agree with): If anyone doesn't know, CiteSeerX is a search engine which finds, collects, and caches publicly available papers from around the internet. It's invaluable for finding freely-available papers which the major sources (like the ACM) only make available from behind paywalls. Here's CiteSeerX's page on the paper in question: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.5242&rank=3&q=A%20nonrecursive%20list%20compacting%20algorithm&osm=&ossid= http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.5... I find it fantastically useful.
- qwertyuiop924 10y ago
  Indeed. It's surprising how many papers you can find for free just by going to the author's website.
- profquail 10y ago
  Google Scholar is also useful for this, and indexes CiteSeerX: http://scholar.google.com http://scholar.google.com

68 points by qwertyuiop924 10y ago

sullyj3 10y ago

Imagine how that headline would look to non-programmers

deleted 10y ago
[deleted]

gpderetta 10y ago

The nice thing about a Cheney-On-The-MTA style collector, in addition to allowing for relatively cheap first class continuations, is that makes the whole stack vs heap allocation moot.

zde 10y ago
Indeed, they use stack as fast bump allocator. That's really smart but probably fairly inefficient, since all the return addresses, stack frames and saved registers are just write-only junk.
- qwertyuiop924 10y ago
  ...But that's the part that allows for cheap first class continuations, because in Scheme, those stack frames can be part of a datastructure. Sort of. Continuations are confusing.
- gpderetta 10y ago
  That's a problem when compiling via C (which admittedly is one of the major selling point of the technique), when targeting a lower level intermediate language or even assembly, custom calling conventions are an option.
- KMag 10y ago
  GCC at least has an annotation that can be used to tell the compiler that a function call never returns. I don't have the details, but I presume it causes the compiler to omit any save/restore code, though I would guess that the return address is still pushed (x86 call instead of jmp) so that you get decent stack traces. 16-byte stack alignment across calls means that the average cost of pushing the return pointer is 8 bytes. It's not free, but it's cheap.

david-given 10y ago

Regarding the rant at the end about papers being behind paywalls (which, BTW, I agree with): If anyone doesn't know, CiteSeerX is a search engine which finds, collects, and caches publicly available papers from around the internet. It's invaluable for finding freely-available papers which the major sources (like the ACM) only make available from behind paywalls. Here's CiteSeerX's page on the paper in question: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.5242&rank=3&q=A%20nonrecursive%20list%20compacting%20algorithm&osm=&ossid= http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.5... I find it fantastically useful.

qwertyuiop924 10y ago
Indeed. It's surprising how many papers you can find for free just by going to the author's website.
profquail 10y ago
Google Scholar is also useful for this, and indexes CiteSeerX: http://scholar.google.com http://scholar.google.com