pijul nest
guest › [sign in] [explore]

Init

[?]
Jan 22, 2021, 11:41 AM
YA6A53B5DH4CTM4QO6RMERXQ6I3H3LAZ4V4Q2TBCG44GILTWMG3AC

Dependencies

Change contents

  • file addition: src (dxwrx-rx-r)
    [1.0]
  • file addition: skiplist.rs (-xw-x--x--)
    [0.6]
    use super::MutPage;
    const N_LEVELS: usize = 7;
    pub const SKIPLIST_ROOT: u16 = 8;
    const RIGHT_CHILD_OFFSET_U64: isize = 1;
    pub const FIRST_BINDING_SIZE: u16 = SKIPLIST_ROOT + 16;
    #[derive(Debug, Copy, Clone)]
    pub struct SkipCursor {
    pub levels: [u16; N_LEVELS],
    pub started: bool,
    }
    impl SkipCursor {
    pub fn new() -> Self {
    SkipCursor {
    levels: [SKIPLIST_ROOT; N_LEVELS],
    started: false,
    }
    }
    pub fn reset(&mut self) {
    for i in self.levels.iter_mut() {
    *i = SKIPLIST_ROOT
    }
    self.started = false
    }
    }
    /// Sets the cursor to the last position strictly smaller than
    /// (key, value). If the key (and possibly value) was found, the
    /// corresponding value is returned.
    pub(crate) fn set_cursor(
    page: &MutPage,
    curs: &mut SkipCursor,
    key: u64,
    ) -> Option<u64> {
    let mut level = N_LEVELS - 1;
    loop {
    let result = set_cursor_at_level(page, &mut curs.levels[level], level, key);
    if level == 0 {
    return result;
    }
    level -= 1;
    curs.levels[level] = curs.levels[level + 1]
    }
    }
    /// Moves the cursor at level `level`, until the final position is
    /// either immediately before NIL, or the largest position
    /// strictly smaller than (key, value). If (key, value) was found,
    /// it is returned.
    fn set_cursor_at_level(
    page: &MutPage,
    position: &mut u16,
    level: usize,
    key: u64,
    ) -> Option<u64> {
    loop {
    let next_position = next_at_level(page, *position, level);
    if next_position == 0 {
    return None;
    }
    let (k, v) = unsafe { read_key_value(page, next_position) };
    if k == key {
    return Some(v)
    } else if k < key {
    debug_assert!(*position != next_position);
    *position = next_position
    } else {
    return None
    }
    }
    }
    unsafe fn set_level(p: *mut u8, level: usize, value: u16) {
    debug_assert!(level < N_LEVELS);
    debug_assert_eq!(value & 7, 0); // Check that value is multiple of 8.
    debug_assert_eq!((p as usize) & 7, 0); // Check that the conversion to *mut u64 is valid.
    let p = p as *mut u64;
    let mut levels = u64::from_le(*p);
    // All values are 8-bytes aligned, we don't need to store the 3 extra 0s.
    let value = (value >> 3) as u64;
    // Set the value at that level to 0.
    levels &= !(0x1ff << (9 * level));
    // Replace with current value.
    levels |= value << (9 * level);
    *p = levels.to_le()
    }
    /// This function panics if there's enough space on the page.
    #[doc(hidden)]
    pub(crate) fn skiplist_insert_after_cursor(
    page: &mut MutPage,
    r: &mut u8,
    cursor: &mut SkipCursor,
    key: u64,
    value: u64,
    right_child: u64,
    ) {
    // First allocate the key and value.
    let off = page.alloc(32);
    debug_assert_ne!(off, 0);
    page.reset_pointers(off);
    unsafe {
    *(page.p.offset(off as isize + 16) as *mut u64) = key;
    *(page.p.offset(off as isize + 24) as *mut u64) = value;
    }
    set_right_child(page, off, right_child);
    // Now insert in the base list.
    let mut g = *r;
    *r += 1;
    for l in 0..N_LEVELS {
    unsafe {
    debug_assert_ne!(off, next_at_level(page, cursor.levels[l], l));
    debug_assert_ne!(off, cursor.levels[l]);
    set_level(
    page.p.offset(off as isize),
    l,
    next_at_level(page, cursor.levels[l], l),
    );
    set_level(page.p.offset(cursor.levels[l] as isize), l, off);
    }
    cursor.levels[l] = off;
    if g & 1 == 0 {
    break;
    }
    g >>= 1
    }
    }
    #[doc(hidden)]
    pub(crate) fn set_right_child(page: &MutPage, off: u16, r: u64) {
    if off >= 4096 {
    panic!("{} < 4096", off);
    }
    unsafe {
    *((page.offset(off as isize) as *mut u64).offset(RIGHT_CHILD_OFFSET_U64)) = r.to_le();
    }
    }
    impl MutPage {
    fn reset_pointers(&mut self, offset: u16) {
    // Initialize the list pointers.
    unsafe {
    let p: *mut u8 = self.p.offset(offset as isize);
    std::ptr::write_bytes(p, 0, 8);
    }
    }
    }
    // All bindings are 8-bytes aligned. There are 7 layers, each
    // encoding 9 bits, which are then multiplied by 8 to get the
    // position on the page.
    pub(crate) fn next_at_level(p: &MutPage, off: u16, level: usize) -> u16 {
    unsafe {
    debug_assert!(level < N_LEVELS);
    let levels = u64::from_le(*(p.offset(off as isize) as *const u64));
    (((levels >> (9 * level)) & 0x1ff) as u16) << 3
    }
    }
    pub(crate) unsafe fn read_key_value(
    p: &MutPage,
    off: u16,
    ) -> (u64, u64) {
    assert!(off < 4096);
    (*(p.offset(off as isize + 16) as *mut u64),
    *(p.offset(off as isize + 24) as *mut u64))
    }
    impl MutPage {
    pub fn init_skiplist_page(&mut self) {
    self.reset_pointers(SKIPLIST_ROOT);
    // Initialize the page metadata.
    self.set_first_free(FIRST_BINDING_SIZE); // first free spot.
    self.set_size(FIRST_BINDING_SIZE); // occupied size on page.
    unsafe {
    *((self.offset(SKIPLIST_ROOT as isize) as *mut u64).offset(RIGHT_CHILD_OFFSET_U64)) = 0;
    }
    }
    }
  • file addition: main.rs (-xw-x--x--)
    [0.6]
    mod skiplist;
    fn main() {
    let mut page = [0u8; 4096];
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
    let mut p = MutPage {
    p: page.as_mut_ptr()
    };
    unsafe {
    p.init();
    let now = std::time::SystemTime::now();
    for i in 0..170 {
    p.put(i * i, i * i * i, 0);
    }
    total_put += now.elapsed().unwrap();
    let now = std::time::SystemTime::now();
    for i in 0..170 {
    p.lookup(i * i);
    }
    total_lookup += now.elapsed().unwrap();
    }
    }
    println!("{:?} {:?}", total_put, total_lookup);
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
    let mut p = MutPage {
    p: page.as_mut_ptr()
    };
    unsafe {
    p.init();
    for i in 0..170 {
    let now = std::time::SystemTime::now();
    p.put_ord(i * i, i * i * i, 0);
    total_put += now.elapsed().unwrap();
    }
    let now = std::time::SystemTime::now();
    for i in 0..170 {
    p.lookup_ord(i * i);
    }
    total_lookup += now.elapsed().unwrap();
    }
    }
    println!("{:?} {:?}", total_put, total_lookup);
    let mut rng = 0;
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
    let mut p = MutPage {
    p: page.as_mut_ptr()
    };
    p.init_skiplist_page();
    let mut c = skiplist::SkipCursor::new();
    let now = std::time::SystemTime::now();
    for i in 0..100 {
    c.reset();
    skiplist::set_cursor(&p, &mut c, i * i);
    skiplist::skiplist_insert_after_cursor(&mut p, &mut rng, &mut c, i*i, i*i*i, 0);
    }
    total_put += now.elapsed().unwrap();
    let now = std::time::SystemTime::now();
    for i in 0..100 {
    c.reset();
    skiplist::set_cursor(&p, &mut c, i * i);
    }
    total_lookup += now.elapsed().unwrap();
    }
    println!("{:?} {:?}", total_put, total_lookup);
    }
    struct MutPage {
    p: *mut u8,
    }
    impl MutPage {
    pub unsafe fn init(&mut self) {
    let p = self.p as *mut u64;
    *(p.offset(1)) = 0;
    self.set_size(16);
    self.set_first_free(16);
    }
    pub fn size(&self) -> u16 {
    unsafe {
    u16::from_le(*(self.p as *mut u16).offset(2))
    }
    }
    pub fn set_size(&self, n: u16) {
    unsafe {
    *(self.p as *mut u16).offset(2) = n.to_le()
    }
    }
    pub fn set_first_free(&self, n: u16) {
    unsafe {
    *(self.p as *mut u16).offset(3) = n.to_le()
    }
    }
    pub fn first_free(&self) -> u16 {
    unsafe {
    u16::from_le(*(self.p as *mut u16).offset(3))
    }
    }
    pub unsafe fn put(&mut self, k0: u64, v0: u64, rr: u64) {
    let rn0 = u64::from_le(*self.offset(8));
    let mut n0 = (rn0 & 0xfff) as isize;
    let mut i = n0;
    n0 = 8;
    while i != 0 {
    let k = u64::from_le(*self.offset(i + 8));
    if k0 < k {
    let rn = u64::from_le(*self.offset(i));
    let n = (rn & 0xfff) as isize;
    n0 = i;
    i = n
    } else if k0 == k {
    return
    } else {
    // Insérer ici.
    let off = self.alloc(24);
    let r0 = *self.offset(n0) & !0xfff;
    *self.offset(n0) = r0 | (off as u64);
    *self.offset(off as isize) = rr | (i as u64);
    *self.offset(off as isize + 8) = k0.to_le();
    *self.offset(off as isize + 16) = v0.to_le();
    return
    }
    }
    let off = self.alloc(24);
    let r0 = *self.offset(n0) & !0xfff;
    *self.offset(n0) = r0 | (off as u64);
    *self.offset(off as isize) = rr.to_le();
    *self.offset(off as isize + 8) = k0.to_le();
    *self.offset(off as isize + 16) = v0.to_le();
    }
    unsafe fn offset(&self, i: isize) -> *mut u64 {
    self.p.offset(i) as *mut u64
    }
    pub fn alloc(&mut self, n: u16) -> u16 {
    self.set_size(self.size() + n);
    let result = self.first_free();
    assert!(result + n <= 4096);
    self.set_first_free(result + n);
    result
    }
    pub unsafe fn lookup(&self, k0: u64) -> Option<u64> {
    let rn0 = u64::from_le(*self.offset(8));
    let mut i = (rn0 & 0xfff) as isize;
    while i != 0 {
    let k = u64::from_le(*self.offset(i + 8));
    if k0 < k {
    let rn = u64::from_le(*self.offset(i));
    let n = (rn & 0xfff) as isize;
    i = n
    } else if k0 == k {
    return Some(u64::from_le(*self.offset(i + 16)))
    } else {
    return None
    }
    }
    None
    }
    }
    impl MutPage {
    pub unsafe fn lookup_ord_(&mut self, k0: u64) -> u16 {
    let mut a = 16;
    let mut b = self.size();
    assert!(b <= 4096);
    while a < b {
    let mid = (a + b) / 2 - 16;
    let mid = 16 + mid - (mid % 24);
    let k = *(self.p.offset(mid as isize) as *mut u64);
    if k < k0 {
    if a == mid {
    break
    }
    a = mid
    } else {
    b = mid
    }
    }
    a
    }
    pub unsafe fn lookup_ord(&mut self, k0: u64) -> Option<u64> {
    let off = self.lookup_ord_(k0) as isize;
    let k = *(self.p.offset(off) as *mut u64);
    if k == k0 {
    Some(*(self.p.offset(off + 8) as *mut u64))
    } else {
    None
    }
    }
    pub unsafe fn put_ord(&mut self, k0: u64, v0: u64, _rr: u64) {
    let size = self.size();
    let off = self.lookup_ord_(k0);
    if size > off {
    std::ptr::copy(self.p.offset(off as isize), self.p.offset(off as isize + 24), (size - off) as usize);
    }
    *self.offset(off as isize + 8) = k0.to_le();
    *self.offset(off as isize + 16) = v0.to_le();
    self.set_size(size + 24);
    }
    }
  • file addition: Cargo.toml (-xw-x--x--)
    [1.0]
    [package]
    name = "sanakirja2"
    version = "0.1.0"
    authors = ["pe"]
    edition = "2018"
    # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
    [dependencies]