[RFC \ WISH] Add -o option to git-rev-list

[RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

I have done some tests about reading git-rev-list output with
different IPC facilities:

- Native Qt QProcess socket based IPC

- pipe based: popen() and fread()

- redirecting git-rev-list to a file (under tmpfs) and 'block reading'
back the file: read() under Qt QFile class. The file, always in
memory, is deleted at the end of loading.


I have tested with different block sizes and different CPU speed on
linux and git trees.

The averaged results on linux tree (about 30MB of data) and CPU set at
1.2GHz are:

- QProcess 6734ms

- pipe and fread() with 64KB blocks 4832ms (38% faster then QProcess)

- temporary file and read() with 64KB blocks 4321ms (10% faster then pipe)


I have not enough knowledge to understand why temporary file is faster
then pipe. My guess is, after reading some docs around, fread() uses a
C standard I/O buffer, while read() is unbuffered.

To make git-rev-list writing a temporary file I create and run a
script more or less like:

git rev-list --header --boundary --parents --topo-order HEAD  >
/tmp/qgit_135902672.txt

There is also some additional kludge to get git-rev-list pid, so to
use in case of a cancel request arrives while loading.


So my request is if it is possible to make git-rev-list write
_directly_ to a file, without shell redirection, I would ask if it is
possible:

- Add a -o, --output option to git-rev-list to specify output file
instead of stdout

- Use an unbuffered binary block write to be as fastest as possible

- Do *not* flush ever the file, it's only a waste under this scenario.


This will let me to avoid the shell launching crap and probably gain
also some more speed.

I understand this could be not exactly a top priority feature for git
people, but I would really like to get the best possible interface
with the plumbing git and the -o options is also a very common one.

Thanks
Marco

P.S: On another thread I explained why I see problematic linking
directly against libgit.a
I rewrite here for completeness:

> I've looked again to Shawn idea (and code) of linking qgit
> against libgit.a but I found these two difficult points:
>
> - traverse_commit_list(&revs, show_commit, show_object) is blocking,
> i.e. the GUI will stop responding for few seconds while traversing the
> list. This is easily and transparently solved by the OS scheduler if
> an external process is used for git-rev-list. To solve this in qgit I
> have two ways: 1) call QEventLoop() once in a while from inside
> show_commit()/ show_object() to process pending events  2) Use a
> separate thread (QThread class). The first idea is not nice, the
> second opens a whole a new set of problems and it's a big amount of
> not trivial new code to add.
>
> -  traverse_commit_list() having an internal state it's not
> re-entrant. git-rev-list it's used to load main view data but also
> file history in another tab, and the two calls _could_ be ran
> concurrently. With external process I simply run two instances of
> DataLoader class and consequently two external git-rev-list processes,
> but If I link against libgit.a that would be a big problem.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Alex Riesen]

Marco Costalba, Sun, Dec 10, 2006 12:38:42 +0100:
> So my request is if it is possible to make git-rev-list write
> _directly_ to a file, without shell redirection, I would ask if it is
> possible:

Well, it is usually possible to redirect stdout directly into a file
(see dup2). "Usually", unless you want windows which as always has
it's own stupid way of doing simple things. Nevertheless, it's
possible to do it without ever touching rev-list.

> I understand this could be not exactly a top priority feature for git
> people, but I would really like to get the best possible interface
> with the plumbing git and the -o options is also a very common one.

Sadly, you're right. Almost every command-line program got the option.
What education could have caused this, I wonder...

> P.S: On another thread I explained why I see problematic linking
> directly against libgit.a

It still is the fastest you can get.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Sun, 10 Dec 2006, Marco Costalba wrote:
> 
> The averaged results on linux tree (about 30MB of data) and CPU set at
> 1.2GHz are:
> 
> - QProcess 6734ms
> 
> - pipe and fread() with 64KB blocks 4832ms (38% faster then QProcess)
> 
> - temporary file and read() with 64KB blocks 4321ms (10% faster then pipe)
> 
> I have not enough knowledge to understand why temporary file is faster
> then pipe. My guess is, after reading some docs around, fread() uses a
> C standard I/O buffer, while read() is unbuffered.

Why don't you use the pipe and standard read()?

Even if you use "popen()" and get a "FILE *" back, you can still do

	int fd = fileno(file);

and use the raw IO capabilities.

The thing is, temporary files can actually be faster under Linux just 
because the Linux page-cache simply kicks ass. But it's not going to be 
_that_ big of a difference, and you need all that crazy "wait for rev-list 
to finish" and the "clean up temp-file on errors" etc crap, so there's no 
way it's a better solution.

If it really is stdio overhead (possibly locking), using "fileno()" and 
the raw unistd.h interfaces is going to avoid it.

(You still need to use "fclose()" to close the struct file afterwards, 
otherwise you'll leak memory, so you shouldn't _forget_ the original 
"struct FILE *", but you don't need to use it for anything else).

Using popen() and pipes also means that if the parent dies, the child will 
get a nice EPIPE on the writing side, which is what you want.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
> Why don't you use the pipe and standard read()?
>
> Even if you use "popen()" and get a "FILE *" back, you can still do
>
>         int fd = fileno(file);
>
> and use the raw IO capabilities.
>
> The thing is, temporary files can actually be faster under Linux just
> because the Linux page-cache simply kicks ass. But it's not going to be
> _that_ big of a difference, and you need all that crazy "wait for rev-list
> to finish" and the "clean up temp-file on errors" etc crap, so there's no
> way it's a better solution.
>

Two things.

- memory use: the next natural step with files is, instead of loading
the file content in memory and *keep it there*, we could load one
chunk at a time, index the chunk and discard. At the end we keep in
memory only indexing info to quickly get to the data when needed, but
the big part of data stay on the file.

- This is probably my ignorance, but experimenting with popen() I
found I could not know *when* git-rev-list ends because both feof()
and ferror() give 0 after a fread() with git-rev-list already defunct.
Not having a reference to the process (it is hidden behind popen() ),
I had to check for 0 bytes read after a successful read (to avoid
racing in case I ask the pipe before the first data it's ready) to
know that job is finished and call pclose().

globs in partial checkout?

[Michael S. Tsirkin]

I'm trying to checkout some files after doing "clone -n".
Should using globs there work? It doesn't:

st@mst-lt:~/scm/wireless-dev$ git checkout master 'include/net/ieee80211*.h'
error: pathspec 'include/net/ieee80211*.h' did not match any file(s) known to
git.
Did you forget to 'git add'?
mst@mst-lt:~/scm/wireless-dev$ git ls-tree master -- include/net/ | grep iee
100644 blob b174ebb277a96668f058e469b0753503c34f164b include/net/ieee80211.h
100644 blob eb476414fd726701d032e9e517751b9d3f7e38df include/net/ieee80211_crypt.h
100644 blob 429b73892a5fc62f91e4a4b05da40859604fa791 include/net/ieee80211_radiotap.h
100644 blob 617b672b1132e7fa3ff5f9c940b1692520dc8483 include/net/ieee80211softmac.h
100644 blob 4ee3ad57283fa3370bd2d1f71cd6ae559b556dbc include/net/ieee80211softmac_wx.h
mst@mst-lt:~/scm/wireless-dev$ git checkout master include/net/ieee80211.h
include/net/ieee80211_crypt.h include/net/ieee80211_radiotap.h
include/net/ieee80211softmac.h include/net/ieee80211softmac_wx.h


-- 

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Sun, 10 Dec 2006, Marco Costalba wrote:
> 
> - memory use: the next natural step with files is, instead of loading
> the file content in memory and *keep it there*, we could load one
> chunk at a time, index the chunk and discard. At the end we keep in
> memory only indexing info to quickly get to the data when needed, but
> the big part of data stay on the file.

Well, that's still just going slower than swapping.

The reason loading things into memory is nice is that:
 - in the common case, you don't need to do anything else.
 - if  the machine is low on memory, it can page things out just about as 
   easily as you could write things to a file anyway.

So don't worry too much about low-memory situations. Yes, there are cases 
where it's better to keep things in files and simply not have a big 
working set AT ALL, but if you keep something in a file and the file data 
is still part of the working set (ie you read it several times, but at the 
beginning and the end), that really isn't any better than having it in 
memory.

So the time to try to optimize memory usage is really only for "streaming 
behaviour" - where you need to touch something only once. Then the best 
option is to actually use a pipe and re-use the memory, but if you have 
file data, you can use things like fadvise(DONTNEED).

> - This is probably my ignorance, but experimenting with popen() I
> found I could not know *when* git-rev-list ends because both feof()
> and ferror() give 0 after a fread() with git-rev-list already defunct.

I suspect you had a bug somewhere. It could be a bug in stdio, but I doubt 
it.

You do realize that the correct way to check "feof()" is only _after_ 
fread() returns 0? 

Stdio ferror/feof is horrible to use corrrectly, and few people get it 
right.  Mostly because it's such a crap interface thanks to being "easy" 
to use and thus hiding all the error handling details on purpose.

Re: globs in partial checkout?

[Linus Torvalds]

On Sun, 10 Dec 2006, Michael S. Tsirkin wrote:
>
> I'm trying to checkout some files after doing "clone -n".
> Should using globs there work? It doesn't:

Not historically at all. "git checkout" needed exact filenames in older 
versions.

However, since about 1.4.4.1 or so, it now does the same filename 
expansion as "git add" etc does, which means that you can give it a 
directory name and it will check out everything under that directory, or 
you can give it a pattern, and it should glob it. But it sounds like you 
may have a slightly older version of git (the pathname matching really is 
fairly recent).

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Sun, 10 Dec 2006, Linus Torvalds wrote:
> 
> So don't worry too much about low-memory situations.

Btw, I should obviously clarify that. You should _always_ worry about 
low-memory situations, but the only real issue is really "working set 
size", not "data in files or in memory".

If the file representation is very dense (like the git pack-files are, for 
example), then it may well make sense to keep the data in a file, just 
because it's smaller there than if you keep it in expanded form in memory.

Also, it's nice to keep stuff in the filesystem rather than in process VM 
memory, because filesystem data that is cached in memory is useful for 
_other_ processes, ie it has a lifetime that is longer than the process 
itself. However, that's obviously only true for long-lived files that are 
shared among processes, it's _not_ true for temporary files.

For temporary files, the memory footprint of a temp-file is usually 
_larger_ than the memory footprint of the same data kept in memory. You 
have things like page-cache alignment, and often the issue of marshalling 
data into ASCII etc. So temp-files are almost never a better solution than 
keeping things in memory (unless you use those temp-files to truly 
_share_ data between processes, ie you do a shared mmap and they can 
re-use the same pages actively in a way they couldn't otherwise).

Re: globs in partial checkout?

[Michael S. Tsirkin]

> However, since about 1.4.4.1 or so, it now does the same filename 
> expansion as "git add" etc does, which means that you can give it a 
> directory name and it will check out everything under that directory, or 
> you can give it a pattern, and it should glob it. But it sounds like you 
> may have a slightly older version of git (the pathname matching really is 
> fairly recent).

Seems like this was post-1.4.4.1. Just updated to 1.4.4.2 and this works for me now,
thanks.

-- 

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>

> data into ASCII etc. So temp-files are almost never a better solution than
> keeping things in memory (unless you use those temp-files to truly
> _share_ data between processes, ie you do a shared mmap and they can
> re-use the same pages actively in a way they couldn't otherwise).
>

Ok. Perhaps I'm doing something wrong but the following code it's
always 10% slower then the temporary file one (4.7s against 4.3s for
linux tree)

bool DataLoader::start(const QStringList& args, const QString& workDir) {

	QDir::setCurrent(workDir);

	_file = popen(args.join(" ").ascii(), "r");
	if (!_file)
		return false;
	
	loadTime.start();
	guiUpdateTimer.start(10, true); // will call on_timeout() in 10ms
	return true;
}

void DataLoader::on_timeout() {

	if (canceling)
		deleteLater();

// 	int fd = fileno(_file);    // read() case

	ssize_t len = 0;
	while (1) {

		QByteArray* ba = new QByteArray(FILE_BLOCK_SIZE); // 64KB

// 		len = read(fd, ba->data(), ba->size());        // read() case

		len = fread(ba->data(), 1, ba->size(), _file); // fread() case
		if (len <= 0) {
			delete ba;
			break;

		} else if (len < (ssize_t)ba->size()) // very rare, 4 out of 40000
on Linux tree
			ba->resize(len);

		loadedBytes += len;
		fh->rowData.append(ba); // fh->rowData it's a pointer's list
		parseSingleBuffer(ba);

		// avoid reading small chunks if data producer is still running
		if (len < FILE_BLOCK_SIZE)
			break;
	}

// 	if (len == 0) {         // read() case
	if (feof(_file)) {      // fread() case
	
		emit loaded(fh, loadedBytes, loadTime.elapsed(), true, "", ""); //
show some stats

		pclose(_file);
		_file = NULL;
		deleteLater();
	} else
		guiUpdateTimer.start(100, true); // next read in 100ms	
}

Uncomment 'read() case' lines and comment out the 'fread case()' ones
and you have a way slooooower code, about 10 times slower!

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/10/06, Marco Costalba <mcostalba@gmail.com> wrote:
> On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
> >
> void DataLoader::on_timeout() {
>
>         if (canceling)
>                 deleteLater();
>

Of course is

	if (canceling) {
		deleteLater();
		return;
	}

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Sun, 10 Dec 2006, Marco Costalba wrote:
> 
> Ok. Perhaps I'm doing something wrong but the following code it's
> always 10% slower then the temporary file one (4.7s against 4.3s for
> linux tree)

Why do you seem to be doing a "new" on every iteration inside the loop?

Also, why do you have that strange FILE_BLOCK_SIZE thing, and in 
particular the "if (len < FILE_BLOCK_SIZE)" check? One thing that pipes vs 
files do is the blocking factor.

Especially with older kernels, I _guarantee_ you that you'll only ever get 
4kB at a time, so because of that "if (len < 64kB) break" thing, the only 
thing you're doing is to make sure things suck performance-wise, and you 
won't be reading the rest of the data until 100ms later.

IOW, your code is written for a file, and makes no sense there either 
(checking "feof(file)" is wrong, since you may well have hit the EOF 
*at*that*time*, but the file may GROW since you are doing it all in the 
background, so you can't rely on feof() anyway).

For a pipe, what you should do is to make sure it's in nonblocking mode, 
and just continue reading until it gets no more. And instead of using a 
timeout, you should use poll() or something to get notified when there is 
more data.

IOW, the reason it's slow is because you're doing the wrong thing.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Sun, 10 Dec 2006, Marco Costalba wrote:
> >
> > Ok. Perhaps I'm doing something wrong but the following code it's
> > always 10% slower then the temporary file one (4.7s against 4.3s for
> > linux tree)
>
> Why do you seem to be doing a "new" on every iteration inside the loop?
>

Becuase it's there where I store the file content.

Function parseSingleBuffer(ba) does only the indexing. But the file
content is stored in QByteArray objects (little wrappers around a
const char* []). So the fread() in the byte array object is the _only_
data copy operation in whole qgit.


> Also, why do you have that strange FILE_BLOCK_SIZE thing, and in
> particular the "if (len < FILE_BLOCK_SIZE)" check? One thing that pipes vs
> files do is the blocking factor.
>
> Especially with older kernels, I _guarantee_ you that you'll only ever get
> 4kB at a time, so because of that "if (len < 64kB) break" thing, the only
> thing you're doing is to make sure things suck performance-wise, and you
> won't be reading the rest of the data until 100ms later.
>

I consistently have len == 65536 bytes until the last fread() where
it's less. See below run against qgit own repository with 'len'
printed inside while loop.

$ ./qgit
Found GNU source-highlight 2.5
len is <65536>
len is <65536>
len is <65536>
len is <65536>
len is <65536>
len is <65536>
len is <65536>
len is <54479>
bash-3.1$

> IOW, your code is written for a file, and makes no sense there either
> (checking "feof(file)" is wrong, since you may well have hit the EOF
> *at*that*time*, but the file may GROW since you are doing it all in the
> background, so you can't rely on feof() anyway).
>

Yes. feof() it's difficult to handle correctly.

> For a pipe, what you should do is to make sure it's in nonblocking mode,
> and just continue reading until it gets no more. And instead of using a
> timeout, you should use poll() or something to get notified when there is
> more data.
>

How can open in nonblocking mode with popen() ?

FILE *popen(const char *command, const char *type);


> IOW, the reason it's slow is because you're doing the wrong thing.
>

That's for sure :-)  My problem is to guess what's is wrong.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Sun, 10 Dec 2006, Marco Costalba wrote:
> 
> I consistently have len == 65536 bytes until the last fread() where
> it's less.

That's because fread() will block until it gets all data. Did you actually 
ever try this with a uncached tree and did you compare what you got with a 
plain "read()". 

On older kernels, I guarantee that you get 4kB at a time for reads, even 
for a blocking pipe. Because we have bigger pipe buffers these days, it 
_may_ return 64kB at a time every time, but only if the writer is much 
faster than the reader.

Based on the fact that you say that "read()" was ten times slower than 
fread(), I very much suspect you got 4kB at a time, and then slept 100ms 
each time or something.

Anyway, you should seriously also check the case when "git rev-list" is 
slow because you have cold caches and unpacked objects. You can't wait for 
it to synchronously write a thousand lines or so - that could take 
seconds.

> How can open in nonblocking mode with popen() ?
> 
> FILE *popen(const char *command, const char *type);

something like

	fcntl(fileno(file), F_SETFL, O_NONBLOCK);

will do it, and then your loop should look something like

	for (;;) {
		int count = read(fileno(file), buf, BUFSIZE);
		if (!count) {
			/* All done, no more to read */
			return 0;
		}
		if (count < 0) {
			if (errno == EAGAIN)
				break;
			if (errno == EINTR)
				continue;
			/* Anything else is fatal - report error */
			return -1;
		}
		... handle 'count' new bytes here ...
	}
	.. this is the EAGAIN case ..
	either set polling on the file descriptor, or use a
	timer here yo get back to this loop eventually.

looks about right.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
> looks about right.
>

Yes it's right. Thanks!

But it's still slow. Almost one second (985ms) to read the little qgit repo:

$ ./qgit HEAD
Found GNU source-highlight 2.5
count is <-1>
count is <60169>
count is <-1>
count is <60505>
count is <-1>
count is <61462>
count is <-1>
count is <61911>
count is <-1>
count is <61392>
count is <-1>
count is <61880>
count is <-1>
count is <62009>
count is <-1>
count is <62549>
count is <-1>
count is <21354>
count is <0>
$

As a compare the temporary file version needs a mere 105ms (1030 revs).

This is the code under test:

bool DataLoader::start(const QStringList& args, const QString& workDir) {

	QDir::setCurrent(workDir);
	_file = popen(args.join(" ").ascii(), "r");
	if (!_file)
		return false;

	fcntl(fileno(_file), F_SETFL, O_NONBLOCK);
	
	loadTime.start();
	guiUpdateTimer.start(10, true);
	return true;
}

void DataLoader::on_timeout() {

	if (canceling) {
		deleteLater();
		return;
	}

	int count;
	for (;;) {

		QByteArray* ba = new QByteArray(FILE_BLOCK_SIZE); // 64KB

		// this is the ONLY deep copy involved in the whole loading
		count = read(fileno(_file), ba->data(), ba->size());

		dbg(count); // DEBUG print

		if (count == 0) {
			/* All done, no more to read */
			delete ba;
			break;
		}
		if (count < 0) {
			delete ba;
			if (errno == EAGAIN)
				break;
			if (errno == EINTR)
				continue;

                       /* Anything else is fatal - report error */
                       dbg("Fatal error");
                       on_cancel();
                       deleteLater();
                       return;
		}
		if (count < (int)ba->size()) // very rare
			ba->resize(count);

		loadedBytes += count;
		fh->rowData.append(ba);
		parseSingleBuffer(*ba);
	}

	if (count == 0) {
		emit loaded(fh, loadedBytes, loadTime.elapsed(), true, "", "");
		pclose(_file);
		_file = NULL;
		deleteLater();
	} else
		guiUpdateTimer.start(100, true);

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Marco Costalba wrote:

> 
> But it's still slow. Almost one second (985ms) to read the little qgit repo:

Right. Because every time you sleep, you sleep for 100 ms.

That's why I was saying that you need to add polling to the thing. I don't 
know what the QT interfaces to asynchronous polling file descriptors are, 
but as long as you just blindly wait for 100ms whenever you run out of 
data, things will always suck.

Using "fread()" hid this problem, because the thing would block in 
fread(), and thus you'd nor see as many of these events.

> As a compare the temporary file version needs a mere 105ms (1030 revs).

How about you just compare something simpler:

	git-rev-list | cat > /dev/null

vs 

	git-rev-list > tmpfile ; cat tmpfile > /dev/null

and see which one works better.

If the pipe works better, that means that it's your code that is buggy and 
broken.

Which gets us back to the basic issue: you're asking for a bad interface.

This is your problem:

> 		guiUpdateTimer.start(100, true);

rather than just blindly starting a timer, you should ask it to wait until 
more data is available.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Linus Torvalds <torvalds@osdl.org> wrote:

>
> How about you just compare something simpler:
>
>         git-rev-list | cat > /dev/null
>
> vs
>
>         git-rev-list > tmpfile ; cat tmpfile > /dev/null
>
> and see which one works better.
>

These are tipical values (warm cache):

  $ time git rev-list --header --boundary --parents --topo-order HEAD  /dev/null
3.04user 0.05system 0:03.09elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+10141minor)pagefaults 0swaps

$ time git rev-list --header --boundary --parents --topo-order HEAD |
cat > /dev/null
3.67user 0.36system 0:04.29elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+18033minor)pagefaults 0swaps

$ time git rev-list --header --boundary --parents --topo-order HEAD >
/tmp/tmp.txt; cat /tmp/tmp.txt > /dev/null
3.44user 0.28system 0:03.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+18033minor)pagefaults 0swaps

For some reason the CPU *never* goes up 93% with pipe (while it's easy
in the other two cases) and I repeated that test at lest 10 times
consecutively. Is it perhaps the signature of some blocking around? Or
too much high frequency of receiver's read call (see below) ?

>
> This is your problem:
>
> >               guiUpdateTimer.start(100, true);
>
> rather than just blindly starting a timer, you should ask it to wait until
> more data is available.
>

OK. I just don't understand how after waiting 100ms I get only 60KB
and stay in the loop only one cycle instead of reading, for many
cycles, much more then 60KB and then wait another 100ms and found
another big (about 1MB) amount of data ready to be read as with the
file case.

Perhaps the pipe buffers are small and block the writer when full. In
the file case when I come back in the loop after 100ms I found _a lot_
of data to be read and I stay in the loop for much more then 1 cycle
before to wait again 100ms.

On the other hand, going to read each say less then 10ms is exactly
what QProcess (socket based) was doing and I ended up with my read
function being called at furious pace slowing down everything.
Experimenting with QProcess I found that, for performance reasons,
it's better to read big chunks few times then small chunks a lot of
times.

  Marco

P.S: 30MB for 64KB each chunk it's 468, in 3.67s it's 1 call each
7.8ms. If the pipe calls the receiver for data ready after each 4KB
(old kernels) then we should have 7.500 calls. Impossible to read in
3.67s, it would be a theoretical 1 call each 0.48ms average.

So IMHO bigger buffers for each read call could be the way to get

Re: [RFC \ WISH] Add -o option to git-rev-list

[Josef Weidendorfer]

On Monday 11 December 2006 01:15, Marco Costalba wrote:
> 		guiUpdateTimer.start(100, true);

What is the result with	"guiUpdateTimer.start(0, true);" ?
There is no need to put in any time interval at all, because
the timeout is a normal event which will be queued in the GUI
event queue.

If there were X events in the mean time, they are queued and handled
before your timeOut function is called again. So the GUI will be
responsive, even if you have a 0 ms timer. 

Re: [RFC \ WISH] Add -o option to git-rev-list

[Alex Riesen]

On 12/11/06, Marco Costalba <mcostalba@gmail.com> wrote:
>   $ time git rev-list --header --boundary --parents --topo-order HEAD
> /dev/null
> 3.04user 0.05system 0:03.09elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+10141minor)pagefaults 0swaps

here you filtered output of git-rev-list by /dev/null, which makes no sense

> $ time git rev-list --header --boundary --parents --topo-order HEAD >
> /tmp/tmp.txt; cat /tmp/tmp.txt > /dev/null
> 3.44user 0.28system 0:03.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+18033minor)pagefaults 0swaps

should be: time { git-rev-list >/tmp/tmp; cat /tmp/tmp >/dev/null; }

Re: [RFC \ WISH] Add -o option to git-rev-list

[Andreas Ericsson]

Marco Costalba wrote:
> On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>>
>> Why don't you use the pipe and standard read()?
>>
>> Even if you use "popen()" and get a "FILE *" back, you can still do
>>
>>         int fd = fileno(file);
>>
>> and use the raw IO capabilities.
>>
>> The thing is, temporary files can actually be faster under Linux just
>> because the Linux page-cache simply kicks ass. But it's not going to be
>> _that_ big of a difference, and you need all that crazy "wait for 
>> rev-list
>> to finish" and the "clean up temp-file on errors" etc crap, so there's no
>> way it's a better solution.
>>
> 
> Two things.
> 
> - memory use: the next natural step with files is, instead of loading
> the file content in memory and *keep it there*, we could load one
> chunk at a time, index the chunk and discard. At the end we keep in
> memory only indexing info to quickly get to the data when needed, but
> the big part of data stay on the file.
> 

memory usage vs speed tradeoff. Since qgit is a pure user-app, I think 
it's safe to opt for the memory hungry option. If people run it on too 
lowbie hardware they'll just have to make do with other ways of viewing 
the DAG or shutting down some other programs.

> - This is probably my ignorance, but experimenting with popen() I
> found I could not know *when* git-rev-list ends because both feof()
> and ferror() give 0 after a fread() with git-rev-list already defunct.
> Not having a reference to the process (it is hidden behind popen() ),
> I had to check for 0 bytes read after a successful read (to avoid
> racing in case I ask the pipe before the first data it's ready) to
> know that job is finished and call pclose().
> 

(coding in MUA, so highly untested)

pid_t runcmd(const char **argv, const char **env, int *out, *int err)
{
	int pid;

	pipe(out);
	pipe(err);

	pid = fork();


	/* parent returns upon forking */
	if (pid) {
		/* close childs file-descriptors in our address space */
		close(out[0]);
		close(err[0]);
		return pid;
	}

	/* child */
	/* close parents file-descriptors */
	close(out[0]);
	close(err[0]);

	/* stdout and stderr writes to childs ends of the pipes */
	dup2(out[1], STDOUT_FILENO);
	dup2(err[1], STDERR_FILENO);
	execve(argv[0], argv, NULL);

	_exit(0); /* not reached unless execve() failed */
}

The caller can now read out[0] and err[0] as regular file-descriptors 
and has the pid of the child-process in the return value. The parent 
receives SIGCHILD if the child exits, the child receives EPIPE when 
writing if the parent crashes.

In a prudent implementation, the parent should waitpid(pid_t pid, int 
*status, WNOHANG) for the child every once in a while to collect its 
exit status gracefully.

Do some experimenting and I'm sure you'll find something suitable for you.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:
> On Monday 11 December 2006 01:15, Marco Costalba wrote:
> >               guiUpdateTimer.start(100, true);
>
> What is the result with "guiUpdateTimer.start(0, true);" ?
> There is no need to put in any time interval at all, because
> the timeout is a normal event which will be queued in the GUI
> event queue.
>
> If there were X events in the mean time, they are queued and handled
> before your timeOut function is called again. So the GUI will be
> responsive, even if you have a 0 ms timer.
>

IOW you suggest to use a brute force polling of the pipe.

I'will try this, just to test the pipe, not the application because I
would really need to read data in big chunks.

Data read from pipe/file or something else is read in an array (char*
[]) and do not touched anymore, no more copies are made. For every
read a new array is allocated on the heap.

With chunks of 64KB, because each rev descriptions is about few
hundered bytes only few revs (about 1% with current linux tree) fall
at the boundary of the chunk, half in one and the rest in the next.
This boundary revs require a special handling that at the end involves
an additional copy.

If I get from the pipe very small data (few KB) probably it would be
better to read always in a local array of fixed size and then copy to
final destination in memory. But this imply that all the data work
copy is duplicated: instead of 30MB of data we'll going to move 60MB
(linux tree)

With big chunks of 64KB only about 1% of data (revs that fall at the
array boundary) is duplicated.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Andreas Ericsson <ae@op5.se> wrote:
> Marco Costalba wrote:
> > On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
> >>
> >> Why don't you use the pipe and standard read()?
> >>
> >> Even if you use "popen()" and get a "FILE *" back, you can still do
> >>
> >>         int fd = fileno(file);
> >>
> >> and use the raw IO capabilities.
> >>
> >> The thing is, temporary files can actually be faster under Linux just
> >> because the Linux page-cache simply kicks ass. But it's not going to be
> >> _that_ big of a difference, and you need all that crazy "wait for
> >> rev-list
> >> to finish" and the "clean up temp-file on errors" etc crap, so there's no
> >> way it's a better solution.
> >>
> >
> > Two things.
> >
> > - memory use: the next natural step with files is, instead of loading
> > the file content in memory and *keep it there*, we could load one
> > chunk at a time, index the chunk and discard. At the end we keep in
> > memory only indexing info to quickly get to the data when needed, but
> > the big part of data stay on the file.
> >
>
> memory usage vs speed tradeoff. Since qgit is a pure user-app, I think
> it's safe to opt for the memory hungry option. If people run it on too
> lowbie hardware they'll just have to make do with other ways of viewing
> the DAG or shutting down some other programs.
>
> > - This is probably my ignorance, but experimenting with popen() I
> > found I could not know *when* git-rev-list ends because both feof()
> > and ferror() give 0 after a fread() with git-rev-list already defunct.
> > Not having a reference to the process (it is hidden behind popen() ),
> > I had to check for 0 bytes read after a successful read (to avoid
> > racing in case I ask the pipe before the first data it's ready) to
> > know that job is finished and call pclose().
> >
>
> (coding in MUA, so highly untested)
>

Thanks Andreas, I will do some tests with your code. But at first
sight I fail to see (I'm not an expert on this tough ;-)  ) where is
the difference from using popen() and fileno() to get the file
descriptors.

Thanks

Re: [RFC \ WISH] Add -o option to git-rev-list

[Josef Weidendorfer]

On Monday 11 December 2006 13:52, Marco Costalba wrote:
> On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:
> > On Monday 11 December 2006 01:15, Marco Costalba wrote:
> > >               guiUpdateTimer.start(100, true);
> >
> > What is the result with "guiUpdateTimer.start(0, true);" ?
> ...
> IOW you suggest to use a brute force polling of the pipe.

Ah, yes. That is probably not what you want.

Why did you introduce the timer at all? What was the problem
with QProcess and handling its signal "data available" ?

If you do

	git-rev-list | cat > /dev/null

the consuming "cat" will do a blocking read, and this should have
the same property "handle data as fast as possible when they
come available" as QProcess with handling the data in
the handler of QProcess' signal "data available".

If it is about postprocessing the small data chunks you get (and the
double copy in memory), I do not think this is a problem: a machine
noadays usually should handle 1 GB/s bandwidth to memory. You probably
are loosing more with your 100ms timer.

Or am I missing something?

Re: [RFC \ WISH] Add -o option to git-rev-list

[Andreas Ericsson]

Marco Costalba wrote:
> On 12/11/06, Andreas Ericsson <ae@op5.se> wrote:
>> Marco Costalba wrote:
>> > On 12/10/06, Linus Torvalds <torvalds@osdl.org> wrote:
>> >>
>> >> Why don't you use the pipe and standard read()?
>> >>
>> >> Even if you use "popen()" and get a "FILE *" back, you can still do
>> >>
>> >>         int fd = fileno(file);
>> >>
>> >> and use the raw IO capabilities.
>> >>
>> >> The thing is, temporary files can actually be faster under Linux just
>> >> because the Linux page-cache simply kicks ass. But it's not going 
>> to be
>> >> _that_ big of a difference, and you need all that crazy "wait for
>> >> rev-list
>> >> to finish" and the "clean up temp-file on errors" etc crap, so 
>> there's no
>> >> way it's a better solution.
>> >>
>> >
>> > Two things.
>> >
>> > - memory use: the next natural step with files is, instead of loading
>> > the file content in memory and *keep it there*, we could load one
>> > chunk at a time, index the chunk and discard. At the end we keep in
>> > memory only indexing info to quickly get to the data when needed, but
>> > the big part of data stay on the file.
>> >
>>
>> memory usage vs speed tradeoff. Since qgit is a pure user-app, I think
>> it's safe to opt for the memory hungry option. If people run it on too
>> lowbie hardware they'll just have to make do with other ways of viewing
>> the DAG or shutting down some other programs.
>>
>> > - This is probably my ignorance, but experimenting with popen() I
>> > found I could not know *when* git-rev-list ends because both feof()
>> > and ferror() give 0 after a fread() with git-rev-list already defunct.
>> > Not having a reference to the process (it is hidden behind popen() ),
>> > I had to check for 0 bytes read after a successful read (to avoid
>> > racing in case I ask the pipe before the first data it's ready) to
>> > know that job is finished and call pclose().
>> >
>>
>> (coding in MUA, so highly untested)
>>
> 
> Thanks Andreas, I will do some tests with your code. But at first
> sight I fail to see (I'm not an expert on this tough ;-)  ) where is
> the difference from using popen() and fileno() to get the file
> descriptors.
> 

read() vs fread(), so no libc buffers. When I did comparisons with this 
(a long time ago, I don't have the test-program around) in style of

	read(out[0], buf, sizeof(buf));
	write(fileno(stdout), buf, sizeof(buf));

with a command line like this;

	cat any-file | test-program > /dev/null

I saw a static ~10ms increase in execution time compared to

	cat any-file > /dev/null

regardless of the size of "any-file", so I assume this overhead comes 
from the extra fork(), which you'll never get rid of unless you use 
libgit.a.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Marco Costalba wrote:
> 
> These are tipical values (warm cache):
> 
> $ time git rev-list --header --boundary --parents --topo-order HEAD | cat > /dev/null
> 3.67user 0.36system 0:04.29elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+18033minor)pagefaults 0swaps

That's not timing what I asked. That's just timing the "git-rev-list". You 
need to time the "cat" part too. Either use a script, or do something like 

	time sh -c "git-rev-list ... | cat > /dev/null".

> $ time git rev-list --header --boundary --parents --topo-order HEAD >
> /tmp/tmp.txt; cat /tmp/tmp.txt > /dev/null
> 3.44user 0.28system 0:03.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+18033minor)pagefaults 0swaps

Again - you're only timing the _writer_, not the "cat" at all.

> For some reason the CPU *never* goes up 93% with pipe (while it's easy
> in the other two cases)

That's because you're only timing 93% of the work (ignoring the "cat" 
part), and in the other cases you're ignoring the "cat" (that happens 
_afterwards_, not concurrently) entirely.

> OK. I just don't understand how after waiting 100ms I get only 60KB
> and stay in the loop only one cycle instead of reading,


That's because the _writer_ will block. It notices that the reader cannot
read ass fast as it can write, so it blocks when its buffers fill up.

If you want to be fast, you need to be fast at reading. It's that simple.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Linus Torvalds wrote:
> 
> That's not timing what I asked. That's just timing the "git-rev-list". You 
> need to time the "cat" part too. Either use a script, or do something like 
> 
> 	time sh -c "git-rev-list ... | cat > /dev/null".

Btw, if you do this, you'll actually see one of the _real_ advantages of 
pipes.

On an SMP system, you'll easily get output like "110%CPU", since now the 
git-rev-list and the user can run in parallel. Of course, they can do so 
with temp-files too, but then you have all the "is it a true EOF, or is it 
just the fact that the writer hasn't written everything yet" problem (and 
the _normal_ solution for that is to simply not allow any overlapping 
work).

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:
> On Monday 11 December 2006 13:52, Marco Costalba wrote:
> > On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:
> > > On Monday 11 December 2006 01:15, Marco Costalba wrote:
> > > >               guiUpdateTimer.start(100, true);
> > >
> > > What is the result with "guiUpdateTimer.start(0, true);" ?
> > ...
> > IOW you suggest to use a brute force polling of the pipe.
>
> Ah, yes. That is probably not what you want.
>
> Why did you introduce the timer at all? What was the problem
> with QProcess and handling its signal "data available" ?
>

I did. Actually the released 1.5.3 version and all the verions before
that do use QProcess, but I experimented an increase in performance
reading the data  on a timer instead of on "data available" signal.
BTW that observation led to all this stuff ;-)

The problem is that the frequency of the signal is very very high
because the producer can write a big amount of data with great speed.
We are talking of a signal "data available" each few ms.

By the way of experimenting with QProcess I have found it's better a
timer when the stream is very very fast, _then_ I have update the
reading code to take _more_ adavntage of the big chunks we were
reading with a low frequency timer and avoid a double copy, but the
increase was _already_ present also with the double copy needed by the
original 'small chunks handling' code activated by "data available"
signal.

If you take a look at released qgit you will see, in dataloader.cpp
the reading slot called on the signal.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Mon, 11 Dec 2006, Linus Torvalds wrote:
> >
> > That's not timing what I asked. That's just timing the "git-rev-list". You
> > need to time the "cat" part too. Either use a script, or do something like
> >
> >       time sh -c "git-rev-list ... | cat > /dev/null".
>
> Btw, if you do this, you'll actually see one of the _real_ advantages of
> pipes.
>
> On an SMP system, you'll easily get output like "110%CPU", since now the
> git-rev-list and the user can run in parallel. Of course, they can do so
> with temp-files too, but then you have all the "is it a true EOF, or is it
> just the fact that the writer hasn't written everything yet" problem (and
> the _normal_ solution for that is to simply not allow any overlapping
> work).
>

Sorry for wrong data, I will repost as soon as I can.

Regarding the _normal_  solution we have one more hipotesys to take
advantage of: git-rev-list when has nothing more to read..exits.

This is what lead to the exit loop condition based on git-rev-list is
still alive, instead of messing with an EOF.

     eof  = (no more data && !rev_list_is_running);

With this we could enter the loop one more time then necessary, but
nothing else bad should happen.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Marco Costalba wrote:
> 
> Regarding the _normal_  solution we have one more hipotesys to take
> advantage of: git-rev-list when has nothing more to read..exits.

Yes. You can just wait for the child exit signal.

However, you seem to continually ignore the thing I've asked you to do 
several times: try with a cold-cache situation.

The thing is, using pipes and poll()/select()/epoll()/whatever will not 
only be efficient, but it will also WORK CORRECTLY in the presense of a 
writer that is _slower_ than the reader.

Right now, you're testing the exact opposite. You're testing the case 
where the reader is slower than the writer, which is actually not that 
interesting - because if "git-rev-list" is instantaneous, then the fastest 
thing to do is to simply _always_ just read the result buffer directly 
into memory without any select() loop etc what-so-ever.

So just by testing that case (and you've slowed down the reader 
artificially even _apart_ from the fact that qgit will probably always be 
slower than git-rev-list off a packed and hot-cache environment), you're 
always going to skew your results into the "do everything in one go" 
direction.

But the point of the pipe and the poll() is that it works nicely even when 
the data trickles in slowly.

[ Of course, as long as you ask for "--topo-order", you'll never see a lot 
  of trickling, and you'll never be able to do really well for the 
  cold-cache case. To see the _real_ advantage of pipes, you should void 
  "--topo-order" entirely, and do it dynamically within qgit, repainting 
  the graph as needed.

  At that point, you'd actually do something that gitk can't do at all, 
  namely work well for the cold-cache not-very-packed large-repository 
  case. ]

To see this in practice (even with hot-caches), do something like the 
following on the full historic Linux archive:

	time sh -c "git rev-list HEAD | head"
	time sh -c "git rev-list --topo-order HEAD | head"

where for me, the firstone takes 0.002s, and the second one takes 0.878s.

Now THAT is an optimization. Not just "10%" or even "ten times", but "four 
HUNDRED times" faster.

And why is that? Simply because it only needed to look at _part_ of the 
data. For the exact same reason, if you were to do the topological sort 
only on the part that you had _looked_ at first, you'd be able to do these 
kinds of several-orders-of-magnitude improvements.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
>
> However, you seem to continually ignore the thing I've asked you to do
> several times: try with a cold-cache situation.

Yes. I will test it. I was testing with warm cache also to my
curiosity about comparing pipes with temporary file reading as data
exchange facility. So I needed to avoid HD artifacts.

>
>
>   At that point, you'd actually do something that gitk can't do at all,
>   namely work well for the cold-cache not-very-packed large-repository
>   case. ]
>

Removing --topo-order from launch parameters is very simple, see from
gitstartup.cpp:

bool Git::startRevList(SCRef args, FileHistory* fh) {

	QString initCmd("git rev-list --header --boundary --parents ");
	if (!isMainHistory(fh)) {
		// fetch history from all branches so any revision in
		// main view that changes the file is always found
		SCRef allBranches = getAllRefSha(BRANCH).join(" ");
		initCmd.append("--remove-empty " + allBranches + " -- ");
	} else
		initCmd.append("--topo-order ");

	return startParseProc(initCmd + args, fh);
}

It is already removed from file history fetching because there the
history it's _almost_ linear and you gain the speed without noticing
the different graph layout. But for main view I fear that complicated
branch structures could became difficult to follow without
--topo-order. Perhaps an option in settings?

> To see this in practice (even with hot-caches), do something like the
> following on the full historic Linux archive:
>
>         time sh -c "git rev-list HEAD | head"
>         time sh -c "git rev-list --topo-order HEAD | head"
>
> where for me, the firstone takes 0.002s, and the second one takes 0.878s.
>

This is  the data:

$ pwd
/git/linux-2.6
bash-3.1$ time sh -c "git rev-list HEAD | head"
200d018eff4be3a1fb9823441cfcebb7de86a677
f0647a52974daccbe20990fb6341f07792445fe0
c25c79d80e02db1bd993426f979c5f1b42a0f132
9fd32cfbb602f3e5e898faa61d83c4a7897bd48a
ed99e2bc1dc5dc54eb5a019f4975562dbef20103
773ff78838ca3c07245e45c06235e0baaa5f710a
52ffe760ea9ec407292d093c3f06c1cda5187228
14b36af46a1d3652aff6734ea24816995dff8123
eb991b39385c7b04923d701764a34694ec54b53d
88032b322a38b37335c8cb2e3473a45c81d280eb
0.08user 0.02system 0:00.10elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+3631minor)pagefaults 0swaps

bash-3.1$  time sh -c "git rev-list --topo-order HEAD | head"
200d018eff4be3a1fb9823441cfcebb7de86a677
f0647a52974daccbe20990fb6341f07792445fe0
c25c79d80e02db1bd993426f979c5f1b42a0f132
9fd32cfbb602f3e5e898faa61d83c4a7897bd48a
ed99e2bc1dc5dc54eb5a019f4975562dbef20103
773ff78838ca3c07245e45c06235e0baaa5f710a
52ffe760ea9ec407292d093c3f06c1cda5187228
14b36af46a1d3652aff6734ea24816995dff8123
eb991b39385c7b04923d701764a34694ec54b53d
33ec32fae0e2c4433bfd1e74cbde6cb16604a719
2.84user 0.12system 0:03.05elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+12086minor)pagefaults 0swaps

Also the long awaited ;-)

$ time sh -c "git rev-list --header --boundary --parents --topo-order
HEAD | cat > /dev/null"
3.75user 0.55system 0:04.42elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+18822minor)pagefaults 0swaps

$ time sh -c "git rev-list --header --boundary --parents --topo-order
HEAD > /tmp/tmp.txt; cat /tmp/tmp.txt > /dev/null"
3.50user 0.30system 0:03.92elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+18800minor)pagefaults 0swaps

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Marco Costalba wrote:
> 
> $ time sh -c "git rev-list --header --boundary --parents --topo-order HEAD | cat > /dev/null"
> $ time sh -c "git rev-list --header --boundary --parents --topo-order HEAD > /tmp/tmp.txt; cat /tmp/tmp.txt > /dev/null"

Btw, for me the numbers aren't stable enough to be al lthat final, but 
doing it multiple times on the kernel archive I get:

	real    0m0.947s
	real    0m1.046s
	real    0m0.943s
	real    0m0.868s

for the pipe case, and

	real    0m0.953s
	real    0m1.056s
	real    0m1.060s
	real    0m0.968s

for the temp-file. IOW, no real difference. Just doing the "> /dev/null" 
directly is more consistent (no task-switching, SMP effects, or cache 
conflicts) at

	real    0m0.806s
	real    0m0.806s
	real    0m0.805s
	real    0m0.808s

but one recurrent theme is definitely true: the "cat" part is a noticeable 
overhead. But that in itself means that git-rev-list is just so efficient 
that even just basically copying its output is going to be measurable. 

Which is obviously a good thing, but it means that it's not very 
interesting in the big picture (ie I bet the real overheads are going to 
be elsewhere if you actually expect to draw anything on the screen).

Re: [RFC \ WISH] Add -o option to git-rev-list

[Josef Weidendorfer]

On Monday 11 December 2006 19:59, Marco Costalba wrote:
> On 12/11/06, Linus Torvalds <torvalds@osdl.org> wrote:
> >
> >
> >
> > However, you seem to continually ignore the thing I've asked you to do
> > several times: try with a cold-cache situation.
> 
> Yes. I will test it. I was testing with warm cache also to my
> curiosity about comparing pipes with temporary file reading as data
> exchange facility. So I needed to avoid HD artifacts.

Hi,

I just looked at the QProcess implementation in Qt 3.3.6, as I was
curious.

Qt does a big select() call in the event loop. If there is data
available from the child process, it is reading in chunks of a
maximum of 4096 bytes, with a select() call inbetween to see if
there is still data available. After every read, the read data
is concatenated into the read buffer.

For the slow/cold cache case, this probably is the best *if* the
consumer application can act as fast as possible when data is
sent. Which makes it a good fit to avoid --topo-order and do
some redrawing of the graph yourself if needed. For sure, this
gives the fastest visual appeareance. You could start filling
the list after e.g. 30 revs are read.

Obviously, there is some possibility for improvement _when_ you
know that you want to read in large amounts of data in big
chunks, given that QProcess uses at least two system calls every
4 kB.

A general question: How many context switches are involved in such
a producer/consumer scenario, given that the consumer writes one
line at a time, and the consumer uses poll/select to wait for the
data?
Is there some possibility to make the kernel write-combine single
small producer writes into bigger chunks, which will be delivered
at once (or smaller data only after a small timeout)?

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Josef Weidendorfer wrote:
> 
> A general question: How many context switches are involved in such
> a producer/consumer scenario, given that the consumer writes one
> line at a time, and the consumer uses poll/select to wait for the
> data?
> Is there some possibility to make the kernel write-combine single
> small producer writes into bigger chunks, which will be delivered
> at once (or smaller data only after a small timeout)?

The data will be write-combined.

The kernel doesn't context-switch after a write() to a pipe if there is 
space left (and usually the pipe buffer is 64kB with current kernels, so 
there obviously will be), unless the reader has a higher priority for some 
reason (ie the reader has been waiting a long time).

So _normally_ you'll see many many writes in one go, and only see context 
switching when the kernel pipe buffer fills up.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Josef Weidendorfer]

On Monday 11 December 2006 21:40, Linus Torvalds wrote:
> On Mon, 11 Dec 2006, Josef Weidendorfer wrote:
> > A general question: How many context switches are involved in such
> > a producer/consumer scenario, given that the consumer writes one
> > line at a time, and the consumer uses poll/select to wait for the
> > data?
> > Is there some possibility to make the kernel write-combine single
> > small producer writes into bigger chunks, which will be delivered
> > at once (or smaller data only after a small timeout)?
> 
> The data will be write-combined.
> 
> The kernel doesn't context-switch after a write() to a pipe if there is 
> space left (and usually the pipe buffer is 64kB with current kernels, so 
> there obviously will be), unless the reader has a higher priority for some 
> reason (ie the reader has been waiting a long time).

Ah, thanks.
So the implementation in Qt's QProcess is a little bit pessimistic, probably
to make it work fine with other UNIXs out there.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Mon, 11 Dec 2006, Josef Weidendorfer wrote:
> 
> So the implementation in Qt's QProcess is a little bit pessimistic, probably
> to make it work fine with other UNIXs out there.

I suspect it may actually have been performance-optimized for Linux-2.4, 
where the pipe buffer size was one page (so if you got a full 4kB on x86, 
you'd know that the buffer was fully emptied).

And it actually does end up depending on the load too. For example, the 
4kB can also happen to match the default buffer size in stdio (or in the 
QT IO buffering equivalent), and in that case you know that any _writer_ 
that uses stdio buffering will usually use that as the blocksize, so you 
have reasons beyond the kernel to think that maybe a certain particular 
blocksize is more common than others.

And if that's the case, then if you know that _usually_ the read() would 
return -EAGAIN, then it's actually better to return to the main loop and 
select(), on the assumption that quite often, the select will be the right 
thing (and if it isn't, it will just return immediately anyway, and you 
can do the second read).

In other words, it's really a "tuning thing" that depends on the IO 
patterns of the apps involved, and the underlying pattern of the OS can 
affect it too.

Of course, most of the time it doesn't make _that_ much of a difference, 
especially when system calls are reasonably cheap (and they largely are, 
under Linux). So you can certainly see the effects of this, but the 
effects will vary so much on the load and other issues that it's hard to 
say that there is "one correct way" to do things.

For example, very subtle issues can be at play:

 - using a larger buffer and having fewer system calls can be 
   advantageous in many cases. But certainly not always.

   HOWEVER. If you have two processes that both do very little with the 
   data (generating it _or_ using it), and process switching is cheap 
   thanks to address space identifiers or clever TLB's, then a small 
   buffer may actually be much better, if it means that the whole working 
   set fits in the L2 cache.

   So a large buffer with fewer system calls may actually be _bad_, if 
   only because it causes things to go to L3 or memory. In contrast, if 
   you can re-use a smaller buffer, you'll stay in the L2 cache better. 

   Same goes for the L1 cache too, but that's really only noticeable for 
   true micro-benchmarks. Sadly, people often do performance analysis with 
   microbenches, so they can actually tune their setup for something that 
   is NOT what people actually see in real life.

   In general, if you re-use your buffer, try to keep it small enough that 
   it stays hot in the L2 can be a good thing. Using 8kB or 16kB buffers 
   and 64-128 system calls can actually be a lot BETTER than using a 1MB 
   buffer and a single system call.

   Examples of this is stdio. Making your stdio buffers bigger simply 
   often isn't a good idea. The system call cost of flushing the buffer 
   simply isn't likely to be the highest cost.

 - real-time or fairness issues. Sometimes you are better off doing a 
   round-robin thing in the main select() loop over 10 smaller buffers 
   than over ten big buffers (or over a single mainloop call-out that 
   keeps doing read() until the buffer is entirely empty). 

   This is not likely to be an issue with qgit-like behaviour (whether you 
   process a 4kB buffer or 64kB buffer in one go is simply not going to 
   make a visible difference to a user interface), but it can make a 
   difference for "server" apps with latency issues. You do not want one 
   busy client to basically freeze out all the other clients by just 
   keeping its queue filled all teh time.

   So returning to the main loop may actually be the right thing after 
   each read(), not for performance reasons, but because it gives a nicer 
   load pattern. It may perform _worse_, but it may well give a smoother 
   feel to the system!

 - simplicity. The main select() loop does the looping anyway, so avoiding 
   looping in the callouts simplifies the system. And since it's not 
   necessarily the right thing to do to loop in the individual routines 
   _anyway_ (see above), why not?

So I don't think there is a right answer here. I suspect QProcess does ok.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/11/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> So I don't think there is a right answer here. I suspect QProcess does ok.
>

I have just pushed a patch (wiil be available in few hours I suspect)
to easily choose the data exchange facility with git-rev-list.

Default its temporary file based, but after uncommenting the
USE_QPROCESS define in dataloader.cpp and compile again, qgit will use
a QProcess based approach to connect with git-rev-list.

Only the low level connection is different in the two cases, _all_ the
rest, expecially data storing and parsing, is the same. If you take a
look at src/dataloader.cpp you will see that the difference between
QProcess and temp file code is minumum.

I've also tried to clearly report in comments the different approaches
and the data copy involved in both cases. I've searched a little bit
in QProcess sources too to get some additional info.


And finally these are mine warm and cold cache tests.

Load time test on Linux tree (44557 revs, 32167KB)
CPU Mobile Pentium 4 set at 1.2GHZ

To set data read interval in ms use (src/dataloader.cpp):
#define GUI_UPDATE_INTERVAL 500

Warmed-up cache
QProcess 7632ms (500ms data read interval)
QProcess 7972ms (100ms data read interval)

Temporary file 4408ms (500ms data read interval)
Temporary file 4591ms (100ms data read interval)


Cold cache
QProcess 25611ms (500ms data read interval)

File 22399ms (500ms data read interval)

Re: [RFC \ WISH] Add -o option to git-rev-list

[Linus Torvalds]

On Fri, 15 Dec 2006, Marco Costalba wrote:
> 
> Warmed-up cache
> QProcess 7632ms (500ms data read interval)
> QProcess 7972ms (100ms data read interval)

Why do you even bother posting numbers, when multiple people have told you 
that the numbers you post are meaningless?

As long as you throttle the writer by not reading data in a timely fashion 
(by using poll() or select() in the main loop and reading when it's 
available), and you continue to talk about "data read intervals", all your 
numbers are CRAP.

OF COURSE a temp-file will work better, because then you basically have an 
infinite buffer, and data read intervals don't _matter_. But we've tried 
to tell you that this is not because temp-files are better, but because 
your reader artificially throttles the writer for a pipe.

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/15/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Fri, 15 Dec 2006, Marco Costalba wrote:
> >
> > Warmed-up cache
> > QProcess 7632ms (500ms data read interval)
> > QProcess 7972ms (100ms data read interval)
>
> Why do you even bother posting numbers, when multiple people have told you
> that the numbers you post are meaningless?
>
> As long as you throttle the writer by not reading data in a timely fashion
> (by using poll() or select() in the main loop and reading when it's
> available), and you continue to talk about "data read intervals", all your
> numbers are CRAP.
>

QProcess implementation is like this FWIK (from
qt-x11-free-3.3.4/src/kernel/qprocess_unix.cpp):

The SIGCHLD handler writes to a socket to tell the manager that
something happened. Then in  QProcessManager::sigchldHnd() data is read by

process->socketRead( proc->socketStdout );


In QProcess::socketRead() a call to C function read() is done to get
4KB of data:

const int basize = 4096;
QByteArray *ba = new QByteArray( basize );
n = ::read( fd, ba->data(), basize );


The pointer ba is then appended to a pointer list.

This happens _ALWAYS_ indipendently of _how_ the application calls the
Qt library for reading.

When application read recieved data with QProcess::readStdout(), then
data stored in buffers pointed by the pointer list is memcpy() to a
temporary array that is the return value of QProcess::readStdout().
See in qt-x11-free-3.3.4/src/kernel/qprocess.cpp:

QByteArray QProcess::readStdout()
{
    if ( readStdoutCalled ) {
	return QByteArray();
    }
    readStdoutCalled = TRUE;
    QMembuf *buf = membufStdout();
    readStdoutCalled = FALSE;

    return buf->readAll();  // here a memcpy() is involved
}


So it' true that we use a timeout, but only to trigger a memcpy() from
Qt internal library buffers that, instead are feeded as soon as
possible by Qt implementation.

IOW the timely select() is already done by Qt library. We just read
what has been already received and stored.

   Marco

Re: [RFC \ WISH] Add -o option to git-rev-list

[Marco Costalba]

On 12/15/06, Marco Costalba <mcostalba@gmail.com> wrote:
>
> IOW the timely select() is already done by Qt library. We just read
> what has been already received and stored.
>

Try to set the timer to a very high value so that never triggers and
there is only one read call at the end, after git-rev-list exited,
when there is a forced call to the data read function.

Times seems to get even better! This is because timely read of the
pipe is _already_ done inside Qt library, not by qgit application.