Guild Prototype
Koichi Sasada
Cookpad Inc.
<ko1@cookpad.com>

RubyKaigi 2016 talkRubyKaigi 2016 talkTL;DR• We can run parallel programs with Guilds• Current implementation is too preliminaryand so buggy (easy to halt)→ “Thread programming” is too hardfor human beings.

Today’s talk
• Background of Guild• Demonstrations• Guild specifications (ideas)• Guild implementations (w/ future plan)• Synchronizations• Performance optimizations

Koichi Sasada
http://atdot.net/~ko1/• A programmer• 2006-2012 Faculty• 2012-2017 Heroku, Inc.
• 2017- Cookpad Inc.

• Job: MRI development• Core parts• VM, Threads, GC, etc

Recent 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).

Advertisement

Cookpad booth events【Day 2】
15:20~15:50 Global Office Hours【Day 3】
12:00~13:00 Q&A with @wyhaines
15:20~15:50 Ruby interpreter developme
live by @ko1 & @mame
Cookpad X RubyKaigi 2018: Day 2 Party⏰ June 1st, 19:30 - 21:30 (opens 19:00)
💰 Free (Registration required)Show up to this booth at 18:40 if you want to head with us!

Background ofGuildMotivation
Productivity (most important for Ruby)• Thread programming is too difficult• Making correct/safe concurrent programs easily
Performance by Parallel execution• Making parallel programs• Threads can make concurrent programs, but can’t run themin parallel on MRI (CRuby)• People want to utilize Multi/many CPU cores

RubyKaigi2016 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

Guilds, Threads and Fibers• Guild has at least one thread (and a thread has atleast one fiber)• Threads in different Guilds can run in parallel

GuildThread
Fiber
Fiber

ThreadFiber

Guild
GuildThread
FiberThreadFiber

Design “Shareable” and “non-sharable”• Non-shareable objects• (normal) Mutable objects (String, Array, …)• They are members of only one Guild• Using only 1 Guild, it compatible with Ruby 2

Guild 1NG!!
objobjobj

Can’t access(read/write)

Guild 2objobj

Demonstrations

Demonstration (on 40 vCPUs)• CPU 40 virtual CPUs (2 x 10 x 2)
• x 2 CPUs
• Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz• x10 cores• x2 hyper threading• 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
GuildFibHub
Guildload 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.receive

endcase 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
20151050020406080# 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

FibHub
Guildload 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

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

Order of fib(n) is “O(2^n)”with serial execution

Speedup ratio comparefib(n) with 40 Guilds on 40 vCPUs
18171615
1413121110
98765432
10fib(9): about 100 recursive calls

Slower0

5

Faster1015

20n 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

02 Guild

40 Guilds

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

GuildSpecification
Temporary one.

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

GuildThread
Fiber
Fiber

ThreadFiber

Guild
GuildThread
FiberThreadFiber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 GGLG1: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

normalmutableobj1

Shareable
obj1

Guild 2

Shareable
obj2

normalmutableobj2

Design “Shareable” and “non-sharable”• You can enjoy usual mutating
programming without any thread-safeconcerns.
• Because we can’t share mutable objects
between Guilds. They are “non-sharable”.
• In other words, you can’t make threadunsafe (data-racy) programs with Guilds.

Design “Shareable” and “non-sharable”• You need to use “Sharable” objects to shareobjects between Guilds• On concurrent programs, most of objects are
not shared (thread-local)• Tons of local objects and a few sharing objects• You only need to care about a few objects
non- nonnonsharable
non- nonsharable
nonsharable
non- nonsharable
non- sharable
sharablenonnon- non- nonsharable
sharablesharablenonsharable
non- sharable
sharablesharablenonsharablesharablesharablesharable

Design “Shareable” and “non-sharable”• Non-shareable objects• (normal) Mutable objects (String, Array, …)• They are member of only one Guild• Using only 1 Guild, it compatible with Ruby 2

Guild 1NG!!
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

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• Numeric objects, symbols, true, false, nil are immutable(from Ruby 2.0, 2.1, 2.2)
• Frozen string objects are immutable (if they don’t haveinstance variables)Shareable objects(2) Class/Module objects• All objects (including any sharable objects) pointto own classes• Good: Sharing class/module objects makes program
easier• Bad: They can point to other mutable objects withConstants, @@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 process 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 withouter local variable (free-variables)• a = []; Proc.new{p a}.call• Introduce Isolated Proc (made byProc#isolate) which is prohibited to accessouter variables
a = []; Proc.new{p a}.isolate.call#=> RuntimeError (can’t access a)• (there are more details but skip)

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Inter-Guild communication API• Actor model, send/receive semantics• 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 << rend
g1 << 30p 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 operation (send request I/O to workers)

Summary of object sharing/non-sharing• Shareable objects• Several types of shareable objects• We can share them between Guilds• They requires special synchronization protocol to mutate them

• 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

• Mutable objects are NOT shared accidentally as Threadprogramming → Correct concurrent Prog.

GuildImplementation
Preliminary implementation includes many bugs, performance issues.

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 so 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
PauserequestRestartrequest

Future work and optimizations• Features• Prohibit sharing non-sharable objects• Introduce synchronizations to protect VMwide 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 reducesynchronizations

One more thing…

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Today’s talk
• Background of Guild• Demonstrations• Guild specifications (ideas)• Guild implementations (w/ future plan)• Synchronizations• Performance optimizations

Thank you for your attention

Guild Prototype
Koichi Sasada
Cookpad Inc.
<ko1@cookpad.com>

Pros./Cons. Matrix
Process

GuildThread

Auto-Fiber

Fiber

Available

Yes

NoYes

No

Yes

Switch ontime

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)

NoNo

Shared data

N/A(mostly) N/A

Everything

Everything

Everything

Comm.

Hard

Maybe Easy

Easy

Easy

Easy

Programming
difficulty

HardEasy

Difficult

Easy

Easy

DebuggingdifficultyEasy?

Maybe Easy

Hard

Maybe hard

Easy