Use slabs for strings

I almost didn't make this change, but after using the new ministat with
the benchmark.sh changes, I found out that, when running all of the
benchmarks together, the slabs version is always faster, after 20 runs
anyway.

What this commit does is add vectors to vm which contain "slabs". These
slabs are a pointer and a length. The pointer always points to an
allocation of 4096 bytes, except when a slab vector is used to allocate
a string that is greater than 128 bytes (including the nul byte). In
that case, space for the string alone is allocated and pushed at the
last spot. That way, I can reduce fragmentation.

Anyway, each slab is basically a bump pointer when allocating space for
strings. When a slab runs out of space, a new one is allocated and used.

This reduces memory allocator pressure by allocating few big pages (in
fact, exactly a page) instead of many small allocations that all need to
be freed. In preliminary tests with Valgrind (which reports the number
of allocations and bytes), these changes could result in 1/4-3/4 as many
allocations, usually 1/4-1/2. Of course, the number of bytes allocated
was usually more, but not by much.

Signed-off-by: Gavin Howard <gavin@yzena.com>

2 files changed, 22 insertions, 5 deletions

diff --git a/include/vector.h b/include/vector.h
index dea3226e..a9dd7c0b 100644
--- a/include/vector.h
+++ b/include/vector.h
@@ -49,6 +49,21 @@ typedef unsigned char uchar;
 
 typedef void (*BcVecFree)(void*);
 
+#define BC_SLAB_SIZE (4096)
+
+typedef struct BcSlab {
+	char *s;
+	size_t len;
+} BcSlab;
+
+void bc_slab_init(BcSlab *s);
+
+char* bc_slab_add(BcSlab *s, const char *str, size_t len);
+void bc_slab_clear(BcSlab *s);
+void bc_slab_undo(BcSlab *s, size_t len);
+
+void bc_slab_free(void *slab);
+
 // Forward declaration.
 struct BcId;
 
@@ -66,8 +81,8 @@ typedef enum BcDtorType {
 #ifndef NDEBUG
 	BC_DTOR_ID,
 #endif // NDEBUG
+	BC_DTOR_SLAB,
 	BC_DTOR_CONST,
-	BC_DTOR_STRING,
 	BC_DTOR_FUNC,
 	BC_DTOR_RESULT,
 #if BC_ENABLE_HISTORY
@@ -98,6 +113,7 @@ void bc_vec_npush(BcVec *restrict v, size_t n, const void *data);
 void* bc_vec_pushEmpty(BcVec *restrict v);
 void bc_vec_pushByte(BcVec *restrict v, uchar data);
 void bc_vec_pushIndex(BcVec *restrict v, size_t idx);
+void bc_vec_pushAt(BcVec *restrict v, const void *data, size_t idx);
 void bc_vec_string(BcVec *restrict v, size_t len, const char *restrict str);
 void bc_vec_concat(BcVec *restrict v, const char *restrict str);
 void bc_vec_empty(BcVec *restrict v);
@@ -124,11 +140,7 @@ char* bc_map_name(const BcVec *restrict v, size_t idx);
 #define bc_vec_popAll(v) (bc_vec_npop((v), (v)->len))
 #define bc_vec_top(v) (bc_vec_item_rev((v), 0))
 
-#ifndef NDEBUG
-#define bc_map_init(v) (bc_vec_init((v), sizeof(BcId), BC_DTOR_ID))
-#else // NDEBUG
 #define bc_map_init(v) (bc_vec_init((v), sizeof(BcId), BC_DTOR_NONE))
-#endif // NDEBUG
 
 extern const BcVecFree bc_vec_dtors[];
 
diff --git a/include/vm.h b/include/vm.h
index 7c8e346d..2c6ee6a5 100644
--- a/include/vm.h
+++ b/include/vm.h
@@ -303,6 +303,10 @@ typedef struct BcVm {
 
 	char *buf;
 	size_t buf_len;
+
+	BcVec main_const_slab;
+	BcVec main_slabs;
+	BcVec other_slabs;
 #endif // !BC_ENABLE_LIBRARY
 
 #if BC_DEBUG_CODE
@@ -330,6 +334,7 @@ size_t bc_vm_growSize(size_t a, size_t b);
 void* bc_vm_malloc(size_t n);
 void* bc_vm_realloc(void *ptr, size_t n);
 char* bc_vm_strdup(const char *str);
+char* bc_vm_strdup2(const char *str, BcVec *slabs);
 
 bool bc_vm_readLine(bool clear);