efficient access to "rotational"; new fcntl?
About a year ago, I fixed GNU rm to avoid quadratic readdir/stat seek penalties on ext3 and ext4 that became overwhelming on directories with many entries (1M entries started to look like infloop or DoS).
From coreutils-7.0 NEWS:
chgrp, chmod, chown, chcon, du, rm: now all display linear performance, even when operating on million-entry directories on ext3 and ext4 file systems. Before, they would exhibit O(N^2) performance, due to linear per-entry seek time cost when operating on entries in readdir order. Rm was improved directly, while the others inherit the improvement from the newer version of fts in gnulib.
To do that efficiently, I changed the core readdir loop (mainly via gnulib's fts.c) to preprocess entries, when needed, by sorting them on inode, and *then* processing them. This optimization is enabled only when the affected file system is of a type likely to benefit, and when the number of directory entries is large enough to matter.
However, with e.g., an ext4 partition on non-rotational hardware like an SSD, that preprocessing is unnecessary and in fact wasted effort. I'd like to avoid the waste by querying the equivalent of /sys/.../rotational, via a syscall like fcntl or statvfs, given a file descriptor.
Is there an efficient way to get that single bit?
IMHO, locating and opening-then-reading a file like /sys/devices/pci0000:00/0000:00:1f.2/host4/target4:0:0/4:0:0:0/block/sdc/queue/rotational is not appropriate in the context of a low-level library function like fts.
Jim
Quoted 6 lines · Jim Meyering
chgrp, chmod, chown, chcon, du, rm: now all display linear performance, even when operating on million-entry directories on ext3 and ext4 file systems. Before, they would exhibit O(N^2) performance, due to linear per-entry seek time cost when operating on entries in readdir order. Rm was improved directly, while the others inherit the improvement from the newer version of fts in gnulib.
Excellent! I didn't know that (since my userspace is still Ubuntu 9.04, which is still using coreutils 6.10).
Quoted 5 lines
However, with e.g., an ext4 partition on non-rotational hardware like an SSD, that preprocessing is unnecessary and in fact wasted effort. I'd like to avoid the waste by querying the equivalent of
/sys/.../rotational, via a syscall like fcntl or statvfs, given a file descriptor.
Have you benchmarked it both ways? The preprocessing will cost some extra CPU time, sure, but for a sufficiently large directory, or if the user is deleting a very large directory hierarchy, such that "rm -rf" spans multiple journal transactions, deleting the files in inode order will still avoid some filesystem metadata blocks getting written multiple times (which for SSD's, especially the crappier ones with nasty write amplification factors) could show a performance impact.
Quoted 1 line
Is there an efficient way to get that single bit?
Not today; if it's really useful, we could add it, of course. But how much overhead are you trying to avoid by avoiding the pre-processing before unlinking the files?
Regards,
- Ted
Quoted 10 lines · Theodore Tso
Quoted 6 lines · Jim Meyering
chgrp, chmod, chown, chcon, du, rm: now all display linear performance, even when operating on million-entry directories on ext3 and ext4 file systems. Before, they would exhibit O(N^2) performance, due to linear per-entry seek time cost when operating on entries in readdir order. Rm was improved directly, while the others inherit the improvement from the newer version of fts in gnulib.
Excellent! I didn't know that (since my userspace is still Ubuntu 9.04, which is still using coreutils 6.10).
Heh. Time to upgrade.
With the upcoming coreutils-7.7, I've removed a quadratic component in rm -r (without -f), and rewrote it to give rm -rf an additional 4-5x speed-up in some nasty cases.
Quoted 6 lines
Quoted 5 lines
However, with e.g., an ext4 partition on non-rotational hardware like an SSD, that preprocessing is unnecessary and in fact wasted effort. I'd like to avoid the waste by querying the equivalent of
/sys/.../rotational, via a syscall like fcntl or statvfs, given a file descriptor.
Quoted 7 lines
Have you benchmarked it both ways? The preprocessing will cost some extra CPU time, sure, but for a sufficiently large directory, or if the user is deleting a very large directory hierarchy, such that "rm -rf" spans multiple journal transactions, deleting the files in inode order will still avoid some filesystem metadata blocks getting written multiple times (which for SSD's, especially the crappier ones with nasty write amplification factors) could show a performance impact.
Yeah, I mentioned I should do exactly that on IRC yesterday. I've just run some tests, and see that at least with one SSD (OCZ Summit 120GB), the 0.5s cost of sorting pays off handsomely with a 12-x speed-up, saving 5.5 minutes, when removing a 1-million-empty-file directory.
----------------------------------------
Timing rm -rf million-file-dir vs. ext4 on a 120GB OCZ Summit on Fedora 11 This is using the very latest rm/remove.c from coreutils.git. The one rewritten to use fts.
Creation took about 63 seconds:
mkdir d;(cd d && seq 1000000|xargs touch)
Removal with inode-sort preprocessing (the 0.543s is sort duration):
$ env time ./rm -rf d 0.543050295 1.62user 20.13system 0:28.25elapsed 77%CPU (0avgtext+0avgdata 0maxresident)k 9968inputs+8outputs (0major+74445minor)pagefaults 0swaps
2nd trial: (create million-file dir)
$ mkdir d;(cd d && seq 1000000|env time xargs touch) 0.63user 62.14system 1:06.49elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k 40inputs+16outputs (1major+19701minor)pagefaults 0swaps
Remove it:
$ env time ./rm -rf d 0.570515343 1.72user 18.49system 0:26.45elapsed 76%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+8outputs (0major+74445minor)pagefaults 0swaps ---------------------------------------------
Repeating, but with fts' sort-on-inode disabled:
ouch. It would have taken about 6 minutes.
I killed it after ~3, when it had removed half of the entries.
Conclusion:
Even on an SSD, this sort-on-inode preprocessing gives more than a 10-x speed-up when removing a 1-million-empty-file directory. Hence, fts does not need access to the "rotational" bit, after all.
Quoted 6 lines · On Sat, 19 Sep 2009 10:01:51 +0200 Jim Meyering <[email protected]> wrote:
Yeah, I mentioned I should do exactly that on IRC yesterday. I've just run some tests, and see that at least with one SSD (OCZ Summit 120GB), the 0.5s cost of sorting pays off handsomely with a 12-x speed-up, saving 5.5 minutes, when removing a 1-million-empty-file directory.
likely because you actually reduce the amount of IO; inodes share disk blocks; repeated unlinks in random order likely write the same block multiple times....
btw have you given thought about using threads as part of rm -r[f] ? (would make the unlinks of unrelated directories/files asynchronous)
Signature · 3 lines
Arjan van de Ven Intel Open Source Technology Centre For development, discussion and tips for power savings, visit http://www.lesswatts.org
Quoted 9 lines · Arjan van de Ven
Quoted 6 lines · On Sat, 19 Sep 2009 10:01:51 +0200 Jim Meyering <[email protected]> wrote:
Yeah, I mentioned I should do exactly that on IRC yesterday. I've just run some tests, and see that at least with one SSD (OCZ Summit 120GB), the 0.5s cost of sorting pays off handsomely with a 12-x speed-up, saving 5.5 minutes, when removing a 1-million-empty-file directory.
Quoted 3 lines
likely because you actually reduce the amount of IO; inodes share disk blocks; repeated unlinks in random order likely write the same block multiple times....
That makes sense.
Maybe cache effects, too?
Quoted 2 lines
btw have you given thought about using threads as part of rm -r[f] ? (would make the unlinks of unrelated directories/files asynchronous)
While it is certainly a nicely parallelizable process,
rm usually runs so quickly that I doubt it'd be worthwhile. If you know in advance that parallelizing a particular recursive removal would give a significant benefit, it's probably best to do it via e.g., xargs --max-procs=N.
However, sort *would* benefit, and some UCLA students implemented that for a term project. Unfortunately, the project is stalled because the implementation was not efficient enough, and no one has found the time to improve it since.
Quoted 8 lines · On Sat, 19 Sep 2009 11:07:21 +0200 Jim Meyering <[email protected]> wrote:
Quoted 2 lines
btw have you given thought about using threads as part of rm -r[f] ? (would make the unlinks of unrelated directories/files asynchronous)
While it is certainly a nicely parallelizable process,
rm usually runs so quickly that I doubt it'd be worthwhile. If you know in advance that parallelizing a particular recursive removal would give a significant benefit, it's probably best to do it via e.g., xargs --max-procs=N.
deleting large files has several seeks kind of cost (small files is cheap). At least on ext3. I guess with btrfs being the future it's indeed not worth doing in userspace.
Quoted 4 lines
However, sort *would* benefit, and some UCLA students implemented that for a term project. Unfortunately, the project is stalled because the implementation was not efficient enough, and no one has found the time to improve it since.
parallel sort... call me skeptical. My gut feeling is that you'll get killed by communication overhead.
(sort seems to be more communication than raw cpu use)
Signature · 3 lines
Arjan van de Ven Intel Open Source Technology Centre For development, discussion and tips for power savings, visit http://www.lesswatts.org
Quoted 10 lines · Arjan van de Ven
Quoted 5 lines
However, sort *would* benefit, and some UCLA students implemented that for a term project. Unfortunately, the project is stalled because the implementation was not efficient enough, and no one has found the time to improve it since.
parallel sort... call me skeptical. My gut feeling is that you'll get killed by communication overhead.
(sort seems to be more communication than raw cpu use)
Why? a sort that fits in memory is purely cpu and memory access.
Instead of O(N log N) you'd get K * O(N/K log N/K) followed by an O(N) merge. For large N and small K, you get a speedup of roughly K (since the O(N) merge is dominated by the preceding sort.
Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
Quoted 13 lines · Jim Meyering
About a year ago, I fixed GNU rm to avoid quadratic readdir/stat seek penalties on ext3 and ext4 that became overwhelming on directories with many entries (1M entries started to look like infloop or DoS).
From coreutils-7.0 NEWS:
chgrp, chmod, chown, chcon, du, rm: now all display linear performance, even when operating on million-entry directories on ext3 and ext4 file systems. Before, they would exhibit O(N^2) performance, due to linear per-entry seek time cost when operating on entries in readdir order. Rm was improved directly, while the others inherit the improvement from the newer version of fts in gnulib.
Quoted 5 lines
To do that efficiently, I changed the core readdir loop (mainly via gnulib's
fts.c) to preprocess entries, when needed, by sorting them on inode, and *then* processing them. This optimization is enabled only when the affected file system is of a type likely to benefit, and when the number of directory entries is large enough to matter.
This is excellent. I've been used to play with variations of 'find -printf "%i %p\n"|sort -n|cut -f2|xargs <cmd>' to sort file operations by inode to speed them up, especially when rm'ing a kernel tree or when doing a prefetch to build from hot cache.
I think you might notice excellent results on CDs where seeks cost a lot. That's where I first use the find|sort method above. I'm really happy to see that such mechanisms are now implemented inside my everyday tools, and I can't wait to upgrade!
Regards,
Willy
Quoted 6 lines · On Sat, 19 Sep 2009 14:11:38 +0300 Avi Kivity <[email protected]> wrote:
Quoted 5 lines · Arjan van de Ven
Quoted 5 lines
However, sort *would* benefit, and some UCLA students implemented that for a term project. Unfortunately, the project is stalled because the implementation was not efficient enough, and no one has found the time to improve it since.
Quoted 7 lines
Quoted 5 lines
parallel sort... call me skeptical. My gut feeling is that you'll get killed by communication overhead.
(sort seems to be more communication than raw cpu use)Why? a sort that fits in memory is purely cpu and memory access.
memory access == communication due to cache line bounces....
Quoted 4 lines
Instead of O(N log N) you'd get K * O(N/K log N/K) followed by an O(N) merge. For large N and small K, you get a speedup of roughly K (since the O(N) merge is dominated by the preceding sort.
doing big-O arithmatic and then add constant divisions/multipliers is rather.. dangerous ;)
You actually get K * C1 * O(N/K log N/K) + C2 * O(N)
where C1/C2 is the actual cost of the extra intra-cpu communication. (and for most sorting, I suspect the communication costs dominate over CPU cost)
I'd be happy to be proven wrong...
Signature · 3 lines
Arjan van de Ven Intel Open Source Technology Centre For development, discussion and tips for power savings, visit http://www.lesswatts.org
Quoted 18 lines · Arjan van de Ven
Quoted 14 lines · On Sat, 19 Sep 2009 14:11:38 +0300 Avi Kivity<[email protected]> wrote:
Quoted 12 lines · Arjan van de Ven
Quoted 6 lines
However, sort *would* benefit, and some UCLA students implemented that for a term project. Unfortunately, the project is stalled because the implementation was not efficient enough, and no one has found the time to improve it since.
parallel sort... call me skeptical. My gut feeling is that you'll get killed by communication overhead.
(sort seems to be more communication than raw cpu use)
Quoted 4 lines
Quoted 2 lines
Why? a sort that fits in memory is purely cpu and memory access.
memory access == communication due to cache line bounces....
For a large sort cache line bounces will be negligible. First, memory size greatly exceeds cache size. Second, every cach eline will be accessed multiple times.
If you're sorting 2MB, then yes, threads aren't needed.
Quoted 7 lines
Quoted 4 lines
Instead of O(N log N) you'd get K * O(N/K log N/K) followed by an O(N) merge. For large N and small K, you get a speedup of roughly K (since the O(N) merge is dominated by the preceding sort.
doing big-O arithmatic and then add constant divisions/multipliers is rather.. dangerous ;)
I'm wearing my seat belt.
Quoted 7 lines
You actually get K * C1 * O(N/K log N/K) + C2 * O(N)
where C1/C2 is the actual cost of the extra intra-cpu communication. (and for most sorting, I suspect the communication costs dominate over CPU cost)I'd be happy to be proven wrong...
Again, if the dataset is large, only a small fraction of the cache lines will be on another cpu. The majority will be in main memory.
Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.