Repository: pkolaczk/fclones (language: rust)

Issue:
Perform partial hashing in order of physical block placement
This [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.300.1104&rep=rep1&type=pdf) reports that ordering accesses by inode id or by physical block location retrieved with ioctl fiemap API can give substantial performance improvements.

These techniques could be applied for the partial hashing phase of `fclones`, where seek time and rotational latency are the major bottleneck.




Discussion / hints:

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index a4f9059..7363b9f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -64,9 +64,9 @@ checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
 
 [[package]]
 name = "block-utils"
-version = "0.8.2"
+version = "0.10.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "76f0c56072fd12b6dcc19bd520169207b828d25db508e230d9696ed15f2e9d38"
+checksum = "ce0299b117aefd8f17ce6edf847e23bf4c0aeae195128fb2fc46d873e29fc9b5"
 dependencies = [
  "fstab",
  "log 0.4.14",
@@ -98,9 +98,9 @@ checksum = "415301c9de11005d4b92193c0eb7ac7adc37e5a49e0ac9bed0a42343512744b8"
 
 [[package]]
 name = "byteorder"
-version = "1.4.2"
+version = "1.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ae44d1a3d5a19df61dd0c8beb138458ac2a53a7ac09eba97d55592540004306b"
+checksum = "14c189c53d098945499cdfa7ecc63567cf3886b3332b312a5b4585d8d3a6a610"
 
 [[package]]
 name = "bytesize"
@@ -173,9 +173,9 @@ dependencies = [
 
 [[package]]
 name = "console"
-version = "0.13.0"
+version = "0.14.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a50aab2529019abfabfa93f1e6c41ef392f91fbf179b347a7e96abb524884a08"
+checksum = "3993e6445baa160675931ec041a5e03ca84b9c6e32a056150d3aa2bdda0a1f45"
 dependencies = [
  "encode_unicode",
  "lazy_static",
@@ -184,7 +184,6 @@ dependencies = [
  "terminal_size",
  "unicode-width",
  "winapi",
- "winapi-util",
 ]
 
 [[package]]
@@ -238,28 +237,26 @@ dependencies = [
 
 [[package]]
 name = "crossbeam-epoch"
-version = "0.9.2"
+version = "0.9.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d60ab4a8dba064f2fbb5aa270c28da5cf4bbd0e72dae1140a6b0353a779dbe00"
+checksum = "2584f639eb95fea8c798496315b297cf81b9b58b6d30ab066a75455333cf4b12"
 dependencies = [
  "cfg-if 1.0.0",
  "crossbeam-utils",
  "lazy_static",
- "loom",
  "memoffset",
  "scopeguard",
 ]
 
 [[package]]
 name = "crossbeam-utils"
-version = "0.8.2"
+version = "0.8.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bae8f328835f8f5a6ceb6a7842a7f2d0c03692adb5c889347235d59194731fe3"
+checksum = "e7e9d99fa91428effe99c5c6d4634cdeba32b8cf784fc428a2a687f61a952c49"
 dependencies = [
  "autocfg",
  "cfg-if 1.0.0",
  "lazy_static",
- "loom",
 ]
 
 [[package]]
@@ -270,9 +267,9 @@ checksum = "7a81dae078cea95a014a339291cec439d2f232ebe854a9d672b796c6afafa9b7"
 
 [[package]]
 name = "csv"
-version = "1.1.5"
+version = "1.1.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "f9d58633299b24b515ac72a3f869f8b91306a3cec616a602843a383acd6f9e97"
+checksum = "22813a6dc45b335f9bade10bf7271dc477e81113e89eb251a0bc2a8a81c536e1"
 dependencies = [
  "bstr",
  "csv-core",
@@ -327,7 +324,7 @@ checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f"
 
 [[package]]
 name = "fclones"
-version = "0.8.1"
+version = "0.9.0"
 dependencies = [
  "atomic-counter",
  "block-utils",
@@ -336,18 +333,22 @@ dependencies = [
  "chrono",
  "clap",
  "console 0.11.3",
+ "crossbeam-utils",
  "csv",
  "dashmap",
  "dunce",
+ "fiemap",
  "indicatif",
  "indoc",
  "itertools",
+ "lazy-init",
  "libc",
  "maplit",
  "metrohash",
  "nix",
  "nom",
  "pcre2",
+ "rand",
  "rayon",
  "regex",
  "serde",
@@ -363,25 +364,21 @@ dependencies = [
 ]
 
 [[package]]
-name = "fstab"
-version = "0.3.1"
+name = "fiemap"
+version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "f3e033bb8a160dab4557780f3537dee55547cbc27e82687baed5b6d305a3d653"
+checksum = "084632422a59165633e28f8436545a6694b3d659405ceb3be0a441d4bfbf25d1"
 dependencies = [
- "log 0.3.9",
+ "bitflags",
 ]
 
 [[package]]
-name = "generator"
-version = "0.6.23"
+name = "fstab"
+version = "0.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8cdc09201b2e8ca1b19290cf7e65de2246b8e91fb6874279722189c4de7b94dc"
+checksum = "f3e033bb8a160dab4557780f3537dee55547cbc27e82687baed5b6d305a3d653"
 dependencies = [
- "cc",
- "libc",
- "log 0.4.14",
- "rustc_version",
- "winapi",
+ "log 0.3.9",
 ]
 
 [[package]]
@@ -419,7 +416,7 @@ version = "0.14.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "49a68371cf417889c9d7f98235b7102ea7c54fc59bcbd22f3dea785be9d27e40"
 dependencies = [
- "console 0.13.0",
+ "console 0.14.1",
  "lazy_static",
  "number_prefix",
  "rayon",
@@ -464,6 +461,12 @@ version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "dd25036021b0de88a0aff6b850051563c6516d0bf53f8638938edbb9de732736"
 
+[[package]]
+name = "lazy-init"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "23517540be87a91d06324e6bf6286ba8214171123ee8862ae9a5e7d938d71815"
+
 [[package]]
 name = "lazy_static"
 version = "1.4.0"
@@ -485,9 +488,9 @@ dependencies = [
 
 [[package]]
 name = "libc"
-version = "0.2.86"
+version = "0.2.91"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b7282d924be3275cec7f6756ff4121987bc6481325397dde6ba3e7802b1a8b1c"
+checksum = "8916b1f6ca17130ec6568feccee27c156ad12037880833a3b842a823236502e7"
 
 [[package]]
 name = "libudev-sys"
@@ -517,17 +520,6 @@ dependencies = [
  "cfg-if 1.0.0",
 ]
 
-[[package]]
-name = "loom"
-version = "0.4.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d44c73b4636e497b4917eb21c33539efa3816741a2d3ff26c6316f1b529481a4"
-dependencies = [
- "cfg-if 1.0.0",
- "generator",
- "scoped-tls",
-]
-
 [[package]]
 name = "maplit"
 version = "1.0.2"
@@ -542,9 +534,9 @@ checksum = "0ee1c47aaa256ecabcaea351eae4a9b01ef39ed810004e298d2511ed284b1525"
 
 [[package]]
 name = "memoffset"
-version = "0.6.1"
+version = "0.6.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "157b4208e3059a8f9e78d559edc658e13df41410cb3ae03979c83130067fdd87"
+checksum = "f83fb6581e8ed1f85fd45c116db8405483899489e38406156c25eb743554361d"
 dependencies = [
  "autocfg",
 ]
@@ -626,9 +618,9 @@ checksum = "17b02fc0ff9a9e4b35b3342880f48e896ebf69f2967921fe8646bf5b7125956a"
 
 [[package]]
 name = "once_cell"
-version = "1.5.2"
+version = "1.7.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "13bd41f508810a131401606d54ac32a467c97172d74ba7662562ebba5ad07fa0"
+checksum = "af8b08b04175473088b46763e51ee54da5f9a164bc162f615b91bc179dbf15a3"
 
 [[package]]
 name = "pcre2"
@@ -657,6 +649,12 @@ version = "0.3.19"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3831453b3449ceb48b6d9c7ad7c96d5ea673e9b470a1dc578c2ce6521230884c"
 
+[[package]]
+name = "ppv-lite86"
+version = "0.2.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ac74c624d6b2d21f425f752262f42188365d7b8ff1aff74c82e45136510a4857"
+
 [[package]]
 name = "proc-macro-error"
 version = "1.0.4"
@@ -705,6 +703,46 @@ dependencies = [
  "proc-macro2",
 ]
 
+[[package]]
+name = "rand"
+version = "0.8.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0ef9e7e66b4468674bfcb0c81af8b7fa0bb154fa9f28eb840da5c447baeb8d7e"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+ "rand_hc",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e12735cf05c9e10bf21534da50a147b924d555dc7a547c42e6bb2d5b6017ae0d"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34cf66eb183df1c5876e2dcf6b13d57340741e8dc255b48e40a26de954d06ae7"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
+name = "rand_hc"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3190ef7066a446f2e7f42e239d161e905420ccab01eb967c9eb27d21b2322a73"
+dependencies = [
+ "rand_core",
+]
+
 [[package]]
 name = "rayon"
 version = "1.5.0"
@@ -732,14 +770,13 @@ dependencies = [
 
 [[package]]
 name = "regex"
-version = "1.3.9"
+version = "1.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9c3780fcf44b193bc4d09f36d2a3c87b251da4a046c87795a0d35f4f927ad8e6"
+checksum = "957056ecddbeba1b26965114e191d2e8589ce74db242b6ea25fc4062427a5c19"
 dependencies = [
  "aho-corasick",
  "memchr",
  "regex-syntax",
- "thread_local",
 ]
 
 [[package]]
@@ -753,18 +790,9 @@ dependencies = [
 
 [[package]]
 name = "regex-syntax"
-version = "0.6.22"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b5eb417147ba9860a96cfe72a0b93bf88fee1744b5636ec99ab20c1aa9376581"
-
-[[package]]
-name = "rustc_version"
-version = "0.2.3"
+version = "0.6.23"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a"
-dependencies = [
- "semver",
-]
+checksum = "24d5f089152e60f62d28b835fbff2cd2e8dc0baf1ac13343bef92ab7eed84548"
 
 [[package]]
 name = "ryu"
@@ -772,47 +800,26 @@ version = "1.0.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "71d301d4193d031abdd79ff7e3dd721168a9572ef3fe51a1517aba235bd8f86e"
 
-[[package]]
-name = "scoped-tls"
-version = "1.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ea6a9290e3c9cf0f18145ef7ffa62d68ee0bf5fcd651017e586dc7fd5da448c2"
-
 [[package]]
 name = "scopeguard"
 version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
 
-[[package]]
-name = "semver"
-version = "0.9.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403"
-dependencies = [
- "semver-parser",
-]
-
-[[package]]
-name = "semver-parser"
-version = "0.7.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
-
 [[package]]
 name = "serde"
-version = "1.0.123"
+version = "1.0.125"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "92d5161132722baa40d802cc70b15262b98258453e85e5d1d365c757c73869ae"
+checksum = "558dc50e1a5a5fa7112ca2ce4effcb321b0300c0d4ccf0776a9f60cd89031171"
 dependencies = [
  "serde_derive",
 ]
 
 [[package]]
 name = "serde_derive"
-version = "1.0.123"
+version = "1.0.125"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9391c295d64fc0abb2c556bad848f33cb8296276b1ad2677d1ae1ace4f258f31"
+checksum = "b093b7a2bb58203b5da3056c05b4ec1fed827dcfdb37347a8841695263b3d06d"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -821,9 +828,9 @@ dependencies = [
 
 [[package]]
 name = "serde_json"
-version = "1.0.62"
+version = "1.0.64"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ea1c6153794552ea7cf7cf63b1231a25de00ec90db326ba6264440fa08e31486"
+checksum = "799e97dc9fdae36a5c8b8f2cae9ce2ee9fdce2058c57a93e6099d919fd982f79"
 dependencies = [
  "itoa",
  "ryu",
@@ -886,9 +893,9 @@ dependencies = [
 
 [[package]]
 name = "syn"
-version = "1.0.60"
+version = "1.0.67"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c700597eca8a5a762beb35753ef6b94df201c81cca676604f547495a0d7f0081"
+checksum = "6498a9efc342871f91cc2d0d694c674368b4ceb40f62b65a7a08c3792935e702"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -970,9 +977,9 @@ dependencies = [
 
 [[package]]
 name = "udev"
-version = "0.4.0"
+version = "0.5.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "24953d50a3bce0f5f5a9a2766567072dc9af8096f8c40ea81815da651066bc9f"
+checksum = "048df778e99eea028c08cca7853b9b521df6948b59bb29ab8bb737c057f58e6d"
 dependencies = [
  "libc",
  "libudev-sys",
@@ -1019,9 +1026,9 @@ checksum = "f1bddf1187be692e79c5ffeab891132dfb0f236ed36a43c7ed39f1165ee20191"
 
 [[package]]
 name = "version_check"
-version = "0.9.2"
+version = "0.9.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b5a972e5669d67ba988ce3dc826706fb0a8b01471c088cb0b6110b805cc36aed"
+checksum = "5fecdca9a5291cc2b8dcf7dc02453fee791a280f3743cb0905f8822ae463b3fe"
 
 [[package]]
 name = "void"
diff --git a/Cargo.toml b/Cargo.toml
index 61eae91..2a97534 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "fclones"
 description = "Finds duplicate, unique, under- or over-replicated files"
-version = "0.8.1"
+version = "0.9.0"
 authors = ["Piotr Kołaczkowski <pkolaczk@gmail.com>"]
 edition = "2018"
 license = "MIT"
@@ -16,12 +16,14 @@ byte-unit = "3.1.3"
 chrono = "0.4.11"
 clap = "2.33.0"
 console = "0.11.2"
+crossbeam-utils = "0.8"
 csv = "1.1.3"
 dashmap = "3.11.1"
 dunce = "1.0.1"
 indicatif = { version = "0.14.0", features = ["with_rayon"] }
 indoc = "0.3.5"
 itertools = "0.9.0"
+lazy-init = "0.5.0"
 maplit = "1.0.2"
 metrohash = "1.0.6"
 nom = { version = "5.1.2", features = ["regexp"] }
@@ -38,7 +40,8 @@ thread_local = "1.0.1"
 uuid = { version = "0.8.1", features = ["v4"] }
 
 [target.'cfg(target_os = "linux")'.dependencies]
-block-utils = "0.8.2"
+block-utils = "0.10.1"
+fiemap = "0.1.1"
 
 [target.'cfg(unix)'.dependencies]
 nix = "0.17.0"
@@ -48,6 +51,9 @@ libc = "0.2.69"
 winapi = "0.3.8"
 winapi-util = "0.1.5"
 
+[dev-dependencies]
+rand = "0.8.3"
+
 [package.metadata.deb]
 maintainer = "Piotr Kołaczkowski <pkolaczk@gmail.com>"
 copyright = "2020, Piotr Kołaczkowski <pkolaczk@gmail.com>"
diff --git a/README.md b/README.md
index 881233a..09ae798 100644
--- a/README.md
+++ b/README.md
@@ -24,7 +24,7 @@ It easily outperforms many other popular duplicate finders by a wide margin (see
   - proper handling of symlinks and hardlinks  
 * High performance
   - parallel processing capability in all I/O and CPU heavy stages
-  - automatic tuning of per-device parallelism based on device type (SSD vs HDD)
+  - automatic tuning of parallelism and access strategy based on device type (SSD vs HDD)
   - low memory footprint thanks to heavily optimized path representation
   - fast, non-cryptographic 128-bit hashing function
   - linear complexity
@@ -194,7 +194,7 @@ At the moment, tuning is possible only for desired parallelism level.
 The `--threads` parameter controls the sizes of the internal thread-pool(s). 
 This can be used to reduce parallelism level when you don't want `fclones` to 
 impact performance of your system too much, e.g. when you need to do some other work
-at the same time. It is also recommended to reduce the parallelism level if you need
+at the same time. We recommended reducing the parallelism level if you need
 to reduce memory usage. 
 
 When using `fclones` up to version 0.6.x to deduplicate files of sizes of at least a few MBs each  
@@ -207,34 +207,42 @@ and it will automatically tune the level of parallelism, memory buffer sizes and
 based on the device type. These automatic settings can be overriden with `-threads` as well.
 
 The following options can be passed to `--threads`. The more specific options override the less specific ones.
-- `main:<value>` – sets the size of the main thread-pool used for random I/O: directory tree scanning, file metadata fetching and partial hashing.
-   These operations typically benefit from high parallelism level, even on spinning drives. Unset by default.
-- `dev:<device>:<value>` – sets the size of the thread-pool used for sequential I/O
-   on the block device with the given name. The name of the device is OS-dependent. 
+- `main:<n>` – sets the size of the main thread-pool used for random I/O: directory tree scanning, 
+   file metadata fetching and in-memory sorting/hashing.
+   These operations typically benefit from high parallelism level, even on spinning drives. 
+   Unset by default, which means the pool will be configured to use all available CPU cores.
+- `dev:<device>:<r>,
` – sets the size of the thread-pool `r` used for random I/O and `s` used for 
+   sequential I/O on the block device with the given name. The name of the device is OS-dependent. 
    Note this is not the same as the partition name or mount point.
-- `ssd:<value>` – sets the size of the thread-pools used for sequential I/O on solid-state drives. Unset by default. 
-- `hdd:<value>` – sets the size of the thread-pools used for sequential I/O on spinning drives. Defaults to 1.
-- `unknown:<value>` –  sets the size of the thread-pools used for sequential I/O on devices of unknown type. Defaults to 1.
+- `ssd:<r>,
` – sets the sizes of the thread-pools used for I/O on solid-state drives. Unset by default. 
+- `hdd:<r>,
` – sets the sizes of the thread-pools used for I/O on spinning drives. 
+   Defaults to `8,1`
+- `removable:<r>,
` –  sets the size of the thread-pools used for I/O 
+   on removable devices (e.g. USB sticks). Defaults to `4,1`
+- `unknown:<r>,
` –  sets the size of the thread-pools used for I/O on devices of unknown type.
    Sometimes the device type can't be determined e.g. if it is mounted as NAS.
-- `default:<value>` – sets the size to be used by all unset options
-- `<value>` - same as `default:<value>`
+   Defaults to `4,1`
+- `default:<r>,
` – sets the pool sizes to be used by all unset options
+- `<r>,
` - same as `default:<r>,
`  
+- `<n>` - same as `default:<n>,<n>`
 
 ## Examples
-To limit the parallelism level for random I/O access to 1:
+To limit the parallelism level for the main thread pool to 1:
 
     fclones <paths> --threads main:1  
   
-To limit the parallelism level for sequential I/O access for all SSD devices (applies to the final full-content hashing):
+To limit the parallelism level for all I/O access for all SSD devices:
 
     fclones <paths> --threads ssd:1 
 
-To set the parallelism level to 2 for sequential I/O access for `/dev/sda` block device:
+To set the parallelism level to the number of cores for random I/O accesss and to 
+2 for sequential I/O access for `/dev/sda` block device:
 
-    fclones <paths> --threads dev:/dev/sda:2 
+    fclones <paths> --threads dev:/dev/sda:0,2 
     
-Multiple `--threads` options can be used together:
+Multiple `--threads` options can be given, separated by spaces:
 
-    fclones <paths> --threads main:16 ssd:4 hdd:1     
+    fclones <paths> --threads main:16 ssd:4 hdd:1,1     
     
     
 ## Benchmarks
diff --git a/src/config.rs b/src/config.rs
index 53d0c70..3a8ccc7 100644
--- a/src/config.rs
+++ b/src/config.rs
@@ -8,6 +8,7 @@ use clap::arg_enum;
 use clap::AppSettings;
 use structopt::StructOpt;
 
+use crate::device::Parallelism;
 use crate::files::FileLen;
 use crate::log::Log;
 use crate::path::Path;
@@ -28,7 +29,8 @@ impl Default for OutputFormat {
     }
 }
 
-fn parse_thread_count_option(str: &str) -> Result<(OsString, usize), String> {
+/// Parses string with format: `<device>:<seq parallelism>[,<rand parallelism>]`
+fn parse_thread_count_option(str: &str) -> Result<(OsString, Parallelism), String> {
     let (key, value) = if str.contains(':') {
         let index = str.rfind(':').unwrap();
         (&str[0..index], &str[(index + 1)..])
@@ -37,10 +39,19 @@ fn parse_thread_count_option(str: &str) -> Result<(OsString, usize), String> {
     };
     let key = OsString::from(key);
     let value = value.to_string();
-    match value.parse() {
-        Ok(v) => Ok((key, v)),
-        Err(e) => Err(format!("{}: {}", e, value)),
-    }
+    let mut pool_sizes = value
+        .split(',')
+        .map(|v| v.parse::<usize>().map_err(|e| format!("{}: {}", e, v)));
+
+    let random = match pool_sizes.next() {
+        Some(v) => v?,
+        None => return Err(String::from("Missing pool size specification")),
+    };
+    let sequential = match pool_sizes.next() {
+        Some(v) => v?,
+        None => random,
+    };
+    Ok((key, Parallelism { sequential, random }))
 }
 
 /// Finds duplicate, unique, under- or over-replicated files
@@ -89,6 +100,7 @@ pub struct Config {
     /// Before matching, transforms each file by the specified program.
     /// The value of this parameter should contain a command: the path to the program
     /// and optionally a list of space-separated arguments.
+    ///
     /// By default, the file to process will be piped to the standard input of the program and the
     /// processed data will be read from the standard output.
     /// If the program does not support piping, but requires its input and/or output file path(s)
@@ -163,16 +175,28 @@ pub struct Config {
     #[structopt(short = "g", long)]
     pub regex: bool,
 
-    /// Sets the size of a thread-pool with the given name.
+    /// Sets the sizes of thread-pools
+    ///
+    /// The spec has the following format: `[<name>:]<r>[,
]`.
     /// The name can be one of:
     /// (1) a physical block device when prefixed with `dev:` e.g. `dev:/dev/sda`;
-    /// (2) a type of device - `ssd`, `hdd` or `unknown`;
+    /// (2) a type of device - `ssd`, `hdd`, `removable` or `unknown`;
     /// (3) a thread pool or thread pool group - `main`, `default`.
     /// If the name is not given, this option sets the size of the main thread pool
     /// and thread pools dedicated to SSD devices.
+    ///
+    /// The values `r` and `s` are integers denoting the sizes of the
+    /// thread-pools used respectively for random access I/O and sequential I/O.
+    /// If `s` is not given, it is assumed to be the same as `r`.
+    ///
     /// This parameter can be used multiple times to configure multiple thread pools.
-    #[structopt(short, long, value_name = "[name:]value", parse(try_from_str = parse_thread_count_option))]
-    pub threads: Vec<(OsString, usize)>,
+    #[structopt(
+      short,
+      long,
+      value_name = "spec",
+      parse(try_from_str = parse_thread_count_option),
+      verbatim_doc_comment)]
+    pub threads: Vec<(OsString, Parallelism)>,
 
     /// Suppresses progress reporting
     #[structopt(short = "Q", long)]
@@ -270,10 +294,10 @@ impl Config {
     }
 
     /// Constructs the transform object and clears the transform command from this object.
-    pub fn take_transform(&mut self, log: &Log) -> Option<Transform> {
+    pub fn transform(&self, log: &Log) -> Option<Transform> {
         self.transform
-            .take()
-            .map(|command| self.build_transform(&command, log))
+            .as_ref()
+            .map(|command| self.build_transform(command, log))
     }
 
     fn build_transform(&self, command: &str, log: &Log) -> Transform {
@@ -291,10 +315,8 @@ impl Config {
         }
     }
 
-    pub fn thread_pool_sizes(&self) -> HashMap<OsString, usize> {
+    pub fn thread_pool_sizes(&self) -> HashMap<OsString, Parallelism> {
         let mut map = HashMap::new();
-        map.insert(OsString::from("hdd"), 1);
-        map.insert(OsString::from("unknown"), 1);
         for (k, v) in self.threads.iter() {
             map.insert(k.clone(), *v);
         }
@@ -306,7 +328,11 @@ impl Config {
     /// The only allowed key name is: "default".
     /// This method should be called after thread pools have been configured and their entries
     /// removed from the map.
-    pub fn check_thread_pools(&self, log: &Log, thread_pool_sizes: &mut HashMap<OsString, usize>) {
+    pub fn check_thread_pools(
+        &self,
+        log: &Log,
+        thread_pool_sizes: &mut HashMap<OsString, Parallelism>,
+    ) {
         thread_pool_sizes.remove(OsStr::new("default"));
         if !thread_pool_sizes.is_empty() {
             for (name, _) in thread_pool_sizes.iter() {
diff --git a/src/device.rs b/src/device.rs
index c31470b..3c45f77 100644
--- a/src/device.rs
+++ b/src/device.rs
@@ -1,43 +1,88 @@
 use core::cmp;
+use std::collections::HashMap;
 use std::ffi::{OsStr, OsString};
+use std::ops::Index;
 
 use itertools::Itertools;
+use lazy_init::Lazy;
+use rayon::{ThreadPool, ThreadPoolBuilder};
 use sysinfo::{DiskExt, DiskType, System, SystemExt};
 
 use crate::files::FileLen;
 use crate::path::Path;
-use rayon::{ThreadPool, ThreadPoolBuilder};
-use std::collections::HashMap;
+
+#[derive(Clone, Copy, Debug)]
+pub struct Parallelism {
+    pub random: usize,
+    pub sequential: usize,
+}
+
+impl Parallelism {
+    pub fn default_for(disk_type: DiskType) -> Parallelism {
+        match disk_type {
+            DiskType::SSD => Parallelism {
+                random: 0,
+                sequential: 0,
+            }, // == number of cores
+            DiskType::HDD => Parallelism {
+                random: 8,
+                sequential: 1,
+            },
+            DiskType::Removable => Parallelism {
+                random: 4,
+                sequential: 1,
+            },
+            DiskType::Unknown(_) => Parallelism {
+                random: 4,
+                sequential: 1,
+            },
+        }
+    }
+}
 
 pub struct DiskDevice {
     pub index: usize,
     pub name: OsString,
     pub disk_type: DiskType,
-    pub thread_pool: ThreadPool,
+    pub parallelism: Parallelism,
+    seq_thread_pool: Lazy<ThreadPool>,
+    rand_thread_pool: Lazy<ThreadPool>,
 }
 
 impl DiskDevice {
-    fn new(index: usize, name: OsString, disk_type: DiskType, parallelism: usize) -> DiskDevice {
-        let parallelism: usize = match parallelism {
-            0 => match disk_type {
-                DiskType::SSD => 0, // == number of cores
-                DiskType::HDD => 1,
-                DiskType::Removable => 1,
-                DiskType::Unknown(_) => 1,
-            },
-            p => p,
-        };
+    fn new(
+        index: usize,
+        name: OsString,
+        disk_type: DiskType,
+        parallelism: Parallelism,
+    ) -> DiskDevice {
         DiskDevice {
             index,
             name,
             disk_type,
-            thread_pool: ThreadPoolBuilder::default()
-                .num_threads(parallelism)
-                .build()
-                .unwrap(),
+            parallelism,
+            seq_thread_pool: Lazy::new(),
+            rand_thread_pool: Lazy::new(),
         }
     }
 
+    fn build_thread_pool(num_threads: usize) -> ThreadPool {
+        ThreadPoolBuilder::default()
+            .num_threads(num_threads)
+            .build()
+            .unwrap()
+    }
+
+    pub fn seq_thread_pool(&self) -> &ThreadPool {
+        self.seq_thread_pool
+            .get_or_create(|| Self::build_thread_pool(self.parallelism.sequential))
+    }
+
+    pub fn rand_thread_pool(&self) -> &ThreadPool {
+        self.rand_thread_pool
+            .get_or_create(|| Self::build_thread_pool(self.parallelism.random))
+    }
+
     pub fn buf_len(&self) -> usize {
         match self.disk_type {
             DiskType::SSD => 64 * 1024,
@@ -50,16 +95,16 @@ impl DiskDevice {
     pub fn min_prefix_len(&self) -> FileLen {
         FileLen(match self.disk_type {
             DiskType::SSD => 4 * 1024,
-            DiskType::HDD => 16 * 1024,
-            DiskType::Removable => 16 * 1024,
-            DiskType::Unknown(_) => 16 * 1024,
+            DiskType::HDD => 4 * 1024,
+            DiskType::Removable => 4 * 1024,
+            DiskType::Unknown(_) => 4 * 1024,
         })
     }
 
     pub fn max_prefix_len(&self) -> FileLen {
         FileLen(match self.disk_type {
             DiskType::SSD => 4 * 1024,
-            DiskType::HDD => 64 * 1024,
+            DiskType::HDD => 16 * 1024,
             DiskType::Removable => 16 * 1024,
             DiskType::Unknown(_) => 16 * 1024,
         })
@@ -86,6 +131,23 @@ pub struct DiskDevices {
 }
 
 impl DiskDevices {
+    #[cfg(test)]
+    pub fn single(disk_type: DiskType, parallelism: usize) -> DiskDevices {
+        let device = DiskDevice::new(
+            0,
+            OsString::from("/"),
+            disk_type,
+            Parallelism {
+                random: parallelism,
+                sequential: parallelism,
+            },
+        );
+        DiskDevices {
+            devices: vec![device],
+            mount_points: vec![(Path::from("/"), 0)],
+        }
+    }
+
     /// Reads the preferred parallelism level for the device based on the
     /// device name or the device type (ssd/hdd) from `pool_sizes` map.
     /// Returns the value under the "default" key if device was not found,
@@ -94,8 +156,8 @@ impl DiskDevices {
     fn get_parallelism(
         name: &OsStr,
         disk_type: DiskType,
-        pool_sizes: &mut HashMap<OsString, usize>,
-    ) -> usize {
+        pool_sizes: &mut HashMap<OsString, Parallelism>,
+    ) -> Parallelism {
         let mut dev_key = OsString::new();
         dev_key.push("dev:");
         dev_key.push(name);
@@ -110,7 +172,9 @@ impl DiskDevices {
                 };
                 match p {
                     Some(p) => *p,
-                    None => *pool_sizes.get(OsStr::new("default")).unwrap_or(&0),
+                    None => *pool_sizes
+                        .get(OsStr::new("default"))
+                        .unwrap_or(&Parallelism::default_for(disk_type)),
                 }
             }
         }
@@ -122,7 +186,7 @@ impl DiskDevices {
         &mut self,
         name: OsString,
         disk_type: DiskType,
-        pool_sizes: &mut HashMap<OsString, usize>,
+        pool_sizes: &mut HashMap<OsString, Parallelism>,
     ) -> usize {
         if let Some((index, _)) = self.devices.iter().find_position(|d| d.name == name) {
             index
@@ -152,9 +216,9 @@ impl DiskDevices {
 
     /// Reads the list of partitions and disks from the system and builds the `DiskDevices`
     /// structure from that information.
-    pub fn new(pool_sizes: &mut HashMap<OsString, usize>) -> DiskDevices {
-        let mut sys = System::new_all();
-        sys.refresh_disks();
+    pub fn new(pool_sizes: &mut HashMap<OsString, Parallelism>) -> DiskDevices {
+        let mut sys = System::new();
+        sys.refresh_disks_list();
         let mut result = DiskDevices {
             devices: Vec::new(),
             mount_points: Vec::new(),
@@ -180,7 +244,7 @@ impl DiskDevices {
         result
     }
 
-    /// Returns the disk device which holds the given path.
+    /// Returns the disk device which holds the given path
     pub fn get_by_path(&self, path: &Path) -> &DiskDevice {
         self.mount_points
             .iter()
@@ -189,20 +253,38 @@ impl DiskDevices {
             .unwrap_or(&self.devices[0])
     }
 
-    /// Returns references to the thread pools associated with devices.
-    /// The order is the same as device order, so thread pools can be selected by
-    /// the device index.
-    pub fn thread_pools(&self) -> Vec<&ThreadPool> {
-        self.devices.iter().map(|d| &d.thread_pool).collect()
+    /// Returns the first device on the list
+    pub fn get_default(&self) -> &DiskDevice {
+        &self.devices[0]
+    }
+
+    /// Returns the number of devices
+    pub fn len(&self) -> usize {
+        self.devices.len()
+    }
+
+    /// Returns true if there are no devices
+    pub fn is_empty(&self) -> bool {
+        self.devices.is_empty()
+    }
+
+    /// Returns an iterator over devices
+    pub fn iter(&self) -> impl Iterator<Item = &DiskDevice> {
+        self.devices.iter()
     }
 }
 
 impl Default for DiskDevices {
     fn default() -> Self {
         let mut pool_sizes = HashMap::new();
-        pool_sizes.insert(OsString::from("ssd"), 0);
-        pool_sizes.insert(OsString::from("hdd"), 1);
-        pool_sizes.insert(OsString::from("default"), 1);
         Self::new(&mut pool_sizes)
     }
 }
+
+impl Index<usize> for DiskDevices {
+    type Output = DiskDevice;
+
+    fn index(&self, index: usize) -> &Self::Output {
+        &self.devices[index]
+    }
+}
diff --git a/src/files.rs b/src/files.rs
index 4c5e015..af64e97 100644
--- a/src/files.rs
+++ b/src/files.rs
@@ -7,7 +7,7 @@ use std::hash::{Hash, Hasher};
 use std::io;
 use std::io::{ErrorKind, Read, Seek, SeekFrom};
 use std::iter::Sum;
-use std::ops::{Add, Mul, Sub};
+use std::ops::{Add, BitXor, Mul, Sub};
 #[cfg(unix)]
 use std::os::unix::fs::OpenOptionsExt;
 #[cfg(unix)]
@@ -19,8 +19,10 @@ use metrohash::{MetroHash128, MetroHash64};
 use serde::*;
 use smallvec::alloc::fmt::Formatter;
 use smallvec::alloc::str::FromStr;
+#[cfg(unix)]
 use sysinfo::{System, SystemExt};
 
+use crate::device::DiskDevices;
 use crate::log::Log;
 use crate::path::Path;
 
@@ -43,32 +45,32 @@ impl Display for FilePos {
 }
 
 impl From<u64> for FilePos {
-    fn from(p: u64) -> Self {
-        FilePos(p)
+    fn from(pos: u64) -> Self {
+        FilePos(pos)
     }
 }
 
 impl From<usize> for FilePos {
-    fn from(p: usize) -> Self {
-        FilePos(p as u64)
+    fn from(pos: usize) -> Self {
+        FilePos(pos as u64)
     }
 }
 
-impl Into<u64> for FilePos {
-    fn into(self) -> u64 {
-        self.0
+impl From<FilePos> for u64 {
+    fn from(pos: FilePos) -> Self {
+        pos.0
     }
 }
 
-impl Into<usize> for FilePos {
-    fn into(self) -> usize {
-        self.0 as usize
+impl From<FilePos> for usize {
+    fn from(pos: FilePos) -> Self {
+        pos.0 as usize
     }
 }
 
-impl Into<SeekFrom> for FilePos {
-    fn into(self) -> SeekFrom {
-        SeekFrom::Start(self.0)
+impl From<FilePos> for SeekFrom {
+    fn from(pos: FilePos) -> Self {
+        SeekFrom::Start(pos.0)
     }
 }
 
@@ -125,15 +127,15 @@ impl From<usize> for FileLen {
     }
 }
 
-impl Into<u64> for FileLen {
-    fn into(self) -> u64 {
-        self.0
+impl From<FileLen> for u64 {
+    fn from(l: FileLen) -> Self {
+        l.0
     }
 }
 
-impl Into<usize> for FileLen {
-    fn into(self) -> usize {
-        self.0 as usize
+impl From<FileLen> for usize {
+    fn from(l: FileLen) -> Self {
+        l.0 as usize
     }
 }
 
@@ -179,37 +181,55 @@ impl Display for FileLen {
     }
 }
 
-/// Keeps metadata of the file that we are interested in.
-/// We don't want to keep unused metadata in memory.
-#[repr(packed(4))]
+pub trait AsPath {
+    fn path(&self) -> &Path;
+}
+
+pub trait IntoPath {
+    fn into_path(self) -> Path;
+}
+
+#[derive(Clone, Debug)]
 pub struct FileInfo {
     pub path: Path,
     pub len: FileLen,
-    pub id_hash: u32,
+    // physical on-disk location of file data for access ordering optimisation
+    // the highest 16 bits encode the device id
+    pub location: u64,
 }
 
-/// An even more packed file information, without length
-#[repr(packed(4))]
-pub struct FileInfoNoLen {
-    pub path: Path,
-    pub id_hash: u32,
+impl AsPath for FileInfo {
+    fn path(&self) -> &Path {
+        &self.path
+    }
+}
+
+impl IntoPath for FileInfo {
+    fn into_path(self) -> Path {
+        self.path
+    }
 }
 
+#[cfg(unix)]
+const OFFSET_MASK: u64 = 0x0000FFFFFFFFFFFF;
+
+#[cfg(unix)]
+const DEVICE_MASK: u64 = 0xFFFF000000000000;
+
 impl FileInfo {
     #[cfg(unix)]
-    fn new(path: Path) -> io::Result<FileInfo> {
+    fn new(path: Path, devices: &DiskDevices) -> io::Result<FileInfo> {
         use std::os::unix::fs::MetadataExt;
 
         match std::fs::metadata(&path.to_path_buf()) {
-            Ok(metadata) => Ok(FileInfo {
-                path,
-                len: FileLen(metadata.len()),
-                id_hash: FileId {
-                    inode: metadata.ino() as u128,
-                    device: metadata.dev(),
-                }
-                .get_hash(),
-            }),
+            Ok(metadata) => {
+                let device_index = devices.get_by_path(&path).index as u64;
+                Ok(FileInfo {
+                    path,
+                    len: FileLen(metadata.len()),
+                    location: device_index << 48 | metadata.ino() & OFFSET_MASK,
+                })
+            }
             Err(e) => Err(io::Error::new(
                 e.kind(),
                 format!("Failed to read metadata of {}: {}", path.display(), e),
@@ -218,18 +238,17 @@ impl FileInfo {
     }
 
     #[cfg(windows)]
-    fn new(path: Path) -> io::Result<FileInfo> {
+    fn new(path: Path, devices: &DiskDevices) -> io::Result<FileInfo> {
         let info = File::open(path.to_path_buf()).and_then(|f| winapi_util::file::information(&f));
         match info {
-            Ok(info) => Ok(FileInfo {
-                path,
-                len: FileLen(info.file_size()),
-                id_hash: FileId {
-                    inode: info.file_index() as u128,
-                    device: info.volume_serial_number() as u64,
-                }
-                .get_hash(),
-            }),
+            Ok(info) => {
+                let device_index = devices.get_by_path(&path).index as u64;
+                Ok(FileInfo {
+                    path,
+                    len: FileLen(info.file_size()),
+                    location: device_index << 24 | info.file_index() & 0xFFFFFFFFFFFF,
+                })
+            }
             Err(e) => Err(io::Error::new(
                 e.kind(),
                 format!("Failed to read metadata of {}: {}", path.display(), e),
@@ -237,48 +256,25 @@ impl FileInfo {
         }
     }
 
-    /// Removes the length field from the information and returns a smaller structure
-    pub fn drop_len(self) -> FileInfoNoLen {
-        FileInfoNoLen {
-            path: self.path,
-            id_hash: self.id_hash,
-        }
-    }
-
-    /// Converts to an aligned representation
-    pub fn unpack(self) -> UnpackedFileInfo {
-        UnpackedFileInfo {
-            path: self.path,
-            len: self.len,
-            id_hash: self.id_hash,
-        }
+    /// Returns the device index into the `DiskDevices` instance passed at creation
+    pub fn get_device_index(&self) -> usize {
+        (self.location >> 48) as usize
     }
-}
-
-/// This structure contains the same data as `FileInfo` but is unpacked (aligned)
-/// and allows borrowing fields. Use [unpack](FileInfo::unpack) and [pack](UnpackedFileInfo::pack)
-/// methods to convert between packed and non-packed representations.
-pub struct UnpackedFileInfo {
-    pub path: Path,
-    pub len: FileLen,
-    pub id_hash: u32,
-}
 
-impl UnpackedFileInfo {
-    /// Converts to a non-aligned representation
-    pub fn pack(self) -> FileInfo {
-        FileInfo {
-            path: self.path,
-            len: self.len,
-            id_hash: self.id_hash,
+    #[cfg(target_os = "linux")]
+    pub fn fetch_physical_location(&mut self) -> io::Result<u64> {
+        let new_location = get_physical_file_location(&self.path())?;
+        if let Some(new_location) = new_location {
+            self.location = self.location & DEVICE_MASK | (new_location >> 8) & OFFSET_MASK;
         }
+        Ok(self.location)
     }
 }
 
 /// Returns file information for the given path.
 /// On failure, logs an error to stderr and returns `None`.
-pub fn file_info_or_log_err(file: Path, log: &Log) -> Option<FileInfo> {
-    match FileInfo::new(file) {
+pub fn file_info_or_log_err(file: Path, devices: &DiskDevices, log: &Log) -> Option<FileInfo> {
+    match FileInfo::new(file, devices) {
         Ok(info) => Some(info),
         Err(e) if e.kind() == ErrorKind::NotFound => None,
         Err(e) => {
@@ -360,6 +356,16 @@ pub fn file_id_or_log_err(file: &Path, log: &Log) -> Option<FileId> {
     }
 }
 
+/// Returns the physical offset of the first data block of the file
+#[cfg(target_os = "linux")]
+pub fn get_physical_file_location(path: &Path) -> io::Result<Option<u64>> {
+    let mut extents = fiemap::fiemap(&path.to_path_buf())?;
+    match extents.next() {
+        Some(fe) => Ok(Some(fe?.fe_physical)),
+        None => Ok(None),
+    }
+}
+
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 pub struct FileHash(pub u128);
 
@@ -385,6 +391,14 @@ impl Display for FileHash {
     }
 }
 
+impl BitXor for FileHash {
+    type Output = Self;
+
+    fn bitxor(self, rhs: Self) -> Self::Output {
+        FileHash(rhs.0 ^ self.0)
+    }
+}
+
 impl Serialize for FileHash {
     fn serialize<S>(&self, serializer: S) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>
     where
diff --git a/src/group.rs b/src/group.rs
index fa9dec3..78900d9 100644
--- a/src/group.rs
+++ b/src/group.rs
@@ -1,14 +1,19 @@
-use std::collections::HashMap;
+use std::collections::BTreeMap;
 use std::hash::Hash;
 use std::marker::PhantomData;
+use std::sync::mpsc::{channel, Receiver, Sender};
+use std::sync::Arc;
 
-use itertools::Itertools;
-use rayon::iter::{IntoParallelIterator, ParallelIterator};
+use crossbeam_utils::thread;
+use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
+use rayon::prelude::ParallelSliceMut;
 use serde::*;
-
-use crate::files::{FileHash, FileLen};
 use smallvec::SmallVec;
-use std::cmp::{max, min};
+use sysinfo::DiskType;
+
+use crate::device::DiskDevices;
+use crate::files::{FileHash, FileInfo, FileLen};
+use crate::semaphore::Semaphore;
 
 /// Groups items by key.
 /// After all items have been added, this structure can be transformed into
@@ -43,13 +48,13 @@ where
     F: Fn(T) -> (K, V),
 {
     item_type: PhantomData<T>,
-    groups: HashMap<K, SmallVec<[V; 1]>>,
+    groups: BTreeMap<K, SmallVec<[V; 1]>>,
     split_fn: F,
 }
 
 impl<T, K, V, F> GroupMap<T, K, V, F>
 where
-    K: Eq + Hash,
+    K: Eq + Hash + Ord,
     F: Fn(T) -> (K, V),
 {
     /// Creates a new empty map.
@@ -59,15 +64,7 @@ where
     pub fn new(split_fn: F) -> GroupMap<T, K, V, F> {
         GroupMap {
             item_type: PhantomData,
-            groups: HashMap::new(),
-            split_fn,
-        }
-    }
-
-    pub fn with_capacity(capacity: usize, split_fn: F) -> GroupMap<T, K, V, F> {
-        GroupMap {
-            item_type: PhantomData,
-            groups: HashMap::with_capacity(capacity),
+            groups: BTreeMap::new(),
             split_fn,
         }
     }
@@ -91,7 +88,7 @@ where
     F: Fn(T) -> (K, V),
 {
     type Item = (K, SmallVec<[V; 1]>);
-    type IntoIter = <HashMap<K, SmallVec<[V; 1]>> as IntoIterator>::IntoIter;
+    type IntoIter = <BTreeMap<K, SmallVec<[V; 1]>> as IntoIterator>::IntoIter;
 
     fn into_iter(self) -> Self::IntoIter {
         self.groups.into_iter()
@@ -103,54 +100,12 @@ where
 pub struct FileGroup<F> {
     /// Length of each file
     pub file_len: FileLen,
-    /// Min length of the prefix such that all files in the group have the same prefix
-    pub prefix_len: FileLen,
     /// Hash of a part or the whole of the file
-    pub hash: FileHash,
-
+    pub file_hash: FileHash,
+    /// Group of files with the same length and hash
     pub files: Vec<F>,
 }
 
-impl<F> FileGroup<F>
-where
-    F: Send,
-{
-    /// Splits a single group into 0 to n groups based on the given hash function if `cond` is true.
-    /// If `cond` is false, then `self` is returned as the only item.
-    /// Files hashing to `None` are removed from the output.
-    /// An empty vector may be returned if all files hash to `None`.
-    pub fn split<H>(self, cond: bool, prefix_len: FileLen, hash: H) -> Vec<FileGroup<F>>
-    where
-        H: Fn(&F) -> Option<FileHash> + Sync + Send,
-    {
-        if cond {
-            let file_len = self.file_len;
-            let prefix_len = min(self.file_len, max(self.prefix_len, prefix_len));
-
-            let mut hashed = self
-                .files
-                .into_par_iter()
-                .filter_map(|f: F| (hash)(&f).map(|h| (h, f)))
-                .collect::<Vec<_>>();
-
-            hashed.sort_by_key(|(h, _p)| h.0);
-            hashed
-                .into_iter()
-                .group_by(|(h, _)| *h)
-                .into_iter()
-                .map(|(hash, group)| FileGroup {
-                    file_len,
-                    prefix_len,
-                    hash,
-                    files: group.map(|(_hash, path)| path).collect(),
-                })
-                .collect()
-        } else {
-            vec![self]
-        }
-    }
-}
-
 /// Computes metrics for reporting summaries of each processing stage.
 pub trait GroupedFileSetMetrics {
     /// Returns the total count of the files
@@ -199,3 +154,367 @@ where
             .sum()
     }
 }
+
+/// Helper struct to preserve the original file hash and keep it together with file information
+/// Sometimes the old hash must be taken into account, e.g. when combining the prefix hash with
+/// the suffix hash.
+struct HashedFileInfo {
+    file_hash: FileHash,
+    file_info: FileInfo,
+}
+
+/// Partitions files into separate vectors, where each vector holds files persisted
+/// on the same disk device. The vectors are returned in the same order as devices.
+fn partition_by_devices(
+    files: Vec<FileGroup<FileInfo>>,
+    devices: &DiskDevices,
+) -> Vec<Vec<HashedFileInfo>> {
+    let mut result: Vec<Vec<HashedFileInfo>> = Vec::with_capacity(devices.len());
+    for _ in 0..devices.len() {
+        result.push(Vec::new());
+    }
+    for g in files {
+        for f in g.files {
+            let device = &devices[f.get_device_index()];
+            result[device.index].push(HashedFileInfo {
+                file_hash: g.file_hash,
+                file_info: f,
+            });
+        }
+    }
+    result
+}
+
+/// Iterates over grouped files, in parallel
+pub fn flat_iter(files: &[FileGroup<FileInfo>]) -> impl ParallelIterator<Item = &FileInfo> {
+    files.par_iter().flat_map(|g| &g.files)
+}
+
+#[derive(Copy, Clone, Debug)]
+pub enum AccessType {
+    Sequential,
+    Random,
+}
+
+/// Groups files by length and hash computed by given `hash_fn`.
+/// Runs in parallel on dedicated thread pools.
+/// Files on different devices are hashed separately from each other.
+/// File hashes within a single device are computed in the order given by
+/// their `location` field to minimize seek latency.
+///
+/// Caveats: the original grouping is lost. It is possible for two files that
+/// were in the different groups to end up in the same group if they have the same length
+/// and they hash to the same value. If you don't want this, you need to combine the old
+/// hash with the new hash in the provided `hash_fn`.
+pub fn rehash<'a, F1, F2, H>(
+    groups: Vec<FileGroup<FileInfo>>,
+    group_pre_filter: F1,
+    group_post_filter: F2,
+    devices: &DiskDevices,
+    access_type: AccessType,
+    hash_fn: H,
+) -> Vec<FileGroup<FileInfo>>
+where
+    F1: Fn(&FileGroup<FileInfo>) -> bool,
+    F2: Fn(&FileGroup<FileInfo>) -> bool,
+    H: Fn((&mut FileInfo, FileHash)) -> Option<FileHash> + Sync + Send + 'a,
+{
+    // Allow sharing the hash function between threads:
+    type HashFn<'a> = dyn Fn((&mut FileInfo, FileHash)) -> Option<FileHash> + Sync + Send + 'a;
+    let hash_fn: &HashFn<'a> = &hash_fn;
+
+    let (tx, rx): (Sender<HashedFileInfo>, Receiver<HashedFileInfo>) = channel();
+
+    // There is no point in processing groups containing a single file.
+    // Normally when searching for duplicates such groups are filtered out automatically after
+    // each stage, however they are possible when searching for unique files.
+    let (groups_to_process, groups_to_pass): (Vec<_>, Vec<_>) =
+        groups.into_iter().partition(group_pre_filter);
+
+    // This way we can split processing to separate thread-pools, one per device:
+    let files = partition_by_devices(groups_to_process, &devices);
+    let mut hash_map =
+        GroupMap::new(|f: HashedFileInfo| ((f.file_info.len, f.file_hash), f.file_info));
+    let hash_map_ref = &mut hash_map;
+
+    // Scope needed so threads can access shared stuff like groups or shared functions.
+    // The threads we launch are guaranteed to not live longer than this scope.
+    thread::scope(move |s| {
+        // Process all files in background
+        for (mut files, device) in files.into_iter().zip(devices.iter()) {
+            if files.is_empty() {
+                continue;
+            }
+
+            let tx = tx.clone();
+
+            // Launch a separate thread for each device, so we can process
+            // files on each device independently
+            s.spawn(move |_| {
+                // Sort files by their physical location, to reduce disk seek latency
+                if device.disk_type != DiskType::SSD {
+                    files.par_sort_unstable_by_key(|f| f.file_info.location);
+                }
+
+                // Some devices like HDDs may benefit from different amount of parallelism
+                // depending on the access type. Therefore we chose a thread pool appropriate
+                // for the access type
+                let thread_pool = match access_type {
+                    AccessType::Sequential => device.seq_thread_pool(),
+                    AccessType::Random => device.rand_thread_pool(),
+                };
+
+                let thread_count = thread_pool.current_num_threads() as isize;
+
+                // Limit the number of tasks spawned at once into the thread-pool.
+                // Each task creates a heap allocation and reserves memory in the queue.
+                // It is more memory efficient to keep these tasks as long as possible
+                // in our vector. Without this limit we observed over 20% more memory use
+                // when processing 1M of files.
+                let semaphore = Arc::new(Semaphore::new(8 * thread_count));
+
+                // Run hashing on the thread-pool dedicated to the device
+                for mut f in files {
+                    let tx = tx.clone();
+                    let guard = semaphore.clone().access_owned();
+
+                    // Spawning a task into a thread-pool requires a static lifetime,
+                    // because generally the task could outlive caller's stack frame.
+                    // However, this is not the case for rehash function, because
+                    // we don't exit before all tasks are processed.
+                    // In the perfect world we should use scopes for that. Unfortunately
+                    // the current implementation of rayon scopes runs the scope body
+                    // on one of the thread-pool worker threads, so it is not possible
+                    // to safely block inside the scope, because that leads to deadlock
+                    // when the pool has only one thread.
+                    let hash_fn: &HashFn<'static> = unsafe { std::mem::transmute(hash_fn) };
+                    thread_pool.spawn_fifo(move || {
+                        if let Some(hash) = hash_fn((&mut f.file_info, f.file_hash)) {
+                            f.file_hash = hash;
+                            tx.send(f).unwrap();
+                        }
+                        // This forces moving the guard into this task and be released when
+                        // the task is done
+                        drop(guard);
+                    });
+                }
+            });
+        }
+        // Drop the original tx, so all tx are closed when the threads finish and
+        // the next while loop will eventually exit
+        drop(tx);
+
+        // Collect the results from all threads and group them.
+        // Note that this will happen as soon as data are available
+        while let Ok(hashed_file) = rx.recv() {
+            hash_map_ref.add(hashed_file);
+        }
+    })
+    .unwrap();
+
+    // Convert the hashmap into vector, leaving only large-enough groups:
+    hash_map
+        .into_iter()
+        .map(|((len, hash), files)| FileGroup {
+            file_len: len,
+            file_hash: hash,
+            files: files.to_vec(),
+        })
+        .filter(group_post_filter)
+        .chain(groups_to_pass.into_iter())
+        .collect()
+}
+
+#[cfg(test)]
+mod test {
+    use std::sync::atomic::{AtomicBool, Ordering};
+    use std::sync::Mutex;
+
+    use rand::seq::SliceRandom;
+
+    use FileGroup;
+
+    use crate::path::Path;
+
+    use super::*;
+
+    /// Files hashing to different values should be placed into different groups
+    #[test]
+    fn test_rehash_puts_files_with_different_hashes_to_different_groups() {
+        let devices = DiskDevices::default();
+        let input = vec![FileGroup {
+            file_len: FileLen(200),
+            file_hash: FileHash(0),
+            files: vec![
+                FileInfo {
+                    len: FileLen(200),
+                    location: 0,
+                    path: Path::from("file1"),
+                },
+                FileInfo {
+                    len: FileLen(200),
+                    location: 35847587,
+                    path: Path::from("file2"),
+                },
+            ],
+        }];
+
+        let result = rehash(
+            input,
+            |_| true,
+            |_| true,
+            &devices,
+            AccessType::Random,
+            |(fi, _)| Some(FileHash(fi.location as u128)),
+        );
+
+        assert_eq!(result.len(), 2);
+        assert_eq!(result[0].files.len(), 1);
+        assert_eq!(result[1].files.len(), 1);
+        assert_ne!(result[0].files[0].path, result[1].files[0].path);
+    }
+
+    /// Files hashing to same values should be placed into the same groups
+    #[test]
+    fn test_rehash_puts_files_with_same_hashes_to_same_groups() {
+        let devices = DiskDevices::default();
+        let input = vec![
+            FileGroup {
+                file_len: FileLen(200),
+                file_hash: FileHash(0),
+                files: vec![FileInfo {
+                    len: FileLen(200),
+                    location: 0,
+                    path: Path::from("file1"),
+                }],
+            },
+            FileGroup {
+                file_len: FileLen(500),
+                file_hash: FileHash(0),
+                files: vec![FileInfo {
+                    len: FileLen(200),
+                    location: 35847587,
+                    path: Path::from("file2"),
+                }],
+            },
+        ];
+
+        let result = rehash(
+            input,
+            |_| true,
+            |_| true,
+            &devices,
+            AccessType::Random,
+            |(_, _)| Some(FileHash(123456)),
+        );
+
+        assert_eq!(result.len(), 1);
+        assert_eq!(result[0].files.len(), 2);
+    }
+
+    #[test]
+    fn test_rehash_can_skip_processing_files() {
+        let devices = DiskDevices::default();
+        let input = vec![FileGroup {
+            file_len: FileLen(200),
+            file_hash: FileHash(0),
+            files: vec![FileInfo {
+                len: FileLen(200),
+                location: 0,
+                path: Path::from("file1"),
+            }],
+        }];
+
+        let called = AtomicBool::new(false);
+        let result = rehash(
+            input,
+            |_| false,
+            |_| true,
+            &devices,
+            AccessType::Random,
+            |(fi, _)| {
+                called.store(true, Ordering::Release);
+                Some(FileHash(fi.location as u128))
+            },
+        );
+
+        assert_eq!(result.len(), 1);
+        assert!(!called.load(Ordering::Acquire));
+    }
+
+    #[test]
+    fn test_rehash_post_filter_removes_groups() {
+        let devices = DiskDevices::default();
+        let input = vec![FileGroup {
+            file_len: FileLen(200),
+            file_hash: FileHash(0),
+            files: vec![
+                FileInfo {
+                    len: FileLen(200),
+                    location: 0,
+                    path: Path::from("file1"),
+                },
+                FileInfo {
+                    len: FileLen(200),
+                    location: 35847587,
+                    path: Path::from("file2"),
+                },
+            ],
+        }];
+
+        let result = rehash(
+            input,
+            |_| true,
+            |g| g.files.len() >= 2,
+            &devices,
+            AccessType::Random,
+            |(fi, _)| Some(FileHash(fi.location as u128)),
+        );
+
+        assert!(result.is_empty())
+    }
+
+    #[test]
+    fn test_rehash_processes_files_in_location_order_on_hdd() {
+        let thread_count = 2;
+        let devices = DiskDevices::single(DiskType::HDD, thread_count);
+        let count = 1000;
+        let mut input = Vec::with_capacity(count);
+        for i in 0..count {
+            input.push(FileGroup {
+                file_len: FileLen(0),
+                file_hash: FileHash(0),
+                files: vec![FileInfo {
+                    len: FileLen(0),
+                    location: i as u64,
+                    path: Path::from(format!("file{}", i)),
+                }],
+            })
+        }
+        input.shuffle(&mut rand::thread_rng());
+
+        let processing_order = Mutex::new(Vec::new());
+        rehash(
+            input,
+            |_| true,
+            |_| true,
+            &devices,
+            AccessType::Random,
+            |(fi, _)| {
+                processing_order.lock().unwrap().push(fi.location as i32);
+                Some(FileHash(fi.location as u128))
+            },
+        );
+        let processing_order = processing_order.into_inner().unwrap();
+
+        // Because we're processing files in parallel, we have no strict guarantee they
+        // will be processed in the exact same order as in the input.
+        // However, we expect some locality so the total distance between subsequent accesses
+        // is low.
+        let mut distance = 0;
+        for i in 0..processing_order.len() - 1 {
+            distance += i32::abs(processing_order[i] - processing_order[i + 1])
+        }
+        assert!(distance < (thread_count * count) as i32)
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index b82196a..937053d 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -5,10 +5,10 @@ pub mod group;
 pub mod log;
 pub mod path;
 pub mod pattern;
-pub mod pools;
 pub mod progress;
 pub mod report;
 pub mod selector;
+pub mod semaphore;
 pub mod transform;
 pub mod util;
 pub mod walk;
diff --git a/src/log.rs b/src/log.rs
index 3ed105a..a9ec4d6 100644
--- a/src/log.rs
+++ b/src/log.rs
@@ -1,4 +1,4 @@
-use std::sync::{Arc, Weak};
+use std::sync::{Arc, Mutex, Weak};
 
 use console::style;
 use indicatif::ProgressDrawTarget;
@@ -9,7 +9,7 @@ use chrono::Local;
 
 pub struct Log {
     program_name: String,
-    progress_bar: Weak<FastProgressBar>,
+    progress_bar: Mutex<Weak<FastProgressBar>>,
     pub log_stderr_to_stdout: bool,
     pub no_progress: bool,
 }
@@ -17,7 +17,7 @@ pub struct Log {
 impl Log {
     pub fn new() -> Log {
         Log {
-            progress_bar: Weak::default(),
+            progress_bar: Mutex::new(Weak::default()),
             program_name: std::env::current_exe()
                 .unwrap()
                 .file_name()
@@ -30,47 +30,51 @@ impl Log {
     }
 
     /// Clears any previous progress bar or spinner and installs a new spinner.
-    pub fn spinner(&mut self, msg: &str) -> Arc<FastProgressBar> {
+    pub fn spinner(&self, msg: &str) -> Arc<FastProgressBar> {
         if self.no_progress {
             return Arc::new(FastProgressBar::new_hidden());
         }
         self.progress_bar
+            .lock()
+            .unwrap()
             .upgrade()
             .iter()
             .for_each(|pb| pb.finish_and_clear());
         let result = Arc::new(FastProgressBar::new_spinner(msg));
-        self.progress_bar = Arc::downgrade(&result);
+        *self.progress_bar.lock().unwrap() = Arc::downgrade(&result);
         result
     }
 
     /// Clears any previous progress bar or spinner and installs a new progress bar.
-    pub fn progress_bar(&mut self, msg: &str, len: u64) -> Arc<FastProgressBar> {
+    pub fn progress_bar(&self, msg: &str, len: u64) -> Arc<FastProgressBar> {
         if self.no_progress {
             return Arc::new(FastProgressBar::new_hidden());
         }
         let result = Arc::new(FastProgressBar::new_progress_bar(msg, len));
-        self.progress_bar = Arc::downgrade(&result);
+        *self.progress_bar.lock().unwrap() = Arc::downgrade(&result);
         result
     }
 
     /// Clears any previous progress bar or spinner and installs a new progress bar.
-    pub fn bytes_progress_bar(&mut self, msg: &str, len: u64) -> Arc<FastProgressBar> {
+    pub fn bytes_progress_bar(&self, msg: &str, len: u64) -> Arc<FastProgressBar> {
         if self.no_progress {
             return Arc::new(FastProgressBar::new_hidden());
         }
         self.progress_bar
+            .lock()
+            .unwrap()
             .upgrade()
             .iter()
             .for_each(|pb| pb.finish_and_clear());
         let result = Arc::new(FastProgressBar::new_bytes_progress_bar(msg, len));
-        self.progress_bar = Arc::downgrade(&result);
+        *self.progress_bar.lock().unwrap() = Arc::downgrade(&result);
         result
     }
 
     /// Prints a message to stdout.
     /// Does not interfere with progress bar.
     pub fn println<I: Display>(&self, msg: I) {
-        match self.progress_bar.upgrade() {
+        match self.progress_bar.lock().unwrap().upgrade() {
             Some(pb) if pb.is_visible() => {
                 pb.set_draw_target(ProgressDrawTarget::hidden());
                 println!("{}", msg);
@@ -83,7 +87,7 @@ impl Log {
     /// Prints a message to stderr.
     /// Does not interfere with progress bar.
     pub fn eprintln<I: Display>(&self, msg: I) {
-        match self.progress_bar.upgrade() {
+        match self.progress_bar.lock().unwrap().upgrade() {
             Some(pb) if pb.is_visible() => pb.println(format!("{}", msg)),
             _ if self.log_stderr_to_stdout => println!("{}", msg),
             _ => eprintln!("{}", msg),
diff --git a/src/main.rs b/src/main.rs
index 91d3248..50b590c 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -5,9 +5,9 @@ use std::env::current_dir;
 use std::ffi::{OsStr, OsString};
 use std::fs::File;
 use std::io::{BufWriter, Write};
-use std::path::PathBuf;
 use std::process::exit;
-use std::sync::mpsc::channel;
+#[cfg(target_os = "linux")]
+use std::sync::atomic::{AtomicU32, Ordering};
 use std::sync::Arc;
 
 use console::{style, Term};
@@ -19,13 +19,12 @@ use structopt::StructOpt;
 use thread_local::ThreadLocal;
 
 use fclones::config::*;
-use fclones::device::{DiskDevice, DiskDevices};
+use fclones::device::{DiskDevice, DiskDevices, Parallelism};
 use fclones::files::*;
 use fclones::group::*;
 use fclones::log::Log;
 use fclones::path::Path;
 use fclones::pattern::ESCAPE_CHAR;
-use fclones::pools::multi_scope;
 use fclones::progress::FastProgressBar;
 use fclones::report::Reporter;
 use fclones::transform::Transform;
@@ -38,19 +37,24 @@ struct AppCtx {
 }
 
 /// Configures global thread pool to use desired number of threads
-fn configure_main_thread_pool(pool_sizes: &mut HashMap<OsString, usize>) {
-    let parallelism = pool_sizes
-        .remove(OsStr::new("main"))
-        .unwrap_or_else(|| *pool_sizes.get(OsStr::new("default")).unwrap_or(&0));
+fn configure_main_thread_pool(pool_sizes: &mut HashMap<OsString, Parallelism>) {
+    let parallelism = pool_sizes.remove(OsStr::new("main")).unwrap_or_else(|| {
+        *pool_sizes
+            .get(OsStr::new("default"))
+            .unwrap_or(&Parallelism {
+                sequential: 0,
+                random: 0,
+            })
+    });
 
     rayon::ThreadPoolBuilder::new()
-        .num_threads(parallelism)
+        .num_threads(parallelism.random)
         .build_global()
         .unwrap();
 }
 
 /// Walks the directory tree and collects matching files in parallel into a vector
-fn scan_files(ctx: &mut AppCtx) -> Vec<Vec<FileInfo>> {
+fn scan_files(ctx: &AppCtx) -> Vec<Vec<FileInfo>> {
     let base_dir = Path::from(current_dir().unwrap_or_default());
     let path_selector = ctx.config.path_selector(&ctx.log, &base_dir);
     let file_collector = ThreadLocal::new();
@@ -70,7 +74,7 @@ fn scan_files(ctx: &mut AppCtx) -> Vec<Vec<FileInfo>> {
     walk.log = Some(&ctx.log);
     walk.on_visit = spinner_tick;
     walk.run(ctx.config.input_paths(), |path| {
-        file_info_or_log_err(path, &ctx.log)
+        file_info_or_log_err(path, &ctx.devices, &ctx.log)
             .into_iter()
             .filter(|info| {
                 let l = info.len;
@@ -97,11 +101,11 @@ fn scan_files(ctx: &mut AppCtx) -> Vec<Vec<FileInfo>> {
     files
 }
 
-fn group_by_size(ctx: &mut AppCtx, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<FileInfoNoLen>> {
+fn group_by_size(ctx: &AppCtx, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<FileInfo>> {
     let file_count: usize = files.iter().map(|v| v.len()).sum();
     let progress = ctx.log.progress_bar("Grouping by size", file_count as u64);
 
-    let mut groups = GroupMap::new(|info: FileInfo| (info.len, info.drop_len()));
+    let mut groups = GroupMap::new(|info: FileInfo| (info.len, info));
     for files in files.into_iter() {
         for file in files.into_iter() {
             progress.tick();
@@ -116,8 +120,7 @@ fn group_by_size(ctx: &mut AppCtx, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<F
         .filter(|(_, files)| files.len() > rf_over)
         .map(|(l, files)| FileGroup {
             file_len: l,
-            hash: FileHash(0),
-            prefix_len: FileLen(0),
+            file_hash: FileHash(0),
             files: files.into_vec(),
         })
         .collect();
@@ -131,54 +134,39 @@ fn group_by_size(ctx: &mut AppCtx, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<F
     groups
 }
 
-fn to_group_of_paths(f: FileGroup<FileInfoNoLen>) -> FileGroup<Path> {
-    FileGroup {
-        file_len: f.file_len,
-        prefix_len: f.prefix_len,
-        hash: f.hash,
-        files: f.files.into_iter().map(|i| i.path).collect(),
-    }
-}
-
 /// Removes duplicate files matching by full-path or by inode-id.
 /// Deduplication by inode-id is not performed if the flag to preserve hard-links (-H) is set.
-fn deduplicate<F>(ctx: &AppCtx, files: &mut Vec<FileInfoNoLen>, progress: F)
+fn deduplicate<F>(ctx: &AppCtx, files: &mut Vec<FileInfo>, progress: F)
 where
     F: Fn(&Path) + Sync + Send,
 {
-    let count = files.len();
-    let mut groups = GroupMap::with_capacity(count, |fi: FileInfoNoLen| (fi.id_hash, fi.path));
+    let mut groups = GroupMap::new(|fi: FileInfo| (fi.location, fi));
     for f in files.drain(..) {
         groups.add(f)
     }
 
-    for (id_hash, mut paths) in groups.into_iter() {
-        if paths.len() == 1 {
-            progress(&paths[0]);
-            files.push(FileInfoNoLen {
-                id_hash,
-                path: paths.remove(0),
-            });
+    for (_, file_group) in groups.into_iter() {
+        if file_group.len() == 1 {
+            files.extend(file_group.into_iter().inspect(|p| progress(&p.path)));
         } else if ctx.config.hard_links {
-            paths
-                .into_iter()
-                .inspect(|p| progress(p))
-                .unique_by(|p| p.hash128())
-                .for_each(|p| files.push(FileInfoNoLen { id_hash, path: p }))
+            files.extend(
+                file_group
+                    .into_iter()
+                    .inspect(|p| progress(&p.path))
+                    .unique_by(|p| p.path.hash128()),
+            )
         } else {
-            paths
-                .into_iter()
-                .inspect(|p| progress(p))
-                .unique_by(|p| file_id_or_log_err(p, &ctx.log))
-                .for_each(|p| files.push(FileInfoNoLen { id_hash, path: p }))
+            files.extend(
+                file_group
+                    .into_iter()
+                    .inspect(|p| progress(&p.path))
+                    .unique_by(|p| file_id_or_log_err(&p.path, &ctx.log)),
+            )
         }
     }
 }
 
-fn remove_same_files(
-    ctx: &mut AppCtx,
-    groups: Vec<FileGroup<FileInfoNoLen>>,
-) -> Vec<FileGroup<Path>> {
+fn remove_same_files(ctx: &AppCtx, groups: Vec<FileGroup<FileInfo>>) -> Vec<FileGroup<FileInfo>> {
     let file_count: usize = groups.total_count();
     let progress = ctx
         .log
@@ -191,7 +179,6 @@ fn remove_same_files(
         .into_par_iter()
         .update(|g| deduplicate(ctx, &mut g.files, |_| progress.tick()))
         .filter(|g| g.files.len() > rf_over)
-        .map(to_group_of_paths)
         .collect();
 
     let count: usize = groups.selected_count(rf_over, rf_under);
@@ -209,50 +196,84 @@ fn remove_same_files(
     groups
 }
 
+#[cfg(target_os = "linux")]
+fn atomic_counter_vec(len: usize) -> Vec<AtomicU32> {
+    let mut v = Vec::with_capacity(len);
+    for _ in 0..len {
+        v.push(AtomicU32::new(0));
+    }
+    v
+}
+
+#[cfg(target_os = "linux")]
+fn update_file_locations(ctx: &AppCtx, groups: &mut Vec<FileGroup<FileInfo>>) {
+    let count = groups.total_count();
+    let progress = ctx.log.progress_bar("Fetching extents", count as u64);
+
+    let err_counters = atomic_counter_vec(ctx.devices.len());
+    const MAX_ERR_COUNT_TO_LOG: u32 = 10;
+
+    groups
+        .par_iter_mut()
+        .flat_map(|g| &mut g.files)
+        .update(|fi| {
+            let device: &DiskDevice = &ctx.devices[fi.get_device_index()];
+            if device.disk_type != sysinfo::DiskType::SSD {
+                if let Err(e) = fi.fetch_physical_location() {
+                    let counter = &err_counters[device.index];
+                    if counter.load(Ordering::Relaxed) < MAX_ERR_COUNT_TO_LOG {
+                        let err_count = counter.fetch_add(1, Ordering::SeqCst);
+                        if err_count < MAX_ERR_COUNT_TO_LOG {
+                            ctx.log.warn(format!(
+                                "Failed to fetch extents for file {}: {}",
+                                fi.path, e
+                            ));
+                            if err_count + 1 == MAX_ERR_COUNT_TO_LOG {
+                                ctx.log.warn(
+                                    "Too many fetch extents errors. \
+                                    More errors will be ignored. \
+                                    Random access performance might be affected on spinning drives.",
+                                )
+                            }
+                        }
+                    }
+                }
+            }
+        })
+        .for_each(|_| progress.tick());
+}
+
 /// Transforms files by piping them to an external program and groups them by their hashes
 fn group_transformed(
-    ctx: &mut AppCtx,
+    ctx: &AppCtx,
     transform: &Transform,
-    groups: Vec<FileGroup<Path>>,
-) -> Vec<FileGroup<Path>> {
+    groups: Vec<FileGroup<FileInfo>>,
+) -> Vec<FileGroup<FileInfo>> {
     let file_count: usize = groups.total_count();
-    let progress = ctx.log.progress_bar("Transforming", file_count as u64);
-
-    let files: Vec<_> = groups
-        .into_par_iter()
-        .flat_map(|g| {
-            g.files
-                .into_par_iter()
-                .inspect(|_| progress.tick())
-                .filter_map(|f: Path| {
-                    let result = transform.run_or_log_err(&f, &ctx.log);
-                    result.map(|(len, hash)| (len, hash, f))
-                })
-                .collect::<Vec<_>>()
-        })
-        .collect();
-
-    drop(progress);
-    let progress = ctx.log.progress_bar("Grouping by hash", files.len() as u64);
-    let mut groups = GroupMap::new(|(len, hash, path)| ((len, hash), path));
-    for f in files {
-        progress.tick();
-        groups.add(f);
-    }
+    let progress = ctx
+        .log
+        .progress_bar("Transforming & grouping", file_count as u64);
 
     let rf_over = ctx.config.rf_over();
     let rf_under = ctx.config.rf_under();
 
-    let groups: Vec<_> = groups
-        .into_iter()
-        .filter(|(_, files)| files.len() > rf_over)
-        .map(|((len, hash), files)| FileGroup {
-            file_len: len,
-            hash,
-            prefix_len: len,
-            files: files.into_vec(),
-        })
-        .collect();
+    let groups = rehash(
+        groups,
+        |_| true,
+        |g| g.files.len() > rf_over,
+        &ctx.devices,
+        AccessType::Sequential,
+        |(fi, _)| {
+            let result = transform
+                .run_or_log_err(&fi.path, &ctx.log)
+                .map(|(len, hash)| {
+                    fi.len = len;
+                    hash
+                });
+            progress.tick();
+            result
+        },
+    );
 
     let count = groups.selected_count(rf_over, rf_under);
     let bytes = groups.selected_size(rf_over, rf_under);
@@ -265,22 +286,38 @@ fn group_transformed(
     groups
 }
 
-/// Returns the desired prefix length for the given group of files.
+/// Returns the maximum value of the given property of the device,
+/// among the devices actually used to store any of the given files
+fn max_device_property<'a>(
+    devices: &DiskDevices,
+    files: impl ParallelIterator<Item = &'a FileInfo>,
+    property_fn: impl Fn(&DiskDevice) -> FileLen + Sync,
+) -> FileLen {
+    files
+        .into_par_iter()
+        .map(|f| property_fn(&devices[f.get_device_index()]))
+        .max()
+        .unwrap_or_else(|| property_fn(devices.get_default()))
+}
+
+/// Returns the desired prefix length for a group of files.
 /// The return value depends on the capabilities of the devices the files are stored on.
 /// Higher values are desired if any of the files resides on an HDD.
-fn prefix_len(partitions: &DiskDevices, g: &FileGroup<Path>) -> FileLen {
-    let v: Vec<&DiskDevice> = g.files.iter().map(|p| partitions.get_by_path(p)).collect();
-    let max_prefix_len = v.iter().map(|&p| p.max_prefix_len()).max().unwrap();
-    let min_prefix_len = v.iter().map(|&p| p.min_prefix_len()).max().unwrap();
-    if g.file_len <= max_prefix_len {
-        g.file_len
-    } else {
-        min_prefix_len
-    }
+fn prefix_len<'a>(
+    partitions: &DiskDevices,
+    files: impl ParallelIterator<Item = &'a FileInfo>,
+) -> FileLen {
+    max_device_property(partitions, files, |dd| dd.max_prefix_len())
 }
 
-fn group_by_prefix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGroup<Path>> {
-    let remaining_files = groups.iter().filter(|g| g.files.len() > 1).total_count();
+/// Groups files by a hash of their first few thousand bytes.
+fn group_by_prefix(
+    ctx: &AppCtx,
+    prefix_len: FileLen,
+    groups: Vec<FileGroup<FileInfo>>,
+) -> Vec<FileGroup<FileInfo>> {
+    let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1;
+    let remaining_files = groups.iter().filter(|&g| pre_filter(g)).total_count();
     let progress = ctx
         .log
         .progress_bar("Grouping by prefix", remaining_files as u64);
@@ -288,31 +325,33 @@ fn group_by_prefix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGr
     let rf_over = ctx.config.rf_over();
     let rf_under = ctx.config.rf_under();
 
-    let groups: Vec<_> = groups
-        .into_par_iter()
-        .flat_map(|g| {
-            let prefix_len = prefix_len(&ctx.devices, &g);
-            let caching = if g.file_len <= prefix_len {
-                Caching::Default
+    let groups = rehash(
+        groups,
+        pre_filter,
+        |g| g.files.len() > rf_over,
+        &ctx.devices,
+        AccessType::Random,
+        |(fi, _)| {
+            progress.tick();
+            let device = &ctx.devices[fi.get_device_index()];
+            let buf_len = device.buf_len();
+            let (caching, prefix_len) = if fi.len <= prefix_len {
+                (Caching::Default, prefix_len)
             } else {
-                Caching::Random
+                (Caching::Random, device.min_prefix_len())
             };
-            g.split(true, prefix_len, |path| {
-                let buf_len = ctx.devices.get_by_path(&path).buf_len();
-                progress.tick();
-                file_hash_or_log_err(
-                    path,
-                    FilePos(0),
-                    prefix_len,
-                    buf_len,
-                    caching,
-                    |_| {},
-                    &ctx.log,
-                )
-            })
-        })
-        .filter(|g| g.files.len() > rf_over)
-        .collect();
+
+            file_hash_or_log_err(
+                &fi.path,
+                FilePos(0),
+                prefix_len,
+                buf_len,
+                caching,
+                |_| {},
+                &ctx.log,
+            )
+        },
+    );
 
     let count = groups.selected_count(rf_over, rf_under);
     let bytes = groups.selected_size(rf_over, rf_under);
@@ -323,25 +362,28 @@ fn group_by_prefix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGr
     groups
 }
 
-fn suffix_threshold(partitions: &DiskDevices, g: &FileGroup<Path>) -> FileLen {
-    let v: Vec<&DiskDevice> = g.files.iter().map(|p| partitions.get_by_path(p)).collect();
-    v.iter().map(|&p| p.suffix_threshold()).max().unwrap()
+/// Returns the desired suffix length for a group of files.
+/// The return value depends on the capabilities of the devices the files are stored on.
+/// Higher values are desired if any of the files resides on an HDD.
+fn suffix_len<'a>(
+    partitions: &DiskDevices,
+    files: impl ParallelIterator<Item = &'a FileInfo>,
+) -> FileLen {
+    max_device_property(partitions, files, |dd| dd.suffix_len())
 }
 
-fn suffix_len(partitions: &DiskDevices, g: &FileGroup<Path>) -> FileLen {
-    let v: Vec<&DiskDevice> = g.files.iter().map(|p| partitions.get_by_path(p)).collect();
-    v.iter().map(|&p| p.suffix_len()).max().unwrap()
+fn suffix_threshold<'a>(
+    partitions: &DiskDevices,
+    files: impl ParallelIterator<Item = &'a FileInfo>,
+) -> FileLen {
+    max_device_property(partitions, files, |dd| dd.suffix_threshold())
 }
 
-fn group_by_suffix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGroup<Path>> {
-    let needs_processing = |partitions: &DiskDevices, g: &FileGroup<Path>| {
-        g.file_len >= suffix_threshold(partitions, g) && g.files.len() > 1
-    };
-
-    let remaining_files = groups
-        .iter()
-        .filter(|&g| (needs_processing)(&ctx.devices, g))
-        .total_count();
+fn group_by_suffix(ctx: &AppCtx, groups: Vec<FileGroup<FileInfo>>) -> Vec<FileGroup<FileInfo>> {
+    let suffix_len = suffix_len(&ctx.devices, flat_iter(&groups));
+    let suffix_threshold = suffix_threshold(&ctx.devices, flat_iter(&groups));
+    let pre_filter = |g: &FileGroup<FileInfo>| g.file_len >= suffix_threshold && g.files.len() > 1;
+    let remaining_files = groups.iter().filter(|&g| pre_filter(g)).total_count();
     let progress = ctx
         .log
         .progress_bar("Grouping by suffix", remaining_files as u64);
@@ -349,30 +391,28 @@ fn group_by_suffix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGr
     let rf_over = ctx.config.rf_over();
     let rf_under = ctx.config.rf_under();
 
-    let groups: Vec<_> = groups
-        .into_par_iter()
-        .flat_map(|g| {
-            let file_len = g.file_len;
-            let prefix_len = g.prefix_len;
-            let suffix_len = suffix_len(&ctx.devices, &g);
-            let needs_processing = needs_processing(&ctx.devices, &g);
-
-            g.split(needs_processing, prefix_len, |path| {
-                progress.tick();
-                let buf_len = ctx.devices.get_by_path(&path).buf_len();
-                file_hash_or_log_err(
-                    path,
-                    file_len.as_pos() - suffix_len,
-                    suffix_len,
-                    buf_len,
-                    Caching::Default,
-                    |_| {},
-                    &ctx.log,
-                )
-            })
-        })
-        .filter(|g| g.files.len() > rf_over)
-        .collect();
+    let groups = rehash(
+        groups,
+        pre_filter,
+        |g| g.files.len() > rf_over,
+        &ctx.devices,
+        AccessType::Random,
+        |(fi, old_hash)| {
+            progress.tick();
+            let device = &ctx.devices[fi.get_device_index()];
+            let buf_len = device.buf_len();
+            file_hash_or_log_err(
+                &fi.path,
+                fi.len.as_pos() - suffix_len,
+                suffix_len,
+                buf_len,
+                Caching::Default,
+                |_| {},
+                &ctx.log,
+            )
+            .map(|new_hash| old_hash ^ new_hash)
+        },
+    );
 
     let count = groups.selected_count(rf_over, rf_under);
     let bytes = groups.selected_size(rf_over, rf_under);
@@ -383,65 +423,40 @@ fn group_by_suffix(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGr
     groups
 }
 
-fn group_by_contents(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<FileGroup<Path>> {
-    let needs_processing = |g: &FileGroup<Path>| g.file_len >= g.prefix_len && g.files.len() > 1;
-    let bytes_to_scan = groups.iter().filter(|&g| needs_processing(g)).total_size();
+fn group_by_contents(
+    ctx: &AppCtx,
+    min_file_len: FileLen,
+    groups: Vec<FileGroup<FileInfo>>,
+) -> Vec<FileGroup<FileInfo>> {
+    let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1 && g.file_len >= min_file_len;
+    let bytes_to_scan = groups.iter().filter(|&g| pre_filter(g)).total_size();
     let progress = &ctx
         .log
         .bytes_progress_bar("Grouping by contents", bytes_to_scan.0);
+
     let rf_over = ctx.config.rf_over();
     let rf_under = ctx.config.rf_under();
 
-    let (tx, rx) = channel();
-    let thread_pools = ctx.devices.thread_pools();
-    let ctx = &*ctx; // drop mutability to allow sharing
-
-    multi_scope(&thread_pools, move |scopes| {
-        for group in groups.into_iter() {
-            let needs_processing = needs_processing(&group);
-            for path in group.files.into_iter() {
-                let tx = tx.clone();
-                let scope = scopes[ctx.devices.get_by_path(&path).index];
-                let len = group.file_len;
-                let buf_len = ctx.devices.get_by_path(&path).buf_len();
-                let hash = group.hash;
-                if needs_processing {
-                    scope.spawn(move |_| {
-                        let hash = file_hash_or_log_err(
-                            &path,
-                            FilePos(0),
-                            len,
-                            buf_len,
-                            Caching::Sequential,
-                            |delta| progress.inc(delta),
-                            &ctx.log,
-                        );
-                        if let Some(hash) = hash {
-                            tx.send((path, len, hash)).unwrap()
-                        }
-                    });
-                } else {
-                    tx.send((path, len, hash)).unwrap();
-                }
-            }
-        }
-    });
-
-    let mut groups = GroupMap::new(|(path, len, hash)| ((len, hash), path));
-    for (path, len, hash) in rx.into_iter() {
-        groups.add((path, len, hash));
-    }
-
-    let groups: Vec<_> = groups
-        .into_iter()
-        .filter(|(_, paths)| paths.len() > rf_over)
-        .map(|((len, hash), paths)| FileGroup {
-            file_len: len,
-            prefix_len: len,
-            hash,
-            files: paths.to_vec(),
-        })
-        .collect();
+    let groups = rehash(
+        groups,
+        pre_filter,
+        |g| g.files.len() > rf_over,
+        &ctx.devices,
+        AccessType::Sequential,
+        |(fi, _)| {
+            let device = &ctx.devices[fi.get_device_index()];
+            let buf_len = device.buf_len();
+            file_hash_or_log_err(
+                &fi.path,
+                FilePos(0),
+                fi.len,
+                buf_len,
+                Caching::Sequential,
+                |delta| progress.inc(delta),
+                &ctx.log,
+            )
+        },
+    );
 
     let count = groups.selected_count(rf_over, rf_under);
     let bytes = groups.selected_size(rf_over, rf_under);
@@ -454,7 +469,7 @@ fn group_by_contents(ctx: &mut AppCtx, groups: Vec<FileGroup<Path>>) -> Vec<File
     groups
 }
 
-fn write_report(ctx: &mut AppCtx, groups: &[FileGroup<Path>]) {
+fn write_report(ctx: &AppCtx, groups: &[FileGroup<Path>]) {
     let remaining_files = groups.total_count();
     let progress = ctx
         .log
@@ -493,7 +508,7 @@ fn stdout_reporter(progress: Arc<FastProgressBar>) -> Reporter<Box<dyn Write>> {
 /// Writes and error message and exists the application if the file cannot be open.
 fn file_reporter(
     ctx: &AppCtx,
-    path: &PathBuf,
+    path: &std::path::Path,
     progress: Arc<FastProgressBar>,
 ) -> Reporter<Box<dyn Write>> {
     match File::create(path) {
@@ -522,7 +537,6 @@ fn paint_help(s: &str) -> String {
 
 fn main() {
     let mut log = Log::new();
-
     let after_help = &paint_help(indoc!(
         "
     # PATTERN SYNTAX:
@@ -562,13 +576,18 @@ fn main() {
         log.no_progress = true;
     }
 
+    log.info("Started");
     let mut thread_pool_sizes = config.thread_pool_sizes();
     configure_main_thread_pool(&mut thread_pool_sizes);
 
-    let mut ctx = AppCtx {
+    let device_scanning_spinner = log.spinner("Fetching disk device list");
+    let devices = DiskDevices::new(&mut thread_pool_sizes);
+    drop(device_scanning_spinner);
+
+    let ctx = AppCtx {
         log,
         config,
-        devices: DiskDevices::new(&mut thread_pool_sizes),
+        devices,
     };
     ctx.config.check_transform(&ctx.log);
     ctx.config
@@ -587,26 +606,40 @@ fn main() {
         }
     }
 
-    let results = process(&mut ctx);
-    write_report(&mut ctx, &results)
+    let results = process(&ctx);
+    write_report(&ctx, &results)
 }
 
 // Extracted for testing
-fn process(mut ctx: &mut AppCtx) -> Vec<FileGroup<Path>> {
-    ctx.log.info("Started");
-    let matching_files = scan_files(&mut ctx);
-    let size_groups = group_by_size(&mut ctx, matching_files);
-    let size_groups_pruned = remove_same_files(&mut ctx, size_groups);
-    let mut groups = match ctx.config.take_transform(&ctx.log) {
+fn process(ctx: &AppCtx) -> Vec<FileGroup<Path>> {
+    let matching_files = scan_files(&ctx);
+    let size_groups = group_by_size(&ctx, matching_files);
+
+    #[allow(unused_mut)]
+    let mut size_groups_pruned = remove_same_files(&ctx, size_groups);
+
+    #[cfg(target_os = "linux")]
+    update_file_locations(ctx, &mut size_groups_pruned);
+
+    let groups = match ctx.config.transform(&ctx.log) {
         Some(transform) => group_transformed(ctx, &transform, size_groups_pruned),
         None => {
-            let prefix_groups = group_by_prefix(&mut ctx, size_groups_pruned);
-            let suffix_groups = group_by_suffix(&mut ctx, prefix_groups);
-            group_by_contents(&mut ctx, suffix_groups)
+            let prefix_len = prefix_len(&ctx.devices, flat_iter(&size_groups_pruned));
+            let prefix_groups = group_by_prefix(&ctx, prefix_len, size_groups_pruned);
+            let suffix_groups = group_by_suffix(&ctx, prefix_groups);
+            group_by_contents(&ctx, prefix_len, suffix_groups)
         }
     };
+    let mut groups: Vec<_> = groups
+        .into_par_iter()
+        .map(|g| FileGroup {
+            file_len: g.file_len,
+            file_hash: g.file_hash,
+            files: g.files.into_iter().map(|fi| fi.path).collect(),
+        })
+        .collect();
     groups.retain(|g| g.files.len() < ctx.config.rf_under());
-    groups.par_sort_by_key(|g| Reverse((g.file_len, g.hash)));
+    groups.par_sort_by_key(|g| Reverse((g.file_len, g.file_hash)));
     groups.par_iter_mut().for_each(|g| g.files.sort());
     groups
 }
@@ -635,7 +668,7 @@ mod test {
 
             let mut ctx = test_ctx();
             ctx.config.paths = vec![file1, file2];
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 1);
             assert_eq!(results[0].file_len, FileLen(3));
             assert_eq!(results[0].files.len(), 2);
@@ -653,7 +686,7 @@ mod test {
             let mut ctx = test_ctx();
             ctx.config.paths = vec![file1, file2];
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 1);
             assert_eq!(results[0].files.len(), 2);
         });
@@ -671,7 +704,7 @@ mod test {
             ctx.config.paths = vec![file1.clone(), file2.clone()];
             ctx.config.rf_over = Some(0);
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 2);
             assert_eq!(
                 results[0].files,
@@ -696,7 +729,7 @@ mod test {
             ctx.config.paths = vec![file1.clone(), file2.clone()];
             ctx.config.unique = true;
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 2);
             assert_eq!(results[0].files.len(), 1);
             assert_eq!(results[1].files.len(), 1);
@@ -717,7 +750,7 @@ mod test {
             ctx.config.paths = vec![file1.clone(), file2.clone()];
             ctx.config.unique = true;
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 2);
             assert_eq!(results[0].files.len(), 1);
             assert_eq!(results[1].files.len(), 1);
@@ -738,7 +771,7 @@ mod test {
             ctx.config.paths = vec![file1.clone(), file2.clone()];
             ctx.config.unique = true;
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 2);
             assert_eq!(results[0].files.len(), 1);
             assert_eq!(results[1].files.len(), 1);
@@ -757,7 +790,7 @@ mod test {
             ctx.config.paths = vec![file1.clone(), file2.clone()];
             ctx.config.unique = true;
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 1);
             assert_eq!(results[0].files.len(), 1);
         });
@@ -773,7 +806,7 @@ mod test {
             ctx.config.unique = true;
             ctx.config.hard_links = true;
 
-            let results = process(&mut ctx);
+            let results = process(&ctx);
             assert_eq!(results.len(), 1);
             assert_eq!(results[0].files.len(), 1);
         });
@@ -799,7 +832,7 @@ mod test {
                 ctx.config.unique = true;
                 ctx.config.hard_links = true;
 
-                let results = process(&mut ctx);
+                let results = process(&ctx);
                 assert_eq!(results.len(), 1);
                 assert_eq!(results[0].files.len(), 1);
             },
@@ -818,8 +851,8 @@ mod test {
             ctx.config.unique = true;
             ctx.config.output = Some(report_file.clone());
 
-            let results = process(&mut ctx);
-            write_report(&mut ctx, &results);
+            let results = process(&ctx);
+            write_report(&ctx, &results);
 
             assert!(report_file.exists());
             let mut report = String::new();
diff --git a/src/pattern.rs b/src/pattern.rs
index 8ed9240..7f9f1c4 100644
--- a/src/pattern.rs
+++ b/src/pattern.rs
@@ -1,6 +1,6 @@
 use std::fmt::{Display, Formatter};
 use std::ops::Add;
-use std::path::{PathBuf, MAIN_SEPARATOR};
+use std::path::{Path, MAIN_SEPARATOR};
 
 use nom::branch::alt;
 use nom::bytes::complete::tag;
@@ -177,7 +177,7 @@ impl Pattern {
     }
 
     /// Returns true if this pattern fully matches given file path
-    pub fn matches_path(&self, path: &PathBuf) -> bool {
+    pub fn matches_path(&self, path: &Path) -> bool {
         self.anchored_regex
             .is_match(path.to_string_lossy().as_bytes())
             .unwrap_or(false)
@@ -307,6 +307,7 @@ impl ToString for Pattern {
 #[cfg(test)]
 mod test {
     use super::*;
+    use std::path::PathBuf;
 
     fn glob_to_regex_str(glob: &str) -> String {
         Pattern::glob(glob).unwrap().to_string()
diff --git a/src/pools.rs b/src/pools.rs
deleted file mode 100644
index a01f558..0000000
--- a/src/pools.rs
+++ /dev/null
@@ -1,88 +0,0 @@
-use rayon::{Scope, ThreadPool};
-
-/// Constructs scopes recursively.
-/// Each recursion level takes (and removes) the first thread pool from
-/// `pools`, creates a scope and pushes it into the `scopes` vector, then calls the next
-/// recursion level inside this scope. Finally it calls `op` passing all the scopes to it.
-fn nest<'scope, OP, R>(pools: &[&ThreadPool], scopes: Vec<&Scope<'scope>>, op: OP) -> R
-where
-    OP: for<'s> FnOnce(&'s [&'s Scope<'scope>]) -> R + Send,
-    R: Send,
-{
-    if !pools.is_empty() {
-        pools[0].scope(move |s| {
-            let mut scopes: Vec<&Scope<'scope>> = scopes;
-            scopes.push(s);
-            nest(&pools[1..], scopes, op)
-        })
-    } else {
-        (op)(&scopes)
-    }
-}
-
-/// Creates multiple Rayon scopes, one per given `ThreadPool`, around the given lambda `op`.
-/// The purpose of this method is to be able to spawn tasks on multiple thread pools when
-/// the number of thread pools is not known at compile-time. Same as with a single scope,
-/// all tasks spawned by `op` are guaranteed to finish before this call exits, so they
-/// are allowed to access structs from outside of the scope.
-///
-/// # Example
-/// ```
-/// use rayon::ThreadPoolBuilder;
-/// use fclones::pools::multi_scope;
-///
-/// let pool1 = ThreadPoolBuilder::new().build().unwrap();
-/// let pool2 = ThreadPoolBuilder::new().build().unwrap();
-/// let common = vec![0, 1, 2]; // common data, must be Send
-/// multi_scope(&[&pool1, &pool2], |scopes| {
-///     scopes[0].spawn(|_| { /* execute on pool1, can use &common */ });
-///     scopes[1].spawn(|_| { /* execute on pool2, can use &common */ });
-/// });
-/// ```
-pub fn multi_scope<'scope, OP, R>(pools: &[&ThreadPool], op: OP) -> R
-where
-    OP: for<'s> FnOnce(&'s [&'s Scope<'scope>]) -> R + Send,
-    R: Send,
-{
-    nest(pools, Vec::with_capacity(pools.len()), op)
-}
-
-#[cfg(test)]
-mod test {
-    use super::*;
-    use rayon::ThreadPoolBuilder;
-    use std::collections::HashSet;
-    use std::sync::mpsc::channel;
-    use std::thread::ThreadId;
-
-    fn distinct_thread_count(pool_id: i32, pairs: &Vec<(i32, ThreadId)>) -> usize {
-        pairs
-            .iter()
-            .filter(|(p_id, _)| *p_id == pool_id)
-            .map(|(_, thread_id)| thread_id)
-            .collect::<HashSet<_>>()
-            .len()
-    }
-
-    #[test]
-    fn test_two_pools() {
-        let pool0 = ThreadPoolBuilder::new().num_threads(1).build().unwrap();
-        let pool1 = ThreadPoolBuilder::new().num_threads(2).build().unwrap();
-
-        let (tx, rx) = channel();
-        multi_scope(&[&pool0, &pool1], move |scopes| {
-            for _ in 0..1000 {
-                let tx = tx.clone();
-                scopes[0].spawn(move |_| tx.send((0, std::thread::current().id())).unwrap());
-            }
-            for _ in 0..1000 {
-                let tx = tx.clone();
-                scopes[1].spawn(move |_| tx.send((1, std::thread::current().id())).unwrap());
-            }
-        });
-
-        let results: Vec<_> = rx.into_iter().collect();
-        assert_eq!(distinct_thread_count(0, &results), 1);
-        assert_eq!(distinct_thread_count(1, &results), 2);
-    }
-}
diff --git a/src/report.rs b/src/report.rs
index 12b35be..0681c67 100644
--- a/src/report.rs
+++ b/src/report.rs
@@ -39,7 +39,7 @@ impl<W: Write> Reporter<W> {
     pub fn write_as_text(&mut self, results: &[FileGroup<Path>]) -> io::Result<()> {
         for g in results {
             let len = style(format!("{:8}", g.file_len)).yellow().bold();
-            let hash = style(format!("{}", g.hash)).blue().bold().bright();
+            let hash = style(format!("{}", g.file_hash)).blue().bold().bright();
             writeln!(
                 self.out,
                 "{} {}:",
@@ -87,7 +87,7 @@ impl<W: Write> Reporter<W> {
         for g in results {
             let mut record = csv::StringRecord::new();
             record.push_field(g.file_len.0.to_string().as_str());
-            record.push_field(g.hash.to_string().as_str());
+            record.push_field(g.file_hash.to_string().as_str());
             record.push_field(g.files.len().to_string().as_str());
             for f in g.files.iter() {
                 record.push_field(f.to_string_lossy().as_ref());
diff --git a/src/semaphore.rs b/src/semaphore.rs
new file mode 100644
index 0000000..da40a6a
--- /dev/null
+++ b/src/semaphore.rs
@@ -0,0 +1,233 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+//
+// Owned guards added by Piotr Kołaczkowski
+
+use std::ops::Drop;
+use std::sync::{Arc, Condvar, Mutex};
+
+/// A counting, blocking, semaphore.
+///
+/// Semaphores are a form of atomic counter where access is only granted if the
+/// counter is a positive value. Each acquisition will block the calling thread
+/// until the counter is positive, and each release will increment the counter
+/// and unblock any threads if necessary.
+///
+/// # Examples
+///
+/// ```
+/// use std_semaphore::Semaphore;
+///
+/// // Create a semaphore that represents 5 resources
+/// let sem = Semaphore::new(5);
+///
+/// // Acquire one of the resources
+/// sem.acquire();
+///
+/// // Acquire one of the resources for a limited period of time
+/// {
+///     let _guard = sem.access();
+///     // ...
+/// } // resources is released here
+///
+/// // Release our initially acquired resource
+/// sem.release();
+/// ```
+pub struct Semaphore {
+    lock: Mutex<isize>,
+    cvar: Condvar,
+}
+
+/// An RAII guard which will release a resource acquired from a semaphore when
+/// dropped.
+pub struct SemaphoreGuard<'a> {
+    sem: &'a Semaphore,
+}
+
+/// An RAII guard which will release a resource acquired from a semaphore when
+/// dropped. This guard allows the semaphore to be acquired on a different thread than
+/// released.
+pub struct OwnedSemaphoreGuard {
+    sem: Arc<Semaphore>,
+}
+
+#[allow(clippy::mutex_atomic)]
+impl Semaphore {
+    /// Creates a new semaphore with the initial count specified.
+    ///
+    /// The count specified can be thought of as a number of resources, and a
+    /// call to `acquire` or `access` will block until at least one resource is
+    /// available. It is valid to initialize a semaphore with a negative count.
+    pub fn new(count: isize) -> Semaphore {
+        Semaphore {
+            lock: Mutex::new(count),
+            cvar: Condvar::new(),
+        }
+    }
+
+    /// Acquires a resource of this semaphore, blocking the current thread until
+    /// it can do so.
+    ///
+    /// This method will block until the internal count of the semaphore is at
+    /// least 1.
+    pub fn acquire(&self) {
+        let mut count = self.lock.lock().unwrap();
+        while *count <= 0 {
+            count = self.cvar.wait(count).unwrap();
+        }
+        *count -= 1;
+    }
+
+    /// Release a resource from this semaphore.
+    ///
+    /// This will increment the number of resources in this semaphore by 1 and
+    /// will notify any pending waiters in `acquire` or `access` if necessary.
+    pub fn release(&self) {
+        *self.lock.lock().unwrap() += 1;
+        self.cvar.notify_one();
+    }
+
+    /// Acquires a resource of this semaphore, returning an RAII guard to
+    /// release the semaphore when dropped.
+    ///
+    /// This function is semantically equivalent to an `acquire` followed by a
+    /// `release` when the guard returned is dropped.
+    pub fn access(&self) -> SemaphoreGuard<'_> {
+        self.acquire();
+        SemaphoreGuard { sem: self }
+    }
+
+    /// Acquires a resource of this semaphore, returning an RAII guard to
+    /// release the semaphore when dropped. Allows moving the guard to a different
+    /// thread.
+    ///
+    /// This function is semantically equivalent to an `acquire` followed by a
+    /// `release` when the guard returned is dropped.
+    pub fn access_owned(self: Arc<Self>) -> OwnedSemaphoreGuard {
+        self.acquire();
+        OwnedSemaphoreGuard { sem: self }
+    }
+}
+
+impl<'a> Drop for SemaphoreGuard<'a> {
+    fn drop(&mut self) {
+        self.sem.release();
+    }
+}
+
+impl Drop for OwnedSemaphoreGuard {
+    fn drop(&mut self) {
+        self.sem.release();
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::prelude::v1::*;
+
+    use super::Semaphore;
+    use std::sync::mpsc::channel;
+    use std::sync::Arc;
+    use std::thread;
+
+    #[test]
+    fn test_sem_acquire_release() {
+        let s = Semaphore::new(1);
+        s.acquire();
+        s.release();
+        s.acquire();
+    }
+
+    #[test]
+    fn test_sem_basic() {
+        let s = Semaphore::new(1);
+        let _g = s.access();
+    }
+
+    #[test]
+    fn test_sem_as_mutex() {
+        let s = Arc::new(Semaphore::new(1));
+        let s2 = s.clone();
+        let _t = thread::spawn(move || {
+            let _g = s2.access();
+        });
+        let _g = s.access();
+    }
+
+    #[test]
+    fn test_sem_as_mutex_owned_guard() {
+        let s = Arc::new(Semaphore::new(1));
+        let g = s.clone().access_owned();
+        let _t = thread::spawn(move || {
+            drop(g);
+        });
+        let _g = s.access();
+    }
+
+    #[test]
+    fn test_sem_as_cvar() {
+        // Child waits and parent signals
+        let (tx, rx) = channel();
+        let s = Arc::new(Semaphore::new(0));
+        let s2 = s.clone();
+        let _t = thread::spawn(move || {
+            s2.acquire();
+            tx.send(()).unwrap();
+        });
+        s.release();
+        let _ = rx.recv();
+
+        // Parent waits and child signals
+        let (tx, rx) = channel();
+        let s = Arc::new(Semaphore::new(0));
+        let s2 = s.clone();
+        let _t = thread::spawn(move || {
+            s2.release();
+            let _ = rx.recv();
+        });
+        s.acquire();
+        tx.send(()).unwrap();
+    }
+
+    #[test]
+    fn test_sem_multi_resource() {
+        // Parent and child both get in the critical section at the same
+        // time, and shake hands.
+        let s = Arc::new(Semaphore::new(2));
+        let s2 = s.clone();
+        let (tx1, rx1) = channel();
+        let (tx2, rx2) = channel();
+        let _t = thread::spawn(move || {
+            let _g = s2.access();
+            let _ = rx2.recv();
+            tx1.send(()).unwrap();
+        });
+        let _g = s.access();
+        tx2.send(()).unwrap();
+        rx1.recv().unwrap();
+    }
+
+    #[test]
+    fn test_sem_runtime_friendly_blocking() {
+        let s = Arc::new(Semaphore::new(1));
+        let s2 = s.clone();
+        let (tx, rx) = channel();
+        {
+            let _g = s.access();
+            thread::spawn(move || {
+                tx.send(()).unwrap();
+                drop(s2.access());
+                tx.send(()).unwrap();
+            });
+            rx.recv().unwrap(); // wait for child to come alive
+        }
+        rx.recv().unwrap(); // wait for child to be done
+    }
+}
diff --git a/src/transform.rs b/src/transform.rs
index e023697..26c2998 100644
--- a/src/transform.rs
+++ b/src/transform.rs
@@ -311,7 +311,7 @@ impl Transform {
     }
 
     #[cfg(unix)]
-    fn create_named_pipe(path: &PathBuf) -> io::Result<()> {
+    fn create_named_pipe(path: &std::path::Path) -> io::Result<()> {
         use nix::sys::stat;
         use nix::unistd::mkfifo;
         if let Err(e) = mkfifo(path, stat::Mode::S_IRWXU) {


Test patch: