Sunday, June 28, 2015

Implement Garbage Collector


Baby's First Garbage Collector – journal.stuffwithstuff.com




  • Any object that’s being referenced by a variable that’s still in scope is in use.
  • Any object that’s referenced by another object that’s in use is in use.


    1. Starting at the roots, traverse the entire object graph. Every time you reach an object, set a “mark” bit on it to true.
    2. Once that’s done, find all of the objects whose mark bits are not set and delete them.
    https://github.com/munificent/mark-sweep/blob/master/main.c
    typedef enum {
      OBJ_INT,
      OBJ_PAIR
    } ObjectType;

    typedef struct sObject {
      ObjectType type;
      unsigned char marked;

      /* The next object in the linked list of heap allocated objects. */
      struct sObject* next;

      union {
        /* OBJ_INT */
        int value;

        /* OBJ_PAIR */
        struct {
          struct sObject* head;
          struct sObject* tail;
        };
      };
    } Object;

    typedef struct {
      Object* stack[STACK_MAX];
      int stackSize;

      /* The first object in the linked list of all objects on the heap. */
      Object* firstObject;

      /* The total number of currently allocated objects. */
      int numObjects;

      /* The number of objects required to trigger a GC. */
      int maxObjects;
    } VM;

    void assert(int condition, const char* message) {
      if (!condition) {
        printf("%s\n", message);
        exit(1);
      }
    }

    VM* newVM() {
      VM* vm = malloc(sizeof(VM));
      vm->stackSize = 0;
      vm->firstObject = NULL;
      vm->numObjects = 0;
      vm->maxObjects = 8;
      return vm;
    }


    void push(VM* vm, Object* value) {
      assert(vm->stackSize < STACK_MAX, "Stack overflow!");
      vm->stack[vm->stackSize++] = value;
    }


    Object* pop(VM* vm) {
      assert(vm->stackSize > 0, "Stack underflow!");
      return vm->stack[--vm->stackSize];
    }

    void mark(Object* object) {
      /* If already marked, we're done. Check this first to avoid recursing
         on cycles in the object graph. */
      if (object->marked) return;

      object->marked = 1;

      if (object->type == OBJ_PAIR) {
        mark(object->head);
        mark(object->tail);
      }
    }

    void markAll(VM* vm)
    {
      for (int i = 0; i < vm->stackSize; i++) {
        mark(vm->stack[i]);
      }
    }

    void sweep(VM* vm)
    {
      Object** object = &vm->firstObject;
      while (*object) {
        if (!(*object)->marked) {
          /* This object wasn't reached, so remove it from the list and free it. */
          Object* unreached = *object;

          *object = unreached->next;
          free(unreached);

          vm->numObjects--;
        } else {
          /* This object was reached, so unmark it (for the next GC) and move on to
           the next. */
          (*object)->marked = 0;
          object = &(*object)->next;
        }
      }
    }

    void gc(VM* vm) {
      int numObjects = vm->numObjects;

      markAll(vm);
      sweep(vm);

      vm->maxObjects = vm->numObjects * 2;

      printf("Collected %d objects, %d remaining.\n", numObjects - vm->numObjects,
             vm->numObjects);
    }

    Object* newObject(VM* vm, ObjectType type) {
      if (vm->numObjects == vm->maxObjects) gc(vm);

      Object* object = malloc(sizeof(Object));
      object->type = type;
      object->next = vm->firstObject;
      vm->firstObject = object;
      object->marked = 0;

      vm->numObjects++;

      return object;
    }

    void pushInt(VM* vm, int intValue) {
      Object* object = newObject(vm, OBJ_INT);
      object->value = intValue;

      push(vm, object);
    }

    Object* pushPair(VM* vm) {
      Object* object = newObject(vm, OBJ_PAIR);
      object->tail = pop(vm);
      object->head = pop(vm);

      push(vm, object);
      return object;
    }

    void objectPrint(Object* object) {
      switch (object->type) {
        case OBJ_INT:
          printf("%d", object->value);
          break;

        case OBJ_PAIR:
          printf("(");
          objectPrint(object->head);
          printf(", ");
          objectPrint(object->tail);
          printf(")");
          break;
      }
    }

    void freeVM(VM *vm) {
      vm->stackSize = 0;
      gc(vm);
      free(vm);
    }
    https://tianrunhe.wordpress.com/2012/03/24/data-structure-and-algorithms-for-garbage-collection-in-c/
    Read full article from Baby's First Garbage Collector – journal.stuffwithstuff.com

    No comments:

    Post a Comment

    Labels

    Review (554) System Design (293) System Design - Review (189) Java (178) Coding (75) Interview-System Design (65) Interview (60) Book Notes (59) Coding - Review (59) to-do (45) Knowledge (39) Linux (39) Interview-Java (35) Knowledge - Review (32) Database (30) Design Patterns (29) Product Architecture (28) Big Data (27) Soft Skills (27) Miscs (25) MultiThread (25) Concurrency (24) Cracking Code Interview (24) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Distributed (20) Interview Q&A (20) OOD Design (20) System Design - Practice (19) Security (17) Algorithm (15) How to Ace Interview (15) Brain Teaser (14) Google (13) Linux - Shell (13) Spark (13) Spring (13) Code Quality (12) How to (12) Interview-Database (12) Interview-Operating System (12) Redis (12) Tools (12) Architecture Principles (11) Company - LinkedIn (11) Testing (11) Resource (10) Solr (10) Amazon (9) Cache (9) Search (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Company - Uber (8) Interview - MultiThread (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Scalability (8) Cassandra (7) Git (7) Interview Corner (7) JVM (7) Java Basics (7) Machine Learning (7) NoSQL (7) C++ (6) Design (6) File System (6) Highscalability (6) How to Better (6) Kafka (6) Network (6) Restful (6) Trouble Shooting (6) CareerCup (5) Code Review (5) Company - Facebook (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Be Architect (4) Big Fata (4) C (4) Company Product Architecture (4) Data structures (4) Design Principles (4) Facebook (4) GeeksforGeeks (4) Generics (4) Google Interview (4) Hardware (4) JDK8 (4) Optimization (4) Product + Framework (4) Shopping System (4) Source Code (4) Web Service (4) node.js (4) Back-of-Envelope (3) Company - Pinterest (3) Company - Twiiter (3) Company - Twitter (3) Consistent Hash (3) GOF (3) Game Design (3) GeoHash (3) Growth (3) Guava (3) Interview-Big Data (3) Interview-Linux (3) Interview-Network (3) Java EE Patterns (3) Javarevisited (3) Map Reduce (3) Math - Probabilities (3) Performance (3) Puzzles (3) Python (3) Resource-System Desgin (3) Scala (3) UML (3) geeksquiz (3) AI (2) API Design (2) AngularJS (2) Behavior Question (2) Bugs (2) Coding Interview (2) Company - Netflix (2) Crawler (2) Cross Data Center (2) Data Structure Design (2) Database-Shard (2) Debugging (2) Docker (2) Elasticsearch (2) Garbage Collection (2) Go (2) Hadoop (2) Html (2) Interview - Soft Skills (2) Interview-Miscs (2) Interview-Web (2) JDK (2) Logging (2) POI (2) Papers (2) Programming (2) Project Practice (2) Random (2) Software Desgin (2) System Design - Feed (2) Thread Synchronization (2) Video (2) ZooKeeper (2) reddit (2) Ads (1) Advanced data structures (1) Algorithm - Review (1) Android (1) Approximate Algorithms (1) Base X (1) Bash (1) Books (1) C# (1) CSS (1) Chrome (1) Client-Side (1) Cloud (1) CodingHorror (1) Company - Yelp (1) Counter (1) DSL (1) Dead Lock (1) Difficult Puzzles (1) Distributed ALgorithm (1) Eclipse (1) Facebook Interview (1) Function Design (1) Functional (1) GoLang (1) How to Solve Problems (1) ID Generation (1) IO (1) Important (1) Internals (1) Interview - Dropbox (1) Interview - Project Experience (1) Interview Tips (1) Interview-Brain Teaser (1) Interview-How (1) Interview-Mics (1) Interview-Process (1) Jeff Dean (1) Joda (1) LeetCode - Review (1) Library (1) LinkedIn (1) LintCode (1) Mac (1) Micro-Services (1) Mini System (1) MySQL (1) Nigix (1) NonBlock (1) Process (1) Productivity (1) Program Output (1) Programcreek (1) Quora (1) RPC (1) Raft (1) RateLimiter (1) Reactive (1) Reading (1) Reading Code (1) Refactoring (1) Resource-Java (1) Resource-System Design (1) Resume (1) SQL (1) Sampling (1) Shuffle (1) Slide Window (1) Spotify (1) Stability (1) Storm (1) Summary (1) System Design - TODO (1) Tic Tac Toe (1) Time Management (1) Web Tools (1) algolist (1) corejavainterviewquestions (1) martin fowler (1) mitbbs (1)

    Popular Posts