dblsaiko/pijul - Change 7NSTS6PKVQWNUGIUYBRS4GWHJPAV57TOPBTDCOBZ5YYQNFZIZW2QC

Adding a cache in find_alive to improve performance in some cases

Created by pmeunier on January 12, 2022

7NSTS6PKVQWNUGIUYBRS4GWHJPAV57TOPBTDCOBZ5YYQNFZIZW2QC

Dependencies

In channels

main

Change contents

Insertion in libpijul/src/missing_context.rs at line 6 [4.696460]
[3.83368]
[4.696625]
```
use std::cell::RefCell;
```
Insertion in libpijul/src/missing_context.rs at line 8 [4.696460]
[4.696664]
[5.26021]
```
use std::rc::Rc;
```

Replacement in libpijul/src/missing_context.rs at line 77 [4.696460]

B:BD[4.698361] → [6.9476:9555]

    let mut alive = find_alive_up(txn, channel, &mut ws.files, c, change_id)?;

[4.698361]

[4.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 [4.696460]
B:BD[4.698828] → [4.698828:698856]
```
                &mut alive,
```
[4.698828]
[4.698856]
```
                &mut *alive,
```

Replacement in libpijul/src/missing_context.rs at line 101 [4.696460]

B:BD[4.698941] → [7.89178:89250]

        repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;

[4.698941]

[4.699912]

        repair_regular_up(txn, channel, &*alive, d, EdgeFlags::PSEUDO)?;

Replacement in libpijul/src/missing_context.rs at line 114 [4.696460]

B:BD[6.9904] → [6.9904:9968]

        debug!("put_graph_with_rev {:?} -> {:?}", ancestor, d);

[6.9904]

[6.9968]

        debug!("repair_regular_up {:?} → {:?}", ancestor, d);

Deletion in libpijul/src/missing_context.rs at line 122 [4.696460]
B:BD[6.10155] → [6.10155:10215]
```
        debug!("repair_missing_up {:?} {:?}", ancestor, d);
```
Insertion in libpijul/src/missing_context.rs at line 139 [4.696460]
[7.89460]
[4.700937]
```
    debug!("repair_missing_down_context {:?}", c);
```

Replacement in libpijul/src/missing_context.rs at line 141 [4.696460]

B:BD[4.700978] → [4.700978:701033]

    let mut alive = find_alive_down(txn, channel, c)?;

[4.700978]

[4.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 [4.696460]

∅:D[6.10353] → [4.701194:701271]

B:BD[4.701194] → [4.701194:701271]

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

[6.10353]

[4.701271]

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

Insertion in libpijul/src/missing_context.rs at line 371 [4.696460]

[6.13269]

[4.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 [4.696460]

B:BD[4.711431] → [4.711431:711490]

B:BD[4.711490] → [6.15180:15277]

            let alive = find_alive_down(txn, channel, p)?;
            repair_missing_up_context(txn, channel, ws, change_id, inode, dest_vertex, &alive)?;

[4.711431]

[4.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 [4.763306]

B:BD[8.64452] → [3.85222:85242]

use crate::HashSet;

[8.64452]

[5.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 [4.763306]

B:BD[4.763631] → [7.114917:114985]

B:BD[7.114985] → [2.3601:3715]

) -> Result<HashSet<Vertex<ChangeId>>, BlockError<T::GraphError>> {
    let mut stack = vec![(
        SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT),
        0,
    )];

[4.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 [4.763306]

B:BD[3.85285] → [3.85285:85325]

B:BD[3.85325] → [9.92:139]

    let mut alive = HashSet::default();
    while let Some((elt, len)) = stack.pop() {

[3.85285]

[10.134265]

    let alive = Rc::new(RefCell::new(HashSet::new()));
    while let Some(elt) = stack.pop() {

Insertion in libpijul/src/find_alive.rs at line 22 [4.763306]

[10.134367]

[4.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 [4.763306]

B:BD[9.184] → [9.184:235]

                        assert!(alive.is_empty());

[9.184]

[2.3716]

                        assert!(alive.borrow().is_empty());

Replacement in libpijul/src/find_alive.rs at line 45 [4.763306]

B:BD[9.305] → [9.305:352]

                        alive.insert(*vertex);

[9.305]

[9.352]

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

Replacement in libpijul/src/find_alive.rs at line 53 [4.763306]
B:BD[4.765010] → [9.457:495]
```
            stack.push((*v, len + 1))
```
[4.765010]
[4.765103]
```
            stack.push(*v)
```

Replacement in libpijul/src/find_alive.rs at line 65 [4.763306]

B:BD[6.15653] → [7.115136:115204]

B:BD[7.115204] → [3.85326:85366]

) -> Result<HashSet<Vertex<ChangeId>>, BlockError<T::GraphError>> {
    let mut alive = HashSet::default();

[6.15653]

[9.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()));

Insertion in libpijul/src/find_alive.rs at line 81 [4.763306]

[10.135055]

[4.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 [4.763306]

∅:D[9.789] → [11.5472:5518]

∅:D[6.16235] → [11.5472:5518]

B:BD[11.5472] → [11.5472:5518]

                        alive.insert(vertex);

[9.789]

[6.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 [4.763306]

∅:D[9.833] → [12.420:466]

B:BD[12.420] → [12.420:466]

                        alive.insert(vertex);

[9.833]

[6.16444]

                        debug!("is alive {:?}", vertex);
                        alive.borrow_mut().insert(vertex);

Replacement in libpijul/src/find_alive.rs at line 132 [4.763306]

∅:D[9.1006] → [6.16532:16574]

B:BD[6.16532] → [6.16532:16574]

                    alive.insert(vertex);

[9.1006]

[6.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 [4.763306]
∅:D[6.16640] → [4.768653:768674]
B:BD[4.768653] → [4.768653:768674]
```
            } else {
```
[6.16640]
[9.1007]
```
            } else if !is_cached {
```