Re: Making diff(1) of linux kernels faster

Re: Making diff(1) of linux kernels faster

[Marco C. Mason]

Paul--

Paul Gortmaker wrote:
> +          if (recursive && preread_dir)
> +           {
> +              preread(inf[0].name);
> +              preread(inf[1].name);
> +            }

While looking over your patch, I notice that you preload *both*
directories.  (At least, that's what the code above appears to do).
Have you tried just preloading one?  This may still give you the speed
benefit (as you'll most likely reduce the seeking) and put less pressure
on the memory system.

--marco

Re: Making diff(1) of linux kernels faster

[Andries.Brouwer]

>> Who's the maintainer for "diff" these days?

> afaict, there is no maintainer.
> The stated maintainer has been ignoring patches for years.

-rw-r--r--   1 aeb        312312 Oct  2  1994 diffutils-2.7.tar.gz

Yes, if that is the latest, that is old.

I wouldn't mind adding diff to util-linux until
the FSF maintainer wakes up.

(Am using a modified diff myself - one that doesn't give
a lot of output for diff after a successful cp -a,
and does not get into a loop when /etc/net is a symlink to /etc.)

Andries

[But try the FSF first. Is it Paul Eggert?]

Re: Making diff(1) of linux kernels faster

[Sean Neakums]

begin  Horst von Brand quotation:
> =?iso-8859-1?q?willy=20tarreau?= <wtarreau@yahoo.fr> said:
> 
> > Be very careful not to modify a multi-linked file, or
> > it will be damaged in all trees and won't be seen by
> > diff. your editor must unlink before saving.
> 
> Most don't. ed(1), vi(1) and emacs(1) are careful tro write to the
> very same file. jed(1) is the only outlier I'm aware of...

If Emacs is configured to save backups (it is shipped with this option
on by default) the existing file is renamed to the backup name and the
new, changed file is saved in a fresh file.  Thus the trick of diffing
two co-linked trees of files should work as expected.

Emacs users should look in the info node "(emacs)Backup Copying" for
complete information on this.

-- 
 /////////////////  |                  | The spark of a pin
<sneakums@zork.net> |  (require 'gnu)  | dropping, falling feather-like.
 \\\\\\\\\\\\\\\\\  |                  | There is too much noise.

Re: Making diff(1) of linux kernels faster

[willy tarreau]

Hi Paul !

congratulations for this improvement, it seems really
interesting. BTW, I personnaly use hard links between
kernels to make the effective data set smaller, and
I'd
like to explain here how I proceed since there are
often people who seem completely amazed by this method
which I learned here on LKML a few years ago :

# cd /usr/src
# tar Ixf anydir/linux-2.4.12.tar.bz2
# cp -dRflp linux linux-2.4.12
>>> this way, only dir entries are duplicated, so very
>>> little overhead
# (cd linux && bzcat anydir/patch-2.4.13pre1.bz2|patch
-Np1)
# cp -dRflp linux linux-2.4.13pre1
>>> now, only file affected by the patch are
duplicated
>>> then, you can work inside linux dir, and construct
>>> your patches very quickly since a few files
>>> effectively differ from your new tree and old
ones.

Be very careful not to modify a multi-linked file, or
it will be damaged in all trees and won't be seen by
diff. your editor must unlink before saving.

I hope it will help someone as it has helped me for a
while now. I nearly always have sub-second diffs, even
with not-so-much RAM.

Cheers,
Willy


___________________________________________________________
Un nouveau Nokia Game commence. 
Allez sur http://fr.yahoo.com/nokiagame avant le 3 novembre
pour participer à cette aventure tous médias.

Re: Making diff(1) of linux kernels faster

[Horst von Brand]

=?iso-8859-1?q?willy=20tarreau?= <wtarreau@yahoo.fr> said:

[...]

> Be very careful not to modify a multi-linked file, or
> it will be damaged in all trees and won't be seen by
> diff. your editor must unlink before saving.

Most don't. ed(1), vi(1) and emacs(1) are careful tro write to the very
same file. jed(1) is the only outlier I'm aware of...
-- 
Horst von Brand                             vonbrand@sleipnir.valparaiso.cl
Casilla 9G, Vin~a del Mar, Chile                               +56 32 672616

Re: Making diff(1) of linux kernels faster

[Nick Craig-Wood]

Horst von Brand wrote:
> =?iso-8859-1?q?willy=20tarreau?= <wtarreau@yahoo.fr> said:
> > Be very careful not to modify a multi-linked file, or
> > it will be damaged in all trees and won't be seen by
> > diff. your editor must unlink before saving.
> 
> Most don't. ed(1), vi(1) and emacs(1) are careful tro write to the very
> same file. jed(1) is the only outlier I'm aware of...

emacs does mv file file~ before saving file so the edited file will
not be linked byt the backup file will be.  You can stop it doing this
by setting backup-by-copying-when-linked.

$ echo "Test1" >> test1
$ ln test1 test2
$ emacs test2 # modify and save the file
$ ls -i test*
2491498 test1  2491500 test2  2491498 test2~

However as Horst von Brand noted if you try this with (standard) vi
you will edit the linked file which is the same behaviour as if you
set backup-by-copying-when-linked in emacs.

-- 
Nick Craig-Wood
ncw@axis.demon.co.uk

Re: Making diff(1) of linux kernels faster

[Wojtek Pilorz]

On Thu, 18 Oct 2001, Nick Craig-Wood wrote:

> Date: Thu, 18 Oct 2001 09:02:22 +0100
> From: Nick Craig-Wood <ncw@axis.demon.co.uk>
> To: linux-kernel@vger.kernel.org
> Cc: Paul Gortmaker <p_gortmaker@yahoo.com>, vonbrand@sleipnir.valparaiso.cl,
>      willy tarreau <wtarreau@yahoo.fr>
> Subject: Re: Making diff(1) of linux kernels faster 
> 
> Horst von Brand wrote:
> > =?iso-8859-1?q?willy=20tarreau?= <wtarreau@yahoo.fr> said:
> > > Be very careful not to modify a multi-linked file, or
> > > it will be damaged in all trees and won't be seen by
To be sure it is not possible to modify original tree files, I do
chown -R root.root original_tree

before copying it (via cp -lR) to new one, which will be modified with
whatever tools by me, logged in as a regular user. For those having root
access to a box this might be a useful way of preventing accidents ...
(this of course also assumes sane file permissions)
[...]
> > > diff. your editor must unlink before saving.
> > 
> > Most don't. ed(1), vi(1) and emacs(1) are careful tro write to the very
> > same file. jed(1) is the only outlier I'm aware of...
> 
> emacs does mv file file~ before saving file so the edited file will
> not be linked byt the backup file will be.  You can stop it doing this
> by setting backup-by-copying-when-linked.
> 
Best regards,

Wojtek

--------------------
Wojtek Pilorz
Wojtek.Pilorz@bdk.pl

Re: Making diff(1) of linux kernels faster

[vda]

Thursday, October 18, 2001, 11:55:41 AM,
Wojtek Pilorz <wpilorz@bdk.pl> wrote:

>> > > Be very careful not to modify a multi-linked file, or
>> > > it will be damaged in all trees and won't be seen by

WP> To be sure it is not possible to modify original tree files, I do
WP> chown -R root.root original_tree

WP> before copying it (via cp -lR) to new one, which will be modified with
WP> whatever tools by me, logged in as a regular user. For those having root
WP> access to a box this might be a useful way of preventing accidents ...
WP> (this of course also assumes sane file permissions)
WP> [...]

Everytime I see this 'hardlinked kernel tree' technique explained,
I think about true COW fs where duplicate files are physically the
same single file but users don't care about that - COW magic...
No hardlink/vi/emacs/... tricks will be needed...
-- 
Best regards, vda
mailto:vda@port.imtp.ilyichevsk.odessa.ua

Making diff(1) of linux kernels faster

[Paul Gortmaker]

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 -ruz orig/diffutils-2.7/diff.c diffutils-2.7/diff.c
--- orig/diffutils-2.7/diff.c	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/diff.c	Sun Oct 14 03:59:33 2001
@@ -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 -ruz orig/diffutils-2.7/diff.h diffutils-2.7/diff.h
--- orig/diffutils-2.7/diff.h	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/diff.h	Fri Oct 12 11:50:43 2001
@@ -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;
diff -ruz orig/diffutils-2.7/io.c diffutils-2.7/io.c
--- orig/diffutils-2.7/io.c	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/io.c	Fri Oct 12 11:51:55 2001
@@ -182,6 +182,64 @@
       current->buffer = xrealloc (current->buffer, current->bufsize);
     }
 }
+
+/* Preload the OS's cache with all files of one branch for recursive diffs */
+
+void
+preread (dir)
+	const char *dir;
+{
+
+  DIR *d;
+  struct dirent *dent;
+
+  d = opendir(dir);
+  if (d == NULL) return;
+
+  while ((dent = readdir(d)) != NULL)
+    {
+
+      char *name, *path;
+      struct file_data *f;
+
+      name = dent->d_name;
+      if (name[0] == '.' && (name[1] == 0 || (name[1] == '.' && name[2] == 0)))
+            continue;
+
+      f = xmalloc(sizeof(struct file_data));
+      memset(f, 0, sizeof(struct file_data));
+
+      path = xmalloc(strlen(dir)+strlen(name)+2);
+      strcpy(path, dir);
+      strcat(path, "/");
+      strcat(path, name);
+
+      if (stat(path, &f->stat) != 0)
+        {
+           free(f);
+           free(path);
+           continue;
+        }
+	
+      if (S_ISDIR(f->stat.st_mode))
+           preread(path);
+      else if (S_ISREG(f->stat.st_mode))
+        {
+          f->desc = open(path, O_RDONLY);
+          if (f->desc != -1)
+            {
+              slurp(f); 
+              if (f->bufsize != 0)
+                free(f->buffer);
+              close(f->desc);
+            }
+        } 
+      free(path);
+      free(f); 
+  }
+  closedir(d);
+}
+
 \f
 /* Split the file into lines, simultaneously computing the equivalence class for
    each line. */

Re: Making diff(1) of linux kernels faster

[john slee]

On Sun, Oct 14, 2001 at 04:58:29AM -0400, Paul Gortmaker wrote:
> 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.

-- 
R N G G   "Well, there it goes again... And we just sit 
 I G G G   here without opposable thumbs." -- gary larson

Re: Making diff(1) of linux kernels faster

[Linus Torvalds]

On Sun, 14 Oct 2001, Paul Gortmaker wrote:
>
> 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.

> 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

Re: Making diff(1) of linux kernels faster

[Paul Gortmaker]

Linus Torvalds wrote:
> 
> On Sun, 14 Oct 2001, Paul Gortmaker wrote:
> >
> > Well, I taught diff to read each tree sequentially 1st and the results
...

> Could you maybe instead of pre-reading the whole tree, just pre-read one
> directory at a time?
...

> 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 -urz orig/diffutils-2.7/diff.c diffutils-2.7/diff.c
--- orig/diffutils-2.7/diff.c	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/diff.c	Mon Oct 15 06:01:08 2001
@@ -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 -urz orig/diffutils-2.7/diff.h diffutils-2.7/diff.h
--- orig/diffutils-2.7/diff.h	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/diff.h	Mon Oct 15 05:33:57 2001
@@ -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;
diff -urz orig/diffutils-2.7/io.c diffutils-2.7/io.c
--- orig/diffutils-2.7/io.c	Thu Sep 22 12:47:00 1994
+++ diffutils-2.7/io.c	Mon Oct 15 05:38:07 2001
@@ -182,6 +182,59 @@
       current->buffer = xrealloc (current->buffer, current->bufsize);
     }
 }
+
+/* Preload the OS's cache with all files in one dir (Avoids disk seeks). */
+
+void
+preread (dir)
+	const char *dir;
+{
+
+  DIR *d;
+  struct dirent *dent;
+
+  d = opendir(dir);
+  if (d == NULL) return;
+
+  while ((dent = readdir(d)) != NULL)
+    {
+
+      char *name, *path;
+      struct file_data *f;
+
+      name = dent->d_name;
+      if (name[0] == '.' && (name[1] == 0 || (name[1] == '.' && name[2] == 0)))
+            continue;
+
+      f = xmalloc(sizeof(struct file_data));
+      memset(f, 0, sizeof(struct file_data));
+
+      path = xmalloc(strlen(dir)+strlen(name)+2);
+      strcpy(path, dir);
+      strcat(path, "/");
+      strcat(path, name);
+
+      if (stat(path, &f->stat) != 0 || !S_ISREG(f->stat.st_mode))
+        {
+           free(f);
+           free(path);
+           continue;
+        }
+	
+      f->desc = open(path, O_RDONLY);
+      if (f->desc != -1)
+        {
+          slurp(f); 
+          if (f->bufsize != 0)
+            free(f->buffer);
+          close(f->desc);
+        }
+      free(f); 
+      free(path);
+  }
+  closedir(d);
+}
+
 \f
 /* Split the file into lines, simultaneously computing the equivalence class for
    each line. */

Re: Making diff(1) of linux kernels faster

[Linus Torvalds]

On Wed, 17 Oct 2001, Paul Gortmaker wrote:
>
> 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..

> 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

Re: Making diff(1) of linux kernels faster

[Marcelo Tosatti]

On Wed, 17 Oct 2001, Linus Torvalds wrote:

> 
> On Wed, 17 Oct 2001, Paul Gortmaker wrote:
> >
> > 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..

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. 

Re: Making diff(1) of linux kernels faster

[Linus Torvalds]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1137 bytes --]


On Wed, 17 Oct 2001, Marcelo Tosatti wrote:
> >
> > 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

[-- Attachment #2: Type: TEXT/PLAIN, Size: 2556 bytes --]

diff -u --recursive --new-file pre3/linux/arch/i386/kernel/entry.S linux/arch/i386/kernel/entry.S
--- pre3/linux/arch/i386/kernel/entry.S	Mon Oct  8 10:39:58 2001
+++ linux/arch/i386/kernel/entry.S	Wed Oct 17 10:02:39 2001
@@ -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)
diff -u --recursive --new-file pre3/linux/include/asm-i386/unistd.h linux/include/asm-i386/unistd.h
--- pre3/linux/include/asm-i386/unistd.h	Mon Oct  8 10:40:16 2001
+++ linux/include/asm-i386/unistd.h	Wed Oct 17 10:03:03 2001
@@ -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> */
 
diff -u --recursive --new-file pre3/linux/mm/filemap.c linux/mm/filemap.c
--- pre3/linux/mm/filemap.c	Mon Oct 15 16:17:40 2001
+++ linux/mm/filemap.c	Wed Oct 17 10:21:37 2001
@@ -1520,6 +1520,53 @@
 	return retval;
 }
 
+static ssize_t do_readahead(struct file *file, unsigned long index, unsigned long nr)
+{
+	struct address_space *mapping = file->f_dentry->d_inode->i_mapping;
+	unsigned long max;
+
+	if (!mapping || !mapping->a_ops || !mapping->a_ops->readpage)
+		return -EINVAL;
+
+	/* Limit it to the size of the file.. */
+	max = (mapping->host->i_size + ~PAGE_CACHE_MASK) >> PAGE_CACHE_SHIFT;
+	if (index > max)
+		return 0;
+	max -= index;
+	if (nr > max)
+		nr = max;
+
+	/* And limit it to a sane percentage of the inactive list.. */
+	max = nr_inactive_pages / 2;
+	if (nr > max)
+		nr = max;
+
+	while (nr) {
+		page_cache_read(file, index);
+		index++;
+		nr--;
+	}
+	return 0;
+}
+
+asmlinkage ssize_t sys_readahead(int fd, loff_t offset, size_t count)
+{
+	ssize_t ret;
+	struct file *file;
+
+	ret = -EBADF;
+	file = fget(fd);
+	if (file) {
+		if (file->f_mode & FMODE_READ) {
+			unsigned long start = offset >> PAGE_CACHE_SHIFT;
+			unsigned long len = (count + ((long)offset & ~PAGE_CACHE_MASK)) >> PAGE_CACHE_SHIFT;
+			ret = do_readahead(file, start, len);
+		}
+		fput(file);
+	}
+	return ret;
+}
+
 /*
  * Read-ahead and flush behind for MADV_SEQUENTIAL areas.  Since we are
  * sure this is sequential access, we don't need a flexible read-ahead

[-- Attachment #3: Type: TEXT/PLAIN, Size: 1472 bytes --]

#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;
}

Re: Making diff(1) of linux kernels faster

[Andrea Arcangeli]

On Wed, Oct 17, 2001 at 11:21:03AM -0700, Linus Torvalds wrote:
> 
> On Wed, 17 Oct 2001, Marcelo Tosatti wrote:
> > >
> > > 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).

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

Re: Making diff(1) of linux kernels faster

[Marcelo Tosatti]

On Wed, 17 Oct 2001, Andrea Arcangeli wrote:

> On Wed, Oct 17, 2001 at 11:21:03AM -0700, Linus Torvalds wrote:
> > 
> > On Wed, 17 Oct 2001, Marcelo Tosatti wrote:
> > > >
> > > > 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).
> 
> 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.

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.

Re: Making diff(1) of linux kernels faster

[chris]

On Wed, 17 Oct 2001, Andrea Arcangeli wrote:

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

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

Re: Making diff(1) of linux kernels faster

[Andrea Arcangeli]

On Wed, Oct 17, 2001 at 10:23:37PM +0100, chris@scary.beasts.org wrote:
> 
> On Wed, 17 Oct 2001, Andrea Arcangeli wrote:
> 
> > 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.
> 
> Do the -ac kernels have the directory in pagecache patch? If not, it could

yes, -ac has it too.

> 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

Re: Making diff(1) of linux kernels faster

[Linus Torvalds]

On Wed, 17 Oct 2001 chris@scary.beasts.org 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

Re: Making diff(1) of linux kernels faster

[John Levon]

On Wed, Oct 17, 2001 at 09:59:35AM -0700, Linus Torvalds wrote:

> 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

-- 
"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

Re: Making diff(1) of linux kernels faster

[Benjamin LaHaise]

On Wed, Oct 17, 2001 at 09:59:35AM -0700, Linus Torvalds wrote:
> 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
diff -urN v2.4.13-pre3/drivers/char/mem.c foo-v2.4.13-pre3/drivers/char/mem.c
--- v2.4.13-pre3/drivers/char/mem.c	Mon Sep 24 02:16:03 2001
+++ foo-v2.4.13-pre3/drivers/char/mem.c	Wed Oct 17 15:12:59 2001
@@ -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__)

Re: Making diff(1) of linux kernels faster

[Andreas Schwab]

Paul Gortmaker <p_gortmaker@yahoo.com> 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.

-- 
Andreas Schwab                                  "And now for something
Andreas.Schwab@suse.de				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