{"header":{"message":"Micro-improvements, now noticeably faster than std::collections::BTreeMap","description":null,"timestamp":"2021-01-30T19:17:04.026715582Z","authors":[{"full_name":"Pierre-Étienne Meunier","name":"pmeunier"}]},"hash":"FMN7X4J24EYPOJNBUWM4NKGWSJTRV2DHCIBMPV2AXLZVVAMNOBKQC","authors":[],"deps":{"hashes":[["FMN7X4J24EYPOJNBUWM4NKGWSJTRV2DHCIBMPV2AXLZVVAMNOBKQC","Micro-improvements, now noticeably faster than std::collections::BTreeMap"],["AA",null],["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","Resetting history"],["R5AJGJPTY6CRGFJNBJEH4XOTOUZUI2FV4YKC3EZQQMYT2GMZJYKAC","Minor performance improvement"]],"deps":["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC"],"known":["R5AJGJPTY6CRGFJNBJEH4XOTOUZUI2FV4YKC3EZQQMYT2GMZJYKAC"]},"hunks":[{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":13,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":3963},"to":{"change":2,"start":3963,"end":3975},"introduced_by":2}],"inode":{"change":2,"pos":3448}}},"contents":[{"Del":"use log::*;\n"}]}},{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":56,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":5216}],"down_context":[{"change":2,"pos":5216}],"flag":"BLOCK","start":0,"end":29,"inode":{"change":2,"pos":3448}}},"contents":[{"Add":" cursor.pointer -= 1;"}]}},{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":65,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":5404},"to":{"change":2,"start":5404,"end":5441},"introduced_by":2}],"inode":{"change":2,"pos":3448}}},"contents":[{"Del":" cursor.pointer -= 1;\n"}]}},{"Replacement":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":66,"ins":{"up_context":[{"change":2,"pos":5516}],"down_context":[{"change":2,"pos":5641}],"flag":"BLOCK","start":30,"end":532,"inode":{"change":2,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":5516},"to":{"change":2,"start":5516,"end":5641},"introduced_by":2}],"inode":{"change":2,"pos":3448}},"ins_contents":[{"Add":" if cursor.pointer > 0 {"},{"Add":" let cur = cursor.current();"},{"Add":" put = P::put("},{"Add":" txn,"},{"Add":" cur.page,"},{"Add":" cursor.pointer < cursor.first_rc_level,"},{"Add":" cur.cursor.as_ref().unwrap(),"},{"Add":" split_key,"},{"Add":" split_value,"},{"Add":" left.0.offset,"},{"Add":" right.0.offset,"},{"Add":" )?"},{"Add":" } else {"}],"del_contents":[{"Del":" if cursor.pointer == 0 {\n debug!(\"Split root: {:?} {:?}\", left.0.offset, right.0.offset);\n"}]}},{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":93,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":6136},"to":{"change":2,"start":6136,"end":6641},"introduced_by":2}],"inode":{"change":2,"pos":3448}}},"contents":[{"Del":" } else {\n debug!(\"put cascade\");\n let cur = cursor.current();\n put = P::put(\n txn,\n cur.page,\n cursor.pointer < cursor.first_rc_level,\n cur.cursor.as_ref().unwrap(),\n split_key,\n split_value,\n left.0.offset,\n right.0.offset,\n )?\n"}]}},{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":95,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":6673},"to":{"change":2,"start":6673,"end":7253},"introduced_by":2}],"inode":{"change":2,"pos":3448}}},"contents":[{"Del":" Put::Ok(Ok { page, freed }) if cursor.pointer > 1 => {\n debug!(\"put update\");\n cursor.pointer -= 1;\n incr_descendants::(txn, cursor, free, freed)?;\n // update\n let ref curs = cursor.current();\n put = Put::Ok(P::update_left_child(\n txn,\n curs.page,\n cursor.pointer < cursor.first_rc_level,\n curs.cursor.as_ref().unwrap(),\n page.0.offset,\n )?)\n }\n"}]}},{"Replacement":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":97,"ins":{"up_context":[{"change":2,"pos":7373}],"down_context":[{"change":2,"pos":7406}],"flag":"BLOCK","start":533,"end":1008,"inode":{"change":2,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":7373},"to":{"change":2,"start":7373,"end":7406},"introduced_by":2}],"inode":{"change":2,"pos":3448}},"ins_contents":[{"Add":" if cursor.pointer > 0 {"},{"Add":" let ref curs = cursor.current();"},{"Add":" put = Put::Ok(P::update_left_child("},{"Add":" txn,"},{"Add":" curs.page,"},{"Add":" cursor.pointer < cursor.first_rc_level,"},{"Add":" curs.cursor.as_ref().unwrap(),"},{"Add":" page.0.offset,"},{"Add":" )?)"},{"Add":" } else {"},{"Add":" return Ok(page);"},{"Add":" }"}],"del_contents":[{"Del":" return Ok(page);\n"}]}},{"Edit":{"inode":{"change":2,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":125,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":7700}],"down_context":[{"change":2,"pos":7700}],"flag":"BLOCK","start":1009,"end":1107,"inode":{"change":2,"pos":3448}}},"contents":[{"Add":" // debug!(\"cursor.pointer {:?}, first_rc_level {:?}\", cursor.pointer, cursor.first_rc_level);"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":2,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":8638},"to":{"change":2,"start":8638,"end":8650},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":"use log::*;\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":112,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":11184},"to":{"change":2,"start":11184,"end":11220},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"leaf put\");\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":114,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":11319},"to":{"change":2,"start":11319,"end":11359},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"internal put\");\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":417,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":22499},"to":{"change":2,"start":22499,"end":22538},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" let hdr = &*header(&page);\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":425,"ins":{"up_context":[{"change":2,"pos":22942}],"down_context":[{"change":2,"pos":23036}],"flag":"BLOCK","start":1108,"end":1202,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":22942},"to":{"change":2,"start":22942,"end":23036},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" if let Some(v0) = v0 {"},{"Add":" s.binary_search_by(|tup| {"}],"del_contents":[{"Del":" s.binary_search_by(|tup| {\n if let Some(v0) = v0 {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":428,"ins":{"up_context":[{"change":2,"pos":23130}],"down_context":[{"change":2,"pos":23163}],"flag":"BLOCK","start":1203,"end":1310,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":23130},"to":{"change":2,"start":23130,"end":23163},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" } else {"},{"Add":" s.binary_search_by(|tup| {"}],"del_contents":[{"Del":" } else {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":432,"ins":{"up_context":[{"change":2,"pos":23225}],"down_context":[{"change":2,"pos":23274}],"flag":"BLOCK","start":1311,"end":1360,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":23225},"to":{"change":2,"start":23225,"end":23274},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" }"}],"del_contents":[{"Del":" }\n })\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":439,"ins":{"up_context":[{"change":2,"pos":23479}],"down_context":[{"change":2,"pos":23713}],"flag":"BLOCK","start":1361,"end":1603,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":23479},"to":{"change":2,"start":23479,"end":23713},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" if let Some(v0) = v0 {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u16::from_le(off);"},{"Add":" let (k, v) = read::(page.data.offset(off as isize));"}],"del_contents":[{"Del":" s.binary_search_by(|&off| {\n let off = u16::from_le(off);\n let (k, v) = read::(page.data.offset(off as isize));\n if let Some(v0) = v0 {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":444,"ins":{"up_context":[{"change":2,"pos":23807}],"down_context":[{"change":2,"pos":23840}],"flag":"BLOCK","start":1604,"end":1859,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":23807},"to":{"change":2,"start":23807,"end":23840},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" } else {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u16::from_le(off);"},{"Add":" let (k, _) = read::(page.data.offset(off as isize));"}],"del_contents":[{"Del":" } else {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":450,"ins":{"up_context":[{"change":2,"pos":23902}],"down_context":[{"change":2,"pos":23951}],"flag":"BLOCK","start":1860,"end":1909,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":23902},"to":{"change":2,"start":23902,"end":23951},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" }"}],"del_contents":[{"Del":" }\n })\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":456,"ins":{"up_context":[{"change":2,"pos":24115}],"down_context":[{"change":2,"pos":24349}],"flag":"BLOCK","start":1910,"end":2152,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":24115},"to":{"change":2,"start":24115,"end":24349},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" if let Some(v0) = v0 {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" let (k, v) = read::(page.data.offset(off as isize & 0xfff));"}],"del_contents":[{"Del":" s.binary_search_by(|&off| {\n let off = u64::from_le(off) & 0xfff;\n let (k, v) = read::(page.data.offset(off as isize & 0xfff));\n if let Some(v0) = v0 {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":461,"ins":{"up_context":[{"change":2,"pos":24439}],"down_context":[{"change":2,"pos":24468}],"flag":"BLOCK","start":2153,"end":2404,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":24439},"to":{"change":2,"start":24439,"end":24468},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" } else {"},{"Add":" s.binary_search_by(|&off| {"},{"Add":" let off = u64::from_le(off) & 0xfff;"},{"Add":" let (k, _) = read::(page.data.offset(off as isize & 0xfff));"}],"del_contents":[{"Del":" } else {\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":467,"ins":{"up_context":[{"change":2,"pos":24526}],"down_context":[{"change":2,"pos":24567}],"flag":"BLOCK","start":2405,"end":2446,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":24526},"to":{"change":2,"start":24526,"end":24567},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" })"},{"Add":" }"}],"del_contents":[{"Del":" }\n })\n"}]}},{"Replacement":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":646,"ins":{"up_context":[{"change":2,"pos":30404}],"down_context":[{"change":2,"pos":30460}],"flag":"BLOCK","start":2447,"end":2506,"inode":{"change":2,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":30404},"to":{"change":2,"start":30404,"end":30460},"introduced_by":2}],"inode":{"change":2,"pos":8623}},"ins_contents":[{"Add":" // debug!(\"{:?} {:?} {:?}\", new, hdr.n(), *n);"}],"del_contents":[{"Del":" debug!(\"{:?} {:?} {:?}\", new, hdr.n(), *n);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1008,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":42704},"to":{"change":2,"start":42704,"end":42731},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"s = {:?}\", s);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1009,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":42774},"to":{"change":2,"start":42774,"end":42817},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"s0 = {:?} s1 = {:?}\", s0, s1);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1060,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":44826},"to":{"change":2,"start":44826,"end":44874},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"s1 = {:?}, kk = {:?}\", s1, kk);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1064,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":44956},"to":{"change":2,"start":44956,"end":45003},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"s1a = {:?} s1b = {:?}\", s1a, s1b);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1065,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":45049},"to":{"change":2,"start":45049,"end":45088},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"clone {:?} {:?}\", n, s1a);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1066,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":45144},"to":{"change":2,"start":45144,"end":45173},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"alloc {:?}\", n);\n"}]}},{"Edit":{"inode":{"change":2,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1067,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":45232},"to":{"change":2,"start":45232,"end":45263},"introduced_by":2}],"inode":{"change":2,"pos":8623}}},"contents":[{"Del":" debug!(\"clone 2 {:?}\", n);\n"}]}},{"Replacement":{"inode":{"change":2,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":81,"ins":{"up_context":[{"change":2,"pos":66237}],"down_context":[{"change":2,"pos":66334}],"flag":"BLOCK","start":2507,"end":2648,"inode":{"change":2,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":66237},"to":{"change":2,"start":66237,"end":66334},"introduced_by":2}],"inode":{"change":2,"pos":63682}},"ins_contents":[{"Add":" while self.pointer < N_CURSORS {"},{"Add":" let current = unsafe { &mut *self.stack.get_unchecked_mut(self.pointer).as_mut_ptr() };"}],"del_contents":[{"Del":" loop {\n let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };\n"}]}},{"Replacement":{"inode":{"change":2,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":104,"ins":{"up_context":[{"change":2,"pos":67229}],"down_context":[{"change":2,"pos":67409}],"flag":"BLOCK","start":2649,"end":2907,"inode":{"change":2,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":67229},"to":{"change":2,"start":67229,"end":67409},"introduced_by":2}],"inode":{"change":2,"pos":63682}},"ins_contents":[{"Add":" unsafe {"},{"Add":" *self.stack.get_unchecked_mut(self.pointer) = MaybeUninit::new(PageCursor {"},{"Add":" page: txn.load_page(next_page)?,"},{"Add":" cursor: None,"},{"Add":" });"},{"Add":" }"}],"del_contents":[{"Del":" self.stack[self.pointer] = MaybeUninit::new(PageCursor {\n page: txn.load_page(next_page)?,\n cursor: None,\n });\n"}]}},{"Edit":{"inode":{"change":2,"pos":77822},"path":"sanakirja/src/main.rs","line":30,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":78605},"to":{"change":2,"start":78605,"end":78616},"introduced_by":2}],"inode":{"change":2,"pos":77822}}},"contents":[{"Del":" /*\n"}]}},{"Replacement":{"inode":{"change":2,"pos":77822},"path":"sanakirja/src/main.rs","line":37,"ins":{"up_context":[{"change":2,"pos":78876}],"down_context":[{"change":2,"pos":78878}],"flag":"BLOCK","start":2908,"end":2919,"inode":{"change":2,"pos":77822}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":78876},"to":{"change":2,"start":78876,"end":78878},"introduced_by":2}],"inode":{"change":2,"pos":77822}},"ins_contents":[{"Add":" /*"}],"del_contents":[{"Del":"\n\n"}]}},{"Replacement":{"inode":{"change":2,"pos":108411},"path":"sanakirja/Cargo.toml","line":12,"ins":{"up_context":[{"change":2,"pos":108664}],"down_context":[{"change":2,"pos":108728}],"flag":"BLOCK","start":2920,"end":2944,"inode":{"change":2,"pos":108411}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":108664},"to":{"change":2,"start":108664,"end":108728},"introduced_by":2}],"inode":{"change":2,"pos":108411}},"ins_contents":[{"Add":"log = { version = \"*\" }"}],"del_contents":[{"Del":"log = { version = \"*\", features = [ \"release_max_level_off\" ] }\n"}]}}],"owner":"pijul","repo":"sanakirja","token":"M9+RCAeCyG1ETBVBo0k1XxZhH7CRTJlNfQwGxD+vmjs=","login":null}

…

Dependencies

Change contents