Search numbers in a really long list.

parallel_search.rs

use std::thread;
use std::sync::atomic::{Ordering, AtomicIsize};
use std::sync::Arc;
use std::time::{Instant};


fn parallel_search(sstables: &Vec<u8>, k: u8, n_threads: usize) -> isize {
    let n_sstables = sstables.len();
    let mut handles = vec![];
    let early_exit = Arc::new(AtomicIsize::new(-1));
    let chunk_size = (n_sstables + n_threads - 1) / n_threads;

    for i in 0..n_threads {
        let mut sstables = sstables.clone();
        let early_exit = early_exit.clone();

        let handle = thread::spawn(move || {
            let start = i * chunk_size;
            let end = std::cmp::min(n_sstables, start + chunk_size);
            for (j, sstable) in sstables.drain(start..end).enumerate() {
                let x = early_exit.load(Ordering::Relaxed);

                if x > (start + j) as isize && x != 0 {
                    println!("{} had an early exit because {} > {}!", i, x, j + start);
                    return;
                }
                if sstable == k && (start+j) as isize > x {
                    early_exit.store((start+j) as isize, Ordering::Relaxed);
                }
            }
        });

        handles.push(handle);
    }

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

    early_exit.load(Ordering::Relaxed)
}

fn main() {
    let start = Instant::now();
    let list = vec![26; 125_000_000];
    let result = parallel_search(&list, 26, 8);
    let duration = start.elapsed();
    println!("{:?} produced in {:?}", result, duration);
    assert_eq!(result, (list.len() - 1) as isize);
}