11 ms·

You can list a directory containing 8M files, but not with ls

172 points by _wldu 5y ago

Y_Y 5y ago
If you haven't prepared for this eventuality then odds are you're going to run out of inodes first. And it's probably not useful to just dump all those filenames to your terminal. And don't even say you were piping the output of `ls` to something else! Anyway the coreutils shouldn't have arbitrary limits like this, at least if they do then the limits should be so high that you have to be really trying hard in order to reach them.
- cmeacham98 5y ago
  There isn't actually an arbitrary limit, it's just that glibc's readdir() implementation is really really slow with millions of files according to the article. Presumably if you waited awhile `ls` would eventually get the whole list.
  - matheusmoreira 5y ago
    The glibc functions are just bad wrappers for the real system calls which no doubt work much more efficiently. I fully expected to find the system call solution in the article and was not disappointed.
  - p_l 5y ago
    it's not readdir() that is slow - it's the way ls needs to load the whole directory into memory then do a bunch of things on it (sorting, calculating column sizes, etc), and depending on what you have in your defaults or passed options it might also try to stat() every of those files first.
mercurialuser 5y ago
did you try ls -1? in the far past I had the same problem listing millions of files in a dir edit: if I remember correctly ls bufferizes the results for sorting. with -1 it just dumps the values
- acdha 5y ago
  It’s not “ls -1” but “--sort=none” or “-U”.
  - loeg 5y ago
    "ls -f" in POSIX ls (which GNU ls also implements). Also, avoid "-F", which will stat each file.
  - the_arun 5y ago
    `ls | more` works too, right?
    - loeg 5y ago
      At least with GNU ls, 'ls | more' does not disable sorting. It disables automatic color (which is important -- coloring requires 'stat(2)'ing every file in the directory).
    - acdha 5y ago
      No - it still does all of the work to sort the entries, which is the slow part since it prevents the first entry from being displayed until the last has been retrieved.
- innagadadavida 5y ago
  I think it also tries to nearly format into columns and this requires it to know name lengths for all files. If you do -l it basically outputs one file per line and can be done more efficiently.
- antegamisou 5y ago
  find . would be another alternative
unwind 5y ago
Meta, if the author is around: there seems to be some kind of encoding problem, on my system (Linux, Firefox) I see a lot of strange characters where there should probably be punctuation. The first section header reads "Why doesnâ€™t ls work?", for instance.
- FpUser 5y ago
  Same here
- cmeacham98 5y ago
  This is because the page has no doctype, thus putting the browser in "quirks mode", defaulting to a charset of ISO-8859-1 (as the page does not specify one). The author can fix this either by specifying the charset, or adding the HTML5 doctype (HTML5 defaults to UTF-8).
  - dheera 5y ago
    Maybe browsers should default to UTF-8 already. It's 2021.
    - lxgr 5y ago
      Why? Defaulting to UTF-8 for modern HTML, and to ISO-8859-1 for legacy pages, makes a lot of sense. Pages that haven‘t been adapted to HTML 5 in the last 10 years or so are exceedingly unlikely to do so in year 11.
      - dheera 5y ago
        ISO-8859-1 is a subset of UTF-8 isn't it? No harm done by defaulting to the superset.
        CodesInChaos 5y ago
        No. ASCII is a subset of UTF-8, ISO-8859-1 is not. The first 256 codepoints of unicode match ISO-8859-1, which is probably the source of your confusion. However Codepoints 128-255 are encoded differently in UTF-8. They are represented by a single byte when encoded as ISO-8859-1, while they turn into two bytes encoded in UTF-8. Plus "ISO-8859-1" is treated as Windows-1252 by browsers, while unicode uses ISO-8859-1 extended with the ISO 6429 control characters for its initial 256 codepoints.
osswid 5y ago
ls -f
- wolfgang42 5y ago
  -f do not sort, enable -aU, disable -ls --color -a do not ignore entries starting with . -U do not sort; list entries in directory order -l use a long listing format -s print the allocated size of each file, in blocks --color colorize the output I assume you mean to imply that by turning off sorting/filtering/formatting ls will run in a more optimized mode where it can avoid buffering and just dump the dentries as described in the article?
  - jjgreen 5y ago
    Seems that way: https://github.com/wertarbyte/coreutils/blob/master/src/ls.c#L2538 https://github.com/wertarbyte/coreutils/blob/master/src/ls.c...
  - loeg 5y ago
    Yeah, exactly. OP is changing 3 variables and concluding that getdirent buffer size was the significant one, but actually the problem was likely (1) stat calls, for --color, and (2) buffer and sort, which adds O(N log N) sorting time to the total run+print time. (Both of which are avoided by using getdirent directly.)
bifrost 5y ago
Interesting point, this does appear to be Linux and situation specific though. Its interesting enough that I'm going to run my own test now.
- bifrost 5y ago
  Its going to take me a bit to generate several million files but so far I've got a single directory with 550k files in it, it takes 30s to ls it on a very busy system running FreeBSD. 1.1M files -> 120 seconds 1.8M files -> 270 seconds (this could be related to system load being over 90 heh)
  - ipaddr 5y ago
    At 3,000 my windows 7 os freezes. Not bad for a million.
    - ygra 5y ago
      You may want to disable short name generation on windows when putting many files on one directory.
  - loeg 5y ago
    Try "ls -f" (don't sort)? Which filesystem you use will also make a big difference here. You could imagine some filesystem that uses the getdirentries(2) binary format for dirents, and that could literally memcpy cached directory pages for a syscall. In FreeBSD, UFS gets somewhat close, but 'struct direct' differs from the ABI 'struct dirent'. And the FS attempts to validate the disk format, too. FWIW, FreeBSD uses 4kB (x86 system page size) where glibc uses 32kB in this article[1]. To the extent libc is actually the problem (I'm not confident of that yet based on the article), this will be worse than glibc's larger buffer. [1]: https://github.com/freebsd/freebsd-src/blob/main/lib/libc/gen/opendir.c#L319-L347 https://github.com/freebsd/freebsd-src/blob/main/lib/libc/ge...
    - bifrost 5y ago
      with "ls -f" on 1.9M files its 45 seconds, much better than regular ls (and system load of 94) 2.25M and its 60 seconds I'm also spamming about 16-18 thousand new files per second to disk using a very inefficient set of csh scripts...
tyingq 5y ago
perl -E 'opendir(my $d,".");say while readdir $d'
marcodiego 5y ago
Makes me think that findfirst and findnext were not that bad after all.
scottlamb 5y ago
tl;dr: try "ls -1 -f". It's fast. This doesn't pass my smell test: > Putting two and two together I could see that the reason it was taking forever to list the directory was because ls was reading the directory entries file 32K at a time, and the file was 513M. So it would take around 16416 system calls of getdents() to list the directory. That is a lot of calls, especially on a slow virtualized disk. 16,416 system calls is a little inefficient but not that noticeable on human terms. And the author is talking as if each one waits 10 ms for a disk head to move to the correct position. That's not true. The OS and drive both do readahead, and they're both quite effective. I recently tried to improve performance of a long-running sequential read on an otherwise-idle old-fashioned spinning disk by tuning the former ("sudo blockdev --setra 6144 /path/to/device"). I found it made no real difference: "iostat" showed OS-level readahead reduces the number of block operations (as expected) but also that total latency doesn't decrease. It turns out in this scenario the disk's cache is full of the upcoming bytes so those extra operations are super fast anyway. The real reason "ls" takes a while to print stuff is that by default it will buffer everything before printing anything so that it can sort it and (when stdout is a terminal) place it into appropriately-sized columns. It also (depending on the options you are using) will stat every file, which obviously will dwarf the number of getdents calls and access the inodes (which are more scattered across the filesystem). "ls -1 -f" disables both those behaviors. It's reasonably fast without changing the buffer size. moonfire-nvr@nuc:/media/14tb/sample$ time ls -1f | wc -l 1042303 real 0m0.934s user 0m0.403s sys 0m0.563s That's on Linux with ext4.
- loeg 5y ago
  Agree re smell test. Those directory blocks are cached, even in front of a slow virtualized disk, and most of those syscalls are hitting in cache. Author is likely running into (1) stat calls and (2) buffer and sort behavior, exactly as you describe.
  - iso1210 5y ago
    Interesting, tried myself on a test VM ~/test$ time for I in `seq -w 1 1000000`; do touch $I; done real 27m8.663s user 14m15.410s sys 12m24.411s OK ~/test$ time ls -1f | wc -l 1000002 real 0m0.604s user 0m0.180s sys 0m0.422s ~/test$ time ls -f | wc -l 1000002 real 0m0.574s ~/test$ time perl -E 'opendir(my $d,".");say while readdir $d' |wc -l 1000002 real 0m0.597s All seems reasonable. Directory size alone is 23M, somewhat larger than the typical 4096 bytes.
majkinetor 5y ago
Yeah ... However, lets just accept that regular people don't know those tricks and we should keep files in subfolders? I have that logic in any app that has potential to spam a directory. You can still show them as a single folder (somewhere called branch view) if you like but every other tools that uses ls will work like a charm (such as your backup shell script)
- yjftsjthsd-h 5y ago
  Then anything working on it needs to recurse.
  - SilverRed 5y ago
    Only if you have multiple layers of depth. You can easily have a single layer and then its a flat loop to list everything and broken up in to multiple much faster operations. I haven't looked in to the details but one system I can imagine is hashing the file names and then placing the file in the folder named with the first x parts of the hash. Then to look up you can use the filename to work out exactly which folder the file is in and you never exceed a set limit for files in one folder. If we say 3000 files is perfectly safe in a single folder, 3000 folders with 3000 files holds 9M files.
sigmonsays 5y ago
seems the author didn't read the man page. ls -1f as others have pointed out is a much better than the solution. Additionally, having 8 million anything in a single directory screams bad planning. It's common for some hashing if directory structure to be planned.
- obloid 5y ago
  I'm sure I am just showing my ignorance, but in the man page it says: "-1 list one file per line." and "-f do not sort, enable -aU, disable -ls --color" It's not obvious to me that this would bypass the buffer and fix the problem of being able to list a large number of files. Just that I would get the files unsorted, one line at a time.
  - p_l 5y ago
    Because the buffer is not the problem. ls is slow because it will first load everything to ram, then do a bunch of operations (and it's not really optimized on those, it seems, at least not for speed) and if you have certain options enabled it will also need to stat() each file first. Been there, done that, learnt not to run ls without -1f in a directory that would result in half-hour run.
    - obloid 5y ago
      In the linked article it seems his conclusion was the issue was the small buffer size ls uses. But it's not the buffer itself so much as the things done to the data in the buffer that slow things down?
      - p_l 5y ago
        The transfer buffer is not a problem (if you get slowdown in actually reading the directory, the reason is probably the amount of data is huge and you have slow i/o). The problem is when ls then tries to do all kinds of things after reading that data in order to sort, columnize, colorize, etc. For example, just figuring out if you should add / after filename to indicate directory can, in worst case, require stat() call on every returned file - because there's no guarantee that file type will be filled in response from readdir()/getdents(). Sorting and displaying in columns is particularly slow. All sorts of things that are nice to have, cheap quality of life benefits, breakdown and become huge slowdowns with such insane directories.
fintler 5y ago
https://github.com/hpc/mpifileutils https://github.com/hpc/mpifileutils handles this pretty well -- with SYS_getdents64. It has a few other tricks in there in addition to this one.
avaika 5y ago
If you are going to have a directory with millions of files, probably there's one more interesting thing to consider. As you might know ext* and some other FSs store filenames right in the directory file. Means the more files you have in the directory, the bigger directory size gets. In majority of cases nothing unusual happens, cause people have maybe a few dozens of dirs / files. However if you'll put millions of files, then directory size grows up to a few megabytes in size. If you decide to clean up later, you'd probably expect the directory size to shrink. But it never happens. Unless you run fsck or re-create a directory. That's because nobody believes the implementation effort really worth it. Here's a link to lkml discussion: https://lkml.org/lkml/2009/5/15/146 https://lkml.org/lkml/2009/5/15/146 PS. Here's a previous discussion of the very same article posted in this submission. It's been 10 years already :) https://news.ycombinator.com/item?id=2888820 https://news.ycombinator.com/item?id=2888820 upd. Here's a code example: $ mkdir niceDir && cd niceDir # this might take a few moments $ for ((i=1;i<133700;i++)); do touch long_long_looong_man_sakeru_$i ; done $ ls -lhd . drwxr-xr-x 2 user user 8.1M Aug 2 13:37 . $ find . -type f -delete $ ls -l total 0 $ ls -lhd . drwxr-xr-x 2 user user 8.1M Aug 2 13:37 .
- exdsq 5y ago
  Can you mv niceDir/* newNiceDir/ && rm -fr niceDir to reset the directory size?
  - jhgb 5y ago
    I'd probably 1) hardlink all the files from the old directory into a temporary new directory, and 2) rename the new directory to the old directory's name. I'm no Unix guru but I believe that this should be completely unintrusive to even running processes, or at least less intrusive than your approach. Also failing in the middle seems more graceful.
    - codetrotter 5y ago
      > completely unintrusive to even running processes Unless between the time that you create the hardlinks and the time that you delete the old directory, a process creates new files in the old directory. Unlikely of course, but not impossible.
kalmi10 5y ago
I once had a directory on OpenZFS with more than a billion files, and after cleaning it up with only handful of folders remaining, running ls in it still took a few seconds. I guess some large but almost empty tree structure remained. https://0kalmi.blogspot.com/2020/02/quick-moving-of-billion-files-from.html https://0kalmi.blogspot.com/2020/02/quick-moving-of-billion-...
neilv 5y ago
This is good to know. The other week, I ended up breaking a flat directory with approaching that number of files in it, into a hierarchy of subdirectories. Fortunately, the filenames were timestamp-based (down to the nanosecond), so could be be solved in one line of `sed`, and the hierarchy made tons of sense. Normally, especially knowing older filesystem limits, I would've done such a filesystem hierarchy from the start (even if something wasn't as inherently hierarchical as timestamp strings, like if it used hash strings). But this wealth of files (originally a secondary QA/debugging check, now a potentially valuable training data set) was due to unexpected success of an MVP launch, and it held up perfectly in production. I only cleaned it up when saving that data offline the other week, so it would be convenient&correct to use with tools that might not scale as well as that Linux filesystem and GNU tools did.
chmaynard 5y ago
Found the author's project history here: http://be-n.com/portfolio/ http://be-n.com/portfolio/
jiggawatts 5y ago
This is a practical issue that can cause real problems. I was looking after an AWS-hosted web application where an unimportant plugin was stuck in a crash-restart loop for weeks. It had created something like tens of millions of tiny log files in the same directory over that period. It turns out that cleaning this up is decidedly non-trivial. Worse still, this was "managed" cloud storage with strict IOPS limits. The "one op per file delete" model seems logical until you're staring down the barrel of multi-week completion times. I tried various things, but in the end the only practical solution was to copy the valid data across to a new volume and drop the old one. There was almost no reasonable way to delete that many files. As in this article, even the most basic command line tools like "ls" were useless! You know you're in a bad spot when you're using "kill" on "ls" multiple times per hour...
- southerntofu 5y ago
  > Worse still, this was "managed" cloud storage with strict IOPS limits. It almost sounds like the cloud was someone else's computer all along, and we don't have any control over it. Thanks for sharing this anecdote!
gwbas1c 5y ago
I know the article is for Linux... I recently was involved with a Windows filesystem driver. Windows lowest-level usermode APIs support iterating through directory contents for infinitely sized directories. (You just need to make sure whatever wrapper your language provides doesn't wrap the result in a pre-allocated array.) For example, in C#, the System.IO.Directory static methods that return IEnumerables will let you iterate over millions of files without issue, at least on Windows. They probably will do the same on Linux and Mac.
- thewakalix 5y ago
  Isn’t that comparing apples with oranges? Low-level APIs on both OSes can deal with very large directories — the question is whether the high-level APIs can. (For that matter, streaming isn’t a panacea if your goal is, as the article states, to determine the number of files in the directory.)
  - gwbas1c 5y ago
    Yes, the high-level APIs can. As I mentioned, "For example, in C#, the System.IO.Directory static methods that return IEnumerables will let you iterate over millions of files without issue, at least on Windows." In C#, at that point counting the number of files in a giant directory is trivial. (I was wrong about the method being static) Basically, "new DirectoryInfo(path).EnumerateFiles().Count()" is all you need. You're going to hit the most efficient APIs on Windows, so all you're limited by is hardware speed. (It's also worth checking on Linux.)
tptacek 5y ago
This happened to me a couple months ago; I screwed up a logrotate entry on some of our servers (thankfully, mostly in the dev dc) and ended up with log.txt.0, log.txt.0.0, log.txt.0.0.0.0, &c &c. If your CWD was the directory with those files, anything you did that called readdir just hung. I ended up having to write a tiny program that looped getdents, and was surprised at how poorly documented/integrated it was with the rest of the API.
SavantIdiot 5y ago
Just ran into this. I had the video app motion running for a few weeks and had accumuluated several million small jpegs and wasn't paying attention to the updater which had stopped pushing images. Basically my webserver was timing out because of how I was searching for new files because there were too many files and I was using a bash script in a cron job that used ls. I found a workaround but it is cool to see this discussion. Kinda reminds me of MS Excel when it first started defaulting to 1048576 rows. You could ctrl-downArrow to the bottom row, but if you ever tried to fill 1M rows it would hang.
ajuc 5y ago
I remember crazy bug that happened in our system because of lots of files in one directory. We had a special directory for temporary files produced when generating labels for barcode printer, and as they were very small (and always caused problems) - we never removed them so we can check out later if something went wrong. After a few years customer complained some barcodes doesn't print. The error message was "cannot create a file XYZ" or something similar. I logged in, checked the disk usage (plenty of space), checked the privileges (correct), did a "touch random_file_name" in that directory - worked fine, copied a few files into this directory - still works fine. Then I did "touch XYZ" and it failed :) But the file XYZ didn't already existed in that directory. I don't remember the exact case (I think it was problem with index growing too big and depending on filename it was assigned to different levels or sth similar). Or maybe it was a hash collision in the filesystem? I don't even remember what filesystem it was - probably reiserfs or ext3. The solution was to remove files after printing them, obviously.
bruce343434 5y ago
Page has mojibake
deadbolt 5y ago
I ran into this issue a couple years back, and while googling found this stackoverflow answer which I thought was pretty neat. https://unix.stackexchange.com/questions/120077/the-ls-command-is-not-working-for-a-directory-with-a-huge-number-of-files/120078#120078 https://unix.stackexchange.com/questions/120077/the-ls-comma...
deleted 5y ago
[deleted]
pvaldes 5y ago
xargs?

172 points by _wldu 5y ago

Y_Y 5y ago

If you haven't prepared for this eventuality then odds are you're going to run out of inodes first. And it's probably not useful to just dump all those filenames to your terminal. And don't even say you were piping the output of `ls` to something else! Anyway the coreutils shouldn't have arbitrary limits like this, at least if they do then the limits should be so high that you have to be really trying hard in order to reach them.

cmeacham98 5y ago
There isn't actually an arbitrary limit, it's just that glibc's readdir() implementation is really really slow with millions of files according to the article. Presumably if you waited awhile `ls` would eventually get the whole list.
- matheusmoreira 5y ago
  The glibc functions are just bad wrappers for the real system calls which no doubt work much more efficiently. I fully expected to find the system call solution in the article and was not disappointed.
- p_l 5y ago
  it's not readdir() that is slow - it's the way ls needs to load the whole directory into memory then do a bunch of things on it (sorting, calculating column sizes, etc), and depending on what you have in your defaults or passed options it might also try to stat() every of those files first.

mercurialuser 5y ago

did you try ls -1? in the far past I had the same problem listing millions of files in a dir edit: if I remember correctly ls bufferizes the results for sorting. with -1 it just dumps the values

acdha 5y ago
It’s not “ls -1” but “--sort=none” or “-U”.
- loeg 5y ago
  "ls -f" in POSIX ls (which GNU ls also implements). Also, avoid "-F", which will stat each file.
- the_arun 5y ago
  `ls | more` works too, right?
  - loeg 5y ago
    At least with GNU ls, 'ls | more' does not disable sorting. It disables automatic color (which is important -- coloring requires 'stat(2)'ing every file in the directory).
  - acdha 5y ago
    No - it still does all of the work to sort the entries, which is the slow part since it prevents the first entry from being displayed until the last has been retrieved.
innagadadavida 5y ago
I think it also tries to nearly format into columns and this requires it to know name lengths for all files. If you do -l it basically outputs one file per line and can be done more efficiently.
antegamisou 5y ago
find . would be another alternative

unwind 5y ago

Meta, if the author is around: there seems to be some kind of encoding problem, on my system (Linux, Firefox) I see a lot of strange characters where there should probably be punctuation. The first section header reads "Why doesnâ€™t ls work?", for instance.

FpUser 5y ago
Same here
cmeacham98 5y ago
This is because the page has no doctype, thus putting the browser in "quirks mode", defaulting to a charset of ISO-8859-1 (as the page does not specify one). The author can fix this either by specifying the charset, or adding the HTML5 doctype (HTML5 defaults to UTF-8).
- dheera 5y ago
  Maybe browsers should default to UTF-8 already. It's 2021.
  - lxgr 5y ago
    Why? Defaulting to UTF-8 for modern HTML, and to ISO-8859-1 for legacy pages, makes a lot of sense. Pages that haven‘t been adapted to HTML 5 in the last 10 years or so are exceedingly unlikely to do so in year 11.
    - dheera 5y ago
      ISO-8859-1 is a subset of UTF-8 isn't it? No harm done by defaulting to the superset.
      - CodesInChaos 5y ago
        No. ASCII is a subset of UTF-8, ISO-8859-1 is not. The first 256 codepoints of unicode match ISO-8859-1, which is probably the source of your confusion. However Codepoints 128-255 are encoded differently in UTF-8. They are represented by a single byte when encoded as ISO-8859-1, while they turn into two bytes encoded in UTF-8. Plus "ISO-8859-1" is treated as Windows-1252 by browsers, while unicode uses ISO-8859-1 extended with the ISO 6429 control characters for its initial 256 codepoints.

osswid 5y ago

ls -f

wolfgang42 5y ago
-f do not sort, enable -aU, disable -ls --color -a do not ignore entries starting with . -U do not sort; list entries in directory order -l use a long listing format -s print the allocated size of each file, in blocks --color colorize the output I assume you mean to imply that by turning off sorting/filtering/formatting ls will run in a more optimized mode where it can avoid buffering and just dump the dentries as described in the article?
- jjgreen 5y ago
  Seems that way: https://github.com/wertarbyte/coreutils/blob/master/src/ls.c#L2538 https://github.com/wertarbyte/coreutils/blob/master/src/ls.c...
- loeg 5y ago
  Yeah, exactly. OP is changing 3 variables and concluding that getdirent buffer size was the significant one, but actually the problem was likely (1) stat calls, for --color, and (2) buffer and sort, which adds O(N log N) sorting time to the total run+print time. (Both of which are avoided by using getdirent directly.)

bifrost 5y ago

Interesting point, this does appear to be Linux and situation specific though. Its interesting enough that I'm going to run my own test now.

bifrost 5y ago
Its going to take me a bit to generate several million files but so far I've got a single directory with 550k files in it, it takes 30s to ls it on a very busy system running FreeBSD. 1.1M files -> 120 seconds 1.8M files -> 270 seconds (this could be related to system load being over 90 heh)
- ipaddr 5y ago
  At 3,000 my windows 7 os freezes. Not bad for a million.
  - ygra 5y ago
    You may want to disable short name generation on windows when putting many files on one directory.
- loeg 5y ago
  Try "ls -f" (don't sort)? Which filesystem you use will also make a big difference here. You could imagine some filesystem that uses the getdirentries(2) binary format for dirents, and that could literally memcpy cached directory pages for a syscall. In FreeBSD, UFS gets somewhat close, but 'struct direct' differs from the ABI 'struct dirent'. And the FS attempts to validate the disk format, too. FWIW, FreeBSD uses 4kB (x86 system page size) where glibc uses 32kB in this article[1]. To the extent libc is actually the problem (I'm not confident of that yet based on the article), this will be worse than glibc's larger buffer. [1]: https://github.com/freebsd/freebsd-src/blob/main/lib/libc/gen/opendir.c#L319-L347 https://github.com/freebsd/freebsd-src/blob/main/lib/libc/ge...
  - bifrost 5y ago
    with "ls -f" on 1.9M files its 45 seconds, much better than regular ls (and system load of 94) 2.25M and its 60 seconds I'm also spamming about 16-18 thousand new files per second to disk using a very inefficient set of csh scripts...

tyingq 5y ago

perl -E 'opendir(my $d,".");say while readdir $d'

marcodiego 5y ago

Makes me think that findfirst and findnext were not that bad after all.

scottlamb 5y ago

tl;dr: try "ls -1 -f". It's fast. This doesn't pass my smell test: > Putting two and two together I could see that the reason it was taking forever to list the directory was because ls was reading the directory entries file 32K at a time, and the file was 513M. So it would take around 16416 system calls of getdents() to list the directory. That is a lot of calls, especially on a slow virtualized disk. 16,416 system calls is a little inefficient but not that noticeable on human terms. And the author is talking as if each one waits 10 ms for a disk head to move to the correct position. That's not true. The OS and drive both do readahead, and they're both quite effective. I recently tried to improve performance of a long-running sequential read on an otherwise-idle old-fashioned spinning disk by tuning the former ("sudo blockdev --setra 6144 /path/to/device"). I found it made no real difference: "iostat" showed OS-level readahead reduces the number of block operations (as expected) but also that total latency doesn't decrease. It turns out in this scenario the disk's cache is full of the upcoming bytes so those extra operations are super fast anyway. The real reason "ls" takes a while to print stuff is that by default it will buffer everything before printing anything so that it can sort it and (when stdout is a terminal) place it into appropriately-sized columns. It also (depending on the options you are using) will stat every file, which obviously will dwarf the number of getdents calls and access the inodes (which are more scattered across the filesystem). "ls -1 -f" disables both those behaviors. It's reasonably fast without changing the buffer size. moonfire-nvr@nuc:/media/14tb/sample$ time ls -1f | wc -l 1042303 real 0m0.934s user 0m0.403s sys 0m0.563s That's on Linux with ext4.

loeg 5y ago
Agree re smell test. Those directory blocks are cached, even in front of a slow virtualized disk, and most of those syscalls are hitting in cache. Author is likely running into (1) stat calls and (2) buffer and sort behavior, exactly as you describe.
- iso1210 5y ago
  Interesting, tried myself on a test VM ~/test$ time for I in `seq -w 1 1000000`; do touch $I; done real 27m8.663s user 14m15.410s sys 12m24.411s OK ~/test$ time ls -1f | wc -l 1000002 real 0m0.604s user 0m0.180s sys 0m0.422s ~/test$ time ls -f | wc -l 1000002 real 0m0.574s ~/test$ time perl -E 'opendir(my $d,".");say while readdir $d' |wc -l 1000002 real 0m0.597s All seems reasonable. Directory size alone is 23M, somewhat larger than the typical 4096 bytes.

majkinetor 5y ago

Yeah ... However, lets just accept that regular people don't know those tricks and we should keep files in subfolders? I have that logic in any app that has potential to spam a directory. You can still show them as a single folder (somewhere called branch view) if you like but every other tools that uses ls will work like a charm (such as your backup shell script)

yjftsjthsd-h 5y ago
Then anything working on it needs to recurse.
- SilverRed 5y ago
  Only if you have multiple layers of depth. You can easily have a single layer and then its a flat loop to list everything and broken up in to multiple much faster operations. I haven't looked in to the details but one system I can imagine is hashing the file names and then placing the file in the folder named with the first x parts of the hash. Then to look up you can use the filename to work out exactly which folder the file is in and you never exceed a set limit for files in one folder. If we say 3000 files is perfectly safe in a single folder, 3000 folders with 3000 files holds 9M files.

sigmonsays 5y ago

seems the author didn't read the man page. ls -1f as others have pointed out is a much better than the solution. Additionally, having 8 million anything in a single directory screams bad planning. It's common for some hashing if directory structure to be planned.

obloid 5y ago
I'm sure I am just showing my ignorance, but in the man page it says: "-1 list one file per line." and "-f do not sort, enable -aU, disable -ls --color" It's not obvious to me that this would bypass the buffer and fix the problem of being able to list a large number of files. Just that I would get the files unsorted, one line at a time.
- p_l 5y ago
  Because the buffer is not the problem. ls is slow because it will first load everything to ram, then do a bunch of operations (and it's not really optimized on those, it seems, at least not for speed) and if you have certain options enabled it will also need to stat() each file first. Been there, done that, learnt not to run ls without -1f in a directory that would result in half-hour run.
  - obloid 5y ago
    In the linked article it seems his conclusion was the issue was the small buffer size ls uses. But it's not the buffer itself so much as the things done to the data in the buffer that slow things down?
    - p_l 5y ago
      The transfer buffer is not a problem (if you get slowdown in actually reading the directory, the reason is probably the amount of data is huge and you have slow i/o). The problem is when ls then tries to do all kinds of things after reading that data in order to sort, columnize, colorize, etc. For example, just figuring out if you should add / after filename to indicate directory can, in worst case, require stat() call on every returned file - because there's no guarantee that file type will be filled in response from readdir()/getdents(). Sorting and displaying in columns is particularly slow. All sorts of things that are nice to have, cheap quality of life benefits, breakdown and become huge slowdowns with such insane directories.

fintler 5y ago

https://github.com/hpc/mpifileutils https://github.com/hpc/mpifileutils handles this pretty well -- with SYS_getdents64. It has a few other tricks in there in addition to this one.

avaika 5y ago

If you are going to have a directory with millions of files, probably there's one more interesting thing to consider. As you might know ext* and some other FSs store filenames right in the directory file. Means the more files you have in the directory, the bigger directory size gets. In majority of cases nothing unusual happens, cause people have maybe a few dozens of dirs / files. However if you'll put millions of files, then directory size grows up to a few megabytes in size. If you decide to clean up later, you'd probably expect the directory size to shrink. But it never happens. Unless you run fsck or re-create a directory. That's because nobody believes the implementation effort really worth it. Here's a link to lkml discussion: https://lkml.org/lkml/2009/5/15/146 https://lkml.org/lkml/2009/5/15/146 PS. Here's a previous discussion of the very same article posted in this submission. It's been 10 years already :) https://news.ycombinator.com/item?id=2888820 https://news.ycombinator.com/item?id=2888820 upd. Here's a code example: $ mkdir niceDir && cd niceDir # this might take a few moments $ for ((i=1;i<133700;i++)); do touch long_long_looong_man_sakeru_$i ; done $ ls -lhd . drwxr-xr-x 2 user user 8.1M Aug 2 13:37 . $ find . -type f -delete $ ls -l total 0 $ ls -lhd . drwxr-xr-x 2 user user 8.1M Aug 2 13:37 .

exdsq 5y ago
Can you mv niceDir/* newNiceDir/ && rm -fr niceDir to reset the directory size?
- jhgb 5y ago
  I'd probably 1) hardlink all the files from the old directory into a temporary new directory, and 2) rename the new directory to the old directory's name. I'm no Unix guru but I believe that this should be completely unintrusive to even running processes, or at least less intrusive than your approach. Also failing in the middle seems more graceful.
  - codetrotter 5y ago
    > completely unintrusive to even running processes Unless between the time that you create the hardlinks and the time that you delete the old directory, a process creates new files in the old directory. Unlikely of course, but not impossible.

kalmi10 5y ago

I once had a directory on OpenZFS with more than a billion files, and after cleaning it up with only handful of folders remaining, running ls in it still took a few seconds. I guess some large but almost empty tree structure remained. https://0kalmi.blogspot.com/2020/02/quick-moving-of-billion-files-from.html https://0kalmi.blogspot.com/2020/02/quick-moving-of-billion-...

neilv 5y ago

This is good to know. The other week, I ended up breaking a flat directory with approaching that number of files in it, into a hierarchy of subdirectories. Fortunately, the filenames were timestamp-based (down to the nanosecond), so could be be solved in one line of `sed`, and the hierarchy made tons of sense. Normally, especially knowing older filesystem limits, I would've done such a filesystem hierarchy from the start (even if something wasn't as inherently hierarchical as timestamp strings, like if it used hash strings). But this wealth of files (originally a secondary QA/debugging check, now a potentially valuable training data set) was due to unexpected success of an MVP launch, and it held up perfectly in production. I only cleaned it up when saving that data offline the other week, so it would be convenient&correct to use with tools that might not scale as well as that Linux filesystem and GNU tools did.

chmaynard 5y ago

Found the author's project history here: http://be-n.com/portfolio/ http://be-n.com/portfolio/

jiggawatts 5y ago

This is a practical issue that can cause real problems. I was looking after an AWS-hosted web application where an unimportant plugin was stuck in a crash-restart loop for weeks. It had created something like tens of millions of tiny log files in the same directory over that period. It turns out that cleaning this up is decidedly non-trivial. Worse still, this was "managed" cloud storage with strict IOPS limits. The "one op per file delete" model seems logical until you're staring down the barrel of multi-week completion times. I tried various things, but in the end the only practical solution was to copy the valid data across to a new volume and drop the old one. There was almost no reasonable way to delete that many files. As in this article, even the most basic command line tools like "ls" were useless! You know you're in a bad spot when you're using "kill" on "ls" multiple times per hour...

southerntofu 5y ago
> Worse still, this was "managed" cloud storage with strict IOPS limits. It almost sounds like the cloud was someone else's computer all along, and we don't have any control over it. Thanks for sharing this anecdote!

gwbas1c 5y ago

I know the article is for Linux... I recently was involved with a Windows filesystem driver. Windows lowest-level usermode APIs support iterating through directory contents for infinitely sized directories. (You just need to make sure whatever wrapper your language provides doesn't wrap the result in a pre-allocated array.) For example, in C#, the System.IO.Directory static methods that return IEnumerables will let you iterate over millions of files without issue, at least on Windows. They probably will do the same on Linux and Mac.

thewakalix 5y ago
Isn’t that comparing apples with oranges? Low-level APIs on both OSes can deal with very large directories — the question is whether the high-level APIs can. (For that matter, streaming isn’t a panacea if your goal is, as the article states, to determine the number of files in the directory.)
- gwbas1c 5y ago
  Yes, the high-level APIs can. As I mentioned, "For example, in C#, the System.IO.Directory static methods that return IEnumerables will let you iterate over millions of files without issue, at least on Windows." In C#, at that point counting the number of files in a giant directory is trivial. (I was wrong about the method being static) Basically, "new DirectoryInfo(path).EnumerateFiles().Count()" is all you need. You're going to hit the most efficient APIs on Windows, so all you're limited by is hardware speed. (It's also worth checking on Linux.)

tptacek 5y ago

This happened to me a couple months ago; I screwed up a logrotate entry on some of our servers (thankfully, mostly in the dev dc) and ended up with log.txt.0, log.txt.0.0, log.txt.0.0.0.0, &c &c. If your CWD was the directory with those files, anything you did that called readdir just hung. I ended up having to write a tiny program that looped getdents, and was surprised at how poorly documented/integrated it was with the rest of the API.

SavantIdiot 5y ago

Just ran into this. I had the video app motion running for a few weeks and had accumuluated several million small jpegs and wasn't paying attention to the updater which had stopped pushing images. Basically my webserver was timing out because of how I was searching for new files because there were too many files and I was using a bash script in a cron job that used ls. I found a workaround but it is cool to see this discussion. Kinda reminds me of MS Excel when it first started defaulting to 1048576 rows. You could ctrl-downArrow to the bottom row, but if you ever tried to fill 1M rows it would hang.

ajuc 5y ago

I remember crazy bug that happened in our system because of lots of files in one directory. We had a special directory for temporary files produced when generating labels for barcode printer, and as they were very small (and always caused problems) - we never removed them so we can check out later if something went wrong. After a few years customer complained some barcodes doesn't print. The error message was "cannot create a file XYZ" or something similar. I logged in, checked the disk usage (plenty of space), checked the privileges (correct), did a "touch random_file_name" in that directory - worked fine, copied a few files into this directory - still works fine. Then I did "touch XYZ" and it failed :) But the file XYZ didn't already existed in that directory. I don't remember the exact case (I think it was problem with index growing too big and depending on filename it was assigned to different levels or sth similar). Or maybe it was a hash collision in the filesystem? I don't even remember what filesystem it was - probably reiserfs or ext3. The solution was to remove files after printing them, obviously.

bruce343434 5y ago

Page has mojibake

deadbolt 5y ago

I ran into this issue a couple years back, and while googling found this stackoverflow answer which I thought was pretty neat. https://unix.stackexchange.com/questions/120077/the-ls-command-is-not-working-for-a-directory-with-a-huge-number-of-files/120078#120078 https://unix.stackexchange.com/questions/120077/the-ls-comma...

deleted 5y ago

[deleted]

pvaldes 5y ago

xargs?