From 67733cd0356ecf398135fc3f2978aabcd6900783 Mon Sep 17 00:00:00 2001
From: Ralph Corderoy <ralph@inputplus.co.uk>
Date: Tue, 25 Apr 2017 23:21:21 +0100
Subject: [PATCH] sbr/vector.c: Embed initial vector storage in header struct.

Instead of a malloc(3)'d struct bvector having a pointer to a separately
malloc'd area for the bits in the normal case of the default initial
size, have non-malloc'd storage in the struct itself, and set the
pointer to that.  It's two unsigned longs, which is less than the
previous default of 256 bits for struct bvector, but still double the
pre-bvector norm of one word on 32 and 64-bit architectures.

This halves the mallocs needed to create a struct bvector in the common
case, but does mean that embedded memory is wasted should it not be
enough.  That's probably an unusual case.  It also means derefencing the
pointer to the bits probably hits the same cache line.

Have separate initial sizes for string and int vectors.
---
 sbr/vector.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

diff --git a/sbr/vector.c b/sbr/vector.c
index 9a97e319..e975e271 100644
--- a/sbr/vector.c
+++ b/sbr/vector.c
@@ -19,7 +19,9 @@
 #include <h/mh.h>
 #include <h/utils.h>
 
-#define VEC_INIT_SIZE 256
+#define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
+#define SVEC_INIT_SIZE 256
+#define IVEC_INIT_SIZE 256
 
 /*
  * These try to hide the type of the "bits" member of bvector.  But if
@@ -36,6 +38,7 @@
 struct bvector {
     unsigned long *bits;
     size_t maxsize;
+    unsigned long tiny[2];
 };
 
 static void bvector_resize (bvector_t, size_t);
@@ -49,8 +52,15 @@ bvector_create (size_t init_size) {
     assert (sizeof *vec->bits <= sizeof 1ul);
 
     NEW(vec);
-    bytes = BVEC_BYTES(init_size  ?  init_size  :  VEC_INIT_SIZE);
 
+    if (init_size <= BVEC_INIT_SIZE) {
+        vec->bits = vec->tiny;
+        vec->maxsize = BVEC_INIT_SIZE;
+        memset(vec->tiny, 0, sizeof vec->tiny);
+        return vec;
+    }
+
+    bytes = BVEC_BYTES(init_size);
     vec->bits = mh_xcalloc (1, bytes);
     vec->maxsize = bytes * CHAR_BIT;
 
@@ -61,7 +71,8 @@ void
 bvector_copy (bvector_t dest, bvector_t src) {
     size_t bytes = BVEC_BYTES(src->maxsize);
 
-    free (dest->bits);
+    if (dest->bits != dest->tiny)
+        free(dest->bits);
     dest->bits = mh_xmalloc (bytes);
     memcpy (dest->bits, src->bits, bytes);
     dest->maxsize = src->maxsize;
@@ -69,7 +80,8 @@ bvector_copy (bvector_t dest, bvector_t src) {
 
 void
 bvector_free (bvector_t vec) {
-    free (vec->bits);
+    if (vec->bits != vec->tiny)
+        free(vec->bits);
     free (vec);
 }
 
@@ -120,7 +132,11 @@ bvector_resize (bvector_t vec, size_t maxsize) {
     while ((vec->maxsize *= 2) < maxsize)
         ;
     bytes = BVEC_BYTES(vec->maxsize);
-    vec->bits = mh_xrealloc (vec->bits, bytes);
+    if (vec->bits == vec->tiny) {
+        vec->bits = mh_xmalloc(bytes);
+        memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
+    } else
+        vec->bits = mh_xrealloc(vec->bits, bytes);
     for (i = old_maxsize; i < vec->maxsize; ++i)
         bvector_clear (vec, i);
 }
@@ -145,7 +161,7 @@ svector_create (size_t init_size) {
     size_t bytes;
 
     NEW(vec);
-    vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+    vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
     bytes = vec->maxsize * sizeof (char *);
     vec->strs = mh_xcalloc (1, bytes);
     vec->size = 0;
@@ -228,7 +244,7 @@ ivector_create (size_t init_size) {
     size_t bytes;
 
     NEW(vec);
-    vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+    vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
     bytes = vec->maxsize * sizeof (int);
     vec->ints = mh_xcalloc (1, bytes);
     vec->size = 0;
-- 
2.56.0