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. ↩