Overallocate for speed in str.c

One of the key motivations for switching to the str_t type internally
is that we can avoid allocations by re-using the same storage over and
over during the transformation.

We can avoid other allocations by overallocating when more storage
is requested, seeing as almost all requests for more storage will
later be followed by other requests.

At the moment, the original implementation is quite fast:

                                user     system      total        real
short slab of ASCII text    1.440000   0.000000   1.440000 (  1.445547)
short slab of UTF-8 text    2.900000   0.010000   2.910000 (  2.927274)
longer slab of ASCII text  12.710000   0.040000  12.750000 ( 12.816209)
longer slab of UTF-8 text  35.210000   0.080000  35.290000 ( 35.661577)

The new implementation is actually slower, because we have had to add
some wasteful conversions back-and-forth between VALUE/String and str_t:

short slab of ASCII text    1.550000   0.000000   1.550000 (  1.556956)
short slab of UTF-8 text    3.340000   0.010000   3.350000 (  3.377874)
longer slab of ASCII text  15.410000   0.030000  15.440000 ( 15.484308)
longer slab of UTF-8 text  45.230000   0.130000  45.360000 ( 45.631355)

It is expected that the performance loss will be recovered once these
wasteful conversions are eliminated.

But before going that far, adding overallocation brings very large
improvements, enough to compensate for the inefficient conversions:

short slab of ASCII text    1.190000   0.010000   1.200000 (  1.233443)
short slab of UTF-8 text    2.460000   0.020000   2.480000 (  2.536714)
longer slab of ASCII text  11.000000   0.050000  11.050000 ( 11.208843)
longer slab of UTF-8 text  33.490000   0.130000  33.620000 ( 34.190941)

Those numbers use an overallocation constant of 256 bytes; will later
experiment with other constants to find the optimal overallocation.

Signed-off-by: Wincent Colaiuta <win@wincent.com>

diff --git a/ext/str.c b/ext/str.c
index ca6395e0a1d35ace8e98717699f8b6971fcf5043..bf4220c3a4c8deea1447e560c798c7115ce81a9e 100644 (file)
--- a/ext/str.c
+++ b/ext/str.c
@@ -23,6 +23,10 @@
 
 #include "str.h"
 
+// when allocating memory, reserve a little more than was asked for,
+// which can help to avoid subsequent allocations
+#define STR_OVERALLOC 256
+
 str_t *str_new(void)
 {
     str_t *str      = ALLOC_N(str_t, 1);
@@ -35,19 +39,19 @@ str_t *str_new(void)
 str_t *str_new_size(long len)
 {
     str_t *str      = ALLOC_N(str_t, 1);
-    str->ptr        = ALLOC_N(char, len);
+    str->ptr        = ALLOC_N(char, len + STR_OVERALLOC);
     str->len        = 0;
-    str->capacity   = len;
+    str->capacity   = len + STR_OVERALLOC;
     return str;
 }
 
 str_t *str_new_copy(const char *src, long len)
 {
     str_t *str      = ALLOC_N(str_t, 1);
-    str->ptr        = ALLOC_N(char, len);
+    str->ptr        = ALLOC_N(char, len + STR_OVERALLOC);
     memcpy(str->ptr, src, len);
     str->len        = len;
-    str->capacity   = len;
+    str->capacity   = len + STR_OVERALLOC;
     return str;
 }
 
@@ -76,27 +80,23 @@ void str_grow(str_t *str, long len)
     if (str->capacity < len)
     {
         if (str->ptr)
-            REALLOC_N(str->ptr, char, len);
+            REALLOC_N(str->ptr, char, len + STR_OVERALLOC);
         else
-            str->ptr = ALLOC_N(char, len);
-        str->capacity = len;
+            str->ptr = ALLOC_N(char, len + STR_OVERALLOC);
+        str->capacity = len + STR_OVERALLOC;
     }
 }
 
-// try overallocating once we've switched more things over to str_t
-// ie. allocate 32 bytes too much, 64 bytes etc
-// and run benchmarks to see if it runs faster
-// and other tests to count the number of allocations
 void str_append(str_t *str, const char *src, long len)
 {
     long new_len = str->len + len;
     if (str->capacity < new_len)
     {
         if (str->ptr)
-            REALLOC_N(str->ptr, char, new_len);
+            REALLOC_N(str->ptr, char, new_len + STR_OVERALLOC);
         else
-            str->ptr = ALLOC_N(char, new_len);
-        str->capacity = new_len;
+            str->ptr = ALLOC_N(char, new_len + STR_OVERALLOC);
+        str->capacity = new_len + STR_OVERALLOC;
     }
     memcpy(str->ptr + str->len, src, len);
     str->len = new_len;