A simple cache of uid->uname lookups and gid->gname lookups eliminates

almost 1/2 of the CPU time required to create an uncompressed archive
and makes a noticable reduction in wallclock time.

3 files changed, 60 insertions, 12 deletions

diff --git a/usr.bin/tar/bsdtar.c b/usr.bin/tar/bsdtar.c
index 0e2092b..690270f 100644
--- a/usr.bin/tar/bsdtar.c
+++ b/usr.bin/tar/bsdtar.c
@@ -115,6 +115,7 @@ main(int argc, char **argv)
 	struct bsdtar		*bsdtar, bsdtar_storage;
 	struct passwd		*pwent;
 	int			 opt;
+	int			 i;
 	char			 mode;
 	char			 buff[16];
 
@@ -390,6 +391,16 @@ main(int argc, char **argv)
 	if (bsdtar->user_uname != NULL)
 		free(bsdtar->user_uname);
 
+	for (i = 0; i < bsdtar_hash_size; i++) {
+		if (bsdtar->uname_lookup[i].uname != NULL)
+			free(bsdtar->uname_lookup[i].uname);
+	}
+
+	for (i = 0; i < bsdtar_hash_size; i++) {
+		if (bsdtar->gname_lookup[i].gname != NULL)
+			free(bsdtar->gname_lookup[i].gname);
+	}
+
 	return 0;
 }
 
diff --git a/usr.bin/tar/bsdtar.h b/usr.bin/tar/bsdtar.h
index dd37326..f11f451 100644
--- a/usr.bin/tar/bsdtar.h
+++ b/usr.bin/tar/bsdtar.h
@@ -77,6 +77,20 @@ struct bsdtar {
 
 	struct links_entry	*links_head;
 	struct archive_dir_entry *archive_dir_head, *archive_dir_tail;
+
+	/* An arbitrary prime number. */
+	#define bsdtar_hash_size 71
+	/* A simple hash of uid/uname for caching uname lookups. */
+	struct {
+		uid_t uid;
+		char *uname;
+	} uname_lookup[bsdtar_hash_size];
+
+	/* A simple hash of gid/gname for caching gname lookups. */
+	struct {
+		gid_t gid;
+		char *gname;
+	} gname_lookup[bsdtar_hash_size];
 };
 
 const char	*bsdtar_progname(void);
diff --git a/usr.bin/tar/write.c b/usr.bin/tar/write.c
index 62a3d2e..2d418da 100644
--- a/usr.bin/tar/write.c
+++ b/usr.bin/tar/write.c
@@ -934,21 +934,31 @@ setup_acls(struct bsdtar *bsdtar, struct archive_entry *entry,
 /*
  * Lookup gid from gname and uid from uname.
  *
- * TODO: Cache gname/uname lookups to improve performance on
- * large extracts.
  */
 const char *
 lookup_uname(struct bsdtar *bsdtar, uid_t uid)
 {
 	struct passwd		*pwent;
+	int slot;
 
-	(void)bsdtar; /* UNUSED */
+	slot = uid % bsdtar_hash_size;
+	if (bsdtar->uname_lookup[slot].uname != NULL) {
+		if (bsdtar->uname_lookup[slot].uid == uid)
+			return (bsdtar->uname_lookup[slot].uname);
+
+		free(bsdtar->uname_lookup[slot].uname);
+		bsdtar->uname_lookup[slot].uname = NULL;
+	}
 
 	pwent = getpwuid(uid);
-	if (pwent)
-		return (pwent->pw_name);
-	if (errno)
-		bsdtar_warnc(errno, "getpwuid(%d) failed", uid);
+	if (pwent == NULL) {
+		if (errno)
+			bsdtar_warnc(errno, "getpwuid(%d) failed", uid);
+		return (NULL);
+	} else if (pwent->pw_name != NULL && pwent->pw_name[0] != '\0') {
+		bsdtar->uname_lookup[slot].uname = strdup(pwent->pw_name);
+		bsdtar->uname_lookup[slot].uid = uid;
+	}
 	return (NULL);
 }
 
@@ -956,13 +966,26 @@ const char *
 lookup_gname(struct bsdtar *bsdtar, gid_t gid)
 {
 	struct group		*grent;
+	int slot;
+
+	slot = gid % bsdtar_hash_size;
+	if (bsdtar->gname_lookup[slot].gname != NULL) {
+		if (bsdtar->gname_lookup[slot].gid == gid)
+			return (bsdtar->gname_lookup[slot].gname);
+
+		free(bsdtar->gname_lookup[slot].gname);
+		bsdtar->gname_lookup[slot].gname = NULL;
+	}
 
-	(void)bsdtar; /* UNUSED */
 	grent = getgrgid(gid);
-	if (grent)
-		return (grent->gr_name);
-	if (errno)
-		bsdtar_warnc(errno, "getgrgid(%d) failed", gid);
+	if (grent == NULL) {
+		if (errno)
+			bsdtar_warnc(errno, "getgrgid(%d) failed", gid);
+		return (NULL);
+	} else if (grent->gr_name != NULL && grent->gr_name[0] != '\0') {
+		bsdtar->gname_lookup[slot].gname = strdup(grent->gr_name);
+		bsdtar->gname_lookup[slot].gid = gid;
+	}
 	return (NULL);
 }