Re: [PATCH/RFC v3 6/8] Add case insensitivity support when using git ls-files

From: Joshua Jensen <jjensen@workspacewhiz.com>
Date: Oct 4, 2010, 14:58 UTC
Message-ID: <4CA9EBA2.9020401@workspacewhiz.com>
In-Reply-To: <AANLkTikgLzczp1Gkmcg2v35oE2bKxBtxY389Z76FJDRz@mail.gmail.com>

  ----- Original Message -----
From: Erik Faye-Lund
Date: 10/4/2010 8:03 AM

Show 19 quoted lines

> On Mon, Oct 4, 2010 at 9:49 AM, Jonathan Nieder<jrnieder@gmail.com>  wrote:
>> Johannes Sixt wrote:
>>> On Sonntag, 3. Oktober 2010, Thomas Adam wrote:
>>>> It's a real shame about the code duplication here.  Can we not avoid
>>>> it just by doing:
>>>>
>>>> unsigned char c1 = (ignore_case) ? tolower(*match) : *match;
>>>> unisgned char c2 = (ignore_case) ? tolower(*name) : *name;
>>>>
>>>> I appreciate that to some it might look like perl golf, but...
>>> It has been discussed, and IIRC, the concensus was to keep the code
>>> duplication because this is an inner loop.
>> Did anyone time it?  If it really is not dwarfed by other computation,
>> then how about (warning: ugly!)
>>
> I believe it was timed. I was the one who reacted on this the first
> time around, and I seem to remember that the performance impact was
> indeed significant. This function is used all the time when updating
> the index etc IIRC.

In a good sized repository I have in front of me now, running 'git ls-files' through this code path results in 705,374 characters being processed by this body of code. Given the code listed above, that means we add 1,410,748 additional comparisons that everyone has to suffer through, even those on a case sensitive file system. Sure, the code could be optimized to not perform the double comparison, and the compiler may actually perform that optimization. Still, it is hundreds of thousands of additional comparisons and branches that were not there before.

I'm running on a really, really fast machine, a Xeon X5560. The difference in time for the above code versus what is in the patch seems to average about 0.07 seconds. Remember, this is an incredibly fast machine, and I imagine it will be worse on machines with slower processors and less cache.

As discussed in the original thread (which, I believe, was on the msysGit mailing list), one of Git's features is its speed. Maintaining that speed in the core.ignorecase=false case is top priority for me, but others with more know how can tell me I'm wrong.

Josh