util.fspath: use a dict rather than a linear scan for lookups
Previously, we'd scan through the entire directory listing looking for a
normalized match. This is O(N) in the number of files in the directory. If we
decide to call util.fspath on each file in it, the overall complexity works out
to O(N^2). This becomes a problem with directories a few thousand files or
larger.
Switch to using a dictionary instead. There is a slightly higher upfront cost
to pay, but for cases like the above this is amortized O(1). Plus there is a
lower constant factor because generator comprehensions are faster than for
loops, so overall it works out to be a very small loss in performance for 1
file, and a huge gain when there's more.
For a large repo with around 200k files in it on a case-insensitive file
system, for a large directory with over 30,000 files in it, the following
command was tested:
ls | shuf -n $COUNT | xargs hg status
This command leads to util.fspath being called on $COUNT files in the
directory.
COUNT before after
1 0.77s 0.78s
100 1.42s 0.80s
1000 6.3s 0.96s
I also tested with COUNT=10000, but before took too long so I gave up.
tests: change obsolete timestamp to avoid "gmtime()" problem on Windows
Before this patch, "test-obsolete.t" fails on Windows environment,
because strings corresponded to "tm_wday" (day of the week) field are
incorrect.
On POSIX environment, "gmtime()" returns correct "tm_wday" value even
for negative "time_t" value. On the other hand, it returns incorrect
one on Windows environment. At least, "gmtime()" of the Windows
runtime library bundled with Python 2.7.3 does.
According to
9a7d0f7e0561 introducing original timestamp value '56
120', it shouldn't cause negative "time_t" value.
test-obsolete: remove subminute timezone in test
Obsmarker format "1" does not supports sub minute timezone. So we
change the test to something slightly more sensible.
It replaced "-d '56 12'" by "-d '56 120'".