Compilers

There are 7 posts filed in Compilers.

Writing a Mark-Sweep Garbage Collector

  1. Video lecture
  2. Tracing vs. Direct collectors
  3. C++ specifics
    1. Exposed pointers semantics
    2. Pointer or number?
    3. GC roots
  4. Implementation
    1. Traceable objects
    2. Object header
    3. Object graph
    4. The garbage
    5. Custom allocator
    6. Mark phase
    7. Sweep phase
    8. Obtaining pointers
    9. Determining roots
  5. Conclusion

In this articles we’re going to implement a Mark-Sweep garbage collector in C++.

This is the 9th lecture from the Essentials of Garbage Collectors course where we discuss in detail all the aspects of automatic memory management.

Continue reading →

Writing a Pool Allocator

  1. Overview
  2. Blocks and Chunks
    1. Chunks: individual objects
    2. Blocks: groups of chunks
  3. Allocation
    1. Block allocation
    2. Chunk allocation
  4. Deallocation
  5. Objects with custom allocator
  6. Usage and testing
  7. Summary
  8. Further reading

In the previous article on Writing a Memory Allocator we discussed and implemented a generic memory allocator. We have seen how a memory is requested from OS (through the memory mapping), and in particular focused on different strategies of the Free-list allocation.

In today’s lecture we’ll be discussing a Pool allocator.

Continue reading →

Writing a Memory Allocator

  1. Video lecture
  2. Mutator, Allocator, Collector
  3. Memory block
  4. Allocator interface
  5. Memory alignment
  6. Memory mapping
  7. Freeing the objects
  8. Blocks reuse
  9. First-fit search
  10. Assignments
    1. Next-fit search
    2. Best-fit search
    3. Blocks splitting
    4. Blocks coalescing
    5. Explicit Free-list
    6. Segregated-list search
    7. Optimizing the storage
    8. Custom sbrk
  11. Conclusion

This is the 6th lecture from the Garbage Collection Algorithms class, devoted to the automatic memory management.

Before discussing algorithms of collecting the garbage, we need to see how these objects (which eventually become a garbage) are allocated on the heap. In today’s lecture we consider mechanisms of memory allocation.

Continue reading →

MIPS Assembly parser

  1. MIPS Assembly
  2. Parser implementation
    1. Brief overview of parsing algorithms
    2. Using Syntax to implement MIPS parser
  3. Conclusion

MIPS architecture is used in many embedded systems today, including gaming consoles, routers, and other devices. It is a RISC architecture, which makes decoding of the instructions easier, and the number of basic instructions is not that big (in contrast with CISC architecture, used e.g. in x86). This makes MIPS a good learning architecture, and that’s why it’s often used in universities in compiler class for code generation. And as a part of course for implementing a virtual machine for a subset of MIPS instructions, I have built the parser for its assembly. Continue reading →