v2, 3 partsgrep: enable threading with -p and -W using lazy attribute lookup

[Eric, I measured some numbers that may be interesting to the discussion about b2924dc. See below.]

This round wraps up the original patch I posted, plus the draft patch I posted inline the other day with René's review taken into account. I also added a patch that rips out threading in the non-worktree case; read on for the reasoning.

René Scharfe wrote:

Well, turns out I was measuring something completely stupid.  I had

  git grep --cached -W INITRAMFS_ROOT_UID

where I put the --cached originally because that makes it independent of the worktree (which in the very first measurements I still had wiped, as I tend to do for this repo; I checked it out again after that). This in fact gives me (~/g/git-grep --cached INITRAMFS_ROOT_UID, leaving aside -W; best of 10):

  THREADS=8:   2.88user 0.21system 0:02.94elapsed
  THREADS=4:   2.89user 0.29system 0:02.99elapsed
  THREADS=2:   2.83user 0.36system 0:02.87elapsed
  NO_PTHREADS: 2.16user 0.08system 0:02.25elapsed

Uhuh. Doesn't scale so well after all. But removing the --cached, as most people probably would:

  THREADS=8:   0.19user 0.32system 0:00.16elapsed
  THREADS=4:   0.16user 0.34system 0:00.17elapsed
  THREADS=2:   0.18user 0.32system 0:00.26elapsed
  NO_PTHREADS: 0.12user 0.17system 0:00.31elapsed

So I conclude that during any grep that cannot use the worktree, having any threads hurts.

In addition, during a grep that *can* use the worktree, THREADS=8 still helps somewhat on my dual-core i7, though it goes downhill from there (12 is again as fast as 4; I verified these details using best-of-50 timings, and it is reproducible.)

I have also run timings on a 2*6-core workstation running OS X, where performance is best at 5 cores:

  2 threads:  0.96 real   0.41 user   1.27 sys
  3 threads:  0.68 real   0.41 user   1.30 sys
  4 threads:  0.54 real   0.43 user   1.63 sys
  5 threads:  0.50 real   0.41 user   1.51 sys
  6 threads:  0.54 real   0.43 user   1.63 sys
  7 threads:  0.86 real   0.49 user   1.93 sys
  8 threads:  0.98 real   0.51 user   2.07 sys

I kid you not. That's best-of-50 and rather stable. It's on the same tree as the Linux machine too, except for the problem that the OS X FS is set to case-insensitive and thus cannot represent the tree exactly. So from git's POV, there are unstaged changes.

Sadly I do not have access to a Linux box having more than 2 physical cores. If you have one, please run some tests :-)

So based on my measurements, I would suggest that unless we have evidence of it scaling beyond 8 cores on some machine, b2924dc (grep: detect number of CPUs for thread spawning) be dropped. For now I'm ignoring the problem that on OS X it doesn't even scale to 8; I'd rather check how it fares on Linux first.

I added a third patch on top that disables threading in any case that does not hit the worktree. I wonder if I missed something or if it really is that simple. The neat part is that it's also a reduction in code required, and at the same time avoids any issues 2/3 might have with a future attributes-from-trees implementation.

With this I get

  worktree, 8 threads: 0.15user 0.37system 0:00.17elapsed
  --cached, 8 threads: 2.18user 0.07system 0:02.27elapsed

Of course, we could probably gain a huge boost if the read_sha1 machinery could be made threaded, so that it can unpack several objects at a time. In addition, I can well imagine that there are combinations of delta density, object size, and luck where it pays off to grep in parallel. Do we care?

Now I really should do something else than fretting over the sub-second performance of git-grep...

Thomas Rast (3):
  grep: load funcname patterns for -W
  grep: enable threading with -p and -W using lazy attribute lookup
  grep: disable threading in all but worktree case

 builtin/grep.c  |  153 ++++++++++++++++--------------------------------------
 grep.c          |   73 ++++++++++++++++----------
 grep.h          |    7 +++
 t/t7810-grep.sh |   14 +++++
 4 files changed, 112 insertions(+), 135 deletions(-)

git-grep avoids loading the funcname patterns unless they are needed. ba8ea74 (grep: add option to show whole function as context, 2011-08-01) forgot to extend this test also to the new funcbody feature. Do so.

The catch is that we also have to disable threading when using
userdiff, as explained in grep_threads_ok().  So we must be careful to
introduce the same test there.
---
 grep.c          |    7 ++++---
 t/t7810-grep.sh |   14 ++++++++++++++
 2 files changed, 18 insertions(+), 3 deletions(-)

Lazily load the userdiff attributes in match_funcname(). Use a separate mutex around this loading to protect the (not thread-safe) attributes machinery. This lets us re-enable threading with -p and -W while reducing the overhead caused by looking up attributes.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 builtin/grep.c |   10 +++++++-
 grep.c         |   74 ++++++++++++++++++++++++++++++++++----------------------
 grep.h         |    7 +++++
 3 files changed, 61 insertions(+), 30 deletions(-)

Measuring grep performance showed that in all but the worktree case (as opposed to --cached, <committish> or <treeish>), threading actually slows things down. For example, on my dual-core hyperthreaded i7 in a linux-2.6.git at v2.6.37-rc2, I got:

Threads worktree case | --cached case -------------------------------------------------------------------------- 8 (default) | 2.17user 0.15sys 0:02.20real | 0.11user 0.26sys 0:00.11real 4 | 2.06user 0.17sys 0:02.08real | 0.11user 0.26sys 0:00.12real 2 | 2.02user 0.25sys 0:02.08real | 0.15user 0.37sys 0:00.28real NO_PTHREADS | 1.57user 0.05sys 0:01.64real | 0.09user 0.12sys 0:00.22real

I conjecture that this is caused by contention on read_sha1_mutex.

So disable threading entirely when not scanning the worktree, to get
the NO_PTHREADS performance in that case.  This obsoletes all code
related to grep_sha1_async.  The thread startup must be delayed until
after all arguments have been parsed, but this does not have a
measurable effect.
---
 builtin/grep.c |  157 ++++++++++++++++----------------------------------------
 1 files changed, 44 insertions(+), 113 deletions(-)

Am 02.12.2011 14:07, schrieb Thomas Rast:

Are the columns mixed up?

Yeah, and I wonder why we need to have this lock in the first place. In theory, multiple readers shouldn't have to affect each other at all, right? The lock could be pushed down into read_sha1_file(), or a thread-safe variant of the function added.

In pratice, however, the code in sha1_file.c etc. scares me. ;-)

This is a bit radical. I think the underlying issue that read_sha1_file() is not thread-safe can be solved eventually and then we'd need to readd that code.

How about adding a parameter to control the number of threads (--threads?) instead that defaults to eight (or five) for the worktree and one for the rest? That would also make benchmarking easier.

René

PS: Patches one and three missed a signoff.

René Scharfe wrote:

Indeed, sorry.

In case you were wondering why this table is different from the numbers given in the cover letter: I noticed at some point that I had an incomplete checkout (apparently 'git checkout -- .' is really not the same as 'git reset --hard'... sigh). Then I saw that while the numbers were different, the conclusion was not, so I forgot to update it.

I'm also scared of sha1_file.c, especially when it gets down to packfiles. But perhaps it wouldn't be *too* hard to do it in parallel iff the object can be read from the loose object store.

Oops, thanks, turns out I had a misconfigured alias ...

Am 02.12.2011 17:15, schrieb René Scharfe:

Like this:

-- >8 --
Subject: grep: add parameter --threads

Allow the number of threads to be specified by the user. This makes benchmarking the performance impact of different numbers of threads much easier.

Move the code for thread handling after argument parsing. This allows to change the default number of threads based on the kind of search (worktree etc.) later on.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
Applies on top of your second patch.

 Documentation/git-grep.txt |    4 ++
 builtin/grep.c             |   75 +++++++++++++++++++++++--------------------
 2 files changed, 44 insertions(+), 35 deletions(-)

Reading of git objects needs to be protected by an exclusive lock and cannot be parallelized. Searching the read buffers can be done in parallel, but for simple expressions threading is a net loss due to its overhead, as measured by Thomas. Turn it off unless we're searching in the worktree.

Once the object store can be read safely by multiple threads in parallel this patch should be reverted.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
Goes on top of my earlier patch.  Could use a better commit message
with your (cleaned up) performance numbers.

 Documentation/git-grep.txt |    5 +++--
 builtin/grep.c             |    2 +-
 2 files changed, 4 insertions(+), 3 deletions(-)

On Wed, Dec 07, 2011 at 12:01:37AM +0100, René Scharfe wrote:

Based on my earlier numbers, I was going to complain that we should also be checking the "simple expressions" assumption here, as time spent in the actual regex might be important.

However, after trying to repeat my experiment, I think the numbers I posted earlier were misleading. For example, using my "more complex" regex of 'a.*b':

  $ time git grep --threads=8 'a.*b' HEAD >/dev/null
  real    0m8.655s
  user    0m23.817s
  sys     0m0.480s

Look at that sweet, sweet parallelism. It's a quad-core with hyperthreading, so we're not getting the 8x speedup we might hope for (presumably due to lock contention on extracting blobs), but hey, 3x isn't bad. Except, wait:

  $ time git grep --threads=0 'a.*b' HEAD >/dev/null
  real    0m7.651s
  user    0m7.600s
  sys     0m0.048s

We can get 1x on a single core, but the total time is lower! This processor is an i7 with "turbo boost", which means it clocks higher in single-core mode than when multiple cores are active. So the numbers I posted earlier were misleading. Yes, we got parallelism, but at the cost of knocking the clock speed down for a net loss.

The sweet spot for me seems to be:

  $ time git grep --threads=2 'a.*b' HEAD >/dev/null
  real    0m6.303s
  user    0m11.129s
  sys     0m0.220s

I'd be curious to see results from somebody with a quad-core (or more) without turbo boost; I suspect that threading may have more benefit there, even though we have some lock contention for blobs.

This doesn't kick in for "--cached", which has the same performance characteristics as grepping a tree. I think you want to add "&& !cached" to the conditional.

-Peff

Am 07.12.2011 05:42, schrieb Jeff King:

Ugh, right, Turbo Boost complicates matters.

I don't understand the multiplied user time in the threaded case, though. Is it caused by busy-waiting? Thomas reported similar numbers earlier.

It would be nice if we could come up with simple rules to calculate defaults for the number of threads on a given run. Users shouldn't have to specify this option normally. And it would be good if these rules didn't require a list of all CPUs known to git. :)

Oh, yes.

René

On Wed, Dec 07, 2011 at 06:11:47PM +0100, René Scharfe wrote:

I think it's mostly the clock speed. This processor runs at 1.86GHz but boosts to 3.2GHz. So we'd expect just the actual work to take close to twice as long. Plus it's a quad-core with hyperthreading, so 8 threads is going to mean two threads sharing each core, including cache (i.e., hyperthreading a core does not let you double performance, even though it presents itself as an extra core).

And then you have context switching and lock overhead. So I can believe that it takes 3x the CPU time to accomplish the task. In an ideal world, it would be mitigated by having 8x the threads, but in this case, lock contention brings us down to less than 3x, and it's a slight net loss.

-Peff

On Tue, Dec 06, 2011 at 11:42:42PM -0500, Jeff King wrote:

Dumb question (I missed the beginning of the conversation): what kind of storage are you using, and is the data already cached?

I seem to recall part of the motivation for the multithreading being NFS, where the goal isn't so much to keep CPU's busy as it is to keep the network busy.

Probably a bigger problem for something like "git status" which I think ends up doing a series of stat's (which can each require a round trip to the server in the NFS case), as it is a problem for something like git-grep that's also doing reads.

Just a plea for considering the IO cost as well when making these kinds of decisions....

(Which maybe you already do, apologies again for just naively dropping into the middle of a thread.)

--b.

On Wed, Dec 07, 2011 at 03:11:05PM -0500, J. Bruce Fields wrote:

Sorry, I should have been clear: all of those numbers are with a warm cache. So this is measuring only CPU.

This system has a decent-quality SSD, so the I/O timings are perhaps not as interesting as they might otherwise be. But here are cold cache numbers (each run after 'echo 3 >/proc/sys/vm/drop_caches'):

  HEAD, --threads=0: 4.956s
  HEAD, --threads=8: 9.917s
  working tree, --threads=0: 17.444s
  working tree, --threads=8: 6.462s

So when pulling from the object db, threads are still a huge loss (because the data is compressed, the SSD is fast, and we spend a lot of CPU time inflating; so it ends up close to the warm cache results). But for the working tree, the I/O parallelism is a huge win.

So at least on my system, cold cache vs. warm cache leads to the same conclusion. "git grep --threads=8 ... HEAD" might still be a win on slow disks or NFS, though.

-Peff

René Scharfe wrote:

[...]

It would be more consistent to stick to the pack.threads convention where 0 means "all of my cores", so to disable threading the user would set the number of threads to 1. Or were you trying to measure the contention between the worker thread and the add_work() thread?

Am 07.12.2011 09:12, schrieb Thomas Rast:

Yes, indeed, the cost for the threading overhead does interest me. The documentation should perhaps mention --no-threads explicitly to avoid confusion.

Currently there is no way to specify "as many threads as there are cores" here. Previous measurements indicated that it wasn't too useful, however, because I/O parallelism was beneficial even for machines with less than eight cores and more threads didn't pay off.

René

rene.scharfe@lsrfire.ath.cx wrote on Wed, 07 Dec 2011 18:00 +0100:

Right. Even for single CPU machines this is true, so the nr_threads calculation above should still use all 8 THREADS regardless of the number of online_cpus().

		-- Pete

Am 10.12.2011 14:13, schrieb Pete Wyckoff:

That makes sense. However, in a quick test with a simple regex against a cache-warm Linux repo threading increased the runtime of git grep by 30% on a single-core virtual machine. Let's keep that check until we understand this better..

René

On Tue, Dec 06, 2011 at 11:48:26PM +0100, René Scharfe wrote:

Should this be "if (nr_threads > 1)"?

As a user, I would do:

  git grep --threads=1 ...

if I wanted a single-threaded process. Instead, we actually spawn a sub-thread and do all of the locking, which has a measurable cost:

  $ time git grep --threads=0 SIMPLE HEAD >/dev/null
  real    0m2.994s
  user    0m2.932s
  sys     0m0.060s

  $ time git grep --threads=1 SIMPLE HEAD >/dev/null
  real    0m3.407s
  user    0m3.392s
  sys     0m0.140s

Should --threads=1 be equivalent to --threads=0?

-Peff

Am 07.12.2011 05:24, schrieb Jeff King:

Yes, the difference is measurable, and that's exactly how I like it to be. :) A user can turn off threading with --threads=0 or (more intuitively) --no-threads. And we can quantify the overhead.

We can do that if there's another way to calculate this difference, or if it is not useful to know. I find your results interesting at least, though. :)

René

On Wed, Dec 07, 2011 at 05:52:10PM +0100, René Scharfe wrote:

That seems acceptable to me if --threads is for speed-testing, but a horrible interface if it is meant for end users who just want git to be fast.

-Peff

René Scharfe wrote:

Sounds good, though in the end we would also want to have a config variable for the poor OS X users who have to tune their threads *down*... :-)

Am 07.12.2011 09:11, schrieb Thomas Rast:

We could set different defaults for different platforms..

René

On Fri, Dec 2, 2011 at 14:07, Thomas Rast <trast@student.ethz.ch> wrote:

Why does git-grep even need to keep a mutex to call read_sha1_file()? It's inherently a read-only operation isn't it? If the lock is needed because data is being shared between threads in sha1_file.c shouldn't we tackle that instead of completely disabling threading?

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

The problem is that all sorts of data is shared.  See

  http://thread.gmane.org/gmane.comp.version-control.git/186618

But I need to go through it again, there are some races and double locks in the posted version.

2011/12/23 Thomas Rast <trast@student.ethz.ch>:

I mentioned this on IRC, but I thought I'd bring it up here too.

Is the expensive part of git-grep all the setup work, or the actual traversal and searching? I'm guessing it's the latter.

In that case an easy way to do git-grep in parallel would be to simply spawn multiple sub-processes, e.g. if we had 1000 files and 4 cores:

 1. Split the 1000 into 4 parts 250 each.
 2. Spawn 4 processes as: git grep <pattern> -- <250 files>
 3. Aggregate all of the results in the parent process

On Sat, Dec 24, 2011 at 02:39:11AM +0100, Ævar Arnfjörð Bjarmason wrote:

That's an interesting idea. The expense of the traversal and searching depends on two things:

  - how complex is your regex?

  - are you reading from objects (which need zlib inflated) or disk?

But you should be able to approximate it by compiling with NO_PTHREADS and doing (assuming you have GNU xargs):

  # grep in working tree
  git ls-files | xargs -P 8 git grep "$re" --

  # grep tree-ish
  git ls-tree -r --name-only $tree | xargs -P 8 git grep "$re" $tree --

I tried to get some timings for this, but ran across some quite surprising results. Here's a simple grep of the linux-2.6 working tree, using a single-threaded grep:

  $ time git grep SIMPLE >/dev/null
  real    0m0.439s
  user    0m0.272s
  sys     0m0.160s

and then the same thing, via xargs, without even turning on parallelization. This should give us a measurement of the overhead for going through xargs at all. We'd expect it to be slower, but not too much so:

  $ time git ls-files | xargs git grep SIMPLE -- >/dev/null
  real    0m11.989s
  user    0m11.769s
  sys     0m0.268s

Twenty-five times slower! Running 'perf' reports the culprit as pathspec matching:

  +  63.23%    git  git                 [.] match_pathspec_depth
  +  28.60%    git  libc-2.13.so        [.] __strncmp_sse42
  +   2.22%    git  git                 [.] strncmp@plt
  +   1.67%    git  git                 [.] kwsexec

where the strncmps are called as part of match_pathspec_depth. So over 90% of the CPU time is spent on matching the pathspecs, compared to less than 2% actually grepping.

Which really makes me wonder if our pathspec matching could stand to be faster. True, giving a bunch of single files is the least efficient way to use pathspecs, but that's pretty amazingly slow.

The case where we would most expect the setup cost to be drowned out is using a more complex regex, grepping tree objects. There we have a baseline of:

  $ time git grep 'a.*c' HEAD >/dev/null
  real    0m5.684s
  user    0m5.472s
  sys     0m0.196s

  $ time git ls-tree --name-only -r HEAD |
      xargs git grep 'a.*c' HEAD -- >/dev/null
  real    0m10.906s
  user    0m10.725s
  sys     0m0.240s

Here, we still almost double our time. It looks like we don't use the same pathspec matching code in this case. But we do waste a lot of extra time zlib-inflating the trees in "ls-tree", only to do it separately in "grep".

Doing it in parallel yields:

  $ time git ls-tree --name-only -r HEAD |
      xargs -n 4000 -P 8 git grep 'a.*c' HEAD -- >/dev/null
  real    0m3.573s
  user    0m21.885s
  sys     0m0.400s

So that does at least yield a real speedup, albeit only by about half, despite using over six times as much CPU (though my numbers are skewed somewhat, as this is a quad i7 with hyperthreading and turbo boost).

-Peff

On Sat, Dec 24, 2011 at 2:07 PM, Jeff King <peff@peff.net> wrote:

We could eliminate get_pathspec_depth() in grep_directory() when read_directory() learns to filter path properly using (and at the cost of) tree_entry_interesting(). The latter function has more optimizaions built in and should be faster than the former. This is a good test case for my read_directory() rewrite. Thanks.

get_pathspec_depth() can still use some optimizations though for grep_cache() case.

(Sorry I replied without reading though the mail)

On Sat, Dec 24, 2011 at 2:07 PM, Jeff King <peff@peff.net> wrote:

I assume this is gree_tree(), we have another form of pathspec matching here: tree_entry_interesting() and it's still a bunch of strcmp inside. Does strcmp show up in perf report?

On Sat, Dec 24, 2011 at 05:55:14PM +0700, Nguyen Thai Ngoc Duy wrote:

Yes, but not nearly as high. The top of the report is:

  +  32.16%    git  libc-2.13.so        [.] re_search_internal
  +  17.82%    git  libz.so.1.2.3.4     [.] 0xe986
  +   7.81%    git  git                 [.] look_ahead
  +   6.24%    git  libc-2.13.so        [.] __strncmp_sse42
  +   4.08%    git  git                 [.] tree_entry_interesting
  +   3.27%    git  git                 [.] end_of_line
  +   2.63%    git  libz.so.1.2.3.4     [.] adler32
  +   1.93%    git  libz.so.1.2.3.4     [.] inflate

where the strncmps are from[1]:

  -   6.24%    git  libc-2.13.so        [.] __strncmp_sse42
     - __strncmp_sse42
        + 80.92% grep_tree
        + 19.08% tree_entry_interesting

So we're spending maybe 10% of our time on pathspecs, but most of it is going to zlib and the actual regex search.

-Peff

[1] Note that this is with -O2, so some of that is from inlined calls.

On Sat, Dec 24, 2011 at 2:07 PM, Jeff King <peff@peff.net> wrote:

Or you could pass blob SHA-1 to git grep to avoid reinflating trees

$ time git ls-tree -r HEAD|cut -c 13-52|xargs git grep 'a.*c' >/dev/null

Doing it in parallel does not seem to save time for me though.

On Fri, Dec 02, 2011 at 02:07:45PM +0100, Thomas Rast wrote:

Wow, that's horrible. Leaving aside the parallelism, it's just terrible that reading from the cache is 20 times slower than the worktree. I get similar results on my quad-core machine.

A quick perf run shows most of the time is spent inflating objects. The diff code has a sneaky trick to re-use worktree files when we know they are stat-clean (in diff's case it is to avoid writing a tempfile). I wonder if we should use the same trick here.

It would hurt the cold cache case, though, as the compressed versions require fewer disk accesses, of course.

-Peff

PS I suspect your timings are somewhat affected by the simplicity of the
   regex you are asking for. The time to inflate the blobs dominates,
   because the search is just a memmem(). On my quad-core w/
   hyperthreading (i.e., 8 apparent cores):

   [no caching, simple regex; we get some parallelism, but the regex
    task is just not that intensive]
   $ /usr/bin/time git grep INITRAMFS_ROOT_UID >/dev/null
   0.42user 0.45system 0:00.15elapsed 578%CPU

   [no caching, harder regex; we get much higher CPU utilization]
   $ /usr/bin/time git grep 'a.*b' >/dev/null
   14.68user 0.50system 0:02.00elapsed 758%CPU

   [with caching, simple regex; we get almost _no_ parallelism because
    all of our time is spent deflating under a lock, and the regex task
    takes very little time]
   $ /usr/bin/time git grep --cached INITRAMFS_ROOT_UID >/dev/null
   7.64user 0.41system 0:07.61elapsed 105%CPU

   [with caching, harder regex; not as much parallelism as we hoped for,
    but still much more than before. Because there is actually work to
    parallelize in the regex]
   $ /usr/bin/time git grep --cached 'a.*b' >/dev/null
   23.46user 0.47system 0:08.42elapsed 284%CPU

   So I think there is value in parallelizing even --cached greps. But
   we could do so much better if blob inflation could be done in
   parallel.

Jeff King wrote:

I just found out that on Linux, there's mincore() that can tell us (racily, but who cares) whether a given file mapping is in memory. If you would like to try it, see the source at the end, but I'm getting things such as

  # in a random collection of files, none of which I have accessed lately
  $ ls -l
  -rw-r--r-- 1 thomas users    116534 Jul  4  2010 IMG_4884.JPG
  -rw-r--r-- 1 thomas users   7278081 Aug 25  2010 remoteserverrepo.zip
  $ ./mincore IMG_4884.JPG 
  00000000000000000000000000000
  $ cat IMG_4884.JPG > /dev/null 
  $ ./mincore IMG_4884.JPG 
  11111111111111111111111111111
  $ ./mincore remoteserverrepo.zip 
  0000000000000000000000[...]
  $ head -10 remoteserverrepo.zip >/dev/null
  $ ./mincore remoteserverrepo.zip 
  1111000000000000000000[...]

So that looks fairly promising, and the order would then be:

- if stat-clean, and we have mincore(), and it tells us we can do it
  cheaply: grab file from tree

- if it's a loose object: decompress it

- if stat-clean: grab file from tree

- access packs as usual

Ok, I see, I missed that part. Perhaps the heuristic should then be "if the regex boils down to memmem, disable threading", but let's see what loose object decompression in parallel can give us.

---- 8< ---- mincore.c ---- 8< ---- #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <sys/mman.h> #include <fcntl.h>

void die(const char *s)
{
	perror(s);
	exit(1);
}

int main (int argc, char *argv[])
{
	void *mem;
	size_t len;
	struct stat st;
	int fd;
	unsigned char *vec;
	int vsize;
	int i;
	size_t page = sysconf(_SC_PAGESIZE);

	if (argc != 2) {
		fprintf(stderr, "usage: %s <file>\n", argv[0]);
		exit(2);
	}

	fd = open(argv[1], O_RDONLY);
	if (fd == -1)
		die("open failed");
	if (fstat(fd, &st) == -1)
		die("fstat failed");
	mem = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
	if (mem == (void*) -1)
		die("mmap failed");

	vsize = (st.st_size+page-1)/page;
	vec = malloc(vsize);
	if (!vec)
		die("malloc failed");
	if (mincore(mem, st.st_size, vec) == -1)
		die("mincore failed");
	for (i = 0; i < vsize; i++)
		printf("%d", (int) vec[i]);
	printf("\n");
	return 0;
}

Thomas Rast wrote:

[...]

Just a small note, I tried two things:

* the simpler option of grabbing a loose object if it exists and is
  mincore() turns out to massively slow down 'git log HEAD', probably
  because only very few of these objects are loose in the first place

* doing this only under grep's use_threads, and dropping the lock
  around unpack_sha1_file() [i.e., zlib decompression] still results
  in a git-grep that is slower than without this, though not much

So no improvement here. Will have to look into the worktree trick though.

On Mon, Dec 05, 2011 at 10:38:16AM +0100, Thomas Rast wrote:

Neat, I didn't know about mincore.

I don't think your third one makes sense. If the working tree file isn't stat clean, then either:

  1. the pack file is in cache, and it's way faster than faulting in the
     working tree file from disk

  2. the pack file is not in cache, and it's a toss-up whether it is
     faster to fault in the smaller compressed pack-file version and
     uncompress it, or to fault in the larger on-disk version. The
     exact result will depend on the ratio of CPU to disk speed, the
     quality of your filesystem, and the size and contents of your file.

     And possibly on the exact delta chains you have. Though this
     optimization only happens when the file is in the index, which
     usually means it's recent, which means it will tend to be at the
     head of the delta chain.

So it probably just makes sense to grab the working tree file only if mincore() tells us we have all (or most) of it, and otherwise go to the packfile.

Yeah. I'd really rather have parallel object decompression than some complex Linux-only mincore optimization (even though that optimization _could_ yield extra savings on top of properly threading, if the blob retrieval is threaded, I think I'll care less about how much CPU time it takes).

-Peff

Hello Thomas,

Thanks for the work and the great info. Some of the numbers are quite surprising.

I do, indeed, have a machine with more cores, but I have been either busy with out-of-town guests or generally plain lazy in the last couple of weeks. I intend to set aside some time to do some benchmarking this weekend.

I'll let you know what I find.

Cheers,
  -Eric