Today, we’d like to share some of our recent work on Sherlock that allowed a pretty significant speedup when listing files in directories with a lot of entries.

Unlike our usual announcements, this post is more of a behind-the-scenes account of things we do on a regular basis on Sherlock, to keep it up and running in the best possible conditions for our users. We hope to have more of this in the future.

Listing many files takes time

It all started from a support question, from a user reporting a usability problem with ls taking several minutes to list the contents of a 15,000+ entries directory on $SCRATCH.

Having thousands of files in a single directory is usually not very file system-friendly, and definitely not recommended. The user knew this already and admitted that wasn’t great, but when he mentioned his laptop was 1,000x faster than Sherlock to list this directory’s contents, of course, it stung. So we looked deeper.

Because ls is nice

We looked at what ls actually does to list the contents of a directory, and why it was taking so long to list files. On most modern distributions, ls is aliased to ls --color=auto by default. Which is nice, because everybody likes 🌈.

But those pretty colors come at a price: for each and every file it displays, ls needs to get information about a file’s type, its permissions, flags, extended attributes and the like, to choose the appropriate color to display.

One easy solution to our problem would have been to disable colored output in ls altogether, but imagine the uproar. There is no way we could have taken 🌈 away from users, we’re not monsters.

So we looked deeper. ls does coloring through the LS_COLORS environment variable, which is set by dircolors(1), based on a dir_colors(5) configuration file. Yes, that’s right: an executable reads a config file to produce an environment variable that is in turn used by ls.[1]

🤯

Let’s dive in

To be able to determine which of those specific coloring schemes were responsible for the slowdowns, 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.7s for 10,000 files, not great. 🐌

BTW, we need the --color=always flag, because, although it’s aliased to ls --color=auto, ls detects when it’s not attached to a terminal (like when piped to something or with its output redirected), and then turns off coloring when set to auto. Smart guy.

So, what’s taking so much time? Equipped with our strace-fu, we looked:

$ 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 by the way, because the attributes that ls is looking for don’t exist in our environment), 10,000 calls to capget().

Can do better for sure.

File capabilities? Nah

Following advice from a 10+ year-old bug, we tried file disabling capability checking:

$ 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

Woohoo, down to 8s! We got rid of all those expensive getxattr() calls, and capget() calls are gone too, 👍.

We still have all those pesky lstat(), though…

How many colors is too many colors?

So we took a look at LS_COLORS in more details.

The first attempt was to simply unset that 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;36:
$ unset LS_COLORS
$ echo $LS_COLORS

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

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

Whaaaaat!?! Still 13s?

It turns out that when the LS_COLORS environment variable is not defined, or when just one of its <type>=color: elements is not there, it defaults to its embedded database and uses colors anyway. So if you want to disable coloring for a specific file type, you need to override it with <type>=:, or <type> 00 in the DIR_COLORS file.

After a lot of trial and error, we narrowed it down to this:

EXEC 00
SETUID 00
SETGID 00
CAPABILITY 00

which translates in

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

In normal people speak, that means: don’t colorize files based on the their file capabilities, setuid/setgid bits nor executable flag.

Let ls fly

And if you don’t do any of those checks, then the lstat() calls disappear, and now, boom 🚀:

$ 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.3s to list 10,000 files, track record. 🏁

This is on Sherlock

From 13s with the default settings, to 0.3s with a small LS_COLORS tweak, that’s a 40x speedup right there, for the cheap price of not having setuid/setgid or executable files colorized differently.

Of course, this is now setup on Sherlock, for every user’s benefit.

But if you want all of your colors back, no worries, you can simply revert to the distribution defaults with:

$ unset LS_COLORS

But then, if you have directories with many many files, be sure to have some coffee handy while ls is doing its thing.


  1. Also, if you didn’t know about doors, well, dir_colors got you covered no matter what. If you really wonder, the file type is do.