December 29, 2023

Exploring Concurrency in Rust: Non-Blocking vs. Blocking Data structures

A non-blocking data structure is a kind of concurrent data structure that allows threads to access and modify it without requiring locks…

By Shobhit chaturvedi

3 min read

A non-blocking data structure is a kind of concurrent data structure that allows threads to access and modify it without requiring locks. This characteristic reduces the likelihood of thread contention and deadlocks, leading to better performance in multithreaded applications.

How They Are Useful:

  1. Performance Efficiency: Non-blocking data structures can provide higher throughput and better scalability compared to their blocking counterparts, especially in highly concurrent environments.
  2. Deadlock Avoidance: Since they don't use traditional locks, they avoid problems like deadlocks, which can be challenging to detect and resolve.
  3. Fault Tolerance: They can be more robust in certain scenarios, such as when a thread fails or is suspended while holding a lock in a blocking structure, which can cause the entire system to stall.

Use Cases and Applications:

  1. Real-time Systems: In systems where response time is critical, like in trading systems or gaming servers, non-blocking structures can ensure timely data processing.
  2. High-Performance Computing: They are useful in scientific computations and simulations that require concurrent data access and manipulation.
  3. Web Servers and Databases: Servers handling numerous concurrent requests can benefit from the efficiency of non-blocking data structures.

How They Work:

Non-blocking data structures typically use atomic operations, like compare-and-swap (CAS), to ensure that multiple threads can safely modify data concurrently. These atomic operations guarantee that the operation either succeeds completely or has no effect, thus maintaining data integrity.

Using Non-blocking Data Structures in Rust:

Rust, with its strong focus on safety and concurrency, provides excellent support for non-blocking data structures through its standard library and external crates.

  1. Standard Library Support: Rust's standard library includes atomic types like AtomicBool, AtomicIsize, AtomicUsize, etc., which can be used to build non-blocking structures.
  2. External Crates: There are crates like crossbeam that offer a range of non-blocking data structures like queues, deques, and stacks.
  3. Implementation: To use them, you would typically employ atomic operations and carefully manage memory through Rust's ownership and borrowing rules, ensuring that data races do not occur.
use std::sync::atomic::{AtomicUsize, Ordering};

let counter = AtomicUsize::new(0);

// Incrementing the counter safely in a concurrent environment
counter.fetch_add(1, Ordering::Relaxed);

In this example, fetch_add is an atomic operation that safely increments the counter even when accessed by multiple threads concurrently.

Rust's strict concurrency and safety guarantees make it an ideal language for implementing and using non-blocking data structures, ensuring both performance and safety in concurrent applications.

for more details on atomic rust :

std::sync::atomic - Rust Atomic types

Lets compare Non blocking and blocking data structures

Rust is renowned for its powerful concurrency features, offering both safety and performance. In this article, we explore two different approaches to synchronization in concurrent Rust programs: non-blocking and blocking. We implement these approaches in two functions, using_non_blocking and using_blocking, to increment a shared counter from multiple threads.

Our program uses a custom procedural macro #[auto_log] from the procedure_macro_crate. This macro automatically logs the entry and exit of the function along with the execution time, providing valuable insights into the performance of each approach. refere for more details about auto log and procedural macro https://medium.com/@learnwithshobhit/rust-develop-attribute-macro-procedural-macro-to-check-function-execution-time-for-benchmarking-4ec7401092d4

non blocking approach

In using_non_blocking, we use AtomicUsize and Arc (Atomic Reference Counted) for thread-safe manipulation and sharing of data. AtomicUsize is a type of atomic variable that supports lock-free, atomic operations. We spawn 100,000 threads, each incrementing the counter exactly once. The fetch_add function atomically increases the counter, ensuring thread safety without the need for murexes.

#[auto_log]
fn using_non_blocking() {
    let counter = Arc::new(AtomicUsize::new(0));
    let mut handles = vec![];

    for _ in 0..100000 {
        let counter_clone = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            counter_clone.fetch_add(1, Ordering::Relaxed);
        });
        handles.push(handle);
    }

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

    println!("Final value: {}", counter.load(Ordering::SeqCst));
}

Blocking Approach

In using_blocking, we use a Mutex to protect the counter. This is a classic example of a blocking approach where each thread must acquire a lock before incrementing the counter. The mutex ensures exclusive access to the counter, preventing data races but potentially leading to thread contention.

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

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

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

    println!("Final value: {}", final_count);
}
fn main() {
    using_non_blocking();
    using_blocking();
}

Performance Comparison

The output of the program is as follows:

Entering function: using_non_blocking
Final value: 100000
Exiting function: using_non_blocking (took 34738 ms)
Entering function: using_blocking
Final value: 100000
Exiting function: using_blocking (took 38158 ms)

From the output, we observe that both approaches correctly increment the counter to 100,000. However, there's a slight difference in execution time:

  • using_non_blocking took 34,738 milliseconds.
  • using_blocking took 38,158 milliseconds.

Analysis

The non-blocking approach is slightly faster in this scenario. This can be attributed to the reduced overhead of not having to acquire and release a lock as in the blocking approach. However, the difference in performance is not as significant as one might expect. This can be due to several factors, such as:

  • The overhead of spawning and managing a large number of threads.
  • The nature of the operation itself (a simple increment), which may not fully expose the potential contention issues in the blocking approach.
  • Modern CPU and compiler optimisations that can mitigate some of the overhead associated with locks.

Conclusion

This comparison illustrates that the choice between non-blocking and blocking approaches depends on the specific use case, contention levels, and the nature of operations performed. While non-blocking structures can provide performance benefits in high-contention scenarios, the simplicity and effectiveness of blocking structures in lower contention or less complex operations should not be overlooked.

In Rust, both approaches benefit from the language's strong emphasis on safety, ensuring that regardless of the choice, data races and concurrency issues are effectively managed, providing a robust foundation for concurrent programming.