Fixing a caching mistake in find_alive

pmeunier

Dec 15, 2023, 8:04 PM

PNKAJTFZM37FD6XPC3HLVBDT54XDC3SQMFNM32N6TTZ72BVFUKWQC

Dependencies

• [2] JQR4Q2NK Fixing a cache miss/unwrap in find_alive for vertices that have been split during insertion
• [3] RSFUX6ML Correct find_alive cache system
• [4] I24UEJQL Various post-fire fixes
• [5] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).
• [6] YN63NUZO Sanakirja 1.0
• [*] 7NSTS6PK Adding a cache in find_alive to improve performance in some cases
• [*] VO5OQW4W Removing anyhow in libpijul

Change contents

• edit in libpijul/src/find_alive.rs at line 3
  [8.1357]

  [9.32357]
  + // use std::collections::hash_map::Entry;
• edit in libpijul/src/find_alive.rs at line 24
  [3.3096]→[3.3096:3152](∅→∅)
  − cache.insert(*vertex, Some(alive.clone()));
• edit in libpijul/src/find_alive.rs at line 26
  [3.3211]

  [2.0]
  + cache.insert(*vertex, Some(alive.clone()));
• edit in libpijul/src/find_alive.rs at line 114
  [8.2247]

  [3.4849]
  +

  + // Each element of the stack is a pair of (1) an edge pointing to

  + // the position we want to visit next and (2) optionally, a set of

  + // alive vertices found until now.

  +

  + // Every time we find an alive vertex, we add it to the sets of

  + // each element on the path to that vertex.

  +
• edit in libpijul/src/find_alive.rs at line 132
  [3.5111]

  [3.134913]
  + debug!("pop {:?} {:?}", elt, alive);
• edit in libpijul/src/find_alive.rs at line 138
  [3.5228]→[3.5228:5285](∅→∅)
  − cache.insert(vertex, (Some(alive), files_));
• edit in libpijul/src/find_alive.rs at line 140
  [3.5344]

  [2.126]
  + cache.insert(vertex, (Some(alive), files_));
• replacement in libpijul/src/find_alive.rs at line 145
  [3.765862]→[3.5419:5603](∅→∅)
  − } else {

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

  − continue;

  − }

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

  − };
  [3.765862]

  [3.134990]
  + }

  +
• edit in libpijul/src/find_alive.rs at line 161
  [3.6114]

  [3.6114]
  + }

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

  + stack.push((elt, Some((HashSet::new(), HashSet::new()))));
• edit in libpijul/src/find_alive.rs at line 165
  [3.6128]

  [3.6128]
  + continue;

  + }

  +

  + if !visited.insert(elt.dest()) {
• edit in libpijul/src/find_alive.rs at line 171
  [3.6160]

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

  +
• edit in libpijul/src/find_alive.rs at line 244
  [3.7611]

  [3.7611]
  + debug!("just push");