Improve performance of makewhatis

Improve performance of makewhatis

[Wesley Moore]

Hello,

In this patch set I aimed to improve the performance of makewhatis. On
my Chimera Linux systems makewhatis -Tutf8 is run to rebuild the index
whenever a package containing man pages is installed or updated. I
noticed this took multiple seconds even on a Ryzen 9 7950X system.

Profiling showed a lot of time spent in the loops of roff_getstrn. To
speed this up I made use of hash tables. I tested the changes on several
different systems:

- OpenBSD amd64 in VM
- Linux on Raspberry Pi 4
- Linux on Ryzen 9 7950X

In each case the wall clock run time for makewhatis -Tutf8 -n showed an
reduction of between 25% and 35%.

The one caveat of this change is the roff/while/into regression test is
failing with my changes. I've tried to work out why but I don't know
roff well enough understand the intent of the test nor have I been able
to clearly determine why my changes affect it. I was hoping to get some
help with this.

Regards,
Wes


--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

[PATCH 1/3] Use ohash for strtab

[Wesley Moore]

---
 roff.c     | 190 +++++++++++++++++++++++++++++++++++++++++++++--------
 roff_int.h |   6 ++
 2 files changed, 170 insertions(+), 26 deletions(-)

diff --git a/roff.c b/roff.c
index bdb0210..4e5bbf9 100644
--- a/roff.c
+++ b/roff.c
@@ -71,6 +71,14 @@ struct	roffkv {
 	struct roffkv	*next; /* next in list */
 };
 
+/*
+ * A key-value string pair used as an entry in an ohash.
+ */
+struct	roff_entry {
+	struct roffstr	 val;
+	char		 key[];
+};
+
 /*
  * A single number register as part of a singly-linked list.
  */
@@ -106,8 +114,8 @@ struct	roff {
 	int		*rstack; /* stack of inverted `ie' values */
 	struct ohash	*reqtab; /* request lookup table */
 	struct roffreg	*regtab; /* number registers */
-	struct roffkv	*strtab; /* user-defined strings & macros */
 	struct roffkv	*rentab; /* renamed strings & macros */
+	struct ohash	*strtab; /* user-defined strings & macros */
 	struct roffkv	*xmbtab; /* multi-byte trans table (`tr') */
 	struct roffstr	*xtab; /* single-byte trans table (`tr') */
 	const char	*current_string; /* value of last called user macro */
@@ -204,6 +212,7 @@ static	void		 roff_expand_patch(struct buf *, int,
 static	void		 roff_free1(struct roff *);
 static	void		 roff_freereg(struct roffreg *);
 static	void		 roff_freestr(struct roffkv *);
+static	void		 roff_free_entry(struct roff_entry *entry);
 static	size_t		 roff_getname(struct roff *, char **, int, int);
 static	int		 roff_getnum(const char *, int *, int *, int);
 static	int		 roff_getop(const char *, int *, char *);
@@ -244,6 +253,8 @@ static	void		 roff_setstr(struct roff *,
 				const char *, const char *, int);
 static	void		 roff_setstrn(struct roffkv **, const char *,
 				size_t, const char *, size_t, int);
+static	void		 roff_setentry(struct ohash *r, const char *name,
+				size_t namesz, const char *string, size_t stringsz, int append);
 static	int		 roff_shift(ROFF_ARGS);
 static	int		 roff_so(ROFF_ARGS);
 static	int		 roff_tr(ROFF_ARGS);
@@ -687,6 +698,55 @@ roffhash_find(struct ohash *htab, const char *name, size_t sz)
 	return req == NULL ? TOKEN_NONE : req->tok;
 }
 
+/* --- key-value table ---------------------------------------------------- */
+
+struct ohash *
+roff_strhash_alloc(void)
+{
+	struct ohash	*htab;
+
+	htab = mandoc_malloc(sizeof(*htab));
+	mandoc_ohash_init(htab, 6, offsetof(struct roff_entry, key));
+	return htab;
+}
+
+void
+roff_strhash_free(struct ohash *htab)
+{
+	struct roff_entry	*entry;
+	unsigned int	 slot;
+
+	if (htab == NULL)
+		return;
+	for (entry = ohash_first(htab, &slot); entry != NULL;
+	     entry = ohash_next(htab, &slot))
+		roff_free_entry(entry);
+	ohash_delete(htab);
+	free(htab);
+}
+
+struct roff_entry	*
+roff_strhash_find(struct ohash *htab, const char *name, size_t sz)
+{
+	struct roff_entry	*entry;
+	const char	*end;
+
+	if (sz) {
+		end = name + sz;
+		entry = ohash_find(htab, ohash_qlookupi(htab, name, &end));
+	} else
+		entry = ohash_find(htab, ohash_qlookup(htab, name));
+	return entry;
+}
+
+void
+roff_strhash_insert(struct ohash *htab, struct roff_entry *entry) {
+	unsigned int slot;
+
+	slot = ohash_qlookup(htab, entry->key);
+	ohash_insert(htab, slot, entry);
+}
+
 /* --- stack of request blocks -------------------------------------------- */
 
 /*
@@ -757,10 +817,11 @@ roff_free1(struct roff *r)
 	roff_freereg(r->regtab);
 	r->regtab = NULL;
 
-	roff_freestr(r->strtab);
+	roff_strhash_free(r->strtab);
 	roff_freestr(r->rentab);
 	roff_freestr(r->xmbtab);
-	r->strtab = r->rentab = r->xmbtab = NULL;
+	r->strtab = NULL;
+	r->rentab = r->xmbtab = NULL;
 
 	if (r->xtab)
 		for (i = 0; i < 128; i++)
@@ -773,6 +834,7 @@ void
 roff_reset(struct roff *r)
 {
 	roff_free1(r);
+	r->strtab = roff_strhash_alloc();
 	r->options |= MPARSE_COMMENT;
 	r->format = r->options & (MPARSE_MDOC | MPARSE_MAN);
 	r->control = '\0';
@@ -803,6 +865,7 @@ roff_alloc(int options)
 
 	r = mandoc_calloc(1, sizeof(struct roff));
 	r->reqtab = roffhash_alloc(0, ROFF_RENAMED);
+	r->strtab = roff_strhash_alloc();
 	r->options = options | MPARSE_COMMENT;
 	r->format = options & (MPARSE_MDOC | MPARSE_MAN);
 	r->mstackpos = -1;
@@ -1458,7 +1521,7 @@ roff_expand(struct roff *r, struct buf *buf, int ln, int pos, char ec)
 			if (iendarg - iarg == 2 &&
 			    buf->buf[iarg] == '.' &&
 			    buf->buf[iarg + 1] == 'T') {
-				roff_setstrn(&r->strtab, ".T", 2, NULL, 0, 0);
+				roff_setentry(r->strtab, ".T", 2, NULL, 0, 0);
 				pos = iend;
 				continue;
 			}
@@ -2021,8 +2084,8 @@ roff_parse(struct roff *r, char *buf, int *pos, int ln, int ppos)
 		*pos = cp - buf;
 	else if (deftype == ROFFDEF_UNDEF) {
 		/* Using an undefined macro defines it to be empty. */
-		roff_setstrn(&r->strtab, mac, maclen, "", 0, 0);
 		roff_setstrn(&r->rentab, mac, maclen, NULL, 0, 0);
+		roff_setentry(r->strtab, mac, maclen, "", 0, 0);
 	}
 	return t;
 }
@@ -2189,21 +2252,21 @@ roff_block(ROFF_ARGS)
 	 */
 
 	if (tok == ROFF_de || tok == ROFF_dei) {
-		roff_setstrn(&r->strtab, name, namesz, "", 0, 0);
 		roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
+		roff_setentry(r->strtab, name, namesz, "", 0, 0);
 	} else if (tok == ROFF_am || tok == ROFF_ami) {
 		deftype = ROFFDEF_ANY;
 		value = roff_getstrn(r, iname, namesz, &deftype);
 		switch (deftype) {  /* Before appending, ... */
 		case ROFFDEF_PRE: /* copy predefined to user-defined. */
-			roff_setstrn(&r->strtab, name, namesz,
+			roff_setentry(r->strtab, name, namesz,
 			    value, strlen(value), 0);
 			break;
 		case ROFFDEF_REN: /* call original standard macro. */
 			csz = mandoc_asprintf(&call, ".%.*s \\$* \\\"\n",
 			    (int)strlen(value), value);
-			roff_setstrn(&r->strtab, name, namesz, call, csz, 0);
 			roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
+			roff_setentry(r->strtab, name, namesz, call, csz, 0);
 			free(call);
 			break;
 		case ROFFDEF_STD:  /* rename and call standard macro. */
@@ -2211,7 +2274,7 @@ roff_block(ROFF_ARGS)
 			roff_setstrn(&r->rentab, rname, rsz, name, namesz, 0);
 			csz = mandoc_asprintf(&call, ".%.*s \\$* \\\"\n",
 			    (int)rsz, rname);
-			roff_setstrn(&r->strtab, name, namesz, call, csz, 0);
+			roff_setentry(r->strtab, name, namesz, call, csz, 0);
 			free(call);
 			free(rname);
 			break;
@@ -2787,7 +2850,7 @@ roff_ds(ROFF_ARGS)
 		string++;
 
 	/* The rest is the value. */
-	roff_setstrn(&r->strtab, name, namesz, string, strlen(string),
+	roff_setentry(r->strtab, name, namesz, string, strlen(string),
 	    ROFF_as == tok);
 	roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
 	return ROFF_IGN;
@@ -3218,8 +3281,8 @@ roff_rm(ROFF_ARGS)
 	while (*cp != '\0') {
 		name = cp;
 		namesz = roff_getname(r, &cp, ln, (int)(cp - buf->buf));
-		roff_setstrn(&r->strtab, name, namesz, NULL, 0, 0);
 		roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
+		roff_setentry(r->strtab, name, namesz, NULL, 0, 0);
 		if (name[namesz] == '\\' || name[namesz] == '\t')
 			break;
 	}
@@ -3565,8 +3628,8 @@ roff_als(ROFF_ARGS)
 
 	valsz = mandoc_asprintf(&value, ".%.*s \\$@\\\"\n",
 	    (int)oldsz, oldn);
-	roff_setstrn(&r->strtab, newn, newsz, value, valsz, 0);
 	roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
+	roff_setentry(r->strtab, newn, newsz, value, valsz, 0);
 	free(value);
 	return ROFF_IGN;
 }
@@ -3849,26 +3912,26 @@ roff_rn(ROFF_ARGS)
 	value = roff_getstrn(r, oldn, oldsz, &deftype);
 	switch (deftype) {
 	case ROFFDEF_USER:
-		roff_setstrn(&r->strtab, newn, newsz, value, strlen(value), 0);
-		roff_setstrn(&r->strtab, oldn, oldsz, NULL, 0, 0);
 		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->strtab, newn, newsz, value, strlen(value), 0);
+		roff_setentry(r->strtab, oldn, oldsz, NULL, 0, 0);
 		break;
 	case ROFFDEF_PRE:
-		roff_setstrn(&r->strtab, newn, newsz, value, strlen(value), 0);
 		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->strtab, newn, newsz, value, strlen(value), 0);
 		break;
 	case ROFFDEF_REN:
 		roff_setstrn(&r->rentab, newn, newsz, value, strlen(value), 0);
 		roff_setstrn(&r->rentab, oldn, oldsz, NULL, 0, 0);
-		roff_setstrn(&r->strtab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
 		break;
 	case ROFFDEF_STD:
 		roff_setstrn(&r->rentab, newn, newsz, oldn, oldsz, 0);
-		roff_setstrn(&r->strtab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
 		break;
 	default:
-		roff_setstrn(&r->strtab, newn, newsz, NULL, 0, 0);
 		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
 		break;
 	}
 	return ROFF_IGN;
@@ -4102,7 +4165,7 @@ roff_setstr(struct roff *r, const char *name, const char *string,
 	size_t	 namesz;
 
 	namesz = strlen(name);
-	roff_setstrn(&r->strtab, name, namesz, string,
+	roff_setentry(r->strtab, name, namesz, string,
 	    string ? strlen(string) : 0, append);
 	roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
 }
@@ -4179,25 +4242,93 @@ roff_setstrn(struct roffkv **r, const char *name, size_t namesz,
 	n->val.sz = (int)(c - n->val.p);
 }
 
+static void
+roff_setentry(struct ohash *r, const char *name, size_t namesz,
+		const char *string, size_t stringsz, int append)
+{
+	struct roff_entry	*entry;
+	char			*c;
+	int			 i;
+	size_t			 oldch, newch;
+
+	/* Search for an existing string with the same name. */
+	entry = roff_strhash_find(r, name, namesz);
+	if (NULL == entry) {
+		/* Create a new string table entry. */
+		entry = mandoc_malloc(sizeof(*entry) + namesz + 1);
+		memcpy(entry->key, name, namesz);
+		entry->key[namesz] = '\0';
+
+		entry->val.p = NULL;
+		entry->val.sz = 0;
+		roff_strhash_insert(r, entry);
+	} else if (0 == append) {
+		/* string is already in hash table, free it in
+		 * preparation for updating.
+		 */
+		free(entry->val.p);
+		entry->val.p = NULL;
+		entry->val.sz = 0;
+	}
+
+	if (NULL == string)
+		return;
+
+	/*
+	 * One additional byte for the '\n' in multiline mode,
+	 * and one for the terminating '\0'.
+	 */
+	newch = stringsz + (1 < append ? 2u : 1u);
+
+	if (NULL == entry->val.p) {
+		entry->val.p = mandoc_malloc(newch);
+		*entry->val.p = '\0';
+		oldch = 0;
+	} else {
+		oldch = entry->val.sz;
+		entry->val.p = mandoc_realloc(entry->val.p, oldch + newch);
+	}
+
+	/* Skip existing content in the destination buffer. */
+	c = entry->val.p + (int)oldch;
+
+	/* Append new content to the destination buffer. */
+	i = 0;
+	while (i < (int)stringsz) {
+		/*
+		 * Rudimentary roff copy mode:
+		 * Handle escaped backslashes.
+		 */
+		if ('\\' == string[i] && '\\' == string[i + 1])
+			i++;
+		*c++ = string[i++];
+	}
+
+	/* Append terminating bytes. */
+	if (1 < append)
+		*c++ = '\n';
+
+	*c = '\0';
+	entry->val.sz = (int)(c - entry->val.p);
+}
+
 static const char *
 roff_getstrn(struct roff *r, const char *name, size_t len,
     int *deftype)
 {
 	const struct roffkv	*n;
 	int			 found, i;
+	const struct roff_entry	*entry;
 	enum roff_tok		 tok;
 
 	found = 0;
-	for (n = r->strtab; n != NULL; n = n->next) {
-		if (strncmp(name, n->key.p, len) != 0 ||
-		    n->key.p[len] != '\0' || n->val.p == NULL)
-			continue;
+	entry = roff_strhash_find(r->strtab, name, len);
+	if (entry != NULL && entry->val.p != NULL) {
 		if (*deftype & ROFFDEF_USER) {
 			*deftype = ROFFDEF_USER;
-			return n->val.p;
+			return entry->val.p;
 		} else {
 			found = 1;
-			break;
 		}
 	}
 	for (n = r->rentab; n != NULL; n = n->next) {
@@ -4265,8 +4396,8 @@ roff_getstrn(struct roff *r, const char *name, size_t len,
 
 		/* Using an undefined string defines it to be empty. */
 
-		roff_setstrn(&r->strtab, name, len, "", 0, 0);
 		roff_setstrn(&r->rentab, name, len, NULL, 0, 0);
+		roff_setentry(r->strtab, name, len, "", 0, 0);
 	}
 
 	*deftype = 0;
@@ -4286,6 +4417,13 @@ roff_freestr(struct roffkv *r)
 	}
 }
 
+static void
+roff_free_entry(struct roff_entry *entry)
+{
+	free(entry->val.p);
+	free(entry);
+}
+
 /* --- accessors and utility functions ------------------------------------ */
 
 /*
diff --git a/roff_int.h b/roff_int.h
index a26afa9..b18a782 100644
--- a/roff_int.h
+++ b/roff_int.h
@@ -19,6 +19,7 @@
  */
 
 struct	ohash;
+struct	roff_entry;
 struct	roff_node;
 struct	roff_meta;
 struct	roff;
@@ -82,6 +83,11 @@ struct ohash	 *roffhash_alloc(enum roff_tok, enum roff_tok);
 enum roff_tok	  roffhash_find(struct ohash *, const char *, size_t);
 void		  roffhash_free(struct ohash *);
 
+struct ohash	 *roff_strhash_alloc(void);
+struct roff_entry*roff_strhash_find(struct ohash *htab, const char *name, size_t sz);
+void		  roff_strhash_insert(struct ohash *htab, struct roff_entry *entry);
+void		  roff_strhash_free(struct ohash *htab);
+
 enum mandoc_esc	  roff_escape(const char *, const int, const int,
 			int *, int *, int *, int *, int *);
 void		  roff_state_reset(struct roff_man *);
-- 
2.42.1

--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

[PATCH 2/3] Use ohash for rentab

[Wesley Moore]

---
 roff.c | 50 ++++++++++++++++++++++++--------------------------
 1 file changed, 24 insertions(+), 26 deletions(-)

diff --git a/roff.c b/roff.c
index 4e5bbf9..74afaab 100644
--- a/roff.c
+++ b/roff.c
@@ -114,8 +114,8 @@ struct	roff {
 	int		*rstack; /* stack of inverted `ie' values */
 	struct ohash	*reqtab; /* request lookup table */
 	struct roffreg	*regtab; /* number registers */
-	struct roffkv	*rentab; /* renamed strings & macros */
 	struct ohash	*strtab; /* user-defined strings & macros */
+	struct ohash	*rentab; /* renamed strings & macros */
 	struct roffkv	*xmbtab; /* multi-byte trans table (`tr') */
 	struct roffstr	*xtab; /* single-byte trans table (`tr') */
 	const char	*current_string; /* value of last called user macro */
@@ -818,10 +818,10 @@ roff_free1(struct roff *r)
 	r->regtab = NULL;
 
 	roff_strhash_free(r->strtab);
-	roff_freestr(r->rentab);
+	roff_strhash_free(r->rentab);
 	roff_freestr(r->xmbtab);
-	r->strtab = NULL;
-	r->rentab = r->xmbtab = NULL;
+	r->strtab = r->rentab = NULL;
+	r->xmbtab = NULL;
 
 	if (r->xtab)
 		for (i = 0; i < 128; i++)
@@ -835,6 +835,7 @@ roff_reset(struct roff *r)
 {
 	roff_free1(r);
 	r->strtab = roff_strhash_alloc();
+	r->rentab = roff_strhash_alloc();
 	r->options |= MPARSE_COMMENT;
 	r->format = r->options & (MPARSE_MDOC | MPARSE_MAN);
 	r->control = '\0';
@@ -866,6 +867,7 @@ roff_alloc(int options)
 	r = mandoc_calloc(1, sizeof(struct roff));
 	r->reqtab = roffhash_alloc(0, ROFF_RENAMED);
 	r->strtab = roff_strhash_alloc();
+	r->rentab = roff_strhash_alloc();
 	r->options = options | MPARSE_COMMENT;
 	r->format = options & (MPARSE_MDOC | MPARSE_MAN);
 	r->mstackpos = -1;
@@ -2084,8 +2086,8 @@ roff_parse(struct roff *r, char *buf, int *pos, int ln, int ppos)
 		*pos = cp - buf;
 	else if (deftype == ROFFDEF_UNDEF) {
 		/* Using an undefined macro defines it to be empty. */
-		roff_setstrn(&r->rentab, mac, maclen, NULL, 0, 0);
 		roff_setentry(r->strtab, mac, maclen, "", 0, 0);
+		roff_setentry(r->rentab, mac, maclen, NULL, 0, 0);
 	}
 	return t;
 }
@@ -2252,8 +2254,8 @@ roff_block(ROFF_ARGS)
 	 */
 
 	if (tok == ROFF_de || tok == ROFF_dei) {
-		roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
 		roff_setentry(r->strtab, name, namesz, "", 0, 0);
+		roff_setentry(r->rentab, name, namesz, NULL, 0, 0);
 	} else if (tok == ROFF_am || tok == ROFF_ami) {
 		deftype = ROFFDEF_ANY;
 		value = roff_getstrn(r, iname, namesz, &deftype);
@@ -2265,13 +2267,13 @@ roff_block(ROFF_ARGS)
 		case ROFFDEF_REN: /* call original standard macro. */
 			csz = mandoc_asprintf(&call, ".%.*s \\$* \\\"\n",
 			    (int)strlen(value), value);
-			roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
 			roff_setentry(r->strtab, name, namesz, call, csz, 0);
+			roff_setentry(r->rentab, name, namesz, NULL, 0, 0);
 			free(call);
 			break;
 		case ROFFDEF_STD:  /* rename and call standard macro. */
 			rsz = mandoc_asprintf(&rname, "__%s_renamed", name);
-			roff_setstrn(&r->rentab, rname, rsz, name, namesz, 0);
+			roff_setentry(r->rentab, rname, rsz, name, namesz, 0);
 			csz = mandoc_asprintf(&call, ".%.*s \\$* \\\"\n",
 			    (int)rsz, rname);
 			roff_setentry(r->strtab, name, namesz, call, csz, 0);
@@ -2852,7 +2854,7 @@ roff_ds(ROFF_ARGS)
 	/* The rest is the value. */
 	roff_setentry(r->strtab, name, namesz, string, strlen(string),
 	    ROFF_as == tok);
-	roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
+	roff_setentry(r->rentab, name, namesz, NULL, 0, 0);
 	return ROFF_IGN;
 }
 
@@ -3281,8 +3283,8 @@ roff_rm(ROFF_ARGS)
 	while (*cp != '\0') {
 		name = cp;
 		namesz = roff_getname(r, &cp, ln, (int)(cp - buf->buf));
-		roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
 		roff_setentry(r->strtab, name, namesz, NULL, 0, 0);
+		roff_setentry(r->rentab, name, namesz, NULL, 0, 0);
 		if (name[namesz] == '\\' || name[namesz] == '\t')
 			break;
 	}
@@ -3628,8 +3630,8 @@ roff_als(ROFF_ARGS)
 
 	valsz = mandoc_asprintf(&value, ".%.*s \\$@\\\"\n",
 	    (int)oldsz, oldn);
-	roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
 	roff_setentry(r->strtab, newn, newsz, value, valsz, 0);
+	roff_setentry(r->rentab, newn, newsz, NULL, 0, 0);
 	free(value);
 	return ROFF_IGN;
 }
@@ -3912,26 +3914,26 @@ roff_rn(ROFF_ARGS)
 	value = roff_getstrn(r, oldn, oldsz, &deftype);
 	switch (deftype) {
 	case ROFFDEF_USER:
-		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
 		roff_setentry(r->strtab, newn, newsz, value, strlen(value), 0);
 		roff_setentry(r->strtab, oldn, oldsz, NULL, 0, 0);
+		roff_setentry(r->rentab, newn, newsz, NULL, 0, 0);
 		break;
 	case ROFFDEF_PRE:
-		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
 		roff_setentry(r->strtab, newn, newsz, value, strlen(value), 0);
+		roff_setentry(r->rentab, newn, newsz, NULL, 0, 0);
 		break;
 	case ROFFDEF_REN:
-		roff_setstrn(&r->rentab, newn, newsz, value, strlen(value), 0);
-		roff_setstrn(&r->rentab, oldn, oldsz, NULL, 0, 0);
+		roff_setentry(r->rentab, newn, newsz, value, strlen(value), 0);
+		roff_setentry(r->rentab, oldn, oldsz, NULL, 0, 0);
 		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
 		break;
 	case ROFFDEF_STD:
-		roff_setstrn(&r->rentab, newn, newsz, oldn, oldsz, 0);
+		roff_setentry(r->rentab, newn, newsz, oldn, oldsz, 0);
 		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
 		break;
 	default:
-		roff_setstrn(&r->rentab, newn, newsz, NULL, 0, 0);
 		roff_setentry(r->strtab, newn, newsz, NULL, 0, 0);
+		roff_setentry(r->rentab, newn, newsz, NULL, 0, 0);
 		break;
 	}
 	return ROFF_IGN;
@@ -4167,7 +4169,7 @@ roff_setstr(struct roff *r, const char *name, const char *string,
 	namesz = strlen(name);
 	roff_setentry(r->strtab, name, namesz, string,
 	    string ? strlen(string) : 0, append);
-	roff_setstrn(&r->rentab, name, namesz, NULL, 0, 0);
+	roff_setentry(r->rentab, name, namesz, NULL, 0, 0);
 }
 
 static void
@@ -4316,7 +4318,6 @@ static const char *
 roff_getstrn(struct roff *r, const char *name, size_t len,
     int *deftype)
 {
-	const struct roffkv	*n;
 	int			 found, i;
 	const struct roff_entry	*entry;
 	enum roff_tok		 tok;
@@ -4331,16 +4332,13 @@ roff_getstrn(struct roff *r, const char *name, size_t len,
 			found = 1;
 		}
 	}
-	for (n = r->rentab; n != NULL; n = n->next) {
-		if (strncmp(name, n->key.p, len) != 0 ||
-		    n->key.p[len] != '\0' || n->val.p == NULL)
-			continue;
+	entry = roff_strhash_find(r->rentab, name, len);
+	if (entry != NULL && entry->val.p != NULL) {
 		if (*deftype & ROFFDEF_REN) {
 			*deftype = ROFFDEF_REN;
-			return n->val.p;
+			return entry->val.p;
 		} else {
 			found = 1;
-			break;
 		}
 	}
 	for (i = 0; i < PREDEFS_MAX; i++) {
@@ -4396,8 +4394,8 @@ roff_getstrn(struct roff *r, const char *name, size_t len,
 
 		/* Using an undefined string defines it to be empty. */
 
-		roff_setstrn(&r->rentab, name, len, NULL, 0, 0);
 		roff_setentry(r->strtab, name, len, "", 0, 0);
+		roff_setentry(r->rentab, name, len, NULL, 0, 0);
 	}
 
 	*deftype = 0;
-- 
2.42.1

--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

[PATCH 3/3] Use ohash for predefined strings

[Wesley Moore]

---
 roff.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

diff --git a/roff.c b/roff.c
index 74afaab..ff85a63 100644
--- a/roff.c
+++ b/roff.c
@@ -113,6 +113,7 @@ struct	roff {
 	struct mctx	*mstack; /* stack of macro contexts */
 	int		*rstack; /* stack of inverted `ie' values */
 	struct ohash	*reqtab; /* request lookup table */
+	struct ohash	*pretab; /* predefined strings table */
 	struct roffreg	*regtab; /* number registers */
 	struct ohash	*strtab; /* user-defined strings & macros */
 	struct ohash	*rentab; /* renamed strings & macros */
@@ -241,6 +242,7 @@ static	int		 roff_parse_comment(struct roff *, struct buf *,
 				int, int, char);
 static	int		 roff_parsetext(struct roff *, struct buf *,
 				int, int *);
+static	struct ohash	*roff_pretab_alloc(void);
 static	int		 roff_renamed(ROFF_ARGS);
 static	int		 roff_req_or_macro(ROFF_ARGS);
 static	int		 roff_return(ROFF_ARGS);
@@ -700,6 +702,21 @@ roffhash_find(struct ohash *htab, const char *name, size_t sz)
 
 /* --- key-value table ---------------------------------------------------- */
 
+struct ohash *
+roff_pretab_alloc(void)
+{
+	int i;
+	struct ohash *htab;
+	struct predef pre;
+
+	htab = roff_strhash_alloc();
+	for (i = 0; i < PREDEFS_MAX; i++) {
+		pre = predefs[i];
+		roff_setentry(htab, pre.name, strlen(pre.name), pre.str, strlen(pre.str), 0);
+	}
+	return htab;
+}
+
 struct ohash *
 roff_strhash_alloc(void)
 {
@@ -852,6 +869,7 @@ roff_free(struct roff *r)
 	int		 i;
 
 	roff_free1(r);
+	roff_strhash_free(r->pretab);
 	for (i = 0; i < r->mstacksz; i++)
 		free(r->mstack[i].argv);
 	free(r->mstack);
@@ -866,6 +884,7 @@ roff_alloc(int options)
 
 	r = mandoc_calloc(1, sizeof(struct roff));
 	r->reqtab = roffhash_alloc(0, ROFF_RENAMED);
+	r->pretab = roff_pretab_alloc();
 	r->strtab = roff_strhash_alloc();
 	r->rentab = roff_strhash_alloc();
 	r->options = options | MPARSE_COMMENT;
@@ -4318,8 +4337,8 @@ static const char *
 roff_getstrn(struct roff *r, const char *name, size_t len,
     int *deftype)
 {
-	int			 found, i;
 	const struct roff_entry	*entry;
+	int			 found;
 	enum roff_tok		 tok;
 
 	found = 0;
@@ -4341,16 +4360,13 @@ roff_getstrn(struct roff *r, const char *name, size_t len,
 			found = 1;
 		}
 	}
-	for (i = 0; i < PREDEFS_MAX; i++) {
-		if (strncmp(name, predefs[i].name, len) != 0 ||
-		    predefs[i].name[len] != '\0')
-			continue;
+	entry = roff_strhash_find(r->pretab, name, len);
+	if (entry != NULL) {
 		if (*deftype & ROFFDEF_PRE) {
 			*deftype = ROFFDEF_PRE;
-			return predefs[i].str;
+			return entry->val.p;
 		} else {
 			found = 1;
-			break;
 		}
 	}
 	if (r->man->meta.macroset != MACROSET_MAN) {
-- 
2.42.1

--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

Re: Improve performance of makewhatis

[Ingo Schwarze]

Hi Wesley,

Wesley Moore wrote on Mon, Nov 13, 2023 at 11:42:42AM +1000:

> In this patch set I aimed to improve the performance of makewhatis.
> On my Chimera Linux systems

Interesting.  I just added Chimera Linux to these two pages:

  https://mandoc.bsd.lv/ports.html
  https://mandoc.bsd.lv/porthistory.html

Can you confirm that these statements are accurate?

 * Chimera Linux includes mandoc in its base system since 2021 Oct 30.
 * There were no official nor unofficial packages of mandoc
   for Chimera Linux before that.
 * It uses the mandoc(1) parsing and formatting engine by default
   since the same date.
 * The default apropos(1) program is mandoc since the same date.
 * The default man(1) program is mandoc since the same date.
 * Chimera Linux does not provide an officially supported
   alternative for the man(1) program that users can select.
 * Chimera Linux does not publish its manual pages on the web
   on a site similar to https://manpages.debian.org/
   or https://man.openbsd.org/ or https://man.voidlinux.org/ .

> makewhatis -Tutf8 is run to rebuild the index
> whenever a package containing man pages is installed or updated.

That's not particularly smart.  Rebuilding the whole database from
scratch is unavoidably slow.  The makewhatis(8) options -d and -u
are specifically provided to serve the needs of package management
systems.  Specifically, if a package management systems cares about
performance, it can use -d to add just those manual page files it
just installed to the existing database, rather than rebuilding the
whole database from scratch, which obviously implies reading every
manual page file in the whole system from disk and parsing all those
files.

> I noticed this took multiple seconds even on a Ryzen 9 7950X system.

That may not be a major problem because installing an additional
package is not usually a fast operation (it usually requires both
network access and expensive database locking and management outside
the domain of manual pages) and it isn't done often either.

So i expect most users won't feel offended if installing new
software takes a few seconds.

> Profiling showed a lot of time spent in the loops of roff_getstrn.

Hmm, even though i'm not convinced your usecase is particularly
important, that's interesting, and i wouldn't have expected it.
It may be worth looking into that.

> To speed this up I made use of hash tables. I tested the changes on
> several different systems:
> 
> - OpenBSD amd64 in VM
> - Linux on Raspberry Pi 4
> - Linux on Ryzen 9 7950X
> 
> In each case the wall clock run time for makewhatis -Tutf8 -n showed
> an reduction of between 25% and 35%.

For makewhatis(8), i would say that's such a small gain that it likely
isn't worth much complication.  Then again, it also affects mandoc(1),
so maybe looking into it is worthwhile after all.

Here is what i found with gprof(1) on OpenBSD-current:

share local
 100%  100% main -> mandocdb
  92%   95% (mandocdb) -> mpages_merge
  66%   67% (mpages_merge) -> mparse_readfd -> mparse_buf_r
  32%   26% (mparse_buf_r) -> roff_parseln
  19%   21% MANY -> free -> ofree
16.3%  2.5% (mparse_buf_r) -> mdoc_parseln
 6.8% 18.4% (mparse_buf_r) -> man_parseln
15.6% 14.7% MANY -> roff_word_alloc
14.9% 17.0% (_libc_malloc etc) -> omalloc
14.7% 10.9% (mpages_merge) -> mparse_reset
14.6% 10.6% (roff_parse, roff_expand) -> roff_getstrn

The "share" column refers to /usr/share/man/, i.e. the OpenBSD base
system manuals, a good example of a large, mdoc(7)-heavy collection
of manual pages.  The "local" column refers to /usr/local/man/,
i.e. the optional third-party software i happen to have installed,
which contains mostly man(7) manual pages.

On each line, the two numbers give the time spent in the respective
function including functions called from it, relative to the time
spent in main() including all functions called from there.
The last name on each line is the respective function.
The names before the arrows specify from where it is usually called.

So only 10-15% of the time is spent in roff_getstrn(), which cannot
possibly result in the 25-35% overall speedup you report, so something
looks fishy here.  Then again, even 25-35% is not a large gain.

In general, improving the structure is much more important than
improving the performance because the code has grown historically,
becoming more and more complicated and less and less uniform in
structure, i.e. harder and harder to maintain.  In particular, such
a small gain is clearly not worth further complication.

On the other hand, the critical code path for the optimization
potential you found is:  roff_parse -> roff_getstrn
In that area, code structure is not particularly good.
Parsing for macros and strings is done in various different ways:

 1. The code path roff_parse -> roff_getstrn looks for
    user-defined and renamed macros using r->strtab and r->rentab.
 2. The code path roff_expand -> roff_getstrn looks for
    predefined strings using a linear search in predefs[].
 3. The code paths roff_block(ROFF_am) -> roff_getstrn and
    roff_rn -> roff_getstrn look for standard high-level macros
    directly in the roff_name[] array.
 4. The functions mdoc_pmacro() in mdoc.c and man_pmacro() in man.c
    look for standard high-level macros using local mdoc->mdocmac
    and man->manmac hash tables with roffhash_find().

So it is likely this can be better structured with less duplication
and not gratuitiously using different data structures, while also
using hash tables for macro and string lookup throughout.

> The one caveat of this change is the roff/while/into regression test is
> failing with my changes. I've tried to work out why but I don't know
> roff well enough understand the intent of the test nor have I been able
> to clearly determine why my changes affect it. I was hoping to get some
> help with this.

The roff/while/into test uses .de in a very strange way, and .de
internally uses the string storage, so that's how it may be related,
but i would have to look at the details.  Then again, studying that
is not urgent because your patch is definitely not ready for commit.
It adds complication rather than removing some.  In particular:

 * Do not touch roff_int.h.  It is only intended for internal API
   features needed by more than one parser, see mandoc_headers(3)
   for details, but what you are doing here is local to the roff
   parser (roff.c).
 * struct roff_entry is essentially the same as struct roffkv.
   There should not be two data structures for the same purpose.
 * roff_free_entry() is trivial and only used at one place,
   so it should be inlined.
 * Renaming roff_setstrn to roff_setentry causes quite some churn,
   so don't do that.  If that means using ohash for xmbtab, too,
   so be it.
 * roff_strhash_alloc is also next to trivial.  Maybe it can be
   inlined - maybe not because it is called from a few more
   places.  If we introduce it, roffhash_alloc should also
   use it.
 * The duplication between roffhash_free() and roff_strhash_free()
   and between roffhash_find() and roff_strhash_find() is rather
   ugly.  Not yet sure what to do about that.
 * roff_strhash_insert() is trivial and called only from one place.

Some ideas are also good:

 * Using struct ohash *strtab directly in struct roff is good,
   just like it is already done for struct ohash *reqtab.
 * Introducing r->pretab and clearing it in roff_free()
   rather than in the badly named roff_free1() - just like
   r->reqtab - is good.

One other thing.  I hate patch series, don't ever send them.
They are usually a symptom of poor development methodology,
and usually i reject them without even inspecting them.
Here, i made an exception because your idea seems to have some merit.

Every patch needs to
 * perform one well-defined task and
 * make the code better even if nothing else is ever committed
   building on it.

Splitting a patch like you did it here only adds obfuscation
If a patch becomes too big for review, then the *task* it performs
needs to be split into logically separate steps, rather than
splitting code changes into mutiple patch files that essentially
all save the same purpose and are similar and closely related in
their content.  Such *logical* splitting can become tricky, but
i doubt that is needed here.

I'm not yet completely sure what the best way forward is.
Probably something like:
 1. Identifying all places that do string lookup in tables or lists.
    Some can probably be left alone:
      arch.c, att.c, cgi.c, chars.c, eqn.c, mansearch.c,
      mdoc_argnames in mdoc.c, msec.c, st.c, regtab in roff.c,
      tbl_layout.c, tbl_opts.c
    But the others should probably be dealt with in a unified manner:
      reqtab, mdocmac, manmac  on the one hand
      strtab, rentab, pretab, xmbtab  on the other hand
      Not sure yet whether xtab can be included into xmbtab.
 2. Design and implement a common handling for these using ohash
    that is as simple as possible.

Not sure yet whether these are multiple steps or a single step,
but doing one separate step for every *tab is definitely not the
way.

I guess that's enough for today...

Yours,
  Ingo
--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

Re: Improve performance of makewhatis

[Wesley Moore]

Hi Ingo,

Thanks for the detailed reply.

On Wed, 15 Nov 2023, at 11:26 AM, Ingo Schwarze wrote:
>
> Can you confirm that these statements are accurate?
>
>  * Chimera Linux includes mandoc in its base system since 2021 Oct 30.

That's correct.

>  * There were no official nor unofficial packages of mandoc
>    for Chimera Linux before that.

Yes that's right.

>  * It uses the mandoc(1) parsing and formatting engine by default
>    since the same date.

Yes (pretty much). It looks like it was added a day later
https://github.com/chimera-linux/cports/commit/3c493733f7f0df345816cc69e273fca32fe70830

>  * The default apropos(1) program is mandoc since the same date.
>  * The default man(1) program is mandoc since the same date.
>  * Chimera Linux does not provide an officially supported
>    alternative for the man(1) program that users can select.
>  * Chimera Linux does not publish its manual pages on the web
>    on a site similar to https://manpages.debian.org/
>    or https://man.openbsd.org/ or https://man.voidlinux.org/ .

Yes all of above are correct.

>> makewhatis -Tutf8 is run to rebuild the index
>> whenever a package containing man pages is installed or updated.

>> I noticed this took multiple seconds even on a Ryzen 9 7950X system.
>
> That may not be a major problem because installing an additional
> package is not usually a fast operation (it usually requires both
> network access and expensive database locking and management outside
> the domain of manual pages) and it isn't done often either.
>
> So i expect most users won't feel offended if installing new
> software takes a few seconds.

Perhaps that is the case but it bothered me enough to go to the effort of writing these patches...

[snip]

> So only 10-15% of the time is spent in roff_getstrn(), which cannot
> possibly result in the 25-35% overall speedup you report, so something
> looks fishy here.  Then again, even 25-35% is not a large gain.

Those are the numbers I saw from my basic benchmarking measuring the wall clock time of makewhatis -Tutf -n across three runs and averaging the results for each machine. The raw data from my notes is available here:

https://gist.github.com/wezm/4043bde0dc2974c88b7706c60b58f900

[snip]

> One other thing.  I hate patch series, don't ever send them.
> They are usually a symptom of poor development methodology,
> and usually i reject them without even inspecting them.
> Here, i made an exception because your idea seems to have some merit.
>
> Every patch needs to
>  * perform one well-defined task and
>  * make the code better even if nothing else is ever committed
>    building on it.
>
> Splitting a patch like you did it here only adds obfuscation
> If a patch becomes too big for review, then the *task* it performs
> needs to be split into logically separate steps, rather than
> splitting code changes into mutiple patch files that essentially
> all save the same purpose and are similar and closely related in
> their content.  Such *logical* splitting can become tricky, but
> i doubt that is needed here.

Sorry about that. While I've been programming for a couple of decades the email based patch workflow is very new to me and different to all my experience to date. If I post any more changes I'll be sure to follow your suggestions.

> I'm not yet completely sure what the best way forward is.
> Probably something like:
>  1. Identifying all places that do string lookup in tables or lists.
>     Some can probably be left alone:
>       arch.c, att.c, cgi.c, chars.c, eqn.c, mansearch.c,
>       mdoc_argnames in mdoc.c, msec.c, st.c, regtab in roff.c,
>       tbl_layout.c, tbl_opts.c
>     But the others should probably be dealt with in a unified manner:
>       reqtab, mdocmac, manmac  on the one hand
>       strtab, rentab, pretab, xmbtab  on the other hand
>       Not sure yet whether xtab can be included into xmbtab.
>  2. Design and implement a common handling for these using ohash
>     that is as simple as possible.

When I have a moment I'll take a look through these and try to come up with an approach/plan and post it for feedback before making code changes.

> Not sure yet whether these are multiple steps or a single step,
> but doing one separate step for every *tab is definitely not the
> way.
>
> I guess that's enough for today...
>
> Yours,
>   Ingo

Wes
--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv

Re: Improve performance of makewhatis

[Ingo Schwarze]

Hi Wesley,

Wesley Moore wrote on Wed, Nov 15, 2023 at 06:29:15PM +1000:
> On Wed, 15 Nov 2023, at 11:26 AM, Ingo Schwarze wrote:

[...]
>>  * It uses the mandoc(1) parsing and formatting engine by default
>>    since the same date.

> Yes (pretty much). It looks like it was added a day later
> https://github.com/chimera-linux/cports/commit/3c493733f7f0df345816cc69e273fca32fe70830

Ah, being unfamiliar with the Chimera Linux packaging system,
i did not find that commit.  I just added HTML comments referencing
the two commit hashes to  https://mandoc.bsd.lv/ports.html .

It appears the dates are already correct, though,
Github lists both commits as "Oct 30, 2021".

[...]
>> So i expect most users won't feel offended if installing new
>> software takes a few seconds.

> Perhaps that is the case but it bothered me enough to go to the
> effort of writing these patches...

:-)

> [snip]
>> So only 10-15% of the time is spent in roff_getstrn(), which cannot
>> possibly result in the 25-35% overall speedup you report, so something
>> looks fishy here.  Then again, even 25-35% is not a large gain.

> Those are the numbers I saw from my basic benchmarking measuring the
> wall clock time of makewhatis -Tutf -n across three runs and averaging
> the results for each machine. The raw data from my notes is available here:
> 
> https://gist.github.com/wezm/4043bde0dc2974c88b7706c60b58f900

The first "Before" lines for OpenBSD and Raspberry are apparently
off to the upper side, possibly because the pages were not yet
in the buffer cache and had to be physically read from disk.
But even excluding these, we have

OpenBSD    3.89 -> 2.71  -30%
Raspberry  7.18 -> 5.91  -18%
Torrent    2.65 -> 1.90  -38%

which is still way above what might be possible according to my
measurements.

I'm not accusing you of lying, btw.  :-)

This could be due to bugs in mandoc, bugs in your patch, mistakes
in your or my measurement methodology, differences in the samples
of manual page trees we used, differences in the operating systems,
C libraries, or compilers we used, or differences in CFLAGS.

None of these look particularly likely causes to me.  But that only
means i have to be extra careful to not commit anything that breaks
parsing or formatting, given that we are clearly not fully understanding
what is going on.

> [snip]
>> One other thing.  I hate patch series, don't ever send them.
>> They are usually a symptom of poor development methodology,
>> and usually i reject them without even inspecting them.
>> Here, i made an exception because your idea seems to have some merit.
>>
>> Every patch needs to
>>  * perform one well-defined task and
>>  * make the code better even if nothing else is ever committed
>>    building on it.
>>
>> Splitting a patch like you did it here only adds obfuscation
>> If a patch becomes too big for review, then the *task* it performs
>> needs to be split into logically separate steps, rather than
>> splitting code changes into mutiple patch files that essentially
>> all save the same purpose and are similar and closely related in
>> their content.  Such *logical* splitting can become tricky, but
>> i doubt that is needed here.

> Sorry about that. While I've been programming for a couple of decades
> the email based patch workflow is very new to me and different to all
> my experience to date.

Sure, when working for hire, it also happened to me that i had to cope
with dubious methodologies like patch series (which encourage sloppy
design, sloppy implementation, very sloppy code review or no code review
at all) or feature branches (which encourage bit rot, logical conflicts,
integration mishaps, and sloppy and delayed merging and testing on top
of the problems of patch series).  But even if most of the biomass in a
state comes in the form of cows, that doesn't imply cows are particularly
intelligent and everybody should strive for bovinity.  ;-)

> If I post any more changes I'll be sure to follow your suggestions.

Thanks!

>> I'm not yet completely sure what the best way forward is.
>> Probably something like:
>>  1. Identifying all places that do string lookup in tables or lists.
>>     Some can probably be left alone:
>>       arch.c, att.c, cgi.c, chars.c, eqn.c, mansearch.c,
>>       mdoc_argnames in mdoc.c, msec.c, st.c, regtab in roff.c,
>>       tbl_layout.c, tbl_opts.c
>>     But the others should probably be dealt with in a unified manner:
>>       reqtab, mdocmac, manmac  on the one hand
>>       strtab, rentab, pretab, xmbtab  on the other hand
>>       Not sure yet whether xtab can be included into xmbtab.
>>  2. Design and implement a common handling for these using ohash
>>     that is as simple as possible.

> When I have a moment I'll take a look through these and try to come up
> with an approach/plan and post it for feedback before making code changes.

After consulting my pillow, i believe the following may work:

 1st step:
   Change strtab, rentab, xmbtab, roff_freestr, roff_setstrn,
   roff_getstrn, and roff_strdup to use ohash.
   That's very close to what you did in your first two patches
   but avoids any additional complication.  It's one logical
   step because it changes the way struct roffkv is used.

That likely results in the main performance gain.  Once that is
committed, we can optionally consider further steps, one by one,
for example:

 2nd step:
   Implement pretab using the facilities from step 1
   similar to what you did in your third patch.
   That's independent because predefs[] is only used by
   roff_getstrn and does not use struct roffkv yet.

 3rd step:
   Maybe unify reqtab, mdocmac, and manmac in order to resolve
   the two ugly roff_name[] loops in roff_getstrn.
   That's likely independent, too, because it won't use
   struct roffkv even in the final state of the code.

Of course, i cannot guarantee that will work - to provide such a
guarantee, i would have to do the work myself.  ;-)
But it looks promising to me, well in line with your goal,
and similar enough to your original implementation.

By the way, *if* this ends up in an amount of code that is non-trivial
in the sense of Copyright, are you OK with having

 * Copyright (c) 2023 Wesley Moore <wes@wezm.net>

Added to the relevant files and to the LICENSE file in the portable
mandoc root directory?

Yours,
  Ingo
--
 To unsubscribe send an email to tech+unsubscribe@mandoc.bsd.lv