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

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:

Marco Costalba, Sun, Dec 10, 2006 12:38:42 +0100:

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.

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

It still is the fastest you can get.

On Sun, 10 Dec 2006, Marco Costalba 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.

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.

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

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().

On Sun, 10 Dec 2006, Marco Costalba wrote:

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).

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.

On Sun, 10 Dec 2006, Linus Torvalds wrote:

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).

On 12/10/06, Linus Torvalds <torvalds@osdl.org> 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)

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!

On 12/10/06, Marco Costalba <mcostalba@gmail.com> wrote:

Of course is

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

On Sun, 10 Dec 2006, Marco Costalba wrote:

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.

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

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.

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$

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

How can open in nonblocking mode with popen() ?

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

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

On Sun, 10 Dec 2006, Marco Costalba wrote:

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.

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.

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

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);

On Mon, 11 Dec 2006, Marco Costalba wrote:

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.

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:

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

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

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) ?

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

On 12/11/06, Marco Costalba <mcostalba@gmail.com> wrote:

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

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

On Mon, 11 Dec 2006, Marco Costalba 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".

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

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.

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.

On Mon, 11 Dec 2006, Linus Torvalds wrote:

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).

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

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.

On Mon, 11 Dec 2006, Marco Costalba wrote:

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.

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

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.

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?

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

On Mon, 11 Dec 2006, Marco Costalba wrote:

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).

On Monday 11 December 2006 19:59, Marco Costalba wrote:

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)?

On Mon, 11 Dec 2006, Josef Weidendorfer wrote:

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.

On Monday 11 December 2006 21:40, Linus Torvalds wrote:

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.

On Mon, 11 Dec 2006, Josef Weidendorfer wrote:

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.

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

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)

On Fri, 15 Dec 2006, Marco Costalba wrote:

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.

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

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

On 12/15/06, Marco Costalba <mcostalba@gmail.com> wrote:

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.

On Monday 11 December 2006 01:15, Marco Costalba wrote:

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.

On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:

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.

On Monday 11 December 2006 13:52, Marco Costalba wrote:

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?

On 12/11/06, Josef Weidendorfer <Josef.Weidendorfer@gmx.de> wrote:

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.

Marco Costalba wrote:

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.

(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.

On 12/11/06, Andreas Ericsson <ae@op5.se> wrote:

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

Marco Costalba wrote:

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.