Interesting Reads: Computer Scientists, SEs, CEs

Status
Not open for further replies.
Joined
Sep 9, 2015
Messages
1,064
Sorry I think this is the right subforum... Old papers but I thought they were amazing and groundbreaking at the time. I think you other Computer Scientists, Software Engineers, Computer Engineers and people who like general algorithms would like these papers.

On the Fly Garbage Collection - Dijkstra et. al
https://pdfs.semanticscholar.org/9be8/b2e40b767544c5da3af1305bbb39f7883044.pdf

I really enjoyed reading this as Dijkstra is, in my opinion, the father of modern computing.

"First we wanted the synchronization and exclusion constraints between the mutator and the collector to be as weak as possible". Definitely seems important. I don't think we want the garbage collector to affect and/or rely on the Mutator. If they did there would be a lot of "stop-the-world" going on as either the mutator would be trying to redirect outgoing edges to other nodes or the garbage collector is trying to sweep the unreachable nodes.


Further reading in the paper:
  • (1) Redirecting an outgoing edge of a reachable node towards an already reachable one
  • (2) Redirecting an outgoing edge of a reachable node towards a not yet reachable one without outgoing edges.
  • (3) Adding -- where an outgoing edge was missing -- an edge pointing from a reachable node towards an already reachable one
  • (4) Adding -- where an outgoing edge was missing -- an edge pointing from a reachable node towards a not yet reachable one without outgoing edges
  • (5) Removing an outgoing edge of a reachable node.

The great subtleties I see in his paper didn't make sense to me until I read the paper for the 3rd time. It was when he mentioned that when he added a NIL root node, then (4) became a special case of (2), and, (3) and (5) became a special case of (1). Interesting to say the least as I didn't understand the first or second time reading through the paper. Then it clicked in my head. -> Since he added a NIL root node (reachable) then (4) is really a special case of (2) because you no longer need to add outgoing edges where they were missing as both edges can exist but just point to NIL and then when a root node needs to point to another sub-node it redirects (action 2) the edge pointing to NIL to the new node.

Further (3) and (5) are special cases because of (1) because now that there is a NIL root node you no longer need to add an edge since when a node is garbage collected, edge to it is redirected to NIL. And for (5) since we can redirect edges to NIL, there is no point in deleting/removing an outgoing edge.

The man is a genius and I love his humbleness, even he states that him and his teammates fell into almost every "logical trap" at the time.


Another amazing read is Mostly Parallel Garbage Collection:
http://www.icsi.berkeley.edu/pubs/networking/ICSI_mostlyparallelgarbage91.pdf

Other leaders in the forefront other than Dijkstra like Boehm when he worked for Xerox Parc. The main thing I found interesting in this his response is that sweeping doesn't matter. What is interesting is how their approach was different or mostly different than Dijkstra's. Pretty nifty how their sweeping phase has little affect on the garbage collector as it is so minimal as they do it sequentially with only objects marked with dirty bits and a page at a time in a queue.

Sorry if it's a TLDR, but I thought they were good reads of people and teams achieving breakthroughs in the computing world that laid the foundation for today.
 
Thanks for the share
smile.gif
 
Originally Posted By: NGRhodes
Thanks, right up my street. I am a Computer Scientist doing systems and software engineering for a University.


Nifty! What University may I ask?
 
Status
Not open for further replies.
Back
Top