From: Mark Wooding <mdw@distorted.org.uk>
Date: Sun, 30 Mar 2025 20:46:06 +0000 (+0100)
Subject: chain.c: Optimize storage layout.
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/wordchain/commitdiff_plain/211d5d6017e8cb5c4ccf6bbe4e5e42ff9c55a130

chain.c: Optimize storage layout.

  * Remove redundant word pointers from node types that don't need
    it.  (That's Xyla, QP-tries, and SGT's `tree234'.)  It's saves an
    indirection to find the string by knowing that it's at a fixed
    offset from the node base.

  * Pack the chain length in with the word length.
---

diff --git a/chain.c b/chain.c
index 94dc4ae..50a92b8 100644
--- a/chain.c
+++ b/chain.c
@@ -180,6 +180,7 @@ struct word {
 } word;
 
 struct node {
+
 #if USE_XYLA
   TREE_NODEPFX;
 #elif TREE == MLIB_SYM
@@ -187,17 +188,38 @@ struct node {
 # define WORDPTR(node) (SYM_NAME(node))
 # define WORDLEN(node) (SYM_LEN(node))
 #endif
+
+#if TREE == MLIB_SYM
+
+  short chlen;
+# define CHLEN(node) ((node)->chlen)
+
+#elif USE_LIBAVL
+
+  union {
+    struct word w;
+    struct { const char *p; unsigned short n; short chlen; } pack;
+  } u;
+# define WORDPTR(node) ((const char *)((node) + 1))
+# define WORDLEN(node) ((node)->u.w.n)
+# define CHLEN(node) ((node)->u.pack.chlen)
+
+#else
+
+  unsigned short wlen;
+# define WORDPTR(node) ((const char *)((node) + 1))
+# define WORDLEN(node) ((node)->wlen)
+
+  short chlen;
+# define CHLEN(node) ((node)->chlen)
+
+#endif
+
 #if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
   struct node *next;
 #endif
-#if TREE != MLIB_SYM
-  struct word w;
-# define WORDPTR(node) ((node)->w.p)
-# define WORDLEN(node) ((node)->w.n)
-#endif
+
   struct node *down, *right, *up;
-  short chlen;
-# define CHLEN(node) ((node)->chlen)
 };
 
 #define WORDMAX 64
@@ -285,17 +307,29 @@ static int word_nav(struct xyla_bt_nodecls *cls,
 #    define CHECK do ; while (0)
 #  else
 
-static const void *word_key(struct xyla_bt_nodecls *cls,
+static const void *node_key(struct xyla_bt_nodecls *cls,
 			    const struct xyla_bt_node *nn)
-  { struct node *node = (struct node *)nn; return (&node->w); }
+  { return (nn); }
+
+static int node_nav(struct xyla_bt_nodecls *cls,
+		    const struct xyla_bt_node *nn, void *k)
+{
+  const struct node *na = k, *nb = (const struct node *)nn;
+
+  return (compare_words(WORDPTR(na), WORDLEN(na), WORDPTR(nb), WORDLEN(nb)));
+}
 
 static void word_ident(struct xyla_bt_nodecls *cls,
 		       const struct xyla_bt_node *nn, FILE *fp)
-  { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
+{
+  struct node *node = (struct node *)nn;
+
+  fprintf(fp, "`%s'", WORDPTR(node));
+}
 
 static const struct xyla_bt_chkops word_ops = {
   { sizeof(word_ops), 0 },
-  { word_nav, word_key },
+  { node_nav, node_key },
   { xyla_bt_chkorder, sizeof(struct xyla_bt_ordinfo), word_ident }
 };
 struct xyla_bt_nodecls word_cls = { &word_ops.node };
@@ -405,7 +439,7 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  define INIT do ; while (0)
 
 #  define INSERT do {							\
-	tbl = Tsetl(tbl, node->w.p, node->w.n, node);			\
+	tbl = Tsetl(tbl, WORDPTR(node), WORDLEN(node), node);		\
 	INSERT_LIST;							\
    } while (0)
 
@@ -421,8 +455,8 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  define FOCUS do ; while (0)
 
 #  define GETPREFIX do {						\
-	word.n = node->w.n - 1; assert(word.n < WORDMAX);		\
-	memcpy(buf, node->w.p, word.n); buf[word.n] = 0;		\
+	word.n = WORDLEN(node) - 1; assert(word.n < WORDMAX);		\
+	memcpy(buf, WORDPTR(node), word.n); buf[word.n] = 0;		\
    } while (0)
 
 #  define LOOKUP Tgetl(tbl, buf, word.n)
@@ -430,7 +464,7 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  if QPTRIE_ITER == QPITER_LIST
 #    define FREE do {							\
 	for (node = all; node; node = next) {				\
-	  tbl = Tsetl(tbl, node->w.p, node->w.n, 0);			\
+	  tbl = Tsetl(tbl, WORDPTR(node), WORDLEN(node), 0);		\
 	  next = node->next; free(node);				\
 	}								\
 	assert(!tbl);							\
@@ -511,6 +545,13 @@ static void free_node(void *n, void *arg) { free(n); }
 	if (!tab) bail("out of memory");				\
    } while (0)
 
+#  define PREPNODE do {							\
+	node = malloc(sizeof(*node) + word.n + 1);			\
+	  if (!node) bail("out of memory");				\
+	memcpy(node + 1, buf, word.n + 1);				\
+	node->u.w.p = (const char *)(node + 1); node->u.w.n = word.n;	\
+   } while (0)
+
 #  define INSERT do {							\
 	p = TREE_PROBE(tab, node); if (!p) bail("out of memory");	\
 	if (*p != node) {						\
@@ -570,8 +611,7 @@ static void free_node(void *n, void *arg) { free(n); }
 #  define PREPNODE do {							\
 	node = malloc(sizeof(*node) + word.n + 1);			\
 	  if (!node) bail("out of memory");				\
-	node->w.p = (char *)(node + 1);					\
-	memcpy(node + 1, buf, word.n + 1); node->w.n = word.n;		\
+	memcpy(node + 1, buf, word.n + 1); node->wlen = word.n;		\
    } while (0)
 #endif