What is the algorithm unix du command uses to calculate disk space?

I've tried using du to calculate disk usage today on a single directory. The size of directory is 6GB and it took the following amount of time to calculate:

prompt> time du -sh .
6.0G   .

real    1m32.405s
user    0m2.053s
sys     0m16.552s

What is the algorithm unix du c开发者_开发百科ommand uses to calculate disk space? Why is it so slow? Are there any alternatives to calculate disk space more efficiently? The platform of invocation is Sun. The directory for which size was calculated is NFS mounted.

du has to list all the directories and stat every file found so that ends up with read all over the disk

while getting the sizes of the files it sums them and when finished it prints the sum

for example on this one directory with like 2 million files on a sshfs filesystem:

prompt$ time du -sh .
367G    .

real    12m53.093s
user    0m3.848s
sys     0m14.265s

but due to caching for the second run it only takes:

prompt$ time du -sh .
367G    .

real    4m56.875s
user    0m4.136s
sys     0m15.257s

I think it just recursively walks the directory, while adding together the sizes of the files found. Quite simple, really, but of course it takes time. It might be faster if the file system makes these operations quicker.

Its speed depends on files/directories count. If you have a directory with 6 1Gb files, it will take much less time to calculate. It calculates files size in the given directory, and recursively for each child directory.