Shared state overview in Rust - Time & Space Complexity

Time Complexity: Shared state overview

O(n)

Understanding Time Complexity

When programs share data between parts, it affects how long tasks take.

We want to see how the time to run changes as more parts share and access the data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

    for _ in 0..10 {
        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!("Result: {}", *counter.lock().unwrap());
}

This code creates 10 threads that share and update a single counter safely using a lock.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop creating 10 threads, each locking and updating shared data once.
• How many times: 10 times, once per thread.

How Execution Grows With Input

As the number of threads increases, the program does more locking and updating steps.

Input Size (n)	Approx. Operations
10	About 10 lock and update steps
100	About 100 lock and update steps
1000	About 1000 lock and update steps

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

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line as more threads share and update the state.

Common Mistake

[X] Wrong: "Adding more threads won't affect time much because they run at the same time."

[OK] Correct: Even if threads run together, they must wait to lock the shared data, so more threads mean more waiting and longer total time.

Interview Connect

Understanding how shared data affects time helps you write safe and efficient programs that work well when many parts run together.

Self-Check

"What if we replaced the Mutex with a lock-free atomic counter? How would the time complexity change?"

Practice

1. What is the main purpose of using Arc in Rust when working with shared state?

easy

A. To copy data between threads

B. To allow multiple ownership of the same data safely across threads

C. To create a mutable reference to data

D. To lock data so only one thread can access it at a time

Solution

1. Step 1: Understand what Arc does

   Arc stands for Atomic Reference Counting. It allows multiple parts of a program to own the same data safely, especially across threads.

2. Step 2: Differentiate from locking mechanisms

   Mutex is used to lock data for safe access, but Arc is about shared ownership, not locking.

3. Final Answer:

   To allow multiple ownership of the same data safely across threads -> Option B

4. Quick Check:

   Arc = shared ownership [OK]

Hint: Arc shares ownership safely across threads [OK]

Common Mistakes:

• Confusing Arc with Mutex
• Thinking Arc locks data
• Assuming Arc copies data

2. Which of the following is the correct way to create a thread-safe shared integer using Arc and Mutex in Rust?

easy

A. let data = Mutex::new(Arc::new(5));

B. let data = Mutex::new(5);

C. let data = Arc::new(5);

D. let data = Arc::new(Mutex::new(5));

Solution

1. Step 1: Understand the order of wrapping

   To share mutable data safely, wrap the data in a Mutex first, then wrap that in an Arc for shared ownership.

2. Step 2: Check each option

   let data = Arc::new(Mutex::new(5)); correctly wraps 5 in a Mutex, then in an Arc. let data = Mutex::new(Arc::new(5)); reverses the order, which is incorrect. Options C and D miss one of the wrappers.

3. Final Answer:

   let data = Arc::new(Mutex::new(5)); -> Option D

4. Quick Check:

   Arc wraps Mutex for shared mutable data [OK]

Hint: Wrap data in Mutex, then Arc for shared mutable state [OK]

Common Mistakes:

• Reversing Arc and Mutex order
• Missing Mutex for mutability
• Using Arc without Mutex for mutable data

3. What will be the output of the following Rust code snippet?

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. 3

B. 0

C. 1

D. Compilation error

Solution

1. Step 1: Understand the shared counter

   The counter is wrapped in Arc and Mutex, allowing safe shared mutable access across threads.

2. Step 2: Analyze thread increments

   Three threads each lock the mutex, increment the counter by 1, then unlock. After all threads join, the counter should be 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 threads increment counter once each = 3 [OK]

Hint: Count increments by threads, sum equals output [OK]

Common Mistakes:

• Forgetting to clone Arc for each thread
• Ignoring Mutex lock for safe access
• Assuming race conditions cause wrong output

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

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

fn main() {
    let data = Arc::new(Mutex::new(vec![1, 2, 3]));
    let data2 = data.clone();

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

    handle.join().unwrap();
    println!("{:?}", data.lock().unwrap());
}

medium

A. No error, code runs and prints [1, 2, 3, 4]

B. Cannot clone Arc with .clone(), must use Arc::clone()

C. Mutex lock is missing unwrap()

D. Vector cannot be shared across threads

Solution

1. Step 1: Check Arc cloning

   Using data.clone() on an Arc is valid and clones the pointer safely.

2. Step 2: Verify Mutex locking and thread usage

   The mutex is locked with unwrap(), vector is safely mutated inside the thread, and join waits for thread completion.

3. Final Answer:

   No error, code runs and prints [1, 2, 3, 4] -> Option A

4. Quick Check:

   Arc clone and Mutex lock correct [OK]

Hint: Arc clone works with .clone(), Mutex lock unwrap needed [OK]

Common Mistakes:

• Thinking Arc::clone() is mandatory
• Forgetting to unwrap Mutex lock
• Believing vectors can't be shared across threads

5. You want to safely share a counter between multiple threads and increment it only if the current value is even. Which approach correctly uses Arc and Mutex to achieve this?

hard

A. Use Arc<i32> only, clone Arc for each thread, increment directly

B. Use Mutex<Arc<i32>>, clone Mutex for each thread, increment without locking

C. Wrap the counter in Arc<Mutex<i32>>, clone Arc for each thread, lock mutex, check if even, then increment

D. Use Mutex<i32> only, share by cloning Mutex, increment without Arc

Solution

1. Step 1: Understand shared mutable state needs

   To share and mutate data safely across threads, use Arc for shared ownership and Mutex for safe mutable access.

2. Step 2: Analyze each option

   Wrap the counter in Arc<Mutex<i32>>, clone Arc for each thread, lock mutex, check if even, then increment correctly wraps the counter in Arc<Mutex<i32>>, clones Arc for threads, locks mutex before checking and incrementing. Other options misuse order or omit locking.

3. Final Answer:

   Wrap the counter in Arc<Mutex<i32>>, clone Arc for each thread, lock mutex, check if even, then increment -> Option C

4. Quick Check:

   Arc + Mutex + lock for safe conditional increment [OK]

Hint: Arc for sharing, Mutex for locking before mutate [OK]

Common Mistakes:

• Not locking mutex before mutate
• Using Arc without Mutex for mutability
• Cloning Mutex instead of Arc