RFC patch, 6 partssymlinks.c: small cleanup and optimisation

Here is 6 small patches which should further improve the time it take to do 'git checkout'. After the 6 patches, the numbers from the 'git checkout -q my-v2.6.27' test, should now look like this:

TOTAL        136752 100.000% OK:124567 NOT: 12185   8.641698 sec   63 usec/call
lstat64       55502  40.586% OK: 49122 NOT:  6380   2.463762 sec   44 usec/call
    strings   55502 tot  30163 uniq   1.840 /uniq   2.463762 sec   44 usec/call
    files     47122 tot  23813 uniq   1.979 /uniq   2.070486 sec   44 usec/call
    dirs       2000 tot   1436 uniq   1.393 /uniq   0.087281 sec   44 usec/call
    errors     6380 tot   5187 uniq   1.230 /uniq   0.305995 sec   48 usec/call
                  4   0.007% OK:     3 NOT:     1  "arch/sh/boards"
                  3   0.005% OK:     3 NOT:     0  ".git/HEAD"
                  3   0.005% OK:     3 NOT:     0  ".git/refs/heads/my-v2.6.27"
                  3   0.005% OK:     3 NOT:     0  ".gitignore"
                  3   0.005% OK:     3 NOT:     0  ".mailmap"
                  3   0.005% OK:     3 NOT:     0  "CREDITS"
                  3   0.005% OK:     3 NOT:     0  "Documentation"
                  3   0.005% OK:     3 NOT:     0  "Documentation/00-INDEX"
                  3   0.005% OK:     3 NOT:     0  "Documentation/ABI/testing/sysfs-block"
                  3   0.005% OK:     3 NOT:     0  "Documentation/ABI/testing/sysfs-firmware-acpi"
                  3   0.005% OK:     3 NOT:     0  "Documentation/CodingStyle"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DMA-API.txt"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DMA-mapping.txt"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/Makefile"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/gadget.tmpl"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/kernel-api.tmpl"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/kernel-locking.tmpl"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/procfs-guide.tmpl"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/procfs_example.c"
                  3   0.005% OK:     3 NOT:     0  "Documentation/DocBook/rapidio.tmpl"
<snipp>
fstat64       14403  10.532% OK: 14403 NOT:     0   0.179938 sec   12 usec/call

So, since last time, and because of patch 4/6, almost 14 400 of the lstat() calls has now become fstat() calls, and it seems we have saved (* 14403 (- 44 12)) = 460 896 microseconds system time because of this. I am planing to do a more complete and long-running /usr/bin/time test, to get real numbers.

With both patch-series, the count of lstat() calls for this particular test have dropped from 120 954 to 55 502, which is a total reduction of 65 452 calls or 54%.

Please note that patch 6/6 is only to be a debug patch, to catch a possible ping-pong situation inside the lstat_cache(), so I think that it should at _most_ be merged to the pu branch, such that people who wish to test, can 'git cherry-pick' the patch from there.

Kjetil Barvik (6):
  symlinks.c: small cleanup and optimisation
  remove some memcpy() and strchr() calls inside create_directories()
  cleanup of write_entry() in entry.c
  use fstat() instead of lstat() when we have an opened file
  combine-diff.c: remove a call to fstat() inside show_patch_diff()
  lstat_cache(): print a warning if doing ping-pong between cache types

 combine-diff.c |    5 +-
 entry.c        |  144 ++++++++++++++++++++++++++++++--------------------------
 symlinks.c     |   48 ++++++++++++++-----
 3 files changed, 115 insertions(+), 82 deletions(-)

Simplify the if-else test in longest_match_lstat_cache() such that we only have one simple if test. Instead of testing for 'i == cache.len' or 'i == len', we transform this to a common test for 'i == max_len'.

And to further optimise we use 'i >= max_len' instead of 'i == max_len', the reason is that it is now the exact opposite of one part inside the while-loop termination expression 'i < max_len && name[i] == cache.path[i]', and then the compiler can hopefully/probably reuse a test-result from it.

We do similar transformations inside the lstat_cache() and the invalidate_lstat_cache() functions.

The result is a little smaller text-size as shown below:

 ~/git/git $ size symlinks_??_*
   text	   data	    bss	    dec	    hex	filename
   1282       0	   4116	   5398	   1516	symlinks_O2_after.o
   1378       0	   4116	   5494	   1576	symlinks_O2_before.o
    896       0	   4116	   5012	   1394	symlinks_Os_after.o
    902       0	   4116	   5018	   139a	symlinks_Os_before.o

'O2' means that the file is compiled with 'gcc -O2', and similar 'Os' means that the file is compiled with 'gcc -Os' (gcc 4.3.2).

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 symlinks.c |   25 +++++++++++++------------
 1 files changed, 13 insertions(+), 12 deletions(-)

Kjetil Barvik <barvik@broadpark.no> writes:

This is *dense*, and made me wonder if is this really worth doing.

As you described in your commit log message, what this really wants to check is (i == max_len). By saying (i >= max_len) you are losing readability, optimizing for compilers (that do not notice this) and pessimizing for human readers (like me, who had to spend a few dozens of seconds to realize what you are doing, to speculate why you might have thought this would be a good idea, and writing this paragraph). I do not know if it is a good trade-off.

Likewise.

Likewise.

Likewise.

People who would want to fix potential bugs in this code 3 months down the road may not have a ready access to your commit log message (they may be looking at an extract from a release tarball, scratching their heads wondering why you are not checking for equality). Perhaps the inline function can have comments that says something like "when comparing the return value from this function to see if it is equal to cache.len or len, checking if the returned value is >= might help your compiler optimize it better" to help the readers, but still, I do not know if it is a good trade-off.

Good.

* Kjetil Barvik <barvik@broadpark.no> writes:

* Junio C Hamano <gitster@pobox.com> writes:

  When the compiler see the source line:

    'while (i < max_len && name[i] == cache.path[i])'

  it will, from what I know about compilers and machine instructions for
  intel cpu's, generate the following pseudo instructions for this line
  (before more compiler optimisation is done):

   1    test !(i < max_len)   /* which is (i >= max_len) */
   2    jump-if-not-zero  first_instruction_address_outside_the_loop
   3    "some instructions to retrieve some memory locations and test
         name[i] == cache.path[i]"
   4    jump-if-not-zero instruction-address-to-continue-to-loop

  So, I thought that if I could use the exact same test as the compiler
  have to generate for line 1, then I would maybe saved a test, and
  maybe also a jump instruction.

  Compiling with 'gcc -Os' (optimise for text segment size) I was able to
  save 4 bytes for this file, which I think shows that gcc is able to
  take advantage of this trick.

  But, it was not easy to come up with a real test which shows a
  noticeable time difference from this trick, so, I guess this is only a
  trick for the kernel people (at most), so I revert it and will use
  '==' for version 2, such that we keep a little better readability.

  -- kjetil

  ps! Compiling with '-march=core2 -O2 -g0 -s -fomit-frame-pointer', the
      difference in text segment was 64 bytes when using this trick.

Remove the call to memcpy() and strchr() for each path component tested, and instead add each path component as we go forward inside the while-loop.

Impact: small optimisation

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---

OK, maybe I instead should have tried to merge the function create_directories() with the safe_create_leading_directories() and *_const() functions? What do pepople think?

 entry.c |   23 ++++++++++++++---------
 1 files changed, 14 insertions(+), 9 deletions(-)

Kjetil Barvik <barvik@broadpark.no> writes:

Strictly speaking, the safe_create_leading_* functions are meant to work on paths inside $GIT_DIR and are not meant for paths inside the work tree, which is this function is about. Their semantics are different with respect to adjust_shared_perm().

Which means that you would either have two variants (one for work tree paths, and another for paths inside $GIT_DIR), or a unified function that has an argument to specify whether to run adjust_shared_perm().

HOWEVER.

That is only "strictly speaking".

A non-bare repository that is shared feels like an oximoron, but perhaps there is a valid "shared work area" workflow that may benefit from such a setup.

I see existing (mis)uses of the safe_create_leading_* in builtin-apply.c, builtin-clone.c (the one that creates the work_tree, the other one is Ok), merge-recursive.c (both call sites) that are used to touch the work tree, but all places that create regular files in the work tree do not run adjust_shared_perm() but simply honor the user's umask.

If we _were_ to support a "shared work area" workflow, having a unified "create leading directory" function that always calls adjust_shared_perm() may make sense (note that adjust_shared_perm() is a no-op in a non-shared repository). We then need to also call adjust_shared_perm() for codepaths that create regular files as well, though (e.g. write_entry() in entry.c, but there are many others).

Please do not split the line like this.

The existing sources are not laid out to allow "grep ^funcname(", nor are we going to reformat all the files to support such a use case.

When we pass <string, length> pair to functions, I think we pass them in the order I just wrote in all the other functions.

The micro-optimization itself makes sense to me, though.

The switch-cases for S_IFREG and S_IFLNK was so similar that it will be better to do some cleanup and use the common parts of it.

Also fold the longest lines such that no line is longer then 80 chars or so.

And the entry.c file should now be clean for 'gcc -Wextra' warnings.

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---

If people do not like this approach I can be willing to drop it from this patch-series, but then I get some source code duplication from the next patch (4/6).

 entry.c |  114 +++++++++++++++++++++++++++++++-------------------------------
 1 files changed, 57 insertions(+), 57 deletions(-)

Kjetil Barvik <barvik@broadpark.no> writes:

Merging of the two similar codepaths looked good from a cursory reading, but if you have doubts about one patch, it usually is easier for other people to work with you if the series is reordered to have it near the end, iow, undisputably good ones first.

You lost greppability when somebody calls for help saying "I am getting an error message that says 'git checkout-index: unable to read sha1 file'".

Currently inside write_entry() we do an lstat(path, &st) call on a file which have just been opened inside the exact same function. It should be better to call fstat(fd, &st) on the file while it is opened, and it should be at least as fast as the lstat() method.

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 entry.c |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

Currently inside show_patch_diff() we have and fstat() call after an ok lstat() call. Since we before the call to fstat() have already test for the link case with S_ISLNK() the fstat() can be removed.

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 combine-diff.c |    5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)

2009/1/26 Kjetil Barvik <barvik@broadpark.no>:

s/have and/have an/ ?

Mike Ralphson <mike.ralphson@gmail.com> writes:

  Correct! Will fix.  Thanks!

  -- kjetil

2009/1/27 Kjetil Barvik <barvik@broadpark.no>

Typo stood out and blinded me to the rest of the grammar... How about:

Currently inside show_patch_diff() we have an fstat() call after an ok lstat() call. Since before the call to fstat() we have already tested for the link case with S_ISLNK(), the fstat() can be removed.

'Half-a-job' Mike

Kjetil Barvik <barvik@broadpark.no> writes:

Good eyes.  Thanks.

Junio C Hamano <gitster@pobox.com> writes:

Heh, I noticed you will update the commit log message, so I'll dequeue this and wait for an update.

Junio C Hamano <gitster@pobox.com> writes:

  Yes, I am planing a v2 in 1 or 3 days (it takes some time to run long-
  running tests).  And then hopefully I have addressed all comments so
  far.  Thanks for comments!

  -- kjetil