A few comments
[?]
Feb 12, 2021, 2:18 PM
RV2L6CZWTMUQ2A52YDAFVHDFGURZL3H4SSCDC347UGN23D3J5KZQCDependencies
- [2]
NXMFNPZ7Comments + debugging drop - [3]
OFINGD26implementing prev() on cursors (+ some cleanup) - [4]
OP6SVMODResetting history - [5]
DV4A2LR7Double-inserts (rebalancing near an internal deletion) - [6]
6DMPXOATMore debugging - [7]
EAAYH6BQDebugging put - [8]
S4V4QZ5CDebugging reference-counting for put - [9]
OTWDDJE7Trait/type cleanup - [10]
6UVFCERMFormatting, debugging, etc. - [11]
KMT3MF5NDrop a database - [12]
ONES3V46reference counting works for put - [13]
H3FVSQIQUnsized pages - [14]
6DCQHIFPMinor changes after benchmarking - [15]
W26CFMAQImproving safety of cursors - [16]
XEU2QVLCDebugging after plugging this into Pijul - [17]
73Z2UB3JCleanup + comments - [18]
WS4ZQM4RDebugging, tests, etc. - [19]
FMN7X4J2Micro-improvements, now noticeably faster than std::collections::BTreeMap - [20]
UUUVNC4DDebugging/cleanup around cursors
Change contents
- edit in sanakirja-core/src/btree/put.rs at line 13
use log::*; - edit in sanakirja-core/src/btree/put.rs at line 28
// Set the cursor to the first element larger than or equal to// `(key, value)`. We will insert at that position (where "insert"// is meant in the sense of Rust's `Vec::insert`. - edit in sanakirja-core/src/btree/put.rs at line 33
// If `(key, value)` already exists in the tree, return. - edit in sanakirja-core/src/btree/put.rs at line 36
// Else, we are at a leaf, since cursors that don't find an// element go all the way to the leaves.//// We put on the leaf page, resulting in a `Put`, i.e. either// `Put::Ok` or `Put::Split`. - edit in sanakirja-core/src/btree/put.rs at line 54
// In both cases (`Ok` and `Split`), we need to walk up the tree// and update each node.// Moreover, since the middle elements of the splits may be on// pages that must be freed at the end of this call, we collect// them in the `free` array below, and free them only at the end// of this function.//// If we didn't hold on to these pages, they could be reallocated// in subsequent splits, and the middle element could be// lost. This is important when the middle element climbs up more// than one level (i.e. the middle element of the split of a leaf// is also the middle element of the split of the leaf's parent,// etc). - edit in sanakirja-core/src/btree/put.rs at line 70
let p = cursor.pointer(); // Save the position of cursor at the leaf. - replacement in sanakirja-core/src/btree/put.rs at line 72
for f in free.iter() {for f in &free[..p] { - replacement in sanakirja-core/src/btree/put.rs at line 94
for _ in 0..N_CURSORS {loop { - replacement in sanakirja-core/src/btree/put.rs at line 103
incr_descendants::<T, K, V, P>(txn, cursor, free, freed, last_freed)?;last_freed = freed & !1;// Here, we are copying all children of the freed// page, except possibly the last freed page (which is// a child of the current node, if we aren't at a// leaf). This includes the split key/value, also// incremented in the following call:incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;// Then, insert the split key/value in the relevant page: - edit in sanakirja-core/src/btree/put.rs at line 112
// If we aren't at the root, just pop the cursor// stack and insert a new entry in the page above. - replacement in sanakirja-core/src/btree/put.rs at line 129
// Splitting the root.debug!("split root {:?} {:?}", split_key, split_value);debug!("{:?} {:?}", left, right);// If we are at the root, the root has// split. Insert the split key/value in a new page// above the entire tree. - edit in sanakirja-core/src/btree/put.rs at line 146
// Return the new root. - replacement in sanakirja-core/src/btree/put.rs at line 151
incr_descendants::<T, K, V, P>(txn, cursor, free, freed, last_freed)?;last_freed = freed & !1;// Same as above: increment the relevant reference// counters.incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;// And update the left child of the current cursor,// since the main invariant of cursors is that we're// always visiting the left child (if we're visiting// the last child of a page, the cursor is set to the// position strictly after the entries). - edit in sanakirja-core/src/btree/put.rs at line 161
// If we aren't at the root, just update the child. - edit in sanakirja-core/src/btree/put.rs at line 172
// If we are at the root, `page` is the updated root. - edit in sanakirja-core/src/btree/put.rs at line 178
unreachable!() - edit in sanakirja-core/src/btree/put.rs at line 180
/// This function does all the memory management for `put`. - replacement in sanakirja-core/src/btree/put.rs at line 191
last_freed: u64,last_freed: &mut u64, - edit in sanakirja-core/src/btree/put.rs at line 193[3.7700]→[3.850:956](∅→∅),[3.956]→[3.331:357](∅→∅),[3.357]→[3.980:1017](∅→∅),[3.980]→[3.980:1017](∅→∅)
debug!("incr_descendants {:?} {:?} {:?} {:?}",cursor.current().page,freed,cursor.pointer(),cursor.first_rc_level); - replacement in sanakirja-core/src/btree/put.rs at line 194
// This also includes the case where cursor.pointer == 0.// If a page has split or was immutable (allocated by a// previous transaction) and has been updated, we need to free// the old page. - replacement in sanakirja-core/src/btree/put.rs at line 199
if let Ok(rc) = txn.rc(freed & !1) {debug!("rc = {:?}", rc);}debug!("pointer {:?} {:?}", cursor.pointer(), cursor.first_rc_level);// Else, the "freed" page is shared with another tree, and// hence we just need to decrement its RC. - replacement in sanakirja-core/src/btree/put.rs at line 205
debug!("free child: {:?}", last_freed);// This means that the new version of the page (either split// or not) contains references to all the children of the// freed page, except the last freed page (because the new// version of that page isn't shared). - replacement in sanakirja-core/src/btree/put.rs at line 210
let mut c = P::cursor_before(cur.page.as_page());P::move_next(&mut c);// Start a cursor at the leftmost position and increase the// leftmost child page's RC (if we aren't at a leaf, and if// that child isn't the last freed page).let mut c = P::cursor_first(cur.page.as_page()); - replacement in sanakirja-core/src/btree/put.rs at line 216
if left != 0 && left != last_freed {debug!("incr {:?}", left);if left != 0 && left != *last_freed { - edit in sanakirja-core/src/btree/put.rs at line 219
// Then, for each entry of the page, increase the RCs of// references contained in the keys and values, and increase// the RC of the right child. - replacement in sanakirja-core/src/btree/put.rs at line 226
if r != 0 && r != last_freed {debug!("incr {:?}", r);if r != 0 && r != *last_freed { - edit in sanakirja-core/src/btree/put.rs at line 231
// Finally, update the last freed page to be the page we just// freed (the `&!1` is here because `freed` might have its LSB set// to indicate that `freed` was allocated by the current// transaction, but that bit isn't set in references to page// `freed` on the parent page).*last_freed = freed & !1; - replacement in sanakirja-core/src/btree/mod.rs at line 100
/// cursor isn't at the end of the page already)./// cursor isn't already after the last element). - edit in sanakirja-core/src/btree/mod.rs at line 390
// This is a for loop, to allow the compiler to unroll (maybe). - edit in sanakirja-core/src/btree/mod.rs at line 399
// Here, Rust says that `k` and `v` have the same lifetime// as `page`, but we actually know that they're alive for// as long as `txn` doesn't change, so we can safely// extend their lifetimes: - edit in sanakirja-core/src/btree/mod.rs at line 405
// The cursor is set to the first element greater than or// equal to the (k, v) we're looking for, so we need to// explore the left subtree. - edit in sanakirja-core/src/btree/mod.rs at line 429
// In order to make this function tail-recursive, we simulate a// stack with the following: - edit in sanakirja-core/src/btree/mod.rs at line 432
- edit in sanakirja-core/src/btree/mod.rs at line 434
let mut ptr = 0;// Push the root page of `db` onto the stack. - replacement in sanakirja-core/src/btree/mod.rs at line 442
let mut ptr = 0;// Then perform a DFS: - edit in sanakirja-core/src/btree/mod.rs at line 445
// Look at the top element of the stack. - edit in sanakirja-core/src/btree/mod.rs at line 447
// If it needs to be dropped (i.e. if its RC is <= 1), iterate// its cursor and drop all its referenced pages. - edit in sanakirja-core/src/btree/mod.rs at line 451
// if there's a current element in the cursor (i.e. we// aren't before or after the elements), decrease its RC. - edit in sanakirja-core/src/btree/mod.rs at line 458
// In all cases, move next and push the left child onto// the stack. This works because pushed cursors are// initially set to before the page's elements. - edit in sanakirja-core/src/btree/mod.rs at line 474
// Here, either rc > 1, or else `P::move_next` returned// `false`, meaning that the cursor is after the last element. - edit in sanakirja-core/src/btree/mod.rs at line 481
// If this was the bottom element of the stack, stop, else, pop.