added memory pool to reduce allocations 5x

5 files changed, 118 insertions, 14 deletions

diff --git a/README.md b/README.md
index 80b2834..a830f03 100644
--- a/README.md
+++ b/README.md
@@ -4,6 +4,7 @@ A simple lisp/scheme interpreter
 
 #### TODO
 
+* reduce allocations
+* overhaul environement/closures
 * improve errors
-* macros
 * FFI
diff --git a/src/env.c b/src/env.c
index 10aa651..35b2ddf 100644
--- a/src/env.c
+++ b/src/env.c
@@ -5,7 +5,13 @@
 #include "env.h"
 #include "value.h"
 
-#define ENV_TABLE_CAP (1 << 8)
+#include "mempool.h"
+
+#define MEMPOOL_OBJ_TYPE struct symbol_table
+#define MEMPOOL_CAP 64
+MEMPOOL_GENERATE(env)
+
+#define ENV_TABLE_CAP (1 << 3)
 
 static unsigned long str_hash(char *str)
 {
@@ -34,7 +40,8 @@ static bool equal(void *key1, void *key2)
 
 env_t env_create(env_t parent, env_destroy_func destroy_func)
 {
-    env_t env = malloc(sizeof(*env));
+    // env_t env = malloc(sizeof(*env));
+    env_t env = env_mempool_allocate();
     env->destroy_func = destroy_func;
     env->parent = parent;
     env->refs = 1;
@@ -59,7 +66,8 @@ void env_destroy(env_t env)
     }
 
     hashtable_destroy(env->table);
-    free(env);
+    // free(env);
+    env_mempool_free(env);
 }
 
 env_t env_copy(env_t env)
diff --git a/src/hashtable.c b/src/hashtable.c
index 9f5d2e1..955a3bf 100644
--- a/src/hashtable.c
+++ b/src/hashtable.c
@@ -4,8 +4,16 @@
 #include "common.h"
 #include "hashtable.h"
 
+#include "mempool.h"
+
+#define MEMPOOL_CAP 32
+#define MEMPOOL_OBJ_TYPE struct hashtable
+MEMPOOL_GENERATE(ht)
+#define MEMPOOL_CAP 128
+#define MEMPOOL_OBJ_TYPE struct hashtable_item
+MEMPOOL_GENERATE(hi)
+
 // TODO:
-// - automatic growing
 // - insertion options
 
 #define HASH(ht, key) (ht->hash_func(key) % ht->cap)
@@ -17,7 +25,8 @@ static void hashtable_table_append_item(struct hashtable_item ** table, size_t i
 hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func)
 {
     hashtable_t ht;
-    ERR_Z(ht = malloc(sizeof(*ht)), goto fail);
+    // ERR_Z(ht = malloc(sizeof(*ht)), goto fail);
+    ht = ht_mempool_allocate();
 
     ht->hash_func = hash_func;
     ht->equal_func = equal_func;
@@ -38,13 +47,15 @@ void hashtable_destroy(hashtable_t ht)
 
     if(ht->table) {
         hashtable_for_each_item_safe(ht, item, i) {
-            free(item);
+            // free(item);
+            hi_mempool_free(item);
         }
 
         free(ht->table);
     }
 
-    free(ht);
+    // free(ht);
+    ht_mempool_free(ht);
 }
 
 void hashtable_reset(hashtable_t ht)
@@ -53,7 +64,8 @@ void hashtable_reset(hashtable_t ht)
 
     if(ht->table) {
         hashtable_for_each_item_safe(ht, item, i) {
-            free(item);
+            // free(item);
+            hi_mempool_free(item);
         }
     }
 
@@ -75,7 +87,8 @@ int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void
         return 0;
     }
 
-    ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM);
+    // ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM);
+    item = hi_mempool_allocate();
 
     item->key = key;
     item->data = data;
@@ -85,7 +98,7 @@ int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void
     ht->size++;
 
     if(ht->size > (ht->cap * 3/4)) {
-        return hashtable_grow(ht, 1 << ht->cap);
+        return hashtable_grow(ht, ht->cap << 1);
     }
 
     return 0;
@@ -124,7 +137,6 @@ static int hashtable_grow(hashtable_t ht, size_t cap)
 {
     struct hashtable_item **new_table;
     ERR_Z(new_table = calloc(cap, sizeof(*new_table)), return -ENOMEM);
-
     if(ht->cap > 0) {
         hashtable_for_each_item_safe(ht, item, i) {
             // hash but with the new cap
diff --git a/src/mempool.h b/src/mempool.h
new file mode 100644
index 0000000..6c25ac9
--- /dev/null
+++ b/src/mempool.h
@@ -0,0 +1,75 @@
+#ifndef MEMPOOL_H
+#define MEMPOOL_H
+
+#ifndef MEMPOOL_OBJ_TYPE
+#define MEMPOOL_OBJ_TYPE int
+#endif
+
+#ifndef MEMPOOL_CAP
+#define MEMPOOL_CAP (1 << 16)
+#endif
+
+#define for_each_block(id, b, head)                     \
+    for(struct id##_block *b = (head), *next = NULL;    \
+        b && (next = b->next, 1); b = next)
+#define get_last_block(b)                       \
+    while((b)->next != NULL) (b) = (b)->next
+
+#define MEMPOOL_GENERATE(id)                                             \
+                                                                         \
+    struct id##_block {                                                  \
+        union id##_chunk {                                               \
+            MEMPOOL_OBJ_TYPE obj;                                        \
+            union id##_chunk *next;                                      \
+        } chunks[MEMPOOL_CAP];                                           \
+                                                                         \
+        struct id##_block *next;                                         \
+    };                                                                   \
+                                                                         \
+    static union  id##_chunk *id##_ap = NULL;                            \
+    static struct id##_block id##_block;                                 \
+    static size_t id##_allocations = 0;                                  \
+                                                                         \
+    static inline void *_##id##_mempool_init_block(struct id##_block *b) \
+    {                                                                    \
+        b->next = NULL;                                                  \
+        for(size_t i = 0; i < MEMPOOL_CAP; i++)                          \
+            b->chunks[i].next = &b->chunks[i+1];                         \
+        b->chunks[MEMPOOL_CAP-1].next = NULL;                            \
+                                                                         \
+        return b->chunks;                                                \
+    }                                                                    \
+                                                                         \
+    static inline void *id##_mempool_allocate(void)                      \
+    {                                                                    \
+        if(!id##_ap) {                                                   \
+            struct id##_block *new_block = &(id##_block);                \
+            if((id##_allocations) > 0) {                                 \
+                new_block = malloc(sizeof(*new_block));                  \
+                struct id##_block *last_block = &(id##_block);           \
+                get_last_block(last_block);                              \
+                last_block->next = new_block;                            \
+            }                                                            \
+            id##_ap = _##id##_mempool_init_block(new_block);             \
+        }                                                                \
+                                                                         \
+        id##_allocations++;                                              \
+                                                                         \
+        void *ptr = &(id##_ap)->obj;                                     \
+        id##_ap = (id##_ap)->next;                                       \
+        return ptr;                                                      \
+    }                                                                    \
+                                                                         \
+    static inline void id##_mempool_free(void *ptr)                      \
+    {                                                                    \
+        ((union id##_chunk *)ptr)->next = id##_ap;                       \
+        id##_ap = (union id##_chunk *)ptr;                               \
+                                                                         \
+        if(--id##_allocations == 0) {                                    \
+            for_each_block(id, b, (id##_block).next)                     \
+                free(b);                                                 \
+            id##_ap = id##_block.chunks;                                 \
+        }                                                                \
+    }                                                                    \
+
+#endif
diff --git a/src/value.c b/src/value.c
index 9a7f9b6..0d263d7 100644
--- a/src/value.c
+++ b/src/value.c
@@ -5,6 +5,12 @@
 #include "value.h"
 #include "lexer.h"
 
+#include "mempool.h"
+
+#define MEMPOOL_OBJ_TYPE struct value
+#define MEMPOOL_CAP 64
+MEMPOOL_GENERATE(value)
+
 #define NOT_IMPLEMENTED() die("Not Implemented. ABORTING")
 
 const char * const value_type_string[] = {
@@ -76,7 +82,8 @@ static void proc_destroy(struct proc *proc);
 
 value_t value_create(enum value_type type, void *value)
 {
-    value_t _value = malloc(sizeof(*_value));
+    // value_t _value = malloc(sizeof(*_value));
+    value_t _value = value_mempool_allocate();
     _value->type = type;
 
     switch(type) {
@@ -98,7 +105,8 @@ void value_destroy(value_t value)
     }
 
     if(value->refs == 0)
-        free(value);
+        value_mempool_free(value);
+        // free(value);
 }
 
 value_t value_from_token(struct token *token)