On Thu, Sep 27, 2001 at 02:00:26PM -0700, Julian Elischer wrote:
>The following patch to replace the linear array (which it realocs if too
>small)
>(which it scans linearly) with a hash-table can makle a DRASTIC change
>to how DU perfomrs for us in this environment.
Sounds good.
>I must stress that the new code is slightly slower for small numbers
>of linked files but the old algorythm is O(N^2) and so started taking
>sizable portions of whole days on our filesystems as they grew.
Note: Since this change has no impact on files with only 1 link,
'file' means 'hard-linked file' below.
The memory requirements also increase significantly - there's a
(NHASHSLOTS * sizeof(ID*) overhead and the larger ID is allocated
singly rather than in blocks. (Though the avoidance of realloc()
will help here). The increased number of malloc's also slows
processing of new files.
My guess is that much of the initial slowdown is due to the explicit
malloc/bzero of the hash array. Since all (non-broken) directories
have multiple hard-links, the hash table will be allocated in all but
degenerate cases, so I don't see any advantage in allocating it at
runtime. Try the attached instead (note - manually edited patch, use
with caution).
Note that a hash table only has a constant cost when it is sparse.
Once you get large numbers of files (>~NHASHSLOTS), the algorithm is
still O(N^2) - it's just a constant factor (~NHASHSLOTS) faster. For
very large numbers of files, you want a bigger value for NHASHSLOTS -
but that is wasteful (and increases overheads) for small numbers of
files. To efficiently support a wide range of sizes, you may need to
implement dynamic re-resizing of the hash table - though this needs a
bigger change to the code and re-hashing can be slow. 100,000 is
probably small enough not to be too expensive for small invocations
(though it's probably at the upper end). Is it big enough for the
large end (eg Vicor)?
Peter
Index: du.c
===================================================================
RCS file: /home/ncvs/src/usr.bin/du/du.c,v
retrieving revision 1.21
diff -u -r1.21 du.c
--- du.c 2001/09/04 09:43:31 1.21
+++ du.c 2001/09/27 20:57:13
@@ -2,6 +2,14 @@
* Copyright (c) 1989, 1993, 1994
* The Regents of the University of California. All rights reserved.
*
+ * This version of du has been modified by Andre de Bruin and Scott Macy for Vicor.
+ * The change is related to the handling of file links, in the official
+ * release, du keeps a simple linked list of all visited i-nodes with
+ * multiple links. This list is now implemented as a "hash table" (actually
+ * a fixed size array) with link list nodes providing a
+ * performance of up to 30% better than the original version.
+ * The only changes are in file create.c and marked with "AdB".
+ *
* This code is derived from software contributed to Berkeley by
* Chris Newcomb.
*
@@ -104,6 +112,15 @@
void ignoreclean __P((void));
int ignorep __P((FTSENT *));
+typedef struct _ID {
+ dev_t dev;
+ ino_t inode;
+ struct _ID *next;
+} ID;
+
+#define NHASHSLOTS 100000
+#define NALLOC 1024
+
int
main(argc, argv)
int argc;
@@ -310,35 +327,42 @@
}
-typedef struct _ID {
- dev_t dev;
- ino_t inode;
-} ID;
-
int
linkchk(p)
FTSENT *p;
{
static ID *files;
- static int maxfiles, nfiles;
+ static int nfiles = NALLOC;
- ID *fp, *start;
+ ID *lp;
ino_t ino;
dev_t dev;
+ int hashval;
+ static ID *ahash[NHASHSLOTS];
ino = p->fts_statp->st_ino;
dev = p->fts_statp->st_dev;
- if ((start = files) != NULL)
- for (fp = start + nfiles - 1; fp >= start; --fp)
- if (ino == fp->inode && dev == fp->dev)
- return (1);
+ hashval = ino % NHASHSLOTS;
+
+
+ /* AdB Use simple hash with linklist to record visited inodes */
+ for (lp = ahash[hashval]; lp != NULL; lp = lp->next) {
+ if (ino == lp->inode && dev == lp->dev)
+ return (1);
+ }
+
+ /* Not found, add it */
- if (nfiles == maxfiles && (files = realloc((char *)files,
- (u_int)(sizeof(ID) * (maxfiles += 128)))) == NULL)
- errx(1, "can't allocate memory");
+ if (nfiles >= NALLOC) {
+ files = malloc(sizeof(ID) * NALLOC));
+ if (files == NULL)
+ errx(1, "can't allocate memory");
+ nfiles = 0;
+ }
files[nfiles].inode = ino;
files[nfiles].dev = dev;
+ files[nfiles].next = ahash[hashval];
+ ahash[hashval] = &files[nfiles];
++nfiles;
return (0);
}
