directory size computed with a pool of threads

It's a little complicated but way faster than with just one thread.

5 files changed, 176 insertions, 32 deletions

diff --git a/Cargo.lock b/Cargo.lock
index a0483c4..f09ce5c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -15,6 +15,14 @@ dependencies = [
 ]
 
 [[package]]
+name = "arrayvec"
+version = "0.4.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "atty"
 version = "0.2.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -34,6 +42,7 @@ name = "broot"
 version = "0.6.2"
 dependencies = [
  "clap 2.32.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "custom_error 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "directories 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "glob 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -87,6 +96,67 @@ dependencies = [
 ]
 
 [[package]]
+name = "crossbeam"
+version = "0.7.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-channel 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-epoch 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "crossbeam-channel"
+version = "0.3.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "crossbeam-deque"
+version = "0.7.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "crossbeam-epoch 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.7.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)",
+ "cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "memoffset 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "scopeguard 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "crossbeam-queue"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.6.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "custom_error"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -153,6 +223,16 @@ version = "2.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "memoffset"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "nodrop"
+version = "0.1.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "num-integer"
 version = "0.1.39"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -199,6 +279,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "scopeguard"
+version = "0.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "serde"
 version = "1.0.88"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -214,6 +299,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "smallvec"
+version = "0.6.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "strsim"
 version = "0.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -321,6 +411,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 [metadata]
 "checksum aho-corasick 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)" = "81ce3d38065e618af2d7b77e10c5ad9a069859b4be3c2250f674af3840d9c8a5"
 "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
+"checksum arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)" = "92c7fb76bc8826a8b33b4ee5bb07a247a81e76764ab4d55e8f73e3a4d8808c71"
 "checksum atty 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "9a7d5b8723950951411ee34d271d99dddcc2035a16ab25310ea2c8cfd4369652"
 "checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
 "checksum byteorder 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a019b10a2a7cdeb292db131fc8113e57ea2a908f6e7894b0c3c671893b65dbeb"
@@ -328,6 +419,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "082bb9b28e00d3c9d39cc03e64ce4cea0f1bb9b3fde493f0cbc008472d22bdf4"
 "checksum chrono 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "45912881121cb26fad7c38c17ba7daa18764771836b34fab7d3fbd93ed633878"
 "checksum clap 2.32.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b957d88f4b6a63b9d70d5f454ac8011819c6efa7727858f458ab71c756ce2d3e"
+"checksum crossbeam 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b14492071ca110999a20bf90e3833406d5d66bfd93b4e52ec9539025ff43fe0d"
+"checksum crossbeam-channel 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "0f0ed1a4de2235cabda8558ff5840bffb97fcb64c97827f354a451307df5f72b"
+"checksum crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b18cd2e169ad86297e6bc0ad9aa679aee9daa4f19e8163860faf7c164e4f5a71"
+"checksum crossbeam-epoch 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "04c9e3102cc2d69cd681412141b390abd55a362afc1540965dad0ad4d34280b4"
+"checksum crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7c979cd6cfe72335896575c6b5688da489e420d36a27a0b9eb0c73db574b4a4b"
+"checksum crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "f8306fcef4a7b563b76b7dd949ca48f52bc1141aa067d2ea09565f3e2652aa5c"
 "checksum custom_error 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9efb928d6df5bf5686767e19c842138d5f4182acd8f8d23663a87acc1aa38b0b"
 "checksum directories 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "72d337a64190607d4fcca2cb78982c5dd57f4916e19696b48a575fa746b6cb0f"
 "checksum fs_extra 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5f2a4a2034423744d2cc7ca2068453168dcdb82c438419e639a26bd87839c674"
@@ -338,14 +435,18 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum libc 0.2.48 (registry+https://github.com/rust-lang/crates.io-index)" = "e962c7641008ac010fa60a7dfdc1712449f29c44ef2d4702394aea943ee75047"
 "checksum log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c84ec4b527950aa83a329754b01dbe3f58361d1c5efacd1f6d68c494d08a17c6"
 "checksum memchr 2.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "2efc7bc57c883d4a4d6e3246905283d8dae951bb3bd32f49d6ef297f546e1c39"
+"checksum memoffset 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "0f9dc261e2b62d7a622bf416ea3c5245cdd5d9a7fcc428c0d06804dfce1775b3"
+"checksum nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)" = "2f9667ddcc6cc8a43afc9b7917599d7216aa09c463919ea32c59ed6cac8bc945"
 "checksum num-integer 0.1.39 (registry+https://github.com/rust-lang/crates.io-index)" = "e83d528d2677f0518c570baf2b7abdcf0cd2d248860b68507bdcb3e91d4c0cea"
 "checksum num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "0b3a5d7cc97d6d30d8b9bc8fa19bf45349ffe46241e8816f50f62f6d6aaabee1"
 "checksum redox_syscall 0.1.51 (registry+https://github.com/rust-lang/crates.io-index)" = "423e376fffca3dfa06c9e9790a9ccd282fafb3cc6e6397d01dbf64f9bacc6b85"
 "checksum redox_termios 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7e891cfe48e9100a70a3b6eb652fef28920c117d366339687bd5576160db0f76"
 "checksum regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "37e7cbbd370869ce2e8dff25c7018702d10b21a20ef7135316f8daecd6c25b7f"
 "checksum regex-syntax 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "8c2f35eedad5295fdf00a63d7d4b238135723f92b434ec06774dad15c7ab0861"
+"checksum scopeguard 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "94258f53601af11e6a49f722422f6e3425c52b06245a5cf9bc09908b174f5e27"
 "checksum serde 1.0.88 (registry+https://github.com/rust-lang/crates.io-index)" = "9f301d728f2b94c9a7691c90f07b0b4e8a4517181d9461be94c04bddeb4bd850"
 "checksum simplelog 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e95345f185d5adeb8ec93459d2dc99654e294cc6ccf5b75414d8ea262de9a13"
+"checksum smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "c4488ae950c49d403731982257768f48fada354a5203fe81f9bb6f43ca9002be"
 "checksum strsim 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "bb4f380125926a99e52bc279241539c018323fab05ad6368b56f93d9369ff550"
 "checksum term 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "5e6b677dd1e8214ea1ef4297f85dbcbed8e8cdddb561040cc998ca2551c37561"
 "checksum termion 1.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "689a3bdfaab439fd92bc87df5c4c78417d3cbe537487274e9b0b2dce76e92096"
diff --git a/Cargo.toml b/Cargo.toml
index b76cdaf..3fb6e6f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -23,6 +23,7 @@ clap = "2.32"
 glob = "0.2"
 users = "0.8"
 jemallocator = "0.1.9"
+crossbeam = "0.7"
 
 [profile.release]
 lto = true
diff --git a/src/file_sizes.rs b/src/file_sizes.rs
index 496ddde..76d38ee 100644
--- a/src/file_sizes.rs
+++ b/src/file_sizes.rs
@@ -9,8 +9,14 @@ use std::fs;
 use std::ops::AddAssign;
 use std::os::unix::fs::MetadataExt;
 use std::path::{Path, PathBuf};
-use std::sync::Mutex;
+use std::sync::{Mutex};
 use std::time::Instant;
+use std::thread;
+use crossbeam::channel::unbounded;
+use crossbeam::sync::WaitGroup;
+use std::sync::Arc;
+use std::sync::atomic::{AtomicIsize, AtomicUsize, Ordering};
+use std::time::Duration;
 
 const SIZE_NAMES: &[&str] = &["", "K", "M", "G", "T", "P", "E", "Z", "Y"]; // Y: for when your disk is bigger than 1024 ZB
 
@@ -36,41 +42,75 @@ impl Size {
         if let Some(s) = size_cache.get(path) {
             return Some(*s);
         }
+
         let start = Instant::now();
-        let mut s = Size::from(0);
-        let mut dirs: Vec<PathBuf> = Vec::new();
-        dirs.push(PathBuf::from(path));
-        let mut inodes: HashSet<u64> = HashSet::new(); // to avoid counting twice an inode
-        let mut nb_duplicate_inodes = 0;
-        while let Some(open_dir) = dirs.pop() {
-            if let Ok(entries) = fs::read_dir(&open_dir) {
-                for e in entries {
-                    if let Ok(e) = e {
-                        if let Ok(md) = e.metadata() {
-                            if md.is_dir() {
-                                dirs.push(e.path());
-                            } else if md.nlink() > 1 && !inodes.insert(md.ino()) {
-                                // it was already in the set
-                                nb_duplicate_inodes += 1;
-                                continue; // let's not add the size
+        let inodes = Arc::new(Mutex::new(HashSet::<u64>::new())); // to avoid counting twice an inode
+        let size = Arc::new(AtomicUsize::new(0));
+
+        let (dirs_sender, dirs_receiver) = unbounded();
+        // busy is the number of directories which are either being processed or queued
+        // We use this count to determine when threads can stop waiting for tasks
+        let busy = Arc::new(AtomicIsize::new(0));
+        busy.fetch_add(1, Ordering::Relaxed);
+        dirs_sender.send(Some(PathBuf::from(path))).unwrap();
+        let wg = WaitGroup::new();
+        let period = Duration::from_micros(50);
+        for _ in 0..8 {
+            let size = Arc::clone(&size);
+            let busy = Arc::clone(&busy);
+            let wg = wg.clone();
+            let (dirs_sender, dirs_receiver) = (dirs_sender.clone(), dirs_receiver.clone());
+            let tl = tl.clone();
+            let inodes = inodes.clone();
+            thread::spawn(move || {
+                loop {
+                    let o = dirs_receiver.recv_timeout(period);
+                    if let Ok(Some(open_dir)) = o {
+                        if let Ok(entries) = fs::read_dir(&open_dir) {
+                            for e in entries {
+                                if let Ok(e) = e {
+                                    if let Ok(md) = e.metadata() {
+                                        if md.is_dir() {
+                                            busy.fetch_add(1, Ordering::Relaxed);
+                                            dirs_sender.send(Some(e.path())).unwrap();
+                                        } else if md.nlink() > 1 {
+                                            let mut inodes = inodes.lock().unwrap();
+                                            if !inodes.insert(md.ino()) {
+                                                // it was already in the set
+                                                continue; // let's not add the size
+                                            }
+                                        }
+                                        size.fetch_add(md.len() as usize, Ordering::Relaxed);
+                                    }
+                                }
                             }
-                            s += Size::from(md.len());
                         }
+                        busy.fetch_sub(1, Ordering::Relaxed);
+                        dirs_sender.send(None).unwrap();
+                    } else {
+                        let busy_count = busy.load(Ordering::Relaxed);
+                        if busy_count < 1 {
+                            break;
+                        }
+                    }
+                    if tl.is_expired() {
+                        break;
                     }
                 }
-            }
-            if tl.is_expired() {
-                return None;
-            }
+                drop(wg);
+            });
         }
+        wg.wait();
+
+        if tl.is_expired() {
+            return None;
+        }
+        let size: usize = size.load(Ordering::Relaxed);
+        let size: u64 = size as u64;
+        let s = Size::from(size);
+
         size_cache.insert(PathBuf::from(path), s);
         debug!("size computation for {:?} took {:?}", path, start.elapsed());
-        if nb_duplicate_inodes > 0 {
-            debug!(
-                " (found {} inodes used more than once)",
-                nb_duplicate_inodes
-            );
-        }
         Some(s)
     }
 
diff --git a/src/skin_conf.rs b/src/skin_conf.rs
index 2893af8..4cf8fb6 100644
--- a/src/skin_conf.rs
+++ b/src/skin_conf.rs
@@ -52,12 +52,8 @@ macro_rules! make_parseurs {
                 return Ok(format!("{}", Bg(Reset)));
             }
             $(
-                debug!("comparing {} and {}", raw, stringify!($name));
                 if raw.eq_ignore_ascii_case(stringify!($name)) {
-                    debug!(" -> ok");
                     return Ok(format!("{}", Bg($name)));
-                } else {
-                    debug!(" -> not ok");
                 }
             )*
             if let Some(level) = parse_gray(raw)? {
diff --git a/src/task_sync.rs b/src/task_sync.rs
index 1380da2..3a34e49 100644
--- a/src/task_sync.rs
+++ b/src/task_sync.rs
@@ -16,6 +16,12 @@ impl TaskLifetime {
             external_value: Arc::clone(external_value),
         }
     }
+    pub fn clone(&self) -> TaskLifetime {
+        TaskLifetime {
+            initial_value: self.initial_value,
+            external_value: Arc::clone(&self.external_value),
+        }
+    }
     pub fn unlimited() -> TaskLifetime {
         TaskLifetime {
             initial_value: 0,