diff --git a/rust/hg-core/src/copy_tracing.rs b/rust/hg-core/src/copy_tracing.rs
--- a/rust/hg-core/src/copy_tracing.rs
+++ b/rust/hg-core/src/copy_tracing.rs
@@ -12,9 +12,9 @@
 
 pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
 
-type PathToken = HgPathBuf;
+type PathToken = usize;
 
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug, PartialEq, Copy)]
 struct TimeStampedPathCopy {
     /// revision at which the copy information was added
     rev: Revision,
@@ -314,6 +314,34 @@
     SecondParent,
 }
 
+#[derive(Clone, Debug, Default)]
+struct TwoWayPathMap {
+    token: HashMap<HgPathBuf, PathToken>,
+    path: HashMap<PathToken, HgPathBuf>,
+}
+
+impl TwoWayPathMap {
+    fn tokenize(&mut self, path: &HgPath) -> PathToken {
+        match self.token.get(path) {
+            Some(a) => *a,
+            None => {
+                let a = self.token.len();
+                let buf = path.to_owned();
+                self.path.insert(a, buf.clone());
+                self.token.insert(buf, a);
+                a
+            }
+        }
+    }
+
+    fn untokenize(&self, token: PathToken) -> &HgPathBuf {
+        match self.path.get(&token) {
+            Some(path) => path,
+            None => panic!("Unknown token: {}", token),
+        }
+    }
+}
+
 /// Same as mercurial.copies._combine_changeset_copies, but in Rust.
 ///
 /// Arguments are:
@@ -337,6 +365,8 @@
     let mut all_copies = HashMap::new();
     let mut oracle = AncestorOracle::new(is_ancestor);
 
+    let mut path_map = TwoWayPathMap::default();
+
     for rev in revs {
         let mut d: DataHolder<D> = DataHolder { data: None };
         let (p1, p2, changes) = rev_info(rev, &mut d);
@@ -352,6 +382,7 @@
             if let Some(parent_copies) = parent_copies {
                 // combine it with data for that revision
                 let vertex_copies = add_from_changes(
+                    &mut path_map,
                     &parent_copies,
                     &changes,
                     Parent::FirstParent,
@@ -368,6 +399,7 @@
             if let Some(parent_copies) = parent_copies {
                 // combine it with data for that revision
                 let vertex_copies = add_from_changes(
+                    &mut path_map,
                     &parent_copies,
                     &changes,
                     Parent::SecondParent,
@@ -382,6 +414,7 @@
                     // If we got data from both parents, We need to combine
                     // them.
                     Some(copies) => Some(merge_copies_dict(
+                        &path_map,
                         vertex_copies,
                         copies,
                         &changes,
@@ -406,7 +439,9 @@
     let mut result = PathCopies::default();
     for (dest, tt_source) in tt_result {
         if let Some(path) = tt_source.path {
-            result.insert(dest, path);
+            let path_dest = path_map.untokenize(dest).to_owned();
+            let path_path = path_map.untokenize(path).to_owned();
+            result.insert(path_dest, path_path);
         }
     }
     result
@@ -441,6 +476,7 @@
 /// Combine ChangedFiles with some existing PathCopies information and return
 /// the result
 fn add_from_changes(
+    path_map: &mut TwoWayPathMap,
     base_copies: &TimeStampedPathCopies,
     changes: &ChangedFiles,
     parent: Parent,
@@ -449,9 +485,11 @@
     let mut copies = base_copies.clone();
     for action in changes.iter_actions(parent) {
         match action {
-            Action::Copied(dest, source) => {
+            Action::Copied(path_dest, path_source) => {
+                let dest = path_map.tokenize(path_dest);
+                let source = path_map.tokenize(path_source);
                 let entry;
-                if let Some(v) = base_copies.get(source) {
+                if let Some(v) = base_copies.get(&source) {
                     entry = match &v.path {
                         Some(path) => Some((*(path)).to_owned()),
                         None => Some(source.to_owned()),
@@ -469,18 +507,19 @@
                 };
                 copies.insert(dest.to_owned(), ttpc);
             }
-            Action::Removed(f) => {
+            Action::Removed(deleted_path) => {
                 // We must drop copy information for removed file.
                 //
                 // We need to explicitly record them as dropped to
                 // propagate this information when merging two
                 // TimeStampedPathCopies object.
-                if copies.contains_key(f.as_ref()) {
+                let deleted = path_map.tokenize(deleted_path);
+                if copies.contains_key(&deleted) {
                     let ttpc = TimeStampedPathCopy {
                         rev: current_rev,
                         path: None,
                     };
-                    copies.insert(f.to_owned(), ttpc);
+                    copies.insert(deleted, ttpc);
                 }
             }
         }
@@ -493,6 +532,7 @@
 /// In case of conflict, value from "major" will be picked, unless in some
 /// cases. See inline documentation for details.
 fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(
+    path_map: &TwoWayPathMap,
     mut minor: TimeStampedPathCopies,
     mut major: TimeStampedPathCopies,
     changes: &ChangedFiles,
@@ -505,7 +545,9 @@
         |dest: &PathToken,
          src_minor: &TimeStampedPathCopy,
          src_major: &TimeStampedPathCopy| {
-            compare_value(changes, oracle, dest, src_minor, src_major)
+            compare_value(
+                path_map, changes, oracle, dest, src_minor, src_major,
+            )
         };
     if minor.is_empty() {
         major
@@ -635,6 +677,7 @@
 /// decide which side prevails in case of conflicting values
 #[allow(clippy::if_same_then_else)]
 fn compare_value<A: Fn(Revision, Revision) -> bool>(
+    path_map: &TwoWayPathMap,
     changes: &ChangedFiles,
     oracle: &mut AncestorOracle<A>,
     dest: &PathToken,
@@ -656,7 +699,8 @@
         // same rev. So this is the same value.
         unreachable!();
     } else {
-        let action = changes.get_merge_case(&dest);
+        let dest_path = path_map.untokenize(*dest);
+        let action = changes.get_merge_case(dest_path);
         if src_major.path.is_none() && action == MergeCase::Salvaged {
             // If the file is "deleted" in the major side but was
             // salvaged by the merge, we keep the minor side alive