Testing/debugging "rebalance causes split of the root"

[?]

Feb 5, 2021, 6:47 PM

KX3WVNZW5KHVEH6EOQTZ4RBEFFJ3SGF5I467X3JWZ74PURRK4HVAC

Dependencies

[2] JEHCE5FN Alignment in unsized splits
[3] 6DCQHIFP Minor changes after benchmarking
[4] OTWDDJE7 Trait/type cleanup
[5] G4JEQLLX Debugging synchronisation
[6] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
[7] 6UVFCERM Formatting, debugging, etc.
[8] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
[9] WS4ZQM4R Debugging, tests, etc.
[10] H3FVSQIQ Unsized pages
[11] OP6SVMOD Resetting history
[12] W26CFMAQ Improving safety of cursors
[13] UUUVNC4D Debugging/cleanup around cursors
[14] QEUTVAZ4 Splitting btree::page
[*] UAQX27N4 Tests

Change contents

replacement in sanakirja-core/src/btree/page_unsized.rs at line 213

[4.9135]→[4.9135:9197](∅→∅)

let size = mod_size + mid_size + occupied - hdr_size;

[4.9135]

[4.9197]

let size = hdr_size + mod_size + mid_size + occupied;
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 14

[4.23215]

[4.23215]

debug!("rebalancing {:?}", m);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 22

[4.23541]→[4.23541:23714](∅→∅)

let mut freed = [0, 0];
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed[0] = m.modified.page.offset | b;

[4.23541]

[4.23714]

let mut freed_ = [0, 0];
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 25

[4.23777]→[4.23777:23842](∅→∅)

if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(

[4.23777]

[4.23842]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::replace(
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 36

[4.24072]

[4.24072]

if freed > 0 {
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 51

[4.24242]→[4.24242:24371](∅→∅)

let mut n = header(new_left.0.as_page()).n() as isize;
alloc::<K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);

[4.24242]

[4.24371]

let hdrl = header(new_left.0.as_page());
debug!("mid = {:?}", m.mid);

let mut lc = <Page<K, V>>::last_cursor(m.modified.page.as_page());
<Page<K, V>>::move_next(m.modified.page.as_page(), &mut lc);
if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_left.0, true, &lc, m.mid.0, m.mid.1, None, 0, rl)?
{
if freed > 0 {
let b = if header(new_left.0.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
new_left = page
} else {
unreachable!()
};
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 82

[4.24722]→[4.24722:24760](∅→∅)

freed[1] = m.other.offset | b

[4.24722]

[4.24760]

freed_[1] = m.other.offset | b
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 89

[4.24945]→[4.24945:24960](∅→∅)

freed,

[4.24945]

[4.24960]

freed: freed_,
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 112

[4.25656]→[4.25656:25829](∅→∅)

let mut freed = [0, 0];
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed[0] = m.modified.page.offset | b;

[4.25656]

[4.25829]

let mut freed_ = [0, 0];
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 115

[4.25893]→[4.25893:25958](∅→∅)

if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(

[4.25893]

[4.25958]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::replace(
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 126

[4.26188]

[4.26188]

if freed > 0 {
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 141

[4.26358]→[4.26358:26396](∅→∅)

if let Put::Ok(Ok { page, .. }) =

[4.26358]

[4.26396]

if let Put::Ok(Ok { page, freed }) =
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 144

[4.26490]

[4.26490]

if freed > 0 {
let b = if header(new_right.0.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 161

[4.26764]→[4.26764:26802](∅→∅)

freed[1] = m.other.offset | b

[4.26764]

[4.26802]

freed_[1] = m.other.offset | b
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 168

[4.26989]→[4.26989:27004](∅→∅)

freed,

[4.26989]

[4.27004]

freed: freed_,
edit in sanakirja-core/src/btree/page_unsized/put.rs at line 58

[4.54]→[4.54:191](∅→∅),[4.191]→[4.28946:28947](∅→∅),[4.28946]→[4.28946:28947](∅→∅)

{
let hdr = header(new.0.as_page());
assert_eq!(hdr.n() as u64 * 16, hdr.left_page() & 0xfff);
}
edit in sanakirja-core/src/btree/page_unsized/put.rs at line 125

[2.48]→[2.48:93](∅→∅)

total += size + L::extra_size();
edit in sanakirja-core/src/btree/page_unsized/put.rs at line 141

[4.31198]

[4.31198]

total += size + L::extra_size();
replacement in sanakirja-core/src/btree/page.rs at line 234

[4.16473]→[4.3025:3087](∅→∅)

let size = mod_size + mid_size + occupied - hdr_size;

[4.16473]

[4.16536]

let size = hdr_size + mod_size + mid_size + occupied;
replacement in sanakirja-core/src/btree/page.rs at line 465

[3.136]→[3.136:158](∅→∅)

s: &[Tuple<K, V>]

[3.136]

[3.158]

s: &[Tuple<K, V>],
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 21

[4.1035]→[4.1035:1208](∅→∅)

let mut freed = [0, 0];
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed[0] = m.modified.page.offset | b;

[4.1035]

[4.1208]

let mut freed_ = [0, 0];
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 24

[4.1271]→[4.1271:1336](∅→∅)

if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(

[4.1271]

[4.1336]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::replace(
edit in sanakirja-core/src/btree/page/rebalance.rs at line 35

[4.1566]

[4.1566]

if freed > 0 {
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 51

[4.1795]→[4.7217:7287](∅→∅)

alloc::<K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);

[4.1795]

[4.1868]

let mut lc = <Page<K, V>>::last_cursor(m.modified.page.as_page());
<Page<K, V>>::move_next(m.modified.page.as_page(), &mut lc);
if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_left.0, true, &lc, m.mid.0, m.mid.1, None, 0, rl)?
{
if freed > 0 {
let b = if header(new_left.0.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
new_left = page
} else {
unreachable!()
};
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 111

[4.3623]→[4.3623:3661](∅→∅)

freed[1] = m.other.offset | b

[4.3623]

[4.3661]

freed_[1] = m.other.offset | b
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 118

[4.3846]→[4.3846:3861](∅→∅)

freed,

[4.3846]

[4.3861]

freed: freed_,
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 141

[4.4562]→[4.4562:4735](∅→∅)

let mut freed = [0, 0];
let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed[0] = m.modified.page.offset | b;

[4.4562]

[4.4735]

let mut freed_ = [0, 0];
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 144

[4.4799]→[4.4799:4864](∅→∅)

if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(

[4.4799]

[4.4864]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::replace(
edit in sanakirja-core/src/btree/page/rebalance.rs at line 155

[4.5094]

[4.5094]

let b = if header(m.modified.page.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 168

[4.5264]→[4.5264:5302](∅→∅)

if let Put::Ok(Ok { page, .. }) =

[4.5264]

[4.5302]

if let Put::Ok(Ok { page, freed }) =
edit in sanakirja-core/src/btree/page/rebalance.rs at line 171

[4.5396]

[4.5396]

if freed > 0 {
let b = if header(new_right.0.as_page()).is_dirty() {
1
} else {
0
};
freed_[0] = freed | b;
}
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 188

[4.5670]→[4.5670:5708](∅→∅)

freed[1] = m.other.offset | b

[4.5670]

[4.5708]

freed_[1] = m.other.offset | b
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 195

[4.5895]→[4.5895:5910](∅→∅)

freed,

[4.5895]

[4.5910]

freed: freed_,
replacement in sanakirja-core/src/btree/cursor.rs at line 191

[4.1020]→[4.1020:1155](∅→∅)

impl<K: Representable + ?Sized + core::fmt::Debug, V: Representable + ?Sized + core::fmt::Debug, P: BTreePage<K, V>> Cursor<K, V, P> {

[4.1020]

[4.11341]

impl<
K: Representable + ?Sized + core::fmt::Debug,
V: Representable + ?Sized + core::fmt::Debug,
P: BTreePage<K, V>,
> Cursor<K, V, P>
{
replacement in sanakirja/src/tests.rs at line 437

[3.1148]→[3.1148:1169](∅→∅)

for i in 1..12 {

[3.1148]

[3.1169]

for i in 1..8 {
replacement in sanakirja/src/tests.rs at line 549

[3.5485]→[3.5485:5486](∅→∅)

[3.5485]

[3.5486]

/*
replacement in sanakirja/src/tests.rs at line 569

[3.6394]→[3.6394:6395](∅→∅)

[3.6394]

[3.6395]

*/
edit in sanakirja/src/tests.rs at line 577

[4.12892]

#[test]
fn split_on_del() {
env_logger::try_init().unwrap_or(());
let env = Env::new_anon(409600000, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = create_db_::<MutTxn<&Env, ()>, u64, [u8], UP<u64, [u8]>>(&mut txn).unwrap();
for i in (0..157).step_by(10) {
for i in i..i + 4 {
let a = [b'a'; 500];
put(&mut txn, &mut db, &i, &a[..]).unwrap();
}
put(&mut txn, &mut db, &(i + 9), &[b'b'; 254]).unwrap();
}
for i in (0..157).step_by(10) {
for i in i + 4..i + 7 {
let a = [b'a'; 500];
put(&mut txn, &mut db, &i, &a[..]).unwrap();
}
}
crate::debug::debug(&txn, &[&db], "debug0", true);
for i in 0..4 {
debug!("============ deleting {:?}", i);
del(&mut txn, &mut db, &i, None).unwrap();
}
crate::debug::debug(&txn, &[&db], "debug1", true);
del(&mut txn, &mut db, &4, None).unwrap();
crate::debug::debug(&txn, &[&db], "debug2", true);
}

#[test]
fn split_on_del2() {
env_logger::try_init().unwrap_or(());
let env = Env::new_anon(409600000, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = create_db_::<MutTxn<&Env, ()>, u64, [u8], UP<u64, [u8]>>(&mut txn).unwrap();
for i in (0..157).step_by(10) {
for i in i..i + 4 {
let a = [b'a'; 500];
put(&mut txn, &mut db, &i, &a[..]).unwrap();
}
put(&mut txn, &mut db, &(i + 9), &[b'b'; 255]).unwrap();
}
for i in (0..157).step_by(10) {
for i in i + 4..i + 7 {
let a = [b'a'; 500];
put(&mut txn, &mut db, &i, &a[..]).unwrap();
}
}
crate::debug::debug(&txn, &[&db], "debug0", true);
del(&mut txn, &mut db, &0, None).unwrap();
crate::debug::debug(&txn, &[&db], "debug1", true);
}
replacement in sanakirja/Cargo.toml at line 27

[3.6555]→[3.6555:6636](∅→∅)

old-sanakirja = { package = "sanakirja", version = "0.15", features = ["mmap"] }

[3.6555]

# old-sanakirja = { package = "sanakirja", version = "0.15", features = ["mmap"] }