Parallel programmingin Ruby3
with Guild
Koichi Sasada
Cookpad Inc.
<ko1@cookpad.com>

Today’s talk
• Ruby 2.6 updates of mine
• Introduction of Guild• Design• Discussion• Implementation• Preliminary demonstration

Koichi Sasada
http://atdot.net/~ko1/• is a programmer• 2006-2012 Faculty• 2012-2017 Heroku, Inc.
• 2017- Cookpad Inc.
• Job: MRI development• Core parts• VM, Threads, GC, etc

Koichi Sasda
is a father of theyoungest attendee ofRails Girls Tokyo 10th
@Cookpad Tokyo officeMy achievements for Ruby 2.6• Speedup `Proc#call` … x1.4 improvements[Bug #10212].
• Speedup `block.call` where `block` ispassed block parameter. [Feature #14330](x2.62).
• Introduce Transient heap [Bug #14858]

Transient heap
• Manage heap for young memories• vs. malloc heap
• malloc()/free() is heavy operation and introduce
memory fragmentation issue and theap solves it.
• Using Generational copy GC algorithm w/ MRI
specific hack

• Array, Object (user defined class), Struct andsmall Hash objects use theap now• Support String is desired, but too difficult

Transient heap
Array creation (loop{Array.new(n))
Array with 0..3
elements don’t
use theap

Speedup ratio (upper is better)

2.5
2

x1.5

1.5

x1.0

1
0.5
0
0

5

10

15

20

Array.new(x)

25

30

35

Transient heap
Small hash creation (loop{h = {…}})
Speedup ratio (upper is better)

3.5
3>8 Hashobjects don’t
use theap

2.5
2

x1.5

1.5

x1.0

1
0.5
0

0

1

2

3

4

5

6

# of Hash elements

7

8

9

10

Ruby 2.6: Transient heap
Summary• Transient heap is new memory hack
• Generational Copy GC technique• MRI specific hack to keep compatibility• Your application can improve performance on
Ruby 2.6• Microbenchmarks show good improvements.
• x1.5 - x2.0 faster for creation & collection• Unfortunately, discourse rails benchmark doesn’tshow clear perf. improvements

Parallel programmingin Ruby3
with Guild
Koichi Sasada
Cookpad Inc.
<ko1@cookpad.com>

TL;DR• Guild is new concurrent abstraction to force
no-sharing mutable objs for Ruby 3• Guild specification is not fixed yet• Guild implementation is not mature (PoC)• Your comments are highly welcome!!

Background of
GuildMotivation
Productivity (most important for Ruby)• Thread programming is too difficult because sharing
mutable objects• Correct/safe concurrent programs easily is important

Performance by Parallel execution• Utilizing Multi/many CPU cores is important for performanceRubyKaigi2016 (and RubyConf 2016)
Proposal
Guild: new concurrency abstraction for Ruby 3• Idea: DO NOT SHARE mutable objects between Guilds→ No data races, no race conditions

Replace Threads to Guilds

Design of
Guild
Not fixed yet.

Guilds, Threads and Fibers• Guild has at least one thread (and a thread
has at least one fiber)

Guild
ThreadFiber
FiberThread
Fiber

Guild
Guild
ThreadFiberThreadFiberThreads in different guilds
can run in PARALLEL• Threads in different guilds can run in parallel• Threads in a same guild can not run in parallelbecause of GVL (or GGL: Giant Guild Lock)
Acquire GGL

G1:T1
G1:T2
G2:T3

Acquire GGLMaking Guilds
g1 = Guild.new do
expr1
end
g2 = Guild.new do
expr2
end
# Two new Guilds and Threads are created# expr1 and expr2 can run in parallel

Inter-Guild communication
Share only “shareable” objects
Guild 1

normalnormalmutablenormalmutableobj
mutableobj
obj

Shareable
obj1

Guild 2

Shareable
obj2

normalnormalmutablenormalmutablenormalobj
mutableobj
mutableobj
obj

Design “shareable” and “non-sharable”• You can enjoy usual mutating
programming without any thread-safeconcerns because we can’t share mutableobjects between Guilds. They are “nonsharable”.
• In other words, you can’t make threadunsafe (data-racy) programs on Guilds.

Design “shareable” and “non-sharable”• On concurrent programs, most of objects are notshared (thread-local)• Tons of local objects and a few sharing objects• You only need to care about a few sharable objects
non- nonnonsharable
non- nonsharable
sharablenon- nonnonsharable
non- sharable
sharablenonnon- non- nonsharable
sharablesharablenonsharable
non- sharable
sharablesharablenonsharable sharable
sharablesharablesharableDesign “shareable” and “non-sharable”• Non-shareable objects == most of objects• Most of mutable objects (String, Array, …)• They are member of only one Guild• If you use only 1 Guild, it compatible with Ruby 2

Guild 1

NG!!
obj

obj
obj

Can’t access(read/write)

Guild 2obj
obj

Design “Shareable” and “non-sharable”• Shareable objects• (1) Immutable objects (Numeric, Symbol, …)• (2) Class/Module objects• (3) Special mutable objects• (4) Isolated Proc

• Important invariant• Sharable objects only refer to sharable
objects

Shareable objects(1) Immutable objects• Immutable objects can be shared with any guilds• Because no mutable operations for them

• “Immutable” != “Frozen”• a1 = [1, 2, 3].freeze: a1 is Immutable• a2 = [1, Object.new, 3].freeze: a2 is not Immutable• Maybe we will introduce deep freeze feature• Example of immutable objects• Numeric objects, symbols, true, false, nil are immutable• Frozen string objects are immutable (if they don’t haveinstance variables)Shareable objects(2) Class/Module objects• All objects (including any sharable objects) point toown classes• Good:• Easy Implementation and good communication performance• Sharing class/module objects makes program easier• Bad:• They can point to other mutable objects with Constants,@@class_variable and @instance_variables

class C
Const = [1, 2, 3] # Const points a mutable
array
end
# We will introduce special protocol for them

Shareable objects(3) Special mutable objects• Introduce shared/concurrent data structure• Shared hash, array, …
• Software transactional memory (from Clojure, …), …
• Guild objects and so on• They require special protocol to force
synchronization explicitly• They can’t mutate without synchronizations.
• Easy to make correct concurrent programs• Compared with normal Array, Hash, … they should
require special synchronization protocol to accessShareable objects(4) Isolated Proc
• Normal Proc can point to mutable objects
with outer local variable (free-variables)a = []; Proc.new{p a}.call• Introduce Isolated Proc (made by
Proc#isolate) which is prohibited to accessouter variables
a = []; Proc.new{p a}.isolate.call#=> RuntimeError (can’t access a)

Shareable objects(4) Isolated Proc
# Initial block for Guild is isolated proc
g1 = Guild.new do
expr1 # Make isolated block and invoke
end
g2 = Guild.new do
p g1 #=> RuntimeError (can’t access “g1”)#because block is isolated
end

FYI: Other languages using similar ideas• Similar to Guild• Racket: Place (imm. or special mut. values)• Kotlin/Native: Worker (check ownership)• Almost isolated• Shell script: Process (copy byte stream)• JavaScript: Worker• Everything immutable• Erlang, Elxir: Process

Inter-Guild communication API• Actor model, send/receive semantics• Not fixed yet (discuss later)• Destination addresses are represented by
Guild itself like Erlang/Elixir processes• Sending shareable objects means sending
only references to the objects (lightweight)• Two methods to send non-shareable objects• (1) COPY
• (2) MOVE

Sending objects between Guilds
g1 = Guild.new do # create Isolated Proc
n = Guild.receiver = fib(n)Guild.parent << r
end
g1 << 30 # or g1.send(30)p Guild.receive #=> 1346269

Sending shareable objects
g2 << o1

Guild1: g1
o1
o2o3
O2:Data

O3:Datao1 =Guild.receive

Guild2: g2

Sending non-shareable objects(1) Send by Copy
g2 << o1

o1 = Guild.receive

Guild2

Guild1o1channelo2
O2:Data

o1
o2

o3

o3
O2:Data

O3:Data

COPY

O3:DataSending non-shareable objects(2) Send by Moveg2.move(o1)o1 =Guild.receive

Guild1

Guild2o1channelo2
O2:Datao3
O3:DataMOVE

Sending non-shareable objects(2) Send by Moveg2.move(o1)o1 = Guild.receive

Guild1

Guild2-o1channel

-

o2
-

o3
O2:Data

From Guild1 perspective,
sent objects are invalidated

MOVE

O3:DataSending non-shareable objects(2) Send by Move
• If we don’t access sent objects after
sending them (and there are many suchcases), we can send them faster• Examples• Huge string data
• I/O objects (send request I/O to workers)

Summary of sharable/non-sharable objects
with copy/move operations• Non-sharable objects• Normal mutable objects (like String, Array, …)• Only one Guild can access such objects == membership• We can send them by COPY or MOVE

• Shareable objects• Several types of shareable objects• They requires special synchronization protocol to mutate them
• We can share them between Guilds by sending references

Mutable objs are NOT shared accidentally as Thread→ Safe concurrent programming

Discussion:
How to represent communication channel?
• Actor model• Destination is specified by a Guild• guild << obj• Erlang/Elixir, …

• CSP model• Destination is specified by a channel• ch << obj• Go, JavaScript, Kotolin/native, Racket, …

• They have advantages and disadvantages…

Retrieve multiple channels• Sometimes we need to manipulate withmultiple channel• Data channel and control channel• Monitoring channel for child Guilds• How to provide APIs to support it?

Go language goroutine and channels# https://tour.golang.org/concurrency/5
select {case c <- x:x, y = y, x+ycase <-quit:
fmt.Println("quit")
return}Erlang/Elixir Process# https://elixir-lang.org/getting-started/processes.html

iex> receive do...>{:hello, msg} -> msg...>{:world, msg} -> "won't match"...> endJavaScript Worker and MessageChannel// https://developer.mozilla.org/en-US/docs/Web/API/MessageChannel
var channel = new MessageChannel();var output = document.querySelector('.output');
var iframe = document.querySelector('iframe');// Wait for the iframe to load
iframe.addEventListener("load", onLoad);function onLoad() {// Listen for messages on port1
channel.port1.onmessage = onMessage;// Transfer port2 to the iframe
iframe.contentWindow.postMessage('Hello from the main page!', '*', [channel.port2]);}// Handle messages received on port1function onMessage(e) {output.innerHTML = e.data;}

Racket place; https://docs.racket-lang.org/reference/sync.html#%28def._%28%28quote._~23~25kernel%29._handle-evt%29%29> (define msg-ch (make-channel))> (define exit-ch (make-channel))> (thread(λ ()(let loop ([val 0])(printf "val = ~a~n" val)
(sync (handle-evt
msg-ch(λ (val) (loop val)))(handle-evt
exit-ch(λ (val) (displayln val)))))))

Multiple channels for Actor model• Support “Tag” (shows channel)• guild.send_to(:data, obj)
• guild.send(obj) send to thedefault tag• Receive with multiple tag• Guild.receive(tag1, tag2,…){|tag, obj| …}

g2 = Guild.new{cont = true
while cont
Guild.receive(:data, :ctrl){|tag, obj|
case tagwhen :datacalc(obj)
when :ctrl
case obj
when :exit
cont = false
else
raise "unknown"
end
end
}
end
}

Multiple channels for CSP model
g2 = Guild.new(data_ch, cntl_c){|d_ch, c_ch|
cont = true
• Making channels explicitly while cont# wait for multiple channel
Guild::Channel.receive(d_ch, c_ch){|ch, obj|
• Send to a channelcase ch• ch << obj
when d_chcalc(obj)• Receive with multiple
when c_chchannelscase obj
when :exit• Guild::Channel.receive(cont = false
ch1, ch2, …){|ch, obj|
else…}raise "unknown ctrl: #{obj}"
end
end
}
end
}

GuildImplementation
Preliminary implementation includes many bugs, performance issues.
https://github.com/ko1/ruby/tree/guild

Guild context• Before Guild• VM -> *Threads -> *Fibers• After Guild• VM -> *Guilds -> *Threads -> *Fibers• Introduce rb_guild_t.

Introduce synchronizations• Before Guild• Multiple threads cannot run simultaneously• After Guild• Run (native) threads in parallel• Need to introduce many synchronizations• Introduce VM-wide locks for VM-wide resources• It is the multi-thread programming!!

Garbage collection• Stop all Guilds (threads) at GC process
G1:T1

G2:T2
G3:T3

GC process
Pause
requestRestartrequestImplementation is not completed• Features• Fix GC bug• Prohibit sharing non-sharable objects• Introduce synchronizations to protect VM-wide
resources (process-global)• Introduce “sharable” object protocols• Performance• Reduce synchronizations• Per Guild Garbage collection• Introduce new “C API” to reduce TLS accessFuture optimizations• Koichi Sasada, et.al. : An
Implementation of Parallel
Threads for YARV: Yet Another
RubyVM (2007)• They introduced several
optimization techniques to reduce
synchronizations

Naming of “Guild”

Why “Guild”?
• Prefix should be different from “P”(Process), “T” (Therad) and “F” (Fiber).
• Ownership can be explained with the word
“Membership”.
• All (normal) objects belong to one Guild.
• Easy to explain “Move” semantics

Any problem?
• “Move” operation is not so popular operation(most of case “copy” is enough)• No other languages use this terminology• Naming is important• Just now “Guild” is a code name of thisprojectDemonstrations
on the current PoW implementation.

Demonstration (on 40 vCPUs)• CPU 40 virtual CPUs (2 x 10 x 2)
• Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz• x10 cores• x2 hyper threading• x2 CPUs• Ubuntu 16.10• Already EOL 

Demonstration (on 40 vCPUs)• Workload• Calculate fib(23) x 100_000 times• Serial version: 100_000.times{ fib(23) }• Guild version:
main
Guild

FibHubGuildload balancing

fibworkerfib
workerfib…
worker

We can change# of workers

https://gist.github.com/ko1/e5327126a77e078a0ffdf005013592ea
FIBHUB = make_worker_hub do |n|while true[n, fib(n)]cmd, sender_guild, data = *Guild.receiveendcase cmd# librarywhen :req# Receive a request from masterif g = guilds.pop# Send a taskg << data# if an idle worker is available

def make_worker_hub n_workers = WN, &worker_proc
pp WN: n_workers if $VERBOSE

else
Guild.new(n_workers, worker_proc) do |nw, wp|
guilds = nw.times.map do
Guild.new dorequests << dataend

# Make worker guilds# Receive an answers from workers
Guild.parent << data # Send an answers to master

when :ans

while data = Guild.receive
result = wp.call(data)

if req = requests.pop

Guild.parent << [:ans, Guild.current, result]sender_guild << req

end

else

end

# Send a remaining task
# to the worker if exists

guilds << sender_guild

end

end

requests = []

end
end

# You don’t need to write such common code
# but we provide some kind of a framework
end

end

fib(23) with # of Guilds on 40 vCPUs
20
15

10
5
0
0

20

40

60

80

# of Guilds
Speedup ratio (compare with serial execution)100

Demonstration (on 40 vCPUs)• Workload• Calculate fib(n) x 100_000 times (0 ≦n≦30)• Serial version: 100_000.times{ fib(23) }• Guild version: 40 Guilds
main
Guild

FibHubGuildload balancing

fibworkerfib
workerfib…
workerExecution time (sec) of fib(n) x 100_000
with 40 Guilds on 40 vCPUs
12,896.23 sec=~ 3.5 hours

15000

sec

10000
5000
791.2541 sec=~ 13 minutes

0
0

5

10

15

20

n for fib(n)real (sec)real-serial (sec)

25

30

35

with serial execution

Speedup ratio compare

fib(n) with 40 Guilds on 40 vCPUs
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

fib(9): about 100 recursive calls

Slower0

5

Faster10

15

20

n for fib(n)

25

30

35

Demonstration (on 40 virtual CPU)
• Workload• Calculate wordcount for files and find a filewhich contains maximum number of words.
• on “ruby/test/**/*” files (1,108 files)
def word_count filer = File.read(file).b.upcase.split(/¥W/).uniq.size
endDemonstration (on 40 virtual CPU)
• Workload• Calculate wordcount for files and find a filewhich contains maximum number of words.
• on “ruby/test/**/*” files (1,108 files)
main
Guild

WCHub
Guild

traverse directories,
correct wc results,
and calculate maximum

load balancing

wc
workerwc
workerwc…
worker

We can change# of workers

10

6.136364(sec)

Execution time

Demonstration (on 40 virtual CPU)5
1.736429

1.652815

Serial1 Guold

2.473468

0
2 Guild

40 Guilds

It is SLOW with multiple Guilds
because GC/object allocation require naïve global locking(current implementation limitation) and huge contentions.

Today’s talk
• Ruby 2.6 updates of mine
• Introduction of Guild• Design• Discussion• Implementation• Preliminary demonstration

Thank you for your attention

Parallel programmingin Ruby3
with Guild
Koichi Sasada
Cookpad Inc.
<ko1@cookpad.com>

Pros./Cons. Matrix
Process

Guild

ThreadAuto-Fiber

Fiber

Available

Yes

No

Yes

No

Yes

Switch on
time

Yes

Yes

Yes

No

No

Switch on I/O

Auto

Auto

Auto

Auto

No

Next target

Auto

Auto

Auto

Auto

Specify

Parallel run

Yes

Yes

No (on MRI)

No

No

Shared data

N/A

(mostly) N/A

Everything

Everything

Everything

Comm.

Hard

Maybe Easy

Easy

Easy

Easy

Programming
difficulty

Hard

Easy

Difficult

Easy

Easy

Debuggingdifficulty

Easy?

Maybe Easy

Hard

Maybe hard

Easy