Fiber in the10th year
Koichi Sasada
ko1@cookpad.com

About this talk
•Behavior of Fiber•History of Fiber•Implementation of Fiber
•Auto Fiber proposal

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

FiberUser-defined context switching

Fiber example
Infinite generator
fib = Fiber.new do
Fiber.yield a = b = 1
loop{ a, b = b, a+b
Fiber.yield a }end10.times{ p fib.resume }Fiber example
Infinite generator
fib = Fiber.new do
2. Resume Fiber
Fiber.yield a = b = 1
loop{ a, b = b, a+b
4. Resume fiber(again)1. Fiber creation
Fiber.yield a }5. Return to the
6. Resume fiber
Return to theend 3.parent
parent fiber(again2)fiber
10.times{ p fib.resume }Fiber example
Infinite generator
fib = Fiber.new do
2. Resume Fiber
Fiber.yield a = b = 1
loop{ a, b = b, a+b
4. Resume fiber(again)1. Fiber creation
Fiber.yield a }5. Return to the
6. Resume fiber
Return to theend 3.parent
parent fiber(again2)
fiber
10.times{ p fib.resume }Not a Proc?
a = 0; b = 1
fib = Proc.new{a, b = b, a+ba}
p fib.call #=> 1
p fib.call #=> 1
p fib.call #=> 2
p fib.call #=> 3
p fib.call #=> 5

Proc can’t restart fromthe middle of blockProc (method) v.s. Fiber
Start
Parameters
ReturnSuspend
Continue

Proc (method)
OK: callFiber
OK: Fiber#resume

OK: block (method) parameters OK: block parameters
OK: exit Proc/method

OK: exit Proc/method

NG: N/A

OK: Fiber.yield

NG: N/A

OK: Fiber#resume

Fiber example
Inner iterator to external iterator
f1 = Fiber.new do
2.times{|i| Fiber.yield i}
end
p f1.resume #=> 0
p f1.resume #=> 1
p f1.resume #=> 2 # return value of #times
p f1.resume #=> dead fiber called(FiberError)

Fiber example
Inner iterator to external iterator
etc_passwd_ex_iter = Fiber.new doopen('/etc/passwd').each_line{|line|
Fiber.yield line}end
p etc_passwd_ex_iter.resume #=> 1st line
p etc_passwd_ex_iter.resume #=> 2nd line…

Fiber example
Inner iterator to external iterator# make Enumerator
iter = open('/etc/passwd').each_line# Enumerator#next use Fiber implicitly
p iter.next #=> 1st line
p iter.next #=> 2nd line…

Fiber example
Agent simulation
characters << Fiber.new{loop{cat.move_up; Fiber.yield}}characters << Fiber.new{loop{dog.move_left; Fiber.yield}}…
loop{cs.each{|e| e.resume}; redraw}

Fiber example
Agent simulation
characters << Fiber.new{# you can specify complex rule for chars
loop{
cow.move_up;
Fiber.yield
cow.move_right; Fiber.yield
cow.move_down; Fiber.yield
cow.move_left; Fiber.yield}}

Fiber example
Non-blocking IO scheduler

Wait multiple IO ops withtraditional “select” ormodern “poll”, “epoll” interface

Not a Thread?
ThreadSuspend/continue
Yes
Switch on timer
Yes
Switch on I/O blocking Yes
Synchronization
RequiredSpecify next context
No
Performance: Creation Heavy
Performance: Switch Lightweight

FiberYes
No (explicit switch)
No (explicit switch)
Not required
YesLightweight
Heavy (initial version)
Lightweight (now)Brief History of Fibers

Fiber: Brief history•2007/05/23 cont.c (for callcc)•2007/05/25 Fiber impl. [ruby-dev:30827]•2007/05/28 Fiber introduced into cont.c•2007/08/25 Fix Fiber spec

Background: Callcc and Fiber on Ruby 1.9• 2007/01 YARV was merged without “callcc”• Biggest usage of “callcc” is for “Generator”• Convert an internal iterator to an external iterator• Usually one-shot continuation is required→ Coroutine is enough for this purpose• Capturing continuation (callcc) is heavy operation• Implementation is easy because we can refer Ruby 1.8 user-levelthreads• 2007/05/?? I was introduced one paper something like generator
for (maybe) C# (so I began to consider about this feature)• And I have a spare time at academic conference2007/05/22 IRC log(seeing a blog post)
00:56:49 <ko1> うーむ，callcc 欲しいっすか
English: Umm, do you want “callcc”?

2007/05/23 cont.c

2007/05/23 IRC log(nobu pointed out there are several bugs on callcc)
12:15:36 <ko1> callcc 禁止でいいよ
EN: callcc should be prohibited
12:15:52 <ko1> これ作りながら，Fiber作ったほうが速いなーとか思って亜
EN: Building callcc, I’m thinking that making Fiberis more straightforward.

Fiber naming• The name “Fiber” is from Windows API• “A fiber is a unit of execution that must be manuallyscheduled by the application. Fibers run in the context
of the threads that schedule them. Each thread canschedule multiple fibers. In general, fibers do notprovide advantages over a well-designed
multithreaded application. However, using fibers canmake it easier to port applications that were designed
to schedule their own threads.”
https://msdn.microsoft.com/jajp/library/windows/desktop/ms682661(v=vs.85).aspx

[ruby-dev:30828] Re: Supporting Fiber
Naming of Fiber“Fiberでいいんじゃないでしょうか。
何かかっこいいですよね。” by shugo
EN: “I’m ok the name of “Fiber”.
Somewhat cool.” by shugo

2007/05/28 Introduction
r13295, [ruby-dev:30827]

First Fiber is Coroutine
Fiber#pass
f1 = Fiber.new{f2.pass; f2.pass}f2 = Fiber.new{f3.pass}f3 = Fiber.new{
f1.pass}
f1.pass

No parents/children
All routines are equivalent
Co-operative routines= Coroutine

NOTE: renamed to “Fiber#transfer” nowFiber#pass → Fiber#yield[ruby-dev:30847] Re: Supporting Fiber

Matz’s idea

Coroutine or Semi-coroutine• Coroutine is difficult• You need to manage all transitions of Fibers• Remember that most of languages have only “routine”(not “co-”) and it is easy to use.
• Most of case, semi-coroutine is easy and enough• Exception handling• On semi-croutine, exceptions are raised to the parent
Fiber(s)• Maybe it has critical BUG issue.

• Coroutine is powerful• No limitation (a bit old-language constructs)

[ruby-dev:31583] Fiber reviesed
Semi-coroutine (Fiber) and Coroutine (Fiber::Core)

2007/08/25 IRC log10:26:49 <ko1> 大クラス主義ならFiber に Semi も Coroutine
も機能いっしょくたにするべきかなあ
EN: Semi- and non-semi Coroutine may bein one class undr big class principle
10:32:15 <ko1> というわけで，いっしょくたにしてみる
EN: So that I merged it.
* It was just idea in two lines…

Fiber::Core was removed

Commit message does not work well…

Final specification of Fiber• Semi-coroutine• Fiber#resume and Fiber.yield• Make parent and child relationship (tree)• Prohibit double resume• Coroutine• Fiber#transfer• Prohibt to call semi-coroutine methods
on “transfer”ed fiber (coroutine)

fib1(parent)

NG!!

resumedouble resume
is prohibited

fib2(child/parent)

resumefib3(child)Implementation of Fibers

Implementation history(1) 2007/05 Copy all machine stack(2) 2010/05 FIBER_USE_NATIVE(3) 2017/09 Switch only pointerFiber context representation•Context:• Thread states (current program counter, etc)
• VM stack• Machine stack•“Context switching” means exchange
contexts

Fiber implementation2007 (1) Copy machine stack•Store and restore “Context” by copyingmachine stack
StoreSwitch fromrunning fib1 tosuspended fib2

machinestack of fib1

machinestack area
Restoremachinestack of fib2

Fiber implementation2007 (1) Copy machine stack•Good• Same idea of a Ruby 1.8
user-level thread code
• Not so many memory usage• Almost portable•Bad• Copy time is relative tostack-depth (O(N))

Storemachine
stack of fib1

machinestack area
Restoremachinestack of fib2

Fiber implementation2010 (2) Use Native support•Switch machine stack by system APIs
• Supported APIs
• POSIX makecontext/setcontext• Win32 Fiber API• Machine stack exchange is only pointerexchange (O(1))•Implemented by Mr. Shiba (with me)

Time ratio

Count of recursive call (== stack depth)“A Fast Fiber Implementation for Ruby 1.9”
“Ruby1.9での高速なFiberの実装”,
第51回プログラミング・シンポジウム予稿集, pp.21--28 (2010).

Fiber implementation2017 (3) More lightweight switching•Context exchange• [copy] Thread states• [ptr exchange] VM stack• [ptr exchange] Machine stack•“setcontext” calls sigprocmask• Ruby threads/fibers use same signal mask
→ Useless system call

Fiber implementation2017 (3) More lightweight switching•Context exchange• [copy->ptr exchange] Thread statesStore

fib1

fib1
ec1

fib1
context

fib1
fib2
context

ptr exchange

ThreadThreadRestoreBefore

fib2

fib2

fib2
contextec2
AfterFiber implementation2017 (3) More lightweight switching•[Futurework] Use custom “setcontext” excludes
sigprocmask• setcontext issues “sigprocmask” system call to restore
signal mask, but MRI doesn’t change signalmask sothat it is completely useless.
• This idea is also proposed athttps://rethinkdb.com/blog/making-coroutines-fast/• License?

Fiber implementation2017 (3) More lightweight switching•PerformanceSec

vm2_fiber_switch*
2.4
2.35
2.3
2.25
2.2
2.15
Ruby 2.4.1

ModifiedFiber implementation2017 (3) More lightweight switching•Performance
vm2_fiber_switch*

Sec3

2.36

2.25

Ruby 2.4.1

Modified210

5%
improvement!

Fiber implementation2017 (3) More lightweight switching•Memory size / fiber

Bytes

sizeof(rb_fiber_t)
2500
2000
1500
1000
500
02264
1616

Ruby 2.4.1

Modified

30% reduced!

Fiber implementation2017 (3) More lightweight switching

Bytes•Memory size / fiber
700,000
600,000
500,000
400,000
300,000
200,000
100,000
0524,288

524,288

131,072
2,264
Ruby 2.4.1

131,072
1,616
Modifiedsizeof(rb_fiber_t)

VM stack

Machine stack2017 (3) More lightweight switching
Not a valuable work?
•I spent this hack 2 or 3 months because ofcode complicity.
•This work (hopefully) will be a basis of Guildwork (we need to pass context informationfor each APIs like mrb_state on mruby)Auto-Fiber proposal

Auto Fiber proposal•“Fiber” enables writing scheduler by Ruby
programmer• Maybe Seki-san introduce one example•Why doesn’t an interpreter support it
natively? → Auto Fiber proposal

Auto Fiber proposal
https://bugs.ruby-lang.org/issues/13618

Auto Fiber proposal
Automatic schedule on I/O blocking• Support Fiber scheduler
natively• Don’t need to returnscheduler• Switch Fibers on all blocking
I/O (and other ops)
• No need to change existing
programs

Comparison
Suspend/continue
Switch on timer
Switch on I/O b.
Synchronization
Specify next
Performance: Creation
Performance: Switch

Thread
Yes

Fiber
Yes

Auto Fiber
Yes

Yes
Yes
RequiredNo
HeavyLightweightNoNo
Not required
YesLightweightLightweight

NoYes
RequiredNo
LightweightLightweightAdvantage and Disadvantage•Advantage• Don’t need to modify existing programs• Lightweight as a Fiber• Safer than Threads (no preemption)•Disadvantage• Introduce “non-deterministic” dangers same asThread programs• Non atomic operations can intercept accidentally.

Change the name…?

About this talk
•Behavior of Fiber•History of Fiber•Implementation of Fiber
•Auto Fiber proposal

Thank you for your attention
Koichi Sasada<ko1@cookpad.com>