lock_free/

skiplist_fast.rs

//! Ultra-fast lock-free skip list implementation
//! 
//! Optimizations:
//! - Fast thread-local RNG instead of SystemTime
//! - Reduced MAX_HEIGHT for better cache usage
//! - Optimized memory layout
//! - Simplified operations

use std::sync::atomic::{AtomicPtr, AtomicU64, Ordering};
use std::ptr::{self, null_mut};
use std::cmp::Ordering as CmpOrdering;
use std::cell::Cell;

const MAX_HEIGHT: usize = 16; // Reduced from 32 for better cache usage
const PROBABILITY: u32 = 0x80000000; // 50% probability (1/2 of u32::MAX)

thread_local! {
    // Fast thread-local RNG
    static RNG: Cell<u64> = Cell::new({
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        std::hash::Hash::hash(&std::thread::current().id(), &mut hasher);
        std::hash::Hasher::finish(&hasher)
    });
}

#[inline]
fn fast_random() -> u32 {
    RNG.with(|rng| {
        // XorShift64
        let mut x = rng.get();
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        rng.set(x);
        (x >> 32) as u32
    })
}

#[inline]
fn random_height() -> usize {
    let mut height = 1;
    while height < MAX_HEIGHT && fast_random() < PROBABILITY {
        height += 1;
    }
    height
}

/// Node in the skip list
#[repr(align(64))]
struct Node<K, V> {
    key: K,
    value: V,
    height: usize,
    next: [AtomicPtr<Node<K, V>>; MAX_HEIGHT],
}

impl<K, V> Node<K, V> {
    fn new(key: K, value: V, height: usize) -> Box<Self> {
        let mut node = Box::new(Node {
            key,
            value,
            height,
            next: unsafe { std::mem::zeroed() },
        });
        
        // Initialize next pointers
        for i in 0..MAX_HEIGHT {
            node.next[i] = AtomicPtr::new(null_mut());
        }
        
        node
    }
}

/// Ultra-fast lock-free skip list
pub struct FastSkipList<K, V> {
    head: Box<Node<K, V>>,
    size: AtomicU64,
}

impl<K: Ord + Default, V: Default> FastSkipList<K, V> {
    /// Create new skip list
    pub fn new() -> Self {
        let head = Node::new(K::default(), V::default(), MAX_HEIGHT);
        Self {
            head,
            size: AtomicU64::new(0),
        }
    }

    /// Find predecessors and successors for a key
    #[inline]
    fn find(&self, key: &K) -> ([*mut Node<K, V>; MAX_HEIGHT], [*mut Node<K, V>; MAX_HEIGHT]) {
        let mut preds: [*mut Node<K, V>; MAX_HEIGHT] = [null_mut(); MAX_HEIGHT];
        let mut succs: [*mut Node<K, V>; MAX_HEIGHT] = [null_mut(); MAX_HEIGHT];
        
        let mut current = &*self.head as *const Node<K, V> as *mut Node<K, V>;
        
        for level in (0..MAX_HEIGHT).rev() {
            loop {
                let next = unsafe { (*current).next[level].load(Ordering::Acquire) };
                
                if next.is_null() {
                    break;
                }
                
                let next_key = unsafe { &(*next).key };
                if next_key < key {
                    current = next;
                } else {
                    break;
                }
            }
            
            preds[level] = current;
            succs[level] = unsafe { (*current).next[level].load(Ordering::Acquire) };
        }
        
        (preds, succs)
    }

    /// Insert key-value pair
    pub fn insert(&self, key: K, value: V) -> bool {
        let height = random_height();
        let new_node = Box::into_raw(Node::new(key, value, height));
        
        loop {
            let (mut preds, mut succs) = self.find(unsafe { &(*new_node).key });
            
            // Check if key already exists
            if !succs[0].is_null() {
                let succ_key = unsafe { &(*succs[0]).key };
                if succ_key == unsafe { &(*new_node).key } {
                    // Key exists, free new node
                    unsafe { Box::from_raw(new_node); }
                    return false;
                }
            }
            
            // Try to link in new node
            for level in 0..height {
                unsafe {
                    (*new_node).next[level].store(succs[level], Ordering::Relaxed);
                }
            }
            
            // Try to link at level 0 first
            let pred_next = unsafe { &(*preds[0]).next[0] };
            match pred_next.compare_exchange(
                succs[0],
                new_node,
                Ordering::Release,
                Ordering::Acquire
            ) {
                Ok(_) => {
                    // Success at level 0, link other levels
                    for level in 1..height {
                        loop {
                            let pred_next = unsafe { &(*preds[level]).next[level] };
                            match pred_next.compare_exchange(
                                succs[level],
                                new_node,
                                Ordering::Release,
                                Ordering::Acquire
                            ) {
                                Ok(_) => break,
                                Err(_) => {
                                    // Retry find for this level
                                    let (new_preds, new_succs) = self.find(unsafe { &(*new_node).key });
                                    preds[level] = new_preds[level];
                                    succs[level] = new_succs[level];
                                }
                            }
                        }
                    }
                    
                    self.size.fetch_add(1, Ordering::Relaxed);
                    return true;
                }
                Err(_) => {
                    // Retry
                    continue;
                }
            }
        }
    }

    /// Check if key exists
    pub fn contains(&self, key: &K) -> bool {
        let mut current = &*self.head as *const Node<K, V> as *mut Node<K, V>;
        
        // Search from top level
        for level in (0..MAX_HEIGHT).rev() {
            loop {
                let next = unsafe { (*current).next[level].load(Ordering::Acquire) };
                
                if next.is_null() {
                    break;
                }
                
                let next_key = unsafe { &(*next).key };
                match next_key.cmp(key) {
                    CmpOrdering::Less => current = next,
                    CmpOrdering::Equal => return true,
                    CmpOrdering::Greater => break,
                }
            }
        }
        
        false
    }

    /// Get value by key
    pub fn get(&self, key: &K) -> Option<*const V> {
        let mut current = &*self.head as *const Node<K, V> as *mut Node<K, V>;
        
        for level in (0..MAX_HEIGHT).rev() {
            loop {
                let next = unsafe { (*current).next[level].load(Ordering::Acquire) };
                
                if next.is_null() {
                    break;
                }
                
                let next_key = unsafe { &(*next).key };
                match next_key.cmp(key) {
                    CmpOrdering::Less => current = next,
                    CmpOrdering::Equal => {
                        return Some(unsafe { &(*next).value as *const V });
                    }
                    CmpOrdering::Greater => break,
                }
            }
        }
        
        None
    }

    /// Remove key
    pub fn remove(&self, key: &K) -> bool {
        let (mut preds, succs) = self.find(key);
        
        // Check if key exists
        if succs[0].is_null() {
            return false;
        }
        
        let node_key = unsafe { &(*succs[0]).key };
        if node_key != key {
            return false;
        }
        
        let node = succs[0];
        let height = unsafe { (*node).height };
        
        // Unlink from all levels
        for level in (0..height).rev() {
            loop {
                let next = unsafe { (*node).next[level].load(Ordering::Acquire) };
                let pred_next = unsafe { &(*preds[level]).next[level] };
                
                match pred_next.compare_exchange(
                    node,
                    next,
                    Ordering::Release,
                    Ordering::Acquire
                ) {
                    Ok(_) => break,
                    Err(_) => {
                        // Find again
                        let (new_preds, _) = self.find(key);
                        preds[level] = new_preds[level];
                    }
                }
            }
        }
        
        // Safe to delete node
        unsafe { Box::from_raw(node); }
        self.size.fetch_sub(1, Ordering::Relaxed);
        true
    }

    /// Get number of elements
    pub fn len(&self) -> usize {
        self.size.load(Ordering::Relaxed) as usize
    }
}

unsafe impl<K: Send, V: Send> Send for FastSkipList<K, V> {}
unsafe impl<K: Send + Sync, V: Send + Sync> Sync for FastSkipList<K, V> {}

impl<K, V> Drop for FastSkipList<K, V> {
    fn drop(&mut self) {
        let mut current = self.head.next[0].load(Ordering::Acquire);
        
        while !current.is_null() {
            let next = unsafe {
                let node = Box::from_raw(current);
                node.next[0].load(Ordering::Acquire)
            };
            current = next;
        }
    }
}