{"thread":{"id":"27801","subject":"[RFC/PATCHv2 0/6] generation numbers for faster traversals","startedAt":"2011-07-13T06:47:09Z","lastAt":"2011-08-06T06:30:53Z","messageCount":57,"participants":["Jeff King","Bert Wesarg","Eric Sunshine","Jonathan Nieder","Junio C Hamano","Sverre Rabbelier","Jakub Narebski","René Scharfe"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"171205","messageId":"20110713064709.GA18499@sigill.intra.peff.net","threadId":"27801","inReplyTo":null,"subject":"[RFC/PATCHv2 0/6] generation numbers for faster traversals","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T06:47:09Z","receivedAt":"2011-07-13T06:47:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here's an updated version of the series posted here:\n\n http://article.gmane.org/gmane.comp.version-control.git/176861\n\nI'll discuss specific changes in each patch, but the summary is:\n\n 1. object-cache is now called metadata-cache.\n\n 2. The interface to \"decorate\" and \"metadata-cache\" is a little\n cleaner, and it's harder to break it by changing the \"width\" field\n at runtime.\n\n 3. Cache files have a header with a version for future-proofing.\n\n 4. Cache files on disk are automatically invalidated if grafts or\n replace refs change.\n\nThe patches are:\n\n [1/6]: decorate: allow storing values instead of pointers\n [2/6]: add metadata-cache infrastructure\n [3/6]: commit: add commit_generation function\n [4/6]: pretty: support %G to show the generation number of a commit\n [5/6]: check commit generation cache validity against grafts\n [6/6]: limit \"contains\" traversals based on commit generation\n\n-Peff\n"},{"id":"171206","messageId":"20110713065700.GA18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T06:57:00Z","receivedAt":"2011-07-13T06:57:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The decorate API provides a mapping of objects to arbitrary\nvalues. Until now, it did this by allowing you to store a\nvoid pointer, which could point to other storage. This has\ntwo problems:\n\n 1. It's inefficient. To store even a small value, you have\n to allocate persistent storage. So we end up storing\n both the value and a pointer to it.\n\n 2. It's a pain to use. To avoid heap overhead for small\n values, you have to either use a custom allocater, or\n you have to shoe-horn the value into the void pointer\n (if it's small enough to fit).\n\nThis patch lets you store fixed-size values directly in the\nhash table without allocating them elsewhere. This is a\ndefinite win for any value smaller than or equal to a\npointer. It's probably a win for slightly larger values, but\nmay eventually be slower for storing large structs (because\nthe values are copied when the hash grows).\n\nIt also provides a more natural interface for storing small\nvalues; see the changes in fast-export.c, which can now drop\nits pointer arithmetic magic.\n\nThe original \"store and retrieve a void pointer\" API is easy\nto implement on top of this (the values we store are the\npointers). The add_decoration and lookup_decoration\nfunctions are kept for compatibility.\n\nSigned-off-by: Jeff King \n---\nThe \"width\" field is now const; you must either use a static\ninitializer or overwrite a struct decoration via memset. This gives us a\nlittle more language-enforced safety.\n\nThe \"stride\" and \"end\" fields were removed in favor of run-time\ncalculation. The calculations are wrapped in inline functions to give\nthe optimizer a chance to remove them.\n\nSince we're translating sizes to pointers in our loops via these\nfunctions now anyway, I made the iteration interface a bit more sane.\nIt used to be:\n\n unsigned char *p;\n for (p = n->hash; p < n->end; p += n->stride) {\n struct object_decoration *e = (struct object_decoration *)p;\n ...\n }\n\nwhich really leaks ugly implementation details. You can now do:\n\n int i;\n for (i = 0; i < n->size; i++) {\n struct object_decoration *e = decoration_slot(n, i);\n ...\n }\n\nwhich is a bit more natural.\n\nI peeked at the output of \"gcc -O3\"; it doesn't actually hoist much of\nthe decoration_slot calculation out of the loop. But I measured the code\nfrom the previous series with this one, and wasn't able to detect a\ndifference. So I think using pointers was just a silly premature\nmicro-optimization.\n\n Documentation/technical/api-decorate.txt | 164 +++++++++++++++++++++++++++++-\n builtin/fast-export.c | 29 ++----\n decorate.c | 70 +++++++++----\n decorate.h | 37 ++++++-\n 4 files changed, 251 insertions(+), 49 deletions(-)\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 1d52a6c..b048b28 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -1,6 +1,166 @@\n decorate API\n ============\n \n-Talk about \n+The decorate API is a system for efficiently mapping objects to values\n+in memory. It is slightly slower than an actual member of an object\n+struct (because it incurs a hash lookup), but it uses less memory when\n+the mapping is not in use, or when the number of decorated objects is\n+small compared to the total number of objects.\n \n-(Linus)\n+For efficiency, the mapping is capable of storing actual byte values, as\n+long as the byte values for each element are of a fixed size. So one\n+could, for example, map objects into 32-bit integers. For ease of use,\n+functions are provided for storing the values of arbitrary pointers,\n+which can point to strings or structs.\n+\n+Data Structures\n+---------------\n+\n+`struct decoration`::\n+\n+\tThis structure represents a single mapping of objects to\n+\tvalues. Its fields are:\n+\n+\t`name`:::\n+\t\tThis field is not used by the decorate API itself, but\n+\t\tmay be used by calling code.\n+\n+\t`width`:::\n+\t\tThis field specifies the width (in units of `char`) of\n+\t\tthe values to be stored. This field must be set to its\n+\t\tfinal value when the decoration struct is initialized.\n+\t\tA width of `0` is equivalent to `sizeof(void *)`.\n+\n+\t`nr`:::\n+\t\tThe number of objects currently mapped by the\n+\t\tdecoration.\n+\n+\t`size`:::\n+\t\tThe number of hash slots allocated; this is kept to at\n+\t\tleast 3/2 of the number of actual slots used, to keep\n+\t\tthe hash sparse.\n+\n+\t`hash`:::\n+\t\tA pointer to an array of actual `object_decoration`\n+\t\tstructs. Note that because the width of `struct\n+\t\tobject_decoration` is not known until runtime, this\n+\t\tarray is stored with type `unsigned char *`. To access\n+\t\tindividual items, one must perform pointer arithmetic;\n+\t\tsee the `decoration_by_offset` function below.\n+\n+`struct object_decoration`::\n+\n+\tA structure representing the decoration of a single object.\n+\tCallers will not normally need to use this object unless they\n+\tare iterating all elements in the decoration hash. The `base`\n+\tfield points to the object being mapped (or `NULL` if it is\n+\tan empty hash slot). The `decoration` field stores the mapped\n+\tvalue as a sequence of bytes; use the `width` field in `struct\n+\tdecoration` to know the exact size.\n+\n+\n+Functions\n+---------\n+\n+`add_decoration_value`::\n+\n+\tAdd a mapping from an object to a sequence of bytes. The number\n+\tof bytes pointed to by `decoration` should be equal to the\n+\t`width` field of the `struct decoration`. If the `old` parameter\n+\tis not NULL and a there was already a value for the object, the\n+\tbytes of the old value are copied into `old`. The return value\n+\tis `1` if there was a previous value, or `0` otherwise. Note\n+\tthat if there is no previous value, then `old` is left\n+\tuntouched; it is the responsibility of the caller to either\n+\tcheck the return value or to set a sentinel value in `old`.\n+\n+`lookup_decoration_value`::\n+\n+\tRetrieve a decoration from the mapping. The return value is a\n+\tpointer to the sequence of bytes representing the value (of\n+\tlength `width`), or `NULL` if no value is found.\n+\n+`add_decoration`::\n+\n+\tAdd a mapping from an object to a void pointer. If a previous\n+\tpointer exists for the object, it is returned; otherwise, `NULL`\n+\tis returned.\n+\n+`lookup_decoration`::\n+\n+\tRetrieve a void pointer from the mapping. The return value is\n+\tthe stored pointer, or `NULL` if there is no stored pointer.\n+\n+`decoration_slot`::\n+\n+\tRetrieve the decoration stored at slot `i` in the hash table.\n+\tIf the `base` field of the returned `struct object_decoration`\n+\tis `NULL`, then no value is stored at that slot. This function\n+\tis useful when iterating over the entire contents of the hash\n+\ttable. See the iteration example below.\n+\n+\n+Examples\n+--------\n+\n+Store and retrieve pointers to structs:\n+\n+-------------------------------------------------------------------\n+/* no need to set width parameter; it defaults to sizeof(void *) */\n+static struct decoration commit_foos;\n+\n+void store_foo(const struct commit *c, const char *name)\n+{\n+\tstruct foo *value = alloc_foo(name);\n+\tstruct foo *old;\n+\n+\told = add_decoration(&commit_foos, c->object, value);\n+\tfree(old);\n+}\n+\n+const struct foo *get_foo(const struct commit *c)\n+{\n+\treturn lookup_decoration(&commit_foos, c->object);\n+}\n+-------------------------------------------------------------------\n+\n+Store and retrieve `unsigned long` integers:\n+\n+-------------------------------------------------------------------\n+static struct decoration longs = { \"my longs\", sizeof(unsigned long) };\n+\n+void store_long(const struct object *obj, unsigned long value)\n+{\n+\tunsigned long old;\n+\tif (add_decoration_value(&longs, obj, &value, &old)\n+\t\tprintf(\"old value was %lu\\n\", old);\n+}\n+\n+void print_long(const struct object *obj)\n+{\n+\tunsigned long *value = lookup_decoration_value(&longs, obj);\n+\tif (!value)\n+\t\tprintf(\"no value\\n\");\n+\telse\n+\t\tprintf(\"value is %lu\\n\", *value);\n+}\n+-------------------------------------------------------------------\n+\n+Iterate over all stored decorations:\n+\n+-------------------------------------------------------------------\n+void dump_longs(void)\n+{\n+\tint i;\n+\tfor (i = 0; i < longs.size; i++) {\n+\t\tstruct object_decoration *e = decoration_slot(&longs, i);\n+\t\tunsigned long *value = (unsigned long *)e->decoration;\n+\n+\t\t/* empty hash slot */\n+\t\tif (!e->base)\n+\t\t\tcontinue;\n+\n+\t\tprintf(\"%s -> %lu\\n\", sha1_to_hex(e->base->sha1), *value);\n+\t}\n+}\n+-------------------------------------------------------------------\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex daf1945..82b458d 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -59,7 +59,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,\n \treturn 0;\n }\n \n-static struct decoration idnums;\n+static struct decoration idnums = { NULL, sizeof(uint32_t) };\n static uint32_t last_idnum;\n \n static int has_unshown_parent(struct commit *commit)\n@@ -73,20 +73,9 @@ static int has_unshown_parent(struct commit *commit)\n \treturn 0;\n }\n \n-/* Since intptr_t is C99, we do not use it here */\n-static inline uint32_t *mark_to_ptr(uint32_t mark)\n-{\n-\treturn ((uint32_t *)NULL) + mark;\n-}\n-\n-static inline uint32_t ptr_to_mark(void * mark)\n-{\n-\treturn (uint32_t *)mark - (uint32_t *)NULL;\n-}\n-\n static inline void mark_object(struct object *object, uint32_t mark)\n {\n-\tadd_decoration(&idnums, object, mark_to_ptr(mark));\n+\tadd_decoration_value(&idnums, object, &mark, NULL);\n }\n \n static inline void mark_next_object(struct object *object)\n@@ -96,10 +85,10 @@ static inline void mark_next_object(struct object *object)\n \n static int get_object_mark(struct object *object)\n {\n-\tvoid *decoration = lookup_decoration(&idnums, object);\n-\tif (!decoration)\n+\tuint32_t *mark = lookup_decoration_value(&idnums, object);\n+\tif (!mark)\n \t\treturn 0;\n-\treturn ptr_to_mark(decoration);\n+\treturn *mark;\n }\n \n static void show_progress(void)\n@@ -537,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)\n static void export_marks(char *file)\n {\n \tunsigned int i;\n-\tuint32_t mark;\n-\tstruct object_decoration *deco = idnums.hash;\n \tFILE *f;\n \tint e = 0;\n \n@@ -547,15 +534,15 @@ static void export_marks(char *file)\n \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n \n \tfor (i = 0; i < idnums.size; i++) {\n+\t\tstruct object_decoration *deco = decoration_slot(&idnums, i);\n \t\tif (deco->base && deco->base->type == 1) {\n-\t\t\tmark = ptr_to_mark(deco->decoration);\n-\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n+\t\t\tuint32_t *mark = (uint32_t *)deco->decoration;\n+\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", *mark,\n \t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n \t\t\t e = 1;\n \t\t\t break;\n \t\t\t}\n \t\t}\n-\t\tdeco++;\n \t}\n \n \te |= ferror(f);\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..5a0747e 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)\n \treturn hash % n;\n }\n \n-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n+static int insert_decoration(struct decoration *n, const struct object *base,\n+\t\t\t const void *decoration, void *old)\n {\n \tint size = n->size;\n-\tstruct object_decoration *hash = n->hash;\n+\tunsigned long width = decoration_width(n);\n \tunsigned int j = hash_obj(base, size);\n \n-\twhile (hash[j].base) {\n-\t\tif (hash[j].base == base) {\n-\t\t\tvoid *old = hash[j].decoration;\n-\t\t\thash[j].decoration = decoration;\n-\t\t\treturn old;\n+\twhile (1) {\n+\t\tstruct object_decoration *e = decoration_slot(n, j);\n+\t\tif (!e->base) {\n+\t\t\te->base = base;\n+\t\t\tmemcpy(e->decoration, decoration, width);\n+\t\t\tn->nr++;\n+\t\t\treturn 0;\n+\t\t}\n+\t\tif (e->base == base) {\n+\t\t\tif (old)\n+\t\t\t\tmemcpy(old, e->decoration, width);\n+\t\t\tmemcpy(e->decoration, decoration, width);\n+\t\t\treturn 1;\n \t\t}\n \t\tif (++j >= size)\n \t\t\tj = 0;\n \t}\n-\thash[j].base = base;\n-\thash[j].decoration = decoration;\n-\tn->nr++;\n-\treturn NULL;\n }\n \n static void grow_decoration(struct decoration *n)\n {\n \tint i;\n \tint old_size = n->size;\n-\tstruct object_decoration *old_hash = n->hash;\n+\tunsigned char *old_hash = n->hash;\n \n \tn->size = (old_size + 1000) * 3 / 2;\n-\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n+\tn->hash = xcalloc(n->size, decoration_stride(n));\n \tn->nr = 0;\n \n \tfor (i = 0; i < old_size; i++) {\n-\t\tconst struct object *base = old_hash[i].base;\n-\t\tvoid *decoration = old_hash[i].decoration;\n-\n-\t\tif (!base)\n-\t\t\tcontinue;\n-\t\tinsert_decoration(n, base, decoration);\n+\t\tstruct object_decoration *e =\n+\t\t\t(struct object_decoration *)\n+\t\t\t(old_hash + i * decoration_stride(n));\n+\t\tif (e->base)\n+\t\t\tinsert_decoration(n, e->base, e->decoration, NULL);\n \t}\n \tfree(old_hash);\n }\n@@ -60,15 +64,35 @@ static void grow_decoration(struct decoration *n)\n void *add_decoration(struct decoration *n, const struct object *obj,\n \t\tvoid *decoration)\n {\n-\tint nr = n->nr + 1;\n+\tvoid *old = NULL;\n+\tadd_decoration_value(n, obj, &decoration, &old);\n+\treturn old;\n+}\n \n+int add_decoration_value(struct decoration *n,\n+\t\t\t const struct object *obj,\n+\t\t\t const void *decoration,\n+\t\t\t void *old)\n+{\n+\tint nr = n->nr + 1;\n \tif (nr > n->size * 2 / 3)\n \t\tgrow_decoration(n);\n-\treturn insert_decoration(n, obj, decoration);\n+\treturn insert_decoration(n, obj, decoration, old);\n }\n \n /* Lookup a decoration pointer */\n-void *lookup_decoration(struct decoration *n, const struct object *obj)\n+void *lookup_decoration(const struct decoration *n, const struct object *obj)\n+{\n+\tvoid **v;\n+\n+\tv = lookup_decoration_value(n, obj);\n+\tif (!v)\n+\t\treturn NULL;\n+\treturn *v;\n+}\n+\n+void *lookup_decoration_value(const struct decoration *n,\n+\t\t\t const struct object *obj)\n {\n \tunsigned int j;\n \n@@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)\n \t\treturn NULL;\n \tj = hash_obj(obj, n->size);\n \tfor (;;) {\n-\t\tstruct object_decoration *ref = n->hash + j;\n+\t\tstruct object_decoration *ref = decoration_slot(n, j);\n \t\tif (ref->base == obj)\n \t\t\treturn ref->decoration;\n \t\tif (!ref->base)\ndiff --git a/decorate.h b/decorate.h\nindex e732804..c0e8e3f 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -3,16 +3,47 @@\n \n struct object_decoration {\n \tconst struct object *base;\n-\tvoid *decoration;\n+\tunsigned char decoration[FLEX_ARRAY];\n };\n \n struct decoration {\n \tconst char *name;\n+\t/* width of data we're holding; must be set before adding */\n+\tconst unsigned int width;\n \tunsigned int size, nr;\n-\tstruct object_decoration *hash;\n+\t/*\n+\t * The hash contains object_decoration structs, but we don't know their\n+\t * size until runtime. So we store is as a pointer to characters to\n+\t * make pointer arithmetic easier.\n+\t */\n+\tunsigned char *hash;\n };\n \n extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);\n-extern void *lookup_decoration(struct decoration *n, const struct object *obj);\n+extern void *lookup_decoration(const struct decoration *n, const struct object *obj);\n+\n+extern int add_decoration_value(struct decoration *n,\n+\t\t\t\tconst struct object *obj,\n+\t\t\t\tconst void *decoration,\n+\t\t\t\tvoid *old);\n+extern void *lookup_decoration_value(const struct decoration *n,\n+\t\t\t\t const struct object *obj);\n+\n+static inline unsigned long decoration_width(const struct decoration *n)\n+{\n+\treturn n->width ? n->width : sizeof(void *);\n+}\n+\n+static inline unsigned long decoration_stride(const struct decoration *n)\n+{\n+\treturn sizeof(struct object_decoration) + decoration_width(n);\n+}\n+\n+static inline struct object_decoration *decoration_slot(const struct decoration *n,\n+\t\t\t\t\t\t\tunsigned i)\n+{\n+\treturn (struct object_decoration *)\n+\t\t(n->hash + (i * decoration_stride(n)));\n+}\n \n #endif\n-- \n1.7.6.37.g989c6\n"},{"id":"171209","messageId":"20110713070405.GB18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:04:05Z","receivedAt":"2011-07-13T07:04:05Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There is sometimes a need to cache some information about an\nobject or set of objects persistently across git\ninvocations. The notes-cache interface can be used for this,\nbut it is very heavyweight and slow for storing small\nvalues.\n\nThis patch introduces a new API, metadata-cache, which\nstores a mapping of objects to values in a concise and\nefficient form. See the added API documentation for details.\n\nSigned-off-by: Jeff King \n---\nMany changes here:\n\n - name changed to metadata-cache\n\n - cache files have an actual header; I doubt they'll need to change\n much, but it's a lot nicer to have an actual version number to make\n sure it's valid\n\n - cache files have a 20-byte slot for a validity hash. See patch 5/6\n for an example of use.\n\n - the data width is stored in only one place, and is const; this gives\n us language support for code accidentally tweaking the width at\n run-time\n\n - initialization is now done by static initializer, and we lazily open\n the disk cache when requested. This is necessary because of the\n previous point, but it also makes client code simpler.\n\n - cached entries are automatically written out on program exit.\n Together with the above point, this makes client code very simple\n and natural. You just declare a static cache object, and then lookup\n and add to it as appropriate.\n\n Documentation/technical/api-decorate.txt | 3 +\n Documentation/technical/api-metadata-cache.txt | 130 +++++++++\n Makefile | 2 +\n metadata-cache.c | 337 ++++++++++++++++++++++++\n metadata-cache.h | 40 +++\n 5 files changed, 512 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-metadata-cache.txt\n create mode 100644 metadata-cache.c\n create mode 100644 metadata-cache.h\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex b048b28..c761b45 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -13,6 +13,9 @@ could, for example, map objects into 32-bit integers. For ease of use,\n functions are provided for storing the values of arbitrary pointers,\n which can point to strings or structs.\n \n+Note that the decorate API only stores the mapping in memory. See the\n+metadata-cache API for persistent storage.\n+\n Data Structures\n ---------------\n \ndiff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt\nnew file mode 100644\nindex 0000000..192a868\n--- /dev/null\n+++ b/Documentation/technical/api-metadata-cache.txt\n@@ -0,0 +1,130 @@\n+Metadata Cache API\n+================\n+\n+The metadata cache API is meant to store a cache of per-object values.\n+The aim is for robustness, speed, and simplicity. The stored data must\n+be of a fixed size, and the only operations allowed are insertion and\n+retrieval with a struct object as the key.\n+\n+This API is similar to the decorate API, but provides persistence of\n+values across multiple invocations. It is also similar to the\n+notes-cache API, but is much lighter weight and suitable for storing\n+small values. If you are storing large, arbitrary data, consider using\n+notes-cache.\n+\n+\n+Storage\n+-------\n+\n+Values are stored both on-disk and in-memory. Newly added values are\n+initially stored in a hash table in memory, and written to disk\n+automatically on program exit.\n+\n+The disk storage consists of a single file per cache, located in the\n+`$GIT_DIR/cache` directory. See \"File Format\" below.\n+\n+When the cache is written to disk, the contents of the in-memory data\n+and the disk data are merged, with in-memory values taking precedence\n+over disk values. The data is written to a temporary file and atomically\n+renamed into the new cache file. Thus there is no lock contention\n+between competing processes on either reading or writing (though one\n+process's updates may be lost).\n+\n+\n+File Format\n+-----------\n+\n+Cache files begin with a 32-byte header, consisting of:\n+\n+ - a 4-byte magic token, {'M', 'T', 'A', 'C' }.\n+\n+ - a 32-bit unsigned integer in network byte-order, indicating the\n+ file format version; this document describes version 1.\n+\n+ - a 32-bit unsigned integer in network byte-order, indicating the\n+ width in bytes of single stored data value.\n+\n+ - a 20-byte sequence indicating the \"validity\" of the cache; the\n+ exact meaning of this value is specific to the type of cache. See\n+ the section on \"Validity\" below.\n+\n+After the header, the file contains a sequence of key-value pairs, with\n+no delimiters. The \"key\" of each pair is a 20-byte binary sha1. The\n+value is a sequence of bytes of length `W`, where `W` is the width\n+specified in the header.\n+\n+\n+Cache Validity\n+--------------\n+\n+The contents of a cache file may be valid only under a specific set of\n+circumstances. The file header contains a 20-byte validity token which\n+can be checked to ensure that the cache data is still valid. The data\n+that goes into each token is specific to the type of cache. For example,\n+a cache that summarizes information on the history graph would be valid\n+only under a specific set of grafts and replace refs.\n+\n+\n+Speed\n+-----\n+\n+Lookup in the cache requires `O(lg(n))` hash comparisons (via binary\n+search of the disk contents, or the in-memory hash table).\n+\n+Insertion into the cache is amortized `O(1)` via the hash table. Writing\n+the cache to disk entails `O(n*lg(n) + m)` hash comparisons, where `m`\n+is the number of existing disk entries and `n` is the number of newly\n+added entries.\n+\n+\n+Data Structures\n+---------------\n+\n+`struct metadata_cache`::\n+\n+\tThis structure represents a single metadata cache (i.e., mapping\n+\teach object to a single fixed-size value). The cache should be\n+\tallocated in static storage and initialized using the\n+\t`METADATA_CACHE_INIT` macro. The lookup code will lazily open the\n+\ton-disk cache as necessary, and any values written by\n+\t`metadata_cache_add` will be automatically written to disk at\n+\tprogram exit.\n++\n+\tThe structure should be considered opaque by calling code.\n+\n+\n+Functions\n+---------\n+\n+`METADATA_CACHE_INIT`::\n+\n+\tStatic initializer for a metadata cache. The `name` parameter\n+\tspecifies a human-readable name which will be used for storage\n+\tin `$GIT_DIR/cache/$name`. The `width` parameter specifies the\n+\tsize, in units of `char`, of the data to be stored (e.g., use\n+\t`sizeof(uint32_t)` to store 32-bit integers). The `validity`\n+\tparameter is either NULL or a pointer to a function providing a\n+\t20-byte validity sha1.\n+\n+`metadata_cache_lookup`::\n+\n+\tRetrieve a value from the object cache. A void pointer to the\n+\tstored value will be returned, or `NULL` if there is no value.\n+\n+`metadata_cache_add`::\n+\n+\tStore a value in the object cache. The value pointer should\n+\tpoint to exactly `width` bytes of data.\n+\n+`metadata_cache_lookup_uint32`::\n+\n+\tConvenience wrapper for retrieving unsigned 32-bit integers. The\n+\tvalue will be returned via the `value` pointer. The return value\n+\tis `0` if a value was found, or negative otherwise (in which\n+\tcase the contents of `value` will be unchanged).\n+\n+`metadata_cache_add_uint32`::\n+\n+\tConvenience wrapper for storing unsigned 32-bit integers. Note\n+\tthat integers are stored on disk in network-byte order, so it is\n+\tsafe to access caches from any architecture.\ndiff --git a/Makefile b/Makefile\nindex f8c72e1..d0b1376 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -532,6 +532,7 @@ LIB_H += log-tree.h\n LIB_H += mailmap.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n+LIB_H += metadata-cache.h\n LIB_H += notes.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n@@ -624,6 +625,7 @@ LIB_OBJS += mailmap.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n+LIB_OBJS += metadata-cache.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/metadata-cache.c b/metadata-cache.c\nnew file mode 100644\nindex 0000000..e2e5ff8\n--- /dev/null\n+++ b/metadata-cache.c\n@@ -0,0 +1,337 @@\n+#include \"cache.h\"\n+#include \"metadata-cache.h\"\n+#include \"sha1-lookup.h\"\n+#include \"object.h\"\n+\n+static struct metadata_cache **autowrite;\n+static int autowrite_nr;\n+static int autowrite_alloc;\n+\n+static int installed_atexit_autowriter;\n+\n+static int record_size(const struct metadata_cache *c)\n+{\n+\t/* a record is a 20-byte sha1 plus the width of the value */\n+\treturn c->mem.width + 20;\n+}\n+\n+static const char *metadata_cache_path(const char *name)\n+{\n+\treturn git_path(\"cache/%s\", name);\n+}\n+\n+static void close_disk_cache(struct metadata_cache *c)\n+{\n+\tif (c->map) {\n+\t\tmunmap(c->map, c->maplen);\n+\t\tc->map = NULL;\n+\t\tc->maplen = 0;\n+\t\tc->disk_entries = 0;\n+\t\tc->disk_nr = 0;\n+\t}\n+\n+\tif (c->fd >= 0) {\n+\t\tclose(c->fd);\n+\t\tc->fd = -1;\n+\t}\n+}\n+\n+static unsigned char *check_cache_header(struct metadata_cache *c,\n+\t\t\t\t\t const char *path)\n+{\n+\tunsigned char *p = c->map;\n+\tunsigned char validity[20];\n+\tuint32_t version;\n+\tuint32_t width;\n+\n+\tif (c->maplen < 32) {\n+\t\twarning(\"cache file '%s' is short (%lu bytes)\",\n+\t\t\tpath, c->maplen);\n+\t\treturn NULL;\n+\t}\n+\n+\tif (memcmp(p, \"MTAC\", 4)) {\n+\t\twarning(\"cache file '%s' has invalid magic: %c%c%c%c\",\n+\t\t\tpath, p[0], p[1], p[2], p[3]);\n+\t\treturn NULL;\n+\t}\n+\tp += 4;\n+\n+\tversion = ntohl(*(uint32_t *)p);\n+\tif (version != 1) {\n+\t\twarning(\"cache file '%s' has unknown version: %\"PRIu32,\n+\t\t\tpath, version);\n+\t\treturn NULL;\n+\t}\n+\tp += 4;\n+\n+\twidth = ntohl(*(uint32_t *)p);\n+\tif (width != c->mem.width) {\n+\t\twarning(\"cache file '%s' does not have desired width: \"\n+\t\t\t\"(%\"PRIu32\" != %u\", path, width, c->mem.width);\n+\t\treturn NULL;\n+\t}\n+\tp += 4;\n+\n+\tif (c->validity_fun) {\n+\t\tc->validity_fun(validity);\n+\t\tif (hashcmp(validity, p))\n+\t\t\treturn NULL;\n+\t}\n+\telse {\n+\t\tif (!is_null_sha1(p))\n+\t\t\treturn NULL;\n+\t}\n+\tp += 20;\n+\n+\treturn p;\n+}\n+\n+static void open_disk_cache(struct metadata_cache *c, const char *path)\n+{\n+\tstruct stat sb;\n+\n+\tc->fd = open(path, O_RDONLY);\n+\tif (c->fd < 0)\n+\t\treturn;\n+\n+\tif (fstat(c->fd, &sb) < 0) {\n+\t\tclose_disk_cache(c);\n+\t\treturn;\n+\t}\n+\n+\tc->maplen = sb.st_size;\n+\tc->map = xmmap(NULL, c->maplen, PROT_READ, MAP_PRIVATE, c->fd, 0);\n+\n+\tc->disk_entries = check_cache_header(c, path);\n+\tif (!c->disk_entries) {\n+\t\tclose_disk_cache(c);\n+\t\treturn;\n+\t}\n+\tc->disk_nr = (sb.st_size - (c->disk_entries - c->map)) / record_size(c);\n+}\n+\n+static unsigned char *flatten_mem_entries(struct metadata_cache *c)\n+{\n+\tint i;\n+\tunsigned char *ret;\n+\tint nr;\n+\n+\tret = xmalloc(c->mem.nr * record_size(c));\n+\tnr = 0;\n+\tfor (i = 0; i < c->mem.size; i++) {\n+\t\tstruct object_decoration *e = decoration_slot(&c->mem, i);\n+\t\tunsigned char *out;\n+\n+\t\tif (!e->base)\n+\t\t\tcontinue;\n+\n+\t\tif (nr == c->mem.nr)\n+\t\t\tdie(\"BUG: decorate hash contained extra values\");\n+\n+\t\tout = ret + (nr * record_size(c));\n+\t\thashcpy(out, e->base->sha1);\n+\t\tout += 20;\n+\t\tmemcpy(out, e->decoration, c->mem.width);\n+\t\tnr++;\n+\t}\n+\n+\treturn ret;\n+}\n+\n+static int void_hashcmp(const void *a, const void *b)\n+{\n+\treturn hashcmp(a, b);\n+}\n+\n+static int write_header(int fd, struct metadata_cache *c)\n+{\n+\tuint32_t width;\n+\tunsigned char validity[20];\n+\n+\tif (write_in_full(fd, \"MTAC\\x00\\x00\\x00\\x01\", 8) < 0)\n+\t\treturn -1;\n+\n+\twidth = htonl(c->mem.width);\n+\tif (write_in_full(fd, &width, 4) < 0)\n+\t\treturn -1;\n+\n+\tif (c->validity_fun)\n+\t\tc->validity_fun(validity);\n+\telse\n+\t\thashcpy(validity, null_sha1);\n+\tif (write_in_full(fd, validity, 20) < 0)\n+\t\treturn -1;\n+\n+\treturn 0;\n+}\n+\n+static int merge_entries(int fd, int size,\n+\t\t\t const unsigned char *left, unsigned nr_left,\n+\t\t\t const unsigned char *right, unsigned nr_right)\n+{\n+#define ADVANCE(name) \\\n+\tdo { \\\n+\t\tname += size; \\\n+\t\tnr_##name--; \\\n+\t} while(0)\n+#define WRITE_ENTRY(name) \\\n+\tdo { \\\n+\t\tif (write_in_full(fd, name, size) < 0) \\\n+\t\t\treturn -1; \\\n+\t\tADVANCE(name); \\\n+\t} while(0)\n+\n+\twhile (nr_left && nr_right) {\n+\t\tint cmp = hashcmp(left, right);\n+\n+\t\t/* skip duplicates, preferring left to right */\n+\t\tif (cmp == 0)\n+\t\t\tADVANCE(right);\n+\t\telse if (cmp < 0)\n+\t\t\tWRITE_ENTRY(left);\n+\t\telse\n+\t\t\tWRITE_ENTRY(right);\n+\t}\n+\twhile (nr_left)\n+\t\tWRITE_ENTRY(left);\n+\twhile (nr_right)\n+\t\tWRITE_ENTRY(right);\n+\n+#undef WRITE_ENTRY\n+#undef ADVANCE\n+\n+\treturn 0;\n+}\n+\n+static int metadata_cache_write(struct metadata_cache *c, const char *name)\n+{\n+\tconst char *path = metadata_cache_path(name);\n+\tstruct strbuf tempfile = STRBUF_INIT;\n+\tint fd;\n+\tunsigned char *mem_entries;\n+\n+\tif (!c->mem.nr)\n+\t\treturn 0;\n+\n+\tstrbuf_addf(&tempfile, \"%s.XXXXXX\", path);\n+\tif (safe_create_leading_directories(tempfile.buf) < 0 ||\n+\t (fd = git_mkstemp_mode(tempfile.buf, 0755)) < 0) {\n+\t\tstrbuf_release(&tempfile);\n+\t\treturn -1;\n+\t}\n+\n+\tif (write_header(fd, c) < 0)\n+\t\tgoto fail;\n+\n+\tmem_entries = flatten_mem_entries(c);\n+\tqsort(mem_entries, c->mem.nr, record_size(c), void_hashcmp);\n+\n+\tif (merge_entries(fd, record_size(c),\n+\t\t\t mem_entries, c->mem.nr,\n+\t\t\t c->disk_entries, c->disk_nr) < 0) {\n+\t\tfree(mem_entries);\n+\t\tgoto fail;\n+\t}\n+\tfree(mem_entries);\n+\n+\tif (close(fd) < 0)\n+\t\tgoto fail;\n+\tif (rename(tempfile.buf, path) < 0)\n+\t\tgoto fail;\n+\n+\tstrbuf_release(&tempfile);\n+\treturn 0;\n+\n+fail:\n+\tclose(fd);\n+\tunlink(tempfile.buf);\n+\tstrbuf_release(&tempfile);\n+\treturn -1;\n+}\n+static void autowrite_metadata_caches(void)\n+{\n+\tint i;\n+\tfor (i = 0; i < autowrite_nr; i++)\n+\t\tmetadata_cache_write(autowrite[i], autowrite[i]->mem.name);\n+}\n+\n+static void metadata_cache_init(struct metadata_cache *c)\n+{\n+\tif (c->initialized)\n+\t\treturn;\n+\n+\topen_disk_cache(c, metadata_cache_path(c->mem.name));\n+\n+\tALLOC_GROW(autowrite, autowrite_nr+1, autowrite_alloc);\n+\tautowrite[autowrite_nr++] = c;\n+\tif (!installed_atexit_autowriter) {\n+\t\tatexit(autowrite_metadata_caches);\n+\t\tinstalled_atexit_autowriter = 1;\n+\t}\n+\n+\tc->initialized = 1;\n+}\n+\n+static void *lookup_disk(struct metadata_cache *c,\n+\t\t\t const struct object *obj)\n+{\n+\tint pos;\n+\n+\tpos = sha1_entry_pos(c->disk_entries, record_size(c), 0,\n+\t\t\t 0, c->disk_nr, c->disk_nr, obj->sha1);\n+\tif (pos < 0)\n+\t\treturn NULL;\n+\n+\treturn c->disk_entries + (pos * record_size(c)) + 20;\n+}\n+\n+const void *metadata_cache_lookup(struct metadata_cache *c,\n+\t\t\t\t const struct object *obj)\n+{\n+\tvoid *r;\n+\n+\tmetadata_cache_init(c);\n+\n+\tr = lookup_decoration_value(&c->mem, obj);\n+\tif (!r)\n+\t\tr = lookup_disk(c, obj);\n+\treturn r;\n+}\n+\n+void metadata_cache_add(struct metadata_cache *c, const struct object *obj,\n+\t\t\tconst void *value)\n+{\n+\tmetadata_cache_init(c);\n+\tadd_decoration_value(&c->mem, obj, value, NULL);\n+}\n+\n+int metadata_cache_lookup_uint32(struct metadata_cache *c,\n+\t\t\t\t const struct object *obj,\n+\t\t\t\t uint32_t *value)\n+{\n+\tconst uint32_t *out;\n+\n+\tif (record_size(c) != 24)\n+\t\tdie(\"BUG: size mismatch in object cache lookup (%d != 24)\",\n+\t\t record_size(c));\n+\n+\tout = metadata_cache_lookup(c, obj);\n+\tif (!out)\n+\t\treturn -1;\n+\n+\t*value = ntohl(*out);\n+\treturn 0;\n+}\n+\n+void metadata_cache_add_uint32(struct metadata_cache *c,\n+\t\t\t const struct object *obj,\n+\t\t\t uint32_t value)\n+{\n+\tif (record_size(c) != 24)\n+\t\tdie(\"BUG: size mismatch in object cache add (%d != 24)\",\n+\t\t record_size(c));\n+\n+\tvalue = htonl(value);\n+\tmetadata_cache_add(c, obj, &value);\n+}\ndiff --git a/metadata-cache.h b/metadata-cache.h\nnew file mode 100644\nindex 0000000..5b761e1\n--- /dev/null\n+++ b/metadata-cache.h\n@@ -0,0 +1,40 @@\n+#ifndef METADATA_CACHE_H\n+#define METADATA_CACHE_H\n+\n+#include \"decorate.h\"\n+\n+typedef void (*metadata_cache_validity_fun)(unsigned char out[20]);\n+\n+struct metadata_cache {\n+\tmetadata_cache_validity_fun validity_fun;\n+\n+\t/* in memory entries */\n+\tstruct decoration mem;\n+\n+\t/* mmap'd disk entries */\n+\tint fd;\n+\tunsigned char *map;\n+\tunsigned long maplen;\n+\tunsigned char *disk_entries;\n+\tint disk_nr;\n+\n+\tint initialized;\n+};\n+\n+#define METADATA_CACHE_INIT(name, width, validity) \\\n+\t{ validity, { (name), (width) } }\n+\n+const void *metadata_cache_lookup(struct metadata_cache *,\n+\t\t\t\t const struct object *);\n+void metadata_cache_add(struct metadata_cache *, const struct object *,\n+\t\t\tconst void *value);\n+\n+/* Convenience wrappers around metadata_cache_{lookup,add} */\n+int metadata_cache_lookup_uint32(struct metadata_cache *,\n+\t\t\t\t const struct object *,\n+\t\t\t\t uint32_t *value);\n+void metadata_cache_add_uint32(struct metadata_cache *,\n+\t\t\t const struct object *,\n+\t\t\t uint32_t value);\n+\n+#endif /* METADATA_CACHE_H */\n-- \n1.7.6.37.g989c6\n"},{"id":"171208","messageId":"20110713070517.GC18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 3/6] commit: add commit_generation function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:05:17Z","receivedAt":"2011-07-13T07:05:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A commit's generation is its height in the history graph, as\nmeasured from the farthest root. It is defined as:\n\n - If the commit has no parents, then its generation is 0.\n\n - Otherwise, its generation is 1 more than the maximum of\n its parents generations.\n\nThe following diagram shows a sample history with\ngenerations:\n\n A(0)--B(1)--C(2)------G(5)--H(6)\n \\ /\n D(2)--E(3)--F(4)\n\nNote that C and D have the same generation, as they are both\nchildren of B. Note also that the merge commit G's\ngeneration is 5, not 3, as we take the maximum of its\nparents' generations.\n\nGeneration numbers can be useful for bounding traversals.\nFor example, if we have two commits with generations 500 and\n600, we know that the second cannot be an ancestor of the\nfirst. The first could be an ancestor of the second, but we\ncan't know unless we traverse the history graph. However,\nwhen walking backwards from the \"600\" commit, once we reach\ngeneration \"499\", we know that the \"500\" commit cannot be an\nancestor of the \"499\" commit, and we can stop the traversal\nwithout even looking at the earlier parts of the history.\n\nWe already do something similar with commit timestamps in\nmany traversals. However, timestamps are somewhat\nuntrustworthy, as we have to deal with clock skew and with\nimports from buggy systems.\n\nGeneration numbers are easy to calculate recursively, though\nyou have to go to the roots to do so. This patch calculates\nand stores them in a persistent cache. It uses a simple\nrecursive algorithm; you could probably drop the recursion\nby topologically sorting a list of all commits and filling\nin generation numbers left to right. But the recursive\ndefinition coupled with the cache make it very cheap to\ncalculate generation numbers for new commits at the tip of\nhistory (you only have to traverse back to the last cached\nparents).\n\nWe could also store generation numbers in the commit header\ndirectly. These would be faster to look at than an external\ncache (they would be on par speed-wise with commit\ntimestamps). But there are a few reasons not to:\n\n 1. The reason to avoid commit timestamps is that they are\n unreliable. Generation numbers would probably be more\n reliable, but they are still redundant with the actual\n graph structure represented by the parent pointers, and\n can therefore be out of sync with the parent\n information. By calculating them ourselves, we know\n they are correct.\n\n 2. With grafts and replacement objects, the graph\n structure (and thus the generation numbers) can be\n changed. So the generation number, while immutable for\n a given commit object, can be changed when we \"lie\"\n about the graph structure via these mechanisms. Being\n able to simply clear the cache when these things are\n changed is helpful.\n\n 3. There's a lot of existing git history without\n generation headers. So we'd still need to have the same\n cache to handle those cases.\n\n 4. It generally pollutes the header with redundant\n information, which we try to avoid. Putting it in the\n commit header is purely a speedup, and it seems we can\n get similar performance with a generation cache.\n\nSigned-off-by: Jeff King \n---\nSame as before, but rebased onto the new metadata-cache interface.\n\n commit.c | 36 ++++++++++++++++++++++++++++++++++++\n commit.h | 2 ++\n 2 files changed, 38 insertions(+), 0 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac337c7..fb37aa0 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"notes.h\"\n+#include \"metadata-cache.h\"\n \n int save_commit_buffer = 1;\n \n@@ -878,3 +879,38 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tstrbuf_release(&buffer);\n \treturn result;\n }\n+\n+static struct metadata_cache generations =\n+\tMETADATA_CACHE_INIT(\"generations\", sizeof(uint32_t), NULL);\n+\n+static unsigned long commit_generation_recurse(struct commit *c)\n+{\n+\tstruct commit_list *p;\n+\tuint32_t r;\n+\n+\tif (!metadata_cache_lookup_uint32(&generations, &c->object, &r))\n+\t\treturn r;\n+\n+\tif (parse_commit(c) < 0)\n+\t\tdie(\"unable to parse commit: %s\", sha1_to_hex(c->object.sha1));\n+\n+\tif (!c->parents)\n+\t\treturn 0;\n+\n+\tr = 0;\n+\tfor (p = c->parents; p; p = p->next) {\n+\t\tunsigned long pgen = commit_generation_recurse(p->item);\n+\t\tif (pgen > r)\n+\t\t\tr = pgen;\n+\t}\n+\tr++;\n+\n+\tmetadata_cache_add_uint32(&generations, &c->object, r);\n+\treturn r;\n+}\n+\n+unsigned long commit_generation(const struct commit *commit)\n+{\n+\t/* drop const because we may call parse_commit */\n+\treturn commit_generation_recurse((struct commit *)commit);\n+}\ndiff --git a/commit.h b/commit.h\nindex a2d571b..bff6b36 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -176,4 +176,6 @@ extern int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author);\n \n+unsigned long commit_generation(const struct commit *commit);\n+\n #endif /* COMMIT_H */\n-- \n1.7.6.37.g989c6\n"},{"id":"171210","messageId":"20110713070552.GD18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 4/6] pretty: support %G to show the generation number of a commit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:05:52Z","receivedAt":"2011-07-13T07:05:52Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This might be useful for external programs doing topological\nsorting or other graph analysis. It's also handy for testing\nthe generation calculation code.\n\nSigned-off-by: Jeff King \n---\nThis now includes some basic tests.\n\n Documentation/pretty-formats.txt | 1 +\n pretty.c | 3 ++\n t/t6070-commit-generations.sh | 41 ++++++++++++++++++++++++++++++++++++++\n 3 files changed, 45 insertions(+), 0 deletions(-)\n create mode 100755 t/t6070-commit-generations.sh\n\ndiff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt\nindex 561cc9f..c58ab52 100644\n--- a/Documentation/pretty-formats.txt\n+++ b/Documentation/pretty-formats.txt\n@@ -133,6 +133,7 @@ The placeholders are:\n - '%gD': reflog selector, e.g., `refs/stash@\\{1\\}`\n - '%gd': shortened reflog selector, e.g., `stash@\\{1\\}`\n - '%gs': reflog subject\n+- '%G': generation number (i.e., distance of path to farthest root ancestor)\n - '%Cred': switch color to red\n - '%Cgreen': switch color to green\n - '%Cblue': switch color to blue\ndiff --git a/pretty.c b/pretty.c\nindex f45eb54..8f1b321 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -965,6 +965,9 @@ static size_t format_commit_one(struct strbuf *sb, const char *placeholder,\n \t\t\treturn 2;\n \t\t}\n \t\treturn 0;\t/* unknown %g placeholder */\n+\tcase 'G':\n+\t\tstrbuf_addf(sb, \"%lu\", commit_generation(commit));\n+\t\treturn 1;\n \tcase 'N':\n \t\tif (c->pretty_ctx->show_notes) {\n \t\t\tformat_display_notes(commit->object.sha1, sb,\ndiff --git a/t/t6070-commit-generations.sh b/t/t6070-commit-generations.sh\nnew file mode 100755\nindex 0000000..3e0f2ad\n--- /dev/null\n+++ b/t/t6070-commit-generations.sh\n@@ -0,0 +1,41 @@\n+#!/bin/sh\n+\n+test_description='calculate and cache commit generations'\n+. ./test-lib.sh\n+\n+test_expect_success 'setup history' '\n+\ttest_commit one &&\n+\ttest_commit two &&\n+\ttest_commit three &&\n+\ttest_commit four &&\n+\tgit checkout -b other two &&\n+\ttest_commit five &&\n+\tgit checkout master &&\n+\tgit merge other &&\n+\ttest_commit six\n+'\n+\n+cat >expect <<'EOF'\n+5 six\n+4 Merge branch 'other'\n+2 five\n+3 four\n+2 three\n+1 two\n+0 one\n+EOF\n+test_expect_success 'check commit generations' '\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'cache file was created' '\n+\ttest_path_is_file .git/cache/generations\n+'\n+\n+test_expect_success 'cached values are the same' '\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.7.6.37.g989c6\n"},{"id":"171211","messageId":"20110713070616.GE18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 5/6] check commit generation cache validity against grafts","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:06:16Z","receivedAt":"2011-07-13T07:06:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Some caches, like the commit generation cache, rely on the\nshape of the history graph to be accurate. Because commits\nare immutable, that shape should never change. However, our\nview onto the graph is modified by grafts and replace refs;\nif these change, the values in our cache are invalid and\nshould be regenerated.\n\nWe take a pretty heavy-handed approach, and simply throw out\nand regenerate the whole cache when either grafts or replace\nrefs change. In theory we could be slightly more efficient\nby comparing the view under which our cache was generated to\nthe current one. But doing that is complex, and requires\nstoring the old state.\n\nInstead, we summarize all of the grafts and replace objects\nwith a single 20-byte sha1. Because the grafts and replace\nrefs don't tend to change very often, this is simple and\nefficient enough.\n\nThe actual contents of what we stir into the sha1 are not\nimportant, as long as:\n\n 1. A given state is consistently represented across runs.\n\n 2. Distinct states generate distinct input to the sha1\n function.\n\nSigned-off-by: Jeff King \n---\nNew in this version of the series.\n\n Documentation/technical/api-metadata-cache.txt | 7 ++++\n cache.h | 1 +\n commit.c | 24 +++++++++++++++-\n commit.h | 2 +\n metadata-cache.c | 16 ++++++++++\n metadata-cache.h | 3 ++\n replace_object.c | 15 ++++++++++\n t/t6070-commit-generations.sh | 36 ++++++++++++++++++++++++\n 8 files changed, 103 insertions(+), 1 deletions(-)\n\ndiff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt\nindex 192a868..f43b1ba 100644\n--- a/Documentation/technical/api-metadata-cache.txt\n+++ b/Documentation/technical/api-metadata-cache.txt\n@@ -128,3 +128,10 @@ Functions\n \tConvenience wrapper for storing unsigned 32-bit integers. Note\n \tthat integers are stored on disk in network-byte order, so it is\n \tsafe to access caches from any architecture.\n+\n+`metadata_graph_validity`::\n+\n+\tThis function is intended to be used with `METADATA_CACHE_INIT`\n+\tas a validity function. It returns a SHA1 summarizing the\n+\tcurrent state of any commit grafts and replace objects that\n+\twould affect the shape of the history graph.\ndiff --git a/cache.h b/cache.h\nindex bc9e5eb..50e8a1c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -745,6 +745,7 @@ static inline const unsigned char *lookup_replace_object(const unsigned char *sh\n \t\treturn sha1;\n \treturn do_lookup_replace_object(sha1);\n }\n+extern void replace_object_validity(git_SHA_CTX *ctx);\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern int sha1_object_info(const unsigned char *, unsigned long *);\ndiff --git a/commit.c b/commit.c\nindex fb37aa0..e72bb3e 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -246,6 +246,27 @@ int unregister_shallow(const unsigned char *sha1)\n \treturn 0;\n }\n \n+void commit_graft_validity(git_SHA_CTX *ctx)\n+{\n+\tint i;\n+\n+\tprepare_commit_graft();\n+\n+\tfor (i = 0; i < commit_graft_nr; i++) {\n+\t\tconst struct commit_graft *c = commit_graft[i];\n+\t\tgit_SHA1_Update(ctx, c->sha1, 20);\n+\t\tif (c->nr_parent < 0)\n+\t\t\tgit_SHA1_Update(ctx, \"shallow\", 7);\n+\t\telse {\n+\t\t\tuint32_t v = htonl(c->nr_parent);\n+\t\t\tint j;\n+\t\t\tgit_SHA1_Update(ctx, &v, sizeof(v));\n+\t\t\tfor (j = 0; j < c->nr_parent; j++)\n+\t\t\t\tgit_SHA1_Update(ctx, c->parent[j], 20);\n+\t\t}\n+\t}\n+}\n+\n int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size)\n {\n \tconst char *tail = buffer;\n@@ -881,7 +902,8 @@ int commit_tree(const char *msg, unsigned char *tree,\n }\n \n static struct metadata_cache generations =\n-\tMETADATA_CACHE_INIT(\"generations\", sizeof(uint32_t), NULL);\n+\tMETADATA_CACHE_INIT(\"generations\", sizeof(uint32_t),\n+\t\t\t metadata_graph_validity);\n \n static unsigned long commit_generation_recurse(struct commit *c)\n {\ndiff --git a/commit.h b/commit.h\nindex bff6b36..e6d144d 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -178,4 +178,6 @@ extern int commit_tree(const char *msg, unsigned char *tree,\n \n unsigned long commit_generation(const struct commit *commit);\n \n+void commit_graft_validity(git_SHA_CTX *ctx);\n+\n #endif /* COMMIT_H */\ndiff --git a/metadata-cache.c b/metadata-cache.c\nindex e2e5ff8..32d3c21 100644\n--- a/metadata-cache.c\n+++ b/metadata-cache.c\n@@ -2,6 +2,7 @@\n #include \"metadata-cache.h\"\n #include \"sha1-lookup.h\"\n #include \"object.h\"\n+#include \"commit.h\"\n \n static struct metadata_cache **autowrite;\n static int autowrite_nr;\n@@ -335,3 +336,18 @@ void metadata_cache_add_uint32(struct metadata_cache *c,\n \tvalue = htonl(value);\n \tmetadata_cache_add(c, obj, &value);\n }\n+\n+void metadata_graph_validity(unsigned char out[20])\n+{\n+\tgit_SHA_CTX ctx;\n+\n+\tgit_SHA1_Init(&ctx);\n+\n+\tgit_SHA1_Update(&ctx, \"grafts\", 6);\n+\tcommit_graft_validity(&ctx);\n+\n+\tgit_SHA1_Update(&ctx, \"replace\", 7);\n+\treplace_object_validity(&ctx);\n+\n+\tgit_SHA1_Final(out, &ctx);\n+}\ndiff --git a/metadata-cache.h b/metadata-cache.h\nindex 5b761e1..15484b5 100644\n--- a/metadata-cache.h\n+++ b/metadata-cache.h\n@@ -37,4 +37,7 @@ void metadata_cache_add_uint32(struct metadata_cache *,\n \t\t\t const struct object *,\n \t\t\t uint32_t value);\n \n+/* Common validity token functions */\n+void metadata_graph_validity(unsigned char out[20]);\n+\n #endif /* METADATA_CACHE_H */\ndiff --git a/replace_object.c b/replace_object.c\nindex d0b1548..9ec462b 100644\n--- a/replace_object.c\n+++ b/replace_object.c\n@@ -115,3 +115,18 @@ const unsigned char *do_lookup_replace_object(const unsigned char *sha1)\n \n \treturn cur;\n }\n+\n+void replace_object_validity(git_SHA_CTX *ctx)\n+{\n+\tint i;\n+\n+\tif (!read_replace_refs)\n+\t\treturn;\n+\n+\tprepare_replace_object();\n+\n+\tfor (i = 0; i < replace_object_nr; i++) {\n+\t\tgit_SHA1_Update(ctx, replace_object[i]->sha1[0], 20);\n+\t\tgit_SHA1_Update(ctx, replace_object[i]->sha1[1], 20);\n+\t}\n+}\ndiff --git a/t/t6070-commit-generations.sh b/t/t6070-commit-generations.sh\nindex 3e0f2ad..0aefd01 100755\n--- a/t/t6070-commit-generations.sh\n+++ b/t/t6070-commit-generations.sh\n@@ -38,4 +38,40 @@ test_expect_success 'cached values are the same' '\n \ttest_cmp expect actual\n '\n \n+cat >expect-grafted <<'EOF'\n+1 six\n+0 Merge branch 'other'\n+EOF\n+test_expect_success 'adding grafts invalidates generation cache' '\n+\tgit rev-parse six^ >.git/info/grafts &&\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect-grafted actual\n+'\n+\n+test_expect_success 'removing graft invalidates cache' '\n+\trm .git/info/grafts &&\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'setup replace ref' '\n+\tH=$(git rev-parse six^) &&\n+\tR=$(git cat-file commit $H |\n+\t sed /^parent/d |\n+\t git hash-object -t commit --stdin -w) &&\n+\tgit update-ref refs/replace/$H $R\n+'\n+\n+test_expect_success 'adding replace refs invalidates generation cache' '\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect-grafted actual\n+'\n+\n+test_expect_success 'cache respects replace-object settings' '\n+\tgit --no-replace-objects log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect actual &&\n+\tgit log --format=\"%G %s\" >actual &&\n+\ttest_cmp expect-grafted actual\n+'\n+\n test_done\n-- \n1.7.6.37.g989c6\n"},{"id":"171212","messageId":"20110713070644.GF18566@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"[RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:06:44Z","receivedAt":"2011-07-13T07:06:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When looking for commits that contain other commits (e.g.,\nvia \"git tag --contains\"), we can end up traversing useless\nportions of the graph. For example, if I am looking for a\ntag that contains a commit made last week, there is not much\npoint in traversing portions of the history graph made five\nyears ago.\n\nThis optimization can provide massive speedups. For example,\ndoing \"git tag --contains HEAD~1000\" in the linux-2.6\nrepository goes from:\n\n real 0m3.139s\n user 0m3.044s\n sys 0m0.092s\n\nto:\n\n real 0m0.035s\n user 0m0.028s\n sys 0m0.004s\n\nWe could use commit timestamps to know when we are going too\nfar back in history, but they are sometimes not trustworthy.\nExtreme clock skew on committers' machines (or bugs in\ncommit-generating software) mean that we may stop the\ntraversal too early when seeing commits skewed into the\npast.\n\nInstead, we use the calculated commit generation, which is a\npropery of the graph itself (but since we cache it, it's\nstill cheap to consult).\n\nSigned-off-by: Jeff King \n---\nSame as previous version.\n\n builtin/tag.c | 20 +++++++++++++++++---\n 1 files changed, 17 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 63bce6e..df6de47 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -40,7 +40,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n }\n \n static int contains_recurse(struct commit *candidate,\n-\t\t\t const struct commit_list *want)\n+\t\t\t const struct commit_list *want,\n+\t\t\t unsigned long cutoff)\n {\n \tstruct commit_list *p;\n \n@@ -57,9 +58,13 @@ static int contains_recurse(struct commit *candidate,\n \tif (parse_commit(candidate) < 0)\n \t\treturn 0;\n \n+\t/* stop searching if we go too far back in time */\n+\tif (commit_generation(candidate) < cutoff)\n+\t\treturn 0;\n+\n \t/* Otherwise recurse and mark ourselves for future traversals. */\n \tfor (p = candidate->parents; p; p = p->next) {\n-\t\tif (contains_recurse(p->item, want)) {\n+\t\tif (contains_recurse(p->item, want, cutoff)) {\n \t\t\tcandidate->object.flags |= TMP_MARK;\n \t\t\treturn 1;\n \t\t}\n@@ -70,7 +75,16 @@ static int contains_recurse(struct commit *candidate,\n \n static int contains(struct commit *candidate, const struct commit_list *want)\n {\n-\treturn contains_recurse(candidate, want);\n+\tunsigned long cutoff = ULONG_MAX;\n+\tconst struct commit_list *c;\n+\n+\tfor (c = want; c; c = c->next) {\n+\t\tunsigned long g = commit_generation(c->item);\n+\t\tif (g < cutoff)\n+\t\t\tcutoff = g;\n+\t}\n+\n+\treturn contains_recurse(candidate, want, cutoff);\n }\n \n static int show_reference(const char *refname, const unsigned char *sha1,\n-- \n1.7.6.37.g989c6\n"},{"id":"171215","messageId":"20110713072350.GA18614@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713070644.GF18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T07:23:50Z","receivedAt":"2011-07-13T07:23:50Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 03:06:44AM -0400, Jeff King wrote:\n\n> This optimization can provide massive speedups. For example,\n> doing \"git tag --contains HEAD~1000\" in the linux-2.6\n> repository goes from:\n> \n> real 0m3.139s\n> user 0m3.044s\n> sys 0m0.092s\n> \n> to:\n> \n> real 0m0.035s\n> user 0m0.028s\n> sys 0m0.004s\n\nI pulled this commit message from the original \"cutoff at timestamp\"\npatch, though I did update the timings for the new code. What it doesn't\nmention is that the first run will take something like 3.7 seconds, and\nthen subsequent ones will be way faster. I had mentioned that number\nelsewhere in the thread, but it should probably go here. I'll put it in\nthe next version.\n\nOne number I haven't mentioned elsewhere, though, is how expensive it is\nto add new commits to the cache. So here's an interesting timing:\n\n $ cd linux-2.6\n\n : slow, cache-generating time\n $ rm .git/cache/generations\n $ time git tag --contains HEAD\n real 0m3.795s\n user 0m3.420s\n sys 0m0.372s\n\n : fast, cached time\n $ time git tag --contains HEAD\n real 0m0.022s\n user 0m0.008s\n sys 0m0.012s\n\n : now what if we add one more commit?\n $ echo foo >>Makefile && git commit -a -m foo\n $ time git tag --contains HEAD\n real 0m0.271s\n user 0m0.020s\n sys 0m0.252s\n\nIt takes barely any time to get the generation of the new commit, but we\nspend .25 seconds writing the whole new cache file out. This could be\nimproved with a more clever disk format that contained a journal of\nunsorted newly written entries. You'd still write the full cache out\nonce in a while, but the cost would be amortized.\n\nI'm not sure the complexity is worth it, though. Yes, the write-out time\nis way slower than the super-fast everything-is-cached case. But it\ndoesn't happen that often (only when you have new commits, _and_ your\ntraversal actually looks at them). And it's still an order of magnitude\nfaster than it is without the cache at all. I doubt I would even notice\na quarter-second delay, or would just chalk it up to a few objects\nneeding to be pulled from disk.\n\nSo I'm inclined to leave it as-is, at least for now. If somebody wants\nto revisit the topic later and speed up cache writing, they can. But I\ndon't want a complex solution to hold up this series, which is already a\nbig improvement.\n\n-Peff\n"},{"id":"171219","messageId":"CAKPyHN1FgK6NXqZFZ=OvMgouhfxnGF0aXU+--y-P1u9BcK9Z4A@mail.gmail.com","threadId":"27801","inReplyTo":"20110713070405.GB18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-13T08:18:28Z","receivedAt":"2011-07-13T08:18:28Z","isPatch":false,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Wed, Jul 13, 2011 at 09:04, Jeff King wrote:\n> diff --git a/metadata-cache.c b/metadata-cache.c\n> new file mode 100644\n> index 0000000..e2e5ff8\n> --- /dev/null\n> +++ b/metadata-cache.c\n> @@ -0,0 +1,337 @@\n> +#include \"cache.h\"\n> +#include \"metadata-cache.h\"\n> +#include \"sha1-lookup.h\"\n> +#include \"object.h\"\n> +\n> +static struct metadata_cache **autowrite;\n> +static int autowrite_nr;\n> +static int autowrite_alloc;\n> +\n> +static int installed_atexit_autowriter;\n> +\n> +static int record_size(const struct metadata_cache *c)\n> +{\n> +       /* a record is a 20-byte sha1 plus the width of the value */\n> +       return c->mem.width + 20;\n\nYou are circumventing your own API. Why do you don't use the\ndecoration_width() accessor here? I don't see any check that\nMETADATA_CACHE_INIT(\"frotz\", 0, NULL) is invalid neither in the\ndocumentation nor in the code.\n\n> +}\n> +\n\nBert\n"},{"id":"171221","messageId":"20110713083139.GA26838@sigill.intra.peff.net","threadId":"27801","inReplyTo":"CAKPyHN1FgK6NXqZFZ=OvMgouhfxnGF0aXU+--y-P1u9BcK9Z4A@mail.gmail.com","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T08:31:39Z","receivedAt":"2011-07-13T08:31:39Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 10:18:28AM +0200, Bert Wesarg wrote:\n\n> > +static int record_size(const struct metadata_cache *c)\n> > +{\n> > +       /* a record is a 20-byte sha1 plus the width of the value */\n> > +       return c->mem.width + 20;\n> \n> You are circumventing your own API. Why do you don't use the\n> decoration_width() accessor here? I don't see any check that\n> METADATA_CACHE_INIT(\"frotz\", 0, NULL) is invalid neither in the\n> documentation nor in the code.\n\n\"struct decoration\" has the \"0 width means store a void pointer\" rule\nfor compatibility with existing callers. But I never intended for\nmetadata-cache to have such an exception. Nor would it make sense to\nstore a void pointer. The pointer would be written to disk, and would\nthen be meaningless during the next run of the program.\n\nI didn't figure anyone would assume the same special rule held for\nmetadata-cache; the fact that it is implemented using \"struct\ndecoration\" is not part of its public API. But I guess I was wrong.\n\nIt might make sense to put:\n\n if (!c->mem.width)\n die(\"BUG: zero-width metadata-cache\");\n\ninto the initialization function to make it more clear, and make a note\nin the API documentation.\n\nI considered briefly that a zero-width cache might actually be useful\nfor storing a membership list (i.e., \"is this sha1 in the list or not\").\nBut then you have no way of distinguishing \"not in the list\" from \"have\nno checked whether it should be in the list\". You are probably better\noff storing a single byte flag in such cases.\n\n-Peff\n"},{"id":"171224","messageId":"CAKPyHN1tixwJPJHG+wY34HVLYGT4fD9Sc-qJ8=on8EWfW-H6aw@mail.gmail.com","threadId":"27801","inReplyTo":"20110713083139.GA26838@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-13T08:45:52Z","receivedAt":"2011-07-13T08:45:52Z","isPatch":false,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Wed, Jul 13, 2011 at 10:31, Jeff King wrote:\n> On Wed, Jul 13, 2011 at 10:18:28AM +0200, Bert Wesarg wrote:\n>\n>> > +static int record_size(const struct metadata_cache *c)\n>> > +{\n>> > +       /* a record is a 20-byte sha1 plus the width of the value */\n>> > +       return c->mem.width + 20;\n>>\n>> You are circumventing your own API. Why do you don't use the\n>> decoration_width() accessor here? I don't see any check that\n>> METADATA_CACHE_INIT(\"frotz\", 0, NULL) is invalid neither in the\n>> documentation nor in the code.\n>\n> \"struct decoration\" has the \"0 width means store a void pointer\" rule\n> for compatibility with existing callers. But I never intended for\n> metadata-cache to have such an exception. Nor would it make sense to\n> store a void pointer. The pointer would be written to disk, and would\n> then be meaningless during the next run of the program.\n>\n> I didn't figure anyone would assume the same special rule held for\n> metadata-cache; the fact that it is implemented using \"struct\n> decoration\" is not part of its public API. But I guess I was wrong.\n\nYou're right here, that it is not part of the public API, but you're\nnot wrong about your guess. But when reading this patch series, the\nreader obviously knows that the metadata-cache uses a struct\ndecoration for the in-memory values. Thus the reader knows that 0 is\nspecial for struct decoration, and that there is an API to get the\nwidth from the struct decoration.\n\n>\n> It might make sense to put:\n>\n>  if (!c->mem.width)\n>          die(\"BUG: zero-width metadata-cache\");\n>\n> into the initialization function to make it more clear, and make a note\n> in the API documentation.\n\nThat should be good. Thanks.\n\nBert\n\n> -Peff\n>\n"},{"id":"171249","messageId":"4E1DAB0B.4020109@gmail.com","threadId":"27801","inReplyTo":"20110713070517.GC18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 3/6] commit: add commit_generation function","fromName":"Eric Sunshine","fromEmail":"ericsunshine@gmail.com","sentAt":"2011-07-13T14:26:19Z","receivedAt":"2011-07-13T14:26:19Z","isPatch":false,"sender":{"key":"ericsunshine@gmail.com","avatar":null},"body":"On 7/13/2011 3:05 AM, Jeff King wrote:\n> A commit's generation is its height in the history graph, as\n> measured from the farthest root. It is defined as:\n>\n> - Otherwise, its generation is 1 more than the maximum of\n> its parents generations.\n\nPossessive: s/parents/parents'/\n\n> We could also store generation numbers in the commit header\n> directly. These would be faster to look at than an external\n> cache (they would be on par speed-wise with commit\n> timestamps). But there are a few reasons not to:\n>\n> 2. With grafts and replacement objects, the graph\n> structure (and thus the generation numbers) can be\n> changed. So the generation number, while immutable for\n> a given commit object, can be changed when we \"lie\"\n> about the graph structure via these mechanisms. Being\n> able to simply clear the cache when these things are\n> changed is helpful.\n\nWould this be clearer? \"Being able to rebuild the cache when...\"\n\n-- ES\n"},{"id":"171250","messageId":"4E1DAB14.5040001@gmail.com","threadId":"27801","inReplyTo":"20110713070616.GE18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 5/6] check commit generation cache validity against grafts","fromName":"Eric Sunshine","fromEmail":"ericsunshine@gmail.com","sentAt":"2011-07-13T14:26:28Z","receivedAt":"2011-07-13T14:26:28Z","isPatch":false,"sender":{"key":"ericsunshine@gmail.com","avatar":null},"body":"On 7/13/2011 3:06 AM, Jeff King wrote:\n> +void metadata_graph_validity(unsigned char out[20])\n> +{\n> +\tgit_SHA_CTX ctx;\n> +\n> +\tgit_SHA1_Init(&ctx);\n> +\n> +\tgit_SHA1_Update(&ctx, \"grafts\", 6);\n> +\tcommit_graft_validity(&ctx);\n> +\n> +\tgit_SHA1_Update(&ctx, \"replace\", 7);\n> +\treplace_object_validity(&ctx);\n\nThe implementation of metadata_graph_validity() makes it clear that \ncommit_graft_validity() and replace_object_validity() are computing \nchecksums in aid of validity-checking of the generations cache. However, \nthe naive reader seeing the names commit_graft_validity() and \nreplace_object_validity() in the API is likely to assume that these \nfunctions are somehow checking validity of the grafts and replace-refs \nthemselves, which is not the case. Perhaps better names would be \ncommit_graft_checksum() and replace_object_checksum()?\n\nThe name metadata_graph_validity() also suffers from this shortcoming. \nThe actual validity check is performed by check_cache_header(), whereas \nmetadata_graph_validity() is merely computing a checksum.\n\n-- ES\n"},{"id":"171274","messageId":"20110713175250.GA1448@elie","threadId":"27801","inReplyTo":"20110713065700.GA18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-13T17:52:50Z","receivedAt":"2011-07-13T17:52:50Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"(+cc: David Barr)\nHi,\n\nJeff King wrote:\n\n> The decorate API provides a mapping of objects to arbitrary\n> values. Until now, it did this by allowing you to store a\n> void pointer, which could point to other storage. This has\n> two problems:\n[...]\n> This patch lets you store fixed-size values directly in the\n> hash table without allocating them elsewhere.\n\nNice idea.\n\n> --- a/Documentation/technical/api-decorate.txt\n> +++ b/Documentation/technical/api-decorate.txt\n> @@ -1,6 +1,166 @@\n> decorate API\n> ============\n> \n> -Talk about \n> +The decorate API is a system for efficiently mapping objects to values\n\nThanks for filling in the API docs! That's awesome.\n\n> +`struct object_decoration`::\n> +\n> +\tA structure representing the decoration of a single object.\n> +\tCallers will not normally need to use this object unless they\n> +\tare iterating all elements in the decoration hash. The `base`\n> +\tfield points to the object being mapped (or `NULL` if it is\n> +\tan empty hash slot). The `decoration` field stores the mapped\n> +\tvalue as a sequence of bytes; use the `width` field in `struct\n> +\tdecoration` to know the exact size.\n\nSo the `decoration` field is an array rather than a pointer now,\nhence...\n\n[...]\n> +void dump_longs(void)\n> +{\n> +\tint i;\n> +\tfor (i = 0; i < longs.size; i++) {\n> +\t\tstruct object_decoration *e = decoration_slot(&longs, i);\n> +\t\tunsigned long *value = (unsigned long *)e->decoration;\n> +\n> +\t\t/* empty hash slot */\n> +\t\tif (!e->base)\n> +\t\t\tcontinue;\n> +\n> +\t\tprintf(\"%s -> %lu\\n\", sha1_to_hex(e->base->sha1), *value);\n\n... a cast is needed to use it. Makes some sense.\n\nWhat alignment guarantees are there for the field, if any? I'm\nespecially worried about platforms like sparc32 where the pointer\nwidth is 32 bits but some types need to be aligned to 64 bits.\n\n> --- a/builtin/fast-export.c\n> +++ b/builtin/fast-export.c\n[...]\n\nNice.\n\n> @@ -547,15 +534,15 @@ static void export_marks(char *file)\n> \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n> \n> \tfor (i = 0; i < idnums.size; i++) {\n> +\t\tstruct object_decoration *deco = decoration_slot(&idnums, i);\n> \t\tif (deco->base && deco->base->type == 1) {\n> -\t\t\tmark = ptr_to_mark(deco->decoration);\n> -\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n> +\t\t\tuint32_t *mark = (uint32_t *)deco->decoration;\n> +\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", *mark,\n> \t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n\nIs this okay according to strict aliasing rules? Maybe it would be\nsafer to write\n\n\t\t\tuint32_t mark;\n\t\t\tmemcpy(&mark, deco->decoration, sizeof(mark));\n\nwhich generates the same code in current versions of gcc on x86 if I\nremember correctly.\n\n> --- a/decorate.c\n> +++ b/decorate.c\n> @@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)\n> \treturn hash % n;\n> }\n> \n> -static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n> +static int insert_decoration(struct decoration *n, const struct object *base,\n> +\t\t\t const void *decoration, void *old)\n> {\n> \tint size = n->size;\n> -\tstruct object_decoration *hash = n->hash;\n> +\tunsigned long width = decoration_width(n);\n\nMicronit: why not size_t?\n\n> \tunsigned int j = hash_obj(base, size);\n> \n> -\twhile (hash[j].base) {\n> -\t\tif (hash[j].base == base) {\n> -\t\t\tvoid *old = hash[j].decoration;\n> -\t\t\thash[j].decoration = decoration;\n> -\t\t\treturn old;\n> +\twhile (1) {\n\nMicrooptimization: the modulo operation can avoid the conditional (j >= size):\n\n\tfor (j = hash_obj(base, size); ; j = (j + 1) % size) {\n\t}\n\nBy the way, how do we know this loop will terminate? Is it because\nthe insertion function is careful to make sure the table never gets\nfilled?\n\n[...]\n> static void grow_decoration(struct decoration *n)\n> {\n> \tint i;\n> \tint old_size = n->size;\n> -\tstruct object_decoration *old_hash = n->hash;\n> +\tunsigned char *old_hash = n->hash;\n> \n> \tn->size = (old_size + 1000) * 3 / 2;\n> -\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n> +\tn->hash = xcalloc(n->size, decoration_stride(n));\n> \tn->nr = 0;\n> \n> \tfor (i = 0; i < old_size; i++) {\n> -\t\tconst struct object *base = old_hash[i].base;\n> -\t\tvoid *decoration = old_hash[i].decoration;\n> -\n> -\t\tif (!base)\n> -\t\t\tcontinue;\n> -\t\tinsert_decoration(n, base, decoration);\n> +\t\tstruct object_decoration *e =\n> +\t\t\t(struct object_decoration *)\n> +\t\t\t(old_hash + i * decoration_stride(n));\n> +\t\tif (e->base)\n> +\t\t\tinsert_decoration(n, e->base, e->decoration, NULL);\n\nI'm worried about alignment here, too.\n\n[...]\n> @@ -60,15 +64,35 @@ static void grow_decoration(struct decoration *n)\n[...]\n> /* Lookup a decoration pointer */\n> -void *lookup_decoration(struct decoration *n, const struct object *obj)\n> +void *lookup_decoration(const struct decoration *n, const struct object *obj)\n> +{\n> +\tvoid **v;\n> +\n> +\tv = lookup_decoration_value(n, obj);\n> +\tif (!v)\n> +\t\treturn NULL;\n> +\treturn *v;\n> +}\n\nMaybe memcpy to avoid alignment problems?\n\n\tunsigned char *p;\n\tvoid *v;\n\n\tp = lookup_decoration_value(n, obj);\n\tif (!p)\n\t\treturn NULL;\n\tmemcpy(v, p, sizeof(v));\n\treturn v;\n\nBut:\n\n> +\n> +void *lookup_decoration_value(const struct decoration *n,\n> +\t\t\t const struct object *obj)\n> {\n> \tunsigned int j;\n> \n> @@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)\n> \t\treturn NULL;\n> \tj = hash_obj(obj, n->size);\n> \tfor (;;) {\n> -\t\tstruct object_decoration *ref = n->hash + j;\n> +\t\tstruct object_decoration *ref = decoration_slot(n, j);\n> \t\tif (ref->base == obj)\n> \t\t\treturn ref->decoration;\n\nI worry that this could have alignment trouble anyway.\n\n> --- a/decorate.h\n> +++ b/decorate.h\n> @@ -3,16 +3,47 @@\n> \n> struct object_decoration {\n> \tconst struct object *base;\n> -\tvoid *decoration;\n> +\tunsigned char decoration[FLEX_ARRAY];\n> };\n\nOn some platforms, this becomes\n\n\tstruct object_decoration {\n\t\tconst struct object *base;\n\t\tunsigned char decoration[];\n\t};\n\nwhich I hope would create a type with the alignment of a pointer\n(generally sufficient except in odd cases like sparc32). But on\nold-fashioned platforms, it is\n\n\tstruct object_decoration {\n\t\tconst struct object *base;\n\t\tunsigned char decoration[1];\n\t};\n\nWill that be a problem, or is it standard for compilers to be smart\nenough to pad to a nice alignment?\n\n> struct decoration {\n> \tconst char *name;\n> +\t/* width of data we're holding; must be set before adding */\n> +\tconst unsigned int width;\n\nMakes sense.\n\n> \tunsigned int size, nr;\n> -\tstruct object_decoration *hash;\n> +\t/*\n> +\t * The hash contains object_decoration structs, but we don't know their\n> +\t * size until runtime. So we store is as a pointer to characters to\n> +\t * make pointer arithmetic easier.\n> +\t */\n> +\tunsigned char *hash;\n> };\n[...]\n> +extern int add_decoration_value(struct decoration *n,\n> +\t\t\t\tconst struct object *obj,\n> +\t\t\t\tconst void *decoration,\n> +\t\t\t\tvoid *old);\n> +extern void *lookup_decoration_value(const struct decoration *n,\n> +\t\t\t\t const struct object *obj);\n\nIf we're willing to incur the cost of a copy that assumes unaligned\nobjects, perhaps\n\n\textern int lookup_decoration_value(const struct decoration *n,\n\t\t\t\tconst struct object *obj,\n\t\t\t\tvoid *result, size_t width);\n\nwould be safer.\n\nAside from the alignment and strict-aliasing worries, this looks very\nnice. Thanks for writing it.\n\nRegards,\nJonathan\n"},{"id":"171278","messageId":"20110713191805.GA1885@sigill.intra.peff.net","threadId":"27801","inReplyTo":"CAKPyHN1tixwJPJHG+wY34HVLYGT4fD9Sc-qJ8=on8EWfW-H6aw@mail.gmail.com","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T19:18:05Z","receivedAt":"2011-07-13T19:18:05Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 10:45:52AM +0200, Bert Wesarg wrote:\n\n> > It might make sense to put:\n> >\n> >  if (!c->mem.width)\n> >          die(\"BUG: zero-width metadata-cache\");\n> >\n> > into the initialization function to make it more clear, and make a note\n> > in the API documentation.\n> \n> That should be good. Thanks.\n\nI've squashed in the patch below for my next re-roll.\n\ndiff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt\nindex 192a868..e335b96 100644\n--- a/Documentation/technical/api-metadata-cache.txt\n+++ b/Documentation/technical/api-metadata-cache.txt\n@@ -102,9 +102,10 @@ Functions\n \tspecifies a human-readable name which will be used for storage\n \tin `$GIT_DIR/cache/$name`. The `width` parameter specifies the\n \tsize, in units of `char`, of the data to be stored (e.g., use\n-\t`sizeof(uint32_t)` to store 32-bit integers). The `validity`\n-\tparameter is either NULL or a pointer to a function providing a\n-\t20-byte validity sha1.\n+\t`sizeof(uint32_t)` to store 32-bit integers). The `width`\n+\tparameter must be greater than 0. The `validity` parameter is\n+\teither NULL or a pointer to a function providing a 20-byte\n+\tvalidity sha1.\n \n `metadata_cache_lookup`::\n \ndiff --git a/metadata-cache.c b/metadata-cache.c\nindex e2e5ff8..025d3a5 100644\n--- a/metadata-cache.c\n+++ b/metadata-cache.c\n@@ -261,6 +261,9 @@ static void metadata_cache_init(struct metadata_cache *c)\n \tif (c->initialized)\n \t\treturn;\n \n+\tif (!c->mem.width)\n+\t\tdie(\"BUG: tried to initialize zero-width metadata cache\");\n+\n \topen_disk_cache(c, metadata_cache_path(c->mem.name));\n \n \tALLOC_GROW(autowrite, autowrite_nr+1, autowrite_alloc);\n\n-Peff\n"},{"id":"171279","messageId":"7vipr66kmz.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110713070405.GB18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-13T19:33:24Z","receivedAt":"2011-07-13T19:33:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> +`metadata_cache_lookup_uint32`::\n> +`metadata_cache_add_uint32`::\n\nI think these are \"uint31\" functions, as you cannot signal missing entry\nby returning a value with the MSB set if higher-end of uint32 range can be\na valid value.\n\n> +\tif (c->validity_fun) {\n> +\t\tc->validity_fun(validity);\n> +\t\tif (hashcmp(validity, p))\n> +\t\t\treturn NULL;\n> +\t}\n\nTwo comments.\n\n - I would have expected that c->validity_check() would be a way for a\n caller to implement a boolean function to check the validity of the\n cache, with another hook c->validity_token() to generate/update the\n token. I could then use the 20-byte space to store a timestamp and\n check can say \"It was still 3-days ago? fresh enough\", or something\n like that. But this is not a complaint--such a scheme I wrote in the\n above four lines may be _too_ flexible to be useful.\n\n - I wonder if validity_fn() callback wants a callback parameter (the\n pointer \"c\" itself, after adding an extra field to metadata_cache that\n stores the callback parameter pointer of type \"void *\" and adding a\n parameter to METADATA_CACHE_INIT() macro to initialize it).\n\nOther than that, this is looking fun ;-)\n"},{"id":"171280","messageId":"20110713193509.GC31965@sigill.intra.peff.net","threadId":"27801","inReplyTo":"4E1DAB14.5040001@gmail.com","subject":"Re: [RFC/PATCHv2 5/6] check commit generation cache validity against grafts","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T19:35:09Z","receivedAt":"2011-07-13T19:35:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 10:26:28AM -0400, Eric Sunshine wrote:\n\n> On 7/13/2011 3:06 AM, Jeff King wrote:\n> >+void metadata_graph_validity(unsigned char out[20])\n> >+{\n> >+\tgit_SHA_CTX ctx;\n> >+\n> >+\tgit_SHA1_Init(&ctx);\n> >+\n> >+\tgit_SHA1_Update(&ctx, \"grafts\", 6);\n> >+\tcommit_graft_validity(&ctx);\n> >+\n> >+\tgit_SHA1_Update(&ctx, \"replace\", 7);\n> >+\treplace_object_validity(&ctx);\n> \n> The implementation of metadata_graph_validity() makes it clear that\n> commit_graft_validity() and replace_object_validity() are computing\n> checksums in aid of validity-checking of the generations cache.\n> However, the naive reader seeing the names commit_graft_validity()\n> and replace_object_validity() in the API is likely to assume that\n> these functions are somehow checking validity of the grafts and\n> replace-refs themselves, which is not the case. Perhaps better names\n> would be commit_graft_checksum() and replace_object_checksum()?\n\nAgreed. The term \"validity\" is a bit funny, and I think checksum is\nbetter.\n\n> The name metadata_graph_validity() also suffers from this\n> shortcoming. The actual validity check is performed by\n> check_cache_header(), whereas metadata_graph_validity() is merely\n> computing a checksum.\n\nYeah. I had originally called it metadata_validity_graph() with the\nassumption that the metadata-cache would provide a collection of\ncommonly-used validity functions. That didn't seem quite right, so I\nswitched the two words around to emphasize that it was about the graph.\nBut this function really has nothing to do with the metadata-cache at\nall (except that validity tokens are a good place to use the result). It\nreally belongs to the commit subsystem, because it is about the shape of\nthe history graph.\n\nSo here's what I've done for the next iteration:\n\n 1. metadata_graph_validity is now:\n\n void commit_graph_checksum(unsigned char out[20]);\n\n and lives in commit.[ch].\n\n 2. commit_graft_validity is now commit_graft_checksum, and is static\n inside commit.c.\n\n 3. replace_object_validity is now replace_objects_checksum. It must\n remain non-static because it lives in replace-object.c. I\n pluralized the \"objects\" to make it more clear it was not about\n checksumming a single replace_object, but rather all of them.\n\nSo now the only two warts I see are:\n\n 1. Some of the *_checksum functions return a 20-byte sha1, and some\n are just meant to stir their contents into a SHA_CTX. I can live\n with that. You can tell which is which by looking at their\n signatures.\n\n 2. The name \"replace_object_checksum\" can be read as \"checksum the\n replace-objects\" or as \"replace this object's checksum\". But the\n ambiguous verb in the name of the subsystem is not a problem I am\n introducing. The \"replace-object\" subsystem should perhaps have\n been called \"replacement-object\" from the beginning to make this\n more clear.\n\nThanks for the suggestions (I also took the suggestions from your other\nemail for improving the commit message).\n\n-Peff\n"},{"id":"171281","messageId":"7vei1u6kbq.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110713083139.GA26838@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-13T19:40:09Z","receivedAt":"2011-07-13T19:40:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I considered briefly that a zero-width cache might actually be useful\n> for storing a membership list (i.e., \"is this sha1 in the list or not\").\n> But then you have no way of distinguishing \"not in the list\" from \"have\n> no checked whether it should be in the list\". You are probably better\n> off storing a single byte flag in such cases.\n\nGood reasoning; if you are going to add \"BUG:zero width\", the above is a\ngood comment to have nearby.\n\nThanks.\n"},{"id":"171282","messageId":"20110713200814.GD31965@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713175250.GA1448@elie","subject":"Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T20:08:15Z","receivedAt":"2011-07-13T20:08:15Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 12:52:50PM -0500, Jonathan Nieder wrote:\n\n> > +void dump_longs(void)\n> > +{\n> > +\tint i;\n> > +\tfor (i = 0; i < longs.size; i++) {\n> > +\t\tstruct object_decoration *e = decoration_slot(&longs, i);\n> > +\t\tunsigned long *value = (unsigned long *)e->decoration;\n> > +\n> > +\t\t/* empty hash slot */\n> > +\t\tif (!e->base)\n> > +\t\t\tcontinue;\n> > +\n> > +\t\tprintf(\"%s -> %lu\\n\", sha1_to_hex(e->base->sha1), *value);\n> \n> ... a cast is needed to use it. Makes some sense.\n> \n> What alignment guarantees are there for the field, if any? I'm\n> especially worried about platforms like sparc32 where the pointer\n> width is 32 bits but some types need to be aligned to 64 bits.\n\nWe're packing these structs into a heap-allocated byte array. Each\nstruct takes up the size of the struct as defined by the compiler, plus\n$width bytes. So with a 32-bit pointer and 32-bit data, you are probably\nlooking at data fields offset by 32-bits. Which might be wrong on\nsparc32.\n\nThe result of malloc is guaranteed to be aligned for any type. But for\narrays, I'm not sure how that is handled. The only thing that makes\nsense to me is that a sparc compiler with something like:\n\n struct foo {\n struct bar *pointer; /* pointers are 32-bits */\n double value; /* assume doubles need to be 64-bit aligned */\n };\n\nwould have to actually put in 32-bits of padding to meet the alignment\ngoals (and possibly some padding at the end so that the followup struct\nin an array is aligned properly). But I don't know how this is handled,\nso I'm just guessing.\n\nAnd if that is the case, then yeah, there may well be an alignment issue\nhere. It gets even worse if you try to store something with an odd\nalignment, like a 3-byte sequence.\n\nSo perhaps the safest thing would be to always memcpy into a real,\nproperly aligned destination. I'd have to tweak the get_value interface\na little bit, but it's not a big deal. It's going to be a little bit\nslower, of course, but I doubt the extra few instructions will be\nmeasurable.\n\nI have to say, though, between the alignment issues and the strict\naliasing, I am tempted to scrap this whole approach and just use macros\nto define the few functions we need. It's not like these containers are\nheterogenous, or that we have a ton of types. Right now we want to map\n\"void *\" and \"uint32_t\". In the future, I'd like to map a 20-byte sha1.\n\nDoing something like:\n\n #define DECLARE_DECORATION(name, type) \\\n void decoration_get_##name(struct decoration_##name *, \\\n struct object *, \\\n type value); \\\n int decoration_set_##name(struct decoration_##name *, \\\n struct object *, \\\n type *value);\n\n DECLARE_DECORATION(void, void *);\n DECLARE_DECORATION(uint32, uint32_t);\n\n /* and then do an IMPLEMENT_DECORATION macro inside decorate.c */\n\nis tempting. Writing your functions inside macros like this is ugly, but\nthen we know it's right, because the compiler knows what the sizes are\nat compile time. And the optimizer can do its job properly, because\nwe're not fiddling the types at runtime.\n\n> > \tfor (i = 0; i < idnums.size; i++) {\n> > +\t\tstruct object_decoration *deco = decoration_slot(&idnums, i);\n> > \t\tif (deco->base && deco->base->type == 1) {\n> > -\t\t\tmark = ptr_to_mark(deco->decoration);\n> > -\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n> > +\t\t\tuint32_t *mark = (uint32_t *)deco->decoration;\n> > +\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", *mark,\n> > \t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n> \n> Is this okay according to strict aliasing rules? Maybe it would be\n> safer to write\n> \n> \t\t\tuint32_t mark;\n> \t\t\tmemcpy(&mark, deco->decoration, sizeof(mark));\n> \n> which generates the same code in current versions of gcc on x86 if I\n> remember correctly.\n\nI guess you didn't read my comments on v1 of the patch. :)\n\nI'm not sure if it's OK or not. Curiously, doing this:\n\n uint32_t mark = *(uint32_t *)deco->decoration;\n\ngenerates a warning under -fstrict-aliasing, but:\n\n uint32_t *mark = (uint32_t *)deco->decoration;\n /* now use *mark */;\n\ndoes not. I'm not sure if there's a subtlety in the strict aliasing\nrules that makes the latter OK, or if it is simply a bug that it doesn't\ntrigger the compiler warning.\n\nUsing memcpy would be the safest thing, both from an alignment and a\nstrict-aliasing point of view.\n\n> > --- a/decorate.c\n> > +++ b/decorate.c\n> > @@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)\n> > \treturn hash % n;\n> > }\n> > \n> > -static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n> > +static int insert_decoration(struct decoration *n, const struct object *base,\n> > +\t\t\t const void *decoration, void *old)\n> > {\n> > \tint size = n->size;\n> > -\tstruct object_decoration *hash = n->hash;\n> > +\tunsigned long width = decoration_width(n);\n> \n> Micronit: why not size_t?\n\nNo reason.\n\n> > \tunsigned int j = hash_obj(base, size);\n> > \n> > -\twhile (hash[j].base) {\n> > -\t\tif (hash[j].base == base) {\n> > -\t\t\tvoid *old = hash[j].decoration;\n> > -\t\t\thash[j].decoration = decoration;\n> > -\t\t\treturn old;\n> > +\twhile (1) {\n> \n> Microoptimization: the modulo operation can avoid the conditional (j >= size):\n> \n> \tfor (j = hash_obj(base, size); ; j = (j + 1) % size) {\n> \t}\n\nYeah, that would work. I doubt the performance is measurable. I couldn't\neven get a measurable difference in iterating using pointers versus\nusing indices and converting them to pointers during each run through\nthe loop. So I suspect we simply don't actually go through this loop\nvery many times (i.e., the hash is doing its job and entries are spread\nout appropriately). So micro-optimizing is probably not worth it.\n\n> By the way, how do we know this loop will terminate? Is it because\n> the insertion function is careful to make sure the table never gets\n> filled?\n\nExactly. See grow_decoration. I had the same question when I looked at\nthe loop (the termination condition is part of the original code, which\nis Linus's).\n\n> > +void *lookup_decoration(const struct decoration *n, const struct object *obj)\n> > +{\n> > +\tvoid **v;\n> > +\n> > +\tv = lookup_decoration_value(n, obj);\n> > +\tif (!v)\n> > +\t\treturn NULL;\n> > +\treturn *v;\n> > +}\n> \n> Maybe memcpy to avoid alignment problems?\n> \n> \tunsigned char *p;\n> \tvoid *v;\n> \n> \tp = lookup_decoration_value(n, obj);\n> \tif (!p)\n> \t\treturn NULL;\n> \tmemcpy(v, p, sizeof(v));\n> \treturn v;\n\nYeah, that would solve it.\n\n> > +void *lookup_decoration_value(const struct decoration *n,\n> > +\t\t\t const struct object *obj)\n> > {\n> > \tunsigned int j;\n> > \n> > @@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)\n> > \t\treturn NULL;\n> > \tj = hash_obj(obj, n->size);\n> > \tfor (;;) {\n> > -\t\tstruct object_decoration *ref = n->hash + j;\n> > +\t\tstruct object_decoration *ref = decoration_slot(n, j);\n> > \t\tif (ref->base == obj)\n> > \t\t\treturn ref->decoration;\n> \n> I worry that this could have alignment trouble anyway.\n\nI don't think it has alignment problems with the value inside the\nstruct, since we are just passing a pointer back to it as a void *; it\nis the caller who will dereference it. We could pass it back as an\nunsigned char *, to make it clear to the caller that they need to\nmemcpy.\n\nBut if you mean there might be an alignment issue looking at the ->base\nfield of the \"struct object_decoration\", then yeah, I am not sure of\nthat.\n\n> > struct object_decoration {\n> > \tconst struct object *base;\n> > -\tvoid *decoration;\n> > +\tunsigned char decoration[FLEX_ARRAY];\n> > };\n> \n> On some platforms, this becomes\n> \n> \tstruct object_decoration {\n> \t\tconst struct object *base;\n> \t\tunsigned char decoration[];\n> \t};\n> \n> which I hope would create a type with the alignment of a pointer\n> (generally sufficient except in odd cases like sparc32). But on\n> old-fashioned platforms, it is\n> \n> \tstruct object_decoration {\n> \t\tconst struct object *base;\n> \t\tunsigned char decoration[1];\n> \t};\n> \n> Will that be a problem, or is it standard for compilers to be smart\n> enough to pad to a nice alignment?\n\nI don't know. Thanks for mentioning it; it was another issue I had\nnoticed while writing, but forgot to bring up when I posted the patches.\n\n> If we're willing to incur the cost of a copy that assumes unaligned\n> objects, perhaps\n> \n> \textern int lookup_decoration_value(const struct decoration *n,\n> \t\t\t\tconst struct object *obj,\n> \t\t\t\tvoid *result, size_t width);\n> \n> would be safer.\n\nAgreed.\n\n> Aside from the alignment and strict-aliasing worries, this looks very\n> nice. Thanks for writing it.\n\nThanks for the review. When I wrote it, and even now, I'm still very\nunsure that the alignment and aliasing issues are right. It seems to\nwork so far for me, but:\n\n 1. I'm on x86_64, which is not one of the more oddball platforms for\n alignment issues.\n\n 2. I'm putting in \"void *\" and \"uint32_t\" values. Those are about as\n vanilla as you can get. But I don't want to leave a time bomb for\n somebody who tries to store a 3-byte sequence.\n\nSo it makes me a bit nervous, and why I'm very tempted by the ugly macro\nsolution.\n\n-Peff\n"},{"id":"171283","messageId":"20110713202536.GE31965@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vipr66kmz.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T20:25:36Z","receivedAt":"2011-07-13T20:25:36Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 12:33:24PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > +`metadata_cache_lookup_uint32`::\n> > +`metadata_cache_add_uint32`::\n> \n> I think these are \"uint31\" functions, as you cannot signal missing entry\n> by returning a value with the MSB set if higher-end of uint32 range can be\n> a valid value.\n\nNo, look at their definitions. I am careful not to assume we have a\nsentinel value for \"not found\", and you must use them like:\n\n uint32_t value;\n if (metadata_cache_lookup_uint32(c, obj, &value))\n printf(\"value is %\"PRIu32\", value);\n else\n printf(\"value is not there\");\n\n> > +\tif (c->validity_fun) {\n> > +\t\tc->validity_fun(validity);\n> > +\t\tif (hashcmp(validity, p))\n> > +\t\t\treturn NULL;\n> > +\t}\n> \n> Two comments.\n> \n> - I would have expected that c->validity_check() would be a way for a\n> caller to implement a boolean function to check the validity of the\n> cache, with another hook c->validity_token() to generate/update the\n> token. I could then use the 20-byte space to store a timestamp and\n> check can say \"It was still 3-days ago? fresh enough\", or something\n> like that. But this is not a complaint--such a scheme I wrote in the\n> above four lines may be _too_ flexible to be useful.\n\nI started with exactly that interface, and came to the conclusion that\nit was unneeded flexibility. I can switch it back, but there's really\nnot a need to at this point. The fact that there are 20 opaque bytes in\nthe file is what will live with us from version to version. But if new\ncode wants to be more flexible about how it checks the bytes, that is\nsomething that can be changed easily when the new code is added.\n\n> - I wonder if validity_fn() callback wants a callback parameter (the\n> pointer \"c\" itself, after adding an extra field to metadata_cache that\n> stores the callback parameter pointer of type \"void *\" and adding a\n> parameter to METADATA_CACHE_INIT() macro to initialize it).\n\nNeither this use nor my proposed patch-id cache would have a need for\nit, so I didn't bother. And like above, it can be easily changed later.\n\n> Other than that, this is looking fun ;-)\n\nThanks. I'm pleased with the performance numbers I'm getting. I'm still\na bit iffy on the alignment and aliasing issues in the first two\npatches.\n\n-Peff\n"},{"id":"171284","messageId":"7vaach7wfh.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110713072350.GA18614@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-13T20:33:22Z","receivedAt":"2011-07-13T20:33:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It takes barely any time to get the generation of the new commit, but we\n> spend .25 seconds writing the whole new cache file out. This could be\n> improved with a more clever disk format that contained a journal of\n> unsorted newly written entries. You'd still write the full cache out\n> once in a while, but the cost would be amortized.\n\nThis series consists of three somewhat related ideas:\n\n - A generic API to persistently annotate 20-byte keys (typically object\n names);\n\n - Using that API to implement commit generation numbers;\n\n - Using commit generation numbers in \"tag --contains\" traversal.\n\nI think the first one is independently a good change, but I have been\nwondering if the entire history needs to be annotated with the generation\nnumber for the goal of the third item. There may be stretches of history\nwhere timestamps are screwed up, but if the commits we should dig through\nwhile traversing (because they, their parents or their children record\nskewed timestamps) are minority in the history, the same generic API could\nbe used to mark only these commits as such, by using far smaller number of\ndisk I/Os, no?\n"},{"id":"171288","messageId":"20110713205844.GA15435@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vaach7wfh.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T20:58:44Z","receivedAt":"2011-07-13T20:58:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 01:33:22PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > It takes barely any time to get the generation of the new commit, but we\n> > spend .25 seconds writing the whole new cache file out. This could be\n> > improved with a more clever disk format that contained a journal of\n> > unsorted newly written entries. You'd still write the full cache out\n> > once in a while, but the cost would be amortized.\n> \n> This series consists of three somewhat related ideas:\n> \n> - A generic API to persistently annotate 20-byte keys (typically object\n> names);\n> \n> - Using that API to implement commit generation numbers;\n> \n> - Using commit generation numbers in \"tag --contains\" traversal.\n\nYup, I think that is accurate.\n\n> I think the first one is independently a good change, but I have been\n> wondering if the entire history needs to be annotated with the generation\n> number for the goal of the third item. There may be stretches of history\n> where timestamps are screwed up, but if the commits we should dig through\n> while traversing (because they, their parents or their children record\n> skewed timestamps) are minority in the history, the same generic API could\n> be used to mark only these commits as such, by using far smaller number of\n> disk I/Os, no?\n\nI'm not sure it's workable. To use generations as a cutoff, even\nfor a subset the subset of commits with broken timestamps, you have to\nknow the generations of other commits, so you know where the cutoff is.\nE.g., in \"git tag --contains HEAD~1000\", I want to search no farther\nback than the generation of HEAD~1000. Which means I need to know what\nits generation is, which involves going to the roots at least once. We\ndon't want to go to the roots on-demand and cache only that one value,\nsince doing so is expensive. So we may as well cache all generations\nas we figure them out, not knowing which ones will be needed for future\ntraversals.\n\nOr are you suggesting dropping generations entirely, and just using\nmarked-up commit timestamps (or even a flag saying \"this timestamp is\nbogus, don't use it for cutoffs\")? I sent such a patch with timings\nearlier in this discussion (I can dig it up if you want). Even based on\na notes-cache[1], it's fast (because there aren't very many entries).\n\nBut there's a big question of deciding which timestamps are bogus. You\ncan only compare commits against their ancestors. A commit skewed to\nthe past is easy to find; its timestamp is less than one of its\nancestors. But for a commit skewed to the future, its descendants will\nall look skewed into the past.\n\nI think we can write our algorithms such that future-skewed timestamps\ndon't give _wrong_ answers, but are just suboptimal (i.e., they may mark\nmany legitimate commits as \"don't trust this timestamp for cutoff\", even\nthough it is their future-skewed ancestor that is actually the problem).\nBut I think I still like generation numbers because:\n\n 1. They're simple, complete, and unambiguous. It makes them easy to\n understand and use. And I suspect they can be applied in more\n places than just cutoff. For example, I seem to recall somebody\n mentioning that we could do topo-sorting much more efficiently with\n generation numbers. I'm not sure the same \"future-skewed commits\n are correct but slow\" property would hold there.\n\n 2. The cache can be generated and maintained on the fly. A cache that\n is simply \"if you are in this list, your timestamp is bogus\"\n suffers from the problem I mentioned elsewhere. If a commit is not\n in the list, is the timestamp good, or has it simply not been\n checked yet?\n\nIf the performance numbers were way worse, I would be more inclined to\nstay with a timestamp solution. But they're not really worse. The\nperformance for initial cache build is about the same (you have to go to\nthe roots in both cases), and the performance for using the cache is\nabout the same. The only slowness for the generation slowness is the\nextra I/O on writing out the cache. But it's not very much, and it's\nactually not that hard a problem to solve; I'm mainly leaving it because\nI'm lazy. But it's not as if file system implementors and key/value\ndatabase designers haven't been solving the problem for the past 30\nyears.\n\n-Peff\n\n[1] If we did want to go the route of \"is this commit in the set of\ncommits with bogus timestamps\", you could probably make things even\nsimpler by using a fixed-size bloom filter. Sized appropriately, it will\noccasionally give a false positive \"this commit has a bogus timestamp\".\nBut as discussed above, that is not going to cause a traversal cutoff to\ndo the wrong thing, but rather only to consider one extra commit it\nmight not have otherwise.\n"},{"id":"171290","messageId":"7vpqld6g14.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110713205844.GA15435@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-13T21:12:55Z","receivedAt":"2011-07-13T21:12:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Or are you suggesting dropping generations entirely, and just using\n> marked-up commit timestamps (or even a flag saying \"this timestamp is\n> bogus, don't use it for cutoffs\")?\n\nNot suggesting, but that was exactly what I was wondering. For example,\nstill_interesting() in revision.c says \"compare timestamp and return SLOP,\nnot 'we are done'\", and presumably that code could notice that \"ah, this\ncommit is marked as being on a stretch that timestamp based cut-off is\nunusable--keep digging\". The \"tag --contains\" and \"name-rev\" would also\nhave similar logic (I haven't looked at them for a while though).\n\n> But there's a big question of deciding which timestamps are bogus.\n\nI agree that the ones that you need to dig through may not be the ones\nwith bogus timestamps, but either an ancestor or a descendant (I haven't\nthought it through) of a commit with bogus timestamp. That is why I said\n\"a commit on a stretch that timestamp based cut-off is unusable\".\n\n> But I think I still like generation numbers because:\n>\n> 1. They're simple, complete, and unambiguous.\n\nNo question nor dispute about it.\n\n> The only slowness for the generation slowness is the\n> extra I/O on writing out the cache. But it's not very much,...\n\nOk.\n"},{"id":"171291","messageId":"20110713211826.GA17284@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vpqld6g14.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T21:18:27Z","receivedAt":"2011-07-13T21:18:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 02:12:55PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Or are you suggesting dropping generations entirely, and just using\n> > marked-up commit timestamps (or even a flag saying \"this timestamp is\n> > bogus, don't use it for cutoffs\")?\n> \n> Not suggesting, but that was exactly what I was wondering. For example,\n> still_interesting() in revision.c says \"compare timestamp and return SLOP,\n> not 'we are done'\", and presumably that code could notice that \"ah, this\n> commit is marked as being on a stretch that timestamp based cut-off is\n> unusable--keep digging\". The \"tag --contains\" and \"name-rev\" would also\n> have similar logic (I haven't looked at them for a while though).\n\nYes, the slop code in still_interesting could use a\n\"timestamp_is_bogus(commit)\" check. It could also use generation\nnumbers. :)\n\nI actually wonder if we could make merge-base computation more efficient\nusing generation numbers, and if it would be worth switching more\nalgorithms over to it. I haven't thought too hard about it, though.\n\n-Peff\n"},{"id":"171343","messageId":"20110714173454.GA21657@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110713200814.GD31965@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T17:34:54Z","receivedAt":"2011-07-14T17:34:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 13, 2011 at 04:08:14PM -0400, Jeff King wrote:\n\n> I have to say, though, between the alignment issues and the strict\n> aliasing, I am tempted to scrap this whole approach and just use macros\n> to define the few functions we need. It's not like these containers are\n> heterogenous, or that we have a ton of types. Right now we want to map\n> \"void *\" and \"uint32_t\". In the future, I'd like to map a 20-byte sha1.\n\nSo here's what that would look like (at least the decorate part).\n\nDoing macro meta-programming like this makes me feel a little dirty, but\nI actually think the result is more readable.\n\n [1/3]: implement generic key/value map\n [2/3]: fast-export: use object to uint32 map instead of \"decorate\"\n [3/3]: decorate: use \"map\" for the underlying implementation\n\nWhat do you think?\n\n-Peff\n"},{"id":"171347","messageId":"20110714175105.GA21771@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110714173454.GA21657@sigill.intra.peff.net","subject":"[PATCH 1/3] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T17:51:05Z","receivedAt":"2011-07-14T17:51:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It is frequently useful to have a fast, generic data\nstructure mapping keys to values. We already have something\nlike this in the \"decorate\" API, but it has two downsides:\n\n 1. The key type must always be a \"struct object *\".\n\n 2. The value type is a void pointer, which means it is\n inefficient and cumbersome for storing small values.\n One must either encode their value inside the void\n pointer, or allocate additional storage for the pointer\n to point to.\n\nThis patch introduces a generic map data structure, mapping\nkeys of arbitrary type to values of arbitrary type.\n\nOne possible strategy for implementation is to have a struct\nthat points to a sequence of bytes for each of the key and\nthe value, and to try to treat them as opaque in the code.\nHowever, this code gets complex, has a lot of casts, and\nruns afoul of violating alignment and strict aliasing rules.\n\nThis patch takes a different approach. We parameterize the\ntypes in each map by putting the declarations and\nimplementations inside macros, and expand the macros with\nthe correct types. This lets the compiler see the actual\ncode, with its real types, and figure out things like struct\npacking and alignment itself.\n\nSigned-off-by: Jeff King \n---\nIn addition to switching from using void pointers to macro expansion,\nthis has one other difference from my previous patch: it handles\narbitrary types for keys, not just object pointers. This was mentioned\nby Jakub, and would allow things like a fast bi-directional map for SVN\nrevision numbers and commits.\n\nI tried to keep the implementation simple. Two things that could be changed:\n\n 1. We can't assume that the map key is a pointer. So the sentinel\n \"NULL\" value isn't necessarily available to use, and we have to\n keep a separate bit in each hash entry to say \"is this valid\".\n This means when we _do_ store a pointer, we end up with an extra\n 32 bits or so in each hash entry for the \"used\" flag.\n\n We could add a macro parameter for sentinel values, so that types\n which _can_ handle this efficiently don't have to pay the price.\n Or we could decide that mapping arbitrary keys isn't worth the\n hassle. I wrote this way to be flexible for future use; I don't\n personally have plans to add svn revision number mappings.\n\n 2. It assumes values are assignable. That means storing something like\n \"unsigned char sha1[20]\" doesn't work. You can wrap it in a struct,\n but do we assume that struct assignment works everywhere? I didn't\n check, but I think it is in C89 but some antique compilers didn't\n allow it. Switching it to use memcpy() would be easy enough (or\n again, parameterizing so that assignable things don't have to pay\n the price).\n\n Makefile | 2 +\n map.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n map.h | 24 +++++++++++++++++\n 3 files changed, 112 insertions(+), 0 deletions(-)\n create mode 100644 map.c\n create mode 100644 map.h\n\ndiff --git a/Makefile b/Makefile\nindex 46793d1..6242321 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -530,6 +530,7 @@ LIB_H += list-objects.h\n LIB_H += ll-merge.h\n LIB_H += log-tree.h\n LIB_H += mailmap.h\n+LIB_H += map.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += notes.h\n@@ -621,6 +622,7 @@ LIB_OBJS += ll-merge.o\n LIB_OBJS += lockfile.o\n LIB_OBJS += log-tree.o\n LIB_OBJS += mailmap.o\n+LIB_OBJS += map.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\ndiff --git a/map.c b/map.c\nnew file mode 100644\nindex 0000000..378cecb\n--- /dev/null\n+++ b/map.c\n@@ -0,0 +1,86 @@\n+#include \"cache.h\"\n+#include \"map.h\"\n+#include \"object.h\"\n+\n+static unsigned int hash_obj(const struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash;\n+\n+\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n+\treturn hash % n;\n+}\n+\n+static unsigned int cmp_obj(const struct object *a, const struct object *b)\n+{\n+\treturn b == a;\n+}\n+\n+#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \\\n+static int map_insert_##name(struct map_##name *m, \\\n+\t\t\t const ktype key, \\\n+\t\t\t vtype value, \\\n+\t\t\t vtype *old) \\\n+{ \\\n+\tunsigned int j; \\\n+ \\\n+\tfor (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \\\n+\t\tif (cmp_fun(m->hash[j].key, key)) { \\\n+\t\t\tif (old) \\\n+\t\t\t\t*old = m->hash[j].value; \\\n+\t\t\tm->hash[j].value = value; \\\n+\t\t\treturn 1; \\\n+\t\t} \\\n+\t} \\\n+ \\\n+\tm->hash[j].key = key; \\\n+\tm->hash[j].value = value; \\\n+\tm->hash[j].used = 1; \\\n+\tm->nr++; \\\n+\treturn 0; \\\n+} \\\n+ \\\n+static void map_grow_##name(struct map_##name *m) \\\n+{ \\\n+\tstruct map_entry_##name *old_hash = m->hash; \\\n+\tunsigned int old_size = m->size; \\\n+\tunsigned int i; \\\n+ \\\n+\tm->size = (old_size + 1000) * 3 / 2; \\\n+\tm->hash = xcalloc(m->size, sizeof(*m->hash)); \\\n+\tm->nr = 0; \\\n+ \\\n+\tfor (i = 0; i < old_size; i++) { \\\n+\t\tif (!old_hash[i].used) \\\n+\t\t\tcontinue; \\\n+\t\tmap_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \\\n+\t} \\\n+\tfree(old_hash); \\\n+} \\\n+ \\\n+int map_set_##name(struct map_##name *m, \\\n+\t\t const ktype key, \\\n+\t\t vtype value, \\\n+\t\t vtype *old) \\\n+{ \\\n+\tif (m->nr >= m->size * 2 / 3) \\\n+\t\tmap_grow_##name(m); \\\n+\treturn map_insert_##name(m, key, value, old); \\\n+} \\\n+ \\\n+int map_get_##name(struct map_##name *m, \\\n+\t\t const ktype key, \\\n+\t\t vtype *value) \\\n+{ \\\n+\tunsigned int j; \\\n+ \\\n+\tif (!m->size) \\\n+\t\treturn 0; \\\n+ \\\n+\tfor (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \\\n+\t\tif (cmp_fun(m->hash[j].key, key)) { \\\n+\t\t\t*value = m->hash[j].value; \\\n+\t\t\treturn 1; \\\n+\t\t} \\\n+\t} \\\n+\treturn 0; \\\n+}\ndiff --git a/map.h b/map.h\nnew file mode 100644\nindex 0000000..496c5d1\n--- /dev/null\n+++ b/map.h\n@@ -0,0 +1,24 @@\n+#ifndef MAP_H\n+#define MAP_H\n+\n+#define DECLARE_MAP(name, ktype, vtype) \\\n+struct map_entry_##name { \\\n+\tconst ktype key; \\\n+\tvtype value; \\\n+\tunsigned used:1; \\\n+}; \\\n+ \\\n+struct map_##name { \\\n+\tunsigned int size, nr; \\\n+\tstruct map_entry_##name *hash; \\\n+}; \\\n+ \\\n+extern int map_get_##name(struct map_##name *, \\\n+\t\t\t const ktype key, \\\n+\t\t\t vtype *value); \\\n+extern int map_set_##name(struct map_##name *, \\\n+\t\t\t const ktype key, \\\n+\t\t\t vtype value, \\\n+\t\t\t vtype *old); \\\n+\n+#endif /* MAP_H */\n-- \n1.7.6.38.ge5b33\n"},{"id":"171348","messageId":"20110714175211.GB21771@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110714173454.GA21657@sigill.intra.peff.net","subject":"[PATCH 2/3] fast-export: use object to uint32 map instead of \"decorate\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T17:52:11Z","receivedAt":"2011-07-14T17:52:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Previously we encoded the \"mark\" mapping inside the \"void *\"\nfield of a \"struct decorate\". It's a little more natural for\nus to do so using a data structure made for holding actual\nvalues.\n\nSigned-off-by: Jeff King \n---\nAnd this is an example of use. It doesn't save all that much code, but I\nthink it's a little more natural. It can also save some bytes of the hash\nvalue in each entry if your pointers are larger than 32-bit.\n\n builtin/fast-export.c | 36 +++++++++++-------------------------\n map.c | 2 ++\n map.h | 2 ++\n 3 files changed, 15 insertions(+), 25 deletions(-)\n\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex daf1945..fd50503 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -12,7 +12,7 @@\n #include \"diffcore.h\"\n #include \"log-tree.h\"\n #include \"revision.h\"\n-#include \"decorate.h\"\n+#include \"map.h\"\n #include \"string-list.h\"\n #include \"utf8.h\"\n #include \"parse-options.h\"\n@@ -59,7 +59,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,\n \treturn 0;\n }\n \n-static struct decoration idnums;\n+static struct map_object_uint32 idnums;\n static uint32_t last_idnum;\n \n static int has_unshown_parent(struct commit *commit)\n@@ -73,20 +73,9 @@ static int has_unshown_parent(struct commit *commit)\n \treturn 0;\n }\n \n-/* Since intptr_t is C99, we do not use it here */\n-static inline uint32_t *mark_to_ptr(uint32_t mark)\n-{\n-\treturn ((uint32_t *)NULL) + mark;\n-}\n-\n-static inline uint32_t ptr_to_mark(void * mark)\n-{\n-\treturn (uint32_t *)mark - (uint32_t *)NULL;\n-}\n-\n static inline void mark_object(struct object *object, uint32_t mark)\n {\n-\tadd_decoration(&idnums, object, mark_to_ptr(mark));\n+\tmap_set_object_uint32(&idnums, object, mark, NULL);\n }\n \n static inline void mark_next_object(struct object *object)\n@@ -96,10 +85,9 @@ static inline void mark_next_object(struct object *object)\n \n static int get_object_mark(struct object *object)\n {\n-\tvoid *decoration = lookup_decoration(&idnums, object);\n-\tif (!decoration)\n-\t\treturn 0;\n-\treturn ptr_to_mark(decoration);\n+\tuint32_t ret = 0;\n+\tmap_get_object_uint32(&idnums, object, &ret);\n+\treturn ret;\n }\n \n static void show_progress(void)\n@@ -537,8 +525,7 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)\n static void export_marks(char *file)\n {\n \tunsigned int i;\n-\tuint32_t mark;\n-\tstruct object_decoration *deco = idnums.hash;\n+\tstruct map_entry_object_uint32 *map = idnums.hash;\n \tFILE *f;\n \tint e = 0;\n \n@@ -547,15 +534,14 @@ static void export_marks(char *file)\n \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n \n \tfor (i = 0; i < idnums.size; i++) {\n-\t\tif (deco->base && deco->base->type == 1) {\n-\t\t\tmark = ptr_to_mark(deco->decoration);\n-\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n-\t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n+\t\tif (map->used && map->key->type == 1) {\n+\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", map->value,\n+\t\t\t\tsha1_to_hex(map->key->sha1)) < 0) {\n \t\t\t e = 1;\n \t\t\t break;\n \t\t\t}\n \t\t}\n-\t\tdeco++;\n+\t\tmap++;\n \t}\n \n \te |= ferror(f);\ndiff --git a/map.c b/map.c\nindex 378cecb..28f885e 100644\n--- a/map.c\n+++ b/map.c\n@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \\\n \t} \\\n \treturn 0; \\\n }\n+\n+MAP_IMPLEMENT(object_uint32, struct object *, uint32_t, cmp_obj, hash_obj)\ndiff --git a/map.h b/map.h\nindex 496c5d1..e80d85d 100644\n--- a/map.h\n+++ b/map.h\n@@ -21,4 +21,6 @@ extern int map_set_##name(struct map_##name *, \\\n \t\t\t vtype value, \\\n \t\t\t vtype *old); \\\n \n+DECLARE_MAP(object_uint32, struct object *, uint32_t)\n+\n #endif /* MAP_H */\n-- \n1.7.6.38.ge5b33\n"},{"id":"171349","messageId":"20110714175348.GC21771@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110714173454.GA21657@sigill.intra.peff.net","subject":"[PATCH 3/3] decorate: use \"map\" for the underlying implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T17:53:48Z","receivedAt":"2011-07-14T17:53:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The decoration API maps objects to void pointers. This is a\nsubset of what the map API is capable of, so let's get rid\nof the duplicate implementation.\n\nWe could just fix all callers of decorate to call the map\nAPI directly. However, the map API is very generic since it\nis meant to handle any type. In particular, it can't use\nsentinel values like \"NULL\" to indicate \"entry not found\"\n(since it doesn't know whether the type can represent such a\nsentinel value).\n\nInstead, the decorate API just becomes a set of wrappers,\nand no callers need to be updated at all.\n\nSigned-off-by: Jeff King \n---\nThe result should perform identically to the existing decorate code with\nthe exception of the extra \"used\" field, which makes each hash entry\nbigger (see the comments in patch 1/3).\n\n decorate.c | 105 ++++++++++--------------------------------------------------\n decorate.h | 10 ++----\n map.c | 1 +\n map.h | 1 +\n 4 files changed, 22 insertions(+), 95 deletions(-)\n rewrite decorate.c (89%)\n\ndiff --git a/decorate.c b/decorate.c\ndissimilarity index 89%\nindex 2f8a63e..31e9656 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -1,88 +1,17 @@\n-/*\n- * decorate.c - decorate a git object with some arbitrary\n- * data.\n- */\n-#include \"cache.h\"\n-#include \"object.h\"\n-#include \"decorate.h\"\n-\n-static unsigned int hash_obj(const struct object *obj, unsigned int n)\n-{\n-\tunsigned int hash;\n-\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n-}\n-\n-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n-{\n-\tint size = n->size;\n-\tstruct object_decoration *hash = n->hash;\n-\tunsigned int j = hash_obj(base, size);\n-\n-\twhile (hash[j].base) {\n-\t\tif (hash[j].base == base) {\n-\t\t\tvoid *old = hash[j].decoration;\n-\t\t\thash[j].decoration = decoration;\n-\t\t\treturn old;\n-\t\t}\n-\t\tif (++j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j].base = base;\n-\thash[j].decoration = decoration;\n-\tn->nr++;\n-\treturn NULL;\n-}\n-\n-static void grow_decoration(struct decoration *n)\n-{\n-\tint i;\n-\tint old_size = n->size;\n-\tstruct object_decoration *old_hash = n->hash;\n-\n-\tn->size = (old_size + 1000) * 3 / 2;\n-\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n-\tn->nr = 0;\n-\n-\tfor (i = 0; i < old_size; i++) {\n-\t\tconst struct object *base = old_hash[i].base;\n-\t\tvoid *decoration = old_hash[i].decoration;\n-\n-\t\tif (!base)\n-\t\t\tcontinue;\n-\t\tinsert_decoration(n, base, decoration);\n-\t}\n-\tfree(old_hash);\n-}\n-\n-/* Add a decoration pointer, return any old one */\n-void *add_decoration(struct decoration *n, const struct object *obj,\n-\t\tvoid *decoration)\n-{\n-\tint nr = n->nr + 1;\n-\n-\tif (nr > n->size * 2 / 3)\n-\t\tgrow_decoration(n);\n-\treturn insert_decoration(n, obj, decoration);\n-}\n-\n-/* Lookup a decoration pointer */\n-void *lookup_decoration(struct decoration *n, const struct object *obj)\n-{\n-\tunsigned int j;\n-\n-\t/* nothing to lookup */\n-\tif (!n->size)\n-\t\treturn NULL;\n-\tj = hash_obj(obj, n->size);\n-\tfor (;;) {\n-\t\tstruct object_decoration *ref = n->hash + j;\n-\t\tif (ref->base == obj)\n-\t\t\treturn ref->decoration;\n-\t\tif (!ref->base)\n-\t\t\treturn NULL;\n-\t\tif (++j == n->size)\n-\t\t\tj = 0;\n-\t}\n-}\n+#include \"cache.h\"\n+#include \"decorate.h\"\n+\n+void *add_decoration(struct decoration *n, const struct object *obj,\n+\t\t void *decoration)\n+{\n+\tvoid *ret = NULL;\n+\tmap_set_object_void(&n->map, obj, decoration, &ret);\n+\treturn ret;\n+}\n+\n+void *lookup_decoration(struct decoration *n, const struct object *obj)\n+{\n+\tvoid *ret = NULL;\n+\tmap_get_object_void(&n->map, obj, &ret);\n+\treturn ret;\n+}\ndiff --git a/decorate.h b/decorate.h\nindex e732804..6a3adcd 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -1,15 +1,11 @@\n #ifndef DECORATE_H\n #define DECORATE_H\n \n-struct object_decoration {\n-\tconst struct object *base;\n-\tvoid *decoration;\n-};\n+#include \"map.h\"\n \n struct decoration {\n-\tconst char *name;\n-\tunsigned int size, nr;\n-\tstruct object_decoration *hash;\n+\tchar *name;\n+\tstruct map_object_void map;\n };\n \n extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);\ndiff --git a/map.c b/map.c\nindex 28f885e..93e0364 100644\n--- a/map.c\n+++ b/map.c\n@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \\\n }\n \n MAP_IMPLEMENT(object_uint32, struct object *, uint32_t, cmp_obj, hash_obj)\n+MAP_IMPLEMENT(object_void, struct object *, void *, cmp_obj, hash_obj)\ndiff --git a/map.h b/map.h\nindex e80d85d..737054e 100644\n--- a/map.h\n+++ b/map.h\n@@ -22,5 +22,6 @@ extern int map_set_##name(struct map_##name *, \\\n \t\t\t vtype *old); \\\n \n DECLARE_MAP(object_uint32, struct object *, uint32_t)\n+DECLARE_MAP(object_void, struct object *, void *)\n \n #endif /* MAP_H */\n-- \n1.7.6.38.ge5b33\n"},{"id":"171358","messageId":"CAKPyHN0-VbzjMaMJFZeGGrGX6HuGNEBHNVNf0cexB2vu21_13g@mail.gmail.com","threadId":"27801","inReplyTo":"20110714175105.GA21771@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-14T18:52:04Z","receivedAt":"2011-07-14T18:52:04Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Thu, Jul 14, 2011 at 19:51, Jeff King wrote:\n> It is frequently useful to have a fast, generic data\n> structure mapping keys to values. We already have something\n> like this in the \"decorate\" API, but it has two downsides:\n>\n>  1. The key type must always be a \"struct object *\".\n>\n>  2. The value type is a void pointer, which means it is\n>     inefficient and cumbersome for storing small values.\n>     One must either encode their value inside the void\n>     pointer, or allocate additional storage for the pointer\n>     to point to.\n>\n> This patch introduces a generic map data structure, mapping\n> keys of arbitrary type to values of arbitrary type.\n>\n> One possible strategy for implementation is to have a struct\n> that points to a sequence of bytes for each of the key and\n> the value, and to try to treat them as opaque in the code.\n> However, this code gets complex, has a lot of casts, and\n> runs afoul of violating alignment and strict aliasing rules.\n>\n> This patch takes a different approach. We parameterize the\n> types in each map by putting the declarations and\n> implementations inside macros, and expand the macros with\n> the correct types. This lets the compiler see the actual\n> code, with its real types, and figure out things like struct\n> packing and alignment itself.\n>\n> Signed-off-by: Jeff King \n> ---\n> In addition to switching from using void pointers to macro expansion,\n> this has one other difference from my previous patch: it handles\n> arbitrary types for keys, not just object pointers. This was mentioned\n> by Jakub, and would allow things like a fast bi-directional map for SVN\n> revision numbers and commits.\n>\n> I tried to keep the implementation simple. Two things that could be changed:\n>\n>  1. We can't assume that the map key is a pointer. So the sentinel\n>     \"NULL\" value isn't necessarily available to use, and we have to\n>     keep a separate bit in each hash entry to say \"is this valid\".\n>     This means when we _do_ store a pointer, we end up with an extra\n>     32 bits or so in each hash entry for the \"used\" flag.\n>\n>     We could add a macro parameter for sentinel values, so that types\n>     which _can_ handle this efficiently don't have to pay the price.\n>     Or we could decide that mapping arbitrary keys isn't worth the\n>     hassle. I wrote this way to be flexible for future use; I don't\n>     personally have plans to add svn revision number mappings.\n>\n>  2. It assumes values are assignable. That means storing something like\n>     \"unsigned char sha1[20]\" doesn't work. You can wrap it in a struct,\n>     but do we assume that struct assignment works everywhere? I didn't\n>     check, but I think it is in C89 but some antique compilers didn't\n>     allow it. Switching it to use memcpy() would be easy enough (or\n>     again, parameterizing so that assignable things don't have to pay\n>     the price).\n>\n>  Makefile |    2 +\n>  map.c    |   86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  map.h    |   24 +++++++++++++++++\n>  3 files changed, 112 insertions(+), 0 deletions(-)\n>  create mode 100644 map.c\n>  create mode 100644 map.h\n>\n> diff --git a/Makefile b/Makefile\n> index 46793d1..6242321 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -530,6 +530,7 @@ LIB_H += list-objects.h\n>  LIB_H += ll-merge.h\n>  LIB_H += log-tree.h\n>  LIB_H += mailmap.h\n> +LIB_H += map.h\n>  LIB_H += merge-file.h\n>  LIB_H += merge-recursive.h\n>  LIB_H += notes.h\n> @@ -621,6 +622,7 @@ LIB_OBJS += ll-merge.o\n>  LIB_OBJS += lockfile.o\n>  LIB_OBJS += log-tree.o\n>  LIB_OBJS += mailmap.o\n> +LIB_OBJS += map.o\n>  LIB_OBJS += match-trees.o\n>  LIB_OBJS += merge-file.o\n>  LIB_OBJS += merge-recursive.o\n> diff --git a/map.c b/map.c\n> new file mode 100644\n> index 0000000..378cecb\n> --- /dev/null\n> +++ b/map.c\n> @@ -0,0 +1,86 @@\n> +#include \"cache.h\"\n> +#include \"map.h\"\n> +#include \"object.h\"\n> +\n> +static unsigned int hash_obj(const struct object *obj, unsigned int n)\n> +{\n> +       unsigned int hash;\n> +\n> +       memcpy(&hash, obj->sha1, sizeof(unsigned int));\n> +       return hash % n;\n> +}\n> +\n> +static unsigned int cmp_obj(const struct object *a, const struct object *b)\n> +{\n> +       return b == a;\n> +}\n> +\n> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \\\n\nThis define should probably in the header too. Else this is completely useless.\n\nBert\n"},{"id":"171360","messageId":"CAKPyHN3G41iMGmGgp6jTcWN=Rxt=RTUS7ktgVDhZEXPBRXvTDQ@mail.gmail.com","threadId":"27801","inReplyTo":"CAKPyHN0-VbzjMaMJFZeGGrGX6HuGNEBHNVNf0cexB2vu21_13g@mail.gmail.com","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-14T18:54:07Z","receivedAt":"2011-07-14T18:54:07Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Thu, Jul 14, 2011 at 20:52, Bert Wesarg wrote:\n> On Thu, Jul 14, 2011 at 19:51, Jeff King wrote:\n>> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \\\n>\n> This define should probably in the header too. Else this is completely useless.\n\nAhh. One have to read patch 2/3, to see how to use this. Please feel\nfree to ignore this than.\n\n>\n> Bert\n>\n"},{"id":"171361","messageId":"20110714185539.GA27141@sigill.intra.peff.net","threadId":"27801","inReplyTo":"CAKPyHN3G41iMGmGgp6jTcWN=Rxt=RTUS7ktgVDhZEXPBRXvTDQ@mail.gmail.com","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T18:55:39Z","receivedAt":"2011-07-14T18:55:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 14, 2011 at 08:54:07PM +0200, Bert Wesarg wrote:\n\n> On Thu, Jul 14, 2011 at 20:52, Bert Wesarg wrote:\n> > On Thu, Jul 14, 2011 at 19:51, Jeff King wrote:\n> >> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \\\n> >\n> > This define should probably in the header too. Else this is completely useless.\n> \n> Ahh. One have to read patch 2/3, to see how to use this. Please feel\n> free to ignore this than.\n\nYeah, you could treat this like a C++ template and assume random bits of\ncode will instantiate a map of whatever types they need. But this is C,\nand we only want to instantiate once. So I just figured to keep the\nstatic list of whatever maps git needs in the map.[ch] files.\n\n-Peff\n"},{"id":"171363","messageId":"CAKPyHN3VV4bmy2CF9vPsRG82EapFtUOCXNYO=mVAJs54QG===g@mail.gmail.com","threadId":"27801","inReplyTo":"20110714185539.GA27141@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-14T19:07:54Z","receivedAt":"2011-07-14T19:07:54Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Thu, Jul 14, 2011 at 20:55, Jeff King wrote:\n> On Thu, Jul 14, 2011 at 08:54:07PM +0200, Bert Wesarg wrote:\n>\n>> On Thu, Jul 14, 2011 at 20:52, Bert Wesarg wrote:\n>> > On Thu, Jul 14, 2011 at 19:51, Jeff King wrote:\n>> >> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \\\n>> >\n>> > This define should probably in the header too. Else this is completely useless.\n>>\n>> Ahh. One have to read patch 2/3, to see how to use this. Please feel\n>> free to ignore this than.\n>\n> Yeah, you could treat this like a C++ template and assume random bits of\n> code will instantiate a map of whatever types they need. But this is C,\n> and we only want to instantiate once. So I just figured to keep the\n> static list of whatever maps git needs in the map.[ch] files.\n\nWhen I wrote such macros in the past, the 'generated' functions where\nall static. So one could instantiate a map multiple times in different\ncompilation units where one need to access this type of map.\n\nBut I'm perfectly fine with your way, which is new to me.\n\nBert\n\n>\n> -Peff\n>\n"},{"id":"171368","messageId":"20110714191416.GC26918@sigill.intra.peff.net","threadId":"27801","inReplyTo":"CAKPyHN3VV4bmy2CF9vPsRG82EapFtUOCXNYO=mVAJs54QG===g@mail.gmail.com","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-14T19:14:16Z","receivedAt":"2011-07-14T19:14:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 14, 2011 at 09:07:54PM +0200, Bert Wesarg wrote:\n\n> > Yeah, you could treat this like a C++ template and assume random bits of\n> > code will instantiate a map of whatever types they need. But this is C,\n> > and we only want to instantiate once. So I just figured to keep the\n> > static list of whatever maps git needs in the map.[ch] files.\n> \n> When I wrote such macros in the past, the 'generated' functions where\n> all static. So one could instantiate a map multiple times in different\n> compilation units where one need to access this type of map.\n\nYeah, that would work. It can bloat the code more, but in practice, not\nmuch. It would also work better if we were providing the map API as a\nlibrary to arbitrary code. But we have the luxury of knowing all of the\ntypes that will be used with it at compile time. :)\n\n-Peff\n"},{"id":"171369","messageId":"CAKPyHN03dvnwZ6O=kROSWpMVtBc4ifwKqboGt0rKo_r0x-bFXg@mail.gmail.com","threadId":"27801","inReplyTo":"20110714191416.GC26918@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] implement generic key/value map","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2011-07-14T19:18:40Z","receivedAt":"2011-07-14T19:18:40Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Thu, Jul 14, 2011 at 21:14, Jeff King wrote:\n> Yeah, that would work. It can bloat the code more, but in practice, not\n> much. It would also work better if we were providing the map API as a\n> library to arbitrary code. But we have the luxury of knowing all of the\n> types that will be used with it at compile time. :)\n\nRight, my thinking was more in the library world back than.\n\nBert\n\n>\n> -Peff\n>\n"},{"id":"171383","messageId":"7vipr4373f.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110714173454.GA21657@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-14T21:06:28Z","receivedAt":"2011-07-14T21:06:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Doing macro meta-programming like this makes me feel a little dirty, but\n> I actually think the result is more readable.\n>\n> [1/3]: implement generic key/value map\n> [2/3]: fast-export: use object to uint32 map instead of \"decorate\"\n> [3/3]: decorate: use \"map\" for the underlying implementation\n>\n> What do you think?\n\nYeah, dirty but nice ;-)\n"},{"id":"171402","messageId":"CAGdFq_guf8fa014t17KyNoEzpCAK-aG5BrpQ40tQ=1507OJ8bw@mail.gmail.com","threadId":"27801","inReplyTo":"20110714175211.GB21771@sigill.intra.peff.net","subject":"Re: [PATCH 2/3] fast-export: use object to uint32 map instead of \"decorate\"","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2011-07-15T09:40:02Z","receivedAt":"2011-07-15T09:40:02Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Thu, Jul 14, 2011 at 19:52, Jeff King wrote:\n> Previously we encoded the \"mark\" mapping inside the \"void *\"\n> field of a \"struct decorate\". It's a little more natural for\n> us to do so using a data structure made for holding actual\n> values.\n>\n> Signed-off-by: Jeff King \n> ---\n> And this is an example of use. It doesn't save all that much code, but I\n> think it's a little more natural. It can also save some bytes of the hash\n> value in each entry if your pointers are larger than 32-bit.\n\nDid you run any benchmarks on this?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"171412","messageId":"7vpqlb1k1g.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110713070644.GF18566@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-15T18:22:03Z","receivedAt":"2011-07-15T18:22:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> diff --git a/builtin/tag.c b/builtin/tag.c\n> index 63bce6e..df6de47 100644\n> --- a/builtin/tag.c\n> +++ b/builtin/tag.c\n> @@ -40,7 +40,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n> }\n> \n> static int contains_recurse(struct commit *candidate,\n> -\t\t\t const struct commit_list *want)\n> +\t\t\t const struct commit_list *want,\n> +\t\t\t unsigned long cutoff)\n> {\n> \tstruct commit_list *p;\n> \n> @@ -57,9 +58,13 @@ static int contains_recurse(struct commit *candidate,\n> \tif (parse_commit(candidate) < 0)\n> \t\treturn 0;\n> \n> +\t/* stop searching if we go too far back in time */\n> +\tif (commit_generation(candidate) < cutoff)\n> +\t\treturn 0;\n> +\n\nHere, the \"generation number\" was the commit timestamp of the commit in\nyour earlier round, but now it is not.\n\nI agree with Linus that for the purpose of \"rev-list A ^B ^C\" computation,\n\"generation number\" is a much better thing to use than the commit\ntimestamp, and I also think if we want to revamp the codepath around\nstill_interesting() in revision.c, Linus's \"let's add generation header in\nnew commits\" is a good first step. I haven't stared at that codepath long\nenough lately to say for sure, but I suspect that in that codepath we\ncould use generation number in commits when available and fall back to\ntimestamp with slop without recomputing the generation number and caching\nfor older commits.\n\nBut that is _not_ the codepath your series is about.\n\nWhat you are trying to say in this series is that \"If a tag points at a\ncommit X (i.e. candidate), another commit Y (i.e. \"want\") that is much\nyounger than cannot possibly be included by it, because a tag was made on\ncommit X way before Y was created\". You cut off by \"age\".\n\nThe heuristics would work efficiently to check what tags point at a\nrelatively recent commit (e.g. when trying to see which releases are\naffected and needing a fix by a recently discovered bug introduced by\ncommit Y) by discarding tags for ancient releases. In such a scenario, the\ntimestamp of a tagged and ancient commit X on a side branch that was never\nmerged in the mainline that leads to commit Y (i.e. \"want\"), in an ideal\nworld without clock skews, will be way older than the timestamp of commit\nY. In other words, if you use timestamp as \"age\", even though X and Y do\nnot relate to each other directly, except that they may share an ancient\ncommon ancestor, their \"age\"s can be compared and you could apply your\nheuristics to optimize.\n\nBut if you use the generation number as \"age\", even in an ideal world\nwithout clock skew nor miscomputed generation number, you no longer can\ncompare \"age\" of X and Y. The ancient side branch that led to X may have\ntons more commits than the history leading to Y.\n\nSo I have two tangents here.\n\n * As to revision traversal, the reason we do the SLOP in\n still_interesting() is to avoid the issue arising from the following\n topology:\n\n 5\n /\n ---2---4---...---1\n \\\n 3---6\n\n where numbers denote the timestamp of the commit (1 incorrectly records\n ancient timestamp, while everybody else has newer timestamp than its\n parents). When we try to \"rev-list 5 --not 1 6\", we start from having\n ~1, ~6 and 5 to \"currently active\" list, and iteratively pick more\n recent commits from the active list to dig deeper while newly found\n ancestors back to the active list. ~6 leads to 3 marked as\n uninteresting and active list gets ~3 while ~6 is removed. 5 leads to 4\n marked as interesting and 4 gets inserted in the list while 5 is\n removed. 4 finds 2 to also be interesting. Then ~3 finds 2 to be\n uninteresting. At that point, we have ~1 (still not processed) and ~2\n in the active list, while we have 5 and 4 in the result list. We need\n to dig through ~1 to realize that 4 is reachable from it to mark it\n uninteresting.\n\n So how about marking commits (using the metainfo-cache facility) that\n has an ancestor (not necessarily its direct parent) that records a\n younger timestamp (e.g. 1 is such a commit, as its ancestors include\n things like 2 and 4)? There should be relatively small number of them,\n and still_interesting() logic can be told to dig through such commits\n even if everybody is uninteresting in the active list.\n\n * As to \"tag --contains\", when timestamp based heuristics breaks down is\n when a tagged commit incorrectly records way young timestamp or the\n \"want\" commit records way old timetsamp. I haven't thought things\n through, but the same metainfo-cache may be useful to detect which\n commit to dig through ignoring the cutoff heuristics.\n"},{"id":"171427","messageId":"20110715200044.GB356@sigill.intra.peff.net","threadId":"27801","inReplyTo":"CAGdFq_guf8fa014t17KyNoEzpCAK-aG5BrpQ40tQ=1507OJ8bw@mail.gmail.com","subject":"Re: [PATCH 2/3] fast-export: use object to uint32 map instead of \"decorate\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-15T20:00:44Z","receivedAt":"2011-07-15T20:00:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 15, 2011 at 11:40:02AM +0200, Sverre Rabbelier wrote:\n\n> On Thu, Jul 14, 2011 at 19:52, Jeff King wrote:\n> > Previously we encoded the \"mark\" mapping inside the \"void *\"\n> > field of a \"struct decorate\". It's a little more natural for\n> > us to do so using a data structure made for holding actual\n> > values.\n> >\n> > Signed-off-by: Jeff King \n> > ---\n> > And this is an example of use. It doesn't save all that much code, but I\n> > think it's a little more natural. It can also save some bytes of the hash\n> > value in each entry if your pointers are larger than 32-bit.\n> \n> Did you run any benchmarks on this?\n\nNo, I didn't. I expect it to be exactly the same on x86_64. We save\n32-bits of pointer space, but the generality I mentioned in patch 1\nwastes 32-bits of space for the \"used\" flag. So it evens out,\nspace-wise.\n\nThe time complexity should be exactly the same (the macro definitions\nare more or less the exact decorate code, but with the types\nparameterized, so the generated code should be the same).\n\nBut I'm not sure this code is going to end up used, anyway. It looks\nlike we might add a generation header after all.\n\n-Peff\n"},{"id":"171433","messageId":"20110715204002.GC356@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vpqlb1k1g.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-15T20:40:02Z","receivedAt":"2011-07-15T20:40:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 15, 2011 at 11:22:03AM -0700, Junio C Hamano wrote:\n\n> > +\t/* stop searching if we go too far back in time */\n> > +\tif (commit_generation(candidate) < cutoff)\n> > +\t\treturn 0;\n> > +\n> \n> Here, the \"generation number\" was the commit timestamp of the commit in\n> your earlier round, but now it is not.\n\nYes.\n\n> [...]\n> What you are trying to say in this series is that \"If a tag points at a\n> commit X (i.e. candidate), another commit Y (i.e. \"want\") that is much\n> younger than cannot possibly be included by it, because a tag was made on\n> commit X way before Y was created\". You cut off by \"age\".\n\nMore or less. Given two ages, X and Y, you cannot know right off the bat\nwhether one is an ancestor of the other. You can only know that the\nhigher generation cannot possibly be an ancestor of the lower\ngeneration.\n\nSo yes, in some cases we will see that the tag has generation 5, and the\n\"want\" commit has generation 10, and we will know there is no point in\ntraversing backwards from 5.\n\nBut we may also see a tag with generation 10, and a want commit with\ngeneration 5. In that case, we have to explore backwards, looking to\neither find the commit, or to pass a point where we hit a commit with\ngeneration less than 5, at which point we know the want commit cannot be\nan ancestor.\n\nSo if you have a history like:\n\n B\n /\n A--C--D--...--Z\n\nand you want to know if \"B\" is in \"Z\", you will have to traverse all the\nway from Z to A before realizing that B cannot be in it. That will have\nthe same complexity as finding a merge base (because the merge-base\nwould breadth-first traverse, looking at the highest age first, and\nwould therefore touch the same sequence of commits).\n\n> The heuristics would work efficiently to check what tags point at a\n> relatively recent commit (e.g. when trying to see which releases are\n> affected and needing a fix by a recently discovered bug introduced by\n> commit Y) by discarding tags for ancient releases. In such a scenario, the\n> timestamp of a tagged and ancient commit X on a side branch that was never\n> merged in the mainline that leads to commit Y (i.e. \"want\"), in an ideal\n> world without clock skews, will be way older than the timestamp of commit\n> Y. In other words, if you use timestamp as \"age\", even though X and Y do\n> not relate to each other directly, except that they may share an ancient\n> common ancestor, their \"age\"s can be compared and you could apply your\n> heuristics to optimize.\n> \n> But if you use the generation number as \"age\", even in an ideal world\n> without clock skew nor miscomputed generation number, you no longer can\n> compare \"age\" of X and Y. The ancient side branch that led to X may have\n> tons more commits than the history leading to Y.\n\nYes, there are cases where commit timestamps can save us some traversal\nwork over generation numbers. But I think there are also cases where the\nreverse is true.\n\nYour example is of a long side branch with very old commits. But you\ncould also have a short side branch with a very recent commit (think\nrecent bugfix forked from an old version). Then with commit timestamps\nwe need to go to the merge base to realize we are talking about\nsomething very old. With a generation number, you can easily see that\nthe short branch's generation is very low.\n\nUsing both as a cutoff (if we assumed we had both, and that they were\nboth implicitly accurate) would let you optimize for either situation.\nIn practice, timestamps are either good enough that we don't need\ngeneration numbers, or are considered to be strictly less accurate than\ngeneration numbers.\n\nSo I think we will end up with one or the other. Of all of the\ncomplaints I have seen over the use of timestamps for cutoffs, I don't\nthink performance of these corner cases has been an issue.\n\n> So how about marking commits (using the metainfo-cache facility) that\n> has an ancestor (not necessarily its direct parent) that records a\n> younger timestamp (e.g. 1 is such a commit, as its ancestors include\n> things like 2 and 4)? There should be relatively small number of them,\n> and still_interesting() logic can be told to dig through such commits\n> even if everybody is uninteresting in the active list.\n\nYou don't even need metainfo-cache for this. The number of commits is\nvery small, so the existing \"notes-cache\" is plenty fast. I even posted\na patch for this already:\n\n http://article.gmane.org/gmane.comp.version-control.git/176642\n\n> * As to \"tag --contains\", when timestamp based heuristics breaks down is\n> when a tagged commit incorrectly records way young timestamp or the\n> \"want\" commit records way old timetsamp. I haven't thought things\n> through, but the same metainfo-cache may be useful to detect which\n> commit to dig through ignoring the cutoff heuristics.\n\nIt can also break down if intermediate commits are wrong, because we\nhave to traverse backwards, and we may erroneously cutoff early.\n\nFor example:\n\n A--B--C\n\n timestamp(A) = 2\n timestamp(B) = 1 # skewed!\n timestamp(C) = 3\n\nIf tag=C and want=A, then we traverse backwards from C. We can't stop\nimmediately because we know that 2 < 3. But we go back to B, and see\nthat 2 > 1, and assume that A cannot possibly be an ancestor of B.\n\nYou can push through another N commits of slop (where N=1 would be fine\nin this case). But you can always have a run of N+1 skewed commits (and\nthe higher N, the more time you are wasting). From earlier measurements\nposted to the list, most repos have runs less than a dozen commits.\nLinux-2.6 is actually the second highest of those measured, with a run\nof 80. The mesa repo apparently has a run of 1520. See:\n\n http://article.gmane.org/gmane.comp.version-control.git/160163\n\nand the surrounding thread (Jonathan did some measurements, too; he\ndidn't include a \"longest run\", but he does include \"total number of\nskewed commits\", which obviously provides an upper bound on a run).\n\n-Peff\n"},{"id":"171435","messageId":"m3aacf9s4k.fsf@localhost.localdomain","threadId":"27801","inReplyTo":"20110713064709.GA18499@sigill.intra.peff.net","subject":"Generation numbers and replacement objects","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-15T21:01:36Z","receivedAt":"2011-07-15T21:01:36Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"[Sorry for sending this email like this, but I forgot where\n I wanted to attach it to threads]\n\nPeff, as Junio said somewhere else either in this thread, or the one\nstarted by Linus, we would want generation numbers both without taking\ninto account replacement objects (e.g. for object traversal during\npush / fetch), and with taking it into account (e.g. when showing log\nor blame for end user).\n\nSo we would need two generation number caches: one with and one\nwithout replaces. Nb. generation header stored in commit object can\ngive only the one without replaces, i.e. speed up object enumeration\n(what happened to caching GSoC project code?) but not git-log.\n\nAlso if replacement object has the same generation as the commit it\nreplaces, and I think also if it has lower generation number, current\ngeneration numbers would still work (ne need to invalidate cache).\n\n-- \nJakub Narebski\n"},{"id":"171436","messageId":"7vzkkfz261.fsf@alter.siamese.dyndns.org","threadId":"27801","inReplyTo":"20110715204002.GC356@sigill.intra.peff.net","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-15T21:04:06Z","receivedAt":"2011-07-15T21:04:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> So how about marking commits (using the metainfo-cache facility) that\n>> has an ancestor (not necessarily its direct parent) that records a\n>> younger timestamp (e.g. 1 is such a commit, as its ancestors include\n>> things like 2 and 4)? There should be relatively small number of them,\n>> and still_interesting() logic can be told to dig through such commits\n>> even if everybody is uninteresting in the active list.\n> ...\n>> * As to \"tag --contains\", when timestamp based heuristics breaks down is\n>> when a tagged commit incorrectly records way young timestamp or the\n>> \"want\" commit records way old timetsamp. I haven't thought things\n>> through, but the same metainfo-cache may be useful to detect which\n>> commit to dig through ignoring the cutoff heuristics.\n>\n> It can also break down if intermediate commits are wrong, because we\n> have to traverse backwards, and we may erroneously cutoff early.\n>\n> For example:\n>\n> A--B--C\n>\n> timestamp(A) = 2\n> timestamp(B) = 1 # skewed!\n> timestamp(C) = 3\n>\n> If tag=C and want=A, then we traverse backwards from C. We can't stop\n> immediately because we know that 2 < 3. But we go back to B, and see\n> that 2 > 1, and assume that A cannot possibly be an ancestor of B.\n\nI envisioned that the metainfo-cache to help rev-list I mentioned earlier\nwould mark B having an ancestor A that has a timestamp younger than it, so\nI think we can certainly notice that we have to \"dig through\" B.\n"},{"id":"171439","messageId":"20110715211033.GA1943@sigill.intra.peff.net","threadId":"27801","inReplyTo":"m3aacf9s4k.fsf@localhost.localdomain","subject":"Re: Generation numbers and replacement objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-15T21:10:33Z","receivedAt":"2011-07-15T21:10:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 15, 2011 at 02:01:36PM -0700, Jakub Narebski wrote:\n\n> Peff, as Junio said somewhere else either in this thread, or the one\n> started by Linus, we would want generation numbers both without taking\n> into account replacement objects (e.g. for object traversal during\n> push / fetch), and with taking it into account (e.g. when showing log\n> or blame for end user).\n> \n> So we would need two generation number caches: one with and one\n> without replaces.\n\nRight. And I already outlined a solution for that by indexing the caches\nby the validity token (I haven't written the patches yet, but it's a\npretty trivial change).\n\n> Nb. generation header stored in commit object can give only the one\n> without replaces, i.e. speed up object enumeration (what happened to\n> caching GSoC project code?) but not git-log.\n\nYes. It is a weakness of putting the generation number in the header. I\nthink Linus has already said he doesn't care about grafting. You are\nwelcome to argue with him about that.\n\n> Also if replacement object has the same generation as the commit it\n> replaces, and I think also if it has lower generation number, current\n> generation numbers would still work (ne need to invalidate cache).\n\nYes, that is why I said elsewhere \"you could be more clever about seeing\nhow the cache's validity constraints changed\". But ultimately, it is not\nthat expensive to regenerate the cache under the new conditions, grafts\ndon't change very often, and the code to figure out exactly which parts\nof the cache could be saved would be complex.\n\n-Peff\n"},{"id":"171440","messageId":"20110715211441.GB1943@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vzkkfz261.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv2 6/6] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-15T21:14:41Z","receivedAt":"2011-07-15T21:14:41Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 15, 2011 at 02:04:06PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> So how about marking commits (using the metainfo-cache facility) that\n> >> has an ancestor (not necessarily its direct parent) that records a\n> >> younger timestamp (e.g. 1 is such a commit, as its ancestors include\n> >> things like 2 and 4)? There should be relatively small number of them,\n> >> and still_interesting() logic can be told to dig through such commits\n> >> even if everybody is uninteresting in the active list.\n> > ...\n> >> * As to \"tag --contains\", when timestamp based heuristics breaks down is\n> >> when a tagged commit incorrectly records way young timestamp or the\n> >> \"want\" commit records way old timetsamp. I haven't thought things\n> >> through, but the same metainfo-cache may be useful to detect which\n> >> commit to dig through ignoring the cutoff heuristics.\n> >\n> > It can also break down if intermediate commits are wrong, because we\n> > have to traverse backwards, and we may erroneously cutoff early.\n> >\n> > For example:\n> >\n> > A--B--C\n> >\n> > timestamp(A) = 2\n> > timestamp(B) = 1 # skewed!\n> > timestamp(C) = 3\n> >\n> > If tag=C and want=A, then we traverse backwards from C. We can't stop\n> > immediately because we know that 2 < 3. But we go back to B, and see\n> > that 2 > 1, and assume that A cannot possibly be an ancestor of B.\n> \n> I envisioned that the metainfo-cache to help rev-list I mentioned earlier\n> would mark B having an ancestor A that has a timestamp younger than it, so\n> I think we can certainly notice that we have to \"dig through\" B.\n\nRight. I thought you were talking about the case where we did not have\nsuch a cache. But given your response, did you mean:\n\n If we have such a cache, then the only thing left to worry about is\n when we specifically ask about a commit (either a tag or a \"want\"\n commit) that is skewed.\n\nThat I agree with.\n\n-Peff\n"},{"id":"171490","messageId":"201107162310.26808.jnareb@gmail.com","threadId":"27801","inReplyTo":"20110715211033.GA1943@sigill.intra.peff.net","subject":"Re: Generation numbers and replacement objects","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-16T21:10:25Z","receivedAt":"2011-07-16T21:10:25Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Fri, Jul 15, 2011, Jeff King wrote:\n> On Fri, Jul 15, 2011 at 02:01:36PM -0700, Jakub Narebski wrote:\n> \n> > Peff, as Junio said somewhere else either in this thread, or the one\n> > started by Linus, we would want generation numbers both without taking\n> > into account replacement objects (e.g. for object traversal during\n> > push / fetch), and with taking it into account (e.g. when showing log\n> > or blame for end user).\n> > \n> > So we would need two generation number caches: one with and one\n> > without replaces.\n> \n> Right. And I already outlined a solution for that by indexing the caches\n> by the validity token (I haven't written the patches yet, but it's a\n> pretty trivial change).\n\nActually we wouldn't probably want a separate cache for each validity\ntoken, but two caches: one with and one without... well, perhaps one per\nnamespace. But certainly not one per replacement.\n \n> > Nb. generation header stored in commit object can give only the one\n> > without replaces, i.e. speed up object enumeration (what happened to\n> > caching GSoC project code?) but not git-log.\n> \n> Yes. It is a weakness of putting the generation number in the header. I\n> think Linus has already said he doesn't care about grafting. You are\n> welcome to argue with him about that.\n\nI tried, but he isn't responding to questions about replacement objects.\n\nI can agree that grafts are terrible hack, and for me turning off using\ngeneration numbers if there are grafts is reasonable solution. Not so\nwith replace objects.\n\n> > Also if replacement object has the same generation as the commit it\n> > replaces, and I think also if it has lower generation number, current\n> > generation numbers would still work (ne need to invalidate cache).\n> \n> Yes, that is why I said elsewhere \"you could be more clever about seeing\n> how the cache's validity constraints changed\". But ultimately, it is not\n> that expensive to regenerate the cache under the new conditions, grafts\n> don't change very often, and the code to figure out exactly which parts\n> of the cache could be saved would be complex.\n\nTrue. Well, at least taking hash of only replacements of commit objects\nthat change generation number could be a reasonable thing... but probably\ntoo complicated anyway.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"172948","messageId":"20110804224354.GA27476@sigill.intra.peff.net","threadId":"27801","inReplyTo":"7vipr4373f.fsf@alter.siamese.dyndns.org","subject":"[RFC/PATCH 0/5] macro-based key/value maps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:43:54Z","receivedAt":"2011-08-04T22:43:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 14, 2011 at 02:06:28PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Doing macro meta-programming like this makes me feel a little dirty, but\n> > I actually think the result is more readable.\n> >\n> > [1/3]: implement generic key/value map\n> > [2/3]: fast-export: use object to uint32 map instead of \"decorate\"\n> > [3/3]: decorate: use \"map\" for the underlying implementation\n> >\n> > What do you think?\n> \n> Yeah, dirty but nice ;-)\n\nWell, if you like that, then here is the end-result of what the\npersistent version would look like. It's quite convenient to use, but an\nawful pain to debug. It's done entirely in the preprocessor; I suspect\nif I wrote the code generation externally, that would be easier and more\nreadable (and there are one or two places where we could be slightly\nmore efficient, that are just difficult to implement via the\npreprocessor).\n\n [1/5]: implement generic key/value map\n [2/5]: fast-export: use object to uint32 map instead of \"decorate\"\n [3/5]: decorate: use \"map\" for the underlying implementation\n [4/5]: map: implement persistent maps\n [5/5]: implement metadata cache subsystem\n\n-Peff\n"},{"id":"172949","messageId":"20110804224547.GA27912@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[PATCH 1/5] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:45:48Z","receivedAt":"2011-08-04T22:45:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It is frequently useful to have a fast, generic data\nstructure mapping keys to values. We already have something\nlike this in the \"decorate\" API, but it has two downsides:\n\n 1. The key type must always be a \"struct object *\".\n\n 2. The value type is a void pointer, which means it is\n inefficient and cumbersome for storing small values.\n One must either encode their value inside the void\n pointer, or allocate additional storage for the pointer\n to point to.\n\nThis patch introduces a generic map data structure, mapping\nkeys of arbitrary type to values of arbitrary type.\n\nOne possible strategy for implementation is to have a struct\nthat points to a sequence of bytes for each of the key and\nthe value, and to try to treat them as opaque in the code.\nHowever, this code gets complex, has a lot of casts, and\nruns afoul of violating alignment and strict aliasing rules.\n\nThis patch takes a different approach. We parameterize the\ntypes in each map by putting the declarations and\nimplementations inside macros, and expand the macros with\nthe correct types. This lets the compiler see the actual\ncode, with its real types, and figure out things like struct\npacking and alignment itself.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-map.txt | 160 +++++++++++++++++++++++++++++++++++\n Makefile | 2 +\n map.c | 86 +++++++++++++++++++\n map.h | 26 ++++++\n 4 files changed, 274 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-map.txt\n create mode 100644 map.c\n create mode 100644 map.h\n\ndiff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt\nnew file mode 100644\nindex 0000000..4153ef1\n--- /dev/null\n+++ b/Documentation/technical/api-map.txt\n@@ -0,0 +1,160 @@\n+map API\n+=======\n+\n+The map API is a system for efficiently mapping keys to values in memory. Items\n+are stored in a hash table for fast lookup; storage efficiency is achieved\n+through macro-based code generation, which lets the compiler store values\n+compactly in memory.\n+\n+Due to the code generation, there are two different facets of this API: macros\n+to build new types of mappings (i.e., generate new function and struct\n+definitions), and generated functions to store and retrieve values from a\n+particular mapping.\n+\n+\n+Related APIs\n+------------\n+\n+The hash API provides a similar key/value store. However, it does not deal with\n+hash collisions itself, leaving the caller to handle bucket management (but\n+this is a feature if you are interested in using the collisions as part of an\n+algorithm). Furthermore, it can store only void pointers, making storage of\n+small values inefficient and cumbersome.\n+\n+The decorate API provides a similar interface to map, but is restricted to\n+using \"struct object\" as the key, and a void pointer as the value.\n+\n+\n+Defining New Map Types\n+----------------------\n+\n+A map type is uniquely defined by the pair of its key and value types. To\n+define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the\n+`IMPLEMENT_MAP` macro in `map.c`. Their usage is described below:\n+\n+`DECLARE_MAP`::\n+\n+\tDeclare a new type of map, including the struct definition and\n+\tdeclarations of access functions. The `name` parameter should describe\n+\tthe types (e.g., `object_uint32` to map objects to 32-bit integers).\n+\tThe `ktype` parameter specifies the C type of the key (e.g.,\n+\t`struct object *`) and the `vtype` parameter specifies the C type of\n+\tthe value (e.g., `uint32_t`).\n+\n+`IMPLEMENT_MAP`::\n+\n+\tCreate function definitions for a map type. The `name` parameter should\n+\tmatch one given to `DECLARE_MAP`. The `equal_fun` parameter should\n+\tspecify a function that, when given two items of type `ktype`, will\n+\treturn a non-zero value if they are equal. The `hash_fun` parameter\n+\tshould specify a function that will convert an object of type `ktype`\n+\tinto an integer hash value.\n+\n+Several convenience functions are provided to fill in macro parameters:\n+\n+`hash_obj`::\n+\n+\tSuitable for `hash_fun` when the key type is `struct object *`.\n+\n+`obj_equal`::\n+\n+\tSuitable for `equal_fun` when the key type is `struct object *`.\n+\n+\n+Data Structures\n+---------------\n+\n+Each defined map type will have its own structure (e.g., `map_object_uint32`).\n+\n+`struct map_NAME`::\n+\n+\tA single map object. This struct should be initialized to all-zeroes.\n+\tThe `nr` field specifies the number of items stored in the map. The\n+\t`size` field specifies the number of hash buckets allocated. The `hash`\n+\tfield stores the actual data. Callers should never need to look at\n+\tthese fields unless they are enumerating all elements of the map (see\n+\tthe example below).\n+\n+`struct map_entry_NAME`::\n+\n+\tA single entry in the hash, which may or may not contain a value. If\n+\tthe `used` field is false, the `key` and `value` fields should not be\n+\texamined at all. Otherwise, the `key` and `value` fields represent a\n+\tsingle mapped pair. You should never need to use this type directly,\n+\tunless you are enumerating all elements of a map.\n+\n+\n+Functions\n+---------\n+\n+Each defined map type will have its own set of access function (e.g.,\n+`map_get_object_uint32`).\n+\n+`map_get_NAME(struct map_NAME *, const ktype key, vtype *value)`::\n+\n+\tRetrieve the value corresponding to `key`, returning it via the pointer\n+\t`value`. Returns 1 if an item was found, zero otherwise (in which case\n+\t`value` is unchanged).\n+\n+`map_set_NAME(struct map_NAME *, const ktype key, vtype value, vtype *old)`::\n+\n+\tInsert a mapping from `key` to `value`. If a mapping for `key` already\n+\texisted, the previous value is copied into `old` (if it is non-NULL)\n+\tand the function returns 1. Otherwise, the function returns 0.\n+\n+\n+Examples\n+--------\n+\n+Create a new mapping type of objects to integers:\n+\n+-------------------------------------------------------------------\n+/* in map.h */\n+DECLARE_MAP(object_int, struct object *, int)\n+\n+/* in map.c */\n+IMPLEMENT_MAP(object_int, struct object *, int, obj_equal, hash_obj)\n+-------------------------------------------------------------------\n+\n+Store and retrieve integers by object key:\n+\n+-------------------------------------------------------------------\n+static struct map_object_int foos;\n+\n+void store_foo(const struct commit *c, int foo)\n+{\n+\tint old;\n+\tif (map_set_object_uint32(&foos, &c->object, foo, &old))\n+\t\tprintf(\"old value was %d\\n\", old);\n+}\n+\n+void print_foo(const struct commit *c)\n+{\n+\tint v;\n+\n+\tif (map_get_object_int(&foos, &c->object, &v))\n+\t\tprintf(\"foo: %d\\n\", v);\n+\telse\n+\t\tprintf(\"no such foo\\n\");\n+}\n+-------------------------------------------------------------------\n+\n+Iterate over all map entries:\n+\n+-------------------------------------------------------------------\n+void dump_foos(void)\n+{\n+\tint i;\n+\n+\tprintf(\"there are %u foos:\\n\", foos.nr);\n+\n+\tfor (i = 0; i < foos.size; i++) {\n+\t\tstruct map_entry_object_int *e = foos.hash[i];\n+\n+\t\tif (!e->used)\n+\t\t\tcontinue;\n+\n+\t\tprintf(\"%s -> %d\\n\", sha1_to_hex(e->key->sha1), e->value);\n+\t}\n+}\n+-------------------------------------------------------------------\ndiff --git a/Makefile b/Makefile\nindex 4ed7996..acda5b8 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -533,6 +533,7 @@ LIB_H += list-objects.h\n LIB_H += ll-merge.h\n LIB_H += log-tree.h\n LIB_H += mailmap.h\n+LIB_H += map.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += notes.h\n@@ -624,6 +625,7 @@ LIB_OBJS += ll-merge.o\n LIB_OBJS += lockfile.o\n LIB_OBJS += log-tree.o\n LIB_OBJS += mailmap.o\n+LIB_OBJS += map.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\ndiff --git a/map.c b/map.c\nnew file mode 100644\nindex 0000000..35f300e\n--- /dev/null\n+++ b/map.c\n@@ -0,0 +1,86 @@\n+#include \"cache.h\"\n+#include \"map.h\"\n+#include \"object.h\"\n+\n+static unsigned int hash_obj(const struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash;\n+\n+\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n+\treturn hash % n;\n+}\n+\n+static int obj_equal(const struct object *a, const struct object *b)\n+{\n+\treturn a == b;\n+}\n+\n+#define IMPLEMENT_MAP(name, equal_fun, hash_fun) \\\n+static int map_insert_##name(struct map_##name *m, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name value, \\\n+\t\t\t map_vtype_##name *old) \\\n+{ \\\n+\tunsigned int j; \\\n+\\\n+\tfor (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \\\n+\t\tif (equal_fun(m->hash[j].key, key)) { \\\n+\t\t\tif (old) \\\n+\t\t\t\t*old = m->hash[j].value; \\\n+\t\t\tm->hash[j].value = value; \\\n+\t\t\treturn 1; \\\n+\t\t} \\\n+\t} \\\n+\\\n+\tm->hash[j].key = key; \\\n+\tm->hash[j].value = value; \\\n+\tm->hash[j].used = 1; \\\n+\tm->nr++; \\\n+\treturn 0; \\\n+} \\\n+\\\n+static void map_grow_##name(struct map_##name *m) \\\n+{ \\\n+\tstruct map_entry_##name *old_hash = m->hash; \\\n+\tunsigned int old_size = m->size; \\\n+\tunsigned int i; \\\n+\\\n+\tm->size = (old_size + 1000) * 3 / 2; \\\n+\tm->hash = xcalloc(m->size, sizeof(*m->hash)); \\\n+\tm->nr = 0; \\\n+\\\n+\tfor (i = 0; i < old_size; i++) { \\\n+\t\tif (!old_hash[i].used) \\\n+\t\t\tcontinue; \\\n+\t\tmap_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \\\n+\t} \\\n+\tfree(old_hash); \\\n+} \\\n+\\\n+int map_set_##name(struct map_##name *m, \\\n+\t\t const map_ktype_##name key, \\\n+\t\t map_vtype_##name value, \\\n+\t\t map_vtype_##name *old) \\\n+{ \\\n+\tif (m->nr >= m->size * 2 / 3) \\\n+\t\tmap_grow_##name(m); \\\n+\treturn map_insert_##name(m, key, value, old); \\\n+} \\\n+\\\n+int map_get_##name(struct map_##name *m, \\\n+\t\t const map_ktype_##name key, \\\n+\t\t map_vtype_##name *value) \\\n+{ \\\n+\tunsigned int j; \\\n+\\\n+\tif (!m->size) \\\n+\t\treturn 0; \\\n+\\\n+\tfor (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \\\n+\t\tif (equal_fun(m->hash[j].key, key)) { \\\n+\t\t\t*value = m->hash[j].value; \\\n+\t\t\treturn 1; \\\n+\t\t} \\\n+\t} \\\n+\treturn 0; \\\n+}\ndiff --git a/map.h b/map.h\nnew file mode 100644\nindex 0000000..cb2d4e2\n--- /dev/null\n+++ b/map.h\n@@ -0,0 +1,26 @@\n+#ifndef MAP_H\n+#define MAP_H\n+\n+#define DECLARE_MAP(name, key_type, value_type) \\\n+typedef key_type map_ktype_##name; \\\n+typedef value_type map_vtype_##name; \\\n+struct map_entry_##name { \\\n+\tmap_ktype_##name key; \\\n+\tmap_vtype_##name value; \\\n+\tunsigned used:1; \\\n+}; \\\n+\\\n+struct map_##name { \\\n+\tunsigned int size, nr; \\\n+\tstruct map_entry_##name *hash; \\\n+}; \\\n+\\\n+extern int map_get_##name(struct map_##name *, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name *value); \\\n+extern int map_set_##name(struct map_##name *, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name value, \\\n+\t\t\t map_vtype_##name *old);\n+\n+#endif /* MAP_H */\n-- \n1.7.6.34.g86521e\n"},{"id":"172950","messageId":"20110804224600.GB27912@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[PATCH 2/5] fast-export: use object to uint32 map instead of \"decorate\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:46:00Z","receivedAt":"2011-08-04T22:46:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Previously we encoded the \"mark\" mapping inside the \"void *\"\nfield of a \"struct decorate\". It's a little more natural for\nus to do so using a data structure made for holding actual\nvalues.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-map.txt | 2 +-\n builtin/fast-export.c | 36 ++++++++++------------------------\n map.c | 2 +\n map.h | 2 +\n 4 files changed, 16 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt\nindex 4153ef1..97e5a32 100644\n--- a/Documentation/technical/api-map.txt\n+++ b/Documentation/technical/api-map.txt\n@@ -149,7 +149,7 @@ void dump_foos(void)\n \tprintf(\"there are %u foos:\\n\", foos.nr);\n \n \tfor (i = 0; i < foos.size; i++) {\n-\t\tstruct map_entry_object_int *e = foos.hash[i];\n+\t\tstruct map_entry_object_int *e = foos.hash + i;\n \n \t\tif (!e->used)\n \t\t\tcontinue;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex becef85..9247871 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -12,7 +12,7 @@\n #include \"diffcore.h\"\n #include \"log-tree.h\"\n #include \"revision.h\"\n-#include \"decorate.h\"\n+#include \"map.h\"\n #include \"string-list.h\"\n #include \"utf8.h\"\n #include \"parse-options.h\"\n@@ -60,7 +60,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,\n \treturn 0;\n }\n \n-static struct decoration idnums;\n+static struct map_object_uint32 idnums;\n static uint32_t last_idnum;\n \n static int has_unshown_parent(struct commit *commit)\n@@ -74,20 +74,9 @@ static int has_unshown_parent(struct commit *commit)\n \treturn 0;\n }\n \n-/* Since intptr_t is C99, we do not use it here */\n-static inline uint32_t *mark_to_ptr(uint32_t mark)\n-{\n-\treturn ((uint32_t *)NULL) + mark;\n-}\n-\n-static inline uint32_t ptr_to_mark(void * mark)\n-{\n-\treturn (uint32_t *)mark - (uint32_t *)NULL;\n-}\n-\n static inline void mark_object(struct object *object, uint32_t mark)\n {\n-\tadd_decoration(&idnums, object, mark_to_ptr(mark));\n+\tmap_set_object_uint32(&idnums, object, mark, NULL);\n }\n \n static inline void mark_next_object(struct object *object)\n@@ -97,10 +86,9 @@ static inline void mark_next_object(struct object *object)\n \n static int get_object_mark(struct object *object)\n {\n-\tvoid *decoration = lookup_decoration(&idnums, object);\n-\tif (!decoration)\n-\t\treturn 0;\n-\treturn ptr_to_mark(decoration);\n+\tuint32_t ret = 0;\n+\tmap_get_object_uint32(&idnums, object, &ret);\n+\treturn ret;\n }\n \n static void show_progress(void)\n@@ -538,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)\n static void export_marks(char *file)\n {\n \tunsigned int i;\n-\tuint32_t mark;\n-\tstruct object_decoration *deco = idnums.hash;\n \tFILE *f;\n \tint e = 0;\n \n@@ -548,15 +534,15 @@ static void export_marks(char *file)\n \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n \n \tfor (i = 0; i < idnums.size; i++) {\n-\t\tif (deco->base && deco->base->type == 1) {\n-\t\t\tmark = ptr_to_mark(deco->decoration);\n-\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n-\t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n+\t\tconst struct map_entry_object_uint32 *m = idnums.hash + i;\n+\n+\t\tif (m->used && m->key->type == 1) {\n+\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", m->value,\n+\t\t\t\tsha1_to_hex(m->key->sha1)) < 0) {\n \t\t\t e = 1;\n \t\t\t break;\n \t\t\t}\n \t\t}\n-\t\tdeco++;\n \t}\n \n \te |= ferror(f);\ndiff --git a/map.c b/map.c\nindex 35f300e..1fdd1aa 100644\n--- a/map.c\n+++ b/map.c\n@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \\\n \t} \\\n \treturn 0; \\\n }\n+\n+IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)\ndiff --git a/map.h b/map.h\nindex cb2d4e2..7449593 100644\n--- a/map.h\n+++ b/map.h\n@@ -23,4 +23,6 @@ extern int map_set_##name(struct map_##name *, \\\n \t\t\t map_vtype_##name value, \\\n \t\t\t map_vtype_##name *old);\n \n+DECLARE_MAP(object_uint32, const struct object *, uint32_t)\n+\n #endif /* MAP_H */\n-- \n1.7.6.34.g86521e\n"},{"id":"172951","messageId":"20110804224608.GC27912@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[PATCH 3/5] decorate: use \"map\" for the underlying implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:46:08Z","receivedAt":"2011-08-04T22:46:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The decoration API maps objects to void pointers. This is a\nsubset of what the map API is capable of, so let's get rid\nof the duplicate implementation.\n\nWe could just fix all callers of decorate to call the map\nAPI directly. However, the map API is very generic since it\nis meant to handle any type. In particular, it can't use\nsentinel values like \"NULL\" to indicate \"entry not found\"\n(since it doesn't know whether the type can represent such a\nsentinel value), which makes the interface slightly more\ncomplicated.\n\nInstead, let's keep the existing decorate API as a wrapper\non top of map. No callers need to be updated at all.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-decorate.txt | 38 +++++++++++++-\n decorate.c | 85 +++---------------------------\n decorate.h | 10 +---\n map.c | 1 +\n map.h | 1 +\n 5 files changed, 48 insertions(+), 87 deletions(-)\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 1d52a6c..3c1197a 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -1,6 +1,40 @@\n decorate API\n ============\n \n-Talk about \n+The decorate API is a system for efficiently mapping objects to values\n+in memory. It is slightly slower than an actual member of an object\n+struct (because it incurs a hash lookup), but it uses less memory when\n+the mapping is not in use, or when the number of decorated objects is\n+small compared to the total number of objects.\n \n-(Linus)\n+The decorate API is a special form of the `map` link:api-map.html[map\n+API]. It has slightly simpler calling conventions, but only use objects\n+as keys, and can only store void pointers as values.\n+\n+\n+Data Structures\n+---------------\n+\n+`struct decoration`::\n+\n+\tThis structure represents a single mapping of objects to values.\n+\tThe `name` field is not used by the decorate API itself, but may\n+\tbe used by calling code. The `map` field represents the actual\n+\tmapping of objects to void pointers (see the\n+\tlink:api-map.html[map API] for details).\n+\n+\n+Functions\n+---------\n+\n+`add_decoration`::\n+\n+\tAdd a mapping from an object to a void pointer. If there was a\n+\tprevious value for this object, the function returns this value;\n+\totherwise, the function returns NULL.\n+\n+`lookup_decoration`::\n+\n+\tRetrieve the stored value pointer for an object from the\n+\tmapping. The return value is the value pointer, or `NULL` if\n+\tthere is no value for this object.\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..31e9656 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -1,88 +1,17 @@\n-/*\n- * decorate.c - decorate a git object with some arbitrary\n- * data.\n- */\n #include \"cache.h\"\n-#include \"object.h\"\n #include \"decorate.h\"\n \n-static unsigned int hash_obj(const struct object *obj, unsigned int n)\n-{\n-\tunsigned int hash;\n-\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n-}\n-\n-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n-{\n-\tint size = n->size;\n-\tstruct object_decoration *hash = n->hash;\n-\tunsigned int j = hash_obj(base, size);\n-\n-\twhile (hash[j].base) {\n-\t\tif (hash[j].base == base) {\n-\t\t\tvoid *old = hash[j].decoration;\n-\t\t\thash[j].decoration = decoration;\n-\t\t\treturn old;\n-\t\t}\n-\t\tif (++j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j].base = base;\n-\thash[j].decoration = decoration;\n-\tn->nr++;\n-\treturn NULL;\n-}\n-\n-static void grow_decoration(struct decoration *n)\n-{\n-\tint i;\n-\tint old_size = n->size;\n-\tstruct object_decoration *old_hash = n->hash;\n-\n-\tn->size = (old_size + 1000) * 3 / 2;\n-\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n-\tn->nr = 0;\n-\n-\tfor (i = 0; i < old_size; i++) {\n-\t\tconst struct object *base = old_hash[i].base;\n-\t\tvoid *decoration = old_hash[i].decoration;\n-\n-\t\tif (!base)\n-\t\t\tcontinue;\n-\t\tinsert_decoration(n, base, decoration);\n-\t}\n-\tfree(old_hash);\n-}\n-\n-/* Add a decoration pointer, return any old one */\n void *add_decoration(struct decoration *n, const struct object *obj,\n-\t\tvoid *decoration)\n+\t\t void *decoration)\n {\n-\tint nr = n->nr + 1;\n-\n-\tif (nr > n->size * 2 / 3)\n-\t\tgrow_decoration(n);\n-\treturn insert_decoration(n, obj, decoration);\n+\tvoid *ret = NULL;\n+\tmap_set_object_void(&n->map, obj, decoration, &ret);\n+\treturn ret;\n }\n \n-/* Lookup a decoration pointer */\n void *lookup_decoration(struct decoration *n, const struct object *obj)\n {\n-\tunsigned int j;\n-\n-\t/* nothing to lookup */\n-\tif (!n->size)\n-\t\treturn NULL;\n-\tj = hash_obj(obj, n->size);\n-\tfor (;;) {\n-\t\tstruct object_decoration *ref = n->hash + j;\n-\t\tif (ref->base == obj)\n-\t\t\treturn ref->decoration;\n-\t\tif (!ref->base)\n-\t\t\treturn NULL;\n-\t\tif (++j == n->size)\n-\t\t\tj = 0;\n-\t}\n+\tvoid *ret = NULL;\n+\tmap_get_object_void(&n->map, obj, &ret);\n+\treturn ret;\n }\ndiff --git a/decorate.h b/decorate.h\nindex e732804..6a3adcd 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -1,15 +1,11 @@\n #ifndef DECORATE_H\n #define DECORATE_H\n \n-struct object_decoration {\n-\tconst struct object *base;\n-\tvoid *decoration;\n-};\n+#include \"map.h\"\n \n struct decoration {\n-\tconst char *name;\n-\tunsigned int size, nr;\n-\tstruct object_decoration *hash;\n+\tchar *name;\n+\tstruct map_object_void map;\n };\n \n extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);\ndiff --git a/map.c b/map.c\nindex 1fdd1aa..73f45e0 100644\n--- a/map.c\n+++ b/map.c\n@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \\\n }\n \n IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)\n+IMPLEMENT_MAP(object_void, obj_equal, hash_obj)\ndiff --git a/map.h b/map.h\nindex 7449593..cb9aea6 100644\n--- a/map.h\n+++ b/map.h\n@@ -24,5 +24,6 @@ extern int map_set_##name(struct map_##name *, \\\n \t\t\t map_vtype_##name *old);\n \n DECLARE_MAP(object_uint32, const struct object *, uint32_t)\n+DECLARE_MAP(object_void, const struct object *, void *)\n \n #endif /* MAP_H */\n-- \n1.7.6.34.g86521e\n"},{"id":"172952","messageId":"20110804224627.GD27912@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[PATCH 4/5] map: implement persistent maps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:46:27Z","receivedAt":"2011-08-04T22:46:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It's sometimes useful to keep a mapping across program\ninvocations (e.g., because a space/time tradeoff makes it\nworth keeping a cache of calculated metadata for some\nobjects).\n\nThis adds a persistent version of the map API which can be\nbacked by a flat memory store (like an mmap'd file). By\nitself, it's not very pleasant to use, as the caller is\nresponsible for actually opening and mapping files. But it\nprovides the building blocks for disk caches, which will\ncome in the next patch.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-map.txt | 132 +++++++++++++++++++++++++++++\n map.c | 157 +++++++++++++++++++++++++++++++++++\n map.h | 17 ++++\n 3 files changed, 306 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt\nindex 97e5a32..8ac0cc0 100644\n--- a/Documentation/technical/api-map.txt\n+++ b/Documentation/technical/api-map.txt\n@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to\n using \"struct object\" as the key, and a void pointer as the value.\n \n \n+Persistent Maps\n+---------------\n+\n+Maps come in two flavors: persistent and in-core. In-core maps are\n+represented by a hash table, and can contain any C type. Persistent maps\n+are backed by flat storage, such as an mmap'd file, and store values\n+between program runs. Key and value types must be serializable to\n+fixed-width byte values.\n+\n+The flat storage is a sorted array of key/value pairs, with no\n+delimiters between pairs or between elements of a pair. Persistent maps\n+uses an in-core map for newly-added values, and then merge the new\n+values into the flat storage on request.\n+\n+\n Defining New Map Types\n ----------------------\n \n@@ -50,6 +65,32 @@ define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the\n \tshould specify a function that will convert an object of type `ktype`\n \tinto an integer hash value.\n \n+To define a persistent map, use these macros instead:\n+\n+`DECLARE_MAP_PERSIST`::\n+\n+\tDeclare a new persistent map. The `name` parameter must match a\n+\tmap declared already with `DECLARE_MAP`.\n+\n+`IMPLEMENT_MAP_PERSIST`::\n+\n+\tCreate function definitions for a persistent map. The `name`\n+\tparameter must match one given to `DECLARE_MAP_PERSIST`. The\n+\t`ksize` and `vsize` parameters indicate the size, in bytes, of\n+\tserialized keys and values.\n++\n+\tThe `k_to_disk` and `v_to_disk` parameters specify functions to\n+\tconvert keys and values to their serialized formats; they take a\n+\tkey (or value), and a pointer to memory of at least `ksize` (or\n+\t`vsize`) bytes to write into. The `disk_to_v` parameter\n+\tspecifies a function to convert a pointer to `vsize` bytes of\n+\tserialized value into a `vtype`.\n++\n+\tThe `disk_lookup_fun` parameter should specify a function for\n+\tperforming a search of the sorted flat disk array (it is given\n+\tthe array, the number of elements, the size of the key and\n+\tvalue, and the key to lookup).\n+\n Several convenience functions are provided to fill in macro parameters:\n \n `hash_obj`::\n@@ -60,6 +101,26 @@ Several convenience functions are provided to fill in macro parameters:\n \n \tSuitable for `equal_fun` when the key type is `struct object *`.\n \n+`obj_to_disk`::\n+\n+\tSuitable for `k_to_disk` when the key type is `struct object *`.\n+\n+`uint32_to_disk`::\n+\n+\tSuitable for `k_to_disk` or `v_to_disk` when the type is\n+\t`uint32_t`. Integers are serialized in network byte order for\n+\tportability.\n+\n+`disk_to_uint32`::\n+\n+\tSuitable for `disk_to_v` when the value type is `uint32_t`.\n+\tIntegers are converted back to host byte order.\n+\n+`disk_lookup_sha1`::\n+\n+\tSuitable for disk_lookup_fun when the serialized keys are sha1\n+\thashes.\n+\n \n Data Structures\n ---------------\n@@ -83,6 +144,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`).\n \tsingle mapped pair. You should never need to use this type directly,\n \tunless you are enumerating all elements of a map.\n \n+`struct map_persist_NAME`::\n+\n+\tA persistent map. This struct should be initialized to\n+\tall-zeroes. The `map` field contains a complete in-core map. The\n+\t`disk_entries` and `disk_nr` fields specify the flat storage.\n+\tThese should not be set directly, but rather through the\n+\t`attach` function.\n+\n \n Functions\n ---------\n@@ -102,6 +171,27 @@ Each defined map type will have its own set of access function (e.g.,\n \texisted, the previous value is copied into `old` (if it is non-NULL)\n \tand the function returns 1. Otherwise, the function returns 0.\n \n+`map_persist_get_NAME(struct map_persist_NAME *, const ktype key, vtype *value)`::\n+\n+\tSame as `map_get_NAME`, but for a persistent map.\n+\n+`map_persist_set_NAME(struct map_persist_NAME *, const ktype key, vtype value)`::\n+\n+\tSame as `map_set_name`, but for a persistent map. It also does\n+\tnot provide the \"old\" value for the key.\n+\n+`map_persist_attach_NAME`::\n+\n+\tAttach storage from `buf` of size `len` bytes as the flat\n+\tbacking store for the map. The map does not copy the storage;\n+\tthe caller is responsible for making sure it stays around as\n+\tlong as the map does.\n+\n+`map_persist_flush_NAME`::\n+\n+\tMerge in-core entries with those found in the backing store, and\n+\twrite the result to `fd`. Returns 0 for success, -1 for failure.\n+\n \n Examples\n --------\n@@ -158,3 +248,45 @@ void dump_foos(void)\n \t}\n }\n -------------------------------------------------------------------\n+\n+Open and close a disk-backed persistent map of objects to 32-bit\n+integers:\n+\n+-------------------------------------------------------------------\n+static int fd;\n+static const unsigned char *buf;\n+static unsigned len;\n+static struct map_persist_object_uint32 map;\n+\n+void open_map(const char *path)\n+{\n+\tstruct stat sb;\n+\tconst unsigned char *p;\n+\n+\tfd = open(path, O_RDONLY);\n+\t/* it's ok not to attach any backing store at all */\n+\tif (fd < 0)\n+\t\treturn;\n+\n+\tfstat(fd, &sb);\n+\tlen = sb.st_size;\n+\tbuf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);\n+\n+\tmap_persist_attach_object_uint32(&map, buf, len);\n+}\n+\n+/* other functions call \"get\" and \"set\" */\n+\n+void close_map(const char *path, const char *tmp)\n+{\n+\tint tmpfd;\n+\n+\ttmpfd = open(tmp, O_RDONLY);\n+\tif (map_persist_flush_object_uint32(&map, tmpfd) < 0)\n+\t\tdie_errno(\"unable to write new map\");\n+\tclose(tmpfd);\n+\trename(tmp, path);\n+\n+\tmunmap(buf, len);\n+\tclose(fd);\n+}\ndiff --git a/map.c b/map.c\nindex 73f45e0..bb0d60a 100644\n--- a/map.c\n+++ b/map.c\n@@ -1,6 +1,7 @@\n #include \"cache.h\"\n #include \"map.h\"\n #include \"object.h\"\n+#include \"sha1-lookup.h\"\n \n static unsigned int hash_obj(const struct object *obj, unsigned int n)\n {\n@@ -15,6 +16,74 @@ static int obj_equal(const struct object *a, const struct object *b)\n \treturn a == b;\n }\n \n+static void obj_to_disk(const struct object *obj, unsigned char *out)\n+{\n+\thashcpy(out, obj->sha1);\n+}\n+\n+static void uint32_to_disk(uint32_t v, unsigned char *out)\n+{\n+\tv = htonl(v);\n+\tmemcpy(out, &v, 4);\n+}\n+\n+static void disk_to_uint32(const unsigned char *disk, uint32_t *out)\n+{\n+\tmemcpy(out, disk, 4);\n+\t*out = ntohl(*out);\n+}\n+\n+static const unsigned char *disk_lookup_sha1(const unsigned char *buf,\n+\t\t\t\t\t unsigned nr,\n+\t\t\t\t\t unsigned ksize, unsigned vsize,\n+\t\t\t\t\t const unsigned char *key)\n+{\n+\tint pos;\n+\n+\tpos = sha1_entry_pos(buf, ksize + vsize, 0, 0, nr, nr, key);\n+\tif (pos < 0)\n+\t\treturn NULL;\n+\treturn buf + (pos * (ksize + vsize)) + ksize;\n+}\n+\n+static int merge_entries(int fd, int ksize, int vsize,\n+\t\t\t const unsigned char *left, unsigned nr_left,\n+\t\t\t const unsigned char *right, unsigned nr_right)\n+{\n+#define ADVANCE(name) \\\n+\tdo { \\\n+\t\tname += ksize + vsize; \\\n+\t\tnr_##name--; \\\n+\t} while (0)\n+#define WRITE_ENTRY(name) \\\n+\tdo { \\\n+\t\tif (write_in_full(fd, name, ksize + vsize) < 0) \\\n+\t\t\treturn -1; \\\n+\t\tADVANCE(name); \\\n+\t} while (0)\n+\n+\twhile (nr_left && nr_right) {\n+\t\tint cmp = memcmp(left, right, ksize);\n+\n+\t\t/* skip duplicates, preferring left to right */\n+\t\tif (cmp == 0)\n+\t\t\tADVANCE(right);\n+\t\telse if (cmp < 0)\n+\t\t\tWRITE_ENTRY(left);\n+\t\telse\n+\t\t\tWRITE_ENTRY(right);\n+\t}\n+\twhile (nr_left)\n+\t\tWRITE_ENTRY(left);\n+\twhile (nr_right)\n+\t\tWRITE_ENTRY(right);\n+\n+#undef WRITE_ENTRY\n+#undef ADVANCE\n+\n+\treturn 0;\n+}\n+\n #define IMPLEMENT_MAP(name, equal_fun, hash_fun) \\\n static int map_insert_##name(struct map_##name *m, \\\n \t\t\t const map_ktype_##name key, \\\n@@ -85,5 +154,93 @@ int map_get_##name(struct map_##name *m, \\\n \treturn 0; \\\n }\n \n+#define IMPLEMENT_MAP_PERSIST(name, \\\n+\t\t\t ksize, k_to_disk, \\\n+\t\t\t vsize, v_to_disk, disk_to_v, \\\n+\t\t\t disk_lookup_fun) \\\n+int map_persist_get_##name(struct map_persist_##name *m, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name *value) \\\n+{ \\\n+\tunsigned char disk_key[ksize]; \\\n+\tconst unsigned char *disk_value; \\\n+\\\n+\tif (map_get_##name(&m->mem, key, value)) \\\n+\t\treturn 1; \\\n+\\\n+\tif (!m->disk_entries) \\\n+\t\treturn 0; \\\n+\\\n+\tk_to_disk(key, disk_key); \\\n+\tdisk_value = disk_lookup_fun(m->disk_entries, m->disk_nr, \\\n+\t\t\t\t ksize, vsize, disk_key); \\\n+\tif (disk_value) { \\\n+\t\tdisk_to_v(disk_value, value); \\\n+\t\treturn 1; \\\n+\t} \\\n+\\\n+\treturn 0; \\\n+} \\\n+\\\n+int map_persist_set_##name(struct map_persist_##name *m, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name value) \\\n+{ \\\n+\treturn map_set_##name(&m->mem, key, value, NULL); \\\n+} \\\n+\\\n+static unsigned char *flatten_mem_entries_##name(struct map_persist_##name *m) \\\n+{ \\\n+\tunsigned char *ret, *out; \\\n+\tint i, nr; \\\n+\\\n+\tout = ret = xmalloc(m->mem.nr * (ksize + vsize)); \\\n+\tnr = 0; \\\n+\tfor (i = 0; i < m->mem.size; i++) { \\\n+\t\tstruct map_entry_##name *e = m->mem.hash + i; \\\n+\\\n+\t\tif (!e->used) \\\n+\t\t\tcontinue; \\\n+\\\n+\t\tif (nr == m->mem.nr) \\\n+\t\t\tdie(\"BUG: map hash contained extra values\"); \\\n+\\\n+\t\tk_to_disk(e->key, out); \\\n+\t\tout += ksize; \\\n+\t\tv_to_disk(e->value, out); \\\n+\t\tout += vsize; \\\n+\t} \\\n+\\\n+\treturn ret; \\\n+} \\\n+\\\n+void map_persist_attach_##name(struct map_persist_##name *m, \\\n+\t\t\t const unsigned char *buf, \\\n+\t\t\t unsigned int len) \\\n+{ \\\n+\tm->disk_entries = buf; \\\n+\tm->disk_nr = len / (ksize + vsize); \\\n+} \\\n+\\\n+static int keycmp_##name(const void *a, const void *b) \\\n+{ \\\n+\treturn memcmp(a, b, ksize); \\\n+} \\\n+\\\n+int map_persist_flush_##name(struct map_persist_##name *m, int fd) \\\n+{ \\\n+\tunsigned char *mem_entries; \\\n+\tint r; \\\n+\\\n+\tmem_entries = flatten_mem_entries_##name(m); \\\n+\tqsort(mem_entries, m->mem.nr, ksize + vsize, keycmp_##name); \\\n+\\\n+\tr = merge_entries(fd, ksize, vsize, \\\n+\t\t\t mem_entries, m->mem.nr, \\\n+\t\t\t m->disk_entries, m->disk_nr); \\\n+\tfree(mem_entries); \\\n+\treturn r; \\\n+}\n+\n IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)\n IMPLEMENT_MAP(object_void, obj_equal, hash_obj)\ndiff --git a/map.h b/map.h\nindex cb9aea6..ceddc14 100644\n--- a/map.h\n+++ b/map.h\n@@ -23,6 +23,23 @@ extern int map_set_##name(struct map_##name *, \\\n \t\t\t map_vtype_##name value, \\\n \t\t\t map_vtype_##name *old);\n \n+#define DECLARE_MAP_PERSIST(name) \\\n+struct map_persist_##name { \\\n+\tstruct map_##name mem; \\\n+\tconst unsigned char *disk_entries; \\\n+\tunsigned int disk_nr; \\\n+}; \\\n+extern int map_persist_get_##name(struct map_persist_##name *, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name *value); \\\n+extern int map_persist_set_##name(struct map_persist_##name *, \\\n+\t\t\t const map_ktype_##name key, \\\n+\t\t\t map_vtype_##name value); \\\n+extern void map_persist_attach_##name(struct map_persist_##name *, \\\n+\t\t\t\t const unsigned char *buf, \\\n+\t\t\t\t unsigned int len); \\\n+extern int map_persist_flush_##name(struct map_persist_##name *, int fd);\n+\n DECLARE_MAP(object_uint32, const struct object *, uint32_t)\n DECLARE_MAP(object_void, const struct object *, void *)\n \n-- \n1.7.6.34.g86521e\n"},{"id":"172953","messageId":"20110804224647.GE27912@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[PATCH 5/5] implement metadata cache subsystem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:46:48Z","receivedAt":"2011-08-04T22:46:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There are some calculations that git makes repeatedly, even\nthough the results are invariant for a certain input (e.g.,\nthe patch-id of a certain commit). We can make a space/time\ntradeoff by caching these on disk between runs.\n\nEven though these may be immutable for a certain commit, we\ndon't want to directly store the results in the commit\nobjects themselves, for a few reasons:\n\n 1. They are not necessarily used by all algorithms, so\n bloating the commit object might slow down other\n algorithms.\n\n 2. Because they can be calculated from the existing\n commits, they are redundant with the existing\n information. Thus they are an implementation detail of\n our current algorithms, and should not be cast in stone\n by including them in the commit sha1.\n\n 3. They may only be immutable under a certain set of\n conditions (e.g., which grafts or replace refs we are\n using). Keeping the storage external means we can\n invalidate and regenerate the cache whenever those\n conditions change.\n\nThe persistent map API already provides the storage we need.\nThis new API takes care of the details of opening and\nclosing the cache files automatically. Callers need only get\nand set values as they see fit.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-metadata-cache.txt | 67 +++++++++++++\n Makefile | 2 +\n metadata-cache.c | 126 ++++++++++++++++++++++++\n metadata-cache.h | 10 ++\n 4 files changed, 205 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-metadata-cache.txt\n create mode 100644 metadata-cache.c\n create mode 100644 metadata-cache.h\n\ndiff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt\nnew file mode 100644\nindex 0000000..5f4422d\n--- /dev/null\n+++ b/Documentation/technical/api-metadata-cache.txt\n@@ -0,0 +1,67 @@\n+metadata cache API\n+==================\n+\n+The metadata cache API provides simple-to-use, persistent key/value\n+storage. It is built on the link:api-map.html[map API], so keys and\n+values can have any serializable type.\n+\n+Caches are statically allocated, and no explicit initialization is\n+required. Callers can simply call the \"get\" and \"set\" functions for a\n+given cache. At program exit, any new entries in the cache are flushed\n+to disk.\n+\n+\n+Defining a New Cache\n+--------------------\n+\n+You need to provide three pieces of information to define a new cache:\n+\n+name::\n+\tThis name will be used both as part of the C identifier and as\n+\tpart of the filename under which the cache is stored. Restrict\n+\tthe characters used to alphanumerics and underscore.\n+\n+map::\n+\tThe type of map (declared by `DECLARE_MAP`) that this cache will\n+\tstore.\n+\n+validity::\n+\tA function that will generate a 20-byte \"validity token\"\n+\trepresenting the conditions under which the cache is valid.\n+\tFor example, a cache that depended on the structure of the\n+\thistory graph would be valid only under a given set of grafts\n+\tand replace refs. That set could be stirred into a sha1 and used\n+\tas a validity token.\n+\n+You must declare the cache in metadata-cache.h using\n+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c\n+using `IMPLEMENT_METADATA_CACHE`.\n+\n+\n+Using a Cache\n+-------------\n+\n+Interaction with a cache consists entirely of getting and setting\n+values. No initialization or cleanup is required. The get and set\n+functions mirror their \"map\" counterparts; see the\n+link:api-map.html[map API] for details.\n+\n+\n+File Format\n+-----------\n+\n+Cache files are stored in the $GIT_DIR/cache directory. Each cache gets\n+its own directory, named after the `name` parameter in the cache\n+definition. Within each directory is a set of files, one cache per file,\n+named after their validity tokens. Caches for multiple sets of\n+conditions can simultaneously exist, and git will use whichever is\n+appropriate.\n+\n+The files themselves consist of an 8-byte header. The first four bytes\n+are the magic sequence \"MTAC\" (for \"MeTA Cache\"), followed by a 4-byte\n+version number, in network byte order. This document describes version\n+1.\n+\n+The rest of the file consists of the persistent map data. This is a\n+compact, sorted list of keys and values; see the link:api-map.html[map\n+API] for details.\ndiff --git a/Makefile b/Makefile\nindex acda5b8..3b39538 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -536,6 +536,7 @@ LIB_H += mailmap.h\n LIB_H += map.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n+LIB_H += metadata-cache.h\n LIB_H += notes.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n@@ -629,6 +630,7 @@ LIB_OBJS += map.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n+LIB_OBJS += metadata-cache.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/metadata-cache.c b/metadata-cache.c\nnew file mode 100644\nindex 0000000..e217db1\n--- /dev/null\n+++ b/metadata-cache.c\n@@ -0,0 +1,126 @@\n+#include \"cache.h\"\n+#include \"metadata-cache.h\"\n+#include \"map.h\"\n+\n+static const char *metadata_cache_path(const char *name,\n+\t\t\t\t void (*validity)(unsigned char [20]))\n+{\n+\tunsigned char token[20];\n+\n+\tif (validity)\n+\t\tvalidity(token);\n+\telse\n+\t\thashcpy(token, null_sha1);\n+\treturn git_path(\"cache/%s/%s\", name, sha1_to_hex(token));\n+}\n+\n+#define IMPLEMENT_METADATA_CACHE(name, map, validity) \\\n+static struct map_persist_##map name##_map; \\\n+static int name##_fd; \\\n+static unsigned char *name##_buf; \\\n+static unsigned long name##_len; \\\n+\\\n+static void write_##name##_cache(void) \\\n+{ \\\n+\tconst char *path; \\\n+\tstruct strbuf tempfile = STRBUF_INIT; \\\n+\tint fd = -1; \\\n+\\\n+\tif (!name##_map.mem.nr) \\\n+\t\treturn; \\\n+\\\n+\tpath = metadata_cache_path(#name, validity); \\\n+\tstrbuf_addf(&tempfile, \"%s.XXXXXX\", path); \\\n+\\\n+\tif (safe_create_leading_directories(tempfile.buf) < 0) \\\n+\t\tgoto fail; \\\n+\tfd = git_mkstemp_mode(tempfile.buf, 0444); \\\n+\tif (fd < 0) \\\n+\t\tgoto fail; \\\n+\\\n+\tif (write_in_full(fd, \"MTAC\\x00\\x00\\x00\\x01\", 8) < 0) \\\n+\t\tgoto fail; \\\n+\tif (map_persist_flush_##map(&name##_map, fd) < 0) \\\n+\t\tgoto fail; \\\n+\tif (close(fd) < 0) \\\n+\t\tgoto fail; \\\n+\tif (rename(tempfile.buf, path) < 0) \\\n+\t\tgoto fail; \\\n+\\\n+\tstrbuf_release(&tempfile); \\\n+\treturn; \\\n+\\\n+fail: \\\n+\tclose(fd); \\\n+\tunlink(tempfile.buf); \\\n+\tstrbuf_release(&tempfile); \\\n+} \\\n+\\\n+static void init_##name##_cache(void) \\\n+{ \\\n+\tstatic int initialized; \\\n+\tconst char *path; \\\n+\tstruct stat sb; \\\n+\tconst unsigned char *p; \\\n+\tuint32_t version; \\\n+\\\n+\tif (initialized) \\\n+\t\treturn; \\\n+\\\n+\tatexit(write_##name##_cache); \\\n+\tinitialized = 1; \\\n+\\\n+\tpath = metadata_cache_path(#name, validity); \\\n+\tname##_fd = open(path, O_RDONLY); \\\n+\tif (name##_fd < 0) \\\n+\t\treturn; \\\n+\\\n+\tif (fstat(name##_fd, &sb) < 0) \\\n+\t\tgoto fail; \\\n+\tname##_len = sb.st_size; \\\n+\tname##_buf = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, \\\n+\t\t\t\t name##_fd, 0); \\\n+\\\n+\tif (name##_len < 8) { \\\n+\t\twarning(\"cache '%s' is missing header\", path); \\\n+\t\tgoto fail; \\\n+\t} \\\n+\tp = name##_buf; \\\n+\tif (memcmp(p, \"MTAC\", 4)) { \\\n+\t\twarning(\"cache '%s' has invalid magic: %c%c%c%c\", \\\n+\t\t\tpath, p[0], p[1], p[2], p[3]); \\\n+\t\tgoto fail; \\\n+\t} \\\n+\tp += 4; \\\n+\tmemcpy(&version, p, 4); \\\n+\tversion = ntohl(version); \\\n+\tif (version != 1) { \\\n+\t\twarning(\"cache '%s' has unknown version: %\"PRIu32, \\\n+\t\t\tpath, version); \\\n+\t\tgoto fail; \\\n+\t} \\\n+\\\n+\tmap_persist_attach_##map(&name##_map, \\\n+\t\t\t\t name##_buf + 8, \\\n+\t\t\t\t name##_len - 8); \\\n+\treturn; \\\n+\\\n+fail: \\\n+\tclose(name##_fd); \\\n+\tname##_fd = -1; \\\n+\tif (name##_buf) \\\n+\t\tmunmap(name##_buf, name##_len); \\\n+\tname##_buf = NULL; \\\n+\tname##_len = 0; \\\n+} \\\n+\\\n+int name##_cache_get(map_ktype_##map key, map_vtype_##map *value) \\\n+{ \\\n+\tinit_##name##_cache(); \\\n+\treturn map_persist_get_##map(&name##_map, key, value); \\\n+} \\\n+int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \\\n+{ \\\n+\tinit_##name##_cache(); \\\n+\treturn map_persist_set_##map(&name##_map, key, value); \\\n+}\ndiff --git a/metadata-cache.h b/metadata-cache.h\nnew file mode 100644\nindex 0000000..851a4eb\n--- /dev/null\n+++ b/metadata-cache.h\n@@ -0,0 +1,10 @@\n+#ifndef METADATA_CACHE_H\n+#define METADATA_CACHE_H\n+\n+#include \"map.h\"\n+\n+#define DECLARE_METADATA_CACHE(name, map) \\\n+extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \\\n+extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);\n+\n+#endif /* METADATA_CACHE_H */\n-- \n1.7.6.34.g86521e\n"},{"id":"172954","messageId":"20110804224848.GA27545@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"[RFC/PATCH 0/2] patch-id caching","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:48:48Z","receivedAt":"2011-08-04T22:48:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 04, 2011 at 04:43:54PM -0600, Jeff King wrote:\n\n> [1/5]: implement generic key/value map\n> [2/5]: fast-export: use object to uint32 map instead of \"decorate\"\n> [3/5]: decorate: use \"map\" for the underlying implementation\n> [4/5]: map: implement persistent maps\n> [5/5]: implement metadata cache subsystem\n\nAnd here's a potential user of the new code:\n\n [1/2]: cherry: read default config\n [2/2]: cache patch ids on disk\n\n-Peff\n"},{"id":"172955","messageId":"20110804224918.GA28215@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224848.GA27545@sigill.intra.peff.net","subject":"[PATCH 1/2] cherry: read default config","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:49:19Z","receivedAt":"2011-08-04T22:49:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We don't currently read the config at all for git-cherry.\nThis doesn't seem to cause any issues so far, because what\nit does is so simple that none of the configuration matters.\n\nHowever, the next patch will add a relevant config option.\n\nSigned-off-by: Jeff King \n---\n builtin/log.c | 2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 5c2af59..f385fb8 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1438,6 +1438,8 @@ int cmd_cherry(int argc, const char **argv, const char *prefix)\n \t\tOPT_END()\n \t};\n \n+\tgit_config(git_default_config, NULL);\n+\n \targc = parse_options(argc, argv, prefix, options, cherry_usage, 0);\n \n \tswitch (argc) {\n-- \n1.7.6.34.g86521e\n"},{"id":"172956","messageId":"20110804224947.GB28215@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224848.GA27545@sigill.intra.peff.net","subject":"[PATCH 2/2] cache patch ids on disk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:49:47Z","receivedAt":"2011-08-04T22:49:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Some workflows may involve running \"git cherry\" a lot to\nlook for identical patches. Git ends up calculating the\npatch-id of some commits many times, which can be slow.\n\nThis patch provides an option to cache the calculated patch\nids persistently on disk. This trades more disk space (and\nmore RAM used for disk cache) for less CPU time. Whether\nthis is a good idea depends on your workflow and how much\ndisk and RAM you have (the cache uses 40 bytes per stored\ncommit).\n\nHere's one cherry-heavy workflow (checking which topic\nbranches have been accepted upstream), and some timings:\n\n have_commits() {\n\t test -z \"`git cherry \"$@\" | grep -v ^-`\"\n }\n for i in $topic_branches; do\n if have_commits origin/master $i $i@{u}; then\n echo $i: merged to origin/master\n elif have_commits origin/next $i $i@{u}; then\n echo $i: merged to origin/next\n else\n echo $i: not merged\n done\n\n # without patch\n real 0m9.709s\n user 0m8.693s\n sys 0m0.676s\n\n # with patch, first run\n real 0m1.946s\n user 0m1.244s\n sys 0m0.428s\n\n # with patch, subsequent run\n real 0m1.379s\n user 0m0.844s\n sys 0m0.268s\n\nand the disk used:\n\n $ du -h .git/cache/patch_id/*\n 8.0K .git/cache/patch_id/0000000000000000000000000000000000000000\n\nSigned-off-by: Jeff King \n---\n cache.h | 1 +\n config.c | 5 +++++\n map.c | 16 ++++++++++++++++\n map.h | 6 ++++++\n metadata-cache.c | 2 ++\n metadata-cache.h | 2 ++\n patch-ids.c | 22 +++++++++++++++++++++-\n 7 files changed, 53 insertions(+), 1 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 9e12d55..060f0f9 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -596,6 +596,7 @@ extern int read_replace_refs;\n extern int fsync_object_files;\n extern int core_preload_index;\n extern int core_apply_sparse_checkout;\n+extern int core_cache_patch_id;\n \n enum branch_track {\n \tBRANCH_TRACK_UNSPECIFIED = -1,\ndiff --git a/config.c b/config.c\nindex e42c59b..09e84c3 100644\n--- a/config.c\n+++ b/config.c\n@@ -659,6 +659,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.cachepatchid\")) {\n+\t\tcore_cache_patch_id = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \t/* Add other config variables here and to Documentation/config.txt. */\n \treturn 0;\n }\ndiff --git a/map.c b/map.c\nindex bb0d60a..9d8d5ab 100644\n--- a/map.c\n+++ b/map.c\n@@ -33,6 +33,16 @@ static void disk_to_uint32(const unsigned char *disk, uint32_t *out)\n \t*out = ntohl(*out);\n }\n \n+static void sha1_to_disk(struct sha1 v, unsigned char *out)\n+{\n+\thashcpy(out, v.v);\n+}\n+\n+static void disk_to_sha1(const unsigned char *disk, struct sha1 *out)\n+{\n+\thashcpy(out->v, disk);\n+}\n+\n static const unsigned char *disk_lookup_sha1(const unsigned char *buf,\n \t\t\t\t\t unsigned nr,\n \t\t\t\t\t unsigned ksize, unsigned vsize,\n@@ -244,3 +254,9 @@ int map_persist_flush_##name(struct map_persist_##name *m, int fd) \\\n \n IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)\n IMPLEMENT_MAP(object_void, obj_equal, hash_obj)\n+\n+IMPLEMENT_MAP(object_sha1, obj_equal, hash_obj)\n+IMPLEMENT_MAP_PERSIST(object_sha1,\n+\t\t 20, obj_to_disk,\n+\t\t 20, sha1_to_disk, disk_to_sha1,\n+\t\t disk_lookup_sha1)\ndiff --git a/map.h b/map.h\nindex ceddc14..18eb939 100644\n--- a/map.h\n+++ b/map.h\n@@ -40,7 +40,13 @@ extern void map_persist_attach_##name(struct map_persist_##name *, \\\n \t\t\t\t unsigned int len); \\\n extern int map_persist_flush_##name(struct map_persist_##name *, int fd);\n \n+struct sha1 {\n+\tunsigned char v[20];\n+};\n+\n DECLARE_MAP(object_uint32, const struct object *, uint32_t)\n DECLARE_MAP(object_void, const struct object *, void *)\n+DECLARE_MAP(object_sha1, const struct object *, struct sha1)\n+DECLARE_MAP_PERSIST(object_sha1)\n \n #endif /* MAP_H */\ndiff --git a/metadata-cache.c b/metadata-cache.c\nindex e217db1..0ce0e90 100644\n--- a/metadata-cache.c\n+++ b/metadata-cache.c\n@@ -124,3 +124,5 @@ int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \\\n \tinit_##name##_cache(); \\\n \treturn map_persist_set_##map(&name##_map, key, value); \\\n }\n+\n+IMPLEMENT_METADATA_CACHE(patch_id, object_sha1, NULL)\ndiff --git a/metadata-cache.h b/metadata-cache.h\nindex 851a4eb..ff2f6d3 100644\n--- a/metadata-cache.h\n+++ b/metadata-cache.h\n@@ -7,4 +7,6 @@\n extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \\\n extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);\n \n+DECLARE_METADATA_CACHE(patch_id, object_sha1)\n+\n #endif /* METADATA_CACHE_H */\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 5717257..d1818eb 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -3,17 +3,37 @@\n #include \"commit.h\"\n #include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n+#include \"metadata-cache.h\"\n+\n+int core_cache_patch_id;\n \n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t unsigned char *sha1)\n {\n+\tif (core_cache_patch_id) {\n+\t\tstruct sha1 v;\n+\t\tif (patch_id_cache_get(&commit->object, &v)) {\n+\t\t\thashcpy(sha1, v.v);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n \t\t commit->object.sha1, \"\", options);\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\tif (diff_flush_patch_id(options, sha1) < 0)\n+\t\treturn -1;\n+\n+\tif (core_cache_patch_id) {\n+\t\tstruct sha1 v;\n+\t\thashcpy(v.v, sha1);\n+\t\tpatch_id_cache_set(&commit->object, v);\n+\t}\n+\n+\treturn 0;\n }\n \n static const unsigned char *patch_id_access(size_t index, void *table)\n-- \n1.7.6.34.g86521e\n"},{"id":"172958","messageId":"20110804225227.GA28241@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224947.GB28215@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] cache patch ids on disk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-04T22:52:27Z","receivedAt":"2011-08-04T22:52:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 04, 2011 at 04:49:47PM -0600, Jeff King wrote:\n\n> +struct sha1 {\n> +\tunsigned char v[20];\n> +};\n> +\n> [...]\n> +DECLARE_MAP(object_sha1, const struct object *, struct sha1)\n\nI'm not altogether happy with this. But the generated code wants to\ntreat the value type as something that can be instantiated as \"vtype\nfoo\", so we need to wrap a struct around an array to make the compiler\nhappy.\n\nWe could do something a little fancier to avoid this, like separating\n\"this is what it looks like to declare a value\" from \"this is what a\npassed value looks like\". And then use \"unsigned char v[20]\" for the\nformer and \"unsigned char *\" for the latter.\n\n-Peff\n"},{"id":"172968","messageId":"20110805110302.GA23619@sigill.intra.peff.net","threadId":"27801","inReplyTo":"20110804224354.GA27476@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 0/5] macro-based key/value maps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-05T11:03:02Z","receivedAt":"2011-08-05T11:03:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 04, 2011 at 04:43:54PM -0600, Jeff King wrote:\n\n> Well, if you like that, then here is the end-result of what the\n> persistent version would look like. It's quite convenient to use, but an\n> awful pain to debug. It's done entirely in the preprocessor; I suspect\n> if I wrote the code generation externally, that would be easier and more\n> readable (and there are one or two places where we could be slightly\n> more efficient, that are just difficult to implement via the\n> preprocessor).\n> \n> [1/5]: implement generic key/value map\n> [2/5]: fast-export: use object to uint32 map instead of \"decorate\"\n> [3/5]: decorate: use \"map\" for the underlying implementation\n> [4/5]: map: implement persistent maps\n> [5/5]: implement metadata cache subsystem\n\nSide note:\n\n Commits 1, 4, and 5 introduce infrastructure in the form of static\n functions and macros that contain functions that call the statics. But\n they don't actually instantiate the macro functions themselves, so\n they won't compile with -Werror (due to the \"unused static\" warning)\n until there is some calling code.\n\n That hurts bisectability a little if you compile with -Werror (you\n need to add -Wno-error=unused-function). I don't know how much we\n care.\n\n-Peff\n"},{"id":"172979","messageId":"4E3C0CD9.4020902@lsrfire.ath.cx","threadId":"27801","inReplyTo":"20110805110302.GA23619@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 0/5] macro-based key/value maps","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-08-05T15:31:37Z","receivedAt":"2011-08-05T15:31:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.08.2011 13:03, schrieb Jeff King:\n> Commits 1, 4, and 5 introduce infrastructure in the form of static\n> functions and macros that contain functions that call the statics. But\n> they don't actually instantiate the macro functions themselves, so\n> they won't compile with -Werror (due to the \"unused static\" warning)\n> until there is some calling code.\n> \n> That hurts bisectability a little if you compile with -Werror (you\n> need to add -Wno-error=unused-function). I don't know how much we\n> care.\n\nI don't know either, but you could avoid the issue by adding a test-maps\ncommand in the first patch and exercising the new functionality a bit.\n\nRené\n"},{"id":"173009","messageId":"20110806063052.GA3583@sigill.intra.peff.net","threadId":"27801","inReplyTo":"4E3C0CD9.4020902@lsrfire.ath.cx","subject":"Re: [RFC/PATCH 0/5] macro-based key/value maps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-06T06:30:53Z","receivedAt":"2011-08-06T06:30:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 05, 2011 at 05:31:37PM +0200, René Scharfe wrote:\n\n> Am 05.08.2011 13:03, schrieb Jeff King:\n> > Commits 1, 4, and 5 introduce infrastructure in the form of static\n> > functions and macros that contain functions that call the statics. But\n> > they don't actually instantiate the macro functions themselves, so\n> > they won't compile with -Werror (due to the \"unused static\" warning)\n> > until there is some calling code.\n> > \n> > That hurts bisectability a little if you compile with -Werror (you\n> > need to add -Wno-error=unused-function). I don't know how much we\n> > care.\n> \n> I don't know either, but you could avoid the issue by adding a test-maps\n> command in the first patch and exercising the new functionality a bit.\n\nYes, but then the final git executable carries around dead code for the\ntest map and cache types. There are ways to split the macros versus\ntheir instantiation so that the test instantiations only live in the\ntest-map program, but then that would bring back the \"static is not\nused\" error.\n\nMaybe carrying the dead code isn't that big a deal. It's not that much\nextra code.\n\n-Peff\n"}]}