{"thread":{"id":"49100","subject":"[PATCH 1/2] fsck: use strbuf_getline() to read skiplist file","startedAt":"2018-08-11T15:44:47Z","lastAt":"2018-10-02T19:19:04Z","messageCount":31,"participants":["René Scharfe","Jeff King","Ævar Arnfjörð Bjarmason","Ramsay Jones","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"355251","messageId":"c1ea6be5-57f7-68f1-0215-b4dceb07603a@web.de","threadId":"49100","inReplyTo":null,"subject":"[PATCH 1/2] fsck: use strbuf_getline() to read skiplist file","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-11T15:39:27Z","receivedAt":"2018-08-11T15:44:47Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The char array named \"buffer\" is unlikely to contain a NUL character, so\nprinting its contents using %s in a die() format is unsafe. Clang's\nASan reports running over the end of buffer in the recently added\nskiplist tests in t5504-fetch-receive-strict.sh as a result.\n\nUse an idiomatic strbuf_getline() loop instead, which ensures the buffer\nis always NUL-terminated. As a side-effect this also adds support for\nskiplist files with CRLF line endings.\n\nSigned-off-by: Rene Scharfe \n---\n fsck.c | 23 ++++++++++-------------\n 1 file changed, 10 insertions(+), 13 deletions(-)\n\ndiff --git a/fsck.c b/fsck.c\nindex a0cee0be59..83f4562390 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -183,8 +183,9 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n static void init_skiplist(struct fsck_options *options, const char *path)\n {\n \tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n-\tint sorted, fd;\n-\tchar buffer[GIT_MAX_HEXSZ + 1];\n+\tint sorted;\n+\tFILE *fp;\n+\tstruct strbuf sb = STRBUF_INIT;\n \tstruct object_id oid;\n \n \tif (options->skiplist)\n@@ -194,25 +195,21 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n \t\toptions->skiplist = &skiplist;\n \t}\n \n-\tfd = open(path, O_RDONLY);\n-\tif (fd < 0)\n+\tfp = fopen(path, \"r\");\n+\tif (!fp)\n \t\tdie(\"Could not open skip list: %s\", path);\n-\tfor (;;) {\n+\twhile (!strbuf_getline(&sb, fp)) {\n \t\tconst char *p;\n-\t\tint result = read_in_full(fd, buffer, sizeof(buffer));\n-\t\tif (result < 0)\n-\t\t\tdie_errno(\"Could not read '%s'\", path);\n-\t\tif (!result)\n-\t\t\tbreak;\n-\t\tif (parse_oid_hex(buffer, &oid, &p) || *p != '\\n')\n-\t\t\tdie(\"Invalid SHA-1: %s\", buffer);\n+\t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n+\t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n \t\toid_array_append(&skiplist, &oid);\n \t\tif (sorted && skiplist.nr > 1 &&\n \t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n \t\t\t\t &oid) > 0)\n \t\t\tsorted = 0;\n \t}\n-\tclose(fd);\n+\tfclose(fp);\n+\tstrbuf_release(&sb);\n \n \tif (sorted)\n \t\tskiplist.sorted = 1;\n-- \n2.18.0\n"},{"id":"355252","messageId":"54a5367f-f832-402c-f51b-3225c92b41ad@web.de","threadId":"49100","inReplyTo":"c1ea6be5-57f7-68f1-0215-b4dceb07603a@web.de","subject":"[PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-11T15:47:56Z","receivedAt":"2018-08-11T15:48:09Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Object IDs to skip are stored in a shared static oid_array. Lookups do\na binary search on the sorted array. The code checks if the object IDs\nare already in the correct order while loading and skips sorting in that\ncase.\n\nSimplify the code by using an oidset instead. Memory usage is a bit\nhigher, but lookups are done in constant time and there is no need to\nworry about any sort order.\n\nEmbed the oidset into struct fsck_options to make its ownership clear\n(no hidden sharing) and avoid unnecessary pointer indirection.\n\nSigned-off-by: Rene Scharfe \n---\n fsck.c | 23 ++---------------------\n fsck.h | 8 +++++---\n 2 files changed, 7 insertions(+), 24 deletions(-)\n\ndiff --git a/fsck.c b/fsck.c\nindex 83f4562390..9246afee22 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -10,7 +10,6 @@\n #include \"fsck.h\"\n #include \"refs.h\"\n #include \"utf8.h\"\n-#include \"sha1-array.h\"\n #include \"decorate.h\"\n #include \"oidset.h\"\n #include \"packfile.h\"\n@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n \n static void init_skiplist(struct fsck_options *options, const char *path)\n {\n-\tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n-\tint sorted;\n \tFILE *fp;\n \tstruct strbuf sb = STRBUF_INIT;\n \tstruct object_id oid;\n \n-\tif (options->skiplist)\n-\t\tsorted = options->skiplist->sorted;\n-\telse {\n-\t\tsorted = 1;\n-\t\toptions->skiplist = &skiplist;\n-\t}\n-\n \tfp = fopen(path, \"r\");\n \tif (!fp)\n \t\tdie(\"Could not open skip list: %s\", path);\n@@ -202,17 +192,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n \t\tconst char *p;\n \t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n \t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n-\t\toid_array_append(&skiplist, &oid);\n-\t\tif (sorted && skiplist.nr > 1 &&\n-\t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n-\t\t\t\t &oid) > 0)\n-\t\t\tsorted = 0;\n+\t\toidset_insert(&options->skiplist, &oid);\n \t}\n \tfclose(fp);\n \tstrbuf_release(&sb);\n-\n-\tif (sorted)\n-\t\tskiplist.sorted = 1;\n }\n \n static int parse_msg_type(const char *str)\n@@ -317,9 +300,7 @@ static void append_msg_id(struct strbuf *sb, const char *msg_id)\n \n static int object_on_skiplist(struct fsck_options *opts, struct object *obj)\n {\n-\tif (opts && opts->skiplist && obj)\n-\t\treturn oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n-\treturn 0;\n+\treturn opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n }\n \n __attribute__((format (printf, 4, 5)))\ndiff --git a/fsck.h b/fsck.h\nindex c3cf5e0034..26120e6186 100644\n--- a/fsck.h\n+++ b/fsck.h\n@@ -1,6 +1,8 @@\n #ifndef GIT_FSCK_H\n #define GIT_FSCK_H\n \n+#include \"oidset.h\"\n+\n #define FSCK_ERROR 1\n #define FSCK_WARN 2\n #define FSCK_IGNORE 3\n@@ -34,12 +36,12 @@ struct fsck_options {\n \tfsck_error error_func;\n \tunsigned strict:1;\n \tint *msg_type;\n-\tstruct oid_array *skiplist;\n+\tstruct oidset skiplist;\n \tstruct decoration *object_names;\n };\n \n-#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }\n-#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }\n+#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT }\n+#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }\n \n /* descend in all linked child objects\n * the return value is:\n-- \n2.18.0\n"},{"id":"355254","messageId":"20180811170248.GC27393@sigill.intra.peff.net","threadId":"49100","inReplyTo":"54a5367f-f832-402c-f51b-3225c92b41ad@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-11T17:02:48Z","receivedAt":"2018-08-11T19:49:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 11, 2018 at 05:47:56PM +0200, René Scharfe wrote:\n\n> Object IDs to skip are stored in a shared static oid_array. Lookups do\n> a binary search on the sorted array. The code checks if the object IDs\n> are already in the correct order while loading and skips sorting in that\n> case.\n> \n> Simplify the code by using an oidset instead. Memory usage is a bit\n> higher, but lookups are done in constant time and there is no need to\n> worry about any sort order.\n> \n> Embed the oidset into struct fsck_options to make its ownership clear\n> (no hidden sharing) and avoid unnecessary pointer indirection.\n\nI actually had a case[1] yesterday where it seems like oidset is a fair\nbit slower than oid_array for a large set.\n\nBut:\n\n - loading the skiplist into memory has pretty lousy performance\n anyway. If we really care about performance of large lists, we\n should define a sorted on-disk format that can be mmap'd and\n searched directly. Or if people are willing to tolerate false\n positives, even a bloom filter.\n\n I've never really used a big skiplist myself, so I haven't done any\n work towards those things.\n\n - we could probably improve the speed of oidset. Two things I notice\n about its implementation:\n\n - it has to malloc for each entry, which I suspect is the main\n\tbottleneck. We could probably pool-allocate blocks, and when\n\tentries get removed just leave the allocations in place until we\n\tclear(). Most callers tend to build up a set and then query it a\n\tlot, or possibly remove items from the set until it's empty. But\n\tmy guess is that few or none want a long-lived set that they add\n\tand remove from randomly.\n\n - insertion lets you do check-and-insert as a single operation\n\t(something I failed to notice in [1]). But it's not implemented\n\tas efficiently as it could be, since the \"contains\" and \"put\"\n\toperations do separate lookups. This doesn't matter for a set\n\tthat's queried a lot more, but for something like de-duping\n\t(like I was doing in [1]) most operations are check-and-insert.\n\nMost of that is just food for thought, but it possibly argues that we\nshould not care about performance characteristics for swapping out\noid_array and oidset here (i.e., that your patch is fine, and the\nsimplicity benefit is the most important thing).\n\n[1] https://public-inbox.org/git/20180810232457.GG19875@sigill.intra.peff.net/\n but note that it's buried pretty deep.\n\n> ---\n> fsck.c | 23 ++---------------------\n> fsck.h | 8 +++++---\n> 2 files changed, 7 insertions(+), 24 deletions(-)\n\nAgain, I didn't see anything wrong with the patch itself.\n\n-Peff\n"},{"id":"355255","messageId":"87lg9csv2u.fsf@evledraar.gmail.com","threadId":"49100","inReplyTo":"54a5367f-f832-402c-f51b-3225c92b41ad@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-08-11T16:54:01Z","receivedAt":"2018-08-11T19:54:20Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, Aug 11 2018, René Scharfe wrote:\n\n> Object IDs to skip are stored in a shared static oid_array. Lookups do\n> a binary search on the sorted array. The code checks if the object IDs\n> are already in the correct order while loading and skips sorting in that\n> case.\n\nI think this change makes sense, but it's missing an update to the\nrelevant documentation in Documentation/config.txt:\n\n fsck.skipList::\n \tThe path to a sorted list of object names (i.e. one SHA-1 per\n \tline) that are known to be broken in a non-fatal way and should\n \tbe ignored. This feature is useful when an established project\n \tshould be accepted despite early commits containing errors that\n \tcan be safely ignored such as invalid committer email addresses.\n \tNote: corrupt objects cannot be skipped with this setting.\n\nAlso, while I use the skipList feature it's for something on the order\nof 10-100 objects, so whatever algorithm the lookup uses isn't going to\nmatter, but I think it's interesting to describe the trade-off in the\ncommit message.\n\nI.e. what if I have 100K objects listed in the skipList, is it only\ngoing to be read lazily during fsck if there's an issue, or on every\nobject etc? What's the difference in performance?\n\nBefore this change, I wanted to follow-up my ab/fsck-transfer-updates\nwith something where we'd die if we found the skipList wasn't ordered as\nwe read it, but from a UI POV this is even better.\n"},{"id":"355256","messageId":"20180811172350.GA2689@sigill.intra.peff.net","threadId":"49100","inReplyTo":"20180811170248.GC27393@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-11T17:23:50Z","receivedAt":"2018-08-11T20:10:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:\n\n> - we could probably improve the speed of oidset. Two things I notice\n> about its implementation:\n> \n> - it has to malloc for each entry, which I suspect is the main\n> \tbottleneck. We could probably pool-allocate blocks, and when\n> \tentries get removed just leave the allocations in place until we\n> \tclear(). Most callers tend to build up a set and then query it a\n> \tlot, or possibly remove items from the set until it's empty. But\n> \tmy guess is that few or none want a long-lived set that they add\n> \tand remove from randomly.\n> \n> - insertion lets you do check-and-insert as a single operation\n> \t(something I failed to notice in [1]). But it's not implemented\n> \tas efficiently as it could be, since the \"contains\" and \"put\"\n> \toperations do separate lookups. This doesn't matter for a set\n> \tthat's queried a lot more, but for something like de-duping\n> \t(like I was doing in [1]) most operations are check-and-insert.\n> [...]\n> [1] https://public-inbox.org/git/20180810232457.GG19875@sigill.intra.peff.net/\n> but note that it's buried pretty deep.\n\nSome notes on this, based on the cat-file patch that I linked to.\n\nBefore any optimizations, my best-of-five timing for:\n\n git cat-file --batch-all-objects --unordered --buffer \\\n --batch-check='%(objectname)' >/dev/null\n\nin git.git was:\n\n real\t0m0.434s\n user\t0m0.414s\n sys\t0m0.020s\n\nThat's enumerating every object in the repo but not doing much more than\nde-duping the names and printing them.\n\nApplying this patch:\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 45992c9be9..04b5cda191 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -443,9 +443,8 @@ static int batch_unordered_object(const struct object_id *oid, void *vdata)\n {\n \tstruct object_cb_data *data = vdata;\n \n-\tif (oidset_contains(data->seen, oid))\n+\tif (oidset_insert(data->seen, oid))\n \t\treturn 0;\n-\toidset_insert(data->seen, oid);\n \n \treturn batch_object_cb(oid, data);\n }\n\nto use the single-call set-and-replace doesn't seem to help (any\nimprovement is within the run-to-run noise). So a single hash lookup per\nobject does not seem to be measurable. And thus teaching oidset_insert()\nto do a single hash lookup for check-and-insert is unlikely to help us.\n\nOn top of that, I tried using a pool to store the set entries:\n\ndiff --git a/oidset.c b/oidset.c\nindex 454c54f933..504929f177 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -17,7 +17,10 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)\n \telse if (oidset_contains(set, oid))\n \t\treturn 1;\n \n-\tentry = xmalloc(sizeof(*entry));\n+\tif (!set->pool)\n+\t\tmem_pool_init(&set->pool, 0);\n+\n+\tentry = mem_pool_alloc(set->pool, sizeof(*entry));\n \toidcpy(&entry->oid, oid);\n \n \toidmap_put(&set->map, entry);\n@@ -29,12 +32,13 @@ int oidset_remove(struct oidset *set, const struct object_id *oid)\n \tstruct oidmap_entry *entry;\n \n \tentry = oidmap_remove(&set->map, oid);\n-\tfree(entry);\n+\t/* abandon pool memory for \"entry\" */\n \n \treturn (entry != NULL);\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\toidmap_free(&set->map, 1);\n+\toidmap_free(&set->map, 0);\n+\tmem_pool_discard(set->pool, 0);\n }\ndiff --git a/oidset.h b/oidset.h\nindex 40ec5f87fe..6b8b802987 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -20,6 +20,7 @@\n */\n struct oidset {\n \tstruct oidmap map;\n+\tstruct mem_pool *pool;\n };\n \n #define OIDSET_INIT { OIDMAP_INIT }\n\nThat drops my best-of-five to:\n\n real\t0m0.300s\n user\t0m0.288s\n sys\t0m0.012s\n\nwhich is over a 25% speedup. So that does seem worth pursuing.\n\nFor reference, the oid_array code path for cat-file is still:\n\n real\t0m0.161s\n user\t0m0.157s\n sys\t0m0.004s\n\nbut that's not completely apples to apples. The oidset code is also\niterating the packfiles in a different order and generating a revidx\n(which I know is about 25ms in this repo). So a better test would\nactually swap one data structure out for the other with no other changes\n(I just happened to have this test handy, and really wanted to know\nwhether the mem_pool stuff would help).\n\n-Peff\n"},{"id":"355259","messageId":"bc9f21c6-b362-2e3f-1820-7da93a76a7c8@ramsayjones.plus.com","threadId":"49100","inReplyTo":"54a5367f-f832-402c-f51b-3225c92b41ad@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-08-11T20:48:18Z","receivedAt":"2018-08-11T20:48:24Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 11/08/18 16:47, René Scharfe wrote:\n> Object IDs to skip are stored in a shared static oid_array.  Lookups do\n> a binary search on the sorted array.  The code checks if the object IDs\n> are already in the correct order while loading and skips sorting in that\n> case.\n> \n> Simplify the code by using an oidset instead.  Memory usage is a bit\n> higher, but lookups are done in constant time and there is no need to\n> worry about any sort order.\n> \n> Embed the oidset into struct fsck_options to make its ownership clear\n> (no hidden sharing) and avoid unnecessary pointer indirection.\n> \n> Signed-off-by: Rene Scharfe \n> ---\n>  fsck.c | 23 ++---------------------\n>  fsck.h |  8 +++++---\n>  2 files changed, 7 insertions(+), 24 deletions(-)\n> \n> diff --git a/fsck.c b/fsck.c\n> index 83f4562390..9246afee22 100644\n> --- a/fsck.c\n> +++ b/fsck.c\n> @@ -10,7 +10,6 @@\n>  #include \"fsck.h\"\n>  #include \"refs.h\"\n>  #include \"utf8.h\"\n> -#include \"sha1-array.h\"\n>  #include \"decorate.h\"\n>  #include \"oidset.h\"\n>  #include \"packfile.h\"\n> @@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n>  \n>  static void init_skiplist(struct fsck_options *options, const char *path)\n>  {\n> -    static struct oid_array skiplist = OID_ARRAY_INIT;\n> -    int sorted;\n>      FILE *fp;\n>      struct strbuf sb = STRBUF_INIT;\n>      struct object_id oid;\n>  \n> -    if (options->skiplist)\n> -        sorted = options->skiplist->sorted;\n> -    else {\n> -        sorted = 1;\n> -        options->skiplist = &skiplist;\n> -    }\n> -\n>      fp = fopen(path, \"r\");\n>      if (!fp)\n>          die(\"Could not open skip list: %s\", path);\n> @@ -202,17 +192,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n>          const char *p;\n>          if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n>              die(\"Invalid SHA-1: %s\", sb.buf);\n> -        oid_array_append(&skiplist, &oid);\n> -        if (sorted && skiplist.nr > 1 &&\n> -                oidcmp(&skiplist.oid[skiplist.nr - 2],\n> -                       &oid) > 0)\n> -            sorted = 0;\n> +        oidset_insert(&options->skiplist, &oid);\n>      }\n>      fclose(fp);\n>      strbuf_release(&sb);\n> -\n> -    if (sorted)\n> -        skiplist.sorted = 1;\n>  }\n>  \n>  static int parse_msg_type(const char *str)\n> @@ -317,9 +300,7 @@ static void append_msg_id(struct strbuf *sb, const char *msg_id)\n>  \n>  static int object_on_skiplist(struct fsck_options *opts, struct object *obj)\n>  {\n> -    if (opts && opts->skiplist && obj)\n> -        return oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n> -    return 0;\n> +    return opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n>  }\n>  \n>  __attribute__((format (printf, 4, 5)))\n> diff --git a/fsck.h b/fsck.h\n> index c3cf5e0034..26120e6186 100644\n> --- a/fsck.h\n> +++ b/fsck.h\n> @@ -1,6 +1,8 @@\n>  #ifndef GIT_FSCK_H\n>  #define GIT_FSCK_H\n>  \n> +#include \"oidset.h\"\n> +\n>  #define FSCK_ERROR 1\n>  #define FSCK_WARN 2\n>  #define FSCK_IGNORE 3\n> @@ -34,12 +36,12 @@ struct fsck_options {\n>      fsck_error error_func;\n>      unsigned strict:1;\n>      int *msg_type;\n> -    struct oid_array *skiplist;\n> +    struct oidset skiplist;\n>      struct decoration *object_names;\n>  };\n>  \n> -#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }\n> -#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }\n> +#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT }\n> +#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }\n\nNote that a NULL initialiser, for the object_names field, is missing\n(not introduced by this patch). Since you have bumped into the 80th\ncolumn, you may not want to add that NULL to the end of these macros\n(it is not _necessary_ after all). However, ... :-D\n\nOtherwise, LGTM.\n\nThanks!\n\nATB,\nRamsay Jones\n\n>  \n>  /* descend in all linked child objects\n>   * the return value is:\n"},{"id":"355260","messageId":"20180811164856.GB27393@sigill.intra.peff.net","threadId":"49100","inReplyTo":"c1ea6be5-57f7-68f1-0215-b4dceb07603a@web.de","subject":"Re: [PATCH 1/2] fsck: use strbuf_getline() to read skiplist file","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-11T16:48:57Z","receivedAt":"2018-08-11T20:49:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 11, 2018 at 05:39:27PM +0200, René Scharfe wrote:\n\n> The char array named \"buffer\" is unlikely to contain a NUL character, so\n> printing its contents using %s in a die() format is unsafe. Clang's\n> ASan reports running over the end of buffer in the recently added\n> skiplist tests in t5504-fetch-receive-strict.sh as a result.\n> \n> Use an idiomatic strbuf_getline() loop instead, which ensures the buffer\n> is always NUL-terminated. As a side-effect this also adds support for\n> skiplist files with CRLF line endings.\n\nNice. Two other side effects, both of which I think are good:\n\n - this is likely faster for a large skiplist due to fewer syscalls\n\n - this will no longer complain about a sha1 with a missing newline at\n the end-of-file (it will quietly handle it as if the newline were\n there)\n\nAnd one I'm not sure about:\n\n - a read() error will now be quietly ignored; I guess we'd have to\n check ferror(fp) to cover this. I'm not sure if it matters.\n\n> fsck.c | 23 ++++++++++-------------\n> 1 file changed, 10 insertions(+), 13 deletions(-)\n\nCode itself looks good to me (assuming we don't care about the read()\nerror thing).\n\n-Peff\n"},{"id":"355268","messageId":"f69e08d7-b29d-a9b7-b6d4-5294c4379133@web.de","threadId":"49100","inReplyTo":"20180811172350.GA2689@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-11T20:59:57Z","receivedAt":"2018-08-11T21:00:18Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 19:23 schrieb Jeff King:\n> On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:\n> \n>> - we could probably improve the speed of oidset. Two things I notice\n>> about its implementation:\n\n> Before any optimizations, my best-of-five timing for:\n> \n> git cat-file --batch-all-objects --unordered --buffer \\\n> --batch-check='%(objectname)' >/dev/null\n> \n> in git.git was:\n> \n> real\t0m0.434s\n> user\t0m0.414s\n> sys\t0m0.020s\n> \n> That's enumerating every object in the repo but not doing much more than\n> de-duping the names and printing them.\n\n> So a single hash lookup per\n> object does not seem to be measurable. And thus teaching oidset_insert()\n> to do a single hash lookup for check-and-insert is unlikely to help us.\n\n> On top of that, I tried using a pool to store the set entries:\n\n> That drops my best-of-five to:\n> \n> real\t0m0.300s\n> user\t0m0.288s\n> sys\t0m0.012s\n> \n> which is over a 25% speedup. So that does seem worth pursuing.\n\n> For reference, the oid_array code path for cat-file is still:\n> \n> real\t0m0.161s\n> user\t0m0.157s\n> sys\t0m0.004s\n> \n> but that's not completely apples to apples. The oidset code is also\n> iterating the packfiles in a different order and generating a revidx\n> (which I know is about 25ms in this repo). So a better test would\n> actually swap one data structure out for the other with no other changes\n> (I just happened to have this test handy, and really wanted to know\n> whether the mem_pool stuff would help).\n\nIf the current oidset implementation is so bad, why not replace it with\none based on oid_array? ;-)\n\nIntuitively I'd try a hashmap with no payload and open addressing via\nsha1hash(), which should reduce memory allocations quite a bit -- no\nneed to store hash codes and next pointers, only an array of object IDs\nwith a fill rate of 50% or so. Deletions are a bit awkward with that\nscheme, though; they could perhaps be implemented as insertions into a\nsecond hashmap.\n\nBalancing might become a problem. Your cat-file example should be fine,\nbut someone could decide to add only hashes with a certain prefix to\ntheir skiplist, and lookups would lopsided.\n\nBut first we'd need something like test-sha1-array for oidset and\nsome kind of performance tests based on these helpers, right?\n\nRené\n"},{"id":"355269","messageId":"e3c1290a-27d9-0aba-76f7-0d4b8c11c045@web.de","threadId":"49100","inReplyTo":"20180811164856.GB27393@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] fsck: use strbuf_getline() to read skiplist file","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-11T21:00:21Z","receivedAt":"2018-08-11T21:00:34Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 18:48 schrieb Jeff King:\n> And one I'm not sure about:\n> \n> - a read() error will now be quietly ignored; I guess we'd have to\n> check ferror(fp) to cover this. I'm not sure if it matters.\n\nI'm not sure, either. It would catch media errors or file system\ncorruption, right? Sounds useful, actually. We should check the other\ncallers of strbuf_getline and friends as well, though, as reporting such\nerrors seems to be omitted in most cases:\n\n\t$ git grep strbuf_getline | wc -l\n\t99\n\t$ git grep ferror | wc -l\n\t35\n\nRené\n"},{"id":"355403","messageId":"6065f3e5-f831-802f-9adc-099de99405fc@web.de","threadId":"49100","inReplyTo":"f69e08d7-b29d-a9b7-b6d4-5294c4379133@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-13T17:15:23Z","receivedAt":"2018-08-13T17:15:35Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 22:59 schrieb René Scharfe:\n> If the current oidset implementation is so bad, why not replace it with\n> one based on oid_array? ;-)\n> \n> Intuitively I'd try a hashmap with no payload and open addressing via\n> sha1hash(), which should reduce memory allocations quite a bit -- no\n> need to store hash codes and next pointers, only an array of object IDs\n> with a fill rate of 50% or so.  Deletions are a bit awkward with that\n> scheme, though; they could perhaps be implemented as insertions into a\n> second hashmap.\n\nHere's roughly what I had in mind, only with a free/occupied bitmap (or\na one-bit payload, if you will). I tried a variant that encoded empty\nslots as null_oid first, which has lower memory usage, but isn't any\nfaster than the current code.\n\n# in git.git\n$ hyperfine \"./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\"\n\nBefore:\nBenchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n\n Time (mean ± σ): 269.5 ms ± 26.7 ms [User: 247.7 ms, System: 21.4 ms]\n\n Range (min … max): 240.3 ms … 339.3 ms\n\nAfter:\nBenchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n\n Time (mean ± σ): 224.2 ms ± 18.2 ms [User: 201.7 ms, System: 22.1 ms]\n\n Range (min … max): 205.0 ms … 259.0 ms\n\nSo that's only slightly faster. :-|\n\n---\n builtin/cat-file.c | 93 +++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 88 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 45992c9be9..b197cca861 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -408,10 +408,93 @@ static void batch_one_object(const char *obj_name, struct batch_options *opt,\n \tbatch_object_write(obj_name, opt, data);\n }\n \n+struct oidset2 {\n+\tsize_t nr, alloc;\n+\tstruct object_id *entries;\n+\tuint32_t *bitmap;\n+};\n+\n+static int is_bit_set(const uint32_t *bitmap, size_t idx)\n+{\n+\tuint32_t mask = 1 << (idx % bitsizeof(bitmap[0]));\n+\treturn bitmap[idx / bitsizeof(bitmap[0])] & mask;\n+}\n+\n+static void set_bit(uint32_t *bitmap, size_t idx)\n+{\n+\tuint32_t mask = 1 << (idx % bitsizeof(bitmap[0]));\n+\tbitmap[idx / bitsizeof(bitmap[0])] |= mask;\n+}\n+\n+static void oidset2_add(struct oidset2 *set, const struct object_id *oid)\n+{\n+\tsize_t idx;\n+\n+\tfor (idx = sha1hash(oid->hash) % set->alloc;;) {\n+\t\tif (!is_bit_set(set->bitmap, idx))\n+\t\t\tbreak;\n+\t\tif (!oidcmp(&set->entries[idx], oid))\n+\t\t\treturn;\n+\t\tif (++idx >= set->alloc)\n+\t\t\tidx = 0;\n+\t}\n+\toidcpy(&set->entries[idx], oid);\n+\tset_bit(set->bitmap, idx);\n+\tset->nr++;\n+}\n+\n+static void oidset2_grow(struct oidset2 *set)\n+{\n+\tstruct oidset2 old_set = *set;\n+\tsize_t idx;\n+\n+\tset->alloc = (old_set.alloc + 1000) * 3 / 2;\n+\tset->nr = 0;\n+\tset->entries = xcalloc(set->alloc, sizeof(set->entries[0]));\n+\tset->bitmap = xcalloc(set->alloc / 32 + 1, sizeof(set->bitmap[0]));\n+\tfor (idx = 0; idx < old_set.alloc; idx++) {\n+\t\tif (!is_bit_set(old_set.bitmap, idx))\n+\t\t\tcontinue;\n+\t\toidset2_add(set, &old_set.entries[idx]);\n+\t}\n+\tfree(old_set.entries);\n+\tfree(old_set.bitmap);\n+}\n+\n+static void oidset2_insert(struct oidset2 *set, const struct object_id *oid)\n+{\n+\tif (set->nr + 1 > set->alloc * 2 / 3)\n+\t\toidset2_grow(set);\n+\toidset2_add(set, oid);\n+}\n+\n+static int oidset2_contains(struct oidset2 *set, const struct object_id *oid)\n+{\n+\tsize_t idx;\n+\n+\tif (!set->nr)\n+\t\treturn 0;\n+\tfor (idx = sha1hash(oid->hash) % set->alloc;;) {\n+\t\tif (!is_bit_set(set->bitmap, idx))\n+\t\t\treturn 0;\n+\t\tif (!oidcmp(&set->entries[idx], oid))\n+\t\t\treturn 1;\n+\t\tif (++idx >= set->alloc)\n+\t\t\tidx = 0;\n+\t}\n+}\n+\n+static void oidset2_clear(struct oidset2 *set)\n+{\n+\tFREE_AND_NULL(set->entries);\n+\tFREE_AND_NULL(set->bitmap);\n+\tset->alloc = set->nr = 0;\n+}\n+\n struct object_cb_data {\n \tstruct batch_options *opt;\n \tstruct expand_data *expand;\n-\tstruct oidset *seen;\n+\tstruct oidset2 *seen;\n };\n \n static int batch_object_cb(const struct object_id *oid, void *vdata)\n@@ -443,9 +526,9 @@ static int batch_unordered_object(const struct object_id *oid, void *vdata)\n {\n \tstruct object_cb_data *data = vdata;\n \n-\tif (oidset_contains(data->seen, oid))\n+\tif (oidset2_contains(data->seen, oid))\n \t\treturn 0;\n-\toidset_insert(data->seen, oid);\n+\toidset2_insert(data->seen, oid);\n \n \treturn batch_object_cb(oid, data);\n }\n@@ -510,7 +593,7 @@ static int batch_objects(struct batch_options *opt)\n \t\tcb.expand = &data;\n \n \t\tif (opt->unordered) {\n-\t\t\tstruct oidset seen = OIDSET_INIT;\n+\t\t\tstruct oidset2 seen = { 0 };\n \n \t\t\tcb.seen = &seen;\n \n@@ -518,7 +601,7 @@ static int batch_objects(struct batch_options *opt)\n \t\t\tfor_each_packed_object(batch_unordered_packed, &cb,\n \t\t\t\t\t FOR_EACH_OBJECT_PACK_ORDER);\n \n-\t\t\toidset_clear(&seen);\n+\t\t\toidset2_clear(&seen);\n \t\t} else {\n \t\t\tstruct oid_array sa = OID_ARRAY_INIT;\n \n-- \n2.18.0\n"},{"id":"355404","messageId":"8c5b2783-a08b-4ea4-3d69-8ae80582b5e3@web.de","threadId":"49100","inReplyTo":"20180811172350.GA2689@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-13T17:15:19Z","receivedAt":"2018-08-13T17:15:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 19:23 schrieb Jeff King:\n> On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:\n> \n>> - we could probably improve the speed of oidset. Two things I notice\n>> about its implementation:\n>>\n>> - it has to malloc for each entry, which I suspect is the main\n>> \tbottleneck. We could probably pool-allocate blocks, and when\n>> \tentries get removed just leave the allocations in place until we\n>> \tclear(). Most callers tend to build up a set and then query it a\n>> \tlot, or possibly remove items from the set until it's empty. But\n>> \tmy guess is that few or none want a long-lived set that they add\n>> \tand remove from randomly.\n>>\n>> - insertion lets you do check-and-insert as a single operation\n>> \t(something I failed to notice in [1]). But it's not implemented\n>> \tas efficiently as it could be, since the \"contains\" and \"put\"\n>> \toperations do separate lookups. This doesn't matter for a set\n>> \tthat's queried a lot more, but for something like de-duping\n>> \t(like I was doing in [1]) most operations are check-and-insert.\n>> [...]\n>> [1] https://public-inbox.org/git/20180810232457.GG19875@sigill.intra.peff.net/\n>> but note that it's buried pretty deep.\n> \n> Some notes on this, based on the cat-file patch that I linked to.\n> \n> Before any optimizations, my best-of-five timing for:\n> \n> git cat-file --batch-all-objects --unordered --buffer \\\n> --batch-check='%(objectname)' >/dev/null\n> \n> in git.git was:\n> \n> real\t0m0.434s\n> user\t0m0.414s\n> sys\t0m0.020s\n> \n> That's enumerating every object in the repo but not doing much more than\n> de-duping the names and printing them.\n> \n> Applying this patch:\n> \n> diff --git a/builtin/cat-file.c b/builtin/cat-file.c\n> index 45992c9be9..04b5cda191 100644\n> --- a/builtin/cat-file.c\n> +++ b/builtin/cat-file.c\n> @@ -443,9 +443,8 @@ static int batch_unordered_object(const struct object_id *oid, void *vdata)\n> {\n> \tstruct object_cb_data *data = vdata;\n> \n> -\tif (oidset_contains(data->seen, oid))\n> +\tif (oidset_insert(data->seen, oid))\n> \t\treturn 0;\n> -\toidset_insert(data->seen, oid);\n> \n> \treturn batch_object_cb(oid, data);\n> }\n> \n> to use the single-call set-and-replace doesn't seem to help (any\n> improvement is within the run-to-run noise). So a single hash lookup per\n> object does not seem to be measurable. And thus teaching oidset_insert()\n> to do a single hash lookup for check-and-insert is unlikely to help us.\n> \n> On top of that, I tried using a pool to store the set entries:\n> \n> diff --git a/oidset.c b/oidset.c\n> index 454c54f933..504929f177 100644\n> --- a/oidset.c\n> +++ b/oidset.c\n> @@ -17,7 +17,10 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)\n> \telse if (oidset_contains(set, oid))\n> \t\treturn 1;\n> \n> -\tentry = xmalloc(sizeof(*entry));\n> +\tif (!set->pool)\n> +\t\tmem_pool_init(&set->pool, 0);\n> +\n> +\tentry = mem_pool_alloc(set->pool, sizeof(*entry));\n> \toidcpy(&entry->oid, oid);\n> \n> \toidmap_put(&set->map, entry);\n> @@ -29,12 +32,13 @@ int oidset_remove(struct oidset *set, const struct object_id *oid)\n> \tstruct oidmap_entry *entry;\n> \n> \tentry = oidmap_remove(&set->map, oid);\n> -\tfree(entry);\n> +\t/* abandon pool memory for \"entry\" */\n> \n> \treturn (entry != NULL);\n> }\n> \n> void oidset_clear(struct oidset *set)\n> {\n> -\toidmap_free(&set->map, 1);\n> +\toidmap_free(&set->map, 0);\n> +\tmem_pool_discard(set->pool, 0);\n> }\n> diff --git a/oidset.h b/oidset.h\n> index 40ec5f87fe..6b8b802987 100644\n> --- a/oidset.h\n> +++ b/oidset.h\n> @@ -20,6 +20,7 @@\n> */\n> struct oidset {\n> \tstruct oidmap map;\n> +\tstruct mem_pool *pool;\n> };\n> \n> #define OIDSET_INIT { OIDMAP_INIT }\n> \n> That drops my best-of-five to:\n> \n> real\t0m0.300s\n> user\t0m0.288s\n> sys\t0m0.012s\n> \n> which is over a 25% speedup. So that does seem worth pursuing.\n> \n> For reference, the oid_array code path for cat-file is still:\n> \n> real\t0m0.161s\n> user\t0m0.157s\n> sys\t0m0.004s\n> \n> but that's not completely apples to apples. The oidset code is also\n> iterating the packfiles in a different order and generating a revidx\n> (which I know is about 25ms in this repo). So a better test would\n> actually swap one data structure out for the other with no other changes\n> (I just happened to have this test handy, and really wanted to know\n> whether the mem_pool stuff would help).\n\nGetting sidetracked here, but the following patch helps both sides a bit:\n\n-- >8 --\nSubject: [PATCH] cat-file: reuse strbuf in batch_object_write()\n\nAvoid allocating and then releasing memory for constructing the output\nfor each object by reusing the strbuf for all of them.\n\nSigned-off-by: Rene Scharfe \n---\n# on git.git\n$ hyperfine \"./git-cat-file --batch-all-objects --buffer --batch-check='%(objectname)'\"\n\nBefore:\nBenchmark #1: ./git-cat-file --batch-all-objects --buffer --batch-check='%(objectname)'\n\n Time (mean ± σ): 139.3 ms ± 20.1 ms [User: 124.2 ms, System: 14.8 ms]\n\n Range (min … max): 124.4 ms … 205.9 ms\n\nAfter:\nBenchmark #1: ./git-cat-file --batch-all-objects --buffer --batch-check='%(objectname)'\n\n Time (mean ± σ): 115.1 ms ± 20.6 ms [User: 102.0 ms, System: 12.8 ms]\n\n Range (min … max): 99.6 ms … 198.1 ms\n\nTest done one a small VM -- the measurements are quite noisy.\n\n builtin/cat-file.c | 17 +++++++++++------\n 1 file changed, 11 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 4a44b2404f..a979fc1f3a 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -211,6 +211,12 @@ struct expand_data {\n \t * optimized out.\n \t */\n \tunsigned skip_object_info : 1;\n+\n+\t/*\n+\t * Scratch space for expanded string; shared between invocations\n+\t * to reduce the number of memory allocations.\n+\t */\n+\tstruct strbuf *scratch;\n };\n \n static int is_atom(const char *atom, const char *s, int slen)\n@@ -340,8 +346,6 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d\n static void batch_object_write(const char *obj_name, struct batch_options *opt,\n \t\t\t struct expand_data *data)\n {\n-\tstruct strbuf buf = STRBUF_INIT;\n-\n \tif (!data->skip_object_info &&\n \t oid_object_info_extended(the_repository, &data->oid, &data->info,\n \t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0) {\n@@ -351,10 +355,10 @@ static void batch_object_write(const char *obj_name, struct batch_options *opt,\n \t\treturn;\n \t}\n \n-\tstrbuf_expand(&buf, opt->format, expand_format, data);\n-\tstrbuf_addch(&buf, '\\n');\n-\tbatch_write(opt, buf.buf, buf.len);\n-\tstrbuf_release(&buf);\n+\tstrbuf_reset(data->scratch);\n+\tstrbuf_expand(data->scratch, opt->format, expand_format, data);\n+\tstrbuf_addch(data->scratch, '\\n');\n+\tbatch_write(opt, data->scratch->buf, data->scratch->len);\n \n \tif (opt->print_contents) {\n \t\tprint_object_or_die(opt, data);\n@@ -453,6 +457,7 @@ static int batch_objects(struct batch_options *opt)\n \t * object.\n \t */\n \tmemset(&data, 0, sizeof(data));\n+\tdata.scratch = &buf;\n \tdata.mark_query = 1;\n \tstrbuf_expand(&buf, opt->format, expand_format, &data);\n \tdata.mark_query = 0;\n-- \n2.18.0\n"},{"id":"355441","messageId":"xmqqmutq5cpo.fsf@gitster-ct.c.googlers.com","threadId":"49100","inReplyTo":"54a5367f-f832-402c-f51b-3225c92b41ad@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-13T18:43:47Z","receivedAt":"2018-08-13T18:43:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> @@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n> static void init_skiplist(struct fsck_options *options, const char\n> *path)\n> {\n> -\tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n> -\tint sorted;\n> \tFILE *fp;\n> \tstruct strbuf sb = STRBUF_INIT;\n> \tstruct object_id oid;\n> -\tif (options->skiplist)\n> -\t\tsorted = options->skiplist->sorted;\n> -\telse {\n\nThat SP before '-' on the removed line is the most curious aspect of\nthis patch; I do not recall the last time I saw a corrupt patch from\nyou---changed where you read/write your mails recently?\n\n> @@ -317,9 +300,7 @@ static void append_msg_id(struct strbuf *sb, const char *msg_id)\n> static int object_on_skiplist(struct fsck_options *opts, struct\n> object *obj)\n> {\n> -\tif (opts && opts->skiplist && obj)\n> -\t\treturn oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n> -\treturn 0;\n> +\treturn opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n\nOK ;-)\n\n"},{"id":"355471","messageId":"49564417-fac3-ede2-7fd1-e3a5a03e4cfe@web.de","threadId":"49100","inReplyTo":"xmqqmutq5cpo.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-13T20:26:22Z","receivedAt":"2018-08-13T20:26:32Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 13.08.2018 um 20:43 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> @@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n>> static void init_skiplist(struct fsck_options *options, const char\n>> *path)\n>> {\n>> -\tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n>> -\tint sorted;\n>> \tFILE *fp;\n>> \tstruct strbuf sb = STRBUF_INIT;\n>> \tstruct object_id oid;\n>> -\tif (options->skiplist)\n>> -\t\tsorted = options->skiplist->sorted;\n>> -\telse {\n> \n> That SP before '-' on the removed line is the most curious aspect of\n> this patch; I do not recall the last time I saw a corrupt patch from\n> you---changed where you read/write your mails recently?\n\nWell, I updated Thunderbird to version 60 a few days ago, but I can't\nsee that extra space in my Sent folder, nor via the NNTP interface of\nthe mailing list [1], nor on the web interface [2]. The latter shows\nextra spaces on the context lines of the first hunk, though, which I\ncan't see anywhere else. All the lines look fine in the citation of\nRamsay's reply [3]. So I don't know where these extra spaces are\ncoming from. :-/\n\nRené\n\n\n[1] news://news.public-inbox.org:119/54a5367f-f832-402c-f51b-3225c92b41ad@web.de\n[2] https://public-inbox.org/git/54a5367f-f832-402c-f51b-3225c92b41ad@web.de/\n[3] https://public-inbox.org/git/bc9f21c6-b362-2e3f-1820-7da93a76a7c8@ramsayjones.plus.com/\n\n"},{"id":"355481","messageId":"xmqqd0um3rhx.fsf@gitster-ct.c.googlers.com","threadId":"49100","inReplyTo":"49564417-fac3-ede2-7fd1-e3a5a03e4cfe@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-13T21:07:22Z","receivedAt":"2018-08-13T21:07:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> the mailing list [1], nor on the web interface [2]. The latter shows\n> extra spaces on the context lines of the first hunk, though, which I\n> can't see anywhere else. All the lines look fine in the citation of\n> Ramsay's reply [3]. So I don't know where these extra spaces are\n> coming from. :-/\n\nHmph, interesting.\n\nhttps://public-inbox.org/git/54a5367f-f832-402c-f51b-3225c92b41ad@web.de/raw\n\nhas \"Content-Type: text/plain; charset=utf-8; format=flowed\". That\npage's rendition is more faithful to the bare text.\n\nThe funky \" -\" one I showed was what Gnus/Emacs came up with as the\nresult of its best effort to make the format=flawed into something\ncloser to \"text\", I think X-<. \n\nIn any case, I do not think format=flowed can be reverted reliably\n(or can it be? If so we should teach mailinfo to repair them).\n"},{"id":"355503","messageId":"fc24f963-1bca-a638-e292-71044057dabb@web.de","threadId":"49100","inReplyTo":"xmqqd0um3rhx.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-13T23:09:17Z","receivedAt":"2018-08-13T23:09:28Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 13.08.2018 um 23:07 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> the mailing list [1], nor on the web interface [2]. The latter shows\n>> extra spaces on the context lines of the first hunk, though, which I\n>> can't see anywhere else. All the lines look fine in the citation of\n>> Ramsay's reply [3]. So I don't know where these extra spaces are\n>> coming from. :-/\n> \n> Hmph, interesting.\n> \n> https://public-inbox.org/git/54a5367f-f832-402c-f51b-3225c92b41ad@web.de/raw\n> \n> has \"Content-Type: text/plain; charset=utf-8; format=flowed\". That\n> page's rendition is more faithful to the bare text.\n\nThat explains it: Thunderbird 60 disables most older Add-ons, among them\nToggle Word Wrap, which used to turn off format=flowed for me. I did\nthat now using the config settings mailnews.send_plaintext_flowed and\nmailnews.display.disable_format_flowed_support.\n\n> The funky \" -\" one I showed was what Gnus/Emacs came up with as the\n> result of its best effort to make the format=flawed into something\n> closer to \"text\", I think X-<. \n\nSorry. :(\n\n> In any case, I do not think format=flowed can be reverted reliably\n> (or can it be? If so we should teach mailinfo to repair them).\n\nRFC3676 gives me a headache, perhaps I should go to bed. If we can\nassume that lines don't have trailing spaces originally then we should\nbe able to reconstruct their contents, no? \"A generating agent SHOULD:\n[...] Trim spaces before user-inserted hard line breaks.\", i.e. lines\nwith trailing spaces are doomed to truncation without hope for repair.\n\nRené\n"},{"id":"355519","messageId":"20180814015842.GA27055@sigill.intra.peff.net","threadId":"49100","inReplyTo":"6065f3e5-f831-802f-9adc-099de99405fc@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T01:58:42Z","receivedAt":"2018-08-14T01:58:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 07:15:23PM +0200, René Scharfe wrote:\n\n> Am 11.08.2018 um 22:59 schrieb René Scharfe:\n> > If the current oidset implementation is so bad, why not replace it with\n> > one based on oid_array? ;-)\n> > \n> > Intuitively I'd try a hashmap with no payload and open addressing via\n> > sha1hash(), which should reduce memory allocations quite a bit -- no\n> > need to store hash codes and next pointers, only an array of object IDs\n> > with a fill rate of 50% or so.  Deletions are a bit awkward with that\n> > scheme, though; they could perhaps be implemented as insertions into a\n> > second hashmap.\n> \n> Here's roughly what I had in mind, only with a free/occupied bitmap (or\n> a one-bit payload, if you will). I tried a variant that encoded empty\n> slots as null_oid first, which has lower memory usage, but isn't any\n> faster than the current code.\n\nHmph, I thought I had sent my version out last night, but it looks like\nI didn't. I got similarly mediocre results.\n\nYour suggestion can be implemented using khash (my patch below).\n\n> Before:\n> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n> \n> Time (mean ± σ): 269.5 ms ± 26.7 ms [User: 247.7 ms, System: 21.4 ms]\n> \n> Range (min … max): 240.3 ms … 339.3 ms\n> \n> After:\n> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n> \n> Time (mean ± σ): 224.2 ms ± 18.2 ms [User: 201.7 ms, System: 22.1 ms]\n> \n> Range (min … max): 205.0 ms … 259.0 ms\n\nYeah. My best-of-five dropped from 300ms to 247ms. That 300 was using\nthe memory pool, though khash's deletion strategy isn't all that\ndifferent (the wasted memory hangs around until the next hash resize,\nbut if you're evenly dropping and adding, you likely won't need to\nresize).\n\nApplying your patch, I get 337ms, worse than the hashmap with a memory\npool. I'm not sure why.\n\n> builtin/cat-file.c | 93 +++++++++++++++++++++++++++++++++++++++++++---\n> 1 file changed, 88 insertions(+), 5 deletions(-)\n\nBy the way, your patch seemed damaged (wouldn't apply, and \"am -3\"\ncomplained of hand-editing). It looks like maybe there's an extra space\ninserted in the context lines?\n\nAnyway, here's the khash patch for reference.\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 5714bcbddd..5a86b10a5e 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -534,7 +534,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \t * add to \"newlist\" between calls, the additions will always be for\n \t * oids that are already in the set.\n \t */\n-\tif (!tip_oids->map.map.tablesize) {\n+\tif (!tip_oids->map) {\n \t\tadd_refs_to_oidset(tip_oids, unmatched);\n \t\tadd_refs_to_oidset(tip_oids, newlist);\n \t}\ndiff --git a/oidset.c b/oidset.c\nindex 454c54f933..2964b43b2d 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -3,38 +3,44 @@\n \n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tif (!set->map.map.tablesize)\n+\tkhiter_t pos;\n+\n+\tif (!set->map)\n \t\treturn 0;\n-\treturn !!oidmap_get(&set->map, oid);\n+\n+\tpos = kh_get_oid(set->map, *oid);\n+\treturn pos < kh_end(set->map);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n+\tint hash_ret;\n \n-\tif (!set->map.map.tablesize)\n-\t\toidmap_init(&set->map, 0);\n-\telse if (oidset_contains(set, oid))\n-\t\treturn 1;\n+\tif (!set->map)\n+\t\tset->map = kh_init_oid();\n \n-\tentry = xmalloc(sizeof(*entry));\n-\toidcpy(&entry->oid, oid);\n-\n-\toidmap_put(&set->map, entry);\n-\treturn 0;\n+\tkh_put_oid(set->map, *oid, &hash_ret);\n+\treturn !hash_ret;\n }\n \n int oidset_remove(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n+\tkhiter_t pos;\n \n-\tentry = oidmap_remove(&set->map, oid);\n-\tfree(entry);\n+\tif (!set->map)\n+\t\treturn 0;\n+\n+\tpos = kh_get_oid(set->map, *oid);\n+\tif (pos < kh_end(set->map)) {\n+\t\tkh_del_oid(set->map, pos);\n+\t\treturn 1;\n+\t}\n \n-\treturn (entry != NULL);\n+\treturn 0;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\toidmap_free(&set->map, 1);\n+\tkh_destroy_oid(set->map);\n+\tset->map = NULL;\n }\ndiff --git a/oidset.h b/oidset.h\nindex 40ec5f87fe..4c4c5a42fe 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -2,6 +2,7 @@\n #define OIDSET_H\n \n #include \"oidmap.h\"\n+#include \"khash.h\"\n \n /**\n * This API is similar to sha1-array, in that it maintains a set of object ids\n@@ -15,19 +16,34 @@\n * table overhead.\n */\n \n+static inline unsigned int oid_hash(const struct object_id oid)\n+{\n+\tunsigned int hash;\n+\tmemcpy(&hash, oid.hash, sizeof(hash));\n+\treturn hash;\n+}\n+\n+static inline int oid_equal(const struct object_id a,\n+\t\t\t const struct object_id b)\n+{\n+\treturn !oidcmp(&a, &b);\n+}\n+\n+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n+\n+\n /**\n * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n */\n struct oidset {\n-\tstruct oidmap map;\n+\tkh_oid_t *map;\n };\n \n-#define OIDSET_INIT { OIDMAP_INIT }\n-\n+#define OIDSET_INIT { NULL }\n \n static inline void oidset_init(struct oidset *set, size_t initial_size)\n {\n-\toidmap_init(&set->map, initial_size);\n+\tset->map = NULL;\n }\n \n /**\n@@ -58,19 +74,25 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);\n void oidset_clear(struct oidset *set);\n \n struct oidset_iter {\n-\tstruct oidmap_iter m_iter;\n+\tkh_oid_t *map;\n+\tkhiter_t iter;\n };\n \n static inline void oidset_iter_init(struct oidset *set,\n \t\t\t\t struct oidset_iter *iter)\n {\n-\toidmap_iter_init(&set->map, &iter->m_iter);\n+\titer->map = set->map;\n+\titer->iter = kh_begin(iter->map);\n }\n \n static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)\n {\n-\tstruct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);\n-\treturn e ? &e->oid : NULL;\n+\tfor (; iter->iter != kh_end(iter->map); iter->iter++) {\n+\t\tif (!kh_exist(iter->map, iter->iter))\n+\t\t\tcontinue;\n+\t\treturn &kh_key(iter->map, iter->iter);\n+\t}\n+\treturn NULL;\n }\n \n static inline struct object_id *oidset_iter_first(struct oidset *set,\n"},{"id":"355520","messageId":"20180814020100.GB27055@sigill.intra.peff.net","threadId":"49100","inReplyTo":"8c5b2783-a08b-4ea4-3d69-8ae80582b5e3@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T02:01:00Z","receivedAt":"2018-08-14T02:01:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 07:15:19PM +0200, René Scharfe wrote:\n\n> Getting sidetracked here, but the following patch helps both sides a bit:\n> \n> -- >8 --\n> Subject: [PATCH] cat-file: reuse strbuf in batch_object_write()\n> \n> Avoid allocating and then releasing memory for constructing the output\n> for each object by reusing the strbuf for all of them.\n\nThanks, this an easy and sensible optimization. I have a few patches to\nsend on top of my cat-file topic, so I'll pick this up there.\n\n-Peff\n"},{"id":"355521","messageId":"20180814020354.GC27055@sigill.intra.peff.net","threadId":"49100","inReplyTo":"20180814015842.GA27055@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T02:03:54Z","receivedAt":"2018-08-14T02:03:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 09:58:42PM -0400, Jeff King wrote:\n\n> > builtin/cat-file.c | 93 +++++++++++++++++++++++++++++++++++++++++++---\n> > 1 file changed, 88 insertions(+), 5 deletions(-)\n> \n> By the way, your patch seemed damaged (wouldn't apply, and \"am -3\"\n> complained of hand-editing). It looks like maybe there's an extra space\n> inserted in the context lines?\n\nOh nevermind, I see you guys dug to the bottom of it elsewhere in the\nthread. :)\n\n-Peff\n"},{"id":"356521","messageId":"a2577ecd-52a4-1343-a0b8-bbf1883db619@web.de","threadId":"49100","inReplyTo":"bc9f21c6-b362-2e3f-1820-7da93a76a7c8@ramsayjones.plus.com","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-25T18:49:19Z","receivedAt":"2018-08-25T18:50:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 22:48 schrieb Ramsay Jones:\n> On 11/08/18 16:47, René Scharfe wrote:\n>> @@ -34,12 +36,12 @@ struct fsck_options {\n>>      fsck_error error_func;\n>>      unsigned strict:1;\n>>      int *msg_type;\n>> -    struct oid_array *skiplist;\n>> +    struct oidset skiplist;\n>>      struct decoration *object_names;\n>>  };\n>>  \n>> -#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }\n>> -#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }\n>> +#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT }\n>> +#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }\n> \n> Note that a NULL initialiser, for the object_names field, is missing\n> (not introduced by this patch). Since you have bumped into the 80th\n> column, you may not want to add that NULL to the end of these macros\n> (it is not _necessary_ after all). However, ... :-D\n\nExactly my thoughts -- except the \"However\" part. :)\n\nI even thought about reordering the struct to move the NULL-initialized\nelements to the end, allowing us to drop them from the initializer, but\nfelt that this would be a bit too much..\n\nRené\n"},{"id":"356524","messageId":"113aa2d7-6f66-8d03-dda4-7337cda9b2df@web.de","threadId":"49100","inReplyTo":"87lg9csv2u.fsf@evledraar.gmail.com","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-25T18:49:41Z","receivedAt":"2018-08-25T18:50:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 11.08.2018 um 18:54 schrieb Ævar Arnfjörð Bjarmason:\n> \n> On Sat, Aug 11 2018, René Scharfe wrote:\n> \n>> Object IDs to skip are stored in a shared static oid_array. Lookups do\n>> a binary search on the sorted array. The code checks if the object IDs\n>> are already in the correct order while loading and skips sorting in that\n>> case.\n> \n> I think this change makes sense, but it's missing an update to the\n> relevant documentation in Documentation/config.txt:\n> \n> fsck.skipList::\n> \tThe path to a sorted list of object names (i.e. one SHA-1 per\n> \tline) that are known to be broken in a non-fatal way and should\n> \tbe ignored. This feature is useful when an established project\n> \tshould be accepted despite early commits containing errors that\n> \tcan be safely ignored such as invalid committer email addresses.\n> \tNote: corrupt objects cannot be skipped with this setting.\n> \n> Also, while I use the skipList feature it's for something on the order\n> of 10-100 objects, so whatever algorithm the lookup uses isn't going to\n> matter, but I think it's interesting to describe the trade-off in the\n> commit message.\n> \n> I.e. what if I have 100K objects listed in the skipList, is it only\n> going to be read lazily during fsck if there's an issue, or on every\n> object etc? What's the difference in performance?\n\nThe list is loaded once up-front and a lookup is done for each\nreportable issue and .gitmodules file. Repositories without them\nwon't be affected at all.\n\n100K bad objects sounds a bit extreme, but a fast-import can create\nsuch a repository relatively quickly. Here are the numbers with and\nwithout the two patches:\n\nTest origin/master HEAD\n----------------------------------------------------------------------------------------\n1450.3: fsck with 0 skipped bad commits 0.84(0.78+0.05) 0.83(0.80+0.03) -1.2%\n1450.5: fsck with 1 skipped bad commits 0.84(0.77+0.07) 0.84(0.79+0.05) +0.0%\n1450.7: fsck with 10 skipped bad commits 0.86(0.81+0.05) 0.84(0.78+0.06) -2.3%\n1450.9: fsck with 100 skipped bad commits 0.85(0.78+0.07) 0.84(0.78+0.05) -1.2%\n1450.11: fsck with 1000 skipped bad commits 0.85(0.80+0.05) 0.84(0.79+0.05) -1.2%\n1450.13: fsck with 10000 skipped bad commits 0.85(0.78+0.07) 0.82(0.75+0.06) -3.5%\n1450.15: fsck with 100000 skipped bad commits 0.73(0.64+0.09) 0.64(0.62+0.02) -12.3%\n\nThey look the same for most sizes, but with all 100000 bad objects in\nthe skiplist the oidset wins decisively. Dialing it up a notch:\n\nTest origin/master HEAD\n-----------------------------------------------------------------------------------------\n1450.3: fsck with 0 skipped bad commits 8.61(7.94+0.66) 8.72(8.14+0.58) +1.3%\n1450.5: fsck with 1 skipped bad commits 8.51(7.87+0.63) 8.53(7.93+0.60) +0.2%\n1450.7: fsck with 10 skipped bad commits 8.56(7.98+0.57) 8.54(7.91+0.63) -0.2%\n1450.9: fsck with 100 skipped bad commits 8.65(8.00+0.65) 8.47(7.93+0.53) -2.1%\n1450.11: fsck with 1000 skipped bad commits 8.69(8.16+0.53) 8.49(8.00+0.49) -2.3%\n1450.13: fsck with 10000 skipped bad commits 8.69(8.13+0.56) 8.50(7.93+0.56) -2.2%\n1450.15: fsck with 100000 skipped bad commits 8.78(8.18+0.60) 8.36(7.85+0.50) -4.8%\n1450.17: fsck with 1000000 skipped bad commits 7.83(7.07+0.76) 6.55(6.42+0.12) -16.3%\n\nSo it looks like successful lookups are faster in the oidset and\nthe oid_array is quicker with just a handful of entries.\n\nA L1 cache line of 64 bytes holds 3 consecutive SHA1 hashes, which\nmight explain it.\n\nHere's the perf test code:\n\n---\n t/perf/p1450-fsck.sh | 40 ++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 40 insertions(+)\n create mode 100755 t/perf/p1450-fsck.sh\n\ndiff --git a/t/perf/p1450-fsck.sh b/t/perf/p1450-fsck.sh\nnew file mode 100755\nindex 0000000000..7c89690777\n--- /dev/null\n+++ b/t/perf/p1450-fsck.sh\n@@ -0,0 +1,40 @@\n+#!/bin/sh\n+\n+test_description='Test fsck skipList performance'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+n=100000\n+\n+test_expect_success \"setup $n bad commits\" '\n+\tfor i in $(test_seq 1 $n)\n+\tdo\n+\t\techo \"commit refs/heads/master\" &&\n+\t\techo \"committer C 1234567890 +0000\" &&\n+\t\techo \"data <skiplist\n+\t'\n+\n+\ttest_perf \"fsck with $skip skipped bad commits\"\t'\n+\t\tgit -c fsck.skipList=skiplist fsck\n+\t'\n+\n+\tcase $skip in\n+\t0) skip=1 ;;\n+\t*) skip=${skip}0 ;;\n+\tesac\n+done\n+\n+test_done\n-- \n2.18.0\n"},{"id":"356522","messageId":"ae61a845-16fa-e2d6-935d-ce5eb1e33e5a@web.de","threadId":"49100","inReplyTo":"c1ea6be5-57f7-68f1-0215-b4dceb07603a@web.de","subject":"[PATCH v2 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-25T18:50:36Z","receivedAt":"2018-08-25T18:50:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Object IDs to skip are stored in a shared static oid_array. Lookups do\na binary search on the sorted array. The code checks if the object IDs\nare already in the correct order while loading and skips sorting in that\ncase. Lookups are done before reporting a (non-fatal) corruption and\nbefore checking .gitmodules files.\n\nSimplify the code by using an oidset instead. Memory usage is a bit\nhigher, but we don't need to worry about any sort order anymore. Embed\nthe oidset into struct fsck_options to make its ownership clear (no\nhidden sharing) and avoid unnecessary pointer indirection.\n\nPerformance on repositories with a low number of reported issues and\n.gitmodules files (i.e. the usual case) won't be affected much. The\noidset should be a bit quicker with higher numbers of bad objects in\nthe skipList.\n\nHelped-by: Ævar Arnfjörð Bjarmason \nSigned-off-by: Rene Scharfe \n---\nAdded small documentation update.\n\n Documentation/config.txt | 2 +-\n fsck.c | 23 ++---------------------\n fsck.h | 8 +++++---\n 3 files changed, 8 insertions(+), 25 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 2fa65b7516..80ab570579 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -1715,7 +1715,7 @@ doing the same for `receive.fsck.` and `fetch.fsck.`\n will only cause git to warn.\n \n fsck.skipList::\n-\tThe path to a sorted list of object names (i.e. one SHA-1 per\n+\tThe path to a list of object names (i.e. one SHA-1 per\n \tline) that are known to be broken in a non-fatal way and should\n \tbe ignored. This feature is useful when an established project\n \tshould be accepted despite early commits containing errors that\ndiff --git a/fsck.c b/fsck.c\nindex 972a26b9ba..4c643f1d40 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -10,7 +10,6 @@\n #include \"fsck.h\"\n #include \"refs.h\"\n #include \"utf8.h\"\n-#include \"sha1-array.h\"\n #include \"decorate.h\"\n #include \"oidset.h\"\n #include \"packfile.h\"\n@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n \n static void init_skiplist(struct fsck_options *options, const char *path)\n {\n-\tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n-\tint sorted;\n \tFILE *fp;\n \tstruct strbuf sb = STRBUF_INIT;\n \tstruct object_id oid;\n \n-\tif (options->skiplist)\n-\t\tsorted = options->skiplist->sorted;\n-\telse {\n-\t\tsorted = 1;\n-\t\toptions->skiplist = &skiplist;\n-\t}\n-\n \tfp = fopen(path, \"r\");\n \tif (!fp)\n \t\tdie(\"Could not open skip list: %s\", path);\n@@ -202,19 +192,12 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n \t\tconst char *p;\n \t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n \t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n-\t\toid_array_append(&skiplist, &oid);\n-\t\tif (sorted && skiplist.nr > 1 &&\n-\t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n-\t\t\t\t &oid) > 0)\n-\t\t\tsorted = 0;\n+\t\toidset_insert(&options->skiplist, &oid);\n \t}\n \tif (ferror(fp))\n \t\tdie_errno(\"Could not read '%s'\", path);\n \tfclose(fp);\n \tstrbuf_release(&sb);\n-\n-\tif (sorted)\n-\t\tskiplist.sorted = 1;\n }\n \n static int parse_msg_type(const char *str)\n@@ -319,9 +302,7 @@ static void append_msg_id(struct strbuf *sb, const char *msg_id)\n \n static int object_on_skiplist(struct fsck_options *opts, struct object *obj)\n {\n-\tif (opts && opts->skiplist && obj)\n-\t\treturn oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n-\treturn 0;\n+\treturn opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n }\n \n __attribute__((format (printf, 4, 5)))\ndiff --git a/fsck.h b/fsck.h\nindex 0c7e8c9428..b95595ae5f 100644\n--- a/fsck.h\n+++ b/fsck.h\n@@ -1,6 +1,8 @@\n #ifndef GIT_FSCK_H\n #define GIT_FSCK_H\n \n+#include \"oidset.h\"\n+\n #define FSCK_ERROR 1\n #define FSCK_WARN 2\n #define FSCK_IGNORE 3\n@@ -35,12 +37,12 @@ struct fsck_options {\n \tfsck_error error_func;\n \tunsigned strict:1;\n \tint *msg_type;\n-\tstruct oid_array *skiplist;\n+\tstruct oidset skiplist;\n \tstruct decoration *object_names;\n };\n \n-#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }\n-#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }\n+#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT }\n+#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }\n \n /* descend in all linked child objects\n * the return value is:\n-- \n2.18.0\n"},{"id":"356523","messageId":"aaf03ba2-1369-2dc3-c3ec-739a1c56606e@web.de","threadId":"49100","inReplyTo":"c1ea6be5-57f7-68f1-0215-b4dceb07603a@web.de","subject":"[PATCH v2 1/2] fsck: use strbuf_getline() to read skiplist file","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-25T18:50:28Z","receivedAt":"2018-08-25T18:50:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"buffer is unlikely to contain a NUL character, so printing its contents\nusing %s in a die() format is unsafe (detected with ASan).\n\nUse an idiomatic strbuf_getline() loop instead, which ensures the buffer\nis always NUL-terminated, supports CRLF files as well, accepts files\nwithout a newline after the last line, supports any hash length\nautomatically, and is shorter.\n\nHelped-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\nAdded error check.\nHopefully fixed my MUA config..\n\n fsck.c | 25 ++++++++++++-------------\n 1 file changed, 12 insertions(+), 13 deletions(-)\n\ndiff --git a/fsck.c b/fsck.c\nindex a0cee0be59..972a26b9ba 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -183,8 +183,9 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,\n static void init_skiplist(struct fsck_options *options, const char *path)\n {\n \tstatic struct oid_array skiplist = OID_ARRAY_INIT;\n-\tint sorted, fd;\n-\tchar buffer[GIT_MAX_HEXSZ + 1];\n+\tint sorted;\n+\tFILE *fp;\n+\tstruct strbuf sb = STRBUF_INIT;\n \tstruct object_id oid;\n \n \tif (options->skiplist)\n@@ -194,25 +195,23 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n \t\toptions->skiplist = &skiplist;\n \t}\n \n-\tfd = open(path, O_RDONLY);\n-\tif (fd < 0)\n+\tfp = fopen(path, \"r\");\n+\tif (!fp)\n \t\tdie(\"Could not open skip list: %s\", path);\n-\tfor (;;) {\n+\twhile (!strbuf_getline(&sb, fp)) {\n \t\tconst char *p;\n-\t\tint result = read_in_full(fd, buffer, sizeof(buffer));\n-\t\tif (result < 0)\n-\t\t\tdie_errno(\"Could not read '%s'\", path);\n-\t\tif (!result)\n-\t\t\tbreak;\n-\t\tif (parse_oid_hex(buffer, &oid, &p) || *p != '\\n')\n-\t\t\tdie(\"Invalid SHA-1: %s\", buffer);\n+\t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n+\t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n \t\toid_array_append(&skiplist, &oid);\n \t\tif (sorted && skiplist.nr > 1 &&\n \t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n \t\t\t\t &oid) > 0)\n \t\t\tsorted = 0;\n \t}\n-\tclose(fd);\n+\tif (ferror(fp))\n+\t\tdie_errno(\"Could not read '%s'\", path);\n+\tfclose(fp);\n+\tstrbuf_release(&sb);\n \n \tif (sorted)\n \t\tskiplist.sorted = 1;\n-- \n2.18.0\n"},{"id":"356559","messageId":"030bac66-eeb4-7bc9-8f27-1e6b4124fd76@web.de","threadId":"49100","inReplyTo":"20180814015842.GA27055@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-26T11:37:41Z","receivedAt":"2018-08-26T11:47:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 14.08.2018 um 03:58 schrieb Jeff King:\n> Your suggestion can be implemented using khash (my patch below).\n> \n>> Before:\n>> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n>>\n>> Time (mean ± σ): 269.5 ms ± 26.7 ms [User: 247.7 ms, System: 21.4 ms]\n>>\n>> Range (min … max): 240.3 ms … 339.3 ms\n>>\n>> After:\n>> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n>>\n>> Time (mean ± σ): 224.2 ms ± 18.2 ms [User: 201.7 ms, System: 22.1 ms]\n>>\n>> Range (min … max): 205.0 ms … 259.0 ms\n> \n> Yeah. My best-of-five dropped from 300ms to 247ms. That 300 was using\n> the memory pool, though khash's deletion strategy isn't all that\n> different (the wasted memory hangs around until the next hash resize,\n> but if you're evenly dropping and adding, you likely won't need to\n> resize).\n\nWith your khash patch:\n\nBenchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n\n Time (mean ± σ): 159.1 ms ± 20.5 ms [User: 140.3 ms, System: 18.5 ms]\n\n Range (min … max): 140.0 ms … 214.0 ms\n\nSo it seems worth it.\n\n> Anyway, here's the khash patch for reference.\n> \n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 5714bcbddd..5a86b10a5e 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -534,7 +534,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n> \t * add to \"newlist\" between calls, the additions will always be for\n> \t * oids that are already in the set.\n> \t */\n> -\tif (!tip_oids->map.map.tablesize) {\n> +\tif (!tip_oids->map) {\n> \t\tadd_refs_to_oidset(tip_oids, unmatched);\n> \t\tadd_refs_to_oidset(tip_oids, newlist);\n> \t}\n\nThe caller shouldn't look at the private parts of the implementation\nlike this. tablesize is the allocation count, which becomes non-zero\nif at least one entry was added. tip_oids is only inserted into, never\ndeleted from, so a count or size function could be used instead as a\ncleaner interface. (In a separate patch..)\n\n> diff --git a/oidset.c b/oidset.c\n> index 454c54f933..2964b43b2d 100644\n> --- a/oidset.c\n> +++ b/oidset.c\n> @@ -3,38 +3,44 @@\n> \n> int oidset_contains(const struct oidset *set, const struct object_id *oid)\n> {\n> -\tif (!set->map.map.tablesize)\n> +\tkhiter_t pos;\n> +\n> +\tif (!set->map)\n> \t\treturn 0;\n> -\treturn !!oidmap_get(&set->map, oid);\n> +\n> +\tpos = kh_get_oid(set->map, *oid);\n> +\treturn pos < kh_end(set->map);\n> }\n> \n> int oidset_insert(struct oidset *set, const struct object_id *oid)\n> {\n> -\tstruct oidmap_entry *entry;\n> +\tint hash_ret;\n> \n> -\tif (!set->map.map.tablesize)\n> -\t\toidmap_init(&set->map, 0);\n> -\telse if (oidset_contains(set, oid))\n> -\t\treturn 1;\n> +\tif (!set->map)\n> +\t\tset->map = kh_init_oid();\n> \n> -\tentry = xmalloc(sizeof(*entry));\n> -\toidcpy(&entry->oid, oid);\n> -\n> -\toidmap_put(&set->map, entry);\n> -\treturn 0;\n> +\tkh_put_oid(set->map, *oid, &hash_ret);\n> +\treturn !hash_ret;\n> }\n\nSo initialization is deferred to the first insert, and the empty set\ncan be represented in two ways -- map == NULL and map->size == 0.\n\nI wondered about the performance impact of all those NULL checks at\ninsert and lookup and converted it to stack storage, with a dirty\nhand-rolled oidset_clear() implementation. It wasn't any faster.\n\n> \n> int oidset_remove(struct oidset *set, const struct object_id *oid)\n> {\n> -\tstruct oidmap_entry *entry;\n> +\tkhiter_t pos;\n> \n> -\tentry = oidmap_remove(&set->map, oid);\n> -\tfree(entry);\n> +\tif (!set->map)\n> +\t\treturn 0;\n> +\n> +\tpos = kh_get_oid(set->map, *oid);\n> +\tif (pos < kh_end(set->map)) {\n> +\t\tkh_del_oid(set->map, pos);\n> +\t\treturn 1;\n> +\t}\n> \n> -\treturn (entry != NULL);\n> +\treturn 0;\n> }\n> \n> void oidset_clear(struct oidset *set)\n> {\n> -\toidmap_free(&set->map, 1);\n> +\tkh_destroy_oid(set->map);\n> +\tset->map = NULL;\n> }\n> diff --git a/oidset.h b/oidset.h\n> index 40ec5f87fe..4c4c5a42fe 100644\n> --- a/oidset.h\n> +++ b/oidset.h\n> @@ -2,6 +2,7 @@\n> #define OIDSET_H\n> \n> #include \"oidmap.h\"\n\nThis can go.\n\n> +#include \"khash.h\"\n> \n> /**\n> * This API is similar to sha1-array, in that it maintains a set of object ids\n> @@ -15,19 +16,34 @@\n> * table overhead.\n> */\n> \n> +static inline unsigned int oid_hash(const struct object_id oid)\n> +{\n> +\tunsigned int hash;\n> +\tmemcpy(&hash, oid.hash, sizeof(hash));\n> +\treturn hash;\n> +}\n> +\n> +static inline int oid_equal(const struct object_id a,\n> +\t\t\t const struct object_id b)\n> +{\n> +\treturn !oidcmp(&a, &b);\n> +}\n\nLook, it's oideq() from that other series in disguise! :)\n\n> +\n> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n\nNote to self: The 0 is for kh_is_map, which means that no values are\nkept and the given value type (int) doesn't matter.\n\n> +\n> +\n> /**\n> * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n> */\n> struct oidset {\n> -\tstruct oidmap map;\n> +\tkh_oid_t *map;\n> };\n> \n> -#define OIDSET_INIT { OIDMAP_INIT }\n> -\n> +#define OIDSET_INIT { NULL }\n> \n> static inline void oidset_init(struct oidset *set, size_t initial_size)\n> {\n> -\toidmap_init(&set->map, initial_size);\n> +\tset->map = NULL;\n> }\n\nThis ignores initial_size, which is misleading. We should probably\ncall kh_resize_oid() here and move the function to oidset.c. Or\nget rid of the second parameter..\n\n> \n> /**\n> @@ -58,19 +74,25 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);\n> void oidset_clear(struct oidset *set);\n> \n> struct oidset_iter {\n> -\tstruct oidmap_iter m_iter;\n> +\tkh_oid_t *map;\n> +\tkhiter_t iter;\n> };\n> \n> static inline void oidset_iter_init(struct oidset *set,\n> \t\t\t\t struct oidset_iter *iter)\n> {\n> -\toidmap_iter_init(&set->map, &iter->m_iter);\n> +\titer->map = set->map;\n> +\titer->iter = kh_begin(iter->map);\n> }\n\nThis is fine even if map == NULL, because kh_begin() can handle any\nparameter value, as it ignores them...\n\n> \n> static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)\n> {\n> -\tstruct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);\n> -\treturn e ? &e->oid : NULL;\n> +\tfor (; iter->iter != kh_end(iter->map); iter->iter++) {\n> +\t\tif (!kh_exist(iter->map, iter->iter))\n> +\t\t\tcontinue;\n> +\t\treturn &kh_key(iter->map, iter->iter);\n> +\t}\n> +\treturn NULL;\n> }\n\n... but kh_end() dereferences map, so iterating a fresh oidset will\nsegfault here.\n\n> \n> static inline struct object_id *oidset_iter_first(struct oidset *set,\n> \n"},{"id":"356569","messageId":"87r2ikdzvc.fsf@evledraar.gmail.com","threadId":"49100","inReplyTo":"ae61a845-16fa-e2d6-935d-ce5eb1e33e5a@web.de","subject":"Re: [PATCH v2 2/2] fsck: use oidset for skiplist","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-08-27T07:37:11Z","receivedAt":"2018-08-27T07:37:17Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, Aug 25 2018, René Scharfe wrote:\n\n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index 2fa65b7516..80ab570579 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -1715,7 +1715,7 @@ doing the same for `receive.fsck.` and `fetch.fsck.`\n> will only cause git to warn.\n>\n> fsck.skipList::\n> -\tThe path to a sorted list of object names (i.e. one SHA-1 per\n> +\tThe path to a list of object names (i.e. one SHA-1 per\n> \tline) that are known to be broken in a non-fatal way and should\n> \tbe ignored. This feature is useful when an established project\n> \tshould be accepted despite early commits containing errors that\n\nI was going to say that since this is a file format we're likely to\nsupport across versions we should make a note that \"up to version\nso-and-so this needed to be sorted, but that's longer the case. So\ne.g. someone wouldn't test this on 2.20 (or read the online docs) and\nthen deploy this for older clients..\n\nBut...\n\n> -\tif (options->skiplist)\n> -\t\tsorted = options->skiplist->sorted;\n> -\telse {\n> -\t\tsorted = 1;\n> -\t\toptions->skiplist = &skiplist;\n> -\t}\n> -\n> \tfp = fopen(path, \"r\");\n> \tif (!fp)\n> \t\tdie(\"Could not open skip list: %s\", path);\n> @@ -202,19 +192,12 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n> \t\tconst char *p;\n> \t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n> \t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n> -\t\toid_array_append(&skiplist, &oid);\n> -\t\tif (sorted && skiplist.nr > 1 &&\n> -\t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n> -\t\t\t\t &oid) > 0)\n> -\t\t\tsorted = 0;\n> +\t\toidset_insert(&options->skiplist, &oid);\n\n...reading this implementation, where we always called\noid_array_append(), but then just kept track of whether the set was\nsorted...\n\n> \t}\n> \tif (ferror(fp))\n> \t\tdie_errno(\"Could not read '%s'\", path);\n> \tfclose(fp);\n> \tstrbuf_release(&sb);\n> -\n> -\tif (sorted)\n> -\t\tskiplist.sorted = 1;\n\n...and here where we assigned to the .sorted member of the oid_array...\n\n> static int object_on_skiplist(struct fsck_options *opts, struct object *obj)\n> {\n> -\tif (opts && opts->skiplist && obj)\n> -\t\treturn oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n> -\treturn 0;\n> +\treturn opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n> }\n\n....and here where we'd always do the lookup if the skiplist was\ninitialized, *not* just if it's sorted, and how the sha1-array.c code\nhas looked ever since cd94c6f91 (\"fsck: git receive-pack: support\nexcluding objects from fsck'ing\", 2015-06-22) when this was first added:\n\n $ git show cd94c6f91:sha1-array.c|grep -A5 sha1_array_lookup\n int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)\n {\n if (!array->sorted)\n sha1_array_sort(array);\n return sha1_pos(sha1, array->sha1, array->nr, sha1_access);\n }\n\nSo I think it makes sense to make this series a three-part, where in the\nfirst part we only change these docs to say s/sorted //, and modify the\ntests I added in 65a836fa6b (\"fsck: add stress tests for fsck.skipList\",\n2018-07-27) to assert that an unsorted & sorted list of SHA-1s works\njust as well.\n\nThen following up with your [12]/2, where the internal implementation is\nchanged, but we make it clear that it's *just* the internal\nimplementation. I.e. from a UI perspective the list never had to be\npre-sorted, we'd just spend some work sorting it on the first lookup if\nit wasn't sorted already.\n\nNow without some very careful reading it's not clear what \"we don't need\nto worry about any sort order anymore\" in the commit message means,\ni.e. what it really means is \"for the purposes of the internal\nimplementation, and as an opt-in user-side optimization ...\".\n\nI.e. an alternate version of this whole patch series could also be:\n\n diff --git a/Documentation/config.txt b/Documentation/config.txt\n index 1c4236498..930807e43 100644\n --- a/Documentation/config.txt\n +++ b/Documentation/config.txt\n @@ -1709,5 +1709,5 @@ will only cause git to warn.\n\n fsck.skipList::\n - The path to a sorted list of object names (i.e. one SHA-1 per\n + The path to a list of object names (i.e. one SHA-1 per\n line) that are known to be broken in a non-fatal way and should\n be ignored. This feature is useful when an established project\n diff --git a/fsck.c b/fsck.c\n index a0cee0be5..9d4e938ad 100644\n --- a/fsck.c\n +++ b/fsck.c\n @@ -184,14 +184,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n {\n static struct oid_array skiplist = OID_ARRAY_INIT;\n - int sorted, fd;\n + int fd;\n char buffer[GIT_MAX_HEXSZ + 1];\n struct object_id oid;\n\n - if (options->skiplist)\n - sorted = options->skiplist->sorted;\n - else {\n - sorted = 1;\n + if (!options->skiplist)\n options->skiplist = &skiplist;\n - }\n\n fd = open(path, O_RDONLY);\n @@ -208,13 +204,6 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n die(\"Invalid SHA-1: %s\", buffer);\n oid_array_append(&skiplist, &oid);\n - if (sorted && skiplist.nr > 1 &&\n - oidcmp(&skiplist.oid[skiplist.nr - 2],\n - &oid) > 0)\n - sorted = 0;\n }\n close(fd);\n -\n - if (sorted)\n - skiplist.sorted = 1;\n }\n\nNow, I like yours much better. I'm just saying that currently the\npatch/commit message combo is confusing about *what* it's\ndoing. I.e. let's not mix up the correction of docs that were always\nwrong with a non-change in the user facing implementation, and some\ninternal optimization all in one patch.\n"},{"id":"356584","messageId":"c7cbc289-d86e-09dc-bdb3-b5496cf0b7ce@web.de","threadId":"49100","inReplyTo":"87r2ikdzvc.fsf@evledraar.gmail.com","subject":"Re: [PATCH v2 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-27T15:23:01Z","receivedAt":"2018-08-27T15:23:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 27.08.2018 um 09:37 schrieb Ævar Arnfjörð Bjarmason:\n> \n> On Sat, Aug 25 2018, René Scharfe wrote:\n> \n>> diff --git a/Documentation/config.txt b/Documentation/config.txt\n>> index 2fa65b7516..80ab570579 100644\n>> --- a/Documentation/config.txt\n>> +++ b/Documentation/config.txt\n>> @@ -1715,7 +1715,7 @@ doing the same for `receive.fsck.` and `fetch.fsck.`\n>> will only cause git to warn.\n>>\n>> fsck.skipList::\n>> -\tThe path to a sorted list of object names (i.e. one SHA-1 per\n>> +\tThe path to a list of object names (i.e. one SHA-1 per\n>> \tline) that are known to be broken in a non-fatal way and should\n>> \tbe ignored. This feature is useful when an established project\n>> \tshould be accepted despite early commits containing errors that\n> \n> I was going to say that since this is a file format we're likely to\n> support across versions we should make a note that \"up to version\n> so-and-so this needed to be sorted, but that's longer the case. So\n> e.g. someone wouldn't test this on 2.20 (or read the online docs) and\n> then deploy this for older clients..\n> \n> But...\n> \n>> -\tif (options->skiplist)\n>> -\t\tsorted = options->skiplist->sorted;\n>> -\telse {\n>> -\t\tsorted = 1;\n>> -\t\toptions->skiplist = &skiplist;\n>> -\t}\n>> -\n>> \tfp = fopen(path, \"r\");\n>> \tif (!fp)\n>> \t\tdie(\"Could not open skip list: %s\", path);\n>> @@ -202,19 +192,12 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n>> \t\tconst char *p;\n>> \t\tif (parse_oid_hex(sb.buf, &oid, &p) || *p != '\\0')\n>> \t\t\tdie(\"Invalid SHA-1: %s\", sb.buf);\n>> -\t\toid_array_append(&skiplist, &oid);\n>> -\t\tif (sorted && skiplist.nr > 1 &&\n>> -\t\t\t\toidcmp(&skiplist.oid[skiplist.nr - 2],\n>> -\t\t\t\t &oid) > 0)\n>> -\t\t\tsorted = 0;\n>> +\t\toidset_insert(&options->skiplist, &oid);\n> \n> ...reading this implementation, where we always called\n> oid_array_append(), but then just kept track of whether the set was\n> sorted...\n> \n>> \t}\n>> \tif (ferror(fp))\n>> \t\tdie_errno(\"Could not read '%s'\", path);\n>> \tfclose(fp);\n>> \tstrbuf_release(&sb);\n>> -\n>> -\tif (sorted)\n>> -\t\tskiplist.sorted = 1;\n> \n> ...and here where we assigned to the .sorted member of the oid_array...\n> \n>> static int object_on_skiplist(struct fsck_options *opts, struct object *obj)\n>> {\n>> -\tif (opts && opts->skiplist && obj)\n>> -\t\treturn oid_array_lookup(opts->skiplist, &obj->oid) >= 0;\n>> -\treturn 0;\n>> +\treturn opts && obj && oidset_contains(&opts->skiplist, &obj->oid);\n>> }\n> \n> ....and here where we'd always do the lookup if the skiplist was\n> initialized, *not* just if it's sorted, and how the sha1-array.c code\n> has looked ever since cd94c6f91 (\"fsck: git receive-pack: support\n> excluding objects from fsck'ing\", 2015-06-22) when this was first added:\n> \n> $ git show cd94c6f91:sha1-array.c|grep -A5 sha1_array_lookup\n> int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1)\n> {\n> if (!array->sorted)\n> sha1_array_sort(array);\n> return sha1_pos(sha1, array->sha1, array->nr, sha1_access);\n> }\n> \n> So I think it makes sense to make this series a three-part, where in the\n> first part we only change these docs to say s/sorted //, and modify the\n> tests I added in 65a836fa6b (\"fsck: add stress tests for fsck.skipList\",\n> 2018-07-27) to assert that an unsorted & sorted list of SHA-1s works\n> just as well.\n> \n> Then following up with your [12]/2, where the internal implementation is\n> changed, but we make it clear that it's *just* the internal\n> implementation. I.e. from a UI perspective the list never had to be\n> pre-sorted, we'd just spend some work sorting it on the first lookup if\n> it wasn't sorted already.\n> \n> Now without some very careful reading it's not clear what \"we don't need\n> to worry about any sort order anymore\" in the commit message means,\n> i.e. what it really means is \"for the purposes of the internal\n> implementation, and as an opt-in user-side optimization ...\".\n> \n> I.e. an alternate version of this whole patch series could also be:\n> \n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index 1c4236498..930807e43 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -1709,5 +1709,5 @@ will only cause git to warn.\n> \n> fsck.skipList::\n> - The path to a sorted list of object names (i.e. one SHA-1 per\n> + The path to a list of object names (i.e. one SHA-1 per\n> line) that are known to be broken in a non-fatal way and should\n> be ignored. This feature is useful when an established project\n> diff --git a/fsck.c b/fsck.c\n> index a0cee0be5..9d4e938ad 100644\n> --- a/fsck.c\n> +++ b/fsck.c\n> @@ -184,14 +184,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n> {\n> static struct oid_array skiplist = OID_ARRAY_INIT;\n> - int sorted, fd;\n> + int fd;\n> char buffer[GIT_MAX_HEXSZ + 1];\n> struct object_id oid;\n> \n> - if (options->skiplist)\n> - sorted = options->skiplist->sorted;\n> - else {\n> - sorted = 1;\n> + if (!options->skiplist)\n> options->skiplist = &skiplist;\n> - }\n> \n> fd = open(path, O_RDONLY);\n> @@ -208,13 +204,6 @@ static void init_skiplist(struct fsck_options *options, const char *path)\n> die(\"Invalid SHA-1: %s\", buffer);\n> oid_array_append(&skiplist, &oid);\n> - if (sorted && skiplist.nr > 1 &&\n> - oidcmp(&skiplist.oid[skiplist.nr - 2],\n> - &oid) > 0)\n> - sorted = 0;\n> }\n> close(fd);\n> -\n> - if (sorted)\n> - skiplist.sorted = 1;\n> }\n> \n> Now, I like yours much better. I'm just saying that currently the\n> patch/commit message combo is confusing about *what* it's\n> doing. I.e. let's not mix up the correction of docs that were always\n> wrong with a non-change in the user facing implementation, and some\n> internal optimization all in one patch.\n\nNow you have me confused. Unsorted lists were always accepted, but the\ndocumentation asked for a sorted one anyway, probably to avoid sorting\nit with every use. Switching the underlying data structure makes that a\nmoot point -- sortedness is no longer a concern at all -- not in the\ncode, and not for users.\n\nInviting users to run the array implementation with unsorted lists is\nnot incorrect, but it also doesn't help anyone. We could clarify that\nsorted lists are preferred or recommended instead of required. I don't\nsee value in perfecting the documentation of a quirk just before\nremoving it, though.\n\nRené\n"},{"id":"356636","messageId":"20180827230040.GA10402@sigill.intra.peff.net","threadId":"49100","inReplyTo":"aaf03ba2-1369-2dc3-c3ec-739a1c56606e@web.de","subject":"Re: [PATCH v2 1/2] fsck: use strbuf_getline() to read skiplist file","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-27T23:00:40Z","receivedAt":"2018-08-27T23:00:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 25, 2018 at 08:50:28PM +0200, René Scharfe wrote:\n\n> buffer is unlikely to contain a NUL character, so printing its contents\n> using %s in a die() format is unsafe (detected with ASan).\n\nHaving mostly forgotten about our earlier discussion, I got confused by\nthis, thinking the problem was that there is some issue with missing\nNULs in the input.\n\nBut it is really just:\n\n We read() into a buffer and on error format the contents using \"%s\".\n But read() does not NUL-terminate, so die() might walk past the end of\n the buffer.\n\nWe _might_ be saved by a NUL in the input, but that is not the primary\nconcern. ;)\n\nNot worth a re-roll on its own, but since there is some other\ndiscussion, I thought I'd mention my confusion. :)\n\n> Added error check.\n> Hopefully fixed my MUA config..\n> \n> fsck.c | 25 ++++++++++++-------------\n> 1 file changed, 12 insertions(+), 13 deletions(-)\n\nPatch itself looks good to me.\n\n-Peff\n"},{"id":"356637","messageId":"20180827230314.GB10402@sigill.intra.peff.net","threadId":"49100","inReplyTo":"030bac66-eeb4-7bc9-8f27-1e6b4124fd76@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-27T23:03:14Z","receivedAt":"2018-08-27T23:03:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 26, 2018 at 01:37:41PM +0200, René Scharfe wrote:\n\n> Am 14.08.2018 um 03:58 schrieb Jeff King:\n> > Your suggestion can be implemented using khash (my patch below).\n> > \n> >> Before:\n> >> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n> >>\n> >> Time (mean ± σ): 269.5 ms ± 26.7 ms [User: 247.7 ms, System: 21.4 ms]\n> >>\n> >> Range (min … max): 240.3 ms … 339.3 ms\n> >>\n> >> After:\n> >> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n> >>\n> >> Time (mean ± σ): 224.2 ms ± 18.2 ms [User: 201.7 ms, System: 22.1 ms]\n> >>\n> >> Range (min … max): 205.0 ms … 259.0 ms\n> > \n> > Yeah. My best-of-five dropped from 300ms to 247ms. That 300 was using\n> > the memory pool, though khash's deletion strategy isn't all that\n> > different (the wasted memory hangs around until the next hash resize,\n> > but if you're evenly dropping and adding, you likely won't need to\n> > resize).\n> \n> With your khash patch:\n> \n> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'\n> \n> Time (mean ± σ): 159.1 ms ± 20.5 ms [User: 140.3 ms, System: 18.5 ms]\n> \n> Range (min … max): 140.0 ms … 214.0 ms\n> \n> So it seems worth it.\n\nHmm, that really does. Which is a shame, because I hoped that one day we\ncould get rid of the nasty macro-infestation that is khash.h. But it\nreally is a lot faster than the alternatives.\n\n> [...]\n\nI agree with all of your comments here. What I posted was just trying to\ndo the least amount of work to get something we could time.\n\nDo you want to pick up this topic and carry it forward?\n\n-Peff\n"},{"id":"359384","messageId":"9e2440cc-39a6-f51b-9aee-8536020ed033@web.de","threadId":"49100","inReplyTo":"20180827230314.GB10402@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-01T19:15:53Z","receivedAt":"2018-10-01T19:21:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.08.2018 um 01:03 schrieb Jeff King:\n> On Sun, Aug 26, 2018 at 01:37:41PM +0200, René Scharfe wrote:\n>> So it seems worth it.\n> \n> Hmm, that really does. Which is a shame, because I hoped that one day we\n> could get rid of the nasty macro-infestation that is khash.h. But it\n> really is a lot faster than the alternatives.\n\nWell, we only compare it to hashmap.c here. There might be better\nimplementations out there. Hash tables in plain old C seem to be much\nharder to find than e.g. in C++, though.\n\nAnd then there are several possible variations that affect\nperformance -- perhaps hashmap.c could be improved by using open\naddressing, maybe with Robin Hood hashing, and/or by offering better\nsupport for sets, and/or by having a few macros to allow type\nspecialization.\n\nBut I like how khash.h is both already in the tree and also really easy\nto deploy, as it's just a single header file. It's a tasty low-hanging\nfruit.\n\n> Do you want to pick up this topic and carry it forward?\n\nWell, I tried to simplify the implementation as much as possible and\nended up doing the opposite of what I wrote earlier. Hmm.\n\nThe patch below postpones struct allocation until cleanup time, which is\na bit weird. We can't avoid it fully without reimplementing kh_destroy,\nbut we can use structs supplied by callers for basically all other\noperations. That avoids NULL checks, and the main benefits of that are\nsimplicity and safety; performance is not much better without them.\n\nThis patch doesn't provide a _count (or _is_empty) method. It would be\ncleaner to have one added as the first step and just change its\nimplementation when switching to khash, but it's harder than expected\nwith hashmap.c; doing that later (if at all) is easier.\n\nUsing sha1hash instead of open-coding it may seem a bit anachronistic,\nbut is the best way to document the usage of that pattern (i.e. to\ntruncate a SHA1 hash to get a shorter one for a hash table).\n\n-- >8 --\nSubject: [PATCH] oidset: use khash\n\nReimplement struct oidset using khash.h in order to reduce its memory\nfootprint and make it faster.\n\nThis is straight-forward, except for oidset_clear(), which needs to\nallocate a kh_oid_t on the heap in order to be able to feed it to\nkh_destroy_oid() for release it. Alternatively we could open-code the\nrelevant parts of the latter, but that would be a layering violation.\n\nPerformance of a command that mainly checks for duplicate objects\nusing an oidset, with master and Clang 6.0.1:\n\n$ cmd=\"./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\"\n\n$ /usr/bin/time $cmd >/dev/null\n0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k\n0inputs+0outputs (0major+11204minor)pagefaults 0swaps\n\n$ hyperfine \"$cmd\"\nBenchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n Time (mean ± σ): 250.0 ms ± 6.0 ms [User: 225.9 ms, System: 23.6 ms]\n\n Range (min … max): 242.0 ms … 261.1 ms\n\nAnd with this patch:\n\n$ /usr/bin/time $cmd >/dev/null\n0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k\n0inputs+0outputs (0major+8318minor)pagefaults 0swaps\n\n$ hyperfine \"$cmd\"\nBenchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n Time (mean ± σ): 151.9 ms ± 4.9 ms [User: 130.5 ms, System: 21.2 ms]\n\n Range (min … max): 148.2 ms … 170.4 ms\n\nInitial-patch-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\n fetch-pack.c | 2 +-\n oidset.c | 36 ++++++++++++++----------------------\n oidset.h | 36 ++++++++++++++++++++++++++++--------\n 3 files changed, 43 insertions(+), 31 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 75047a4b2a..a839315726 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \t * add to \"newlist\" between calls, the additions will always be for\n \t * oids that are already in the set.\n \t */\n-\tif (!tip_oids->map.map.tablesize) {\n+\tif (!tip_oids->set.n_buckets) {\n \t\tadd_refs_to_oidset(tip_oids, unmatched);\n \t\tadd_refs_to_oidset(tip_oids, newlist);\n \t}\ndiff --git a/oidset.c b/oidset.c\nindex 454c54f933..d15b2b7a89 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -3,38 +3,30 @@\n \n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tif (!set->map.map.tablesize)\n-\t\treturn 0;\n-\treturn !!oidmap_get(&set->map, oid);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\treturn pos != kh_end(&set->set);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tif (!set->map.map.tablesize)\n-\t\toidmap_init(&set->map, 0);\n-\telse if (oidset_contains(set, oid))\n-\t\treturn 1;\n-\n-\tentry = xmalloc(sizeof(*entry));\n-\toidcpy(&entry->oid, oid);\n-\n-\toidmap_put(&set->map, entry);\n-\treturn 0;\n+\tint added;\n+\tkh_put_oid(&set->set, *oid, &added);\n+\treturn !added;\n }\n \n int oidset_remove(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tentry = oidmap_remove(&set->map, oid);\n-\tfree(entry);\n-\n-\treturn (entry != NULL);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\tif (pos == kh_end(&set->set))\n+\t\treturn 0;\n+\tkh_del_oid(&set->set, pos);\n+\treturn 1;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\toidmap_free(&set->map, 1);\n+\tkh_oid_t *to_free = kh_init_oid();\n+\t*to_free = set->set;\n+\tkh_destroy_oid(to_free);\n+\toidset_init(set, 0);\n }\ndiff --git a/oidset.h b/oidset.h\nindex 40ec5f87fe..4b90540cd4 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,7 +1,8 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n-#include \"oidmap.h\"\n+#include \"hashmap.h\"\n+#include \"khash.h\"\n \n /**\n * This API is similar to sha1-array, in that it maintains a set of object ids\n@@ -15,19 +16,33 @@\n * table overhead.\n */\n \n+static inline unsigned int oid_hash(struct object_id oid)\n+{\n+\treturn sha1hash(oid.hash);\n+}\n+\n+static inline int oid_equal(struct object_id a, struct object_id b)\n+{\n+\treturn oideq(&a, &b);\n+}\n+\n+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n+\n /**\n * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n */\n struct oidset {\n-\tstruct oidmap map;\n+\tkh_oid_t set;\n };\n \n-#define OIDSET_INIT { OIDMAP_INIT }\n+#define OIDSET_INIT { { 0 } }\n \n \n static inline void oidset_init(struct oidset *set, size_t initial_size)\n {\n-\toidmap_init(&set->map, initial_size);\n+\tmemset(&set->set, 0, sizeof(set->set));\n+\tif (initial_size)\n+\t\tkh_resize_oid(&set->set, initial_size);\n }\n \n /**\n@@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);\n void oidset_clear(struct oidset *set);\n \n struct oidset_iter {\n-\tstruct oidmap_iter m_iter;\n+\tkh_oid_t *set;\n+\tkhiter_t iter;\n };\n \n static inline void oidset_iter_init(struct oidset *set,\n \t\t\t\t struct oidset_iter *iter)\n {\n-\toidmap_iter_init(&set->map, &iter->m_iter);\n+\titer->set = &set->set;\n+\titer->iter = kh_begin(iter->set);\n }\n \n static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)\n {\n-\tstruct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);\n-\treturn e ? &e->oid : NULL;\n+\tfor (; iter->iter != kh_end(iter->set); iter->iter++) {\n+\t\tif (kh_exist(iter->set, iter->iter))\n+\t\t\treturn &kh_key(iter->set, iter->iter++);\n+\t}\n+\treturn NULL;\n }\n \n static inline struct object_id *oidset_iter_first(struct oidset *set,\n-- \n2.19.0\n"},{"id":"359389","messageId":"20181001202605.GB10234@sigill.intra.peff.net","threadId":"49100","inReplyTo":"9e2440cc-39a6-f51b-9aee-8536020ed033@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-01T20:26:06Z","receivedAt":"2018-10-01T20:26:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 01, 2018 at 09:15:53PM +0200, René Scharfe wrote:\n\n> Am 28.08.2018 um 01:03 schrieb Jeff King:\n> > On Sun, Aug 26, 2018 at 01:37:41PM +0200, René Scharfe wrote:\n> >> So it seems worth it.\n> > \n> > Hmm, that really does. Which is a shame, because I hoped that one day we\n> > could get rid of the nasty macro-infestation that is khash.h. But it\n> > really is a lot faster than the alternatives.\n> \n> Well, we only compare it to hashmap.c here. There might be better\n> implementations out there. Hash tables in plain old C seem to be much\n> harder to find than e.g. in C++, though.\n\nI think it may be either-or here. The speed benefit to using khash here\nis that we stick the data into the hash table itself, rather than\nincurring a separate malloc for each entry. Which is pretty hard to do\nin C without macros (the alternative is lots of void pointers, and\ntelling the hash table \"your size is X bytes\").\n\n> And then there are several possible variations that affect\n> performance -- perhaps hashmap.c could be improved by using open\n> addressing, maybe with Robin Hood hashing, and/or by offering better\n> support for sets, and/or by having a few macros to allow type\n> specialization.\n\nThe reason hashmap.c was added was to avoid open addressing. ;)\n\nSo yeah, I think it could perhaps be improved, but in my mind talking\nabout \"hashmap.c\" is fundamentally talking about chained buckets.\n\nBut whatever you want to call it, I would be happy with a more type-safe\nand performance hashmap.\n\n> But I like how khash.h is both already in the tree and also really easy\n> to deploy, as it's just a single header file. It's a tasty low-hanging\n> fruit.\n\nYeah. And if it really does perform better, I think we should stick with\nit in the code base. I wonder if we could stand to clean up the\ninterfaces a little. E.g., I had a hard time declaring a hash in one\nplace, and then defining it somewhere else. And I think as you found\nthat it insists on heap-allocating the hash-table struct itself, which\ndoes not match our usual style.\n\n> > Do you want to pick up this topic and carry it forward?\n> \n> Well, I tried to simplify the implementation as much as possible and\n> ended up doing the opposite of what I wrote earlier. Hmm.\n> \n> The patch below postpones struct allocation until cleanup time, which is\n> a bit weird. We can't avoid it fully without reimplementing kh_destroy,\n> but we can use structs supplied by callers for basically all other\n> operations. That avoids NULL checks, and the main benefits of that are\n> simplicity and safety; performance is not much better without them.\n\nYour patch looks OK from a cursory view. I actually think that retaining\nthe extra NULL encapsulation is not the worst thing in the world. Most\ncallers should be going through the oid_* functions anyway.\n\nBut if we want to take the time to refactor khash (or even write our own\nversion, taking inspiration from what's there), the result would be\nbetter still. If you're not planning to work on that in the near future,\nthough, I'd be OK with either of the alternates (the extra level of\npointer indirection from earlier, or this slight kh_destroy hackery\nhere).\n\n> -- >8 --\n> Subject: [PATCH] oidset: use khash\n> \n> Reimplement struct oidset using khash.h in order to reduce its memory\n> footprint and make it faster.\n> \n> This is straight-forward, except for oidset_clear(), which needs to\n> allocate a kh_oid_t on the heap in order to be able to feed it to\n> kh_destroy_oid() for release it. Alternatively we could open-code the\n> relevant parts of the latter, but that would be a layering violation.\n\nThis is kind of a layering violation, too. You're assuming that struct\nassignment is sufficient to make one kh struct freeable from another\npointer. That's probably reasonable, since you're just destroying them\nboth (e.g., some of our FLEX structs point into their own struct memory,\nmaking a hidden dependency; but they obviously would not need to free\nsuch a field).\n\n-Peff\n"},{"id":"359445","messageId":"d2421f36-563c-92ac-3fc9-29306d94b6fd@web.de","threadId":"49100","inReplyTo":"20181001202605.GB10234@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-02T19:05:32Z","receivedAt":"2018-10-02T19:05:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 01.10.2018 um 22:26 schrieb Jeff King:\n> On Mon, Oct 01, 2018 at 09:15:53PM +0200, René Scharfe wrote:\n> The reason hashmap.c was added was to avoid open addressing. ;)\nBecause efficient removal of elements is easier to implement with\nchaining, according to 6a364ced49 (add a hashtable implementation that\nsupports O(1) removal). khash.h deletes using its flags bitmap. We\ndidn't compare their performance when entries are removed so far.\n\n> So yeah, I think it could perhaps be improved, but in my mind talking\n> about \"hashmap.c\" is fundamentally talking about chained buckets.\n\nAdmittedly I wouldn't touch hashmap.c, as I find its interface too\ncomplex to wrap my head around. But perhaps I just didn't try hard\nenough, yet.\n\n>> But I like how khash.h is both already in the tree and also really easy\n>> to deploy, as it's just a single header file. It's a tasty low-hanging\n>> fruit.\n> \n> Yeah. And if it really does perform better, I think we should stick with\n> it in the code base. I wonder if we could stand to clean up the\n> interfaces a little. E.g., I had a hard time declaring a hash in one\n> place, and then defining it somewhere else.\n\nYou can't use KHASH_DECLARE and KHASH_INIT together, as both declare\nthe same structs. So I guess the idea is to have a header file with\nKHASH_DECLARE and a .c file with KHASH_INIT, the latter *not* including\nthe former, but both including khash.h. I didn't actually try that,\nthough.\n\n> And I think as you found\n> that it insists on heap-allocating the hash-table struct itself, which\n> does not match our usual style.\n\nPerhaps we can fix that with little effort (see below).\n\n>> This is straight-forward, except for oidset_clear(), which needs to\n>> allocate a kh_oid_t on the heap in order to be able to feed it to\n>> kh_destroy_oid() for release it. Alternatively we could open-code the\n>> relevant parts of the latter, but that would be a layering violation.\n> \n> This is kind of a layering violation, too. You're assuming that struct\n> assignment is sufficient to make one kh struct freeable from another\n> pointer. That's probably reasonable, since you're just destroying them\n> both (e.g., some of our FLEX structs point into their own struct memory,\n> making a hidden dependency; but they obviously would not need to free\n> such a field).\n\nFair enough. How about this on top? (The khash.h part would go in\nfirst in a separate patch in a proper series.)\n\nNB: I stuck to the 4-spaces-tabs formatting in khash.h here.\n\n---\n khash.h | 9 +++++++--\n oidset.c | 4 +---\n 2 files changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/khash.h b/khash.h\nindex 07b4cc2e67..d10caa0c35 100644\n--- a/khash.h\n+++ b/khash.h\n@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;\n \tSCOPE kh_##name##_t *kh_init_##name(void) {\t\t\t\t\t\t\t\\\n \t\treturn (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\tSCOPE void kh_release_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n+\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree(h->flags);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->keys);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \tSCOPE void kh_destroy_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n \t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\tif (h) {\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tfree((void *)h->keys); free(h->flags);\t\t\t\t\t\\\n-\t\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\\\n+\t\t\tkh_release_##name(h);\t\t\t\t\t\t\t\t\t\t\\\n \t\t\tfree(h);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\ndiff --git a/oidset.c b/oidset.c\nindex d15b2b7a89..9836d427ef 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -25,8 +25,6 @@ int oidset_remove(struct oidset *set, const struct object_id *oid)\n \n void oidset_clear(struct oidset *set)\n {\n-\tkh_oid_t *to_free = kh_init_oid();\n-\t*to_free = set->set;\n-\tkh_destroy_oid(to_free);\n+\tkh_release_oid(&set->set);\n \toidset_init(set, 0);\n }\n-- \n2.19.0\n"},{"id":"359452","messageId":"20181002191900.GA2014@sigill.intra.peff.net","threadId":"49100","inReplyTo":"d2421f36-563c-92ac-3fc9-29306d94b6fd@web.de","subject":"Re: [PATCH 2/2] fsck: use oidset for skiplist","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-02T19:19:00Z","receivedAt":"2018-10-02T19:19:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 02, 2018 at 09:05:32PM +0200, René Scharfe wrote:\n\n> > The reason hashmap.c was added was to avoid open addressing. ;)\n> Because efficient removal of elements is easier to implement with\n> chaining, according to 6a364ced49 (add a hashtable implementation that\n> supports O(1) removal). khash.h deletes using its flags bitmap. We\n> didn't compare their performance when entries are removed so far.\n\nI think it may depend on your workload. Open-addressing generally uses a\ntombstone, so you're still dealing with the \"deleted\" entries until the\nnext table resize. I suspect that's fine in most cases, but I also am\nsure you could find a benchmark that favors the chained approach (I\nthink in most cases we actually never delete at all -- we simply fill up\na table and then eventually clear it).\n\n> > So yeah, I think it could perhaps be improved, but in my mind talking\n> > about \"hashmap.c\" is fundamentally talking about chained buckets.\n> \n> Admittedly I wouldn't touch hashmap.c, as I find its interface too\n> complex to wrap my head around. But perhaps I just didn't try hard\n> enough, yet.\n\nFWIW, it's not just you. ;)\n\n> > Yeah. And if it really does perform better, I think we should stick with\n> > it in the code base. I wonder if we could stand to clean up the\n> > interfaces a little. E.g., I had a hard time declaring a hash in one\n> > place, and then defining it somewhere else.\n> \n> You can't use KHASH_DECLARE and KHASH_INIT together, as both declare\n> the same structs. So I guess the idea is to have a header file with\n> KHASH_DECLARE and a .c file with KHASH_INIT, the latter *not* including\n> the former, but both including khash.h. I didn't actually try that,\n> though.\n\nYeah, that seems weird. You'd want to include one from the other to make\nsure that they both match.\n\nBy the way, if you do want to pursue changes, I have no problem at all\nhacking up khash into something that can't be merged with its upstream.\nIt's nice that it's a well-used and tested library, but I'd much rather\nhave something that we on this project understand (and that matches our\nconventions and style).\n\n> > This is kind of a layering violation, too. You're assuming that struct\n> > assignment is sufficient to make one kh struct freeable from another\n> > pointer. That's probably reasonable, since you're just destroying them\n> > both (e.g., some of our FLEX structs point into their own struct memory,\n> > making a hidden dependency; but they obviously would not need to free\n> > such a field).\n> \n> Fair enough. How about this on top? (The khash.h part would go in\n> first in a separate patch in a proper series.)\n\nYes, much nicer, and the khash change wasn't too painful.\n\n-Peff\n"}]}