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

You can list a directory containing 8 million files But not with ls..

olark.com

Post reply on HN
Print view View original

31–40 of 93 posts

Re: You can list a directory containing 8 million files But not with ls..

#31

Post by tzs »

I suspect the author is incorrect in his claim that reading in 32k chunks is responsible for the slowness. Due to read ahead and buffering, Unix-like systems tend to do reasonably well on small reads. Yes, big reads are better, but small reads are not unreasonably slow.

To test this, he should try "ls | cat". On large directories that often runs many orders of magnitude faster than "ls". This is because, I believe, ls by default on most people's systems, want to display information such as file modes or type via coloring or otherwise decorating the file names, and getting that information requires looking at the inode for each file.

It's all those inode lookups that slow things down, as the inodes are likely to be scattered all over the place. When you do "ls | cat", ls noticed output is not a terminal, and so turns off the fancy stuff, and just lists the file names. The names can be determined entirely from the directory, and so performance is much better.

Re: You can list a directory containing 8 million files But not with ls..

#32

Post by sixtofour »

blhack wrote: post #25
carbonica wrote: post #18

>>> "Don’t be afraid to compile code and modify it" I was a bit thrown by this advice. Are there folks out there that are afraid to compile code and modify it?

Absolutely. The sad reality is that, to a lot of linux users right now (and I'm talking about people that know they're running linux, not android users), it's a black box. Software is "packages" that you install with "synaptic". Source code? Compiler? What's that?

That's not sad reality, that's success.

Re: You can list a directory containing 8 million files But not with ls..

#33

Post by bcx »

tzs wrote: post #31

I suspect the author is incorrect in his claim that reading in 32k chunks is responsible for the slowness. Due to read ahead and buffering, Unix-like systems tend to do reasonably well on small reads. Yes, big reads are better, but small reads are not unreasonably slow. To test this, he should try "ls | cat". On large directories that often runs many orders of magnitude faster than "ls". This is because, I believe, l…

The original onus for the post was python's os.listdir() which as far as I know doesn't stat(). ls, just made the blog post more interesting :-).

I was surprised that the 32K reads were taking so long. It's possible since it was on a virtualized disk ("in the cloud") that something else was slowing down disk IO (like Xen).

But I can assure you that a larger read buffer performed much better in this given scenario.

I'd welcome more tests though.

Re: You can list a directory containing 8 million files But not with ls..

#34

Post by tedunangst »

tzs wrote: post #31

I suspect the author is incorrect in his claim that reading in 32k chunks is responsible for the slowness. Due to read ahead and buffering, Unix-like systems tend to do reasonably well on small reads. Yes, big reads are better, but small reads are not unreasonably slow. To test this, he should try "ls | cat". On large directories that often runs many orders of magnitude faster than "ls". This is because, I believe, l…

You are right that 32k buffers should be more than enough to read 5MB in a reasonable time, regardless of disk/VM architecture, but I don't think stat was the problem either. My guess would be readdir or possibly getdents is probably O(n^2) somewhere.

[just noticed it was 500M (oh wow), but same difference]

Re: You can list a directory containing 8 million files But not with ls..

#35

Post by Ralith »

tzs wrote: post #31

I suspect the author is incorrect in his claim that reading in 32k chunks is responsible for the slowness. Due to read ahead and buffering, Unix-like systems tend to do reasonably well on small reads. Yes, big reads are better, but small reads are not unreasonably slow. To test this, he should try "ls | cat". On large directories that often runs many orders of magnitude faster than "ls". This is because, I believe, l…

At first glance what you say makes sense, but then why did find and the python call both have similar issues?

Re: You can list a directory containing 8 million files But not with ls..

#36

Post by Ralith »

sixtofour wrote: post #32
blhack wrote: post #25

Earlier quoted context omitted.

Absolutely. The sad reality is that, to a lot of linux users right now (and I'm talking about people that know they're running linux, not android users), it's a black box. Software is "packages" that you install with "synaptic". Source code? Compiler? What's that?

That's not sad reality, that's success.

Both valid perspectives; it depends on your priorities. Some people want computers to be a black box, because when the black box works, it means less cognitive load to use.

Re: You can list a directory containing 8 million files But not with ls..

#37

Post by Ralith »

moe wrote: post #15
rarrrrrr wrote: post #10

The easy way to do this is: find . -maxdepth 1 -mindepth 1 Those arguments will remove the need for find to stat each directory entry. Regardless, this is a nice walk through of low level details often overlooked.

Actually 'find' will also stat each entry no matter what. Many of the standard-tools that most people would intuitively expect to be rather optimized (find, rsync, gzip) are embarrassingly inefficient under the hood and turn belly up when confronted with data of any significant size. That probably stems from the fact that most of the development on these tools took place during a time when 1GB harddrives were "huge"…

But times have changed, and development isn't dead. Why haven't they been updated? The optimizations you imply are often straightforward and well-understood; not major undertakings to implement.

Re: You can list a directory containing 8 million files But not with ls..

#39

Post by sixtofour »

Ralith wrote: post #36
sixtofour wrote: post #32

Earlier quoted context omitted.

That's not sad reality, that's success.

Both valid perspectives; it depends on your priorities. Some people want computers to be a black box, because when the black box works, it means less cognitive load to use.

The most interesting thing (in this subthread) is that Linux is able to be a black box. That wasn't the case not too long ago.

Re: You can list a directory containing 8 million files But not with ls..

#40

Post by tedunangst »

moe wrote: post #15
rarrrrrr wrote: post #10

The easy way to do this is: find . -maxdepth 1 -mindepth 1 Those arguments will remove the need for find to stat each directory entry. Regardless, this is a nice walk through of low level details often overlooked.

Actually 'find' will also stat each entry no matter what. Many of the standard-tools that most people would intuitively expect to be rather optimized (find, rsync, gzip) are embarrassingly inefficient under the hood and turn belly up when confronted with data of any significant size. That probably stems from the fact that most of the development on these tools took place during a time when 1GB harddrives were "huge"…

The only issue I'm aware of with gzip is actually in zlib, where it stored 32-bit byte counters, but those were strictly optional and it works fine with data that overflowed them. The zlib window size may be only 32k, but bzip2 doesn't do that much better with 900k and a better algorithm, so I wouldn't consider it embarrassingly inefficient.
Post reply on HN