Today we want to discuss some recent updates to the Sherlock system [a high-performance cluster of Stanford University - ed.], which significantly speed up file listing in directories with a large number of entries.

Unlike regular articles, this is more of an insider report on how ongoing work on Sherlock is conducted to keep it in top shape for our users. We hope to publish more articles like this in the future.

Listing many files takes time

It all started with a support query from a user. They reported an issue that execution ls takes several minutes in a directory with over 15,000 entries in $SCRATCH [a directory for temporary files - ed.].

Thousands of files in one directory usually create difficulties for the file system, and this is definitely not recommended. The user was aware of this and acknowledged that it was not good, but mentioned that on their laptop, the listing is done 1000 times faster than in Sherlock. Naturally, this concerned us. So we looked deeper.

Because ls looks nice

We examined what actually happens ls when listing a directory and why the process takes so much time. In most modern distributions ls it by default runs as ls --color=auto, because everyone likes color.

But pretty colors come at a cost: for each file, ls it must obtain information about the file type, its permissions, flags, extended attributes, and so on to choose the appropriate color.

One simple solution to the problem is to disable color in ls entirely, but imagine the user outrage. We certainly can't take away colored output; we're not monsters.

So we looked deeper. ls colors the entries through the environment variable LS_COLORS, which is set by dircolors(1) based on the configuration file dir_colors(5).Yes, the executable reads the configuration file to create the environment variable, which ls then uses (and if you don't know about the files door (do), then dir_colors will respond, despite everything).

Let's delve deeper

To determine which of the coloring schemes causes the slowdown, we created an experimental environment:

$ mkdir $SCRATCH/dont
$ touch $SCRATCH/dont/{1..10000} # don't try this at home!
$ time ls --color=always $SCRATCH/dont | wc -l
10000

real    0m12.758s
user    0m0.104s
sys     0m0.699s

12.7 seconds for 10,000 files, not very good.

By the way, a flag is needed --color=always: although it switches to ls --color=auto, but ls detects when it's not connected to a terminal (e.g., through a pipe or with output redirection) and disables coloring if set to auto. Smart guy.

So what takes so long? We looked into it using strace:

$ strace -c ls --color=always $SCRATCH/dont | wc -l
10000
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 44.21    0.186617          19     10000           lstat
 42.60    0.179807          18     10000     10000 getxattr
 12.19    0.051438           5     10000           capget
  0.71    0.003002          38        80           getdents
  0.07    0.000305          10        30           mmap
  0.05    0.000217          12        18           mprotect
  0.03    0.000135          14        10           read
  0.03    0.000123          11        11           open
  0.02    0.000082           6        14           close
[...]

Wow: 10,000 calls to lstat(), 10,000 calls to getxattr() (which all fail because there are no attributes that ls is looking for in our environment), 10,000 calls to capget().

Surely this can be optimized.

Attribute capabilities? Nope.

Following the advice of a 10-year-old bug, we tried disabling attribute checks capabilities:

$ eval $(dircolors -b | sed s/ca=[^:]*:/ca=:/)
$ time strace -c ls --color=always $SCRATCH/dont | wc -l
10000
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 98.95    0.423443          42     10000           lstat
  0.78    0.003353          42        80           getdents
  0.04    0.000188          10        18           mprotect
  0.04    0.000181           6        30           mmap
  0.02    0.000085           9        10           read
  0.02    0.000084          28         3           mremap
  0.02    0.000077           7        11           open
  0.02    0.000066           5        14           close
[...]
------ ----------- ----------- --------- --------- ----------------
100.00    0.427920                 10221         6 total

real    0m8.160s
user    0m0.115s
sys     0m0.961s

Wow, a speedup to 8 seconds! We eliminated all those expensive calls getxattr(), and the calls capget() disappeared too, great.

But there are still these pesky calls lstat(), though…

How many colors are needed?

So we examined it in more detail LS_COLORS.

We initially just disabled this variable:

$ echo $LS_COLORS
rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so=01;35:do=01;35:bd=40;33;01:cd=40;33;01:or=40;31;01:su=37;41:sg=30;43:ca=:tw=30;42:ow=34;42:st=37;44:ex=01;32:*.tar=01;31:*.tgz=01;31:*.arc=01;31:*.arj=01;31:*.taz=01;31:*.lha=01;31:*.lz4=01;31:*.lzh=01;31:*.lzma=01;31:*.tlz=01;31:*.txz=01;31:*.tzo=01;31:*.t7z=01;31:*.zip=01;31:*.z=01;31:*.Z=01;31:*.dz=01;31:*.gz=01;31:*.lrz=01;31:*.lz=01;31:*.lzo=01;31:*.xz=01;31:*.bz2=01;31:*.bz=01;31:*.tbz=01;31:*.tbz2=01;31:*.tz=01;31:*.deb=01;31:*.rpm=01;31:*.jar=01;31:*.war=01;31:*.ear=01;31:*.sar=01;31:*.rar=01;31:*.alz=01;31:*.ace=01;31:*.zoo=01;31:*.cpio=01;31:*.7z=01;31:*.rz=01;31:*.cab=01;31:*.jpg=01;35:*.jpeg=01;35:*.gif=01;35:*.bmp=01;35:*.pbm=01;35:*.pgm=01;35:*.ppm=01;35:*.tga=01;35:*.xbm=01;35:*.xpm=01;35:*.tif=01;35:*.tiff=01;35:*.png=01;35:*.svg=01;35:*.svgz=01;35:*.mng=01;35:*.pcx=01;35:*.mov=01;35:*.mpg=01;35:*.mpeg=01;35:*.m2v=01;35:*.mkv=01;35:*.webm=01;35:*.ogm=01;35:*.mp4=01;35:*.m4v=01;35:*.mp4v=01;35:*.vob=01;35:*.qt=01;35:*.nuv=01;35:*.wmv=01;35:*.asf=01;35:*.rm=01;35:*.rmvb=01;35:*.flc=01;35:*.avi=01;35:*.fli=01;35:*.flv=01;35:*.gl=01;35:*.dl=01;35:*.xcf=01;35:*.xwd=01;35:*.yuv=01;35:*.cgm=01;35:*.emf=01;35:*.axv=01;35:*.anx=01;35:*.ogv=01;35:*.ogx=01;35:*.aac=00;36:*.au=00;36:*.flac=00;36:*.mid=00;36:*.midi=00;36:*.mka=00;36:*.mp3=00;36:*.mpc=00;36:*.ogg=00;36:*.ra=00;36:*.wav=00;36:*.axa=00;36:*.oga=00;36:*.spx=00;36:*.xspf=00:
$ unset LS_COLORS
$ echo $LS_COLORS

$  time ls --color=always $SCRATCH/dont | wc -l
10000

real    0m13.037s
user    0m0.077s
sys     0m1.092s

What?! Still 13 seconds?

It turns out that when the environment variable LS_COLORS is not defined or only one of its elements is missing =color:, it defaults to using the built-in database and still utilizes colors. Therefore, if you want to disable coloring for a specific file type, you need to override it with = or 00 in the file DIR_COLORS.

After much trial and error, we narrowed it down to this:

EXEC 00
SETUID 00
SETGID 00
CAPABILITY 00

written as

LS_COLORS='ex=00:su=00:sg=00:ca=00:'

This means: do not color files by attributes capabilities, nor by bits setuid/setgid, or by executable flag.

Speeding up `ls`

And if none of these checks are performed, the calls lstat() disappear, and it's a whole different story:

$ export LS_COLORS='ex=00:su=00:sg=00:ca=00:'
$ time strace -c ls --color=always $SCRATCH/dont | wc -l
10000
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 63.02    0.002865          36        80           getdents
  8.10    0.000368          12        30           mmap
  5.72    0.000260          14        18           mprotect
  3.72    0.000169          15        11           open
  2.79    0.000127          13        10           read
[...]
------ ----------- ----------- --------- --------- ----------------
100.00    0.004546                   221         6 total

real    0m0.337s
user    0m0.032s
sys     0m0.029s

0.3 seconds on a list of 10,000 files, a record.

Configuring Sherlock

From 13 seconds with default settings to 0.3 seconds with slight adjustments LS_COLORS means a 40-fold speedup by omitting setuid / setgid and colored executable files. Not such a big loss.

Of course, it's now set up in Sherlock for each user.

But if you want to restore the coloring, you can simply revert to the default settings: