Concurrency safety guarantees in Rust - Time & Space Complexity

Time Complexity: Concurrency safety guarantees

O(n)

Understanding Time Complexity

When working with concurrency in Rust, it is important to understand how safety checks affect performance.

We want to see how the program's running time changes as we use concurrency features safely.

Scenario Under Consideration

Analyze the time complexity of the following Rust code using concurrency safety features.

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut handles = vec![];
    let n = 100usize;

    for _ in 0..n {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = counter.lock().unwrap();
            *num += 1;
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }
}
    

This code creates n threads, each safely incrementing a shared counter using a mutex.

Identify Repeating Operations

Look for loops and repeated actions that affect time.

• Primary operation: Spawning and joining n threads, each locking and unlocking the mutex once.
• How many times: Exactly n times, once per thread.

How Execution Grows With Input

As n grows, the number of threads and mutex locks grows linearly.

Input Size (n)	Approx. Operations
10	About 10 thread spawns and 10 mutex locks
100	About 100 thread spawns and 100 mutex locks
1000	About 1000 thread spawns and 1000 mutex locks

Pattern observation: The work grows directly with the number of threads created.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line as you add more threads.

Common Mistake

[X] Wrong: "Using a mutex makes the program run in constant time regardless of threads."

[OK] Correct: Each thread must wait to lock the mutex, so time grows with the number of threads.

Interview Connect

Understanding how concurrency safety affects performance shows you can write code that is both safe and efficient.

Self-Check

"What if we replaced the mutex with an atomic type? How would the time complexity change?"

Practice

1. Which Rust type is used to safely share ownership of data across multiple threads?

easy

A. Rc

B. Box

C. Arc

D. RefCell

Solution

1. Step 1: Understand ownership sharing in concurrency

   In Rust, Arc (Atomic Reference Counted) allows multiple threads to share ownership safely.

2. Step 2: Compare other options

   Box is for single ownership, Rc is not thread-safe, and RefCell is for interior mutability but not thread-safe.

3. Final Answer:

   Arc -> Option C

4. Quick Check:

   Safe shared ownership across threads = Arc [OK]

Hint: Arc is for thread-safe shared ownership [OK]

Common Mistakes:

• Confusing Rc with Arc for multithreading
• Using Box for shared ownership
• Thinking RefCell is thread-safe

2. Which of the following is the correct syntax to create a Mutex protecting an integer value 5?

easy

A. let m = Mutex::new(5);

B. let m = Mutex(5);

C. let m = new Mutex(5);

D. let m = Mutex::create(5);

Solution

1. Step 1: Recall Mutex creation syntax

   In Rust, you create a Mutex by calling Mutex::new(value).

2. Step 2: Check each option

   Only let m = Mutex::new(5); uses the correct Mutex::new(5) syntax; others are invalid.

3. Final Answer:

   let m = Mutex::new(5); -> Option A

4. Quick Check:

   Mutex creation uses Mutex::new() [OK]

Hint: Use Mutex::new(value) to create a Mutex [OK]

Common Mistakes:

• Omitting ::new when creating Mutex
• Using constructor syntax like Mutex(5)
• Confusing new() with create()

3. What will the following Rust code print?

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut handles = vec![];

    for _ in 0..3 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = counter.lock().unwrap();
            *num += 1;
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("{}", *counter.lock().unwrap());
}

medium

A. 0

B. 3

C. Compilation error

D. 1

Solution

1. Step 1: Understand the code's concurrency logic

   The code creates 3 threads, each increments the shared counter by 1 inside a Mutex lock.

2. Step 2: Calculate the final counter value

   Each thread adds 1, so total increments = 3. The final print shows 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   3 threads incrementing counter = 3 [OK]

Hint: Count threads incrementing inside Mutex lock [OK]

Common Mistakes:

• Ignoring Mutex lock and thinking of race conditions
• Assuming only one thread runs
• Expecting compilation error due to Arc usage

4. Identify the error in this Rust code snippet that tries to share a vector across threads:

use std::sync::Arc;
use std::thread;

fn main() {
    let numbers = vec![1, 2, 3];
    let shared_numbers = Arc::new(numbers);

    let handle = thread::spawn(move || {
        shared_numbers.push(4);
    });

    handle.join().unwrap();
}

medium

A. Vector is not thread-safe without Mutex or RwLock

B. Arc does not implement Send for Vec<T>

C. Cannot move vector into Arc

D. Missing clone of Arc before move

Solution

1. Step 1: Examine the thread code

   The thread attempts to mutate the shared Arc<Vec<i32>> by calling push, but Arc provides only shared immutable access.

2. Step 2: Recall requirements for mutable shared data

   To mutate data shared across threads, wrap it in Mutex or RwLock inside the Arc, e.g., Arc<Mutex<Vec<i32>>>.

3. Step 3: Eliminate other options

   A: Vec can be moved into Arc. B: Arc<Vec<T>> implements Send/Sync for T: Sync. D: Clone not needed for single-thread move.

4. Final Answer:

   Vector is not thread-safe without Mutex or RwLock -> Option A

5. Quick Check:

   Mutable shared data needs Mutex or RwLock [OK]

Hint: Mutable shared data needs Mutex or RwLock [OK]

Common Mistakes:

• Thinking Arc alone makes data mutable and safe
• Confusing Send trait errors
• Assuming clone is needed before move

5. You want to safely share and mutate a HashMap across multiple threads in Rust. Which combination of types ensures concurrency safety and allows mutation?

hard

A. Arc<RefCell<HashMap<String, i32>>>

B. Mutex<HashMap<String, i32>>

C. Rc<RefCell<HashMap<String, i32>>>

D. Arc<RwLock<HashMap<String, i32>>>

Solution

1. Step 1: Identify thread-safe shared ownership

   To share data across threads, Arc is needed for atomic reference counting.

2. Step 2: Choose synchronization primitive for mutation

   For mutable access, Mutex or RwLock can be used. RwLock allows multiple readers or one writer, improving concurrency.

3. Step 3: Evaluate options

   Arc<RefCell<HashMap<String, i32>>> uses RefCell which is not Sync and thus not thread-safe. Arc<RwLock<HashMap<String, i32>>> uses RwLock which is suitable for read-heavy workloads with mutations. Rc<RefCell<HashMap<String, i32>>> uses Rc and RefCell, which are not thread-safe. Mutex<HashMap<String, i32>> lacks Arc, so no shared ownership across threads.

4. Final Answer:

   Arc<RwLock<HashMap<String, i32>>> -> Option D

5. Quick Check:

   Arc + RwLock = safe shared mutable access [OK]

Hint: Use Arc with RwLock for shared mutable access [OK]

Common Mistakes:

• Using Rc or RefCell for multithreading
• Omitting Arc for shared ownership
• Choosing Mutex over RwLock without reason