{"thread":{"id":"27684","subject":"[RFC/PATCH 0/3]","startedAt":"2011-06-22T07:33:29Z","lastAt":"2011-06-24T17:02:16Z","messageCount":12,"participants":["David Barr","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"170449","messageId":"1308728011-14136-1-git-send-email-davidbarr@google.com","threadId":"27684","inReplyTo":null,"subject":"[RFC/PATCH 0/3]","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-22T07:33:29Z","receivedAt":"2011-06-22T07:33:29Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"This series is the early stages of adding infrastructure to git\nto memory-effective but fast and scalable caching of object\ngraphs.\nThe inspiration comes from a desire to build a libfastimport and\nalso the outstanding FIXME in hash.c\nPatches 1 and 2 are the first small components that have emerged\nfrom my experiments with different ways of representing and\nindexing graphs. Patch 3 doesn't exist at the time of composing\nthis summary but will be an alternate hash table implementation\nthe builds on the first two.\n\nI'm putting this out for early feedback, to be incorporated into\na future complete series.\n\n--\nDavid Barr\n"},{"id":"170450","messageId":"1308728011-14136-2-git-send-email-davidbarr@google.com","threadId":"27684","inReplyTo":"1308728011-14136-1-git-send-email-davidbarr@google.com","subject":"[RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-22T07:33:30Z","receivedAt":"2011-06-22T07:33:30Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"One struct to capture all types, just 4 methods:\ndecode_message, encode_message, sizeof_message, hash_field.\n\nSigned-off-by: David Barr <davidbarr@google.com>\n---\n\n This is the first in a series of small patches to introduce some higher-level\n constructs into the git toolbag.\n The motivation is to empower a libfastimport implementation that is frugal\n with memory, fast and scalable.\n\n This version lacks any driver or tests.\n\n Soon to come are:\n * an efficient allocator that provides a mapping from an integer handle to\n  pointer and length\n * a hash table that is time and memory effective for very numerous entries\n\n protobuf.c |  193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n protobuf.h |   70 ++++++++++++++++++++++\n varint.h   |   59 ++++++++++++++++++\n 3 files changed, 322 insertions(+), 0 deletions(-)\n create mode 100644 protobuf.c\n create mode 100644 protobuf.h\n create mode 100644 varint.h\n\ndiff --git a/protobuf.c b/protobuf.c\nnew file mode 100644\nindex 0000000..09223dd\n--- /dev/null\n+++ b/protobuf.c\n@@ -0,0 +1,193 @@\n+#include \"git-compat-util.h\"\n+#include \"protobuf.h\"\n+#include \"varint.h\"\n+\n+static int decode_binary(const char **buf, const char *end, const char **result, size_t len)\n+{\n+\tif (end && *buf + len > end)\n+\t\treturn 1;\n+\t*result = *buf;\n+\t*buf += len;\n+\treturn 0;\n+}\n+\n+static int encode_binary(char **buf, const char *end, const char *value, size_t len)\n+{\n+\tif (end && *buf + len > end)\n+\t\treturn 1;\n+\tmemcpy(*buf, value, len);\n+\t*buf += len;\n+\treturn 0;\n+}\n+\n+static int decode_field(const char **buf, const char *end, struct protobuf_field *field)\n+{\n+\tuint32_t u32;\n+\tuint64_t key;\n+\tbzero(field, sizeof(struct protobuf_field));\n+\tif (decode_varint(buf, end, &key))\n+\t\treturn 1;\n+\tfield->tag = key >> WT_BITS,\n+\tfield->type = key & WT_MASK;\n+\tswitch (field->type) {\n+\tcase WT_VARINT:\n+\t\tif (decode_varint(buf, end, &field->val.num))\n+\t\t\treturn 1;\n+\t\treturn 0;\n+\tcase WT_64BIT:\n+\t\tfield->val.bin.len = sizeof(uint64_t);\n+\t\tbreak;\n+\tcase WT_STRING:\n+\t\tif (decode_varint(buf, end, &field->val.bin.len))\n+\t\t\treturn 1;\n+\t\tbreak;\n+\tcase WT_SHA1:\n+\t\tfield->val.bin.len = 20;\n+\t\tbreak;\n+\tcase WT_32BIT:\n+\t\tfield->val.bin.len = sizeof(uint32_t);\n+\t\tbreak;\n+\tdefault:\n+\t\treturn 1;\n+\t}\n+\tif (decode_binary(buf, end, &field->val.bin.ptr, field->val.bin.len))\n+\t\treturn 1;\n+\tswitch (field->type) {\n+\tcase WT_64BIT:\n+\t\tmemcpy(&field->val.num, field->val.bin.ptr, field->val.bin.len);\n+\t\tbreak;\n+\tcase WT_32BIT:\n+\t\tmemcpy(&u32, field->val.bin.ptr, field->val.bin.len);\n+\t\tfield->val.num = u32;\n+\t}\n+\treturn 0;\n+}\n+\n+int decode_message(const char **buf, const char *end, struct protobuf_field *message, size_t fields)\n+{\n+\tstruct protobuf_field current;\n+\tbzero(message, fields * sizeof(struct protobuf_field));\n+\twhile (*buf != end) {\n+\t\tif (decode_field(buf, end, &current))\n+\t\t\treturn 1;\n+\t\tif (current.tag < fields)\n+\t\t\tmessage[current.tag] = current;\n+\t}\n+\treturn 0;\n+}\n+\n+static size_t sizeof_field(const struct protobuf_field *field)\n+{\n+\tsize_t sizeof_key = sizeof_varint(field->tag << WT_BITS | field->type);\n+\tswitch (field->type) {\n+\tcase WT_VARINT:\n+\t\tif (field->val.num)\n+\t\t\treturn sizeof_key + sizeof_varint(field->val.num);\n+\t\tbreak;\n+\tcase WT_64BIT:\n+\t\tif (field->val.num)\n+\t\t\treturn sizeof_key + sizeof(uint64_t);\n+\t\tbreak;\n+\tcase WT_STRING:\n+\t\tif (field->val.bin.len && field->val.bin.ptr)\n+\t\t\treturn sizeof_key + sizeof_varint(field->val.bin.len)\n+\t\t\t       + field->val.bin.len;\n+\t\tbreak;\n+\tcase WT_SHA1:\n+\t\tif (field->val.bin.ptr)\n+\t\t\treturn sizeof_key + 20;\n+\t\tbreak;\n+\tcase WT_32BIT:\n+\t\tif (field->val.num)\n+\t\t\treturn sizeof_key + sizeof(uint32_t);\n+\t\tbreak;\n+\t}\n+\treturn 0;\n+}\n+\n+uint64_t sizeof_message(const struct protobuf_field *message, size_t fields)\n+{\n+\tuint64_t size = 0;\n+\twhile (fields--)\n+\t\tsize += sizeof_field(message++);\n+\treturn size;\n+}\n+\n+static int encode_field(char **buf, const struct protobuf_field *field, char *end)\n+{\n+\tuint32_t u32;\n+\tuint64_t len;\n+\tconst char *ptr;\n+\tuint64_t key = (field->tag << WT_BITS) | field->type;\n+\tif (!sizeof_field(field))\n+\t\treturn 0;\n+\tif (encode_varint(buf, end, key))\n+\t\treturn 1;\n+\tswitch (field->type) {\n+\tcase WT_VARINT:\n+\t\tif (encode_varint(buf, end, field->val.num))\n+\t\t\treturn 1;\n+\t\treturn 0;\n+\tcase WT_64BIT:\n+\t\tptr = (const char *)&field->val.num;\n+\t\tlen = sizeof(uint64_t);\n+\t\tbreak;\n+\tcase WT_STRING:\n+\t\tif (encode_varint(buf, end, field->val.bin.len))\n+\t\t\treturn 1;\n+\t\tptr = field->val.bin.ptr;\n+\t\tlen = field->val.bin.len;\n+\t\tbreak;\n+\tcase WT_SHA1:\n+\t\tptr = field->val.bin.ptr;\n+\t\tlen = 20;\n+\t\tbreak;\n+\tcase WT_32BIT:\n+\t\tu32 = field->val.num;\n+\t\tptr = (const char *)&u32;\n+\t\tlen = sizeof(uint64_t);\n+\t\tbreak;\n+\tdefault:\n+\t\treturn 1;\n+\t}\n+\tif (encode_binary(buf, end, ptr, len))\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+int encode_message(char **buf, char *end, const struct protobuf_field *message, size_t fields)\n+{\n+\twhile (*buf != end && fields--)\n+\t\tif (encode_field(buf, message++, end))\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n+static uint32_t x65599(const char *s, uint64_t len)\n+{\n+\tuint32_t r = 0;\n+\twhile (len--)\n+\t\tr = *s++ + (r << 6) + (r << 16) - r;\n+\treturn r;\n+}\n+\n+uint32_t hash_field(const struct protobuf_field *field)\n+{\n+\tuint32_t hc = 0;\n+\tswitch (field->type) {\n+\tcase WT_VARINT:\n+\tcase WT_64BIT:\n+\t\thc = (0x9e3779b97f4a7c15ull * field->val.num) >> 32;\n+\t\tbreak;\n+\tcase WT_SHA1:\n+\t\tmemcpy(&hc, field->val.bin.ptr, sizeof(hc));\n+\t\tbreak;\n+\tcase WT_STRING:\n+\t\thc = x65599(field->val.bin.ptr, field->val.bin.len);\n+\t\tbreak;\n+\tcase WT_32BIT:\n+\t\thc = 0x9e3779b9ul * (uint32_t)field->val.num;\n+\t\tbreak;\n+\t}\n+\treturn hc;\n+}\ndiff --git a/protobuf.h b/protobuf.h\nnew file mode 100644\nindex 0000000..89b70a4\n--- /dev/null\n+++ b/protobuf.h\n@@ -0,0 +1,70 @@\n+#ifndef PROTOBUF_H_\n+#define PROTOBUF_H_\n+\n+#define WT_BITS 3\n+#define WT_MASK 0x7\n+\n+enum wire_type {\n+\tWT_VARINT = 0,\n+\tWT_64BIT  = 1,\n+\tWT_STRING = 2,\n+\t/* Custom wire type */\n+\tWT_SHA1   = 3,\n+\tWT_32BIT  = 5\n+};\n+\n+struct protobuf_field\n+{\n+\tuint64_t tag : 64 - WT_BITS,\n+\t\t type : WT_BITS;\n+\tunion protobuf_value {\n+\t\tuint64_t num;\n+\t\tstruct protobuf_binary {\n+\t\t\tuint64_t len;\n+\t\t\tconst char *ptr;\n+\t\t} bin;\n+\t} val;\n+};\n+\n+#define PROTOBUF_KEY(p, f, wt) do { \\\n+\t(p)->f.tag = &((p)->f) - (struct protobuf_field*)(p); \\\n+\t(p)->f.type = wt; \\\n+} while(0)\n+\n+#define WT_VARINT(p, f, v) do { \\\n+\tPROTOBUF_KEY(p, f, WT_VARINT); \\\n+\t(p)->f.val.num = v; \\\n+} while(0)\n+\n+#define WT_64BIT(p, f, v) do { \\\n+\tPROTOBUF_KEY(p, f, WT_64BIT); \\\n+\t(p)->f.val.num = v; \\\n+} while(0)\n+\n+#define WT_STRING(p, f, s, l) do { \\\n+\tPROTOBUF_KEY(p, f, WT_STRING); \\\n+\t(p)->f.val.bin.ptr = s; \\\n+\t(p)->f.val.bin.len = l; \\\n+} while(0)\n+\n+#define WT_SHA1(p, f, v) do { \\\n+\tPROTOBUF_KEY(p, f, WT_SHA1); \\\n+\t(p)->f.val.bin.ptr = s; \\\n+\t(p)->f.val.bin.len = 20; \\\n+} while(0)\n+\n+#define WT_32BIT(p, f, v) do { \\\n+\tPROTOBUF_KEY(p, f, WT_32BIT); \\\n+\t(p)->f.val.num = v; \\\n+} while(0)\n+\n+#define PROTOBUF_CAST(p) \\\n+\t(struct protobuf_field*)(p), \\\n+\tsizeof(*(p)) / sizeof(struct protobuf_field)\n+\n+int decode_message(const char **buf, const char *end, struct protobuf_field *message, size_t fields);\n+uint64_t sizeof_message(const struct protobuf_field *message, size_t fields);\n+int encode_message(char **buf, char *end, const struct protobuf_field *message, size_t fields);\n+uint32_t hash_field(const struct protobuf_field *field);\n+\n+#endif\ndiff --git a/varint.h b/varint.h\nnew file mode 100644\nindex 0000000..48a3547\n--- /dev/null\n+++ b/varint.h\n@@ -0,0 +1,59 @@\n+#ifndef VARINT_H_\n+#define VARINT_H_\n+\n+#define VLI_CONTINUE\t0x80\n+#define VLI_DIGIT_MASK\t0x7f\n+#define VLI_BITS_PER_DIGIT 7\n+\n+static int decode_varint(const char **buf, const char *end, uint64_t *result)\n+{\n+\tuint64_t rv = 0;\n+\tint shift = 0;\n+\tconst char *pos;\n+\tfor (pos = *buf; pos != end && shift < 64; pos++) {\n+\t\tunsigned char ch = *pos;\n+\n+\t\trv |= (ch & VLI_DIGIT_MASK) << shift;\n+\t\tshift += VLI_BITS_PER_DIGIT;\n+\t\tif (ch & VLI_CONTINUE)\n+\t\t\tcontinue;\n+\n+\t\t*result = rv;\n+\t\t*buf = pos + 1;\n+\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\n+\n+static int encode_varint(char **buf, const char *end, uint64_t value)\n+{\n+\tchar *pos;\n+\tfor (pos = *buf; pos != end; pos++) {\n+\t\tunsigned char ch = value & VLI_DIGIT_MASK;\n+\n+\t\tvalue >>= VLI_BITS_PER_DIGIT;\n+\t\tif (value)\n+\t\t\tch |= VLI_CONTINUE;\n+\t\t*pos = ch;\n+\t\tif (ch & VLI_CONTINUE)\n+\t\t\tcontinue;\n+\n+\t\t*buf = pos + 1;\n+\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\n+\n+static size_t sizeof_varint(uint64_t value) {\n+\tsize_t size = 0;\n+\tint shift = VLI_BITS_PER_DIGIT;\n+\twhile (shift < 64) {\n+\t\tsize++;\n+\t\tif (value < (1ull << shift))\n+\t\t\tbreak;\n+\t\tshift += VLI_BITS_PER_DIGIT;\n+\t}\n+\treturn size;\n+}\n+\n+#endif\n-- \n1.7.5.1\n"},{"id":"170451","messageId":"1308728011-14136-3-git-send-email-davidbarr@google.com","threadId":"27684","inReplyTo":"1308728011-14136-1-git-send-email-davidbarr@google.com","subject":"[RFC/PATCH 2/3] small-alloc: add allocator for small objects","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-22T07:33:31Z","receivedAt":"2011-06-22T07:33:31Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"This allocator assigns an integer handle to each allocation which\ncan be used to retrieve the pointer to the start of the allocation\nand its length.\nOn average, the per-allocation memory overhead is twice the length\nof the variable-length-encoding of the allocation size. For objects\nless than 128 bytes in size, this equates to 2 bytes of overhead.\n\nSigned-off-by: David Barr <davidbarr@google.com>\n---\n\n This is the second in a series of patches to enable libfastimport.\n The theme of series is memory-effective, fast, scalable data structures.\n\n small-alloc.c |   82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n small-alloc.h |   18 ++++++++++++\n 2 files changed, 100 insertions(+), 0 deletions(-)\n create mode 100644 small-alloc.c\n create mode 100644 small-alloc.h\n\ndiff --git a/small-alloc.c b/small-alloc.c\nnew file mode 100644\nindex 0000000..936884e\n--- /dev/null\n+++ b/small-alloc.c\n@@ -0,0 +1,82 @@\n+#include \"git-compat-util.h\"\n+#include \"cache.h\"\n+#include \"varint.h\"\n+#include \"small-alloc.h\"\n+\n+static const size_t chunk_size = 2 * 1024 * 1024;\n+\n+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out)\n+{\n+\tstatic size_t id = 1;\n+\tsize_t n;\n+\tvoid *r;\n+\n+\tif ((pool->end - pool->next_free >= len) &&\n+\t    (pool->len_free >= sizeof_varint(len)))\n+\t\tn = pool->nr - 1;\n+\telse {\n+\t\tif ((pool->end - pool->next_free < len)) {\n+\t\t\tsize_t pool_size = chunk_size;\n+\t\t\tif (len >= (chunk_size/2))\n+\t\t\t\tpool_size = len;\n+\t\t\tpool->total_allocd += pool_size;\n+\t\t\tpool->next_free = malloc(pool_size);\n+\t\t\tpool->end = pool->next_free + pool_size;\n+\t\t}\n+\t\tpool->total_allocd += sizeof(*pool->first_id) +\n+\t\t\t\tsizeof(*pool->space) +\n+\t\t\t\tsizeof(*pool->len);\n+\t\tALLOC_GROW(pool->first_id, pool->nr + 1, pool->f_alloc);\n+\t\tALLOC_GROW(pool->len, pool->nr + 1, pool->l_alloc);\n+\t\tALLOC_GROW(pool->space, pool->nr + 1, pool->s_alloc);\n+\t\tpool->first_id[pool->nr] = id;\n+\t\tpool->len_free = sizeof(*pool->len);\n+\t\tbzero(pool->len[pool->nr], sizeof(*pool->len));\n+\t\tpool->space[pool->nr] = pool->next_free;\n+\t\tn = pool->nr++;\n+\t}\n+\n+\tif (id_out)\n+\t\t*id_out = id;\n+\tid++;\n+\n+\tchar *t = &pool->len[n][sizeof(*pool->len) - pool->len_free];\n+\tif (encode_varint(&t, pool->len[n] + sizeof(*pool->len), len))\n+\t\treturn NULL;\n+\tpool->len_free = pool->len[n] + sizeof(*pool->len) - t;\n+\n+\tr = pool->next_free;\n+\tpool->next_free += len;\n+\treturn r;\n+}\n+\n+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out)\n+{\n+\tchar *r;\n+\tconst char *t;\n+\tuint64_t len = 0, cur;\n+\n+\tif (!id || !pool->nr)\n+\t\treturn NULL;\n+\n+\tsize_t n = pool->nr * id / pool->first_id[pool->nr - 1];\n+\tif (n >= pool->nr - 1)\n+\t\tn = pool->nr - 1;\n+\twhile (n && pool->first_id[n] > id)\n+\t\tn--;\n+\twhile (n + 1 < pool->nr && pool->first_id[n + 1] <= id)\n+\t\tn++;\n+\tif (pool->first_id[n] > id)\n+\t\treturn NULL;\n+\n+\tcur = pool->first_id[n];\n+\tfor (r = pool->space[n], t = (const char*) pool->len[n];\n+\t     !decode_varint(&t, pool->len[n] + sizeof(*pool->len), &len);\n+\t     r += len, cur++)\n+\t\tif (cur == id) {\n+\t\t\tif (len_out)\n+\t\t\t\t*len_out = len;\n+\t\t\treturn r;\n+\t\t}\n+\treturn NULL;\n+}\ndiff --git a/small-alloc.h b/small-alloc.h\nnew file mode 100644\nindex 0000000..eb77491\n--- /dev/null\n+++ b/small-alloc.h\n@@ -0,0 +1,18 @@\n+#ifndef SMALL_ALLOC_H_\n+#define SMALL_ALLOC_H_\n+\n+struct mem_pool {\n+\tsize_t *first_id;\n+\tchar **space;\n+\tchar (*len)[sizeof(size_t) + sizeof(char*)];\n+\tsize_t f_alloc, s_alloc, l_alloc, nr;\n+\tchar *next_free;\n+\tchar *end;\n+\tint len_free;\n+\tsize_t total_allocd;\n+};\n+\n+void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out);\n+void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out);\n+\n+#endif\n-- \n1.7.5.1\n"},{"id":"170477","messageId":"7voc1p64ap.fsf@alter.siamese.dyndns.org","threadId":"27684","inReplyTo":"1308728011-14136-2-git-send-email-davidbarr@google.com","subject":"Re: [RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-22T19:42:54Z","receivedAt":"2011-06-22T19:42:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr <davidbarr@google.com> writes:\n\n> One struct to capture all types, just 4 methods:\n> decode_message, encode_message, sizeof_message, hash_field.\n>\n> Signed-off-by: David Barr <davidbarr@google.com>\n> ---\n>\n>  This is the first in a series of small patches to introduce some higher-level\n>  constructs into the git toolbag.\n>  The motivation is to empower a libfastimport implementation that is frugal\n>  with memory, fast and scalable.\n>\n>  This version lacks any driver or tests.\n>\n>  Soon to come are:\n>  * an efficient allocator that provides a mapping from an integer handle to\n>   pointer and length\n>  * a hash table that is time and memory effective for very numerous entries\n>\n>  protobuf.c |  193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  protobuf.h |   70 ++++++++++++++++++++++\n\nHow does this relate to http://code.google.com/p/protobuf/ which has a\nvery similar name?  If we do not intend to have any interoperability with\nit, we should avoid such a confusing name, I think.\n\n> diff --git a/protobuf.c b/protobuf.c\n> new file mode 100644\n> index 0000000..09223dd\n> --- /dev/null\n> +++ b/protobuf.c\n> @@ -0,0 +1,193 @@\n> +#include \"git-compat-util.h\"\n> +#include \"protobuf.h\"\n> +#include \"varint.h\"\n> +\n> +static int decode_binary(const char **buf, const char *end, const char **result, size_t len)\n> +{\n> +\tif (end && *buf + len > end)\n> +\t\treturn 1;\n\nIn low-level library-ish code, we tend to signal an error with a negative\nvalue and success with zero, unless there is a compelling reason not to.\n\nWhen this error is triggered, what does it tell us?  Programming error\n(i.e. BUG())?  Incoming data stream error?\n\n> +\t*result = *buf;\n> +\t*buf += len;\n> +\treturn 0;\n> +}\n> +\n> +static int encode_binary(char **buf, const char *end, const char *value, size_t len)\n> +{\n> +\tif (end && *buf + len > end)\n> +\t\treturn 1;\n> +\tmemcpy(*buf, value, len);\n> +\t*buf += len;\n> +\treturn 0;\n> +}\n> +\n> +static int decode_field(const char **buf, const char *end, struct protobuf_field *field)\n> +{\n> +\tuint32_t u32;\n> +\tuint64_t key;\n> +\tbzero(field, sizeof(struct protobuf_field));\n\nPlease use memset(..., '\\0', ...), as we use functions from memXXX()\nfamily declared in <string.h>, just like you chose to use memcpy() over\nbcopy() in encode_binary() above.\n\n> +\tif (decode_varint(buf, end, &key))\n> +\t\treturn 1;\n> +\tfield->tag = key >> WT_BITS,\n> +\tfield->type = key & WT_MASK;\n> +\tswitch (field->type) {\n> +\tcase WT_VARINT:\n> +\t\tif (decode_varint(buf, end, &field->val.num))\n> +\t\t\treturn 1;\n> +\t\treturn 0;\n> +\tcase WT_64BIT:\n> +\t\tfield->val.bin.len = sizeof(uint64_t);\n> +\t\tbreak;\n> +\tcase WT_STRING:\n> +\t\tif (decode_varint(buf, end, &field->val.bin.len))\n> +\t\t\treturn 1;\n> +\t\tbreak;\n> +\tcase WT_SHA1:\n> +\t\tfield->val.bin.len = 20;\n> +\t\tbreak;\n> +\tcase WT_32BIT:\n> +\t\tfield->val.bin.len = sizeof(uint32_t);\n> +\t\tbreak;\n> +\tdefault:\n> +\t\treturn 1;\n> +\t}\n> +\tif (decode_binary(buf, end, &field->val.bin.ptr, field->val.bin.len))\n> +\t\treturn 1;\n> +\tswitch (field->type) {\n> +\tcase WT_64BIT:\n> +\t\tmemcpy(&field->val.num, field->val.bin.ptr, field->val.bin.len);\n> +\t\tbreak;\n> +\tcase WT_32BIT:\n> +\t\tmemcpy(&u32, field->val.bin.ptr, field->val.bin.len);\n> +\t\tfield->val.num = u32;\n\nIs there any need for byte-order considerations, or an encoded \"message\"\nis defined (by this library) to use host encoding, and will never be sent\nover the wire to other systems in the future?\n\n> +int decode_message(const char **buf, const char *end, struct protobuf_field *message, size_t fields)\n> +{\n> +\tstruct protobuf_field current;\n> +\tbzero(message, fields * sizeof(struct protobuf_field));\n> +\twhile (*buf != end) {\n> +\t\tif (decode_field(buf, end, &current))\n> +\t\t\treturn 1;\n> +\t\tif (current.tag < fields)\n> +\t\t\tmessage[current.tag] = current;\n\nIs there any need to check the incoming *buf for duplicated tags, whose\npayload may overwrite an element in message[] that was populated in the\nprevious iteration of this loop?\n\nCould decode_field() move *buf beyond end (IOW, would it be an improvement\nif we said \"while (*buf < end)\" instead)?\n\n> +static size_t sizeof_field(const struct protobuf_field *field)\n> +{\n> +\tsize_t sizeof_key = sizeof_varint(field->tag << WT_BITS | field->type);\n> +\tswitch (field->type) {\n> +\tcase WT_VARINT:\n> +\t\tif (field->val.num)\n> +\t\t\treturn sizeof_key + sizeof_varint(field->val.num);\n> +\t\tbreak;\n> +\tcase WT_64BIT:\n> +\t\tif (field->val.num)\n> +\t\t\treturn sizeof_key + sizeof(uint64_t);\n> +\t\tbreak;\n> +\tcase WT_STRING:\n> +\t\tif (field->val.bin.len && field->val.bin.ptr)\n> +\t\t\treturn sizeof_key + sizeof_varint(field->val.bin.len)\n> +\t\t\t       + field->val.bin.len;\n> +\t\tbreak;\n> +\tcase WT_SHA1:\n> +\t\tif (field->val.bin.ptr)\n> +\t\t\treturn sizeof_key + 20;\n> +\t\tbreak;\n> +\tcase WT_32BIT:\n> +\t\tif (field->val.num)\n> +\t\t\treturn sizeof_key + sizeof(uint32_t);\n> +\t\tbreak;\n> +\t}\n> +\treturn 0;\n\nDoesn't this function want to return an error when it does not understand\nwhat is in field->type field? If yes, I would imagine that this function\nneeds to be of type ssize_t, you would return -1 here, and the callers\nwould check the return value.\n\n> +static uint32_t x65599(const char *s, uint64_t len)\n> +{\n> +\tuint32_t r = 0;\n> +\twhile (len--)\n> +\t\tr = *s++ + (r << 6) + (r << 16) - r;\n> +\treturn r;\n\nWould it be an improvement if we made sure that each byte in s is taken as\nunsigned (or signed if you really wanted to but I do not see why) char on\nall platforms to guarantee reproducibility?\n\n> +}\n> +\n> +uint32_t hash_field(const struct protobuf_field *field)\n> +{\n> +\tuint32_t hc = 0;\n> +\tswitch (field->type) {\n> +\tcase WT_VARINT:\n> +\tcase WT_64BIT:\n> +\t\thc = (0x9e3779b97f4a7c15ull * field->val.num) >> 32;\n> +\t\tbreak;\n> +\tcase WT_SHA1:\n> +\t\tmemcpy(&hc, field->val.bin.ptr, sizeof(hc));\n> +\t\tbreak;\n> +\tcase WT_STRING:\n> +\t\thc = x65599(field->val.bin.ptr, field->val.bin.len);\n> +\t\tbreak;\n> +\tcase WT_32BIT:\n> +\t\thc = 0x9e3779b9ul * (uint32_t)field->val.num;\n> +\t\tbreak;\n> +\t}\n> +\treturn hc;\n> +}\n\nPlease make the magic Q64 and Q32 into symbolic constants somewhere in\nthis file, or at least give comment. Naming 65599 to SOMETHING_PRIME would\nalso be better.\n\n> diff --git a/varint.h b/varint.h\n> new file mode 100644\n> index 0000000..48a3547\n> --- /dev/null\n> +++ b/varint.h\n> @@ -0,0 +1,59 @@\n> +#ifndef VARINT_H_\n> +#define VARINT_H_\n> +\n> +#define VLI_CONTINUE\t0x80\n> +#define VLI_DIGIT_MASK\t0x7f\n> +#define VLI_BITS_PER_DIGIT 7\n> +\n> +static int decode_varint(const char **buf, const char *end, uint64_t *result)\n> +{\n> +\tuint64_t rv = 0;\n> +\tint shift = 0;\n> +\tconst char *pos;\n> +\tfor (pos = *buf; pos != end && shift < 64; pos++) {\n> +\t\tunsigned char ch = *pos;\n> +\n> +\t\trv |= (ch & VLI_DIGIT_MASK) << shift;\n> +\t\tshift += VLI_BITS_PER_DIGIT;\n> +\t\tif (ch & VLI_CONTINUE)\n> +\t\t\tcontinue;\n> +\n> +\t\t*result = rv;\n> +\t\t*buf = pos + 1;\n> +\t\treturn 0;\n\nThis seems to be the same 7-bit-at-a-time encoding used to encode object\nsize in packfiles, which is slightly looser than the one used to express\nthe pack offset of base objects (Cf. eb32d23 -- introduce delta objects\nwith offset to base, 2006-09-21). Would it make more sense to use the\nslightly tighter one?\n"},{"id":"170478","messageId":"7vk4cd617u.fsf@alter.siamese.dyndns.org","threadId":"27684","inReplyTo":"1308728011-14136-3-git-send-email-davidbarr@google.com","subject":"Re: [RFC/PATCH 2/3] small-alloc: add allocator for small objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-22T20:49:25Z","receivedAt":"2011-06-22T20:49:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr <davidbarr@google.com> writes:\n\n> This allocator assigns an integer handle to each allocation which\n> can be used to retrieve the pointer to the start of the allocation\n> and its length.\n> On average, the per-allocation memory overhead is twice the length\n> of the variable-length-encoding of the allocation size. For objects\n> less than 128 bytes in size, this equates to 2 bytes of overhead.\n\n> diff --git a/small-alloc.c b/small-alloc.c\n> new file mode 100644\n> index 0000000..936884e\n> --- /dev/null\n> +++ b/small-alloc.c\n> @@ -0,0 +1,82 @@\n> +#include \"git-compat-util.h\"\n> +#include \"cache.h\"\n> +#include \"varint.h\"\n> +#include \"small-alloc.h\"\n> +\n> +static const size_t chunk_size = 2 * 1024 * 1024;\n> +\n> +void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out)\n> +{\n> +\tstatic size_t id = 1;\n\nDoes this mean that even though you can have more than one mem_pool object\nactive in the system, you won't have id collision throughout the system?\nThat is a nice property (e.g. given an ID that does not belong to a pool,\nyou won't risk returning a wrong chunk of <mem,len> pair from pool_ptr()),\nbut is there a downside using function-scope static like this, I wonder?\n\nFor example, if I have two pools A and B, and call pool_alloc on A and\nthen on B and then on A again, A's space[0] will have the first and the\nthird object, with id=1 and id=3. How does this interact with your\nimplementation of pool_ptr() which seems to assume that id's are\nconsecutive within a single pool->space[]?\n\n> +\tsize_t n;\n> +\tvoid *r;\n> +\n> +\tif ((pool->end - pool->next_free >= len) &&\n> +\t    (pool->len_free >= sizeof_varint(len)))\n> +\t\tn = pool->nr - 1;\n\nHelp me make sure I understand what is going on here.\n\nA mem-pool has pool->nr chunks (and it can grow as more memory is asked\nfrom this pool). A new memory request is satisfied by carving out of\npool->space[n] (where n is the \"newest chunk\" in the pool).\npool->len[n] is a fixed sized byte array and stores the length of each\nmemory block carved out of pool->space[n] as a sequence of varint.\nIf pool->space[n] has enough space to fit \"len\" bytes, and if pool->len[n]\nstill has enough space to record the length, you use the current chunk,\notherwise (i.e. the else clause) you add a new chunk.\n\nAm I with you so far?\n\nWith the chunk_size of 2MB, you would fit roughly 16k allocation requests\nfor 128-byte memory, and you would need 2-bytes to express the length of\none piece of memory in your varint encoding, i.e. you would need to size\nan element of pool->len[] to 32kB if you wanted to store 16k allocation of\n128-byte for a chunk.\n\nThis would all depend on what the expected distribution of request size,\nbut it somehow feels wasteful to be limited by both space[] and len[]. If\nyou chose sizeof(*pool->len) that is too small for the workload, wouldn't\nyou end up allocating many 2MB space[], only to use potentially very\ninitial parts of them before len[] fills up?\n\n> +\telse {\n> +\t\tif ((pool->end - pool->next_free < len)) {\n> +\t\t\tsize_t pool_size = chunk_size;\n> +\t\t\tif (len >= (chunk_size/2))\n> +\t\t\t\tpool_size = len;\n> +\t\t\tpool->total_allocd += pool_size;\n> +\t\t\tpool->next_free = malloc(pool_size);\n> +\t\t\tpool->end = pool->next_free + pool_size;\n> +\t\t}\n> +\t\tpool->total_allocd += sizeof(*pool->first_id) +\n> +\t\t\t\tsizeof(*pool->space) +\n> +\t\t\t\tsizeof(*pool->len);\n> +\t\tALLOC_GROW(pool->first_id, pool->nr + 1, pool->f_alloc);\n> +\t\tALLOC_GROW(pool->len, pool->nr + 1, pool->l_alloc);\n> +\t\tALLOC_GROW(pool->space, pool->nr + 1, pool->s_alloc);\n> +\t\tpool->first_id[pool->nr] = id;\n> +\t\tpool->len_free = sizeof(*pool->len);\n> +\t\tbzero(pool->len[pool->nr], sizeof(*pool->len));\n> +\t\tpool->space[pool->nr] = pool->next_free;\n> +\t\tn = pool->nr++;\n> +\t}\n> +\n> +\tif (id_out)\n> +\t\t*id_out = id;\n> +\tid++;\n> +\n> +\tchar *t = &pool->len[n][sizeof(*pool->len) - pool->len_free];\n\nPlease avoid decl_after_statement.\n\n> +\tif (encode_varint(&t, pool->len[n] + sizeof(*pool->len), len))\n> +\t\treturn NULL;\n> +\tpool->len_free = pool->len[n] + sizeof(*pool->len) - t;\n> +\n> +\tr = pool->next_free;\n> +\tpool->next_free += len;\n> +\treturn r;\n> +}\n> +\n> +void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out)\n> +{\n> +\tchar *r;\n> +\tconst char *t;\n> +\tuint64_t len = 0, cur;\n> +\n> +\tif (!id || !pool->nr)\n> +\t\treturn NULL;\n> +\n> +\tsize_t n = pool->nr * id / pool->first_id[pool->nr - 1];\n> +\tif (n >= pool->nr - 1)\n> +\t\tn = pool->nr - 1;\n> +\twhile (n && pool->first_id[n] > id)\n> +\t\tn--;\n> +\twhile (n + 1 < pool->nr && pool->first_id[n + 1] <= id)\n> +\t\tn++;\n\nI was about to say \"bsearch?\", but perhaps it is not worth it.\n\n> +\tif (pool->first_id[n] > id)\n> +\t\treturn NULL;\n> +\n> +\tcur = pool->first_id[n];\n> +\tfor (r = pool->space[n], t = (const char*) pool->len[n];\n> +\t     !decode_varint(&t, pool->len[n] + sizeof(*pool->len), &len);\n> +\t     r += len, cur++)\n> +\t\tif (cur == id) {\n> +\t\t\tif (len_out)\n> +\t\t\t\t*len_out = len;\n> +\t\t\treturn r;\n> +\t\t}\n> +\treturn NULL;\n> +}\n> diff --git a/small-alloc.h b/small-alloc.h\n> new file mode 100644\n> index 0000000..eb77491\n> --- /dev/null\n> +++ b/small-alloc.h\n> @@ -0,0 +1,18 @@\n> +#ifndef SMALL_ALLOC_H_\n> +#define SMALL_ALLOC_H_\n> +\n> +struct mem_pool {\n> +\tsize_t *first_id;\n> +\tchar **space;\n> +\tchar (*len)[sizeof(size_t) + sizeof(char*)];\n\nEach element of pool->len[] is just a byte-array that stores varint, no?\nIt is very misleading to specify its size as sizeof(size_t)+sizeof(char*)\nas if you would store a \"struct { size_t some; char *thing; }\" here.\n\nInstead of having two independently depleted byte-buffer (space[] and\nlen[]), I wonder if it would be more space efficient (without being less\nprocessing efficient) to use a single buffer space.  Your pool_ptr() would\nstart at the beginning of pool->space[n], decode a varint and take it as a\nlength, if that is not the object you are looking for, skip that many\nbytes (i.e. payload immediately follows the length) to the next object,\nand so on.\n\nAlso what kind of alignment guarantee would we _want_ to give the callers?\nAs far as I can tell, this implementation does not guarantee any alignment.\n\n> +\tsize_t f_alloc, s_alloc, l_alloc, nr;\n> +\tchar *next_free;\n> +\tchar *end;\n> +\tint len_free;\n> +\tsize_t total_allocd;\n> +};\n> +\n> +void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out);\n> +void *pool_ptr(struct mem_pool *pool, size_t id, size_t *len_out);\n> +\n> +#endif\n"},{"id":"170508","messageId":"7vpqm431sl.fsf@alter.siamese.dyndns.org","threadId":"27684","inReplyTo":"1308728011-14136-3-git-send-email-davidbarr@google.com","subject":"Re: [RFC/PATCH 2/3] small-alloc: add allocator for small objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-23T17:17:30Z","receivedAt":"2011-06-23T17:17:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr <davidbarr@google.com> writes:\n\n> This allocator assigns an integer handle to each allocation which can be\n> used to retrieve the pointer to the start of the allocation and its\n> length.\n\nOne more thing to add to yesterday's review. I think you would need to\ninclude a \"method\" that initializes a mem_pool object, and possibly\nanother to destroy an existing one, freeing the resources (unless the API\nis meant to replace something like obj_hash in object.c).\n\nIt was quite difficult to judge how good this API is as it took\nimagination on the reviewer's part on how a typical caller would look\nlike.\n"},{"id":"170510","messageId":"7vliws31k8.fsf@alter.siamese.dyndns.org","threadId":"27684","inReplyTo":"1308728011-14136-2-git-send-email-davidbarr@google.com","subject":"Re: [RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-23T17:22:31Z","receivedAt":"2011-06-23T17:22:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr <davidbarr@google.com> writes:\n\n> One struct to capture all types, just 4 methods: decode_message,\n> encode_message, sizeof_message, hash_field.\n\nAdding to the review from yesterday, hash_field() looked quite out of\nplace. If you are going to implement a hash table that holds protobuf\nobjects in a separate file/module, I would imagine the function belongs\nthere, not here.\n\n> +uint32_t hash_field(const struct protobuf_field *field)\n> +{\n> +\tuint32_t hc = 0;\n> +\tswitch (field->type) {\n> +\tcase WT_VARINT:\n> +\tcase WT_64BIT:\n> +\t\thc = (0x9e3779b97f4a7c15ull * field->val.num) >> 32;\n> +\t\tbreak;\n> +\tcase WT_SHA1:\n> +\t\tmemcpy(&hc, field->val.bin.ptr, sizeof(hc));\n> +\t\tbreak;\n> +\tcase WT_STRING:\n> +\t\thc = x65599(field->val.bin.ptr, field->val.bin.len);\n> +\t\tbreak;\n> +\tcase WT_32BIT:\n> +\t\thc = 0x9e3779b9ul * (uint32_t)field->val.num;\n> +\t\tbreak;\n> +\t}\n> +\treturn hc;\n> +}\n\nIt all depends on how you envision a \"hash table of protobuf objects\" is\nto be used, but what is the point of using a complex math for 64BIT/32BIT\ninteger values? If you plan to have different kinds of protobuf objects\nthrown into a single hash table, it may make sense, but without a crystal\nball it was kind of hard to judge.\n"},{"id":"170531","messageId":"BANLkTi=34cQvU9oE0gPe=5PFDYfhxoYF+A@mail.gmail.com","threadId":"27684","inReplyTo":"7vk4cd617u.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 2/3] small-alloc: add allocator for small objects","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-24T14:38:51Z","receivedAt":"2011-06-24T14:38:51Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Junio,\n\nSorry for the repeat, accidentally sent as HTML, rejected by the list.\n\nOn Wednesday, June 22, 2011, Junio C Hamano wrote:\nDavid Barr <davidbarr@google.com> writes:\n\n> +void *pool_alloc(struct mem_pool *pool, size_t len, size_t *id_out)\n> +{\n> +     static size_t id = 1;\n\nDoes this mean that even though you can have more than one mem_pool object\nactive in the system, you won't have id collision throughout the system?\nThat is a nice property (e.g. given an ID that does not belong to a pool,\nyou won't risk returning a wrong chunk of <mem,len> pair from pool_ptr()),\nbut is there a downside using function-scope static like this, I wonder?\n\nThis is an artifact that I missed in refactoring my experimental code.\nThis ought to be a field in struct mem_pool.\nMy intent was for id's to be unique and contiguous within a pool.\n\nFor example, if I have two pools A and B, and call pool_alloc on A and\nthen on B and then on A again, A's space[0] will have the first and the\nthird object, with id=1 and id=3. How does this interact with your\nimplementation of pool_ptr() which seems to assume that id's are\nconsecutive within a single pool->space[]?\n\nIt would interact very poorly.\n\n> +     size_t n;\n\n> +     void *r;\n> +\n> +     if ((pool->end - pool->next_free >= len) &&\n> +         (pool->len_free >= sizeof_varint(len)))\n> +             n = pool->nr - 1;\n\nHelp me make sure I understand what is going on here.\n\nA mem-pool has pool->nr chunks (and it can grow as more memory is asked\nfrom this pool). A new memory request is satisfied by carving out of\npool->space[n] (where n is the \"newest chunk\" in the pool).\npool->len[n] is a fixed sized byte array and stores the length of each\nmemory block carved out of pool->space[n] as a sequence of varint.\nIf pool->space[n] has enough space to fit \"len\" bytes, and if pool->len[n]\nstill has enough space to record the length, you use the current chunk,\notherwise (i.e. the else clause) you add a new chunk.\n\nAm I with you so far?\n\nAbsolutely.\n\nWith the chunk_size of 2MB, you would fit roughly 16k allocation requests\nfor 128-byte memory, and you would need 2-bytes to express the length of\none piece of memory in your varint encoding, i.e. you would need to size\nan element of pool->len[] to 32kB if you wanted to store 16k allocation of\n128-byte for a chunk.\n\nThis would all depend on what the expected distribution of request size,\nbut it somehow feels wasteful to be limited by both space[] and len[]. If\nyou chose sizeof(*pool->len) that is too small for the workload, wouldn't\nyou end up allocating many 2MB space[], only to use potentially very\ninitial parts of them before len[] fills up?\n\nYes, this is a weakness of this iteration of the design.\n\n> +     if (id_out)\n\n> +             *id_out = id;\n> +     id++;\n> +\n> +     char *t = &pool->len[n][sizeof(*pool->len) - pool->len_free];\n\nPlease avoid decl_after_statement.\n\nThanks for the reminder, will clean up some more.\n\n> +     size_t n = pool->nr * id / pool->first_id[pool->nr - 1];\n\n> +     if (n >= pool->nr - 1)\n> +             n = pool->nr - 1;\n> +     while (n && pool->first_id[n] > id)\n> +             n--;\n> +     while (n + 1 < pool->nr && pool->first_id[n + 1] <= id)\n> +             n++;\n\nI was about to say \"bsearch?\", but perhaps it is not worth it.\n\nA linear guesstimate is typically off by a small amount, so linear\nsearch is fine.\nAlso, the index of id's is contiguous, so linear search has good cache locality.\nIf I address the next concern in this review, this search will no\nlonger be necessary.\n\n> +struct mem_pool {\n> +     size_t *first_id;\n> +     char **space;\n> +     char (*len)[sizeof(size_t) + sizeof(char*)];\n\nEach element of pool->len[] is just a byte-array that stores varint, no?\nIt is very misleading to specify its size as sizeof(size_t)+sizeof(char*)\nas if you would store a \"struct { size_t some; char *thing; }\" here.\n\nInstead of having two independently depleted byte-buffer (space[] and\nlen[]), I wonder if it would be more space efficient (without being less\nprocessing efficient) to use a single buffer space.  Your pool_ptr() would\nstart at the beginning of pool->space[n], decode a varint and take it as a\nlength, if that is not the object you are looking for, skip that many\nbytes (i.e. payload immediately follows the length) to the next object,\nand so on.\n\nI have already investigated this arrangement, it has very poor\nlocality of access.\nFor objects <32 bytes long, its not too bad since typically 2 bytes of a 64 byte\ncache line would be read consecutively. For larger objects this is pathological\ncache behavior. On the other hand, the current design means that the entire\nsequence of lengths will fit on a single >=16 byte cache line.\n\nAlso what kind of alignment guarantee would we _want_ to give the callers?\nAs far as I can tell, this implementation does not guarantee any alignment.\n\nNo alignment guarantee provided. An interesting possibility is to provide a\nguarantee and use the padding bytes for metadata.\n\nAlthough on second reading I think I must have mis-read, I've been investigating\nfixing the number of objects per chunk rather than fixing the space for lengths.\nI have an inkling that I already considered this and found that it introduced a\nnasty corner case. This investigation is ongoing.\n\n--\nDavid Barr.\n"},{"id":"170532","messageId":"BANLkTimov2ZFYZjU4=CXPE8yjH8cMs3HCg@mail.gmail.com","threadId":"27684","inReplyTo":"7voc1p64ap.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-24T14:39:42Z","receivedAt":"2011-06-24T14:39:42Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Junio,\n\nSorry for the repeat, accidentally sent as HTML, rejected by the list.\n\nOn Thursday, June 23, 2011, Junio C Hamano wrote:\nDavid Barr <davidbarr@google.com> writes:\n\n> One struct to capture all types, just 4 methods: decode_message,\n> encode_message, sizeof_message, hash_field.\n\nAdding to the review from yesterday, hash_field() looked quite out of\nplace. If you are going to implement a hash table that holds protobuf\nobjects in a separate file/module, I would imagine the function belongs\nthere, not here.\n\nI agree completely, another artifact of refactoring from experimental code.\n\n--\nDavid Barr\n"},{"id":"170534","messageId":"BANLkTim3WeCHp=ECDBcbHjT=Guv_epL90Q@mail.gmail.com","threadId":"27684","inReplyTo":"7voc1p64ap.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-24T16:04:11Z","receivedAt":"2011-06-24T16:04:11Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Hi,\n\nOn Wed, Jun 22, 2011 at 12:42 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> David Barr <davidbarr@google.com> writes:\n>>  protobuf.c |  193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>>  protobuf.h |   70 ++++++++++++++++++++++\n>\n> How does this relate to http://code.google.com/p/protobuf/ which has a\n> very similar name?  If we do not intend to have any interoperability with\n> it, we should avoid such a confusing name, I think.\n\nThe relationship is that the design is shamelessly copied.\nThe reason for going with this particular design is that it very closely mirrors\nmy though experiments on the subject but is supported by heavy use for\nreal workloads. This is of course offset by introducing git-specific tweaks\nand removing network order constraints.\n\n>> diff --git a/protobuf.c b/protobuf.c\n>> new file mode 100644\n>> index 0000000..09223dd\n>> --- /dev/null\n>> +++ b/protobuf.c\n>> @@ -0,0 +1,193 @@\n>> +#include \"git-compat-util.h\"\n>> +#include \"protobuf.h\"\n>> +#include \"varint.h\"\n>> +\n>> +static int decode_binary(const char **buf, const char *end, const char **result, size_t len)\n>> +{\n>> +     if (end && *buf + len > end)\n>> +             return 1;\n>\n> In low-level library-ish code, we tend to signal an error with a negative\n> value and success with zero, unless there is a compelling reason not to.\n>\n> When this error is triggered, what does it tell us?  Programming error\n> (i.e. BUG())?  Incoming data stream error?\n\nThis would be a programming error, since the interface provides a method\nto calculate the required buffer size before persisting it.\n\n>> +static int decode_field(const char **buf, const char *end, struct protobuf_field *field)\n>> +{\n>> +     uint32_t u32;\n>> +     uint64_t key;\n>> +     bzero(field, sizeof(struct protobuf_field));\n>\n> Please use memset(..., '\\0', ...), as we use functions from memXXX()\n> family declared in <string.h>, just like you chose to use memcpy() over\n> bcopy() in encode_binary() above.\n\nWill do.\n>> +     case WT_64BIT:\n>> +             memcpy(&field->val.num, field->val.bin.ptr, field->val.bin.len);\n>> +             break;\n>> +     case WT_32BIT:\n>> +             memcpy(&u32, field->val.bin.ptr, field->val.bin.len);\n>> +             field->val.num = u32;\n>\n> Is there any need for byte-order considerations, or an encoded \"message\"\n> is defined (by this library) to use host encoding, and will never be sent\n> over the wire to other systems in the future?\n\nHost encoding is intentional but only because network encoding is a little\nmessy to write for 64-bit values. I don't think its prohibitive to implement.\n\n>> +int decode_message(const char **buf, const char *end, struct protobuf_field *message, size_t fields)\n>> +{\n>> +     struct protobuf_field current;\n>> +     bzero(message, fields * sizeof(struct protobuf_field));\n>> +     while (*buf != end) {\n>> +             if (decode_field(buf, end, &current))\n>> +                     return 1;\n>> +             if (current.tag < fields)\n>> +                     message[current.tag] = current;\n>\n> Is there any need to check the incoming *buf for duplicated tags, whose\n> payload may overwrite an element in message[] that was populated in the\n> previous iteration of this loop?\n\nThis feature comes from the original protobuf design.\nIt allows values to be updated by appending to the buffer.\n\n> Could decode_field() move *buf beyond end (IOW, would it be an improvement\n> if we said \"while (*buf < end)\" instead)?\n\nThe contract is that decode_field() will not move *buf beyond end.\nHowever for clarity, \"while (*buf < end)\" is better.\n\n>> +static size_t sizeof_field(const struct protobuf_field *field)\n>> +{\n>> +     size_t sizeof_key = sizeof_varint(field->tag << WT_BITS | field->type);\n>> +     switch (field->type) {\n>> +     case WT_VARINT:\n>> +             if (field->val.num)\n>> +                     return sizeof_key + sizeof_varint(field->val.num);\n>> +             break;\n>> +     case WT_64BIT:\n>> +             if (field->val.num)\n>> +                     return sizeof_key + sizeof(uint64_t);\n>> +             break;\n>> +     case WT_STRING:\n>> +             if (field->val.bin.len && field->val.bin.ptr)\n>> +                     return sizeof_key + sizeof_varint(field->val.bin.len)\n>> +                            + field->val.bin.len;\n>> +             break;\n>> +     case WT_SHA1:\n>> +             if (field->val.bin.ptr)\n>> +                     return sizeof_key + 20;\n>> +             break;\n>> +     case WT_32BIT:\n>> +             if (field->val.num)\n>> +                     return sizeof_key + sizeof(uint32_t);\n>> +             break;\n>> +     }\n>> +     return 0;\n>\n> Doesn't this function want to return an error when it does not understand\n> what is in field->type field? If yes, I would imagine that this function\n> needs to be of type ssize_t, you would return -1 here, and the callers\n> would check the return value.\n\nYes, just to be clear, something like:\n  break;\n+ default:\n+   return -1;\n  }\n\n>> +static uint32_t x65599(const char *s, uint64_t len)\n>> +{\n>> +     uint32_t r = 0;\n>> +     while (len--)\n>> +             r = *s++ + (r << 6) + (r << 16) - r;\n>> +     return r;\n>\n> Would it be an improvement if we made sure that each byte in s is taken as\n> unsigned (or signed if you really wanted to but I do not see why) char on\n> all platforms to guarantee reproducibility?\n\nAlthough it shouldn't affect hash distribution, reproducibility is good.\n\n>> +}\n>> +\n>> +uint32_t hash_field(const struct protobuf_field *field)\n>> +{\n>> +     uint32_t hc = 0;\n>> +     switch (field->type) {\n>> +     case WT_VARINT:\n>> +     case WT_64BIT:\n>> +             hc = (0x9e3779b97f4a7c15ull * field->val.num) >> 32;\n>> +             break;\n>> +     case WT_SHA1:\n>> +             memcpy(&hc, field->val.bin.ptr, sizeof(hc));\n>> +             break;\n>> +     case WT_STRING:\n>> +             hc = x65599(field->val.bin.ptr, field->val.bin.len);\n>> +             break;\n>> +     case WT_32BIT:\n>> +             hc = 0x9e3779b9ul * (uint32_t)field->val.num;\n>> +             break;\n>> +     }\n>> +     return hc;\n>> +}\n>\n> Please make the magic Q64 and Q32 into symbolic constants somewhere in\n> this file, or at least give comment. Naming 65599 to SOMETHING_PRIME would\n> also be better.\n\nMaybe some documentation ought to be attached describing why 65599.\nIts not just any prime [1], it has very good mixing characteristics mod 2^32.\nAlso its form, 2^a +/- 2^b +/- 1, enables multiplication using just 2\nshift operations.\nIt produces less collisions than 31 for short strings.\n\n>> +#define VLI_CONTINUE 0x80\n>> +#define VLI_DIGIT_MASK       0x7f\n>> +#define VLI_BITS_PER_DIGIT 7\n>> +\n>> +static int decode_varint(const char **buf, const char *end, uint64_t *result)\n>> +{\n>> +     uint64_t rv = 0;\n>> +     int shift = 0;\n>> +     const char *pos;\n>> +     for (pos = *buf; pos != end && shift < 64; pos++) {\n>> +             unsigned char ch = *pos;\n>> +\n>> +             rv |= (ch & VLI_DIGIT_MASK) << shift;\n>> +             shift += VLI_BITS_PER_DIGIT;\n>> +             if (ch & VLI_CONTINUE)\n>> +                     continue;\n>> +\n>> +             *result = rv;\n>> +             *buf = pos + 1;\n>> +             return 0;\n>\n> This seems to be the same 7-bit-at-a-time encoding used to encode object\n> size in packfiles, which is slightly looser than the one used to express\n> the pack offset of base objects (Cf. eb32d23 -- introduce delta objects\n> with offset to base, 2006-09-21). Would it make more sense to use the\n> slightly tighter one?\n\nI'm inclined to use the tighter encoding but it does have implications for the\ncomplexity of encoding. Decoding remains simple.\n\n--\nDavid Barr\n\n[1] http://www.cse.yorku.ca/~oz/hash.html#sdbm\n"},{"id":"170535","messageId":"7vei2j18hg.fsf@alter.siamese.dyndns.org","threadId":"27684","inReplyTo":"BANLkTim3WeCHp=ECDBcbHjT=Guv_epL90Q@mail.gmail.com","subject":"Re: [RFC/PATCH 1/3] protobuf: minimal implementation for compact in-memory structures","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-06-24T16:48:11Z","receivedAt":"2011-06-24T16:48:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr <davidbarr@google.com> writes:\n\n>> How does this relate to http://code.google.com/p/protobuf/ which has a\n>> very similar name?  If we do not intend to have any interoperability with\n>> it, we should avoid such a confusing name, I think.\n>\n> The relationship is that the design is shamelessly copied.\n\n... and this will be API and bytestream compatible with that other\nprotobuf?\n\nIf not, please don't use that name. It confuses people, and if somebody\nwants to take libified part of our codebase into their application and\nlink with the real protobuf, it will get even more confusing ;-).\n\nYou can (and should) still state that the design was inspired by the other\nwork in the comment at the beginning of the file or something.\n\nThanks.\n"},{"id":"170536","messageId":"BANLkTi=1NhVHMScynVFWxQo2H_mAGq0t1Q@mail.gmail.com","threadId":"27684","inReplyTo":"BANLkTi=34cQvU9oE0gPe=5PFDYfhxoYF+A@mail.gmail.com","subject":"Re: [RFC/PATCH 2/3] small-alloc: add allocator for small objects","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-06-24T17:02:16Z","receivedAt":"2011-06-24T17:02:16Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Junio wrote:\n> Instead of having two independently depleted byte-buffer (space[] and\n> len[]), I wonder if it would be more space efficient (without being less\n> processing efficient) to use a single buffer space.  Your pool_ptr() would\n> start at the beginning of pool->space[n], decode a varint and take it as a\n> length, if that is not the object you are looking for, skip that many\n> bytes (i.e. payload immediately follows the length) to the next object,\n> and so on.\n\nDavid Barr wrote:\n> I have already investigated this arrangement, it has very poor\n> locality of access.\n> For objects <32 bytes long, its not too bad since typically 2 bytes of a 64 byte\n> cache line would be read consecutively. For larger objects this is pathological\n> cache behavior. On the other hand, the current design means that the entire\n> sequence of lengths will fit on a single >=16 byte cache line.\n\nAnother approach is to keep the buffers separate but interleave\npointers and lengths.\nI'll give this a go and see if it's an overall improvement.\n\n--\nDavid Barr\n"}]}