Mercurial > hg
diff 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.
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Wed, 29 Nov 2023 15:58:24 -0500 |
parents | ed6683d4cb29 |
children |
line wrap: on
line diff
--- a/rust/hg-core/src/dagops.rs Wed Nov 29 10:04:41 2023 -0500 +++ b/rust/hg-core/src/dagops.rs Wed Nov 29 15:58:24 2023 -0500 @@ -12,6 +12,8 @@ //! 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}; @@ -81,26 +83,26 @@ 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`. +/// 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 [bool], + 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[idx] = true; + not_heads.get_mut(idx).unwrap().commit(true); continue; } for parent in graph.parents(rev)?.iter() { if *parent != NULL_REVISION { - not_heads[parent.0 as usize] = true; + not_heads.get_mut(parent.0 as usize).unwrap().commit(true); } } }