{"thread":{"id":"44086","subject":"Journal of Failed Git Experiments, Volume 1","startedAt":"2016-09-14T23:55:56Z","lastAt":"2016-09-25T14:17:51Z","messageCount":8,"participants":["Jeff King","Stefan Beller","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"301942","messageId":"20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net","threadId":"44086","inReplyTo":null,"subject":"Journal of Failed Git Experiments, Volume 1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-14T23:55:48Z","receivedAt":"2016-09-14T23:55:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I try a lot of different experiments with git performance, some of them\nmore hare-brained than others. The ones that succeed end up as real\npatches. But I hate for the ones that fail to die a quiet death. Then\nnobody learns what _doesn't_ work, and nobody has the opportunity to\npoint out the spot where I made a stupid mistake that invalidates the\nwhole result.\n\nHere are two performance experiments that did _not_ turn out. They\nare in patch form, because I want to document exactly what I did\n(especially because it helps in the \"stupid mistake\" case, or if\nsomebody wants to try building on my results).\n\nSo without further ado:\n\n  [1/2]: obj_hash: convert to a critbit tree\n  [2/2]: use zstd zlib wrapper\n\n-Peff\n"},{"id":"301943","messageId":"20160914235633.gofr534hvslkclzm@sigill.intra.peff.net","threadId":"44086","inReplyTo":"20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net","subject":"[PATCH 1/2] obj_hash: convert to a critbit tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-14T23:56:34Z","receivedAt":"2016-09-14T23:56:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"For operations that traverse the whole reachability graph,\nlike \"rev-list --objects\", the obj_hash in object.c shows up\nas a hotspot. We basically have to do \"nr_commits *\nsize_of_tree\" hash lookups, because each tree we look at, we\nneed to say \"have we seen this sha1 yet?\" (it's a little\nmore complicated because we avoid digging into sub-trees we\nknow we've already seen, but it's a reasonable\napproximation).  So graph traversal operations like that are\nvery sensitive to improvements in lookup time.\n\nFor keys with length \"m\", a hash table is generally O(m) to\ncompute the hash (and verify that you've found the correct\nkey), and O(1) in finding the correct slot. The latter is\nsubject to collisions and probing strategy, but we keep the\nload factor on the obj_hash table below 50%, which is quite\nlow. And we have a good hash (we reuse the sha1s themselves,\nwhich are effectively random). So we'd expect relatively few\ncollisions, and past experiments to tweak the probing\nstrategy haven't yielded any benefit (we use linear probing;\nI tried quadratic probing at one point, and Junio tried\ncuckoo hashing).\n\nAnother data structure with similar properties is sometimes\nknown as a \"critbit tree\" (see http://cr.yp.to/critbit.html\nfor discussion and history). The basic idea is a binary trie\nwhere each node is either an internal node, representing a\nsingle bit of a stored key, or a leaf node, representing one\nor more \"remainder\" bits. So if you were storing two bit\nsequences 1011 and \"1100\", you'd have three nodes (besides\nthe root):\n\n        (root)\n        /    \\\n       0      1\n      /        \\\n    NULL    (internal)\n             /    \\\n            0      1\n           /        \\\n        \"11\"       \"00\"\n\nSo finding \"1011\" involves traversing the trie: down the \"1\"\nside, then the \"0\" side, and then check that the rest\nmatches \"11\".\n\nLooking up a key is O(m), and there's no issue with\ncollisions or probing. It can use less memory than a hash\ntable, because there's no load factor to care about.\n\nThat's the good news. The bad news is that big-O analysis\nis not the whole story. You'll notice that we have to do a\nlot of conditional pointer-jumping to walk the trie. Whereas\na hash table can jump right to a proposed key and do a\nmemcmp() to see if we got it.\n\nSo I wasn't overly optimistic that this would be any faster.\nAnd indeed it's not. It's about three times slower (about\n4.5s versus 1.5s running \"rev-list --objects --all\" on\ngit.git).\n\nThe reason is, I think, a combination of:\n\n  0. We care much more about performance for this hash than\n     memory efficiency. So we keep the load factor\n     quite low, and thus reduce the number of collisions.\n\n  1. For many hash tables, computing the hash is expensive.\n     Not so here, because we are storing sha1s. So it is\n     literally just casting the first 4 bytes of the sha1 to\n     an int; we don't even look at the other bytes until the\n     collision check (and because of point 0, we don't\n     generally have to do very many collision checks during\n     our probe).\n\n  2. The collision check _does_ have to look at all 20 bytes\n     of the sha1. And we may have to do it multiple times as\n     we linearly probe the collisions. _But_ it can be done\n     with memcmp(), which is optimized to compare 32 or 64\n     bits at a time. So we our O(m) has a very nice constant\n     factor.\n\n     Whereas in the critbit tree, we pay an instruction for\n     _each_ bit we look at.\n\nIt's possible that (2) would be better if instead of a\ncritbit tree, we used a \"critbyte\" tree. That would involve\nfewer node traversals, at the cost of making each node\nlarger (right now the internal nodes store 2 pointer slots;\nthey'd have to store 256 to handle a full byte). I didn't\ntry it, but I suspect it would still be slower for the same\nreasons.\n\nThe code is below for reference. I pulled the critbit\nimplementation from:\n\n  https://github.com/ennorehling/critbit\n\nbut made a few tweaks:\n\n  - the critbit does not store the keys themselves, as we\n    already have them in the \"struct object\", and do not\n    want to waste space. As a result, I baked in some\n    assumptions about the 20-byte key-length (which is fine\n    for our purposes here).\n\n  - rather than malloc() each node, I used a pool allocator\n    (to try to keep the nodes closer together in cache)\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile  |   1 +\n critbit.c | 350 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n critbit.h |  60 +++++++++++\n object.c  |  85 ++-------------\n 4 files changed, 417 insertions(+), 79 deletions(-)\n create mode 100644 critbit.c\n create mode 100644 critbit.h\n\ndiff --git a/Makefile b/Makefile\nindex 7f18492..99e0eb2 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -720,6 +720,7 @@ LIB_OBJS += connected.o\n LIB_OBJS += convert.o\n LIB_OBJS += copy.o\n LIB_OBJS += credential.o\n+LIB_OBJS += critbit.o\n LIB_OBJS += csum-file.o\n LIB_OBJS += ctype.o\n LIB_OBJS += date.o\ndiff --git a/critbit.c b/critbit.c\nnew file mode 100644\nindex 0000000..7354375\n--- /dev/null\n+++ b/critbit.c\n@@ -0,0 +1,350 @@\n+/*\n+Copyright (c) 2012, Enno Rehling <enno@eressea.de>\n+\n+Permission to use, copy, modify, and/or distribute this software for any\n+purpose with or without fee is hereby granted, provided that the above\n+copyright notice and this permission notice appear in all copies.\n+\n+THE SOFTWARE IS PROVIDED \"AS IS\" AND THE AUTHOR DISCLAIMS ALL WARRANTIES\n+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF\n+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR\n+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES\n+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN\n+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF\n+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.\n+**/\n+\n+#include \"cache.h\"\n+#include \"critbit.h\"\n+\n+/* see http://cr.yp.to/critbit.html */\n+struct critbit_node {\n+    void * child[2];\n+    size_t byte;\n+    unsigned int mask;\n+};\n+\n+#define EXTERNAL_NODE 0\n+#define INTERNAL_NODE 1\n+\n+static int decode_pointer(void ** ptr)\n+{\n+    ptrdiff_t numvalue = (char*)*ptr - (char*)0;\n+    if (numvalue & 1) {\n+        *ptr = (void*)(numvalue - 1);\n+        return EXTERNAL_NODE;\n+    }\n+    return INTERNAL_NODE;\n+}\n+\n+static void * make_external_node(const void * key, size_t keylen)\n+{\n+    return (unsigned char *)key + 1;\n+}\n+\n+static void from_external_node(void * ptr, void **key, size_t *keylen)\n+{\n+    /* eek */\n+    *keylen = 20;\n+    *key = ptr;\n+}\n+\n+static struct critbit_node *node_pool;\n+static int node_pool_used;\n+static int node_pool_alloc;\n+\n+static struct critbit_node * make_internal_node(void)\n+{\n+    if (node_pool_used == node_pool_alloc) {\n+        node_pool_alloc = 1024;\n+        node_pool_used = 0;\n+        ALLOC_ARRAY(node_pool, node_pool_alloc);\n+    }\n+    return &node_pool[node_pool_used++];\n+}\n+\n+static int cb_less(const struct critbit_node * a, const struct critbit_node * b)\n+{\n+    return a->byte < b->byte || (a->byte == b->byte && a->mask < b->mask);\n+}\n+\n+int cb_insert(critbit_tree * cb, const void * key, size_t keylen)\n+{\n+    assert(cb);\n+    assert(key);\n+    if (!cb->root) {\n+        cb->root = make_external_node(key, keylen);\n+        return CB_SUCCESS;\n+    }\n+    else {\n+        void ** iter = &cb->root;\n+        struct critbit_node * prev = 0;\n+        for (;;) {\n+            void * ptr = *iter;\n+            if (decode_pointer(&ptr) == INTERNAL_NODE) {\n+                struct critbit_node * node = (struct critbit_node *)ptr;\n+                unsigned char * bytes = (unsigned char *)key;\n+                int branch = (keylen <= node->byte) ? 0 : ((1 + ((bytes[node->byte] | node->mask) & 0xFF)) >> 8);\n+                iter = &node->child[branch];\n+                prev = node;\n+            }\n+            else {\n+                unsigned char *iptr, *bytes = (unsigned char *)key, *ikey = bytes;\n+                void * vptr;\n+                unsigned int mask, byte = 0;\n+                int branch;\n+                size_t len;\n+                struct critbit_node * node;\n+\n+                from_external_node(ptr, &vptr, &len);\n+\n+                for (iptr = vptr; byte < keylen && byte < len && *ikey == *iptr;) {\n+                    ++ikey;\n+                    ++iptr;\n+                    ++byte;\n+                }\n+\n+                if (byte == keylen && byte == len) {\n+                    return CB_EXISTS; /* duplicate entry */\n+                }\n+                node = make_internal_node();\n+                node->byte = byte;\n+                mask = *ikey ^ *iptr; /* these are all the bits that differ */\n+                mask |= mask >> 1;\n+                mask |= mask >> 2;\n+                mask |= mask >> 4; /* now, every bit up to the MSB is set to 1 */\n+                mask = (mask&~(mask >> 1)) ^ 0xFF;\n+                node->mask = (unsigned char)mask;\n+\n+                /* find the right place to insert, iff prev's crit-bit is later in the string than new crit-bit */\n+                if (prev && cb_less(node, prev)) {\n+                    for (iter = &cb->root;;) {\n+                        ptr = *iter;\n+                        if (decode_pointer(&ptr) == INTERNAL_NODE) {\n+                            struct critbit_node * next = (struct critbit_node *)ptr;\n+                            if (cb_less(next, node)) {\n+                                branch = ((1 + ((bytes[next->byte] | next->mask) & 0xFF)) >> 8);\n+                                iter = &next->child[branch];\n+                            }\n+                            else {\n+                                break;\n+                            }\n+                        }\n+                        else {\n+                            assert(!\"should never get here\");\n+                        }\n+                    }\n+                }\n+\n+                branch = ((1 + ((*ikey | node->mask) & 0xFF)) >> 8);\n+                node->child[branch] = make_external_node(key, keylen);\n+                node->child[1 - branch] = *iter;\n+                *iter = (void *)node;\n+\n+                return CB_SUCCESS;\n+            }\n+        }\n+    }\n+}\n+\n+static void * cb_find_top_i(const critbit_tree * cb, const void * key, size_t keylen)\n+{\n+    void *ptr, *top = 0;\n+    assert(key);\n+\n+    if (!cb->root) {\n+        return 0;\n+    }\n+    for (ptr = cb->root, top = cb->root;;) {\n+        void * last = ptr;\n+        if (decode_pointer(&ptr) == INTERNAL_NODE) {\n+            struct critbit_node * node = (struct critbit_node *)ptr;\n+            int branch;\n+            if (keylen <= node->byte) {\n+                break;\n+            }\n+            else {\n+                unsigned char * bytes = (unsigned char *)key;\n+                top = last;\n+                branch = (1 + ((bytes[node->byte] | node->mask) & 0xFF)) >> 8;\n+                ptr = node->child[branch];\n+            }\n+        }\n+        else {\n+            /* we reached an external node before exhausting the key length */\n+            top = last;\n+            break;\n+        }\n+    }\n+    return top;\n+}\n+\n+static int cb_find_prefix_i(void * ptr, const void * key, size_t keylen, void ** results, int numresults, int * offset, int next)\n+{\n+    assert(next <= numresults);\n+    if (next == numresults) {\n+        return next;\n+    }\n+    else if (decode_pointer(&ptr) == INTERNAL_NODE) {\n+        struct critbit_node * node = (struct critbit_node *)ptr;\n+        next = cb_find_prefix_i(node->child[0], key, keylen, results, numresults, offset, next);\n+        if (next < numresults) {\n+            next = cb_find_prefix_i(node->child[1], key, keylen, results, numresults, offset, next);\n+        }\n+    }\n+    else {\n+        /* reached an external node */\n+        char * str;\n+        void * vptr;\n+        size_t len;\n+\n+        from_external_node(ptr, &vptr, &len);\n+        str = vptr;\n+        if (len >= keylen && memcmp(key, str, keylen) == 0) {\n+            if (*offset>0) {\n+                --*offset;\n+            }\n+            else {\n+                results[next++] = str;\n+            }\n+        }\n+    }\n+    return next;\n+}\n+\n+int cb_find_prefix(const critbit_tree * cb, const void * key, size_t keylen, void ** results, int numresults, int offset)\n+{\n+    if (numresults > 0) {\n+        void *top = cb_find_top_i(cb, key, keylen);\n+        if (top) {\n+            /* recursively add all children except the ones from [0-offset) of top to the results */\n+            return cb_find_prefix_i(top, key, keylen, results, numresults, &offset, 0);\n+        }\n+    }\n+    return 0;\n+}\n+\n+static int cb_foreach_i(void * ptr, const void * key, size_t keylen, int(*match_cb)(const void * match, const void * key, size_t keylen, void *), void *data)\n+{\n+    int result = 0;\n+\n+    if (decode_pointer(&ptr) == INTERNAL_NODE) {\n+        struct critbit_node * node = (struct critbit_node *)ptr;\n+        result = cb_foreach_i(node->child[0], key, keylen, match_cb, data);\n+        if (!result) {\n+            result = cb_foreach_i(node->child[1], key, keylen, match_cb, data);\n+        }\n+    }\n+    else {\n+        /* reached an external node */\n+        void * match;\n+        size_t len;\n+\n+        from_external_node(ptr, &match, &len);\n+        if (len >= keylen && memcmp(key, match, keylen) == 0) {\n+            return match_cb(match, key, keylen, data);\n+        }\n+    }\n+    return result;\n+}\n+\n+int cb_foreach(critbit_tree * cb, const void * key, size_t keylen, int(*match_cb)(const void * match, const void * key, size_t keylen, void *), void *data)\n+{\n+    void *top = cb_find_top_i(cb, key, keylen);\n+    if (top) {\n+        /* recursively add all children except the ones from [0-offset) of top to the results */\n+        return cb_foreach_i(top, key, keylen, match_cb, data);\n+    }\n+    return 0;\n+}\n+\n+const void * cb_find(critbit_tree * cb, const void * key, size_t keylen)\n+{\n+    void * str;\n+    size_t len;\n+    unsigned char * bytes = (unsigned char *)key;\n+    void * ptr;\n+\n+    assert(cb);\n+    assert(key);\n+    if (!cb->root) return 0;\n+    for (ptr = cb->root; decode_pointer(&ptr) == INTERNAL_NODE; ) {\n+        struct critbit_node *node = (struct critbit_node *)ptr;\n+        uint8_t c = 0;\n+        int direction;\n+        if (node->byte < keylen)\n+            c = bytes[node->byte];\n+        direction = (1+(c|node->mask))>>8;\n+        ptr = node->child[direction];\n+    }\n+    from_external_node(ptr, &str, &len);\n+    if (len >= keylen && memcmp(key, str, keylen) == 0) {\n+        return str;\n+    }\n+    return 0;\n+}\n+\n+int cb_erase(critbit_tree * cb, const void * key, size_t keylen)\n+{\n+    void **iter = NULL;\n+    void *ptr = cb->root;\n+    struct critbit_node *parent = 0;\n+    unsigned char * bytes = (unsigned char *)key;\n+    int branch;\n+\n+    if (!cb->root) return CB_NOTFOUND;\n+\n+    for (;;) {\n+        int type;\n+\n+        type = decode_pointer(&ptr);\n+        if (type == INTERNAL_NODE) {\n+            iter = parent ? &parent->child[branch] : &cb->root;\n+            parent = (struct critbit_node*)ptr;\n+            branch = (keylen <= parent->byte) ? 0 : ((1 + ((bytes[parent->byte] | parent->mask) & 0xFF)) >> 8);\n+            ptr = parent->child[branch];\n+        }\n+        else {\n+            void * str;\n+            size_t len;\n+            from_external_node(ptr, &str, &len);\n+            if (len == keylen && memcmp(key, str, len) == 0) {\n+                free(ptr);\n+                if (iter) {\n+                    *iter = parent->child[1 - branch];\n+                    free(parent);\n+                }\n+                else {\n+                    cb->root = 0;\n+                }\n+                return CB_SUCCESS;\n+            }\n+            return CB_NOTFOUND;\n+        }\n+    }\n+}\n+\n+size_t cb_new_kv(const char *key, size_t keylen, const void * value, size_t len, void * out)\n+{\n+    char * dst = (char*)out;\n+    if (dst != key) {\n+        memmove(dst, key, keylen);\n+    }\n+    dst[keylen] = 0;\n+    memmove(dst + keylen + 1, value, len);\n+    return len + keylen + 1;\n+}\n+\n+void cb_get_kv(const void *kv, void * value, size_t len)\n+{\n+    const char * key = (const char *)kv;\n+    size_t keylen = strlen(key) + 1;\n+    memmove(value, key + keylen, len);\n+}\n+\n+void cb_get_kv_ex(void *kv, void ** value)\n+{\n+    char * key = (char *)kv;\n+    size_t keylen = strlen(key) + 1;\n+    *value = key + keylen;\n+}\ndiff --git a/critbit.h b/critbit.h\nnew file mode 100644\nindex 0000000..ee774e8\n--- /dev/null\n+++ b/critbit.h\n@@ -0,0 +1,60 @@\n+/*\n+Copyright (c) 2012, Enno Rehling <enno@eressea.de>\n+\n+Permission to use, copy, modify, and/or distribute this software for any\n+purpose with or without fee is hereby granted, provided that the above\n+copyright notice and this permission notice appear in all copies.\n+\n+THE SOFTWARE IS PROVIDED \"AS IS\" AND THE AUTHOR DISCLAIMS ALL WARRANTIES\n+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF\n+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR\n+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES\n+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN\n+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF\n+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.\n+**/\n+\n+#ifndef _CRITBITT_H\n+#define _CRITBITT_H\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+#include <stddef.h>\n+\n+typedef struct critbit_tree {\n+  void * root;\n+} critbit_tree;\n+\n+#define CB_SUCCESS 0\n+#define CB_EXISTS 1\n+#define CB_NOTFOUND 2\n+\n+#define CRITBIT_TREE() { 0 }\n+\n+int cb_insert(critbit_tree * cb, const void * key, size_t keylen);\n+const void * cb_find(critbit_tree * cb, const void * key, size_t keylen);\n+int cb_erase(critbit_tree * cb, const void * key, size_t keylen);\n+int cb_find_prefix(const critbit_tree * cb, const void * key, size_t keylen, void ** results, int numresults, int offset);\n+int cb_foreach(critbit_tree * cb, const void * key, size_t keylen, int (*match_cb)(const void * match, const void * key, size_t keylen, void *), void *data);\n+void cb_clear(critbit_tree * cb);\n+\n+#define cb_insert_str(cb, key) \\\n+  cb_insert(cb, (void *)key, strlen(key)+1)\n+#define cb_find_str(cb, key) \\\n+  (const char *)cb_find(cb, (void *)key, strlen(key)+1)\n+#define cb_erase_str(cb, key) \\\n+  cb_erase(cb, (void *)key, strlen(key)+1)\n+#define cb_find_prefix_str(cb, key, results, numresults, offset) \\\n+  cb_find_prefix(cb, (const void *)key, strlen(key), results, numresults, offset)\n+\n+#define CB_KV_SIZE(keylen, datalen) (keylen+datalen+1)\n+size_t cb_new_kv(const char *key, size_t keylen, const void * value, size_t len, void * out);\n+void cb_get_kv(const void *kv, void * value, size_t len);\n+void cb_get_kv_ex(void *kv, void ** value);\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+#endif\ndiff --git a/object.c b/object.c\nindex 67d9a9e..24d26a8 100644\n--- a/object.c\n+++ b/object.c\n@@ -4,6 +4,7 @@\n #include \"tree.h\"\n #include \"commit.h\"\n #include \"tag.h\"\n+#include \"critbit.h\"\n \n static struct object **obj_hash;\n static int nr_objs, obj_hash_size;\n@@ -51,32 +52,8 @@ int type_from_string_gently(const char *str, ssize_t len, int gentle)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-/*\n- * Return a numerical hash value between 0 and n-1 for the object with\n- * the specified sha1.  n must be a power of 2.  Please note that the\n- * return value is *not* consistent across computer architectures.\n- */\n-static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)\n-{\n-\treturn sha1hash(sha1) & (n - 1);\n-}\n-\n-/*\n- * Insert obj into the hash table hash, which has length size (which\n- * must be a power of 2).  On collisions, simply overflow to the next\n- * empty bucket.\n- */\n-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n-{\n-\tunsigned int j = hash_obj(obj->oid.hash, size);\n \n-\twhile (hash[j]) {\n-\t\tj++;\n-\t\tif (j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j] = obj;\n-}\n+struct critbit_tree objects;\n \n /*\n  * Look up the record for the given sha1 in the hash map stored in\n@@ -84,58 +61,10 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n  */\n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tunsigned int i, first;\n-\tstruct object *obj;\n-\n-\tif (!obj_hash)\n+\tconst unsigned char *ret = cb_find(&objects, sha1, 20);\n+\tif (!ret)\n \t\treturn NULL;\n-\n-\tfirst = i = hash_obj(sha1, obj_hash_size);\n-\twhile ((obj = obj_hash[i]) != NULL) {\n-\t\tif (!hashcmp(sha1, obj->oid.hash))\n-\t\t\tbreak;\n-\t\ti++;\n-\t\tif (i == obj_hash_size)\n-\t\t\ti = 0;\n-\t}\n-\tif (obj && i != first) {\n-\t\t/*\n-\t\t * Move object to where we started to look for it so\n-\t\t * that we do not need to walk the hash table the next\n-\t\t * time we look for it.\n-\t\t */\n-\t\tstruct object *tmp = obj_hash[i];\n-\t\tobj_hash[i] = obj_hash[first];\n-\t\tobj_hash[first] = tmp;\n-\t}\n-\treturn obj;\n-}\n-\n-/*\n- * Increase the size of the hash map stored in obj_hash to the next\n- * power of 2 (but at least 32).  Copy the existing values to the new\n- * hash map.\n- */\n-static void grow_object_hash(void)\n-{\n-\tint i;\n-\t/*\n-\t * Note that this size must always be power-of-2 to match hash_obj\n-\t * above.\n-\t */\n-\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n-\tstruct object **new_hash;\n-\n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n-\tfor (i = 0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n-\t\tif (!obj)\n-\t\t\tcontinue;\n-\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n-\t}\n-\tfree(obj_hash);\n-\tobj_hash = new_hash;\n-\tobj_hash_size = new_hash_size;\n+\treturn (struct object *)(ret - offsetof(struct object, oid));\n }\n \n void *create_object(const unsigned char *sha1, void *o)\n@@ -147,10 +76,8 @@ void *create_object(const unsigned char *sha1, void *o)\n \tobj->flags = 0;\n \thashcpy(obj->oid.hash, sha1);\n \n-\tif (obj_hash_size - 1 <= nr_objs * 2)\n-\t\tgrow_object_hash();\n+\tcb_insert(&objects, &obj->oid, 20);\n \n-\tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n \treturn obj;\n }\n-- \n2.10.0.271.ge3ee153\n\n"},{"id":"301944","messageId":"20160914235843.nacr54ekvl6rjipk@sigill.intra.peff.net","threadId":"44086","inReplyTo":"20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net","subject":"[PATCH 2/2] use zstd zlib wrapper","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-14T23:58:43Z","receivedAt":"2016-09-14T23:59:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There's a fancy new compression algorithm called \"zstd\". The\nidea is that it's supposed to get similar compression ratios\nto zlib, but with much faster compression and decompression\ntimes. And on top of that, a nice sliding scale to trade off\nsize versus time on the compression side.\n\nThe zstd site at https://facebook.github.io/zstd/ claims\nclose to 3x speedup for both compression and decompression\nversus zlib, with similar compression ratios. There are\nother fast algorithms (like lz4), but they usually compress\nmuch worse (follow the link above for a nice table of\nresults).\n\nSince any git operations that have to access objects need to\ndo a zlib inflate, in theory we can speed up everything by\nusing zstd. And then on the packing side, use higher\ncompression levels when making on-disk packfiles (which will\nbe accessed many times) and lower ones when making loose\nobjects, or deflating packed objects on the fly when serving\nfetches.\n\nThe catch, of course, is that it's a new incompatible\nformat. This would be a pretty huge change and totally break\nbackwards compatibility for git, not just on disk but\non-the-wire as well. So my goal here was not a finished\nproduct but just a quick experiment to see if it did indeed\nbring the promise speedups.\n\nDisappointingly, the answer seems to be \"no\".\n\nThe patch is relatively straightforward. zstd ships with a\nzlib-compatible wrapper that we can just plug in. For\ncompression, it writes with zlib by default, but you can\nflip it to zstd mode with a run-time flag. For\ndecompression, it auto-detects and runs the correct choice\nbetween zlib and zstd. So this patch _could_ serve as the\nbasis for a real solution. We'd bundle zstd and its wrapper\nwith the runtime switch off, and then after several years\npeople could enable zstd writing to cut off older clients.\nIn the patch below, that switch is just setting the\npack.compression level to \"zstd1\", \"zstd2\", etc.\n\nI ran a series of tests where I would:\n\n  1. Repack with \"-F\" and a particular pack.compression\n     setting, measuring both the time to repack and the size\n     of the resulting pack.\n\n  2. Time \"git rev-list --objects --all\" to see the effect\n     on commit/tree traversal.\n\n  3. Run \"log -Sfoo --raw\" to see the additional effect on\n     accessing the blobs.\n\nAll the timings below are against linux.git. The rev-list\ntimings are best-of-five, but I didn't do multiple timings\nfor the repack or \"log -S\" tests, because they were so\npainfully slow (and because the effect sizes seemed to be\nlarger than run-to-run noise).\n\nI did these on top of my delta-cache and pack-mru patches,\nsince that would amplify any effect we see (i.e.,\nthose speed up other things so decompression time is a\nrelatively larger share of the pie).\n\nHere's a baseline run using stock zlib, with the default\ncompression settings:\n\n [zlib]\n - pack\n   1122845190\n - repack\n   real    4m43.817s\n   user    17m32.396s\n   sys     0m5.964s\n - rev-list --objects --all\n   real    0m27.378s\n   user    0m27.132s\n   sys     0m0.240s\n - log -Sfoo --raw\n   real    5m3.490s\n   user    5m0.040s\n   sys     0m3.424s\n\nYou can see that we're pretty much CPU bound. You can also\nsee that there's quite a bit of parallelism going on in the\nrepack (this is a quad-core with hyperthreading).\n\nHere's the same thing built against the zstd wrapper, but\nstill using zlib:\n\n [zstd, disabled]\n - pack\n   1123089975\n   (+0.02%)\n - repack\n   real    4m58.263s\n   user    17m50.596s\n   sys     0m7.200s\n   (+5%)\n - rev-list --objects --all\n   real    0m28.143s\n   user    0m27.864s\n   sys     0m0.272s\n   (+3%)\n - log -Sfoo --raw\n   real    5m12.742s\n   user    5m9.804s\n   sys     0m2.912s\n   (+3%)\n\nThe percentages show the difference against the baseline run\nabove (wall-clock times for the timing results). The pack\nsize is similar, which we'd expect (it's not identical\nbecause the threaded delta search is slightly\nnon-deterministic).\n\nSadly we lose 3-5% just to the wrapper sitting in front of\nzlib. So that's not a great start. But it also means we\nmight be able to recover that through code optimizations of\nthe wrapper, the way we call it, etc.\n\nNow here it is with zstd turned onto its lowest setting:\n\n [zstd, 1]\n - pack\n   1199180502\n   (+7%)\n - repack\n   real    4m11.740s\n   user    16m36.510s\n   sys     0m7.700s\n   (-11%)\n - rev-list --objects --all\n   real    0m25.870s\n   user    0m25.632s\n   sys     0m0.232s\n   (-5.5%)\n - log -Sfoo --raw\n   real    4m10.899s\n   user    4m7.788s\n   sys     0m3.056s\n   (-17%)\n\nWe've definitely traded off some space here. But the\ncompression is faster, _and_ so is the decompression.\n\nSo let's bump up the compression level a bit:\n\n [zstd, 3]\n - pack\n   1162416903\n   (+3.5%)\n - repack\n   real    5m1.477s\n   user    19m34.476s\n   sys     0m17.720s\n   (+6.2%)\n - rev-list --objects --all\n   real    0m25.716s\n   user    0m25.468s\n   sys     0m0.244s\n   (-6%)\n - log -Sfoo --raw\n   real    4m10.547s\n   user    4m6.500s\n   sys     0m3.884s\n   (-17%)\n\nOK, the size is improving. But now our compression is\nnoticeably slower. The decompression remains better, which\nis nice. Let's go further:\n\n [zstd, 5]\n - pack\n   1144433165\n   (+2%)\n - repack\n   real    5m46.050s\n   user    22m7.580s\n   sys     1m2.212s\n   (+22%)\n - rev-list --objects --all\n   real    0m25.717s\n   user    0m25.404s\n   sys     0m0.304s\n   (-6%)\n - log -Sfoo --raw\n   real    4m14.651s\n   user    4m11.176s\n   sys     0m3.448s\n   (-16%)\n\nGetting close to parity on the size. But the compression\ntime keeps creeping up.\n\n [zstd, 10]\n - pack\n   1132922195\n   (+0.8%)\n - repack\n   real    41m35.835s\n   user    166m36.956s\n   sys     50m11.436s\n   (+780%)\n - rev-list --objects --all\n   real    0m25.946s\n   user    0m25.656s\n   sys     0m0.284s\n   (-5%)\n - log -Sfoo --raw\n   real    4m8.490s\n   user    4m5.864s\n   sys     0m2.604s\n   (-18%)\n\nOof. We still haven't reached size parity, and now we're\nusing a _lot_ more CPU on the repack.\n\nI wanted to take it all the way to \"22\", zstd's maximum,\njust for fun. But after 2 hours (real time, so pegging all\nmy cores while doing so), we were only at 12% of the delta\nphase. Yikes.\n\nSo...it doesn't seem like a great tradeoff (especially\nconsidering the costs in migrating to a new algorithm). The\ndecompression _is_ delightfully faster, and it's true that\nwe decompress more than we compress. But the speed/size\ntradeoff for compression doesn't seem great.\n\nI'm not sure why we don't get numbers as nice as the ones on\nthe zstd website. Obviously possibility 0 is that I simply\nscrewed something up. But here are some other thoughts /\nwild guesses:\n\n  1. There's clearly some overhead to using the zlib\n     wrapper. Even just calling into zlib with it to\n     compress seems to cost about 5%.\n\n     For zstd, it's less clear. The regular (non-wrapper)\n     zstd API seems to involve allocating a zstd compressor,\n     and then feeding multiple compressions to it. So that\n     would amortize the setup cost. I'd guess that the zlib\n     wrapper has to allocate a new zstd compressor for each\n     wrapped compression (obviously they could share one,\n     but then you run into threading issues).\n\n     The fact that the time increases as we bump the\n     compression level implies to me that the main cost is\n     in the actual compression, though, not in the setup.\n     It's possible that the setup cost is higher when the\n     compression level is higher, but I wouldn't really\n     expect it to scale as rapidly as my numbers show.\n\n     So this is probably making things worse than they\n     otherwise could be, but I doubt it's the real cause of\n     the problems.\n\n  2. Git tends to do a lot of relatively small compressions,\n     as we zlib-compress deltas. So I wonder (and this is a\n     wild guess) if zstd performs more favorably on \"normal\"\n     sized inputs.\n\n     That would be possible to test. Or could probably be\n     found out by digging more into the zstd benchmarks;\n     they used some standard corpuses, but the results are\n     summarized. More broken-down results may show patterns.\n\n     I didn't do those things, hence \"wild guess\".\n\nAnd obviously even this patch series _does_ show an\nimprovement on the decompression side (which happens a lot\nmore often than compression!). So this isn't a total dead\nend. But given the ratio/time tradeoff I saw on the\ncompression side, there are other options. E.g., lz4 is even\nfaster than zstd, but comes with a size penalty (though I\nthink it's more like 30%, not 7%).\n\nI would have liked to test with lz4, too, but they don't\nship a totally trivial zlib wrapper. :)\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile               |  9 +++++++++\n builtin/pack-objects.c | 19 +++++++++++++------\n cache.h                |  4 ++++\n 3 files changed, 26 insertions(+), 6 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 99e0eb2..e29edbe 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1138,6 +1138,15 @@ else\n endif\n IMAP_SEND_LDFLAGS += $(OPENSSL_LINK) $(OPENSSL_LIBSSL) $(LIB_4_CRYPTO)\n \n+# for linking straight out of zstd build directory\n+ifdef ZSTD_PATH\n+\tLIB_OBJS += $(ZSTD_PATH)/zlibWrapper/zstd_zlibwrapper.o\n+\tBASIC_CFLAGS += -I$(ZSTD_PATH)/zlibWrapper\n+\tBASIC_CFLAGS += -I$(ZSTD_PATH)/lib -I$(ZSTD_PATH)/lib/common\n+\tBASIC_CFLAGS += -DUSE_ZSTD\n+\tEXTLIBS += $(ZSTD_PATH)/lib/libzstd.a\n+endif\n+\n ifdef ZLIB_PATH\n \tBASIC_CFLAGS += -I$(ZLIB_PATH)/include\n \tEXTLIBS += -L$(ZLIB_PATH)/$(lib) $(CC_LD_DYNPATH)$(ZLIB_PATH)/$(lib)\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4a63398..b424465 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -62,6 +62,7 @@ static int num_preferred_base;\n static struct progress *progress_state;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n static int pack_compression_seen;\n+static int pack_compression_max = Z_BEST_COMPRESSION;\n \n static struct packed_git *reuse_packfile;\n static uint32_t reuse_packfile_objects;\n@@ -2220,11 +2221,17 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\treturn 0;\n \t}\n \tif (!strcmp(k, \"pack.compression\")) {\n-\t\tint level = git_config_int(k, v);\n-\t\tif (level == -1)\n-\t\t\tlevel = Z_DEFAULT_COMPRESSION;\n-\t\telse if (level < 0 || level > Z_BEST_COMPRESSION)\n-\t\t\tdie(\"bad pack compression level %d\", level);\n+\t\tint level;\n+\t\tif (!v)\n+\t\t\treturn config_error_nonbool(k);\n+#ifdef USE_ZSTD\n+\t\tif (skip_prefix(v, \"zstd\", &v)) {\n+\t\t\tuseZSTD(1);\n+\t\t\t/* XXX doesn't seem to be a constant? */\n+\t\t\tpack_compression_max = 22;\n+\t\t}\n+#endif\n+\t\tlevel = git_config_int(k, v);\n \t\tpack_compression_level = level;\n \t\tpack_compression_seen = 1;\n \t\treturn 0;\n@@ -2765,7 +2772,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\treuse_delta = 0;\n \tif (pack_compression_level == -1)\n \t\tpack_compression_level = Z_DEFAULT_COMPRESSION;\n-\telse if (pack_compression_level < 0 || pack_compression_level > Z_BEST_COMPRESSION)\n+\telse if (pack_compression_level < 0 || pack_compression_level > pack_compression_max)\n \t\tdie(\"bad pack compression level %d\", pack_compression_level);\n \n \tif (!delta_search_threads)\t/* --threads=0 means autodetect */\ndiff --git a/cache.h b/cache.h\nindex 3556326..9b2f8f5 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -37,7 +37,11 @@\n #define git_SHA1_Update\t\tgit_SHA1_Update_Chunked\n #endif\n \n+#ifdef USE_ZSTD\n+#include \"zstd_zlibwrapper.h\"\n+#else\n #include <zlib.h>\n+#endif\n typedef struct git_zstream {\n \tz_stream z;\n \tunsigned long avail_in;\n-- \n2.10.0.271.ge3ee153\n"},{"id":"301947","messageId":"CAGZ79kb4_k=+O6pzQkZBGHQty+kdYTnQX_3110RNt097AVn+Kg@mail.gmail.com","threadId":"44086","inReplyTo":"20160914235633.gofr534hvslkclzm@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] obj_hash: convert to a critbit tree","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-15T00:52:06Z","receivedAt":"2016-09-15T00:52:24Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Sep 14, 2016 at 4:56 PM, Jeff King <peff@peff.net> wrote:\n> For operations that traverse the whole reachability graph,\n> like \"rev-list --objects\", the obj_hash in object.c shows up\n> as a hotspot. We basically have to do \"nr_commits *\n> size_of_tree\" hash lookups, because each tree we look at, we\n> need to say \"have we seen this sha1 yet?\" (it's a little\n> more complicated because we avoid digging into sub-trees we\n> know we've already seen, but it's a reasonable\n> approximation).  So graph traversal operations like that are\n> very sensitive to improvements in lookup time.\n>\n> For keys with length \"m\", a hash table is generally O(m) to\n> compute the hash (and verify that you've found the correct\n> key), and O(1) in finding the correct slot. The latter is\n> subject to collisions and probing strategy, but we keep the\n> load factor on the obj_hash table below 50%, which is quite\n> low. And we have a good hash (we reuse the sha1s themselves,\n> which are effectively random). So we'd expect relatively few\n> collisions, and past experiments to tweak the probing\n> strategy haven't yielded any benefit (we use linear probing;\n> I tried quadratic probing at one point, and Junio tried\n> cuckoo hashing).\n>\n> Another data structure with similar properties is sometimes\n> known as a \"critbit tree\" (see http://cr.yp.to/critbit.html\n> for discussion and history). The basic idea is a binary trie\n> where each node is either an internal node, representing a\n> single bit of a stored key, or a leaf node, representing one\n> or more \"remainder\" bits. So if you were storing two bit\n> sequences 1011 and \"1100\", you'd have three nodes (besides\n> the root):\n>\n>         (root)\n>         /    \\\n>        0      1\n>       /        \\\n>     NULL    (internal)\n>              /    \\\n>             0      1\n>            /        \\\n>         \"11\"       \"00\"\n>\n> So finding \"1011\" involves traversing the trie: down the \"1\"\n> side, then the \"0\" side, and then check that the rest\n> matches \"11\".\n\nSo we stop building a tree as soon as we hit a unique data\nelement (i.e. if we stick to the idea of encoding the hash along the way,\nwe would have needed another node each for \"11\" as well as \"00\"\nthat points to NULL and the ending data respectively.\n\nSo we stop short as soon as we have a unique.\n\nThat makes insertion very easy, because as soon as we hit\na unique, we'd just introduce a node and add the two uniques\nleft and right. (Well what happens if we were to insert\n101010111 and 101010101 ? Both have a long prefix,\nI suppose we'd have 7 nodes and then the distiguishing\nnode for those 2.)\n\n>\n> Looking up a key is O(m), and there's no issue with\n> collisions or probing. It can use less memory than a hash\n> table, because there's no load factor to care about.\n>\n> That's the good news. The bad news is that big-O analysis\n> is not the whole story. You'll notice that we have to do a\n> lot of conditional pointer-jumping to walk the trie. Whereas\n> a hash table can jump right to a proposed key and do a\n> memcmp() to see if we got it.\n>\n> So I wasn't overly optimistic that this would be any faster.\n> And indeed it's not. It's about three times slower (about\n> 4.5s versus 1.5s running \"rev-list --objects --all\" on\n> git.git).\n>\n> The reason is, I think, a combination of:\n>\n>   0. We care much more about performance for this hash than\n>      memory efficiency. So we keep the load factor\n>      quite low, and thus reduce the number of collisions.\n>\n>   1. For many hash tables, computing the hash is expensive.\n>      Not so here, because we are storing sha1s. So it is\n>      literally just casting the first 4 bytes of the sha1 to\n>      an int; we don't even look at the other bytes until the\n>      collision check (and because of point 0, we don't\n>      generally have to do very many collision checks during\n>      our probe).\n>\n>   2. The collision check _does_ have to look at all 20 bytes\n>      of the sha1. And we may have to do it multiple times as\n>      we linearly probe the collisions. _But_ it can be done\n>      with memcmp(), which is optimized to compare 32 or 64\n>      bits at a time. So we our O(m) has a very nice constant\n>      factor.\n>\n>      Whereas in the critbit tree, we pay an instruction for\n>      _each_ bit we look at.\n>\n> It's possible that (2) would be better if instead of a\n> critbit tree, we used a \"critbyte\" tree. That would involve\n> fewer node traversals, at the cost of making each node\n> larger (right now the internal nodes store 2 pointer slots;\n> they'd have to store 256 to handle a full byte). I didn't\n> try it, but I suspect it would still be slower for the same\n> reasons.\n\nI would expect to go for a crit-\"variable-length\" tree instead.\n\nThe reason for this is that a higher fan out seems to be more\nbeneficial in the earlier stages, e.g. we could use critbyte trees\nfor the first 1-3 layers in the tree as that will have good memory\nefficiency (all 256 slots filled), but will be faster than the critbit trees\n(one lookup instead of 8 conditional jumps).\n\nIn a degenerated form a crit-\"variable-length\" tree could be\nimagined as a hashmap with a critbit tree as the collision resolver,\nas we flip from the one extreme of hashmaps (memory inefficient,\nbut O(1) lookup with low constant factors), to the other extreme\nof critbits (memory efficient, but need O(log(size)) nodes which\neach need time per bit)\n\nSo maybe we could start with a crit-word (16bit) node at the top,\nthen have critbyte tree nodes (8 bits), and then go for critbit nodes?\nThe crit-word would have 2**16 entries, i.e. 64k, which is more than\ngit.gits count of objects (~44k), so we'd get the memory inefficiency of\na hash map, combined with slightly higher costs for collision resolving.\n\nI guess when trying to improve the hashsets, someone tried trees\nas a collision resolver?\n\n>\n> The code is below for reference. I pulled the critbit\n> implementation from:\n>\n>   https://github.com/ennorehling/critbit\n>\n> but made a few tweaks:\n>\n>   - the critbit does not store the keys themselves, as we\n>     already have them in the \"struct object\", and do not\n>     want to waste space. As a result, I baked in some\n>     assumptions about the 20-byte key-length (which is fine\n>     for our purposes here).\n>\n>   - rather than malloc() each node, I used a pool allocator\n>     (to try to keep the nodes closer together in cache)\n\n\nI think this is another interesting part, so let's talk about caching.\nWhile we may not care about the memory inefficiency for the lost\nmemory, it is still bad for caches. And the cache inefficiency may\nbe worse than a few instructions of walking down a critbit for\nexample. I was instantly reminded of 9a414486d9f0\n(lookup_object: prioritize recently found objects)\n\nSo maybe we could have some software sided cache for hot entries?\n(I imagine a data structure consisting of 2 hash sets here, one\nhashset containing\nthe complete data set, and the other hashset is a very small hashset with e.g.\njust 256(?) entries that are an LRU cache for the cache entries.\nThough this sounds like we'd be trying to outsmart the hardware... Not sure\nI'd expect gains from that)\n\nI guess we rather want to split up the data sets on the application\nside: i.e. instead of\nhaving so many objects, have hash sets for e.g. blobs, trees, commits separately\nand then use slightly different strategies there (different load factors?)\n\nUnrelated note about hashmaps:\nI wonder if we rather want to give good initial estimates of the size\nas one improvement\n\n\nThanks for posting these patches!\nThey are really fun to learn from!\n\nStefan\n"},{"id":"301949","messageId":"20160915011353.l5lx6ltcn2zegbnx@sigill.intra.peff.net","threadId":"44086","inReplyTo":"CAGZ79kb4_k=+O6pzQkZBGHQty+kdYTnQX_3110RNt097AVn+Kg@mail.gmail.com","subject":"Re: [PATCH 1/2] obj_hash: convert to a critbit tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-15T01:13:54Z","receivedAt":"2016-09-15T01:14:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 14, 2016 at 05:52:06PM -0700, Stefan Beller wrote:\n\n> > So finding \"1011\" involves traversing the trie: down the \"1\"\n> > side, then the \"0\" side, and then check that the rest\n> > matches \"11\".\n> \n> So we stop building a tree as soon as we hit a unique data\n> element (i.e. if we stick to the idea of encoding the hash along the way,\n> we would have needed another node each for \"11\" as well as \"00\"\n> that points to NULL and the ending data respectively.\n> \n> So we stop short as soon as we have a unique.\n> \n> That makes insertion very easy, because as soon as we hit\n> a unique, we'd just introduce a node and add the two uniques\n> left and right. (Well what happens if we were to insert\n> 101010111 and 101010101 ? Both have a long prefix,\n> I suppose we'd have 7 nodes and then the distiguishing\n> node for those 2.)\n\nI think it actually can represent the interior sequence as a single\nnode. That's what the \"critical\" part of critbit is for; the critical\nbit is the one where we diverge. But I'm not 100% sure that it's\nimplemented that way.\n\nIn practice, though, sha1 would give us a pretty full tree near the\nfront, so I'd expect each bit to be \"critical\".\n\n> > It's possible that (2) would be better if instead of a\n> > critbit tree, we used a \"critbyte\" tree. That would involve\n> > fewer node traversals, at the cost of making each node\n> > larger (right now the internal nodes store 2 pointer slots;\n> > they'd have to store 256 to handle a full byte). I didn't\n> > try it, but I suspect it would still be slower for the same\n> > reasons.\n> \n> I would expect to go for a crit-\"variable-length\" tree instead.\n> \n> The reason for this is that a higher fan out seems to be more\n> beneficial in the earlier stages, e.g. we could use critbyte trees\n> for the first 1-3 layers in the tree as that will have good memory\n> efficiency (all 256 slots filled), but will be faster than the critbit trees\n> (one lookup instead of 8 conditional jumps).\n\nYeah, I suspect a hybrid approach may be a better tradeoff. I encourage\nyou to try and measure. :)\n\n> I guess when trying to improve the hashsets, someone tried trees\n> as a collision resolver?\n\nI don't think so. hashmap.c uses a linked list, but obj_hash just does\nlinear probing. Both are linear, but the latter is more memory efficient\nand especially has a more compact cache footprint when resolving\ncollisions. The downside of open probing like that is that it's very\nhard to delete an entry, but we don't care about that for obj_hash.\n\nI don't think that improving collision resolution would help that much\nfor obj_hash, though. The fact that quadratic probing and cuckoo hashing\ndidn't yield big benefits implies that we don't spend most of our time\non collisions in the first place (OTOH, my 9a414486d9f0 that you found\ndoes help _only_ when there are collisions, so maybe I'm wrong).\n\n> So maybe we could have some software sided cache for hot entries?\n> (I imagine a data structure consisting of 2 hash sets here, one\n> hashset containing\n> the complete data set, and the other hashset is a very small hashset with e.g.\n> just 256(?) entries that are an LRU cache for the cache entries.\n> Though this sounds like we'd be trying to outsmart the hardware... Not sure\n> I'd expect gains from that)\n\nYeah. Basically what we want is the reverse of a bloom filter: it's OK\nto be wrong, but it most be wrong to say \"it's not here\" when it is, not\nthe other way around. And so that's basically...a cache of a smaller\ndata-structure in front of the larger one.\n\nBut given that the hash table is already O(1)-ish, it's hard to beat\nthat (because remember when you have a cache miss, you then have to do\nan extra lookup in the full table anyway).\n\nI did play around with stuff like that when I was coming up with\n9a414486d9f0, but was never able to make it faster. Patches welcome, of\ncourse.\n\n> I guess we rather want to split up the data sets on the application\n> side: i.e. instead of\n> having so many objects, have hash sets for e.g. blobs, trees, commits separately\n> and then use slightly different strategies there (different load factors?)\n\nMy gut is that would not make a big difference (and sometimes it would\nbe worse, because we don't know what the object type is, or we want to\nmake _sure_ that we don't have the object known as a different type).\n\n> Unrelated note about hashmaps:\n> I wonder if we rather want to give good initial estimates of the size\n> as one improvement\n\nMy recollection is that the growth isn't really relevant. At least for\nobj_hash, we do _way_ more lookups than insertions, so the only thing\nthat really matters is lookup speed.\n\nBut as with everything, if you can come up with improved numbers, I'm\nhappy to look at the patches. :)\n\n-Peff\n"},{"id":"301950","messageId":"CAGZ79kYcB-x40_w1fcWL3NSp8JU9SPrTAEiru-6Jpb7fDM1Y0w@mail.gmail.com","threadId":"44086","inReplyTo":"20160914235843.nacr54ekvl6rjipk@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] use zstd zlib wrapper","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-15T01:22:17Z","receivedAt":"2016-09-15T01:22:23Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Sep 14, 2016 at 4:58 PM, Jeff King <peff@peff.net> wrote:\n> There's a fancy new compression algorithm called \"zstd\". The\n> idea is that it's supposed to get similar compression ratios\n> to zlib, but with much faster compression and decompression\n> times. And on top of that, a nice sliding scale to trade off\n> size versus time on the compression side.\n>\n> The zstd site at https://facebook.github.io/zstd/ claims\n> close to 3x speedup for both compression and decompression\n> versus zlib, with similar compression ratios. There are\n> other fast algorithms (like lz4), but they usually compress\n> much worse (follow the link above for a nice table of\n> results).\n>\n> Since any git operations that have to access objects need to\n> do a zlib inflate, in theory we can speed up everything by\n> using zstd. And then on the packing side, use higher\n> compression levels when making on-disk packfiles (which will\n> be accessed many times) and lower ones when making loose\n> objects, or deflating packed objects on the fly when serving\n> fetches.\n>\n> The catch, of course, is that it's a new incompatible\n> format. This would be a pretty huge change and totally break\n> backwards compatibility for git, not just on disk but\n> on-the-wire as well. So my goal here was not a finished\n> product but just a quick experiment to see if it did indeed\n> bring the promise speedups.\n>\n> Disappointingly, the answer seems to be \"no\".\n\nAfter having looked at the data, I disagree with the conclusion.\nAnd for that I think we need to reason about the frequency\nof the operations happening.\n\n* As an enduser, happily hacking away at one repository,\n  I probably do not care about the pack size on disk as much\n  as I care about timing of the local operations. And I assume\n  that for each repack we have about 1000 reads (log/rev-list)\n  The 1000 is a wild speculation without any data to back it up.\n  So as an end user I'd be happy about [zstd, ~5]\n  For the end user LZ4 seems to be the best solution if it were available.\n\n* As a service provider, I know we have a lot more reads than\n  writes, and repacking is annoying. Also at that scale the disk\n  isn't negligible cheap. So we need to weigh the numbers differently,\n  but how? I suspect depending on the weighting it could still be\n  considered beneficial to go with zstd5. (No hard numbers here)\n"},{"id":"301954","messageId":"20160915062845.sfackmnezb7oy3j5@sigill.intra.peff.net","threadId":"44086","inReplyTo":"CAGZ79kYcB-x40_w1fcWL3NSp8JU9SPrTAEiru-6Jpb7fDM1Y0w@mail.gmail.com","subject":"Re: [PATCH 2/2] use zstd zlib wrapper","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-15T06:28:46Z","receivedAt":"2016-09-15T06:28:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 14, 2016 at 06:22:17PM -0700, Stefan Beller wrote:\n\n> > Disappointingly, the answer seems to be \"no\".\n> \n> After having looked at the data, I disagree with the conclusion.\n> And for that I think we need to reason about the frequency\n> of the operations happening.\n\nI definitely agree that reads outnumber writes, and it's OK to have an\nasymmetric tradeoff between the two. zstd5 isn't _too_ bad in that\nrespect. I guess I was just disappointed that the pack size was still\nbigger, as I was really hoping to see some speed tradeoff without\ngetting a worse pack.\n\nThe other thing to weigh against is \"if we were designing it today\"\nversus \"is it worth the compatibility headaches now\". A 6% improvement\nin \"rev-list --objects\" is not that amazing for a data format change.\nBitmaps were an _easier_ data format change and are more like a 99%\nspeedup.\n\nThey do not apply to every operations, but we may be able to do similar\nspace/time tradeoffs that are easier to handle in terms of backwards\ncompatibility, and which yield bigger results.\n\n-Peff\n"},{"id":"302518","messageId":"alpine.DEB.2.20.1609251614040.129229@virtualbox","threadId":"44086","inReplyTo":"20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net","subject":"Re: Journal of Failed Git Experiments, Volume 1","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-09-25T14:17:28Z","receivedAt":"2016-09-25T14:17:51Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Wed, 14 Sep 2016, Jeff King wrote:\n\n> I try a lot of different experiments with git performance, some of them\n> more hare-brained than others. The ones that succeed end up as real\n> patches. But I hate for the ones that fail to die a quiet death. Then\n> nobody learns what _doesn't_ work, and nobody has the opportunity to\n> point out the spot where I made a stupid mistake that invalidates the\n> whole result.\n\nTo show those experiments, with analysis, is a really good idea.\n\nI found the zstd experiment in particular very educating, as I wondered\nabout the same: could we maybe use it to accelerate Git operations? Now I\nknow.\n\nCiao,\nDscho\n"}]}