Hacker News Reader

Comment by ck2 | Hacker News Reader

I want a command that counts files in a tree like du does sizes but without having to pipe find through wc which is crazy for hundred thousand files.

Can't they just directly access inodes for high speed counting?

View on HN

It's not usually installed by default, but tree will do this: http://linux.die.net/man/1/tree

Available in most repositories, source code available at: http://mama.indstate.edu/users/ice/tree/

> Can't they just directly access inodes for high speed counting?

Don't know what you mean by that exactly. But, I'd be stunned if find is actually reading the actual files rather than just reading the directory entries in directory "files". Which is what I'd call accessing inodes "directly"

If you're dealing with a truly large number of files you could use "find . -type f -printf 1 | wc -c" which would just print a single character to the pipe and count the characters. I really doubt this is significantly slower than one program that does both would be. It'll do roughly the same amount of work.

Counting number of files is probably not a sufficiently frequently used case to justify a new standard command. What part of piping concerns you?

It can be really slow, even for a few tens of thousands of tiles. I remember watching Nautilus's "properties" panel slowly count up the number of files and directories.

I'm not sure what this has to do with piping (why would nautilus pipe the output of find when doing a directory listing?), but I doubt it's the pipe that's causing performance issues. Uncached file system access has a tendency to be slow[0].

0 - https://gist.github.com/nahurst/3711264

du just uses the fts API, so if you want something directly equivalent (omitting options and error handling) it was only barely too long to post: http://pastie.org/8315296

Compared to the equivalent find, code #1 is much faster in this completely scientific best of several runs:

  $ time (find OSS/llvm -type f -or -type l | wc -l)
  real	0m4.681s
  $ time du -d0 OSS/llvm
  real	0m4.863s
  $ time ./fts OSS/llvm
  real	0m0.559s

Ostensibly because of the lack of stat calls. On the other hand the second paste and find with no arguments are equivalent.

edit: screwed up benchmarks

Your code examples were very educational, thank you!

I have this in my .bashrc:

function lc() { if [[ "$#" -gt 1 ]]; then for DIR in "$@"; do echo -n "$DIR - " ; ls -AU1 $DIR | wc -l ; done ; else ls -AU1 "$@" | wc -l ; fi; }

Then "lc dir/" will print the number of files in the directory, and "lc dir/*" will print the number of files in each of the subdirectories. This exactly what you're looking for because it doesn't descend into the tree. If you're working with directories that may have tens or hundreds of thousands of files in them, it's useful to check first.

There really isn't any way around this. The first pass over your data is going to be slow while the inode data is examined, but it will be cached for the next pass. If you do this before that data gets removed from the cache it will be much faster.

  imac:~
  $ time find . | wc -l
  419191

  real	0m37.865s
  user	0m0.385s
  sys	0m2.611s
  imac:~
  $ time find . | wc -l
  419195

  real	0m10.503s
  user	0m0.330s
  sys	0m1.430s

This is a nasty hack where it is counting the output from find.

What do you do when find cannot handle the sheer number of files, argument too long from the linux hardcoded MAX_ARG_PAGES

We need a dedicated utility that counts inodes.

In this invocation find and wc both have two fixed arguments, you're never going to hit MAX_ARG_PAGES. The output from find is passed to wc over a pipe, and to my knowledge there's no upper limit on how much data you can transfer over a pipe. I've piped huge disk images.

I think you are confused — at no time are any files passed as arguments in the command "find . | wc -l".

Also, to count the number of files in a directory, you need to do readdir(), which will get you the names. Then, to see if any of them are directories to be recursed into you need to stat() the names individually. This is all "find" does. How, I'd very much like to know, is this "a nasty hack"?

I am not saying find is outputting files, I am saying it is decoding the full table entry for each file and formatting it, then passing that listing as an entry to wc. Which has to be a bunch of overhead that adds up when you have hundreds of thousands of files to count.

All we want from find is "count the number of inode entries in this tree branch that are type f". No formatting, no output, just count. That has to be much more efficient.

You are going to need to rely on the filesystem authors to write a tool to traverse their inode trees directly, or probably write something like that yourself.

https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux....

OMM, looking at 700k files on a spinning disk, I'm getting an uncached run at 1m13s, and a cached run at 1.2 seconds.

That's "time find . | wc -l"

It's going to be disk limited unless you're in cache.

Switching to "time find . -printf '1' | wc -c" lowers overhead to .7 seconds, so roughly 1us/file.

There is a more important benefit to using the -prinf '1' approach - which is that it won't miscount the result if any of the filenames contain newlines.

The only argument to his find command is '.', so where is the concern about argument list?

That is not at all correct.

The output from find is a list of filenames separated by newlines. The wc command is reading from stdin and counting those newlines[1] -- wc itself has just two arguments in its argv array here ("wc", "-l"). You will not exceed its argument list. Further, it is not at all a hack to count the number of files this way; rather using pipes to compose functionality is the Unix way[2].

But fwiw, if you want a count of the inodes in use in the entire filesystem, you can get that directly from "df -i".

In any case, as an exercise to the reader, I encourage you to grab the source to find and add the -count output option you desire.

[1] Technically a filename can contain newlines, so this would throw off the count. The fix for that would be to use find's -print0 output option and then pipe to something which can count on the nulls. In practice, you're unlikely to have such filenames.

[2] cf. http://harmful.cat-v.org/cat-v/unix_prog_design.pdf

It's not the pipe through wc, but statting the directory entries which slows you down.

If your locatedb is current, you can use locate for this:

    $ locate $PWD | wc -l

That runs in just a hair under a second (0.908s real) for the first instance. 'find' takes a few seconds on first pass (it's got to read from disk), but is surprising fast (0.227s real) on subsequent runs.

So I guess it depends on whether you're doing it just once or multiple times.

Try something like:

find . | sed -e 's=/[^/]*$==' | uniq -c

tree does this, don't know about suppressing the actual tree, but it tells you number of files and dirs printed at the end.

A regex match will do that easily enough:

    tree | egrep -o "[0-9]+ file(s|)"

edit: or you could just tail the output (should have thought of this first!)

    tree | tail -n1

alas it does not show file count per subdirectory

Reply on news.ycombinator.com