Making diff(1) of linux kernels faster
Subsystems (3)
A while ago somebody with too much memory was gloating that they would do a "find ... xargs cat>/dev/null" on several 2.4.x trees so that diff wouldn't thrash the disk with a million seeks :-)
Well, I taught diff to read each tree sequentially 1st and the results were quite surprising (linux-2.2 kernel, two identical 8 MB trees, on some older hardware, average times reported, new diff option is "-z").
diff -urN, nothing cached: 36 seconds
diff -urzN, nothing cached: 7.5 seconds (about 1/5 !!!!!)
diff -urN, all cached: 1.04 seconds
diff -urzN, all cached: 1.66 seconds
So, with the cold cache, my patch cut the time by a factor of 5(!!) and the amount of audible death growls from the disk is also reduced. In the warm case, you pay a slight penalty since the simple hack doesn't try to keep the file data around while priming the cache.
Now if I only had enough ram to personally test how much it helps against a couple of 2.4.x kernel trees... other stats welcomed.
Paul.
diff.c renamed from diffutils-2.7/diff.c +17 -1
@@ -206,6 +206,7 @@ {"exclude", 1, 0, 'x'}, {"exclude-from", 1, 0, 'X'}, {"side-by-side", 0, 0, 'y'}, + {"zoom", 0, 0, 'z'}, {"unified", 2, 0, 'U'}, {"left-column", 0, 0, 129}, {"suppress-common-lines", 0, 0, 130},
@@ -244,7 +245,7 @@/* Decode the options. */ while ((c =getopt_long (argc, argv, -"0123456789abBcC:dD:efF:hHiI:lL:nNpPqrsS:tTuU:vwW:x:X:y" , +"0123456789abBcC:dD:efF:hHiI:lL:nNpPqrsS:tTuU:vwW:x:X:yz" , longopts,0 )) !=EOF ) { switch (c)
@@ -493,6 +494,11 @@specify_style (OUTPUT_SDIFF );break ; +case 'z' : +/* Pre-read each tree sequentially to prime cache, avoid seeks. */ + preread_tree =1 ; +break ; +case 'W' :/* Set the line width for OUTPUT_SDIFF. */ if (ck_atoi (optarg, &width) || width <=0 )
@@ -736,6 +742,7 @@"-S FILE --starting-file=FILE Start with FILE when comparing directories.\n" ,"--horizon-lines=NUM Keep NUM lines of the common prefix and suffix." ,"-d --minimal Try hard to find a smaller set of changes." , +"-z --zoom Assume both trees (with -r) will fit into machine core." ,"-H --speed-large-files Assume large files and many scattered small changes.\n" ,"-v --version Output version info." , "--help Output this help.",
@@ -990,6 +997,15 @@ }else { + +/* Sometimes faster to load each tree into OS's cache 1st */ + +if (depth ==0 && recursive && preread_tree) + { +preread (inf[0 ].name); +preread (inf[1 ].name); + } + val =diff_dirs (inf, compare_files, depth); }
diff.h renamed from diffutils-2.7/diff.h +3 -0
@@ -93,6 +93,9 @@/* File labels for `-c' output headers (-L). */ EXTERN char *file_label[2]; +/* 1 if trees should be read sequentially to avoid seeks during recursive. */ +EXTERN int preread_tree; +struct regexp_list {struct re_pattern_buffer buf;
io.c renamed from diffutils-2.7/io.c +58 -0
64 lines not on this page · raw message
Quoted 4 lines · Paul Gortmaker
So, with the cold cache, my patch cut the time by a factor of 5(!!) and the amount of audible death growls from the disk is also reduced. In the warm case, you pay a slight penalty since the simple hack doesn't try to keep the file data around while priming the cache.
excellent. how does it go on other kernels? (solaris? irix? win32?)
j.
Signature · 2 lines
R N G G "Well, there it goes again... And we just sit I G G G here without opposable thumbs." -- gary larson
Quoted 4 lines · Paul Gortmaker
Well, I taught diff to read each tree sequentially 1st and the results were quite surprising (linux-2.2 kernel, two identical 8 MB trees, on some older hardware, average times reported, new diff option is "-z").
Not that surprising. The very same factor of 5 was talked about in the read-ahed thread - "diff -ur" is nasty because the kernel usually cannot effectively read-ahead much of anything (each file is small, and the kernel doesn't do intra-file read-ahead), and because the trees are in different locations on the disk you end up seeking a _lot_ between each file diff.
Quoted 2 lines
Now if I only had enough ram to personally test how much it helps against a couple of 2.4.x kernel trees... other stats welcomed.
Could you maybe instead of pre-reading the whole tree, just pre-read one directory at a time?
Quite frankly, the whole-tree approach only works well if you have _much_ more than 2*tree-size worth of memory (not counting other apps you have open). Not everybody has that, especially not these days when the full tree is 50MB+ or something.
So the full pre-read is probably only worthwhile on machines with closer to half a gig of memory, or with old kernels..
Even just doing it one directory at a time should improve speed _noticeably_. I'd bet you'll get close to the same improvement, with much less memory pressure..
Linus
Quoted 4 lines · Linus Torvalds
Quoted 2 lines · Paul Gortmaker
Well, I taught diff to read each tree sequentially 1st and the results
...
Quoted 2 lines
Could you maybe instead of pre-reading the whole tree, just pre-read one directory at a time?
...
Quoted 5 lines
Even just doing it one directory at a time should improve speed _noticeably_. I'd bet you'll get close to the same improvement, with much less memory pressure..
Linus
Yup, on the small 8MB tree (v1.2.0) it seems to be the same improvement (within the errors of my $0.02 test) and doesn't require gobs of ram.
On a more real world test; on a 90% full ext2 2GB disk with 2.4.10 trees on a 32MB machine, this patch cuts the diff time in about 1/2. (The first version of the patch would have been pathological on such a low mem machine - essentially doubling the time taken vs. unpatched.) Obviously maximum improvement would be for unfragmented trees living at opposite edges of the disk and with more mem - so I would expect that people should see a minimum of a factor of two improvement.
Oh, and prereading the dirs of both trees (vs. just one and letting normal execution read in the 2nd) seems to offer better improvements. (Steady stream of requests results in better merging perhaps?)
This was all running under a 2.2.x kernel btw; might have time to test on a 2.4.x one later. Either way, it kind of makes you wonder why nobody had done this earlier (not to mention feeding the source to indent -kr -i8...)
Paul.
diff.c renamed from diffutils-2.7/diff.c +17 -1
@@ -206,6 +206,7 @@ {"exclude", 1, 0, 'x'}, {"exclude-from", 1, 0, 'X'}, {"side-by-side", 0, 0, 'y'}, + {"zoom", 0, 0, 'z'}, {"unified", 2, 0, 'U'}, {"left-column", 0, 0, 129}, {"suppress-common-lines", 0, 0, 130},
@@ -244,7 +245,7 @@/* Decode the options. */ while ((c =getopt_long (argc, argv, -"0123456789abBcC:dD:efF:hHiI:lL:nNpPqrsS:tTuU:vwW:x:X:y" , +"0123456789abBcC:dD:efF:hHiI:lL:nNpPqrsS:tTuU:vwW:x:X:yz" , longopts,0 )) !=EOF ) { switch (c)
@@ -493,6 +494,11 @@specify_style (OUTPUT_SDIFF );break ; +case 'z' : +/* Pre-read each dir sequentially to prime cache, avoid seeks. */ + preread_dir =1 ; +break ; +case 'W' :/* Set the line width for OUTPUT_SDIFF. */ if (ck_atoi (optarg, &width) || width <=0 )
@@ -736,6 +742,7 @@"-S FILE --starting-file=FILE Start with FILE when comparing directories.\n" ,"--horizon-lines=NUM Keep NUM lines of the common prefix and suffix." ,"-d --minimal Try hard to find a smaller set of changes." , +"-z --zoom Read ahead whole directories (with -r) at a time." ,"-H --speed-large-files Assume large files and many scattered small changes.\n" ,"-v --version Output version info." , "--help Output this help.",
@@ -990,6 +997,15 @@ }else { + +/* Sometimes faster to load a whole dir into OS's cache 1st */ + +if (recursive && preread_dir) + { +preread (inf[0 ].name); +preread (inf[1 ].name); + } + val =diff_dirs (inf, compare_files, depth); }
diff.h renamed from diffutils-2.7/diff.h +3 -0
@@ -93,6 +93,9 @@/* File labels for `-c' output headers (-L). */ EXTERN char *file_label[2]; +/* 1 if dirs should be read sequentially to avoid seeks during recursive. */ +EXTERN int preread_dir; +struct regexp_list {struct re_pattern_buffer buf;
io.c renamed from diffutils-2.7/io.c +53 -0
59 lines not on this page · raw message
Quoted 4 lines · Paul Gortmaker
Oh, and prereading the dirs of both trees (vs. just one and letting normal execution read in the 2nd) seems to offer better improvements. (Steady stream of requests results in better merging perhaps?)
That doesn't make much sense, but I'll take your word for it. Does this behaviour show up on 2.4.x too? It sounds like a performance buglet in the kernel or some infrastructure, really.
The one problem with pre-reading is that it will now artificially touch the data twice, and when running on 2.4.x it will activate the pages. That's going to be exactly what _I_ want it to do on my machine, but others are likely to be less happy about it.
Btw, why use "slurp()" and actually doing the memory allocations etc, only to throw it away again? It would be better to either really keep the allocation around (which would also fix the touch-twice issue but would cause much more changes to 'diff'), or to just read into the same buffer over and over again..
And I've for a long time thought about adding a "readahead()" system call. There are just too many uses for it, it has come up in many different areas..
Quoted 4 lines
This was all running under a 2.2.x kernel btw; might have time to test on a 2.4.x one later. Either way, it kind of makes you wonder why nobody had done this earlier (not to mention feeding the source to indent -kr -i8...)
Who's the maintainer for "diff" these days? This change seems small and simple enough that they might accept it, and I'd love to see it. I'll probably do this in my copy anyway, but it would be nicer to not have to patch it specially..
As to using sane indentation - you're talking about a FSF-maintained thing. Which means that they'll almost certainly not fix their horrible problems with indentation ;(
Linus
Quoted 4 lines · Linus Torvalds
Who's the maintainer for "diff" these days? This change seems small and simple enough that they might accept it, and I'd love to see it. I'll probably do this in my copy anyway, but it would be nicer to not have to patch it specially..
afaict, there is no maintainer. The stated maintainer has been ignoring patches for years.
regards
john
Signature · 3 lines
"There are two kinds of fool. One says, 'This is old, and therefore good.' And one says, 'This is new, and therefore better'." - John Brunner
Quoted 22 lines · Linus Torvalds
Quoted 4 lines · Paul Gortmaker
Oh, and prereading the dirs of both trees (vs. just one and letting normal execution read in the 2nd) seems to offer better improvements. (Steady stream of requests results in better merging perhaps?)
That doesn't make much sense, but I'll take your word for it. Does this behaviour show up on 2.4.x too? It sounds like a performance buglet in the kernel or some infrastructure, really.
The one problem with pre-reading is that it will now artificially touch the data twice, and when running on 2.4.x it will activate the pages. That's going to be exactly what _I_ want it to do on my machine, but others are likely to be less happy about it.
Btw, why use "
slurp()" and actually doing the memory allocations etc, only to throw it away again? It would be better to either really keep the allocation around (which would also fix the touch-twice issue but would cause much more changes to 'diff'), or to just read into the same buffer over and over again..
Quoted 3 lines
And I've for a long time thought about adding a "
readahead()" system call. There are just too many uses for it, it has come up in many different areas..
There is a paper on USENIX 2001 which does implement directory readahead and it shows huge improvements for some workload.
I'll dig it down and see if I can find that.
Quoted 7 lines · Marcelo Tosatti
Quoted 4 lines
And I've for a long time thought about adding a "
readahead()" system call. There are just too many uses for it, it has come up in many different areas..There is a paper on USENIX 2001 which does implement directory readahead and it shows huge improvements for some workload.
Hmm.. The implementation is trivial, it's really just a simple 3-line while-loop, with the rest of the code just doing argument checking etc.
Attached is the kernel diff ("ra-diff") along with a stupid program ("preread.c"), cribbed mostly from Pauls first patch to use it to pre-read a while tree.
It took much longer to compile the kernel and reboot, and write the test-program than it did to write the patch itself ;)
It walks the whole kernel tree in 0.2 seconds of CPU-time on my machine (of course, if it actually needs to start IO, the 0.2 seconds becomes 0.3 seconds of CPU time and almost a minute and a half of wall-clock. Anyway, it clearly isn't a CPU-hog like doing a real "read" would have been).
And unlike the read, it doesn't have any impact on the active queue.
Linus
arch/i386/kernel/entry.S renamed from linux/arch/i386/kernel/entry.S +1 -0
@@ -621,6 +621,7 @@ .long SYMBOL_NAME(sys_ni_syscall) /* reserved for TUX */ .long SYMBOL_NAME(sys_ni_syscall) /* Reserved for Security */ .long SYMBOL_NAME(sys_gettid) + .long SYMBOL_NAME(sys_readahead) /* 225 */ .rept NR_syscalls-(.-sys_call_table)/4 .long SYMBOL_NAME(sys_ni_syscall)
include/asm-i386/unistd.h renamed from linux/include/asm-i386/unistd.h +1 -0
@@ -229,6 +229,7 @@#define __NR_fcntl64 221#define __NR_security 223/* syscall for security modules */ #define __NR_gettid 224 +#define __NR_readahead 225/* user-visible error numbers are in the range -1 - -124: see <asm-i386/errno.h> */
mm/filemap.c renamed from linux/mm/filemap.c +47 -0
53 lines not on this page · raw message
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <stdlib.h>
#include <sys/fcntl.h>
/* Preload the OS's cache with all files of one branch for recursive diffs */
#define __NR_readahead 225
asm(
"__readahead:\n\t"
"pushl %ebx\n\t"
"pushl %esi\n\t"
"movl 12(%esp),%ebx\n\t"
"movl 16(%esp),%ecx\n\t"
"movl 20(%esp),%edx\n\t"
"movl 24(%esp),%esi\n\t"
"movl $225,%eax\n\t"
"int $0x80\n\t"
"popl %esi\n\t"
"popl %ebx\n\t"
"ret");
extern ssize_t __readahead(int fd, loff_t offset, size_t size);
void
preread (dir)
const char *dir;
{
DIR *d;
struct dirent *dent;
d = opendir(dir);
if (d == NULL) return;
while ((dent = readdir(d)) != NULL)
{
int fd;
struct stat st;
char *name, *path; name = dent->d_name;
if (name[0] == '.' && (name[1] == 0 || (name[1] == '.' && name[2] == 0)))
continue;
path = malloc(strlen(dir)+strlen(name)+2);
strcpy(path, dir);
strcat(path, "/");
strcat(path, name);
fd = open(path, O_RDONLY);
if (fd >= 0) {
if (fstat(fd, &st) == 0) {
if (S_ISDIR(st.st_mode))
preread(path);
else if (S_ISREG(st.st_mode))
{
__readahead(fd, 0, ~0UL);
}
}
close(fd);
}
free(path); }
closedir(d);
}
int main(int argc, char **argv)
{
preread(argv[1]);
return 0;
}Paul Gortmaker <[email protected]> writes:
|> This was all running under a 2.2.x kernel btw; might have time to |> test on a 2.4.x one later. Either way, it kind of makes you wonder |> why nobody had done this earlier
What's wrong with running find on the tree first? IMHO there is no need to introduce an obscure option if there is already a working alternative.
Andreas.
Signature · 4 lines
Andreas Schwab "And now for something [email protected] completely different." SuSE Labs, SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
Quoted 3 lines · Linus Torvalds
And I've for a long time thought about adding a "
readahead()" system call. There are just too many uses for it, it has come up in many different areas..
Well, here's a sendpage for /dev/null which is useful for prefetching. Now we just need a background open().
-ben
...~/patches/v2.4.13-pre3-null_sendpage.diff
drivers/char/mem.c +7 -0
@@ -339,6 +339,12 @@return count; } +static ssize_t sendpage_null (struct file *file,struct page *page,int offset, +size_t size,loff_t *pos,int more) +{ +return size; +} +/* * For fun, we are using the MMU for this. */
@@ -512,6 +518,7 @@ llseek: null_lseek, read: read_null, write: write_null, + sendpage: sendpage_null, };#if !defined(__mc68000__)
Quoted 17 lines · Linus Torvalds
Quoted 7 lines · Marcelo Tosatti
Quoted 4 lines
And I've for a long time thought about adding a "
readahead()" system call. There are just too many uses for it, it has come up in many different areas..There is a paper on USENIX 2001 which does implement directory readahead and it shows huge improvements for some workload.
Hmm.. The implementation is trivial, it's really just a simple 3-line while-loop, with the rest of the code just doing argument checking etc.
Attached is the kernel diff ("ra-diff") along with a stupid program ("
preread.c"), cribbed mostly from Pauls first patch to use it to pre-read a while tree.
Quoted 8 lines
It took much longer to compile the kernel and reboot, and write the test-program than it did to write the patch itself ;)
It walks the whole kernel tree in 0.2 seconds of CPU-time on my machine (of course, if it actually needs to start IO, the 0.2 seconds becomes 0.3 seconds of CPU time and almost a minute and a half of wall-clock. Anyway, it clearly isn't a CPU-hog like doing a real "read" would have been).
I think with directory readahead Marcelo meant a transparent kernel heuristic in the readdir path. ext2_get_page is completly synchronous and it's reading one page at time, that's bad but it can be improved transparently to userspace, just like we do with the files, and also like the old code was doing before the directory in pagecache IIRC.
I don't see a real benefit in the sys_readahead code compared to just reading the files, except it doesn't mark the pagecache referenced, but I think activating the cache of the tree is ok in those special cases. Also I believe in those cases we want to trim the active cache, not only the inactive cache, in order to run diff faster, and we probably want the tree in active cache too ASAP in case we need to run some more diff.
Andrea
Quoted 27 lines · Andrea Arcangeli
Quoted 17 lines · Linus Torvalds
Quoted 7 lines · Marcelo Tosatti
Quoted 4 lines
And I've for a long time thought about adding a "
readahead()" system call. There are just too many uses for it, it has come up in many different areas..There is a paper on USENIX 2001 which does implement directory readahead and it shows huge improvements for some workload.
Hmm.. The implementation is trivial, it's really just a simple 3-line while-loop, with the rest of the code just doing argument checking etc.
Attached is the kernel diff ("ra-diff") along with a stupid program ("
preread.c"), cribbed mostly from Pauls first patch to use it to pre-read a while tree.Quoted 8 lines
It took much longer to compile the kernel and reboot, and write the test-program than it did to write the patch itself ;)
It walks the whole kernel tree in 0.2 seconds of CPU-time on my machine (of course, if it actually needs to start IO, the 0.2 seconds becomes 0.3 seconds of CPU time and almost a minute and a half of wall-clock. Anyway, it clearly isn't a CPU-hog like doing a real "read" would have been).
Quoted 5 lines
I think with directory readahead Marcelo meant a transparent kernel heuristic in the readdir path.
ext2_get_pageis completly synchronous and it's reading one page at time, that's bad but it can be improved transparently to userspace, just like we do with the files, and also like the old code was doing before the directory in pagecache IIRC.
Exactly.
Btw, the USENIX 2001 paper is called "Design and Implementation of a Predictive File Prefetching Algorithm".
They have a Linux implementation of their complex prediction algo, but I think directory readahead itself makes sense for most stuff.
Quoted 5 lines · Andrea Arcangeli
I think with directory readahead Marcelo meant a transparent kernel heuristic in the readdir path.
ext2_get_pageis completly synchronous and it's reading one page at time, that's bad but it can be improved transparently to userspace, just like we do with the files, and also like the old code was doing before the directory in pagecache IIRC.
Do the -ac kernels have the directory in pagecache patch? If not, it could explain why the -ac kernel performed _much_ better for the creat()/stat()/unlink() tests in bonnie++.
Cheers
Chris
Quoted 10 lines · On Wed, Oct 17, 2001 at 10:23:37PM +0100, [email protected] wrote:
Quoted 5 lines · Andrea Arcangeli
I think with directory readahead Marcelo meant a transparent kernel heuristic in the readdir path.
ext2_get_pageis completly synchronous and it's reading one page at time, that's bad but it can be improved transparently to userspace, just like we do with the files, and also like the old code was doing before the directory in pagecache IIRC.Do the -ac kernels have the directory in pagecache patch? If not, it could
yes, -ac has it too.
Quoted 2 lines
explain why the -ac kernel performed _much_ better for the creat()/stat()/unlink() tests in bonnie++.
It can't explain that. But there was another optimization in -ac that avoids restarting searching entries from the start of the directory. That could make a relevant difference. It is included in mainline too starting from 2.4.10.
Andrea
Quoted 4 lines · On Wed, 17 Oct 2001 [email protected] wrote:
Do the -ac kernels have the directory in pagecache patch? If not, it could explain why the -ac kernel performed _much_ better for the creat()/stat()/unlink() tests in bonnie++.
I think that's because bforget() got disabled during the initial buffers-in-pacgecache work, and I forgot to re-enable it again. I'll make a 13pre4, if you want to test.
Linus