Fiber for cooperative concurrency in Ruby - Time & Space Complexity

Time Complexity: Fiber for cooperative concurrency

O(n)

Understanding Time Complexity

When using Fibers for cooperative concurrency, we want to understand how the program's running time changes as we switch between tasks.

We ask: How does the number of Fiber switches affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following Ruby code using Fibers.

fiber1 = Fiber.new do
  3.times do |i|
    puts "Fiber1: step #{i}"
    Fiber.yield
  end
end

fiber2 = Fiber.new do
  3.times do |i|
    puts "Fiber2: step #{i}"
    Fiber.yield
  end
end

while fiber1.alive? || fiber2.alive?
  fiber1.resume if fiber1.alive?
  fiber2.resume if fiber2.alive?
end

This code runs two Fibers that take turns running steps, yielding control back and forth.

Identify Repeating Operations

Look for loops and repeated Fiber switches.

• Primary operation: The loop that resumes each Fiber until both finish.
• How many times: Each Fiber runs 3 times, so total of 6 resumes and yields combined.

How Execution Grows With Input

Imagine increasing the number of steps each Fiber runs.

Input Size (steps per Fiber)	Approx. Operations (Fiber resumes)
10	20 (2 Fibers x 10 steps)
100	200 (2 Fibers x 100 steps)
1000	2000 (2 Fibers x 1000 steps)

Pattern observation: The total operations grow linearly with the number of steps per Fiber.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows directly in proportion to the number of steps each Fiber performs.

Common Mistake

[X] Wrong: "Using Fibers makes the program run faster automatically."

[OK] Correct: Fibers help organize work cooperatively but do not reduce the total amount of work done; they just switch tasks without parallel speedup.

Interview Connect

Understanding how Fibers manage work step-by-step helps you explain cooperative multitasking and its impact on program flow and performance.

Self-Check

What if we added more Fibers running concurrently? How would the time complexity change?

Practice

1. What is the main purpose of using Fiber in Ruby?

easy

A. To pause and resume tasks manually for cooperative multitasking

B. To create multiple threads that run in parallel automatically

C. To speed up code by running it on multiple CPU cores

D. To handle database connections asynchronously

Solution

1. Step 1: Understand Fiber's role

   Fibers allow manual pausing and resuming of code execution, enabling cooperative multitasking.

2. Step 2: Differentiate from threads

   Unlike threads, Fibers do not run in parallel automatically; they require explicit control.

3. Final Answer:

   To pause and resume tasks manually for cooperative multitasking -> Option A

4. Quick Check:

   Fiber = manual pause/resume [OK]

Hint: Fibers pause and resume tasks manually, not parallel threads [OK]

Common Mistakes:

• Confusing Fibers with threads or parallelism
• Thinking Fibers run automatically in background
• Assuming Fibers speed up CPU usage

2. Which of the following is the correct way to create a Fiber in Ruby?

easy

A. fiber = Fiber.start { puts 'Hello' }

B. fiber = Fiber.new { puts 'Hello' }

C. fiber = Fiber.create { puts 'Hello' }

D. fiber = Fiber.run { puts 'Hello' }

Solution

1. Step 1: Recall Fiber creation syntax

   Ruby uses Fiber.new with a block to create a new Fiber.

2. Step 2: Check other options

   Methods like create, start, or run do not exist for Fiber creation.

3. Final Answer:

   fiber = Fiber.new { puts 'Hello' } -> Option B

4. Quick Check:

   Fiber creation = Fiber.new [OK]

Hint: Use Fiber.new with a block to create a Fiber [OK]

Common Mistakes:

• Using non-existent Fiber methods like create or start
• Forgetting to pass a block to Fiber.new
• Confusing Fiber with Thread syntax

3. What will be the output of the following Ruby code?

fiber = Fiber.new do
  puts 'Step 1'
  Fiber.yield
  puts 'Step 2'
end

fiber.resume
puts 'Between'
fiber.resume

medium

A. Step 2
Between
Step 1

B. Step 1
Step 2
Between

C. Between
Step 1
Step 2

D. Step 1
Between
Step 2

Solution

1. Step 1: Trace first resume call

   Calling fiber.resume runs until Fiber.yield, printing 'Step 1'.

2. Step 2: Trace code after first resume

   After yield, control returns to main, printing 'Between'.

3. Step 3: Trace second resume call

   Second fiber.resume resumes after yield, printing 'Step 2'.

4. Final Answer:

   Step 1 Between Step 2 -> Option D

5. Quick Check:

   Fiber.yield pauses, resume continues [OK]

Hint: Fiber.yield pauses; resume continues after yield [OK]

Common Mistakes:

• Assuming all code runs at first resume
• Confusing order of prints around yield
• Thinking yield stops Fiber permanently

4. Identify the error in this Fiber usage:

fiber = Fiber.new do
  puts 'Start'
  Fiber.yield
  puts 'End'
end

fiber.yield
fiber.resume

medium

A. Calling Fiber.yield outside a Fiber block causes an error

B. Fiber.resume must be called before Fiber.yield

C. Fiber.new requires a parameter for yield count

D. Fiber cannot print inside its block

Solution

1. Step 1: Check where Fiber.yield is called

   The code calls fiber.yield outside the Fiber block, which is invalid.

2. Step 2: Understand Fiber.yield usage

   Fiber.yield is a class method to pause current Fiber, not an instance method on Fiber objects.

3. Final Answer:

   Calling Fiber.yield outside a Fiber block causes an error -> Option A

4. Quick Check:

   Fiber.yield only inside Fiber block [OK]

Hint: Fiber.yield is called inside Fiber block only [OK]

Common Mistakes:

• Calling fiber.yield instead of Fiber.yield
• Expecting Fiber.resume before yield call
• Thinking Fiber.new needs parameters for yield

5. Given two Fibers that alternate printing numbers, what is the output of this code?

fiber1 = Fiber.new do
  3.times do |i|
    puts "Fiber1: #{i}"
    Fiber.yield
  end
end

fiber2 = Fiber.new do
  3.times do |i|
    puts "Fiber2: #{i}"
    Fiber.yield
  end
end

while fiber1.alive? || fiber2.alive?
  fiber1.resume if fiber1.alive?
  fiber2.resume if fiber2.alive?
end

hard

A. Fiber2: 0
Fiber1: 0
Fiber2: 1
Fiber1: 1
Fiber2: 2
Fiber1: 2

B. Fiber1: 0
Fiber1: 1
Fiber1: 2
Fiber2: 0
Fiber2: 1
Fiber2: 2

C. Fiber1: 0
Fiber2: 0
Fiber1: 1
Fiber2: 1
Fiber1: 2
Fiber2: 2

D. Fiber1: 0
Fiber2: 0
Fiber2: 1
Fiber1: 1
Fiber1: 2
Fiber2: 2

Solution

1. Step 1: Understand Fiber alternation

   Each Fiber prints a number then yields, pausing itself.

2. Step 2: Trace the while loop

   The loop resumes fiber1 then fiber2 alternately while they are alive.

3. Step 3: Follow output order

   Output alternates: Fiber1:0, Fiber2:0, Fiber1:1, Fiber2:1, Fiber1:2, Fiber2:2.

4. Final Answer:

   Fiber1: 0 Fiber2: 0 Fiber1: 1 Fiber2: 1 Fiber1: 2 Fiber2: 2 -> Option C

5. Quick Check:

   Fibers alternate resume and yield [OK]

Hint: Fibers alternate resume and yield to interleave output [OK]

Common Mistakes:

• Assuming one Fiber runs completely before the other
• Mixing order of Fiber resumes
• Forgetting Fiber.yield pauses execution