11 ms·
Show HN: Dut – a fast Linux disk usage calculator
"dut" is a disk usage calculator that I wrote a couple months ago in C. It is multi-threaded, making it one of the fastest such programs. It beats normal "du" in all cases, and beats all other similar programs when Linux's caches are warm (so, not on the first run). I wrote "dut" as a challenge to beat similar programs that I used a lot, namely pdu[1] and dust[2].
"dut" displays a tree of the biggest things under your current directory, and it also shows the size of hard-links under each directory as well. The hard-link tallying was inspired by ncdu[3], but I don't like how unintuitive the readout is. Anyone have ideas for a better format?
There's installation instructions in the README. dut is a single source file, so you only need to download it and copy-paste the compiler command, and then copy somewhere on your path like /usr/local/bin.
I went through a few different approaches writing it, and you can see most of them in the git history. At the core of the program is a datastructure that holds the directories that still need to be traversed, and binary heaps to hold statted files and directories. I had started off using C++ std::queues with mutexes, but the performance was awful, so I took it as a learning opportunity and wrote all the datastructures from scratch. That was the hardest part of the program to get right.
These are the other techniques I used to improve performance:
* Using fstatat(2) with the parent directory's fd instead of lstat(2) with an absolute path. (10-15% performance increase)
* Using statx(2) instead of fstatat. (perf showed fstatat running statx code in the kernel). (10% performance increase)
* Using getdents(2) to get directory contents instead of opendir/readdir/closedir. (also around 10%)
* Limiting inter-thread communication. I originally had fs-traversal results accumulated in a shared binary heap, but giving each thread a binary-heap and then merging them all at the end was faster.
I couldn't find any information online about fstatat and statx being significantly faster than plain old stat, so maybe this info will help someone in the future.
[1]: https://github.com/KSXGitHub/parallel-disk-usage https://github.com/KSXGitHub/parallel-disk-usage
[2]: https://github.com/bootandy/dust https://github.com/bootandy/dust
[3]: https://dev.yorhel.nl/doc/ncdu2 https://dev.yorhel.nl/doc/ncdu2, see "Shared Links"
- cycomanic 2y agoThis looks awesome! One comment, I find the benchmark results really cumbersome to read. Why don't you make a graph (e.g. a barplot) that would make results obvious at a quick glance. I'm a strong believer in presenting numerical data graphically whenever possible, it avoids many mistakes and misunderstandings.
- oigursh 2y agoncdu has been my go to for years. Pleased to have a modern alternative.
- jbaber 2y agoI always want treemaps. console: rust: cargo install diskonaut python: pip install ohmu GUI: gdmap windows: windirstat mac: grand perspective (I seem to r call)
- pmdfgy 2y agoNice work. I really miss the simplicity of C. One file. One Makefile and that's it. Has anyone tested with a node_modules folder ?
- kccqzy 2y agoI'm away from my Linux machine now but I'm curious whether/how you handle reflinks. On a supported file system such as Btrfs which I use, how does `cp --reflink` gets counted? Similar to hard links? I'm curious because I use this feature extensively.
- 201984 2y agoI've actually never heard of --reflink, so I had to look it up. `cp` from coreutils uses the FICLONE ioctl to clone the file on btrfs instead of a regular syscall. I don't handle them specifically in dut, so it will total up whatever statx(2) reports for any reflink files.
- vlovich123 2y agoYou’ll probably end up with dupes (and removing these files won’t have the effect you intend) but I don’t know that there’s a good way to handle and report such soft links anyway.
- namibj 2y agoBtdu will be you friend.
- hsbauauvhabzb 2y agoThis looks handy. Do you have any tips for stuff like queued ‘mv’ or similar? If I’m moving data around on 3-4 drives, it’s common where I’ll stack commands where the 3rd command may free up space for the 4th to run successfully - I use && a to ensure a halt on failure, but I need to mentally calculate the space free when I’m writing the commands as the free space after the third mv will be different to the output of ‘df’ before any of the commands have run.
- 201984 2y agoI haven't run into a situation like that, but if I did, I'd be doing mental math like you. `dut` would only be useful as a (quicker) replacement for `du` for telling you how large the source of a `cp -r` is.
- timrichard 2y agoLooks nice, although a feature I like in ncdu is the 'd' key to delete the currently highlighted file or directory.
- 201984 2y agoThis isn't an interactive program, so ncdu would be better for interactively going around and freeing up space. If you just want an overview, though, then dut runs much quicker than ncdu and will show large files deep down in subdirectories without having to go down manually.
- notarealllama 2y agoIf this accurately shows hidden stuff, such as docker build cache and old kernels, then it will become my go-to!
- jepler 2y agodid you consider using io_uring? if not, was there a reason other than portability?
- 201984 2y agoio_uring doesn't support the getdents syscall, so there's no way to traverse the filesystem with it. I considered using it for statx(2) to get the disk usage of each file, but decided not to because (a) it would be complicated to mix normal syscalls and io_uring and (b) perf showed the kernel spending most of its time doing actual work and not syscall boilerplate.
- jepler 2y agoI appreciate the explanation!
- nh2 2y agoAre you sure the perf may not be misleading? E.g. memory accesses might show up as slower die to CPU caches being flushed when switching between user and kernel space. I would be extremely interested in a quick (standalone?) benchmark of e.g. 1M stats with vs without uring. Also https://github.com/tdanecker/iouring-getdents https://github.com/tdanecker/iouring-getdents reports big uring speedups for getdents, which makes it surprising to get no speedups for stat. If uring turns out fast, you might ignore (a), just doing the getdents first and then all stats afterwards. Since getdents is a "batch" syscalls covering many files anyway, but stat isn't.
- montroser 2y agoNice work. Some times I wonder if there's any way to trade away accuracy for speed? Like, often I don't care _exactly_ how many bytes is the biggest user of space, but I just want to see some orders of magnitude. Maybe there could be an iterative breadth-first approach, where first you quickly identify and discard the small unimportant items, passing over anything that can't be counted quickly. Then with what's left you identify the smallest of those and discard, and then with what's left the smallest of those, and repeat and repeat. Each pass through, you get a higher resolution picture of which directories and files are using the most space, and you just wait until you have the level of detail you need, but you get to see the tally as it happens across the board. Does this exist?
- 201984 2y agoThanks! What you described is a neat idea, but it's not possible with any degree of accuracy AFAIK. To give you a picture of the problem, calculating the disk usage of a directory requires calling statx(2) on every file in that directory, summing up the reported sizes, and then recursing into every subdirectory and starting over. The problem with doing a partial search is that all the data is at the leaves of the tree, so you'll miss some potentially very large files. Picture if your program only traversed the first, say, three levels of subdirectories to get a rough estimate. If there was a 1TB file down another level, your program would miss it completely and get a very innaccurate estimate of the disk usage, so it wouldn't be useful at all for finding the biggest culprits. You have the same problem if you decide to stop counting after seeing N files, since file N+1 could be gigantic and you'd never know.
- montroser 2y agoYeah, maybe approximation is not really possible. But it still seems like if you could do say, up to 1000 stats per directory per pass, then running totals could be accumulated incrementally and reported along the way. So after just a second or two, you might be able to know with certainty that a bunch of small directories are small, and then that a handful of others are at least however big has been counted so far. And that could be all you need, or else you could wait longer to see how the bigger directories play out.
- chomp 2y agoGPLv3, you love to see it. Great work.
- jeffbee 2y agoIt's also interesting that the perf report for running dut on my homedir shows that it spends virtually all of the time looking for, not finding, and inserting entries in dentry cache slabs, where the entries are never found again, only inserted :-/ Great cache management by the kernel there. ETA: Apparently the value in /proc/sys/vm/vfs_cache_pressure makes a huge difference. With the default of 100, my dentry and inode caches never grow large enough to contain the ~15M entries in my homedir. Dentry slabs get reclaimed to stay < 1% of system RAM, while the xfs_inode slab cache grows to the correct size. The threads in dut are pointless in this case because the access to the xfs inodes serializes. If I set this kernel param to 15, then the caches grow to accommodate the tens of millions of inodes in my homedir. Ultimately the slab caches occupy 20GB of RAM! When the caches are working the threading in dut is moderately effective, job finishes in 5s with 200% CPU time.
- 201984 2y agoAre you referring to the kmem_cache_alloc calls in the profile? If so, that's all in kernel space and there's nothing I can do about it. https://share.firefox.dev/3XT9L7P https://share.firefox.dev/3XT9L7P
- jeffbee 2y agoNo, see how your profiles have `lookup_fast` at the leaves? Mine has `__lookup_slow` and it is slow indeed.
- 201984 2y agoI just saw your edit. You have WAY more stuff under your home directory than I do. I only have ~2.5M inodes on both my laptop drives combined. The difference in the buff/cache output of `free` before and after running `dut` is only 1 GB for me. Also, TIL about that kernel parameter, thanks!
- jeffbee 2y agoYeah I have a TB of bazel outputs in my cache directory. Unfortunately automatically deleting old bazel outputs is beyond the frontier of computer science and has been pushed out to future releases for 6 years and still going: https://github.com/bazelbuild/bazel/issues/5139 https://github.com/bazelbuild/bazel/issues/5139
- tambourine_man 2y ago> https://dev.yorhel.nl/doc/ncdu2 https://dev.yorhel.nl/doc/ncdu2 I wasn't aware that there was a rewrite of ncdu in Zig. That link is a nice read.
- jftuga 2y agoYou should include the "How to build" instructions near the beginning of the main.c file.
- 201984 2y agoDone
- teamspirit 2y agoNice job. I've been using dua[0] and have found it to be quite fast on my MacBook Pro. I'm interested to see how this compares. [0] https://github.com/Byron/dua-cli https://github.com/Byron/dua-cli
- 201984 2y agoI benchmarked against dua while developing, and the results are in the README. Note that dut uses Linux-specific syscalls, so it won't run on MacOS. TL;DR: dut is 3x faster with warm caches, slightly faster on SSD, slightly slower on HDD.
- IAmLiterallyAB 2y agoI'm surprised statx was that much faster than fstatat. fstatat looks like a very thin wrapper around statx, it just calls vfs_statx and copies out the result to user space.
- 201984 2y agoOut of curiosity, I switched it back to fstatat and compared, and found no significant difference. Must've been some other change I made at the time, although I could've sworn this was true. Could be a system update changed something in the three months since I did that. I can't edit my post now though, so that wrong info is stuck there.
- deleted 2y ago[deleted]
- jmakov 2y agoWould be great to have a TUI interface for browsing like ncdu.
- jonhohle 2y agoDid you consider the fts[0] family of functions for traversal? I use that along with a work queue for filtered entries to get pretty good performance with dedup[1]. For my use case I could avoid any separate stat call altogether, the FTSENT already provided everything I needed. 0 - https://linux.die.net/man/3/fts_read https://linux.die.net/man/3/fts_read 1 - https://github.com/ttkb-oss/dedup/blob/6a906db5a940df71deb4fdcdc7fc8bb4fcd0eb29/dedup.c#L621 https://github.com/ttkb-oss/dedup/blob/6a906db5a940df71deb4f...
- nh2 2y agofts is just wrapper functions. You cannot around getdents and stat family syscalls on Linux if you need file sizes.
- 201984 2y agoThose are single threaded, so they would have kneecapped performance pretty badly. 'du' from coreutils uses them, and you can see the drastic speed difference between that and my program in the README.
- dima55 2y agoIdeas for a better format: do what xdiskusage does.
- shellfishgene 2y agoWhat I need is a du that caches the results somewhere and then does not rescan the 90% of dirs that have not changed when I run it again a month later...
- kstrauser 2y agoAnd it would know they did not change without scanning them because how?
- svpg 2y agoIt could hash the contents of a dir. Along the lines of git
- Galanwe 2y agoExcept hashing requires... reading. There is not much to be done here. Directories entries are just names, no guarantees that the files were not modified or replaced. The best you could do is something similar to the strategies of rsync, rely on metadata (modified date, etc) and cross fingers nobody did `cp -a`.
- shellfishgene 2y agoI would be fine with the latter, the program could display a warning like "Results may be inaccurate, full scan required" or something. I guess I'm just annoyed that for Windows/NTFS really fast programs are available but not for Linux filesystems.
- legends2k 2y agoAnd to hash something needs reading all of its data. I think deducing the file size would actually be faster in some file systems and never slower with any.
- mort96 2y agoFaster in all file systems I'd guess, stat is fast, opening the file and reading its contents and updating a checksum is slow, and gets slower the larger the file is.
- anon-3988 2y agoI have been using diskonaut, its fast enough given that it also produces a nice visual output.
- rafaelgoncalves 2y agoneat tool, congrats on the release and thank you for this and the analysis/comparison.
- mg 2y agoI have this in my bashrc: alias duwim='du --apparent-size -c -s -B1048576 * | sort -g' It produces a similar output, showing a list of directories and their sizes under the current dir. The name "duwim" stands for "du what I mean". It came naturally after I dabbled for quite a while to figure out how to make du do what I mean.
- mixmastamyk 2y agoNot as featureful, but what I've been using. If you can't install this tool for some reason, it's still useful. I call it usage: #!/bin/bash du -hs * .??* 2> /dev/null | sort -h | tail -22
- tamimio 2y agoSomeone, please create a Gdut, a fork that will produce graphs for a quick and easy way to read, it’s almost impossible to read in small vertical screens.
- sandreas 2y agoNice work! There is also gdu[1], where the UI is heavily inspired by ncdu and somehow feels way faster... 1: https://github.com/dundee/gdu https://github.com/dundee/gdu
- nh2 2y ago> I don't know why one ordering is better than the other, but the difference is pretty drastic. I have the suspicion that some file systems store stat info next to the getdents entries. Thus cache locality would kick in if you stat a file after receiving it via getdents (and counterintuitively, smaller getdents buffers make it faster then). Also in such cases it would be important to not sort combined getdents outputs before starting (which would destroy the locality again). I found such a situation with CephFS but don't know what the layout is for common local file systems.
- miew 2y agoWhy C and not Rust or even Zig?
- Galanwe 2y agoWhy Rust or Zig and not C?
- nottorp 2y agoBetter for the author's resume, if they want to make it hype driven. Also some nebulous "being more secure". Never mind that this tool does not have elevated privileges. You gotta watch out for those remote root exploits even for a local only app, man.
- _flux 2y agoI mean you could extract an archive you've downloaded to your filesystem and said archive could have funky file names and then you use this tool.. But I suppose it's not a very likely bug to have in this kind of tool.
- nottorp 2y agoOr “they” could enter your house at 2 am, drug you and hit you with a $5 wrench until they get access to your files :)
- gsck 2y agoNever understood this line of thought. Not everything needs to be super secure. Not everything is going to be an attack vector. No one is going to deploy this onto a production server where this program specifically is going to be the attack vector. Memory safety is cool and all, but a program that effectively sums a bunch of numbers together isn't going to cause issues. Worst case the program segfaults
- craftoman 2y agoBecause C is like a cult Toyota Supra with twin turbo and Rust or Zig is like another cool boring Corvette roadster.
- trustno2 2y agoDoes it depend on linux functionality or can I use it on macos? Well I can just try :)
- Ringz 2y agoFrom the author: „Note that dut uses Linux-specific syscalls, so it won't run on MacOS.“
- INTPenis 2y agoReminds me of someone's script I have been using for over a decade. #/bin/sh du -k --max-depth=1 "$@" | sort -nr | awk ' BEGIN { split("KB,MB,GB,TB", Units, ","); } { u = 1; while ($1 >= 1024) { $1 = $1 / 1024; u += 1 } $1 = sprintf("%.1f %s", $1, Units[u]); print $0; } '
- mshook 2y agoI don't understand the point of the script, it's nothing more than: du -h --max-depth=1 "$@" | sort -hr
- out-of-ideas 2y ago`-h` is not available in all `sort` implementations
- BlackLotus89 2y agoEven the busybox port has it. The only sort implementation I know of that doesn't have -h is toybox (I guess older busybox implementations are missing it as well), but I'm using -h for well over a decade and seldom had it missing
- out-of-ideas 2y agoi was actually curious when busybox's sort added it; but didnt search too hard. was certainly easy to see gnu get it in 2009 i think (but even then if the dude setup there bashrc long ago and that func/alias works, likely no reason to change it immediatly) i can say an `BusyBox v1.35.0 (2022-08-01 15:14:44 UTC)` did not have -h; so it having it now is kind of a shock to me (looks like busybox v1.36.1 has it - at least from 2023-06-22) - good too! always frustrating when a dev tries using gnu-args and it blows up and i gotta explain the diff between mac-shell-cmds, gnu, and busybox
- dotancohen 2y ago
- laixintao 2y ago> Anyone have ideas for a better format? Hi, how about flamegraph? I always want to display the file hierarchy in flamegraph like format. - previous discussion: https://x.com/laixintao/status/1744012609983295816 https://x.com/laixintao/status/1744012609983295816 - my work display flamegraph in terminal: https://github.com/laixintao/flameshow https://github.com/laixintao/flameshow
- robocat 2y ago> but I don't like how unintuitive the readout is The best disk usage UI I ever saw was this one: https://www.trishtech.com/2013/10/scanner-display-hard-disk-usage-in-chart-form/ https://www.trishtech.com/2013/10/scanner-display-hard-disk-... The inner circle is the top level directories, and each ring outwards is one level deeper in the directory heirarchy. You would mouse over large subdirectories to see what they were, or double click to drilldown into a subdirectory. Download it and try it - it is quite spectacularly useful on Windows (although I'm not sure how well it handles Terabyte size drives - I haven't used Windows for a long time). Hard to do a circular graph in a terminal... It is very similar to a flame graph? Perhaps look at how flame graphs are drawn by other terminal performance tools.
- pricechild 2y ago"Disk Usage Analyser" / "Baobab" on Linux is awesome with the same UI: https://apps.gnome.org/en-GB/Baobab/ https://apps.gnome.org/en-GB/Baobab/
- rlue 2y agoThat’s called a ring chart or a sunburst chart.
- krackers 2y agoDaisyDisk on mac does that. Also it's blazing fast, it seems to even beat "du" so I don't know what tricks they're pulling.
- supernes 2y ago
- Neil44 2y agoOn Windows I always used to use Windirstat but it was slow, then I found Wiztree which is many orders of magnitude faster. I understand it works by directly reading the NTFS tables rather than spidering through the directories laboriously. I wonder if this approach would work for ext4 or whatever.
- utensil4778 2y ago> it works by directly reading the NTFS tables rather than spidering through the directories Maybe I'm just ignorant of linux filesystems, but this seems like the obvious thing to do. Do ext and friends not have a file table like this?
- Filligree 2y agoNTFS is pointlessly slow, so bypassing the VFS provides a decent speedup in exchange for the ridiculous fragility. Linux doesn’t have the same issue, and I’d be quite concerned if an application like this needed root access to function.
- ablob 2y agoI want to take this opportunity to recommend the talk "NTFS isn't that bad" (https://www.youtube.com/watch?v=qbKGw8MQ0i8 https://www.youtube.com/watch?v=qbKGw8MQ0i8). NTFS prefers a different access pattern than most usual file systems. I remember that a part of the talk was about speed-ups on Linux as well. So even if it doesn't sway your opinion it should enhance your perspective on how file systems work.
- p_l 2y agoThe issue usually isn't NTFS, but the other layers in the I/O stack. NTFS-the-on-disk-structure by itself can easily provide setup comparable to XFS realtime extensions.
- luma 2y agoI think you underestimate how much of a speedup we're talking about: it can pull in the entire filesystem in a couple seconds on a multi TB volume with Bs of files. I have yet to see anything in the linux world (including the OP) that comes anywhere near this performance level via tree walking.
- tiku 2y agoNcdu is easy to remember and use, clicking through etc. would be cool to find a faster replacement, same usage instead of a new tool with parameters to remember..
- bArray 2y agoI think that 'ls' should also be evaluating the size of the files contained within. The size and number of contained files/folders really does reveal a lot about the contents of a directory without peeking inside. The speed of this is what would be most concerning though.
- frumiousirc 2y agodut looks very nice. One small surprise I found came when I have a symlink to a directory and refer to that with a trailing "/". dut doesn't follow the link in order to scan the real directory. Ie I have this symlink: ln -s /big/disk/dev ~/dev then ./dut ~/dev/ returns zero size while du -sh ~/dev/ returns the full size. I'm not sure how widespread this convention is to resolve symlinks to their target directories if named with a trailing "/" but it's one my fingers have memorized. In any case, this is another tool for my toolbox. Thank you for sharing it.
- classified 2y agoI get boatloads of "undefined reference" errors. Where's the list of dependencies?
- imiric 2y agoI've been using my own function with `du` for ages now, similar to others here, but I appreciate new tools in this space. I gave `dut` a try, but I'm confused by its output. For example: 3.2G 0B |- .pyenv 3.4G 0B | /- toolchains 3.4G 0B |- .rustup 4.0G 0B | |- <censored> 4.4G 0B | /- <censored> 9.2G 0B |- Work 3.7G 0B | /- flash 3.8G 0B | /- <censored> 16G 4.0K |- Downloads 5.1G 0B | |- <censored> 5.2G 0B | /- <censored> 16G 0B |- Projects 3.2G 42M | /- <censored> 17G 183M |- src 17G 0B | /- <censored> 17G 0B |- Videos 3.7G 0B | /- Videos 28G 0B |- Music 6.9G 0B | |- tmp 3.4G 0B | | /- tmp 8.8G 0B | |- go 3.6G 0B | | /- .versions 3.9G 0B | | |- go 8.5G 0B | | | /- dir 8.5G 0B | | | /- vfs 8.5G 0B | | | /- storage 8.5G 0B | | /- containers 15G 140M | /- share 34G 183M /- .local 161G 0B . - I expected the output to be sorted by the first column, yet some items are clearly out of order. I don't use hard links much, so I wouldn't expect this to be because of shared data. - The tree rendering is very confusing. Some directories are several levels deep, but in this output they're all jumbled, so it's not clear where they exist on disk. Showing the full path with the `-p` option, and removing indentation with `-i 0` somewhat helps, but I would almost remove tree rendering entirely.
- 201984 2y agoIt is being sorted by the first column, but it also keeps subdirectories with each other. Look at the order of your top-level directories. 3.2G 0B |- .pyenv 3.4G 0B |- .rustup 9.2G 0B |- Work 16G 4.0K |- Downloads 17G 183M |- src 28G 0B |- Music 34G 183M /- .local If you don't want the tree output and only want the top directories, you can use `-d 1` to limit to depth=1.
- imiric 2y agoAh, I see, that makes sense. But still, the second `Videos` directory of 3.7G is a subdirectory of `Music`, so it should appear below it, no? Same for the two `tmp` directories, they're subdirectories of `.local`, so I would expect them to be listed under it. Right now there doesn't seem to be a clear order in either case.
- bitwize 2y agoNeat, a new C program! I get a little frisson of good vibes whenever someone announces a new project in C, as opposed to Rust or Python or Go. Even though C is pretty much a lost cause at this point. It looks like it has some real sophisticated performance optimizations going on too.
- inbetween 2y agoI often want to know who there is a sudden growth disk usage over the last month/week/etc, what suddenly take space. In those cases I find myself wishing that du and friends would cache their last few runs and would offer a diff against them, this easily listing the new disk eating files or directories. Could dut evolve to do something like that?
- namibj 2y agobtdu extra (or expert?) mode with snapshots kinda does that: you can see what's only in the new version and not in a snapshot; and vice-versa. Also it offers attributing size to folders only for extends that aren't shared with a different folder (snapshots are essentially just special folders), to kinda get a diff between the two (stuff only present in the old snapshot is shown there; stuff only present in the new version is shown there).
- beepbooptheory 2y agodu[t] > .disk-usage-"`date +"%d-%m-%Y"`" And then use diff later?
- inbetween 2y agoAlmost all of them will have some difference. What is needed is to parse the previous state, calculate the difference in size, and show only the "significant" difference.
- thesh4d0w 2y agogt5 does this - https://gt5.sourceforge.net/ https://gt5.sourceforge.net/
- inbetween 2y agoThat looks perfect, thanks!
- kseistrup 2y agoNow available from AUR: https://aur.archlinux.org/packages/dut-git https://aur.archlinux.org/packages/dut-git
- tonymet 2y agogreat app. very fast at scanning nested dirs. I often need recursive disk usage when I suddenly run out of space and scramble to clean up while everything is crashing.