rhg: faster hg cat when many files are requested

With this patch I'm seeing a ~39ms improvement (220ms -> 181ms) when
running [hg cat] on ~220 files in a ~260k-file repo.

The timing for [hg cat] on an individual file becomes slightly worse
(losing 5ms: 145ms -> 150ms).
A follow-up commit is intended to improve that.

Differential Revision: https://phab.mercurial-scm.org/D11615

rust/hg-core/src/operations/cat.rs

@@ -1,71 +1,80 b''
 // list_tracked_files.rs
 //
 // Copyright 2020 Antoine Cezar <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 use crate::repo::Repo;
 use crate::revlog::revlog::RevlogError;
 use crate::revlog::Node;
 
 use crate::utils::hg_path::HgPathBuf;
 
+use itertools::EitherOrBoth::{Both, Left, Right};
+use itertools::Itertools;
+
 pub struct CatOutput {
     /// Whether any file in the manifest matched the paths given as CLI
     /// arguments
     pub found_any: bool,
     /// The contents of matching files, in manifest order
     pub concatenated: Vec<u8>,
     /// Which of the CLI arguments did not match any manifest file
     pub missing: Vec<HgPathBuf>,
     /// The node ID that the given revset was resolved to
     pub node: Node,
 }
 
 /// Output the given revision of files
 ///
 /// * `root`: Repository root
 /// * `rev`: The revision to cat the files from.
 /// * `files`: The files to output.
 pub fn cat<'a>(
     repo: &Repo,
     revset: &str,
-    files: &'a [HgPathBuf],
+    mut files: Vec<HgPathBuf>,
 ) -> Result<CatOutput, RevlogError> {
     let rev = crate::revset::resolve_single(revset, repo)?;
     let manifest = repo.manifest_for_rev(rev)?;
     let node = *repo
         .changelog()?
         .node_from_rev(rev)
         .expect("should succeed when repo.manifest did");
     let mut bytes = vec![];
-    let mut matched = vec![false; files.len()];
     let mut found_any = false;
+    files.sort_unstable();
+
+    let mut missing = vec![];
 
-    for (manifest_file, node_bytes) in manifest.files_with_nodes() {
-        for (cat_file, is_matched) in files.iter().zip(&mut matched) {
-            if cat_file.as_bytes() == manifest_file.as_bytes() {
-                *is_matched = true;
+    for entry in manifest
+        .files_with_nodes()
+        .merge_join_by(files.iter(), |(manifest_file, _), file| {
+            manifest_file.cmp(&file.as_ref())
+        })
+    {
+        match entry {
+            Left(_) => (),
+            Right(path) => missing.push(path),
+            Both((manifest_file, node_bytes), _) => {
                 found_any = true;
                 let file_log = repo.filelog(manifest_file)?;
                 let file_node = Node::from_hex_for_repo(node_bytes)?;
                 let entry = file_log.data_for_node(file_node)?;
                 bytes.extend(entry.data()?)
             }
         }
     }
 
-    let missing: Vec<_> = files
+    let missing: Vec<HgPathBuf> = missing
         .iter()
-        .zip(&matched)
-        .filter(|pair| !*pair.1)
-        .map(|pair| pair.0.clone())
+        .map(|file| (*(file.as_ref())).to_owned())
         .collect();
     Ok(CatOutput {
         found_any,
         concatenated: bytes,
         missing,
         node,
     })
 }

rust/rhg/src/commands/cat.rs

@@ -1,93 +1,93 b''
 use crate::error::CommandError;
 use clap::Arg;
 use format_bytes::format_bytes;
 use hg::operations::cat;
 use hg::utils::hg_path::HgPathBuf;
 use micro_timer::timed;
 use std::convert::TryFrom;
 
 pub const HELP_TEXT: &str = "
 Output the current or given revision of files
 ";
 
 pub fn args() -> clap::App<'static, 'static> {
     clap::SubCommand::with_name("cat")
         .arg(
             Arg::with_name("rev")
                 .help("search the repository as it is in REV")
                 .short("-r")
                 .long("--rev")
                 .value_name("REV")
                 .takes_value(true),
         )
         .arg(
             clap::Arg::with_name("files")
                 .required(true)
                 .multiple(true)
                 .empty_values(false)
                 .value_name("FILE")
                 .help("Files to output"),
         )
         .about(HELP_TEXT)
 }
 
 #[timed]
 pub fn run(invocation: &crate::CliInvocation) -> Result<(), CommandError> {
     let rev = invocation.subcommand_args.value_of("rev");
     let file_args = match invocation.subcommand_args.values_of("files") {
         Some(files) => files.collect(),
         None => vec![],
     };
 
     let repo = invocation.repo?;
     let cwd = hg::utils::current_dir()?;
     let working_directory = repo.working_directory_path();
     let working_directory = cwd.join(working_directory); // Make it absolute
 
     let mut files = vec![];
     for file in file_args.iter() {
         if file.starts_with("set:") {
             let message = "fileset";
             return Err(CommandError::unsupported(message));
         }
 
         let normalized = cwd.join(&file);
         // TODO: actually normalize `..` path segments etc?
         let dotted = normalized.components().any(|c| c.as_os_str() == "..");
         if file == &"." || dotted {
             let message = "`..` or `.` path segment";
             return Err(CommandError::unsupported(message));
         }
         let stripped = normalized
             .strip_prefix(&working_directory)
             // TODO: error message for path arguments outside of the repo
             .map_err(|_| CommandError::abort(""))?;
         let hg_file = HgPathBuf::try_from(stripped.to_path_buf())
             .map_err(|e| CommandError::abort(e.to_string()))?;
         files.push(hg_file);
     }
     // TODO probably move this to a util function like `repo.default_rev` or
     // something when it's used somewhere else
     let rev = match rev {
         Some(r) => r.to_string(),
         None => format!("{:x}", repo.dirstate_parents()?.p1),
     };
 
-    let output = cat(&repo, &rev, &files).map_err(|e| (e, rev.as_str()))?;
+    let output = cat(&repo, &rev, files).map_err(|e| (e, rev.as_str()))?;
     invocation.ui.write_stdout(&output.concatenated)?;
     if !output.missing.is_empty() {
         let short = format!("{:x}", output.node.short()).into_bytes();
         for path in &output.missing {
             invocation.ui.write_stderr(&format_bytes!(
                 b"{}: no such file in rev {}\n",
                 path.as_bytes(),
                 short
             ))?;
         }
     }
     if output.found_any {
         Ok(())
     } else {
         Err(CommandError::Unsuccessful)
     }
 }