This allocator assigns an integer handle to each allocation which
can be used to retrieve the pointer to the start of the allocation
and its length.
On average, the per-allocation memory overhead is twice the length
of the variable-length-encoding of the allocation size. For objects
less than 128 bytes in size, this equates to 2 bytes of overhead.
Signed-off-by: David Barr <davidbarr@xxxxxxxxxx>
---
This is the second in a series of patches to enable libfastimport.
The theme of series is memory-effective, fast, scalable data structures.
small-alloc.c | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
small-alloc.h | 18 ++++++++++++
2 files changed, 100 insertions(+), 0 deletions(-)
create mode 100644 small-alloc.c
create mode 100644 small-alloc.h
diff --git a/small-alloc.c b/small-alloc.c
new file mode 100644
index 0000000..936884e
--- /dev/null
+++ b/small-alloc.c
@@ -0,0 +1,82 @@
+#include "git-compat-util.h"
+#include "cache.h"
+#include "varint.h"
+#include "small-alloc.h"
+
+static const size_t chunk_size = 2 * 1024 * 1024;
+
+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out)
+{
+ static size_t id = 1;
+ size_t n;
+ void *r;
+
+ if ((pool->end - pool->next_free >= len) &&
+ (pool->len_free >= sizeof_varint(len)))
+ n = pool->nr - 1;
+ else {
+ if ((pool->end - pool->next_free < len)) {
+ size_t pool_size = chunk_size;
+ if (len >= (chunk_size/2))
+ pool_size = len;
+ pool->total_allocd += pool_size;
+ pool->next_free = malloc(pool_size);
+ pool->end = pool->next_free + pool_size;
+ }
+ pool->total_allocd += sizeof(*pool->first_id) +
+ sizeof(*pool->space) +
+ sizeof(*pool->len);
+ ALLOC_GROW(pool->first_id, pool->nr + 1, pool->f_alloc);
+ ALLOC_GROW(pool->len, pool->nr + 1, pool->l_alloc);
+ ALLOC_GROW(pool->space, pool->nr + 1, pool->s_alloc);
+ pool->first_id[pool->nr] = id;
+ pool->len_free = sizeof(*pool->len);
+ bzero(pool->len[pool->nr], sizeof(*pool->len));
+ pool->space[pool->nr] = pool->next_free;
+ n = pool->nr++;
+ }
+
+ if (id_out)
+ *id_out = id;
+ id++;
+
+ char *t = &pool->len[n][sizeof(*pool->len) - pool->len_free];
+ if (encode_varint(&t, pool->len[n] + sizeof(*pool->len), len))
+ return NULL;
+ pool->len_free = pool->len[n] + sizeof(*pool->len) - t;
+
+ r = pool->next_free;
+ pool->next_free += len;
+ return r;
+}
+
+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out)
+{
+ char *r;
+ const char *t;
+ uint64_t len = 0, cur;
+
+ if (!id || !pool->nr)
+ return NULL;
+
+ size_t n = pool->nr * id / pool->first_id[pool->nr - 1];
+ if (n >= pool->nr - 1)
+ n = pool->nr - 1;
+ while (n && pool->first_id[n] > id)
+ n--;
+ while (n + 1 < pool->nr && pool->first_id[n + 1] <= id)
+ n++;
+ if (pool->first_id[n] > id)
+ return NULL;
+
+ cur = pool->first_id[n];
+ for (r = pool->space[n], t = (const char*) pool->len[n];
+ !decode_varint(&t, pool->len[n] + sizeof(*pool->len), &len);
+ r += len, cur++)
+ if (cur == id) {
+ if (len_out)
+ *len_out = len;
+ return r;
+ }
+ return NULL;
+}
diff --git a/small-alloc.h b/small-alloc.h
new file mode 100644
index 0000000..eb77491
--- /dev/null
+++ b/small-alloc.h
@@ -0,0 +1,18 @@
+#ifndef SMALL_ALLOC_H_
+#define SMALL_ALLOC_H_
+
+struct mem_pool {
+ size_t *first_id;
+ char **space;
+ char (*len)[sizeof(size_t) + sizeof(char*)];
+ size_t f_alloc, s_alloc, l_alloc, nr;
+ char *next_free;
+ char *end;
+ int len_free;
+ size_t total_allocd;
+};
+
+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out);
+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out);
+
+#endif
--
1.7.5.1
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html