comparison rust/hg-core/src/dagops.rs @ 51259:ed6683d4cb29

rust-index: implement faster retain heads using a vec instead of a hashset

This is the same optimization that the C index does, we're only catching up
now because this showed up as slow in benchmarking.

51258:8b89f7cc953a

//! - By *relative heads* of a collection of revision numbers (`Revision`), we
//!   mean those revisions that have no children among the collection.
//! - Similarly *relative roots* of a collection of `Revision`, we mean those
//!   whose parents, if any, don't belong to the collection.
use super::{Graph, GraphError, Revision, NULL_REVISION};
use crate::ancestors::AncestorsIterator;
use std::collections::{BTreeSet, HashSet};

fn remove_parents<S: std::hash::BuildHasher>(
    graph: &impl Graph,
    rev: Revision,

    // mutating
    let as_vec: Vec<Revision> = revs.iter().cloned().collect();
    for rev in as_vec {
        if rev != NULL_REVISION {
            remove_parents(graph, rev, revs)?;
        }
    }
    Ok(())
}

51259:ed6683d4cb29

//! - By *relative heads* of a collection of revision numbers (`Revision`), we
//!   mean those revisions that have no children among the collection.
//! - Similarly *relative roots* of a collection of `Revision`, we mean those
//!   whose parents, if any, don't belong to the collection.
use super::{Graph, GraphError, Revision, NULL_REVISION};
use crate::{ancestors::AncestorsIterator, BaseRevision};
use std::collections::{BTreeSet, HashSet};

fn remove_parents<S: std::hash::BuildHasher>(
    graph: &impl Graph,
    rev: Revision,

    // mutating
    let as_vec: Vec<Revision> = revs.iter().cloned().collect();
    for rev in as_vec {
        if rev != NULL_REVISION {
            remove_parents(graph, rev, revs)?;
        }
    }
    Ok(())
}

/// Optimized version of `retain_heads` that expects an zeroed array of the size
/// of the graph, to act as a faster but less space-efficient `HashSet`.
///
/// # Panics
///
/// Can panic if `not_heads` is shorten than the length of graph.
pub fn retain_heads_fast(
    graph: &impl Graph,
    not_heads: &mut [bool],
    filtered_revs: &HashSet<Revision>,
) -> Result<(), GraphError> {
    for idx in (0..not_heads.len()).rev() {
        let rev = Revision(idx as BaseRevision);
        if !not_heads[idx] && filtered_revs.contains(&rev) {
            not_heads[idx] = true;
            continue;
        }
        for parent in graph.parents(rev)?.iter() {
            if *parent != NULL_REVISION {
                not_heads[parent.0 as usize] = true;
            }
        }
    }
    Ok(())
}