Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The fastest rm command and one of the fastest cp commands

alexsaveau.dev

Post reply on HN
Print view View original

61–70 of 83 posts

Re: The fastest rm command and one of the fastest cp commands

#61

Post by preseinger »

mort96 wrote: post #37
preseinger wrote: post #18

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

Parallel execution absolutely helps when operations are IO bound, if they're more or less independent. Making two network requests in parallel is twice as fast as making them sequentially, if the payload is small enough so that latency dominates and bandwidth is negligible. The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't…

making two io-bound requests in parallel is twice as fast as making them sequentially, only if they don't contend for the same io resource -- bandwidth, disk iops, etc.

maybe this is what you mean by independent?

but the thing is that in disk io, directory structure is (as far as i know) basically unrelated to relevant contentious resources, when measuring speed

maybe if you're doing a billion small files than overhead begins to matter, but copying 3 big files from 3 different directories is gonna take just as long if you do them in parallel vs. if you do them sequentially

that may not be true if they're on different disks, but that kind of proves my point, the directory isn't the factor, the underlying disk is

> The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't block each other.

yeah and in this sense the article is misleading, because (as far as i know) directories are basically unrelated to independence in the general case

Re: The fastest rm command and one of the fastest cp commands

#62

Post by preseinger »

imtringued wrote: post #43
preseinger wrote: post #18

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

Synchronous file system IO throughput is inversely correlated with latency. If you have a remote network then using multiple connections at the same time allows linear performance improvements until you have maxed out the throughout of your network link or remote filesystem.

yes, or the remote network link, or any middlebox between you and they

but this is all a bit tangential as the article is about file system stuff

Re: The fastest rm command and one of the fastest cp commands

#63

Post by zamalek »

vlovich123 wrote: post #60
zamalek wrote: post #53

Earlier quoted context omitted.

You interpreted it the wrong way. You gain concurrency, you gain latency. With blocking I/O and parallelism you have a thread ready to go when the operation is complete. You have N threads for N iops. With concurrency you have to dequeue completed work, and then delegate that work to (usually) fewer than N threads. Dequeuing completed iops takes time (it's an extra syscall), and there may not be a thread ready hand t…

I’m not aware of any latency impact from io_uring. If anything, it has lower latency because you can pipeline I/O from a single CPU which you can’t do from typically thread-based parallelism. Additionally, the processing of the ring buffer could happen on a background kernel thread (in theory not sure if it happens today) which then avoids context switching away from your thread and screwing with cache performance.

io_uring avoids the syscall overhead. Consider this intentionally bad scenario: you have one background thread pulling completions off the ringbuffer, and passing those completions to a single worker thread (nodejs would be a real example of this). In this scenario the latency of the first completion would be fantastic, but you'd have to wait for the single to become available for subsequent completions.

To be clear, the added latency here is better than the work never happening at all (which would be the result of running 1000s of threads on modern mainstream operating systems), but there is unavoidable latency if you are handling >N iops with N threads (which is intrinsic to the definition of concurrency).

I am referring to the broad, general case, much like big-O works. You can find numerous exception to big-O, such as preferring arrays over hashes when the set is very small. Let's invent big-L notation, N is the number of threads, M is number of iops. With pure parallelism you have L(N), with pure concurrency you have L(M), and with a hybrid you have L(M-N).

Re: The fastest rm command and one of the fastest cp commands

#64

Post by SUPERCILEX »

saagarjha wrote: post #10

Hmm. I appreciate the cute name for the project but I tested this on my machine (a Mac) and the results were not very impressive. I sacrificed a few of my SSD cycles to test how this is on deleting Xcode (for those unaware, it's a 11 GB mess of several hundred thousand files of varying sizes). Here are the results: $ time rm -rf Xcode.app real 0m39.850s user 0m0.429s sys 0m29.153s $ time rmz Xcode.app real 0m36.476s…

I added a clarification to the benchmarks section:

"The macOS/Windows implementations are currently equivalent to the *_rayon implementations shown in the benchmarks."

Rayon is pretty good, but clearly suboptimal as evidenced by the benchmarks.

Re: The fastest rm command and one of the fastest cp commands

#65

Post by SUPERCILEX »

rektide wrote: post #3

I cant wait to see the future where we have uring (io_uring) based tools that all work async, getting hopefully embarassingly parallel. Heck yes copying & deleting 2x as fast. Actually I'm on btrfs so reflink copy is like instant I think? I should test that better.

We're working on this! https://github.com/axboe/liburing/issues/830

Re: The fastest rm command and one of the fastest cp commands

#66

Post by SUPERCILEX »

preseinger wrote: post #18

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory."

Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/f...

---

> file operations are (almost always) io bound

This is a common misconception. It was presumably true a decade ago, but PCIe is getting exponentially faster every 3 years: https://arstechnica.com/gadgets/2022/06/months-after-finaliz...

The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s. Assuming a single core can produce 64 bytes (an entire cache line!) per cycle running at 5GHz, you're still only at 320/512=62.5% saturation. This napkin math is a little BS, but my point is that individual cores are quickly going to be outpaced by bandwidth availability.

> and totally unclear how directories represent an "interference" boundary

To add a bit more color here, it depends on how your file system is implemented. I belive Windows stores every file's metadata in a global database, so segmenting operations by directory yields no benefits. On the other hand, Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory.

[1]: https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AH...

Re: The fastest rm command and one of the fastest cp commands

#67

Post by preseinger »

SUPERCILEX wrote: post #66
preseinger wrote: post #18

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory." Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/f... --- > file operations are (al…

> The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s

is disk IO bottlenecked by NVMe/PCIe limits, or by disk iops limits?

> Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory.

again, you're handwaving on what "interfere" means

do "inode mappings" represent resources with no shared resource constraints?

is reading one "inode mapping" as fast as you can with one core independent from reading a different "inode mapping" as fast as you can with a separate core?

afaik it is not, am i wrong?

Re: The fastest rm command and one of the fastest cp commands

#68

Post by preseinger »

SUPERCILEX wrote: post #66
preseinger wrote: post #18

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory." Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/f... --- > file operations are (al…

> The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention.

why do you think this is true?

i've never heard of anything like it

directories are inodes on a file system, they are in no way "shared resources for their direct children", and there is no concept of a "directory-modifying operation" which contends with operations on any file (or directory) which is a "child" (subdir, sub-file) of that directory

your claim is totally bizarre to me, afaik it's nonsensical, but i guess i could be mistaken

Re: The fastest rm command and one of the fastest cp commands

#69

Post by SUPERCILEX »

preseinger wrote: post #68
SUPERCILEX wrote: post #66

Earlier quoted context omitted.

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory." Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/f... --- > file operations are (al…

> The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. why do you think this is true? i've never heard of anything like it directories are inodes on a file system, they are in no way "shared resources for their direct children", and there is no concept of a "directory-modifying operation" whic…

A directory is a file like anything else that contains a map of names to inodes. If you're trying to add or remove mappings (create or delete files), then clearly some synchronization must occur or the contents of the file will contain garbage. In theory you could get away with a very small critical section that says "lock bytes N through M" of the file, but then how do you deal with disk block alignment (i.e. two pairs of n-m bytes are on the same disk block, so they need to take turns anyway) and how do you deal with I/O errors (the first n-m bytes fail, but the second n-m succeed, now you have a hole with garbage).

Also no need to theorize: run the benchmark I linked for yourself. It clearly shows a massive advantage to having each thread work with its own directory.

Re: The fastest rm command and one of the fastest cp commands

#70

Post by preseinger »

SUPERCILEX wrote: post #69
preseinger wrote: post #68

Earlier quoted context omitted.

> The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. why do you think this is true? i've never heard of anything like it directories are inodes on a file system, they are in no way "shared resources for their direct children", and there is no concept of a "directory-modifying operation" whic…

A directory is a file like anything else that contains a map of names to inodes. If you're trying to add or remove mappings (create or delete files), then clearly some synchronization must occur or the contents of the file will contain garbage. In theory you could get away with a very small critical section that says "lock bytes N through M" of the file, but then how do you deal with disk block alignment (i.e. two pa…

1. your benchmarks exercise a very narrow set of use cases

2. the overhead of modifying the dirent is statistically zero compared to the costs related to manipulating the files on disk

Post reply on HN