For every excluded object walkRDirTree called DirTree.Find to see
whether the parent directory was already in the tree. Find scans the
parent's entries linearly, so this went quadratic with many excluded
files next to many kept files, or with many directories each holding
an excluded file on a bucket based remote. With --exclude-if-present it
also ran a FileExists for every excluded object rather than once per
directory.
This keeps a set of the directories already added to the tree or
already checked, so each directory is checked once and Find isn't
needed.
With 100k kept and 100k excluded files this takes the tree build from
14.0s to 0.2s in one directory and from 39.5s to 0.54s with each pair
in its own directory.
dualfroz
upstream