Adding a cache in find_alive to improve performance in some cases

pmeunier

Jan 12, 2022, 12:17 PM

7NSTS6PKVQWNUGIUYBRS4GWHJPAV57TOPBTDCOBZ5YYQNFZIZW2QC

Dependencies

• [2] RRCSHAYZ Formatting
• [3] WZVCLZKY address clippy lints
• [4] SFQBWL6P Improving unrecord performance (8 times faster on my tests)
• [5] CCLLB7OI Upgrading to Sanakirja 0.15 + version bump
• [6] VO5OQW4W Removing anyhow in libpijul
• [7] 6YMDOZIB Refactoring apply
• [8] YN63NUZO Sanakirja 1.0
• [9] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).
• [10] I24UEJQL Various post-fire fixes
• [11] I52XSRUH Massive cleanup, and simplification
• [12] T7CAACFB Fixing zombie conflicts (some vertices were wrongly detected alive)
• [13] AD6M434O find_alive performance (matters a lot for unrecord)

Change contents

• edit in libpijul/src/missing_context.rs at line 6
  [3.83368]

  [3.696625]
  + use std::cell::RefCell;
• edit in libpijul/src/missing_context.rs at line 8
  [3.696664]

  [3.26021]
  + use std::rc::Rc;
• replacement in libpijul/src/missing_context.rs at line 77
  [3.698361]→[3.9476:9555](∅→∅)
  − let mut alive = find_alive_up(txn, channel, &mut ws.files, c, change_id)?;
  [3.698361]

  [3.698423]
  + let alive = find_alive_up(

  + txn,

  + channel,

  + &mut ws.files,

  + c,

  + change_id,

  + &mut ws.alive_up_cache,

  + )?;

  + let mut alive = alive.borrow_mut();

  + debug!("files = {:?}", ws.files);
• replacement in libpijul/src/missing_context.rs at line 96
  [3.698828]→[3.698828:698856](∅→∅)
  − &mut alive,
  [3.698828]

  [3.698856]
  + &mut *alive,
• replacement in libpijul/src/missing_context.rs at line 101
  [3.698941]→[3.89178:89250](∅→∅)
  − repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;
  [3.698941]

  [3.699912]
  + repair_regular_up(txn, channel, &*alive, d, EdgeFlags::PSEUDO)?;
• replacement in libpijul/src/missing_context.rs at line 114
  [3.9904]→[3.9904:9968](∅→∅)
  − debug!("put_graph_with_rev {:?} -> {:?}", ancestor, d);
  [3.9904]

  [3.9968]
  + debug!("repair_regular_up {:?} → {:?}", ancestor, d);
• edit in libpijul/src/missing_context.rs at line 122
  [3.10155]→[3.10155:10215](∅→∅)
  − debug!("repair_missing_up {:?} {:?}", ancestor, d);
• edit in libpijul/src/missing_context.rs at line 139
  [3.89460]

  [3.700937]
  + debug!("repair_missing_down_context {:?}", c);
• replacement in libpijul/src/missing_context.rs at line 141
  [3.700978]→[3.700978:701033](∅→∅)
  − let mut alive = find_alive_down(txn, channel, c)?;
  [3.700978]

  [3.701033]
  + let alive = find_alive_down(txn, channel, c, &mut ws.alive_down_cache)?;

  + let mut alive = alive.borrow_mut();

  + debug!("alive = {:?}", alive);
• replacement in libpijul/src/missing_context.rs at line 147
  [3.10353]→[3.701194:701271](∅→∅),[3.701194]→[3.701194:701271](∅→∅)
  − crate::alive::remove_redundant_children(graph, vids, &mut alive, c);
  [3.10353]

  [3.701271]
  + crate::alive::remove_redundant_children(graph, vids, &mut *alive, c);
• edit in libpijul/src/missing_context.rs at line 371
  [3.13269]

  [3.707180]
  + 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>>>>,

  + ),

  + >,
• replacement in libpijul/src/missing_context.rs at line 518
  [3.711431]→[3.711431:711490](∅→∅),[3.711490]→[3.15180:15277](∅→∅)
  − let alive = find_alive_down(txn, channel, p)?;

  − repair_missing_up_context(txn, channel, ws, change_id, inode, dest_vertex, &alive)?;
  [3.711431]

  [3.711583]
  + let alive = find_alive_down(txn, channel, p, &mut ws.alive_down_cache)?;

  + repair_missing_up_context(

  + txn,

  + channel,

  + ws,

  + change_id,

  + inode,

  + dest_vertex,

  + &*alive.borrow(),

  + )?;
• replacement in libpijul/src/find_alive.rs at line 2
  [3.64452]→[3.85222:85242](∅→∅)
  − use crate::HashSet;
  [3.64452]

  [3.32357]
  + use crate::{HashMap, HashSet};

  + use std::cell::RefCell;

  + use std::rc::Rc;

  +

  + type Alive = Rc<RefCell<HashSet<Vertex<ChangeId>>>>;
• replacement in libpijul/src/find_alive.rs at line 12
  [3.763631]→[3.114917:114985](∅→∅),[3.114985]→[2.3601:3715](∅→∅)
  − ) -> Result<HashSet<Vertex<ChangeId>>, BlockError<T::GraphError>> {

  − let mut stack = vec![(

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

  − 0,

  − )];
  [3.763631]

  [3.85243]
  + cache: &mut HashMap<Vertex<ChangeId>, Alive>,

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

  + let mut stack = vec![SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT)];
• replacement in libpijul/src/find_alive.rs at line 16
  [3.85285]→[3.85285:85325](∅→∅),[3.85325]→[3.92:139](∅→∅)
  − let mut alive = HashSet::default();

  − while let Some((elt, len)) = stack.pop() {
  [3.85285]

  [3.134265]
  + let alive = Rc::new(RefCell::new(HashSet::new()));

  + while let Some(elt) = stack.pop() {
• edit in libpijul/src/find_alive.rs at line 22
  [3.134367]

  [3.764136]
  + if let Some(c) = cache.get(vertex) {

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

  + continue;

  + } else {

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

  + }
• replacement in libpijul/src/find_alive.rs at line 42
  [3.184]→[3.184:235](∅→∅)
  − assert!(alive.is_empty());
  [3.184]

  [2.3716]
  + assert!(alive.borrow().is_empty());
• replacement in libpijul/src/find_alive.rs at line 45
  [3.305]→[3.305:352](∅→∅)
  − alive.insert(*vertex);
  [3.305]

  [3.352]
  + alive.borrow_mut().insert(*vertex);
• replacement in libpijul/src/find_alive.rs at line 53
  [3.765010]→[3.457:495](∅→∅)
  − stack.push((*v, len + 1))
  [3.765010]

  [3.765103]
  + stack.push(*v)
• replacement in libpijul/src/find_alive.rs at line 65
  [3.15653]→[3.115136:115204](∅→∅),[3.115204]→[3.85326:85366](∅→∅)
  − ) -> Result<HashSet<Vertex<ChangeId>>, BlockError<T::GraphError>> {

  − let mut alive = HashSet::default();
  [3.15653]

  [3.496]
  + cache: &mut HashMap<Vertex<ChangeId>, (Alive, Alive)>,

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

  + debug!("find alive up: {:?}", vertex0);

  + let alive = Rc::new(RefCell::new(HashSet::default()));

  + let files_ = Rc::new(RefCell::new(HashSet::default()));
• edit in libpijul/src/find_alive.rs at line 81
  [3.135055]

  [3.765934]
  + debug!("vertex = {:?}", vertex);

  + 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

  + };
• replacement in libpijul/src/find_alive.rs at line 115
  [3.789]→[3.5472:5518](∅→∅),[3.16235]→[3.5472:5518](∅→∅),[3.5472]→[3.5472:5518](∅→∅)
  − alive.insert(vertex);
  [3.789]

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

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

  + files_.borrow_mut().insert(vertex);
• replacement in libpijul/src/find_alive.rs at line 123
  [3.833]→[3.420:466](∅→∅),[3.420]→[3.420:466](∅→∅)
  − alive.insert(vertex);
  [3.833]

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

  + alive.borrow_mut().insert(vertex);
• replacement in libpijul/src/find_alive.rs at line 132
  [3.1006]→[3.16532:16574](∅→∅),[3.16532]→[3.16532:16574](∅→∅)
  − alive.insert(vertex);
  [3.1006]

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

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

  + files_.borrow_mut().insert(vertex);
• replacement in libpijul/src/find_alive.rs at line 138
  [3.16640]→[3.768653:768674](∅→∅),[3.768653]→[3.768653:768674](∅→∅)
  − } else {
  [3.16640]

  [3.1007]
  + } else if !is_cached {