Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Papers We Love - Immix mark-region garbage coll...

brixen
August 25, 2016

Papers We Love - Immix mark-region garbage collector

Papers We Love Portland, OR presentation 25 Aug 2016 on the Immix mark-region garbage collector.

brixen

August 25, 2016
Tweet

More Decks by brixen

Other Decks in Technology

Transcript

  1. void fun(Obj a) { Obj m = new Obj(a); work(m);

    delete(m); } Manual Automatic void fun(Obj a) { Obj m(a); work(m); } Managing memory is coupled with program meaning Is the object m garbage collected?
  2. Stack allocation return addr reg N reg M local 0

    obj B obj A ... stack pointer (SP) what is the lifetime of A? does it exceed SF lifetime?
  3. Bump-pointer allocation Obj m = new Obj(a); 0 N M

    M+S current pointer = start of free space new start of free space S = size of object T
  4. Let be an object graph Let A, B, C be

    elements of a graph If A ∈ and A → B, then B ∈ If A ∈ and A → B and B → C, then C ∈
  5. Space efficiency 1. Ratio of space used / space reserved

    close to 1 2. Percentage of space used by metadata as small as possible ( < 1-2%) Fragmentation is the biggest opponent
  6. Fast collection 1. Touch as few objects as possible 2.

    Perform as few operations per object as possible
  7. Two lines define a point Two points define a line

    Duals Two X define a Y ^ intersecting ^ dissimilar
  8. Heap structure Heap divided into blocks Block divided into lines

    Objects cannot span blocks Objects can span lines
  9. Initial allocation 0 N M M+S current pointer = start

    of free space new start of free space S = size of object
  10. Steady-state allocation X N M M+S a hole is free

    range between two pointers (found lazily) Y what happens when an object is too big to fit in the current hole?
  11. Details and policies 1. When to recycle a block? F

    = 1 free object 2. Where to allocate "medium" objects? Overflow block 3. Parallelism - multiple allocator and collector threads, but not concurrent collection 4. Allocate into completely free blocks last
  12. Space efficiency 1. Ratio of space reserved / space used

    close to 1 2. Percentage of space used by metadata as small as possible ( < 1-2%) Fragmentation is the biggest opponent
  13. Fast collection 1. Touch as few objects as possible 2.

    Perform as few operations per object as possible
  14. Fragmentation 1. Bad: occupancy ~20% 2. No overflow allocation and

    bigger "medium" object size 3. No defragmentation
  15. 1. Method inline cache region 2. Constant inline cache region

    3. Machine code region 4. Symbol region 5. Variable scope region 6. Roots region 7. Object finalizer region 8. Inflated header region
  16. "Every system with a primary tracing collector has a poorly

    specified, buggy, slow, partial implementation of a reference counting collector."
  17. $ rbx compile -B -e 'Array.new' ============= :__script__ ============== Arguments:

    0 required, 0 post, 0 total Arity: 0 Locals: 0 Stack size: 2 Literals: 4: :Array, :new, :allocate, :initialize Lines to IP: 1: 0..22 0000: push_const :Array 0002: dup 0003: check_serial :new, 47 0006: goto_if_false 0018: 0008: allow_private 0009: send_method :allocate 0011: dup 0012: allow_private 0013: send_method :initialize 0015: pop 0016: goto 0020: 0018: send_method :new 0020: pop 0021: push_true 0022: ret ----------------------------------------
  18. $ rbx compile -B -e 'Array.new' ============= :__script__ ============== Arguments:

    0 required, 0 post, 0 total Arity: 0 Locals: 0 Stack size: 1 Literals: 1: :Array Lines to IP: 1: 0..5 0000: push_const :Array 0002: allocate 0003: pop 0004: push_true 0005: ret ----------------------------------------