Correct find_alive cache system

pmeunier

Jan 14, 2022, 12:12 PM

RSFUX6MLPHII3DRELHN62DOJCHFCDNKSRMWJDSFGTWN5S4RJVSSQC

Dependencies

• [2] FJTRJD6B Supporting patches recorded with older versions of Pijul
• [3] 3I4PAA2A Making a few types and methods public
• [4] KNB3RZMS Fixing path crashes related to the new non-null roots
• [5] FABI77LL Cleaning up the cache in missing_context and find_alive
• [6] 6YMDOZIB Refactoring apply
• [7] WZVCLZKY address clippy lints
• [8] YN63NUZO Sanakirja 1.0
• [9] CCLLB7OI Upgrading to Sanakirja 0.15 + version bump
• [10] I52XSRUH Massive cleanup, and simplification
• [11] AD6M434O find_alive performance (matters a lot for unrecord)
• [12] 7NSTS6PK Adding a cache in find_alive to improve performance in some cases
• [13] VO5OQW4W Removing anyhow in libpijul
• [14] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).
• [15] T7CAACFB Fixing zombie conflicts (some vertices were wrongly detected alive)
• [16] RRCSHAYZ Formatting
• [17] GHO6DWPI Refactoring iterators
• [18] I24UEJQL Various post-fire fixes
• [19] SFQBWL6P Improving unrecord performance (8 times faster on my tests)
• [*] MDADYULS Fix a panic when switching between channels that have different files

Change contents

• edit in libpijul/src/missing_context.rs at line 6
  [6.83368]→[6.0:24](∅→∅)
  − use std::cell::RefCell;
• edit in libpijul/src/missing_context.rs at line 7
  [6.696664]→[6.25:42](∅→∅)
  − use std::rc::Rc;
• replacement in libpijul/src/missing_context.rs at line 83
  [6.197]→[5.0:44](∅→∅),[5.44]→[6.237:275](∅→∅),[6.237]→[6.237:275](∅→∅),[6.275]→[6.698423:698527](∅→∅),[6.9555]→[6.698423:698527](∅→∅),[6.698423]→[6.698423:698527](∅→∅)
  − let mut alive = alive.borrow().clone();

  − debug!("files = {:?}", ws.files);

  − crate::TIMERS.lock().unwrap().find_alive += now.elapsed();

  − ws.load_graph(txn, channel, inode)?;
  [6.197]

  [6.698527]
  + if let Some(alive) = alive {

  + let mut alive = alive.clone();

  + debug!("files = {:?}", ws.files);

  + crate::TIMERS.lock().unwrap().find_alive += now.elapsed();

  + ws.load_graph(txn, channel, inode)?;
• replacement in libpijul/src/missing_context.rs at line 89
  [6.698528]→[6.698528:698590](∅→∅),[6.698652]→[6.698652:698670](∅→∅),[6.698670]→[6.9556:9619](∅→∅),[6.9619]→[6.698731:698828](∅→∅),[6.698731]→[6.698731:698828](∅→∅),[6.698828]→[5.45:73](∅→∅),[5.73]→[6.698856:698931](∅→∅),[6.305]→[6.698856:698931](∅→∅),[6.698856]→[6.698856:698931](∅→∅)
  − debug!("repair_missing_up_context, alive = {:?}", alive);

  − for &d in d {

  − if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

  − crate::alive::remove_redundant_parents(

  − graph,

  − vids,

  − &mut alive,

  − &mut ws.covered_parents,

  − d,

  − );
  [6.698528]

  [6.698931]
  + debug!("repair_missing_up_context, alive = {:?}", alive);

  + for &d in d {

  + if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

  + crate::alive::remove_redundant_parents(

  + graph,

  + vids,

  + &mut alive,

  + &mut ws.covered_parents,

  + d,

  + );

  + }

  + repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;
• replacement in libpijul/src/missing_context.rs at line 102
  [6.698941]→[5.74:146](∅→∅)
  − repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;
  [6.698941]

  [6.699912]
  + } else {

  + debug!("repair_missing_up_context: {:?} is alive", c);
• replacement in libpijul/src/missing_context.rs at line 144
  [6.574]→[5.147:191](∅→∅),[5.191]→[6.614:649](∅→∅),[6.614]→[6.614:649](∅→∅),[6.649]→[6.701033:701137](∅→∅),[6.701033]→[6.701033:701137](∅→∅),[6.701137]→[6.10294:10353](∅→∅),[6.10353]→[5.192:269](∅→∅),[5.269]→[6.701271:701277](∅→∅),[6.728]→[6.701271:701277](∅→∅),[6.701271]→[6.701271:701277](∅→∅)
  − let mut alive = alive.borrow().clone();

  − debug!("alive = {:?}", alive);

  − crate::TIMERS.lock().unwrap().find_alive += now.elapsed();

  − ws.load_graph(txn, channel, inode)?;

  − if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

  − crate::alive::remove_redundant_children(graph, vids, &mut alive, c);

  − }
  [6.574]

  [6.701277]
  + if let Some(alive) = alive {

  + let mut alive = alive.clone();

  + debug!("alive = {:?}", alive);

  + crate::TIMERS.lock().unwrap().find_alive += now.elapsed();

  + ws.load_graph(txn, channel, inode)?;

  + if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

  + crate::alive::remove_redundant_children(graph, vids, &mut alive, c);

  + }
• replacement in libpijul/src/missing_context.rs at line 153
  [6.701278]→[6.701278:701379](∅→∅)
  − if !alive.is_empty() {

  − debug!("repair_missing_down_context alive = {:#?}", alive);

  − }
  [6.701278]

  [6.701379]
  + if !alive.is_empty() {

  + debug!("repair_missing_down_context alive = {:#?}", alive);

  + }
• replacement in libpijul/src/missing_context.rs at line 157
  [6.701380]→[6.701380:701398](∅→∅),[6.701398]→[6.10354:10501](∅→∅),[6.10501]→[6.701621:701647](∅→∅),[6.701621]→[6.701621:701647](∅→∅)
  − for &d in d {

  − for &desc in alive.iter() {

  − if d == desc {

  − info!("repair_missing_down_context, alive: {:?} == {:?}", d, desc);

  − continue;
  [6.701380]

  [6.701647]
  + for &d in d {

  + for &desc in alive.iter() {

  + if d == desc {

  + info!("repair_missing_down_context, alive: {:?} == {:?}", d, desc);

  + continue;

  + }

  + debug!("repair_missing_down {:?} {:?}", d, desc);

  + put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, d, desc, ChangeId::ROOT)?;
• edit in libpijul/src/missing_context.rs at line 166
  [6.701661]→[6.10502:10564](∅→∅),[6.10564]→[6.89461:89552](∅→∅)
  − debug!("repair_missing_down {:?} {:?}", d, desc);

  − put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, d, desc, ChangeId::ROOT)?;
• edit in libpijul/src/missing_context.rs at line 167
  [6.701835]

  [6.701835]
  + } else {

  + debug!("repair_missing_down: {:?} is alive", c);
• replacement in libpijul/src/missing_context.rs at line 377
  [6.13269]→[6.729:1005](∅→∅)
  − alive_down_cache: HashMap<Vertex<ChangeId>, Rc<RefCell<HashSet<Vertex<ChangeId>>>>>,

  − alive_up_cache: HashMap<

  − Vertex<ChangeId>,

  − (

  − Rc<RefCell<HashSet<Vertex<ChangeId>>>>,

  − Rc<RefCell<HashSet<Vertex<ChangeId>>>>,

  − ),

  − >,
  [6.13269]

  [6.707180]
  + alive_down_cache: HashMap<Vertex<ChangeId>, Option<HashSet<Vertex<ChangeId>>>>,

  + alive_up_cache:

  + HashMap<Vertex<ChangeId>, (Option<HashSet<Vertex<ChangeId>>>, HashSet<Vertex<ChangeId>>)>,
• replacement in libpijul/src/missing_context.rs at line 523
  [6.711431]→[6.1006:1091](∅→∅)
  − let alive = find_alive_down(txn, channel, p, &mut ws.alive_down_cache)?;
  [6.711431]

  [6.1091]
  + let alive = find_alive_down(txn, channel, p, &mut ws.alive_down_cache)?.clone();
• replacement in libpijul/src/missing_context.rs at line 531
  [6.1275]→[6.1275:1309](∅→∅)
  − &*alive.borrow(),
  [6.1275]

  [6.1309]
  + alive.iter().flat_map(|t| t.iter()),
• edit in libpijul/src/fs.rs at line 881
  [4.554]

  [4.554]
  + debug!("name_dest = {:?}", name_dest);
• edit in libpijul/src/fs.rs at line 960
  [21.2747]

  [2.0]
  + debug!("inode_vertex = {:?}", inode_vertex);
• edit in libpijul/src/fs.rs at line 993
  [6.114634]

  [6.114634]
  + debug!("next = {:?}", next);
• edit in libpijul/src/fs.rs at line 1005
  [6.762693]

  [6.762693]
  + debug!("youngest");
• edit in libpijul/src/find_alive.rs at line 3
  [6.1357]→[6.1357:1452](∅→∅)
  − use std::cell::RefCell;

  − use std::rc::Rc;

  −

  − type Alive = Rc<RefCell<HashSet<Vertex<ChangeId>>>>;
• replacement in libpijul/src/find_alive.rs at line 4
  [6.32358]→[6.114846:114891](∅→∅)
  − pub(crate) fn find_alive_down<T: GraphTxnT>(
  [6.32358]

  [6.763561]
  + /// The following is an unrolled DFS, where each alive vertex is

  + /// inserted into each "alive set" along the current path (which is

  + /// recognised by looking at the visited vertices on the stack).

  + pub(crate) fn find_alive_down<'a, T: GraphTxnT>(
• replacement in libpijul/src/find_alive.rs at line 11
  [6.763631]→[6.1453:1637](∅→∅)
  − cache: &mut HashMap<Vertex<ChangeId>, Alive>,

  − ) -> Result<Alive, BlockError<T::GraphError>> {

  − let mut stack = vec![SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT)];
  [6.763631]

  [6.85243]
  + cache: &'a mut HashMap<Vertex<ChangeId>, Option<HashSet<Vertex<ChangeId>>>>,

  + ) -> Result<&'a Option<HashSet<Vertex<ChangeId>>>, BlockError<T::GraphError>> {

  + let mut stack: Vec<(_, Option<HashSet<Vertex<ChangeId>>>)> = vec![(

  + SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT),

  + None,

  + )];
• replacement in libpijul/src/find_alive.rs at line 18
  [6.85285]→[6.1638:1733](∅→∅),[6.139]→[6.134265:134306](∅→∅),[6.1733]→[6.134265:134306](∅→∅),[6.764007]→[6.134265:134306](∅→∅)
  − let alive = Rc::new(RefCell::new(HashSet::new()));

  − while let Some(elt) = stack.pop() {

  − if !visited.insert(elt.dest()) {
  [6.85285]

  [6.764046]
  + while let Some((elt, alive)) = stack.pop() {

  + if let Some(alive) = alive {

  + // We've gone through all the descendants, put this in the

  + // cache.

  + let vertex = txn.find_block(&channel, elt.dest())?;

  + cache.insert(*vertex, Some(alive.clone()));

  + if stack.is_empty() {

  + // Done!

  + return Ok(cache.get(&vertex0).unwrap());

  + }
• edit in libpijul/src/find_alive.rs at line 29
  [6.764068]

  [6.764068]
  + } else {

  + if !visited.insert(elt.dest()) {

  + continue;

  + }

  + stack.push((elt, Some(HashSet::new())));
• replacement in libpijul/src/find_alive.rs at line 37
  [6.1779]→[6.1779:1846](∅→∅)
  − alive.borrow_mut().extend(c.borrow().iter().cloned());
  [6.1779]

  [6.1846]
  + for st in stack.iter_mut() {

  + if let Some(ref mut st) = st.1 {

  + if let Some(c) = c {

  + st.extend(c.iter().cloned());

  + } else {

  + st.insert(*vertex);

  + }

  + }

  + }
• edit in libpijul/src/find_alive.rs at line 47
  [6.1868]→[6.1868:1935](∅→∅)
  − } else {

  − cache.insert(*vertex, alive.clone());
• replacement in libpijul/src/find_alive.rs at line 62
  [6.184]→[6.1946:2006](∅→∅),[6.2006]→[6.3716:3758](∅→∅),[6.235]→[6.3716:3758](∅→∅)
  − assert!(alive.borrow().is_empty());

  − return Ok(alive);
  [6.184]

  [6.276]
  + // vertex0 is alive.

  + stack.truncate(elt_index);

  + let (_, alive) = stack.pop().unwrap();

  + let alive = alive.unwrap();

  + assert!(alive.is_empty());

  + cache.insert(vertex0, None);

  + return Ok(cache.get(&vertex0).unwrap());
• replacement in libpijul/src/find_alive.rs at line 70
  [6.305]→[6.2007:2067](∅→∅)
  − alive.borrow_mut().insert(*vertex);
  [6.305]

  [6.352]
  + // vertex is alive, insert it into all the

  + // alive sets on the current DFS path

  + // (including `vertex`).

  + for st in stack.iter_mut() {

  + if let Some(ref mut st) = st.1 {

  + st.insert(*vertex);

  + }

  + }
• replacement in libpijul/src/find_alive.rs at line 83
  [5.469]→[5.469:500](∅→∅)
  − stack.push(*v)
  [5.469]

  [6.764996]
  + stack.push((*v, None))
• replacement in libpijul/src/find_alive.rs at line 87
  [6.765119]→[6.765119:765133](∅→∅)
  − Ok(alive)
  [6.765119]

  [6.765133]
  + unreachable!()
• replacement in libpijul/src/find_alive.rs at line 90
  [6.32414]→[3.4703:4739](∅→∅)
  − pub fn find_alive_up<T: GraphTxnT>(
  [6.32414]

  [6.765228]
  + pub fn find_alive_up<'a, T: GraphTxnT>(
• replacement in libpijul/src/find_alive.rs at line 96
  [6.15653]→[6.2096:2203](∅→∅)
  − cache: &mut HashMap<Vertex<ChangeId>, (Alive, Alive)>,

  − ) -> Result<Alive, BlockError<T::GraphError>> {
  [6.15653]

  [6.2203]
  + cache: &'a mut HashMap<

  + Vertex<ChangeId>,

  + (Option<HashSet<Vertex<ChangeId>>>, HashSet<Vertex<ChangeId>>),

  + >,

  + ) -> Result<&'a Option<HashSet<Vertex<ChangeId>>>, BlockError<T::GraphError>> {
• replacement in libpijul/src/find_alive.rs at line 102
  [6.2247]→[6.2247:2366](∅→∅),[6.2366]→[6.496:580](∅→∅),[6.85366]→[6.496:580](∅→∅)
  − let alive = Rc::new(RefCell::new(HashSet::default()));

  − let files_ = Rc::new(RefCell::new(HashSet::default()));

  − let mut stack = vec![SerializedEdge::empty(vertex0.end_pos(), ChangeId::ROOT)];
  [6.2247]

  [6.85367]
  + let mut stack: Vec<(

  + _,

  + Option<(HashSet<Vertex<ChangeId>>, HashSet<Vertex<ChangeId>>)>,

  + )> = vec![(

  + SerializedEdge::empty(vertex0.end_pos(), ChangeId::ROOT),

  + None,

  + )];
• replacement in libpijul/src/find_alive.rs at line 111
  [6.95]→[6.581:621](∅→∅)
  − while let Some(elt) = stack.pop() {
  [6.95]

  [6.134913]
  + while let Some((elt, alive)) = stack.pop() {
• replacement in libpijul/src/find_alive.rs at line 115
  [6.765801]→[6.134948:134989](∅→∅)
  − if !visited.insert(elt.dest()) {
  [6.765801]

  [6.765840]
  + if let Some((alive, files_)) = alive {

  + let vertex = *txn.find_block_end(&channel, elt.dest())?;

  + cache.insert(vertex, (Some(alive), files_));

  + if stack.is_empty() {

  + // Done!

  + return Ok(&cache.get(&vertex0).unwrap().0);

  + }
• replacement in libpijul/src/find_alive.rs at line 123
  [6.765862]→[6.765862:765872](∅→∅)
  − }
  [6.765862]

  [6.134990]
  + } else {

  + if !visited.insert(elt.dest()) {

  + continue;

  + }

  + stack.push((elt, Some((HashSet::new(), HashSet::new()))));

  + };
• replacement in libpijul/src/find_alive.rs at line 131
  [6.2408]→[6.2408:2927](∅→∅)
  − let is_cached = if let Some((c, f)) = cache.get(&vertex) {

  − alive.borrow_mut().extend(c.borrow().iter().cloned());

  − files_.borrow_mut().extend(f.borrow().iter().cloned());

  − files.extend(f.borrow().iter().cloned());

  − // We're not continuing here, since the while loop below

  − // needs to insert stuff into `files` and `files_`.

  − true

  − } else {

  − cache.insert(vertex, (alive.clone(), files_.clone()));

  − false

  − };
  [6.2408]

  [6.765934]
  + if let Some((c, d)) = cache.get(&vertex) {

  + debug!("Cached: {:?} {:?}", c, d);

  + for st in stack.iter_mut() {

  + if let Some((ref mut al, ref mut f)) = st.1 {

  + if let Some(c) = c {

  + al.extend(c.iter().cloned());

  + } else {

  + al.insert(vertex);

  + }

  + f.extend(d.iter().cloned());

  + files.extend(d.iter().cloned());

  + }

  + }

  + continue;

  + }
• replacement in libpijul/src/find_alive.rs at line 149
  [6.766044]→[6.15707:15740](∅→∅)
  − let mut is_file = false;
  [6.766044]

  [6.115205]
  + let mut is_file = false; // Is this the "inode" vertex of a file?
• edit in libpijul/src/find_alive.rs at line 162
  [6.135257]

  [6.135257]
  + if vertex == vertex0 {

  + // vertex0 is alive.

  + stack.truncate(elt_index);

  + let (_, alive) = stack.pop().unwrap();

  + let (alive, _) = alive.unwrap();

  + assert!(alive.is_empty());

  + cache.insert(vertex0, (None, HashSet::new()));

  + return Ok(&cache.get(&vertex0).unwrap().0);

  + }
• replacement in libpijul/src/find_alive.rs at line 176
  [6.115464]→[6.735:789](∅→∅)
  − if is_file && vertex != vertex0 {
  [6.115464]

  [6.2928]
  + if is_file {
• replacement in libpijul/src/find_alive.rs at line 178
  [6.2995]→[6.2995:3114](∅→∅)
  − alive.borrow_mut().insert(vertex);

  − files_.borrow_mut().insert(vertex);
  [6.2995]

  [6.16236]
  + for st in stack.iter_mut() {

  + if let Some((ref mut al, ref mut fi)) = st.1 {

  + al.insert(vertex);

  + fi.insert(vertex);

  + }

  + }
• replacement in libpijul/src/find_alive.rs at line 188
  [6.69]→[6.790:833](∅→∅),[6.833]→[6.3115:3231](∅→∅)
  − if vertex != vertex0 {

  − debug!("is alive {:?}", vertex);

  − alive.borrow_mut().insert(vertex);
  [6.69]

  [6.16444]
  + debug!("is alive {:?}", vertex);

  + for st in stack.iter_mut() {

  + if let Some((ref mut st, _)) = st.1 {

  + st.insert(vertex);

  + }
• replacement in libpijul/src/find_alive.rs at line 199
  [6.135477]→[6.956:1006](∅→∅),[6.1006]→[6.3232:3396](∅→∅)
  − if is_file && vertex != vertex0 {

  − debug!("is alive {:?}", vertex);

  − alive.borrow_mut().insert(vertex);

  − files_.borrow_mut().insert(vertex);
  [6.135477]

  [6.16574]
  + if is_file {

  + debug!("is pseudo-alive folder {:?}", vertex);

  + for st in stack.iter_mut() {

  + if let Some((ref mut al, ref mut fi)) = st.1 {

  + al.insert(vertex);

  + fi.insert(vertex);

  + }

  + }
• replacement in libpijul/src/find_alive.rs at line 210
  [6.16640]→[6.3397:3432](∅→∅),[6.3432]→[6.1007:1038](∅→∅),[6.768674]→[6.1007:1038](∅→∅)
  − } else if !is_cached {

  − stack.push(*v)
  [6.16640]

  [6.768704]
  + } else {

  + stack.push((*v, None))
• replacement in libpijul/src/find_alive.rs at line 216
  [6.768850]→[6.16685:16699](∅→∅)
  − Ok(alive)
  [6.768850]

  [6.768873]
  + unreachable!()