comparison rust/hg-core/src/dagops.rs @ 51260:c4f1a790bda8

rust-index: use a `BitVec` instead of plain `Vec` for heads computation

The `Vec` method uses one byte per revision, this uses 1 per 8 revisions,
which improves our memory footprint. For large graphs (10+ millions), this
can make a measurable difference server-side.

I have seen no measurable impact on execution speed.

51259:ed6683d4cb29

//! # Terminology
//! - 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>(

        }
    }
    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(())
}

51260:c4f1a790bda8

//! # Terminology
//! - 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 bitvec::slice::BitSlice;

use super::{Graph, GraphError, Revision, NULL_REVISION};
use crate::{ancestors::AncestorsIterator, BaseRevision};
use std::collections::{BTreeSet, HashSet};

fn remove_parents<S: std::hash::BuildHasher>(

        }
    }
    Ok(())
}

/// Optimized version of `retain_heads` that expects an zeroed bitvec 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 BitSlice,
    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.get_mut(idx).unwrap().commit(true);
            continue;
        }
        for parent in graph.parents(rev)?.iter() {
            if *parent != NULL_REVISION {
                not_heads.get_mut(parent.0 as usize).unwrap().commit(true);
            }
        }
    }
    Ok(())
}