Ask HN: How to Implementing Garbage Collection Algorithms

#1

Post by shefaliprateek » Thu, Jan 12, 2017, 12:57 PM UTC

I have always been interested in garbage collection algorithms and language runtimes. And recently got my hands on "The Garbage Collection Handbook"[1].

My questions is, how can I go about implementing these algorithms :

- are there any student focused language VMs that anyone can recommend ?

- or any other recommendations on how to go about them?

[1] http://gchandbook.org/

Re: Ask HN: How to Implementing Garbage Collection Algorithms

#2

Post by hackermailman » Thu, Jan 12, 2017, 5:52 PM UTC

The Art of Computer Programming Vol 1: Fundamental Algorithms has a chapter on GC for linked lists which is interesting and shows implementation, there's also the Golang forums/mailing lists which discuss GC and it's optimization https://blog.golang.org/go15gc

SICP also has a chapter on GC w/implementation https://mitpress.mit.edu/sicp/full-text/sicp/book/node117.ht...

Universities have some lectures on this too and you can look up the algorithms they mention

https://suif.stanford.edu/~courses/cs243/lectures/l14.pdf Intro to GC

http://web.stanford.edu/class/cs243/lectures/L17-Advanced-GC... Advanced GC

Re: Ask HN: How to Implementing Garbage Collection Algorithms

#3

Post by bjourne » Sat, Jan 14, 2017, 9:38 AM UTC

A prerequisite to that book is understanding objects and pointers. With that I mean how they are represented in actual memory. We don't have to deal with those details when using HLLs. E.g the book talks a lot about "slots" but it is useless unless you understand how a slot and how a reference to a slot is implemented.

Therefore firm knowledge of C is required. Then when you have that knowledge, you can build an object model. I suggest starting with just two simple types: array and integer objects.

Then you can implement simple memory management. The easiest is probably to begin with reference counting. After you have that, continue with mark and sweep, copying collection and more advanced techniques.