From eb6d0f387ce3495e4263d8dd0866bd0d41e476bc Mon Sep 17 00:00:00 2001
From: Siraaj Khandkar <siraaj@khandkar.net>
Date: Mon, 26 Nov 2018 20:36:23 -0500
Subject: [PATCH] Parallelize file head sampling

---
 dups.ml | 31 ++++++++++++++++++++++---------
 1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/dups.ml b/dups.ml
index 6afba6a..6628d99 100644
--- a/dups.ml
+++ b/dups.ml
@@ -381,6 +381,8 @@ module File : sig
   val lookup : string Stream.t -> t Stream.t
   (** Lookup file info for given paths *)
 
+  val head : t -> len:int -> metrics:M.t -> string
+
   val filter_out_unique_sizes : t Stream.t -> metrics:M.t -> t Stream.t
   val filter_out_unique_heads : t Stream.t -> len:int -> metrics:M.t -> t Stream.t
 end = struct
@@ -444,7 +446,8 @@ end = struct
       ~group:(fun {size; _} -> size)
       ~handle_singleton:(fun (size, _, _) -> M.file_unique_size metrics ~size)
 
-  let head path ~len ~metrics =
+  let head {path; _} ~len ~metrics =
+    M.file_sampled metrics;
     let buf = Bytes.make len ' ' in
     let ic = open_in_bin path in
     let rec read pos len =
@@ -467,10 +470,7 @@ end = struct
   let filter_out_unique_heads files ~len ~metrics =
     filter_out_singletons
       files
-      ~group:(fun {path; _} ->
-        M.file_sampled metrics;
-        head path ~len ~metrics
-      )
+      ~group:(head ~len ~metrics)
       ~handle_singleton:(fun (_, _, files) ->
         let {size; _} = List.hd files in  (* Guaranteed non-empty *)
         M.file_unique_sample metrics ~size
@@ -563,7 +563,20 @@ let main {input; output; ignore; sample = sample_len; njobs} =
   let wt0_group_by_sample = wt1_group_by_size in
   let pt0_group_by_sample = pt1_group_by_size in
   eprintf "[debug] filtering-out files with unique heads\n%!";
-  let files = File.filter_out_unique_heads files ~len:sample_len ~metrics in
+  let files =
+    if njobs > 1 then begin
+      let q = Queue.create () in
+      files
+        |> Stream.bag_map ~njobs ~f:(File.head ~len:sample_len ~metrics)
+        |> Stream.group_by ~f:snd
+        |> Stream.map ~f:(fun (d, n, pairs) -> (d, n, List.map pairs ~f:fst))
+        |> Stream.filter ~f:(fun (_, n, _) -> n > 1)
+        |> Stream.iter ~f:(fun (_, _, fs) -> List.iter fs ~f:(fun f -> Queue.add f q))
+        ;
+      Stream.of_queue q
+    end else
+      File.filter_out_unique_heads files ~len:sample_len ~metrics
+  in
   let pt1_group_by_sample = time_proc () in
   let wt1_group_by_sample = time_wall () in
 
@@ -572,10 +585,10 @@ let main {input; output; ignore; sample = sample_len; njobs} =
   eprintf "[debug] hashing\n%!";
   let groups =
     if njobs > 1 then
-      let digests =
+      let with_digests =
         Stream.bag_map files ~njobs ~f:(fun {File.path; _} -> Digest.file path)
       in
-      Stream.map (Stream.group_by digests ~f:(fun (_, d) -> d)) ~f:(
+      Stream.map (Stream.group_by with_digests ~f:snd) ~f:(
         fun (digest, n, file_digest_pairs) ->
           let files =
             List.map file_digest_pairs ~f:(fun (file, _) ->
@@ -632,7 +645,7 @@ let get_opt () : opt =
   let output = ref Stdout in
   let ignore = ref (fun _ -> false) in
   let sample = ref 512 in
-  let njobs  = ref 8 in
+  let njobs  = ref 6 in
   let spec =
     [ ( "-out"
       , Arg.String (fun path ->
-- 
2.20.1