Methods of Memory Management in MRI

Interactive Portion

Unlock your phones

Selfie Sticks

Two Purposes

Help you identify people who like fun stuff and to
have a fun time

Let you know who doesn’t like to have fun or
like fun things

Have you seen this?

It’s me!

Methods of Memory Management in MRI

mmmmRuby

Aaron Patterson @tenderlove PGP Fingerprint: 4CE9 1B75 A798 28E8 6B1A
A8BB 9531 70BC B4FF AFC6

I am from Seattle

Which is not Ohio

"Ohio"

h GitHub

GitHub Certiﬁed® Engineer

Bear Metal

x tenderlove

Please call me "Aaron"

("tenderlove" is ﬁne too)

I love cats!

Cats are the best!

I have stickers of my cats

I also have GitHub stickers!

I was in the news recently

Keyboards

New Ruby Features

Soft Typing

Dynamic Typing

Static Typing

Garbage Collector

Memory Terms

Stack Heap

Heap Ruby Heap

GC in MRI

Apps in Production

Scaling Issues

Tuning Issues

What I want you to learn

If you don’t know much about GC

If you know about GC terminology

If you already know the algorithms

If you already know the new stuff

GC Algorithms (in MRI)

Two sides of a GC

Collection Algorithm

Allocation Algorithm

Introspection API

Tuning Variables

Collection Algorithm

What type is the MRI collector?

Generational Incremental Mark & Sweep

High level: What is a GC?

Tree of Objects Root A B C D a =
[ { c: 'd' } ] Ruby Array Hash String Symbol

Tree of Objects Root A B C D a =
[ { c: 'd' } ] a = nil Ruby Array Hash String Symbol

Important Words!

Root Set

Garbage

Live Data

GC’s job: Find unlinked nodes, then free them

How to ﬁnd unlinked nodes

Mark & Sweep

2 distinct phases

Mark Phase Root D A B C F E H
G

Sweep Phase Root D A B C F E H
G

Sweep Phase Root D A B C F

Mark & Sweep Very Easy! Too Slow

"Stop the world"

Visits every object, every time

Walk every object every time

Generational

Objects die young

Divide objects in to "old" and "new"

Generational Root A B D C Gen 0 Gen 1

Generational Root B D Gen 0 Gen 1

Generational Root B D Gen 0 Gen 1 E F
G

Generational Root B D Gen 0 Gen 1 F G

We didn’t have to touch "B"

One Slight Problem

Generational Root B D Gen 0 Gen 1

Generational Root B D Gen 0 Gen 1 E U
nused!

Remembered Set Root B D Gen 0 Gen 1 E

Remember!

Important Words

Write Barrier

Remembered Set

Generational Fast(er)! Not so easy

"Stop the world"

Incremental GC

Tri-Color Marking

Object Colors • White: will be collected • Black: No
reference to white objects, but reachable from the root • Gray: Reachable from root, but not yet scanned

Algorithm 1. Pick an object from the gray set and
move it to the black set 2. For each object it references, move it to the gray set 3. Repeat 1 and 2 until the gray set is empty

Tri-Color Marking Root H G F C B D A
E

What is the beneﬁt?

We can interrupt steps!

Each step can be performed incrementally

Halting time is reduced

One Slight Problem

Tri-Color Marking Root F C B D A

Tri-Color Marking Root F C B D A G

Tri-Color Marking Root F C B D A G Write!

Important Words

Incremental

Write Barrier

Remembered Set

Minimize tracing

Decrease halting

Things our GC is not

Parallel

Real-Time

Compacting

Allocation Algorithm

Heap layout

malloc isn’t free GET IT?????

Large Chunk: Page (or Slab)

Page memory is contiguous

Each page holds a linked list

Nodes are called "slots"

Each slot is a Ruby object

Page Layout Page Ruby Object Ruby Object Ruby Object Ruby
Object Ruby Object

"Free List"

Find the ﬁrst open slot!

Move to the next space in the free list

"Bump Pointer" allocation

Full Pages Object Object Object Object Page Page

"Eden" pages are searched

GC Time Object Object Object Object ☠

Important Words

Interesting Allocation Hacks

Not every object requires allocation

1 Page: 16k

1 Object: 40 bytes

Pages are "aligned"

Not `malloc` but "aligned malloc" `posix_memalign`

Choose "40" as a multiple

Start = 40 >> start = 40 => 40 >>
(start * 1).to_s(2).rjust(10, '0') => "0000101000" >> (start * 2).to_s(2).rjust(10, '0') => "0001010000" >> (start * 3).to_s(2).rjust(10, '0') => "0001111000" >> (start * 4).to_s(2).rjust(10, '0') => "0010100000" >> (start * 5).to_s(2).rjust(10, '0') => "0011001000" >> (start * 6).to_s(2).rjust(10, '0') => "0011110000" >> (start * 7).to_s(2).rjust(10, '0') => "0100011000"

"0000101000" "0001010000" "0001111000" "0010100000" "0011001000" "0011110000" "0100011000"

Use these bits to add meaning

Represent Integers Without Allocation

Encode Number 2 >> INT_FLAG = 0x1 => 1 >>
2.to_s(2) => "10" >> ((2 << 1) | INT_FLAG).to_s(2) => "101"

Decode Number 2 >> 0b101 => 5 >> 0b101 >>
1 => 2

Biggest Fixnum >> ((2 ** 64) - 1).to_s(2) => "11111111111111111111111111111111111111111111111
11111111111111111" >> ((2 ** 64) - 1).class => Bignum >> ((2 ** 63) - 1).class => Bignum >> ((2 ** 62) - 1).class => Fixnum >> ((2 ** 62)).class => Bignum

Biggest Before Heap Allocation >> ((2 ** 64) - 1).to_s(2)
=> "11111111111111111111111111111111111111111111111 11111111111111111" >> ((2 ** 64) - 1).class => Integer >> ((2 ** 63) - 1).class => Integer >> ((2 ** 62) - 1).class => Integer >> ((2 ** 62)).class => Integer R uby 2.4

Fixnums are singletons >> ((2 ** 62) - 1).object_id =>
9223372036854775807 >> ((2 ** 62) - 1).object_id => 9223372036854775807 >> ((2 ** 62)).object_id => 70213216135940 >> ((2 ** 62)).object_id => 70213216117840

Tagged Pointer

Tagged Pointers • Fixnum • Floats • True / False
/ Nil • Symbols

Allocation Problems

Poor Reclamation Object Object Object Object Object Object Object Object
Object Object Object Object

NOPE

CoW problems

1 Ruby Memory Page != 1 OS Memory Page

1 Ruby Page: 16k 1 OS Page: 4k

Object Object Object Parent Process Child Process Object

OS Copies 1 OS Page

We wrote 40 bytes, but 4kb got copied.

Solution: Group Old Objects

Two Page Types Probably Old Page Page Object Object

What is going to be old?

Probably Old class Foo end module Bar CONSTANT = Object.new
def foo "frozen string".freeze end end

Statistically Determined

Efﬁciently use space

Reduce GC time

CoW Friendly

GC Work G GitHub

Key Objects Class / Module Empty

~17% Smaller Heap

github.com/ github/ruby

Future Work

Moving Objects

NOPE YEP

Stack Scanning, Forward Pointers

GC Introspection

Seeing GC info

GC.stat {:count=>21, :heap_allocated_pages=>87, :heap_sorted_length=>87, :heap_allocatable_pages=>0, :heap_available_slots=>35460, :heap_live_slots=>35342, :heap_free_slots=>118, :heap_final_slots=>0, :heap_marked_slots=>22207,
:heap_eden_pages=>87, :heap_tomb_pages=>0, :total_allocated_pages=>87, :total_freed_pages=>0, :total_allocated_objects=>208577, :total_freed_objects=>173235, :malloc_increase_bytes=>5152, :malloc_increase_bytes_limit=>16777216, :minor_gc_count=>19, :major_gc_count=>2, :remembered_wb_unprotected_objects=>189, :remembered_wb_unprotected_objects_limit=>374, :old_objects=>21977, :old_objects_limit=>39876, :oldmalloc_increase_bytes=>485600, :oldmalloc_increase_bytes_limit=>16777216}

GC Performance

GC::Proﬁler >> GC::Profiler.enable => nil >> GC::Profiler.report => nil >>
GC.start => nil >> GC::Profiler.report GC 22 invokes. Index Invoke Time(sec) Use Size(byte) Total Size(byte) Total Object GC Time(ms) 1 0.143 906920 1419840 35496 3.72500000000000586198 => nil >> GC.start => nil >> GC::Profiler.report GC 23 invokes. Index Invoke Time(sec) Use Size(byte) Total Size(byte) Total Object GC Time(ms) 1 0.143 906920 1419840 35496 3.72500000000000586198 2 0.148 906920 1419840 35496 3.47800000000000864020

GC::Proﬁler.enable

GC::Proﬁler.report

Heap Inspection

ObjectSpace.dump_all

ObjectSpace.dump >> require 'objspace' => false >> x = Object.new
=> #<Object:0x007fbcd09334a8> >> ObjectSpace.dump x => "{\"address\":\"0x007fbcd09334a8\", \"type\":\"OBJECT\", \"class\": \"0x007fbcd08dd878\", \"ivars\":0, \"memsize\":40, \"flags\": {\"wb_protected\":true}}\n"

ObjectSpace.dump >> x = Object.new => #<Object:0x007fbcd0959248> >> JSON.parse(ObjectSpace.dump(x))['flags'] =>
{"wb_protected"=>true} >> GC.start => nil >> JSON.parse(ObjectSpace.dump(x))['flags'] => {"wb_protected"=>true} >> GC.start => nil >> JSON.parse(ObjectSpace.dump(x))['flags'] => {"wb_protected"=>true} >> GC.start => nil >> JSON.parse(ObjectSpace.dump(x))['flags'] => {"wb_protected"=>true, "old"=>true, "uncollectible"=>true, "marked"=>true}

Object have 3 generations

ObjectSpace

trace_object_allocations

GC Tuning

RUBY_GC_HEAP _FREE_SLOTS Number of free slots available after a GC

RUBY_GC_HEAP _INIT_SLOTS Number of free slots to initialize the GC
with

RUBY_GC_HEAP_GR OWTH_MAX_SLOTS Never grow more than this many objects

THANKS!

Methods of Memory Management in MRI

Methods of Memory Management in MRI

More Decks by Aaron Patterson

Other Decks in Technology

Featured

Transcript