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

…

Dependencies

Change contents