{"thread":{"id":"27788","subject":"[RFC/PATCH 0/5] generation numbers for faster traversals","startedAt":"2011-07-11T16:13:32Z","lastAt":"2011-07-14T16:26:11Z","messageCount":35,"participants":["Jeff King","Shawn Pearce","Clemens Buchacher","Junio C Hamano","Illia Bobyr","Miles Bader","Jakub Narebski","John Szakmeister"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"171072","messageId":"20110711161332.GA10057@sigill.intra.peff.net","threadId":"27788","inReplyTo":null,"subject":"[RFC/PATCH 0/5] generation numbers for faster traversals","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:13:32Z","receivedAt":"2011-07-11T16:13:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"So here's my series for using cached generations with \"tag --contains\".\nI already posted some numbers here:\n\n  http://article.gmane.org/gmane.comp.version-control.git/176807\n\nBut to recap, this seems to be about as fast as limiting by timestamp,\nbut without the skew issues. It uses 24 bytes per commit of disk\nstorage for the cache (about 6 megabytes for linux-2.6).\n\nIf we like this approach, we could do something similar for \"branch\n--contains\", and possibly move \"name-rev\" to use generations instead of\ntimestamps with a timestamp slop.\n\nThese patches are built on top of ffc4b80 (tag: speed up --contains\ncalculation, 2011-06-11), the first commit from jk/tag-contains-ab.\n\n  [1/5]: decorate: allow storing values instead of pointers\n  [2/5]: add object-cache infrastructure\n  [3/5]: commit: add commit_generation function\n  [4/5]: pretty: support %G to show the generation number of a commit\n  [5/5]: limit \"contains\" traversals based on commit generation\n\n-Peff\n"},{"id":"171073","messageId":"20110711161649.GA10418@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161332.GA10057@sigill.intra.peff.net","subject":"[PATCH 1/5] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:16:50Z","receivedAt":"2011-07-11T16:16:50Z","isPatch":true,"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 <peff@peff.net>\n---\n Documentation/technical/api-decorate.txt |  170 +++++++++++++++++++++++++++++-\n builtin/fast-export.c                    |   32 ++----\n decorate.c                               |  102 ++++++++++++-------\n decorate.h                               |   22 ++++-\n 4 files changed, 263 insertions(+), 63 deletions(-)\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 1d52a6c..8d10b66 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -1,6 +1,172 @@\n decorate API\n ============\n \n-Talk about <decorate.h>\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 before any objects are added to the mapping.\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\tusing the `stride` field (see the description of\n+\t\t`stride` below, or the \"Examples\" section).\n+\n+\t`stride`:::\n+\t\tThe size of a single object_decoration record.\n+\t\tTechnically this can be computed as a function of the\n+\t\twidth, but it is here for ease-of-use.\n+\n+\t`end`:::\n+\t\tA pointer to storage just past the end of the `hash`\n+\t\tarray. This can be used as a boundary for iterating the\n+\t\titems in the hash (see \"Examples\" below). Technically\n+\t\tthis can be computed as a function of the hash pointer,\n+\t\tthe size field, and the stride, but is here for\n+\t\tease-of-use.\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+\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+\tunsigned char *p;\n+\tfor (p = longs.hash; p < longs.end; p += longs.stride) {\n+\t\tstruct object_decoration *e = (struct object_decoration *)p;\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..c053f1f 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@@ -536,20 +525,19 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)\n \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+\tunsigned char *p;\n \n \tf = fopen(file, \"w\");\n \tif (!f)\n \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n \n-\tfor (i = 0; i < idnums.size; i++) {\n+\tfor (p = idnums.hash; p < idnums.end; p += idnums.stride) {\n+\t\tstruct object_decoration *deco = (struct object_decoration *)p;\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;\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..55ebaee 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -6,6 +6,11 @@\n #include \"object.h\"\n #include \"decorate.h\"\n \n+#define WIDTH(n) ((n)->width ? (n)->width : sizeof(void *))\n+#define REF_OFFSET(n, i) ((n)->hash + ((i) * n->stride))\n+#define REF_OBJECT(n, obj) (REF_OFFSET(n, hash_obj(obj, n->size)))\n+#define OBJ(p) ((struct object_decoration *)(p))\n+\n static unsigned int hash_obj(const struct object *obj, unsigned int n)\n {\n \tunsigned int hash;\n@@ -14,75 +19,100 @@ 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 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+\tunsigned long width = WIDTH(n);\n+\tunsigned char *p = REF_OBJECT(n, base);\n+\n+\twhile (OBJ(p)->base) {\n+\t\tstruct object_decoration *e = OBJ(p);\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\tp += n->stride;\n+\t\tif (p >= n->end)\n+\t\t\tp = n->hash;\n \t}\n-\thash[j].base = base;\n-\thash[j].decoration = decoration;\n+\tOBJ(p)->base = base;\n+\tmemcpy(OBJ(p)->decoration, decoration, width);\n \tn->nr++;\n-\treturn NULL;\n+\treturn 0;\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+\tunsigned char *old_end = n->end;\n+\tunsigned char *p;\n \n-\tn->size = (old_size + 1000) * 3 / 2;\n-\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n+\tn->stride = sizeof(struct object_decoration) + WIDTH(n);\n+\tn->size = (n->size + 1000) * 3 / 2;\n+\tn->hash = xcalloc(n->size, n->stride);\n+\tn->end = n->hash + (n->size * n->stride);\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+\tfor (p = old_hash; p < old_end; p += n->stride) {\n+\t\tif (!OBJ(p)->base)\n \t\t\tcontinue;\n-\t\tinsert_decoration(n, base, decoration);\n+\t\tinsert_decoration(n, OBJ(p)->base, OBJ(p)->decoration, NULL);\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+\tvoid *old = NULL;\n \n-\tif (nr > n->size * 2 / 3)\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+\tif (n->nr + 1 > 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+\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-\tunsigned int j;\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+\tconst unsigned char *p;\n \n \t/* nothing to lookup */\n \tif (!n->size)\n \t\treturn NULL;\n-\tj = hash_obj(obj, n->size);\n+\n+\tp = REF_OBJECT(n, obj);\n \tfor (;;) {\n-\t\tstruct object_decoration *ref = n->hash + j;\n+\t\tstruct object_decoration *ref = OBJ(p);\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\tp += n->stride;\n+\t\tif (p >= n->end)\n+\t\t\tp = n->hash;\n \t}\n }\ndiff --git a/decorate.h b/decorate.h\nindex e732804..b75054a 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -3,16 +3,32 @@\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+\tunsigned 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+\tunsigned int stride; /* size of a single record */\n+\tunsigned char *end; /* end of the hash array */\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 #endif\n-- \n1.7.6.37.g989c6\n"},{"id":"171074","messageId":"20110711161754.GB10418@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161332.GA10057@sigill.intra.peff.net","subject":"[PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:17:54Z","receivedAt":"2011-07-11T16:17:54Z","isPatch":true,"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, object-cache, which stores\na mapping of objects to values in a concise and efficient\nform. See the added API documentation for details.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nAs I mentioned earlier, I wanted this to be generic and size-agnostic,\nbecause I'd also like to try caching patch-ids for git-cherry.\n\n Documentation/technical/api-decorate.txt     |    3 +\n Documentation/technical/api-object-cache.txt |  101 +++++++++++++\n Makefile                                     |    2 +\n object-cache.c                               |  204 ++++++++++++++++++++++++++\n object-cache.h                               |   32 ++++\n 5 files changed, 342 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-object-cache.txt\n create mode 100644 object-cache.c\n create mode 100644 object-cache.h\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 8d10b66..c851f59 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+object-cache API for persistent storage.\n+\n Data Structures\n ---------------\n \ndiff --git a/Documentation/technical/api-object-cache.txt b/Documentation/technical/api-object-cache.txt\nnew file mode 100644\nindex 0000000..ecead4c\n--- /dev/null\n+++ b/Documentation/technical/api-object-cache.txt\n@@ -0,0 +1,101 @@\n+Object Cache API\n+================\n+\n+The object cache API is meant to store a cache of per-object values. The\n+aim is for robustness, speed, and simplicity. The stored data must be of\n+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 only\n+when `object_cache_write` is called.\n+\n+The disk storage consists of a single file per cache, located in the\n+`$GIT_DIR/cache` directory. Each file contains a list of rows ordered by\n+sha1. Each row contains a binary sha1, followed by the fixed-size data\n+mapped to that sha1.\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+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 object_cache`::\n+\n+\tThis structure represents a single object cache. Its contents\n+\tshould be considered opaque by calling code.\n++\n+\tThe `fd`, `disk_entries`, `disk_nr`, and `record_size` fields\n+\trepresent the mmap'd on-disk data. The `mem` field represents\n+\tthe in-memory data (see the decorate API for details).\n+\n+\n+Functions\n+---------\n+\n+`object_cache_init`::\n+\n+\tInitialize a new object cache; this must be called before any\n+\tother functions are called on the 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., pass\n+\tin `sizeof(uint32_t)` to store 32-bit integers).\n+\n+`object_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+`object_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+`object_cache_write`::\n+\n+\tMerge the in-memory and existing disk entries, and write the\n+\tresulting cache to disk, under the name `$GIT_DIR/cache/$name`.\n+\tIf no in-memory entries exist, the on-disk cache will be left\n+\tunchanged.\n+\n+`object_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+`object_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..dd05579 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -535,6 +535,7 @@ LIB_H += merge-recursive.h\n LIB_H += notes.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n+LIB_H += object-cache.h\n LIB_H += object.h\n LIB_H += pack.h\n LIB_H += pack-refs.h\n@@ -628,6 +629,7 @@ LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\n LIB_OBJS += notes-merge.o\n+LIB_OBJS += object-cache.o\n LIB_OBJS += object.o\n LIB_OBJS += pack-check.o\n LIB_OBJS += pack-refs.o\ndiff --git a/object-cache.c b/object-cache.c\nnew file mode 100644\nindex 0000000..d019f0a\n--- /dev/null\n+++ b/object-cache.c\n@@ -0,0 +1,204 @@\n+#include \"cache.h\"\n+#include \"object-cache.h\"\n+#include \"sha1-lookup.h\"\n+#include \"object.h\"\n+\n+static const char *object_cache_path(const char *name)\n+{\n+\treturn git_path(\"cache/%s\", name);\n+}\n+\n+static void open_disk_cache(struct object_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(c->fd);\n+\t\tc->fd = -1;\n+\t\treturn;\n+\t}\n+\n+\tc->disk_entries = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE,\n+\t\t\t\tc->fd, 0);\n+\tc->disk_nr = sb.st_size / c->record_size;\n+}\n+\n+void object_cache_init(struct object_cache *c, const char *name, int width)\n+{\n+\tmemset(c, 0, sizeof(*c));\n+\tc->record_size = 20 + width;\n+\tc->mem.width = width;\n+\topen_disk_cache(c, object_cache_path(name));\n+}\n+\n+static void *lookup_disk(const struct object_cache *c,\n+\t\t\t const struct object *obj)\n+{\n+\tint pos;\n+\n+\tpos = sha1_entry_pos(c->disk_entries, c->record_size, 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 * c->record_size) + 20;\n+}\n+\n+const void *object_cache_lookup(const struct object_cache *c,\n+\t\t\t\t\t const struct object *obj)\n+{\n+\tvoid *r;\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 object_cache_add(struct object_cache *c, const struct object *obj,\n+\t\t      const void *value)\n+{\n+\tadd_decoration_value(&c->mem, obj, value, NULL);\n+}\n+\n+static unsigned char *flatten_mem_entries(struct object_cache *c)\n+{\n+\tunsigned char *p;\n+\tunsigned char *ret;\n+\tint nr;\n+\n+\tret = xmalloc(c->mem.nr * c->record_size);\n+\tnr = 0;\n+\tfor (p = c->mem.hash; p < c->mem.end; p += c->mem.stride) {\n+\t\tstruct object_decoration *e = (struct object_decoration *)p;\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 * c->record_size);\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+int object_cache_write(struct object_cache *c, const char *name)\n+{\n+\tconst char *path = object_cache_path(name);\n+\tstruct strbuf tempfile = STRBUF_INIT;\n+\tint fd;\n+\tunsigned char *mem_entries;\n+\tint i, j;\n+\tint r;\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+\tmem_entries = flatten_mem_entries(c);\n+\tqsort(mem_entries, c->mem.nr, c->record_size, void_hashcmp);\n+\n+#define WRITE_ENTRY(e) \\\n+do { \\\n+\tif (write_in_full(fd, e, c->record_size) < 0) { \\\n+\t\tclose(fd); \\\n+\t\tunlink(tempfile.buf); \\\n+\t\tstrbuf_release(&tempfile); \\\n+\t\tfree(mem_entries); \\\n+\t\treturn -1; \\\n+\t} \\\n+} while (0)\n+\n+\ti = j = 0;\n+\twhile (i < c->mem.nr && j < c->disk_nr) {\n+\t\tunsigned char *mem = mem_entries + (i * c->record_size);\n+\t\tunsigned char *disk = c->disk_entries + (j * c->record_size);\n+\t\tint cmp = hashcmp(mem, disk);\n+\n+\t\t/* replace disk entries with in-memory ones */\n+\t\tif (cmp == 0)\n+\t\t\tj++;\n+\t\telse if (cmp < 0) {\n+\t\t\tWRITE_ENTRY(mem);\n+\t\t\ti++;\n+\t\t}\n+\t\telse {\n+\t\t\tWRITE_ENTRY(disk);\n+\t\t\tj++;\n+\t\t}\n+\t}\n+\twhile (i < c->mem.nr) {\n+\t\tunsigned char *mem = mem_entries + (i * c->record_size);\n+\t\tWRITE_ENTRY(mem);\n+\t\ti++;\n+\t}\n+\twhile (j < c->disk_nr) {\n+\t\tunsigned char *disk = c->disk_entries + (j * c->record_size);\n+\t\tWRITE_ENTRY(disk);\n+\t\tj++;\n+\t}\n+#undef WRITE_ENTRY\n+\n+\tfree(mem_entries);\n+\n+\tif (close(fd) < 0 || rename(tempfile.buf, path) < 0)\n+\t\tr = -1;\n+\telse\n+\t\tr = 0;\n+\n+\tunlink(tempfile.buf);\n+\tstrbuf_release(&tempfile);\n+\treturn r;\n+}\n+\n+int object_cache_lookup_uint32(const struct object_cache *c,\n+\t\t\t       const struct object *obj,\n+\t\t\t       uint32_t *value)\n+{\n+\tconst uint32_t *out;\n+\n+\tif (c->record_size != 24)\n+\t\tdie(\"BUG: size mismatch in object cache lookup (%d != 24)\",\n+\t\t    c->record_size);\n+\n+\tout = object_cache_lookup(c, obj);\n+\tif (!out)\n+\t\treturn -1;\n+\n+\t*value = ntohl(*out);\n+\treturn 0;\n+}\n+\n+void object_cache_add_uint32(struct object_cache *c,\n+\t\t\t     const struct object *obj,\n+\t\t\t     uint32_t value)\n+{\n+\tif (c->record_size != 24)\n+\t\tdie(\"BUG: size mismatch in object cache add (%d != 24)\",\n+\t\t    c->record_size);\n+\n+\tvalue = htonl(value);\n+\tobject_cache_add(c, obj, &value);\n+}\ndiff --git a/object-cache.h b/object-cache.h\nnew file mode 100644\nindex 0000000..b869f1e\n--- /dev/null\n+++ b/object-cache.h\n@@ -0,0 +1,32 @@\n+#ifndef OBJECT_CACHE_H\n+#define OBJECT_CACHE_H\n+\n+#include \"decorate.h\"\n+\n+struct object_cache {\n+\t/* mmap'd disk entries */\n+\tint fd;\n+\tunsigned char *disk_entries;\n+\tint disk_nr;\n+\tint record_size;\n+\n+\t/* in memory entries */\n+\tstruct decoration mem;\n+};\n+\n+void object_cache_init(struct object_cache *, const char *name, int width);\n+const void *object_cache_lookup(const struct object_cache *,\n+\t\t\t\tconst struct object *);\n+void object_cache_add(struct object_cache *, const struct object *,\n+\t\t      const void *value);\n+int object_cache_write(struct object_cache *, const char *name);\n+\n+/* Convenience wrappers around object_cache_{lookup,add} */\n+int object_cache_lookup_uint32(const struct object_cache *,\n+\t\t\t       const struct object *,\n+\t\t\t       uint32_t *value);\n+void object_cache_add_uint32(struct object_cache *,\n+\t\t\t     const struct object *,\n+\t\t\t     uint32_t value);\n+\n+#endif /* OBJECT_CACHE_H */\n-- \n1.7.6.37.g989c6\n"},{"id":"171075","messageId":"20110711161814.GC10418@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161332.GA10057@sigill.intra.peff.net","subject":"[PATCH 3/5] commit: add commit_generation function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:18:14Z","receivedAt":"2011-07-11T16:18:14Z","isPatch":true,"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 <peff@peff.net>\n---\n commit.c |   48 ++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h |    2 ++\n 2 files changed, 50 insertions(+), 0 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac337c7..d412e05 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 \"object-cache.h\"\n \n int save_commit_buffer = 1;\n \n@@ -878,3 +879,50 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tstrbuf_release(&buffer);\n \treturn result;\n }\n+\n+static struct object_cache generations;\n+\n+static unsigned long commit_generation_recurse(struct commit *c)\n+{\n+\tstruct commit_list *p;\n+\tuint32_t r;\n+\n+\tif (!object_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+\tobject_cache_add_uint32(&generations, &c->object, r);\n+\treturn r;\n+}\n+\n+static void write_generation_cache(void)\n+{\n+\tobject_cache_write(&generations, \"generations\");\n+}\n+\n+unsigned long commit_generation(const struct commit *commit)\n+{\n+\tstatic int initialized;\n+\n+\tif (!initialized) {\n+\t\tobject_cache_init(&generations, \"generations\", sizeof(uint32_t));\n+\t\tatexit(write_generation_cache);\n+\t\tinitialized = 1;\n+\t}\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":"171076","messageId":"20110711161827.GD10418@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161332.GA10057@sigill.intra.peff.net","subject":"[PATCH 4/5] pretty: support %G to show the generation number of a commit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:18:27Z","receivedAt":"2011-07-11T16:18:27Z","isPatch":true,"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 <peff@peff.net>\n---\n Documentation/pretty-formats.txt |    1 +\n pretty.c                         |    3 +++\n 2 files changed, 4 insertions(+), 0 deletions(-)\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,\n-- \n1.7.6.37.g989c6\n"},{"id":"171077","messageId":"20110711161846.GE10418@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161332.GA10057@sigill.intra.peff.net","subject":"[PATCH 5/5] limit \"contains\" traversals based on commit generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:18:46Z","receivedAt":"2011-07-11T16:18:46Z","isPatch":true,"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 <peff@peff.net>\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":"171080","messageId":"20110711163959.GA29781@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161649.GA10418@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:39:59Z","receivedAt":"2011-07-11T16:39:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 12:16:50PM -0400, Jeff King wrote:\n\n> diff --git a/decorate.h b/decorate.h\n> index e732804..b75054a 100644\n> --- a/decorate.h\n> +++ b/decorate.h\n> @@ -3,16 +3,32 @@\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> +\tunsigned 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> +\tunsigned int stride; /* size of a single record */\n> +\tunsigned char *end; /* end of the hash array */\n>  };\n\nAs you can see here, there's a bit of C magic here. We don't know what\nwe're storing in the object_decoration struct, so it has a variable\nsize. So there were two subtle things I was concerned about:\n\n  1. Not violating alignment rules when accessing items.\n\n  2. Not violating strict aliasing rules.\n\nI think (1) is OK via the add/lookup interface. It takes void pointers\nto objects to store and to retrieve into (and knows the width via the\nwidth field above). And then we memcpy() into and out of the flex-array.\nWhich means you never access the bytes in the flex array as an \"int\" or\nwhatever; you memcpy them into an _actual_ int, and then access them.\n\nI don't think we have to worry about strict aliasing, for two reasons:\n\n  1. Pointers to char (or unsigned char) are assumed to be aliases for\n     other things by gcc's strict aliasing rules. Because they are the\n     only way to do byte-level pointer arithmetic, which makes them\n     useful for stuff like this.\n\n  2. The pointer accesses are hidden across function call boundaries,\n     anyway, so I suspect the optimizer has to assume the worst.\n\nWhat's slightly worrisome to me is the iteration code in fast-export.c\nthat touches the decoration struct more directly:\n\n> +\tfor (p = idnums.hash; p < idnums.end; p += idnums.stride) {\n> +\t\tstruct object_decoration *deco = (struct object_decoration *)p;\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\nHere we're directly casting the bytes to a uint32 and accessing them.\nI'm not sure if this can create alignment issues. The bytes are in a\nstruct which is in an array of such packed structs. I suspect in\npractice that a uint32_t is not a problem, as the data bytes will always\nbe on a 4-byte boundary. It might matter for other types, though.\n\nAs for strict aliasing, I thought that the \"pointer to char can be an\nalias\" rule would save us. But actually, from my reading, the rule is \"a\npointer to char can be an alias to another object\" but not necessarily\nthat \"a pointer to another object can be an alias to char\". What has me\nconfused is that gcc complains about type-punning under -O3 (which turns\non -fstrict-aliasing) with this:\n\n  struct object_decoration *deco = (struct object_decoration *)p;\n  uint32_t mark = *(uint32_t *)deco->decoration;\n  fprintf(\"%\"PRIu32, mark);\n\nbut not with the code in the patch:\n\n  struct object_decoration *deco = (struct object_decoration *)p;\n  uint32_t *mark = (uint32_t *)deco->decoration;\n  fprintf(\"%\"PRIu32, *mark);\n\nso there may be something I'm not understanding.\n\nBut I wonder if the safest thing for both alignment and aliasing would\njust be:\n\n  struct object_decoration *deco = (struct object_decoration *)p;\n  uint32_t mark;\n  memcpy(&mark, deco->decoration, sizeof(mark));\n\nWhich is probably a little slower, but I'm not sure it's worth\nmicro-optimizing this loop[1].\n\n-Peff\n\n[1] Actually, if you read the rest of the patch, you will note that what\n    used to be assignment to or reading from a void pointer in the\n    original decorate.[ch] is now a memcpy, as well. The original\n    probably compiled to a single assignment instruction, and now we\n    loop via memcpy. That's the price of run-time flexibility. I doubt\n    that the extra few instructions are a big deal, considering we by\n    definition have just done a lookup in a hash table.\n"},{"id":"171081","messageId":"20110711164635.GB29781@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711161754.GB10418@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T16:46:35Z","receivedAt":"2011-07-11T16:46:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 12:17:54PM -0400, Jeff King wrote:\n\n> +Storage\n> +-------\n> [...]\n> +The disk storage consists of a single file per cache, located in the\n> +`$GIT_DIR/cache` directory. Each file contains a list of rows ordered by\n> +sha1. Each row contains a binary sha1, followed by the fixed-size data\n> +mapped to that sha1.\n\nThere's nothing else in the file, not even a header. I should probably\nadd at least a version byte, in case we ever do want to change what goes\ninto a cache (in which case we could just blow away what's there and\nregenerate).\n\nWe could also have a \"validity\" field that must match for the cache to\nbe valid. Junio mentioned earlier that you would want to regenerate a\ngenerations cache whenever grafts or replace objects changed. It\nwouldn't be hard to do something like:\n\n  validity = sha1(grafts + replace);\n  if (validity != cache_validity)\n    empty_disk_cache();\n\nAnd then it would just automatically work, without the user having to\nremember to clear the cache.  Calculating the validity would be cheap in\nthe common case (you have no grafts or replace objects), and not much\nmore expensive when you do have them (we have to read that data anyway\nto respect the replacements).\n\n-Peff\n"},{"id":"171083","messageId":"CAJo=hJvv7a_8FJfHERxdwvMLVkpun-u-hR+ds40JuVNn2Lyb7A@mail.gmail.com","threadId":"27788","inReplyTo":"20110711164635.GB29781@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-07-11T16:58:28Z","receivedAt":"2011-07-11T16:58:28Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 11, 2011 at 09:46, Jeff King <peff@peff.net> wrote:\n> On Mon, Jul 11, 2011 at 12:17:54PM -0400, Jeff King wrote:\n>\n>> +Storage\n>> +-------\n>> [...]\n>> +The disk storage consists of a single file per cache, located in the\n>> +`$GIT_DIR/cache` directory. Each file contains a list of rows ordered by\n>> +sha1. Each row contains a binary sha1, followed by the fixed-size data\n>> +mapped to that sha1.\n>\n> There's nothing else in the file, not even a header. I should probably\n> add at least a version byte, in case we ever do want to change what goes\n> into a cache (in which case we could just blow away what's there and\n> regenerate).\n\nPlease do. We don't always need to invent a new version... but for a\ncache file its probably more common than the PACK network stream, or\nthe pack-*.idx file. And its painful to shoehorn in a version change\nafter the fact.\n\n> We could also have a \"validity\" field that must match for the cache to\n> be valid. Junio mentioned earlier that you would want to regenerate a\n> generations cache whenever grafts or replace objects changed. It\n> wouldn't be hard to do something like:\n>\n>  validity = sha1(grafts + replace);\n>  if (validity != cache_validity)\n>    empty_disk_cache();\n>\n> And then it would just automatically work, without the user having to\n> remember to clear the cache.  Calculating the validity would be cheap in\n> the common case (you have no grafts or replace objects), and not much\n> more expensive when you do have them (we have to read that data anyway\n> to respect the replacements).\n\nThis is a pretty good idea too. Saves the hapless user from surprises\nwhen they forget the cache exists, but they changed grafts or replace\ndata.\n\n-- \nShawn.\n"},{"id":"171093","messageId":"20110711175709.GA6245@toss.lan","threadId":"27788","inReplyTo":"20110711161814.GC10418@sigill.intra.peff.net","subject":"Re: [PATCH 3/5] commit: add commit_generation function","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-11T17:57:09Z","receivedAt":"2011-07-11T17:57:09Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Mon, Jul 11, 2011 at 12:18:14PM -0400, Jeff King wrote:\n>\n> +unsigned long commit_generation(const struct commit *commit)\n> +{\n[...]\n> +\t/* drop const because we may call parse_commit */\n> +\treturn commit_generation_recurse((struct commit *)commit);\n> +}\n\nOut of curiosity, why make it const in the first place?\n\nClemens\n"},{"id":"171098","messageId":"7vr55wd1hw.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"20110711161649.GA10418@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] decorate: allow storing values instead of pointers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-11T19:06:08Z","receivedAt":"2011-07-11T19:06:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\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> +\tunsigned char *old_end = n->end;\n> +\tunsigned char *p;\n>  \n> -\tn->size = (old_size + 1000) * 3 / 2;\n> -\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n> +\tn->stride = sizeof(struct object_decoration) + WIDTH(n);\n\nThis value should not change once it is initialized, or all h*ll breaks\nloose while accessing the old-hash, right?  Just wondering if it makes the\nintention clearer if the function had something like this in it:\n\n\tif (!old_size) {\n\t\t/* initial */\n                n->stride = ...\n\t} else {\n\t\t/* rehash to grow */\n\t}\n\nI am mostly worried about both width and stride being assignable\nfields. An alternative may be to expose\n\n\tint decoration_stride(struct decoration *n)\n        {\n        \treturn sizeof(struct object_decoration) + WIDTH(n);\n\t}\n\nto the outside callers and drop \"stride\" field.\n"},{"id":"171100","messageId":"7vliw4d1hu.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"20110711161754.GB10418@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-11T19:17:56Z","receivedAt":"2011-07-11T19:17:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> As I mentioned earlier, I wanted this to be generic and size-agnostic,\n> because I'd also like to try caching patch-ids for git-cherry.\n\nSounds like a good thing to aim for, but \"Object Cache\" sounded too much\nlike giving access to the object data that is faster than either loose or\npacked objects.\n\nThis is a completely unrelated tangent but because you brought up\npatch-ids ;-), the other day I tried to rebase mm patches on top of\nupdated linux-next while trying to help Andrew, and noticed that in real\nlife, many \"duplicate\" patches you find in updated upstream are \"slightly\nreworded better\" and \"rebase --skip\" is often the right thing to do, but\nit is often very difficult to diagnose, as (1) the patch you are trying to\napply from your old series may be part of a long patch series, and (2) the\ncommit you are trying to re-apply the said patch to, i.e. the updated\nupstream, may already contain many of these semi-duplicate patches. The\nconflict resulting from \"am -3\" in such a situation is not very pleasant\nto look at (it looks mostly as if you are reverting the effect of updated\nversions of later patches in your series).\n"},{"id":"171103","messageId":"20110711211013.GA30155@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110711175709.GA6245@toss.lan","subject":"Re: [PATCH 3/5] commit: add commit_generation function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T21:10:13Z","receivedAt":"2011-07-11T21:10:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 07:57:09PM +0200, Clemens Buchacher wrote:\n\n> On Mon, Jul 11, 2011 at 12:18:14PM -0400, Jeff King wrote:\n> >\n> > +unsigned long commit_generation(const struct commit *commit)\n> > +{\n> [...]\n> > +\t/* drop const because we may call parse_commit */\n> > +\treturn commit_generation_recurse((struct commit *)commit);\n> > +}\n> \n> Out of curiosity, why make it const in the first place?\n\nTwo reasons:\n\n  1. At the API layer, it's conceptually const. We're not changing the\n     commit, but the lazy load of parse_commit is an implementation\n     detail.\n\n     In C++, you would stick a \"mutable\" tag on the parts we lazily load\n     via parse_object. Here, we have to cast.\n\n     This isn't C++, of course, and while we do follow some\n     object-oriented principles, it's not necessarily worth fighting the\n     language like this for the sake of a const. And I would be fine\n     with saying \"all commit objects should not be marked const, because\n     we may lazily parse them, and it's well known that they are not to\n     be freed anyway\".\n\n     But...\n\n  2. The callsite in pretty.c has a const commit, so we have to cast\n     somewhere, and this spot seemed the most appropriate to me (or we\n     could drop the consts there, which I would be OK with).\n\n-Peff\n"},{"id":"171107","messageId":"20110711212032.GB30155@sigill.intra.peff.net","threadId":"27788","inReplyTo":"7vr55wd1hw.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/5] decorate: allow storing values instead of pointers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T21:20:32Z","receivedAt":"2011-07-11T21:20:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 12:06:08PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\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> > +\tunsigned char *old_end = n->end;\n> > +\tunsigned char *p;\n> >  \n> > -\tn->size = (old_size + 1000) * 3 / 2;\n> > -\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n> > +\tn->stride = sizeof(struct object_decoration) + WIDTH(n);\n> \n> This value should not change once it is initialized, or all h*ll breaks\n> loose while accessing the old-hash, right?  Just wondering if it makes the\n> intention clearer if the function had something like this in it:\n> \n> \tif (!old_size) {\n> \t\t/* initial */\n>                 n->stride = ...\n> \t} else {\n> \t\t/* rehash to grow */\n> \t}\n\nYes, things will break horribly if you ever change the width. I wonder\nif we can get some language support with:\n\n  struct decoration {\n     ...\n     const int width;\n     ...\n  };\n\nwhich would require that calling code set the width during\ninitialization. Doing anything else is more or less insane, although it\ndoes make trouble for the object-cache code, which uses a run-time\nfunction to initialize itself.  But as it's somewhat tightly coupled\nwith decorations and knows what it's doing, I would not be opposed to\ncasting away the constness in that one spot with a comment as a\nworkaround.\n\n> I am mostly worried about both width and stride being assignable\n> fields. An alternative may be to expose\n> \n> \tint decoration_stride(struct decoration *n)\n>         {\n>         \treturn sizeof(struct object_decoration) + WIDTH(n);\n> \t}\n> \n> to the outside callers and drop \"stride\" field.\n\nYeah, I considered that (the \"end\" field is calculable, too). I just\ndidn't want the overhead of:\n\n  for (p = d->hash; p < decoration_end(d); p += decoration_stride(d))\n     ...\n\nBut I suppose we can inline both of those and let the optimizer deal\nwith hoisting the actual calculations them out of the loop. Or maybe I'm\njust being stupid and optimizing too early. Speed is definitely one of\nmy criteria for this series, though.\n\n-Peff\n"},{"id":"171113","messageId":"20110711220107.GC30155@sigill.intra.peff.net","threadId":"27788","inReplyTo":"7vliw4d1hu.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-11T22:01:07Z","receivedAt":"2011-07-11T22:01:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 12:17:56PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > As I mentioned earlier, I wanted this to be generic and size-agnostic,\n> > because I'd also like to try caching patch-ids for git-cherry.\n> \n> Sounds like a good thing to aim for, but \"Object Cache\" sounded too much\n> like giving access to the object data that is faster than either loose or\n> packed objects.\n\nAgreed. I'm open to better suggestions for the name. I would have just\ncalled it a straight out \"cache\" as it can be used for caching anything,\nbut that term is already taken in git. :)\n\nYou could argue we are caching metadata about objects, so something like\nobject_metadata_cache might be OK. I dunno.\n\n> This is a completely unrelated tangent but because you brought up\n> patch-ids ;-), the other day I tried to rebase mm patches on top of\n> updated linux-next while trying to help Andrew, and noticed that in real\n> life, many \"duplicate\" patches you find in updated upstream are \"slightly\n> reworded better\" and \"rebase --skip\" is often the right thing to do, but\n> it is often very difficult to diagnose, as (1) the patch you are trying to\n> apply from your old series may be part of a long patch series, and (2) the\n> commit you are trying to re-apply the said patch to, i.e. the updated\n> upstream, may already contain many of these semi-duplicate patches. The\n> conflict resulting from \"am -3\" in such a situation is not very pleasant\n> to look at (it looks mostly as if you are reverting the effect of updated\n> versions of later patches in your series).\n\nYeah, I run into this in git.git because I aggressively rebase my topics\non what you apply upstream. Usually it's very helpful, as I either skip\npatches automatically if patch-ids match (which means I throw away my\nversion in favor of what you marked up based on list comments), or I get\na conflict that looks like:\n\n  <<<<<<< HEAD\n  /* what you marked up */\n  =======\n  /* what I originally had */\n  >>>>>>> jk/foobar\n\nand I can easily confirm that what you have is better and resolve in\nfavor (or if not better, I can go on the list and complain :) ).\n\nBut what I sometimes run into, and what I think you are mentioning with\n\"looks as if you are reverting\" is when you have changes that textually\nbuild on one another. For example:\n\n  git init repo &&\n  cd repo &&\n\n  # make one base commit\n  echo base >base && git add base && git commit -m base &&\n\n  # now make a \"topic\" of two commits that textually build on one another\n  git checkout -b topic &&\n  echo one >file && git add file && git commit -m one &&\n  echo two >file && git add file && git commit -m two &&\n\n  # now pretend that they got applied upstream, but with a\n  # slight tweak only in the first patch so that patch-ids don't match\n  git checkout master &&\n  echo 'modified one' >file && git add file && git commit -m one &&\n  echo 'two' >file && git add file && git commit -m two &&\n\n  # and now rebase the series on top\n  git rebase master topic\n\nWhat you would like to see (and what you would see without the second\ncommit) is:\n\n  <<<<<<< HEAD\n  modified one\n  =======\n  one\n  >>>>>>> one\n\nwhich quite obviously shows that your patch was marked up, and the\nresolution is clear. But with a commit no top, you get:\n\n  <<<<<<< HEAD\n  two\n  =======\n  one\n  >>>>>>> one\n\nwhich looks like you are reverting, because of course you are building\non top of the finished series.\n\nI think the only solution would be to do a better job of heuristically\nmatching up commits when rebase skips already-in-upstream commits. I\nknow we discussed it recently and decided that the false positives are\ntoo dangerous for it to just skip based on something like the commit\nmessage. I.e., even though they probably _are_ the same commit, the fact\nthat the patches don't match is actually really important, and the user\nneeds to see the conflict.\n\nBut we can show them the differences in other ways besides trying to\napply the patch and coming up with a conflict. For example, for any\ncommit that we think we have already in upstream (by commit message or\nwhatever heuristic), but whose patch-id is not found, we could show the\ninterdiff between the possible upstream commit and the rebased commit,\nand say \"Do you want to skip this?\".\n\nThen instead of having to look at the merge conflict of commit one on\ntop of upstream's commit two, you get to see what commit one would look\nlike on top of the upstream's commit one. Which is a lot more readable.\nSo the human is still involved, and still gets to see the conflicting\ntext, but it's in a much more useful form.\n\nDoes that make sense? In this example, I would expect something like:\n\n  $ git rebase master topic\n  Applying: one\n  Using index info to reconstruct a base tree...\n  Falling back to patching base and 3-way merge...\n  Auto-merging file\n  CONFLICT (content): Merge conflict in file\n  Failed to merge in the changes.\n  Patch failed at 0001 one\n\n  hint: this commit may already be in upstream as 1234abcd;\n  hint: the differences between that commit and this one are:\n\n  diff --git a/file b/file\n  --- a/file\n  +++ b/file\n  @@ -1 +1 @@\n  -modified one\n  +one\n\n  When you have resolved this problem run \"git rebase --continue\".\n  If you would prefer to skip this patch, instead run \"git rebase --skip\".\n  To restore the original branch and stop rebasing run \"git rebase --abort\".\n\nAnd then the user can decide to look at the conflict, or skip based on\nthe interdiff. For that matter, we can let them run the equivalent of\nthe interdiff themselves if we simply give them commit sha1s for the\npotential upstream and the patch we're applying.\n\n-Peff\n"},{"id":"171117","messageId":"7vk4bo9ze5.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"20110711220107.GC30155@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-11T23:21:54Z","receivedAt":"2011-07-11T23:21:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ... But with a commit no top, you get:\n>\n>   <<<<<<< HEAD\n>   two\n>   =======\n>   one\n>   >>>>>>> one\n>\n> which looks like you are reverting, because of course you are building\n> on top of the finished series.\n\nExactly.\n\n>   $ git rebase master topic\n>   Applying: one\n>   Using index info to reconstruct a base tree...\n>   Falling back to patching base and 3-way merge...\n>   Auto-merging file\n>   CONFLICT (content): Merge conflict in file\n>   Failed to merge in the changes.\n>   Patch failed at 0001 one\n>\n>   hint: this commit may already be in upstream as 1234abcd;\n>   hint: the differences between that commit and this one are:\n>\n>   diff --git a/file b/file\n>   --- a/file\n>   +++ b/file\n>   @@ -1 +1 @@\n>   -modified one\n>   +one\n>\n>   When you have resolved this problem run \"git rebase --continue\".\n>   If you would prefer to skip this patch, instead run \"git rebase --skip\".\n>   To restore the original branch and stop rebasing run \"git rebase --abort\".\n\nActually I do not think identifying the ones that can safely skipped is\nsuch a big issue. The case I am most concerned about is when you see that\n\"two reverted back to one\" (which you obviously want to avoid, to keep the\neffect of the commit the upstream has to have \"two\" on that line), but at\nthe same time when you do not agree with the change that the upstream took\nfor the _current commit_ you are replaying (i.e. you want the final result\nto have \"one\", not \"modified one\" which the upstream has applied).\n\nThe conflict resolution to come up with such an incremental change is very\npainful. You have to avoid the \"s/two/one/\" revert, and you have to keep\nthe \"s/modified one/one\" revert, and you need to know which hunks are\nconflicting due to what (i.e. the former is because a patch similar to the\none you haven't replayed in this rebase session is already in upstream,\nthe latter is the upstream tweaked the current patch you are looking at in\na way you do not agree with).\n\nI do not have a good idea to solve this in mind yet.\n"},{"id":"171118","messageId":"7vfwmc9yfn.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"7vk4bo9ze5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-11T23:42:36Z","receivedAt":"2011-07-11T23:42:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Actually I do not think identifying the ones that can safely skipped is\n> such a big issue. The case I am most concerned about is when you see that\n> \"two reverted back to one\" (which you obviously want to avoid, to keep the\n> effect of the commit the upstream has to have \"two\" on that line), but at\n> the same time ...\n\nIt is even worse if you do not necessarily agree with that \"two\", which\nyou might originally have written \"t w o\". You _still_ want to keep the\nversion from the upstream (i.e. leaving the result as \"two\") while\nreplaying the patch that adds \"one\" (and correcting the change upstream\ndid to make it \"modified one\"), and when it is the \"t w o\" patch's turn,\nyou would want to do the same dance to make an incremental correction to\nthe way the upstream butchered your original change.\n"},{"id":"171119","messageId":"20110712000304.GA32276@sigill.intra.peff.net","threadId":"27788","inReplyTo":"7vk4bo9ze5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-12T00:03:04Z","receivedAt":"2011-07-12T00:03:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 04:21:54PM -0700, Junio C Hamano wrote:\n\n> Actually I do not think identifying the ones that can safely skipped is\n> such a big issue. The case I am most concerned about is when you see that\n> \"two reverted back to one\" (which you obviously want to avoid, to keep the\n> effect of the commit the upstream has to have \"two\" on that line), but at\n> the same time when you do not agree with the change that the upstream took\n> for the _current commit_ you are replaying (i.e. you want the final result\n> to have \"one\", not \"modified one\" which the upstream has applied).\n\nI'm not sure there's a general solution to that. You can't keep the\ncommit you want intact, because you are rebasing and therefore building\non top of the other broken commit. So in a history like:\n\n    B'--C'\n   /\n  A--B--C\n\nYou really want to perform the transformation of B to B', but on top of\nC (i.e., \"git checkout C; git diff B' B | git apply\"). But if B and C\nare textually related, it's going to conflict horribly. And I don't\nthink there is a general solution short of a darcs-style patch algebra.\n\n-Peff\n"},{"id":"171120","messageId":"4E1B91D8.5040500@ronin-capital.com","threadId":"27788","inReplyTo":"7vk4bo9ze5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Illia Bobyr","fromEmail":"illia.bobyr@ronin-capital.com","sentAt":"2011-07-12T00:14:16Z","receivedAt":"2011-07-12T00:14:16Z","isPatch":true,"sender":{"key":"illia.bobyr@ronin-capital.com","avatar":null},"body":"On 7/11/2011 6:21 PM, Junio C Hamano wrote:\n> Jeff King<peff@peff.net>  writes:\n>\n>> ... But with a commit no top, you get:\n>>\n>>    <<<<<<<  HEAD\n>>    two\n>>    =======\n>>    one\n>>    >>>>>>>  one\n>>\n>> which looks like you are reverting, because of course you are building\n>> on top of the finished series.\n> Exactly.\n>\n>>    $ git rebase master topic\n>>    Applying: one\n>>    Using index info to reconstruct a base tree...\n>>    Falling back to patching base and 3-way merge...\n>>    Auto-merging file\n>>    CONFLICT (content): Merge conflict in file\n>>    Failed to merge in the changes.\n>>    Patch failed at 0001 one\n>>\n>>    hint: this commit may already be in upstream as 1234abcd;\n>>    hint: the differences between that commit and this one are:\n>>\n>>    diff --git a/file b/file\n>>    --- a/file\n>>    +++ b/file\n>>    @@ -1 +1 @@\n>>    -modified one\n>>    +one\n>>\n>>    When you have resolved this problem run \"git rebase --continue\".\n>>    If you would prefer to skip this patch, instead run \"git rebase --skip\".\n>>    To restore the original branch and stop rebasing run \"git rebase --abort\".\n> Actually I do not think identifying the ones that can safely skipped is\n> such a big issue. The case I am most concerned about is when you see that\n> \"two reverted back to one\" (which you obviously want to avoid, to keep the\n> effect of the commit the upstream has to have \"two\" on that line), but at\n> the same time when you do not agree with the change that the upstream took\n> for the _current commit_ you are replaying (i.e. you want the final result\n> to have \"one\", not \"modified one\" which the upstream has applied).\n>\n> The conflict resolution to come up with such an incremental change is very\n> painful. You have to avoid the \"s/two/one/\" revert, and you have to keep\n> the \"s/modified one/one\" revert, and you need to know which hunks are\n> conflicting due to what (i.e. the former is because a patch similar to the\n> one you haven't replayed in this rebase session is already in upstream,\n> the latter is the upstream tweaked the current patch you are looking at in\n> a way you do not agree with).\n>\n> I do not have a good idea to solve this in mind yet.\n\nI am not 100% sure that my solution is exactly about this problem, but \nit seems to be quite relevant.\n\nI think that if you rebase \"step-by-step\" by doing, for this particular \nexample, something like\n\n$ git rebase master^ topic\n$ git rebase master topic\n\nYou will first see the /modified one/one/ conflict that you will resolve \nyour \"two\" against and then your second rebase will apply with no conflicts.\n\nI have a set of scripts that help me do this kind of rebases by \nessentially rebasing the topic branch against every single commit on the \nupstream.\n\nThis way I can clearly see every conflict as at appears and can fix it \neven in cases when a rebase against the final state would give an \nabsolutely unbearable diff.\n\nIt definitely is much slower but in my case I find this to be the only \npossible solution.  rerere helps enormously here.\nAt the same time the less changes are in topic...master the faster it \nwould be and the more changes are there the more you benefit from a \ngradual rebase.\n\n\nHere is the actual use case in case I was not very clear above or in \ncase someone is interested.\n\nI have a very longed lived branch that I have to rebase against an \nactively developed master.\nBesides been longed live the branch contains a lot of absolutely \nunrelated changes.\n\nThe branch is a \"next version branch\" and contains a result of a two \nyear work done by two people who though that their version of the \napplication will become master \"tomorrow\", so they where not too shy to \nchange things.\n\nThe upstream is developed by another 6 - 8 people over 3 years and they \nhave no knowledge of the changes done in the \"next version branch\".\n\nHere is were I step in and am told to get the changes from the next \nversion branch onto the master.  And I am not part of either of these \ntwo groups of people.\n\nIn addition to that one of the guys who developed the next version has \nleft the company before I joined and the other one is also gone by now.\n\nWhile it seems pretty crazy to me, thanks to git rebase, git rerere and \nthe \"step-by-step\" rebase I am at my 9th rebase of this topic branch \nthrough last year and had only minor problems so far.\n\nEssentially now we have 6 people developing the application \"in the \nmiddle\" of its history with one person trying to hold the rest of the \nhistory on top.\nI imagine this as a kind of an acrobatic trick worth showing in a circus :)\n\nIlya Bobyr"},{"id":"171122","messageId":"20110712053532.GB11644@sigill.intra.peff.net","threadId":"27788","inReplyTo":"4E1B91D8.5040500@ronin-capital.com","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-12T05:35:32Z","receivedAt":"2011-07-12T05:35:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2011 at 07:14:16PM -0500, Illia Bobyr wrote:\n\n> I am not 100% sure that my solution is exactly about this problem, but \n> it seems to be quite relevant.\n> \n> I think that if you rebase \"step-by-step\" by doing, for this particular \n> example, something like\n> \n> $ git rebase master^ topic\n> $ git rebase master topic\n> \n> You will first see the /modified one/one/ conflict that you will resolve \n> your \"two\" against and then your second rebase will apply with no conflicts.\n> \n> I have a set of scripts that help me do this kind of rebases by \n> essentially rebasing the topic branch against every single commit on the \n> upstream.\n\nThat makes a lot of sense to me as a strategy. Of course, as you\nmention, it is horribly slow. And when you do have real conflicts, you\nwould end up looking at the same conflicts again and again (and as you\nmention, rerere can be some help there, though not necessarily\nperfect).\n\n> At the same time the less changes are in topic...master the faster it \n> would be and the more changes are there the more you benefit from a \n> gradual rebase.\n\nYeah, this seems like the real problem to me. It's one thing to rebase\non top of a single series that somebody has applied upstream. But if it\nhas been 2 weeks, there may be hundreds of commits, and doing hundreds\nof rebases is awful. I wonder if you could do better by picking out some\n\"key\" commits in master to rebase on top of using one of:\n\n  1. Divide-and-conquer the commit space. Try the rebase, starting on\n     the HEAD. If it works, great. If the user says \"this is too hard\",\n     then find the midpoint between where we tried to rebase and the\n     merge base, and try rebasing there. Every time it's too hard, go\n     back halfway to the start. Every time it's easy, try the new result\n     on top of HEAD.\n\n     So it's basically doing a O(lg n) search backwards for an easy\n     place to rebase, and then repeatedly checking if that was a good\n     spot (and repeating the backwards search if not). The worst case\n     complexity is O(n lg n) rebases. But in practice, you can hopefully\n     find the problematic spot in O(lg n), and then everything will just\n     work out after 1 or 2 problematic spots.\n\n  2. Use heuristics (like commit message content) to find related\n     commits. So if I have a 5-patch series, I can perhaps find the\n     likely commits upstream that match my patches, and those are\n     good places to try individual rebases. And then I don't care how\n     many commits are in master. If I have a 5 patch series, I won't do\n     more than 5 rebases.\n\nBut I've never tried this in practice. Maybe next time a rebase is ugly\nI'll manually work through one of the methods and see how it fares.\n\n-Peff\n"},{"id":"171140","messageId":"buovcv8f1kd.fsf@dhlpc061.dev.necel.com","threadId":"27788","inReplyTo":"20110711220107.GC30155@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Miles Bader","fromEmail":"miles@gnu.org","sentAt":"2011-07-12T06:36:02Z","receivedAt":"2011-07-12T06:36:02Z","isPatch":true,"sender":{"key":"miles@gnu.org","avatar":"https://gravatar.com/avatar/01069b69593af7bff28e2f97afeb3644ae6fe2f5f56cb3a8cf34c5fb8c36efe5?d=mp&s=160"},"body":"Jeff King <peff@peff.net> writes:\n>> Sounds like a good thing to aim for, but \"Object Cache\" sounded too much\n>> like giving access to the object data that is faster than either loose or\n>> packed objects.\n>\n> Agreed. I'm open to better suggestions for the name. I would have just\n> called it a straight out \"cache\" as it can be used for caching anything,\n> but that term is already taken in git. :)\n\n\"Info Cache\"?  Even more generic, but avoids the loaded term \"object\"....\n\n-miles\n\n-- \n`Life is a boundless sea of bitterness'\n"},{"id":"171146","messageId":"201107121241.40242.jnareb@gmail.com","threadId":"27788","inReplyTo":"20110711161754.GB10418@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-12T10:41:35Z","receivedAt":"2011-07-12T10:41:35Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Mon, 11 July 2011, Jeff King wrote:\n\n> There is sometimes a need to cache some information about an\n> object or set of objects persistently across git\n> invocations. The notes-cache interface can be used for this,\n> but it is very heavyweight and slow for storing small\n> values.\n> \n> This patch introduces a new API, object-cache, which stores\n> a mapping of objects to values in a concise and efficient\n> form. See the added API documentation for details.\n> \n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> As I mentioned earlier, I wanted this to be generic and size-agnostic,\n> because I'd also like to try caching patch-ids for git-cherry.\n\nCould this API be generalized to support \"reverse cache\", for example\nto map Subversion revision numbers to Git revision identifiers (for \ngit-svn)?\n\n-- \nJakub Narebski\nPoland\n"},{"id":"171168","messageId":"20110712175739.GA17031@sigill.intra.peff.net","threadId":"27788","inReplyTo":"201107121241.40242.jnareb@gmail.com","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-12T17:57:39Z","receivedAt":"2011-07-12T17:57:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 12, 2011 at 12:41:35PM +0200, Jakub Narebski wrote:\n\n> On Mon, 11 July 2011, Jeff King wrote:\n> \n> > There is sometimes a need to cache some information about an\n> > object or set of objects persistently across git\n> > invocations. The notes-cache interface can be used for this,\n> > but it is very heavyweight and slow for storing small\n> > values.\n> > \n> > This patch introduces a new API, object-cache, which stores\n> > a mapping of objects to values in a concise and efficient\n> > form. See the added API documentation for details.\n> > \n> > Signed-off-by: Jeff King <peff@peff.net>\n> > ---\n> > As I mentioned earlier, I wanted this to be generic and size-agnostic,\n> > because I'd also like to try caching patch-ids for git-cherry.\n> \n> Could this API be generalized to support \"reverse cache\", for example\n> to map Subversion revision numbers to Git revision identifiers (for \n> git-svn)?\n\nI hadn't really considered that. It definitely _could_ be done, but I'm\nnot sure if it's a good idea, for two reasons:\n\n  1. The in-memory store is based on decorate.[ch], which actually\n     stores pointers to objects instead of sha1s as keys. Which keeps\n     the hash entries a little smaller, and makes comparisons faster.\n\n     We can only take that shortcut because we know what the keys are\n     (i.e., objects, and the in-memory store gets pointers and the disk\n     store gets sha1s). So I have some fear that a more generalized form\n     may be a little slower.\n\n  2. The disk store uses a binary search over a sorted list of sha1s.\n     Generalizing this to \"a sequence of bytes\" would not be hard. But\n     we currently have the option of using the uniform distribution of\n     sha1 to make better guesses about our \"middle\" (see the comments in\n     sha1-lookup.c). That assumption does not hold over arbitrary bytes.\n\n-Peff\n"},{"id":"171175","messageId":"7v62n78hpk.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"20110712175739.GA17031@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-12T18:41:27Z","receivedAt":"2011-07-12T18:41:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   2. The disk store uses a binary search over a sorted list of sha1s.\n>      Generalizing this to \"a sequence of bytes\" would not be hard. But\n>      we currently have the option of using the uniform distribution of\n>      sha1 to make better guesses about our \"middle\" (see the comments in\n>      sha1-lookup.c). That assumption does not hold over arbitrary bytes.\n\nA side note. I notice that the \"comment\" you refer to appears twice in the\nfile, and the sha1_pos() function that comes earlier in the file does not\nprotect itself from overshoot penalty like the sha1_entry_pos() function\ndoes.\n\nPerhaps we should think about unifying them somehow.\n"},{"id":"171180","messageId":"20110712193844.GA17322@toss.lan","threadId":"27788","inReplyTo":"20110712000304.GA32276@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-12T19:38:44Z","receivedAt":"2011-07-12T19:38:44Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Mon, Jul 11, 2011 at 08:03:04PM -0400, Jeff King wrote:\n> On Mon, Jul 11, 2011 at 04:21:54PM -0700, Junio C Hamano wrote:\n> \n> > Actually I do not think identifying the ones that can safely skipped is\n> > such a big issue. The case I am most concerned about is when you see that\n> > \"two reverted back to one\" (which you obviously want to avoid, to keep the\n> > effect of the commit the upstream has to have \"two\" on that line), but at\n> > the same time when you do not agree with the change that the upstream took\n> > for the _current commit_ you are replaying (i.e. you want the final result\n> > to have \"one\", not \"modified one\" which the upstream has applied).\n> \n> I'm not sure there's a general solution to that. You can't keep the\n> commit you want intact, because you are rebasing and therefore building\n> on top of the other broken commit. So in a history like:\n> \n>     B'--C'\n>    /\n>   A--B--C\n> \n> You really want to perform the transformation of B to B', but on top of\n> C (i.e., \"git checkout C; git diff B' B | git apply\"). But if B and C\n> are textually related, it's going to conflict horribly. And I don't\n> think there is a general solution short of a darcs-style patch algebra.\n\nFWIW, I tried this in darcs and it has exactly the same problem.\n\nIt does have better granularity when detecting changes. For\nexample, it will recognize the changes of B' in B, even if B\ncontains non-conflicting hunks on top of the changes in B'. Git\nonly recognizes identical commits, and this is something where we\ncould improve without too much difficulty (think per-hunk\npatch-ids).\n\nBut if the changes in B and B' have conflicts, then darcs will\npresent the user with the options B' and C, which looks like we\nwere trying to revert C, just like it does with git.\n\nClemens\n"},{"id":"171182","messageId":"20110712194540.GA21180@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110712193844.GA17322@toss.lan","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-12T19:45:40Z","receivedAt":"2011-07-12T19:45:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 12, 2011 at 09:38:44PM +0200, Clemens Buchacher wrote:\n\n> > I'm not sure there's a general solution to that. You can't keep the\n> > commit you want intact, because you are rebasing and therefore building\n> > on top of the other broken commit. So in a history like:\n> > \n> >     B'--C'\n> >    /\n> >   A--B--C\n> > \n> > You really want to perform the transformation of B to B', but on top of\n> > C (i.e., \"git checkout C; git diff B' B | git apply\"). But if B and C\n> > are textually related, it's going to conflict horribly. And I don't\n> > think there is a general solution short of a darcs-style patch algebra.\n> \n> FWIW, I tried this in darcs and it has exactly the same problem.\n\nIt has been a long time since I've looked at darcs, but from my\nrecollection, it will only work with specific patch types. That is, it\nworks if B and C are commutative. For text patches that touch the same\narea, that is not the case. But if \"B\" were a token-renaming patch, for\nexample, I think it might work.\n\nAnyway, that is not really relevant to git. I think we decided long ago\nthat being simple and stupid about the content changes (i.e., blob A\nbecame blob B) is better in general, even when there are a few corner\ncases that might have been better off the other way.\n\n> It does have better granularity when detecting changes. For\n> example, it will recognize the changes of B' in B, even if B\n> contains non-conflicting hunks on top of the changes in B'. Git\n> only recognizes identical commits, and this is something where we\n> could improve without too much difficulty (think per-hunk\n> patch-ids).\n\nI'd be curious to see an example worked out. In my experience, even if\nsomething like patch-ids don't match, it's not a big deal for the hunks\nthat do match, because when we get to the actual content merge, we will\nrealize that both sides made the same change to that hunk.  So it's not\nlike you are getting unrelated conflicts; whatever small part of the\ndiff made the patch-id different will be the part where you get the\nconflict, and the should merge cleanly.\n\nHaving said something so general, I'm sure there is probably some corner\ncase that proves me wrong.\n\n-Peff\n"},{"id":"171189","messageId":"20110712210716.GB17322@toss.lan","threadId":"27788","inReplyTo":"20110712194540.GA21180@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-12T21:07:16Z","receivedAt":"2011-07-12T21:07:16Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Tue, Jul 12, 2011 at 03:45:40PM -0400, Jeff King wrote:\n>\n> It has been a long time since I've looked at darcs, but from my\n> recollection, it will only work with specific patch types. That is, it\n> works if B and C are commutative. For text patches that touch the same\n> area, that is not the case. But if \"B\" were a token-renaming patch, for\n> example, I think it might work.\n\nIf they were commutative, we would not have a problem in git\neither.\n\n> Anyway, that is not really relevant to git. I think we decided long ago\n> that being simple and stupid about the content changes (i.e., blob A\n> became blob B) is better in general, even when there are a few corner\n> cases that might have been better off the other way.\n\nYes, but that only applies to git merge. When we talk about\nrebasing we are looking at individual patches rather than a single\nglobal merge. For rebase I think \"patch algebra\" is very relevant,\nand we have already implemented a simple patch algebra with\npatch-id's.\n\n> > It does have better granularity when detecting changes. For\n> > example, it will recognize the changes of B' in B, even if B\n> > contains non-conflicting hunks on top of the changes in B'. Git\n> > only recognizes identical commits, and this is something where we\n> > could improve without too much difficulty (think per-hunk\n> > patch-ids).\n> \n> I'd be curious to see an example worked out. In my experience, even if\n> something like patch-ids don't match, it's not a big deal for the hunks\n> that do match, because when we get to the actual content merge, we will\n> realize that both sides made the same change to that hunk.  So it's not\n> like you are getting unrelated conflicts; whatever small part of the\n> diff made the patch-id different will be the part where you get the\n> conflict, and the should merge cleanly.\n\nI am reading that last part as \"they should not merge cleanly\". And\nin general I agree. We have to resolve the conflict manually and\nit's just a question of how the conflict is presented and resolved.\nThis is already being discussed some in a different branch of this\nthread.\n\n> Having said something so general, I'm sure there is probably some corner\n> case that proves me wrong.\n\nExactly. The case I am talking about is where the patch-id's are\ndifferent but there are no conflicts. I have worked out an example\nfor git and darcs. Below are two scripts to demonstrate. In the\nexample, the patch-id is different because upstream changes the\npatch in a way that does not conflict with the original patch. It\nsimply adds another change that goes into a different hunk. Git\nfails to merge cleanly because the patch-id's are different. It\npresents the user with an awkward conflict that looks like a\nrevert. Darcs, on the other hand, merges cleanly. It recognizes the\nfact that all changes from the original patch are contained\nupstream and do not conflict with the upstream version. The fact\nthat more changes are added on top does not bother darcs.\n\nNow, one might argue that this is a corner case. But it's actually\nvery common. In the example, the patch-id changes because of an\nextra change in a different text area. That is indeed unlikely.\nHowever, the same problem will occur in a much more common case.\nLet's say we have a patch with 10 hunks. The patch is applied\nupstream, with only one difference in one of the hunks.\nSubsequently, text areas affected by any of the other hunks change\nupstream. When the original patch is rebased on top of that, it\nwill conflict with the one hunk that was changed in the upstream\nversion of that patch. And that's ok. Git should not decide which\nversion is correct. But in addition to that conflict there will\nalso be conflicts for all the other hunks, which the upstream patch\ndid _not_ modify. And all of those conflicts will look like\nreverts.\n\nI believe that is the main reason why rebase is so painful all the\ntime.\n\nBut I am not saying that we necessarily need a finer granularity of\npatch-id's. If we rebase the patch on top of its upstream version\nbefore rebasing it to the upstream head, as was already suggested\nelsewhere, the problem described here will also go away on its own.\n\nClemens\n\n---\n\n#!/bin/sh\n#\n# Darcs recognizes matching upstream changes\n#\n\ntestdir=test-darcs\n\nmkdir \"$testdir\" || exit 1\n\n(\n\tcd \"$testdir\"\n\tmkdir master\n\tcd master\n\tdarcs init\n\n\tfor line in $(seq 20)\n\tdo\n\t\techo $line >>file\n\tdone\n\n\tdarcs add file\n\tdarcs record -a -m initial\n\n\tcd ..\n\tdarcs get master side\n\tcd side\n\tsed -i '5 s/^.*$/original change/' file\n\tdarcs record -a -m 'original change'\n\n\tcd ../master\n\tsed -i '5 s/.*/original change/' file\n\tsed -i '15 s/^.*$/with an extra hunk/' file\n\tdarcs record -a -m 'original change'\n\n\tsed -i '5 s/.*/modified change/' file\n\tdarcs record -a -m 'modified change'\n\n\tdarcs pull -a ../side\n)\n\n#!/bin/sh\n#\n# Git does not recognize matching upstream changes\n#\n\ntestdir=test-darcs\n\nmkdir \"$testdir\" || exit 1\n\n(\n\tcd \"$testdir\"\n\tmkdir master\n\tcd master\n\tdarcs init\n\n\tfor line in $(seq 20)\n\tdo\n\t\techo $line >>file\n\tdone\n\n\tdarcs add file\n\tdarcs record -a -m initial\n\n\tcd ..\n\tdarcs get master side\n\tcd side\n\tsed -i '5 s/^.*$/original change/' file\n\tdarcs record -a -m 'original change'\n\n\tcd ../master\n\tsed -i '5 s/.*/original change/' file\n\tsed -i '15 s/^.*$/with an extra hunk/' file\n\tdarcs record -a -m 'original change'\n\n\tsed -i '5 s/.*/modified change/' file\n\tdarcs record -a -m 'modified change'\n\n\tdarcs pull -a ../side\n)\n"},{"id":"171190","messageId":"20110712211537.GA3220@toss.lan","threadId":"27788","inReplyTo":"20110712210716.GB17322@toss.lan","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-12T21:15:37Z","receivedAt":"2011-07-12T21:15:37Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Tue, Jul 12, 2011 at 11:07:16PM +0200, Clemens Buchacher wrote:\n> \n> Exactly. The case I am talking about is where the patch-id's are\n> different but there are no conflicts. I have worked out an example\n> for git and darcs. Below are two scripts to demonstrate.\n\nOops, that was the same script twice. Here are the darcs and git\nversions, respectively:\n\n#!/bin/sh\n#\n# Darcs recognizes matching upstream changes\n#\n\ntestdir=test-darcs\n\nmkdir \"$testdir\" || exit 1\n\n(\n\tcd \"$testdir\"\n\tmkdir master\n\tcd master\n\tdarcs init\n\n\tfor line in $(seq 20)\n\tdo\n\t\techo $line >>file\n\tdone\n\n\tdarcs add file\n\tdarcs record -a -m initial\n\n\tcd ..\n\tdarcs get master side\n\tcd side\n\tsed -i '5 s/^.*$/original change/' file\n\tdarcs record -a -m 'original change'\n\n\tcd ../master\n\tsed -i '5 s/.*/original change/' file\n\tsed -i '15 s/^.*$/with an extra hunk/' file\n\tdarcs record -a -m 'original change'\n\n\tsed -i '5 s/.*/modified change/' file\n\tdarcs record -a -m 'modified change'\n\n\tdarcs pull -a ../side\n)\n\n\n#!/bin/sh\n#\n# Git does not recognize matching upstream changes\n#\n\ntestdir=test-git\n\nmkdir \"$testdir\" || exit 1\n\n(\n\tcd \"$testdir\"\n\tgit init -q\n\n\tfor line in $(seq 20)\n\tdo\n\t\techo $line >>file\n\tdone\n\n\tgit add file\n\tgit commit -q -m initial\n\n\tgit checkout -q -b side\n\tsed -i '5 s/^.*$/original change/' file\n\tgit add file\n\tgit commit -q -m 'original change'\n\n\tgit checkout -q master\n\tsed -i '5 s/.*/original change/' file\n\tsed -i '15 s/^.*$/with an extra hunk/' file\n\tgit add file\n\tgit commit -q -m 'original change'\n\n\tsed -i '5 s/.*/modified change/' file\n\tgit add file\n\tgit commit -q -m 'modified change'\n\n\tgit rebase master side\n\tgit diff\n)\n"},{"id":"171193","messageId":"20110712213607.GA12447@sigill.intra.peff.net","threadId":"27788","inReplyTo":"20110712210716.GB17322@toss.lan","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-12T21:36:07Z","receivedAt":"2011-07-12T21:36:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 12, 2011 at 11:07:16PM +0200, Clemens Buchacher wrote:\n\n> On Tue, Jul 12, 2011 at 03:45:40PM -0400, Jeff King wrote:\n> >\n> > It has been a long time since I've looked at darcs, but from my\n> > recollection, it will only work with specific patch types. That is, it\n> > works if B and C are commutative. For text patches that touch the same\n> > area, that is not the case. But if \"B\" were a token-renaming patch, for\n> > example, I think it might work.\n> \n> If they were commutative, we would not have a problem in git\n> either.\n\nExcept that git doesn't support many commutative special forms, like\ntoken-renaming patches.\n\n> > Anyway, that is not really relevant to git. I think we decided long ago\n> > that being simple and stupid about the content changes (i.e., blob A\n> > became blob B) is better in general, even when there are a few corner\n> > cases that might have been better off the other way.\n> \n> Yes, but that only applies to git merge. When we talk about\n> rebasing we are looking at individual patches rather than a single\n> global merge. For rebase I think \"patch algebra\" is very relevant,\n> and we have already implemented a simple patch algebra with\n> patch-id's.\n\nI can buy that argument, but I think most of the benefit in darcs comes\nfrom annotating your patch as \"this is just renaming 'foo' to 'bar'\" and\nother special patch types. Because the algebraic properties of those\ntypes is more interesting. And what we really don't want in git is\nhaving to put the burden on users of making those annotations (not just\nbecause it's annoying to do, but because when the annotation doesn't\nmatch what's in the blobs, the results would be extremely confusing).\n\nBut if you are proposing that we could do run-time detection on those\nsorts of patch properties and use the result in making a better rebase,\nI don't think that's a bad idea (though I do wonder if the amount of\ncode will be worth it).\n\nAgain, it has been a long time since I've looked at darcs, and I was\nnever a serious user of it, so everything I say above may be utterly\nwrong.\n\n> > I'd be curious to see an example worked out. In my experience, even if\n> > something like patch-ids don't match, it's not a big deal for the hunks\n> > that do match, because when we get to the actual content merge, we will\n> > realize that both sides made the same change to that hunk.  So it's not\n> > like you are getting unrelated conflicts; whatever small part of the\n> > diff made the patch-id different will be the part where you get the\n> > conflict, and the should merge cleanly.\n> \n> I am reading that last part as \"they should not merge cleanly\".\n\nSorry, it was supposed to be \"...and the rest should merge cleanly\". But\nI think you got my meaning.\n\n> Exactly. The case I am talking about is where the patch-id's are\n> different but there are no conflicts. I have worked out an example\n> for git and darcs. Below are two scripts to demonstrate. In the\n> example, the patch-id is different because upstream changes the\n> patch in a way that does not conflict with the original patch. It\n> simply adds another change that goes into a different hunk. Git\n> fails to merge cleanly because the patch-id's are different. It\n> presents the user with an awkward conflict that looks like a\n> revert. Darcs, on the other hand, merges cleanly. It recognizes the\n> fact that all changes from the original patch are contained\n> upstream and do not conflict with the upstream version. The fact\n> that more changes are added on top does not bother darcs.\n\nAh, OK, I see. Let me try to amend what I said earlier to make sure.\n\nIn the normal case of applying patch B on top of patch A, it doesn't\nmatter if we use per-hunk patch-ids or normal patch-ids. Because even if\nwe decide to actually go through with the merge of B on top of A, any\nhunks that _would have_ had their per-hunk patch-ids match will merge\ncleanly.\n\nBut in the real world, it is about applying patch Z on top of patches\nA..Y, where Z has similar hunks to patch N. And then it _does_ make a\ndifference, because it is about skipping hunks from Z that are already\nin N, but will end up applied on top of Y. And what's in Y and what's in\nN may be quite different.\n\nDoes that sound right?\n\n> Now, one might argue that this is a corner case. But it's actually\n> very common. In the example, the patch-id changes because of an\n> extra change in a different text area. That is indeed unlikely.\n> However, the same problem will occur in a much more common case.\n> Let's say we have a patch with 10 hunks. The patch is applied\n> upstream, with only one difference in one of the hunks.\n> Subsequently, text areas affected by any of the other hunks change\n> upstream. When the original patch is rebased on top of that, it\n> will conflict with the one hunk that was changed in the upstream\n> version of that patch. And that's ok. Git should not decide which\n> version is correct. But in addition to that conflict there will\n> also be conflicts for all the other hunks, which the upstream patch\n> did _not_ modify. And all of those conflicts will look like\n> reverts.\n\nRight, that makes sense to me now.\n\n-Peff\n"},{"id":"171194","messageId":"4E1CC237.3050401@ronin-capital.com","threadId":"27788","inReplyTo":"20110712053532.GB11644@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Illia Bobyr","fromEmail":"illia.bobyr@ronin-capital.com","sentAt":"2011-07-12T21:52:55Z","receivedAt":"2011-07-12T21:52:55Z","isPatch":true,"sender":{"key":"illia.bobyr@ronin-capital.com","avatar":null},"body":"On 7/12/2011 12:35 AM, Jeff King wrote:\n> On Mon, Jul 11, 2011 at 07:14:16PM -0500, Illia Bobyr wrote:\n>\n>> I am not 100% sure that my solution is exactly about this problem, but\n>> it seems to be quite relevant.\n>>\n>> I think that if you rebase \"step-by-step\" by doing, for this particular\n>> example, something like\n>>\n>> $ git rebase master^ topic\n>> $ git rebase master topic\n>>\n>> You will first see the /modified one/one/ conflict that you will resolve\n>> your \"two\" against and then your second rebase will apply with no conflicts.\n>>\n>> I have a set of scripts that help me do this kind of rebases by\n>> essentially rebasing the topic branch against every single commit on the\n>> upstream.\n> That makes a lot of sense to me as a strategy. Of course, as you\n> mention, it is horribly slow. And when you do have real conflicts, you\n> would end up looking at the same conflicts again and again (and as you\n> mention, rerere can be some help there, though not necessarily\n> perfect).\n\nWell, I would like to comment on \"horribly slow\" a little bit :)\nIt is slower than a normal rebase, but it is much faster than, at least \nin my case, me doing the conflict resolution on the final versions \nwithout intermediate steps.\n\nAlso, in my case, it is faster than compiling every single commit of the \ntopic branch after the rebase.  Something that I just have to do, again, \nbecause if I do this only with the final version it gives me so much \nerrors all over the code, that I can hardly do anything with it.  \nBesides I would like the commits that were \"incorrectly\" merged and that \nintroduced the compilation error to contain the fixes, not have all the \nfixes as a final \"merge\" commit.\n\nIn other words, while been slow, it is just one step in a general \nprocess that, in my case, have steps that are slower.\n\nAlso, my guess is that, as rebase is an sh script it may be made faster \nand a step-by-step rebase will became considerably faster as well, if it \nwould be rewritten in C.  Though I have not looked a lot inside the \nscript, so I might be wrong.\n\nI would like to note that in case of hundreds of rebases with dozens of \nconflicts rerere's help is hard to overestimate.  I have rebased my \ntopic branch through at least 500 commits for the last 6 month and as I \nactually do not copy any changes into the master branch, some conflicts \nstay we me for the whole time.\n\n>> At the same time the less changes are in topic...master the faster it\n>> would be and the more changes are there the more you benefit from a\n>> gradual rebase.\n> Yeah, this seems like the real problem to me. It's one thing to rebase\n> on top of a single series that somebody has applied upstream. But if it\n> has been 2 weeks, there may be hundreds of commits, and doing hundreds\n> of rebases is awful. I wonder if you could do better by picking out some\n> \"key\" commits in master to rebase on top of using one of:\n>\n>    1. Divide-and-conquer the commit space. Try the rebase, starting on\n>       the HEAD. If it works, great. If the user says \"this is too hard\",\n>       then find the midpoint between where we tried to rebase and the\n>       merge base, and try rebasing there. Every time it's too hard, go\n>       back halfway to the start. Every time it's easy, try the new result\n>       on top of HEAD.\n>\n>       So it's basically doing a O(lg n) search backwards for an easy\n>       place to rebase, and then repeatedly checking if that was a good\n>       spot (and repeating the backwards search if not). The worst case\n>       complexity is O(n lg n) rebases. But in practice, you can hopefully\n>       find the problematic spot in O(lg n), and then everything will just\n>       work out after 1 or 2 problematic spots.\n\nI have problems all over the upstream history :)\nAnd the issue is not in exactly in finding a problem spot.  It is about \ngiving the user (that is me in this case) something that he can merge in \na reasonable amount of time.\n\nI have a topic branch with 174 commits.  It takes my machine about 7 \nminutes to rebase it.\nIf I have a conflict that I do not understand, it may take me, on \naverage, two hours to figure out what a conflict is about and fix it.  \nSometimes it may take 4 hours or even more if I have to involve other \ndevelopers.\nIf my machine will have to do 20 rebases or even 40 and it will present \nme with simple conflicts that I can solve in seconds it would still be \nbetter than if I will spend hours trying to figure out something and \ngive up by saying \"this is too hard\".  Note that while it rebases I am \nworking on something else.\n\nIn my case sometimes even the most basic conflicts that arise because of \na rebase against just one commit may be hard to merge.\nIf I can avoid even one of these I will be happy to let one of my \nmachine cores run for hours :)\n\nObviously, my case is a wired case caused by not-the-best development \npractices.  But, I guess, one can still consider it as one of the points \non the curve that approximate this kind of use cases.  A pretty extreme \npoint.\n\n>    2. Use heuristics (like commit message content) to find related\n>       commits. So if I have a 5-patch series, I can perhaps find the\n>       likely commits upstream that match my patches, and those are\n>       good places to try individual rebases. And then I don't care how\n>       many commits are in master. If I have a 5 patch series, I won't do\n>       more than 5 rebases.\n>\n> But I've never tried this in practice. Maybe next time a rebase is ugly\n> I'll manually work through one of the methods and see how it fares.\n\nI guess that I view this problem from a little different angle, as in my \ncase, it is not be exactly my own patches that are causing problems, but \nan upstream changes that have other changes base on them.\n\nNow I am guessing, but here is another idea.\n\nI think that one can check the modification history of the lines in the \nmaster commits we are rebasing against and in all the topic commits, \nsimilar to what blame does.\nEssentially take a set of all lines that were modified by the topic \nbranch (along with the context lines) and sets of lines modified by ever \nsingle commit (without the context lines).\nIf a commit does not touch lines from the topic branch set it will not \ncause conflicts and we can skip it.  It will just cause offsets in the \nline numbers when the patches will be applied.\n\nIf you are rebasing against a lot of changes that are unrelated to your \ntopic branch and if they are split into commits correctly, this way, I \nguess, it would be possible to find those that may cause conflicts.\nThe actual rebase may still be able to go through some of them without \nconflicts but I see this as a first approximation that might save time.  \nAnd it seems to give only false negatives.\n\nKind of a conflict prediction approximation.\n\nIlya"},{"id":"171199","messageId":"CAEBDL5WYn7v7kZiR8p5GD4r5sMPxMUibcmhMHBjvdZ4n6mSPag@mail.gmail.com","threadId":"27788","inReplyTo":"20110712210716.GB17322@toss.lan","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"John Szakmeister","fromEmail":"john@szakmeister.net","sentAt":"2011-07-13T01:33:57Z","receivedAt":"2011-07-13T01:33:57Z","isPatch":true,"sender":{"key":"john@szakmeister.net","avatar":"https://avatars.githubusercontent.com/u/448087?v=4"},"body":"On Tue, Jul 12, 2011 at 5:07 PM, Clemens Buchacher <drizzd@aon.at> wrote:\n[snip]\n> Now, one might argue that this is a corner case. But it's actually\n> very common. In the example, the patch-id changes because of an\n> extra change in a different text area. That is indeed unlikely.\n> However, the same problem will occur in a much more common case.\n> Let's say we have a patch with 10 hunks. The patch is applied\n> upstream, with only one difference in one of the hunks.\n> Subsequently, text areas affected by any of the other hunks change\n> upstream. When the original patch is rebased on top of that, it\n> will conflict with the one hunk that was changed in the upstream\n> version of that patch. And that's ok. Git should not decide which\n> version is correct. But in addition to that conflict there will\n> also be conflicts for all the other hunks, which the upstream patch\n> did _not_ modify. And all of those conflicts will look like\n> reverts.\n>\n> I believe that is the main reason why rebase is so painful all the\n> time.\n\nClemens, that's a great description of the problem.  I've run into\nthis several times, and it is really confusing.  I've spent\nconsiderable time tracking down the real conflict... only to find the\nreal issue was in something non-related and easily resolved.  IMHO, I\nagree with you Clemens: this has been my major source of pain.\n\n-John\n"},{"id":"171203","messageId":"20110713063701.GA18238@sigill.intra.peff.net","threadId":"27788","inReplyTo":"7v62n78hpk.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-13T06:37:01Z","receivedAt":"2011-07-13T06:37:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 12, 2011 at 11:41:27AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> >   2. The disk store uses a binary search over a sorted list of sha1s.\n> >      Generalizing this to \"a sequence of bytes\" would not be hard. But\n> >      we currently have the option of using the uniform distribution of\n> >      sha1 to make better guesses about our \"middle\" (see the comments in\n> >      sha1-lookup.c). That assumption does not hold over arbitrary bytes.\n> \n> A side note. I notice that the \"comment\" you refer to appears twice in the\n> file, and the sha1_pos() function that comes earlier in the file does not\n> protect itself from overshoot penalty like the sha1_entry_pos() function\n> does.\n> \n> Perhaps we should think about unifying them somehow.\n\nIt would be easy to implement sha1_entry_pos in terms of sha1_pos by\nwriting an access function. But it seems unnecessarily slow to add\nfunction call overhead in what should be a fairly tight loop.\n\nOTOH, we do it everywhere else that we call sha1_pos; either it isn't a\nbig deal, or nobody has bothered to measure and micro-optimize there\nyet.\n\n-Peff\n"},{"id":"171273","messageId":"7vmxgi6pg3.fsf@alter.siamese.dyndns.org","threadId":"27788","inReplyTo":"20110713063701.GA18238@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-13T17:49:32Z","receivedAt":"2011-07-13T17:49:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> It would be easy to implement sha1_entry_pos in terms of sha1_pos by\n> writing an access function. But it seems unnecessarily slow to add\n> function call overhead in what should be a fairly tight loop.\n\nYeah, that could also be a double-regression as sha1_pos() implementation\nis sloppier and does not protect itself from its guess overshooting the\ntarget like sha1_entry_pos() does. The first step definitely is to remove\nthe duplicated comment, and the second step would probably be to unify the\n\"mi\" selection logic in sha1_pos() and sha1_entry_pos().\n\nEither the simplicity of the former is sufficient for the users of the\nlatter, or the users of the former would also benefit from the less\nagressive selection of the latter.\n"},{"id":"171310","messageId":"20110714080453.GA6690@toss.lan","threadId":"27788","inReplyTo":"20110712213607.GA12447@sigill.intra.peff.net","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-14T08:04:53Z","receivedAt":"2011-07-14T08:04:53Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Tue, Jul 12, 2011 at 05:36:07PM -0400, Jeff King wrote:\n> \n> In the normal case of applying patch B on top of patch A, it doesn't\n> matter if we use per-hunk patch-ids or normal patch-ids. Because even if\n> we decide to actually go through with the merge of B on top of A, any\n> hunks that _would have_ had their per-hunk patch-ids match will merge\n> cleanly.\n> \n> But in the real world, it is about applying patch Z on top of patches\n> A..Y, where Z has similar hunks to patch N. And then it _does_ make a\n> difference, because it is about skipping hunks from Z that are already\n> in N, but will end up applied on top of Y. And what's in Y and what's in\n> N may be quite different.\n> \n> Does that sound right?\n\nYes, exactly.\n\nAnd one possible solution would be to drop all hunks from Z which\nare already somewhere in A..Y. But that undermines the whole\nchangeset idea.\n\nIf we detect the similarities between Z and N, then we could rebase\nZ to N, make the user resolve any conflicts, which should make more\nsense than what we would have between Z and Y. Then we have Z' on\ntop of N:\n\n  Z      Z'     Z\"\n /      /      /\nA--..--N--..--Y\n\nSubsequently we rebase Z' to Y, at which point only changes remain\nthat we disagreed with. For those we may have to do conflict\nresolution again. So, in some cases this approach could result in\nmore work.\n\nClemens\n"},{"id":"171339","messageId":"4E1F18A3.5070605@ronin-capital.com","threadId":"27788","inReplyTo":"20110714080453.GA6690@toss.lan","subject":"Re: [PATCH 2/5] add object-cache infrastructure","fromName":"Illia Bobyr","fromEmail":"illia.bobyr@ronin-capital.com","sentAt":"2011-07-14T16:26:11Z","receivedAt":"2011-07-14T16:26:11Z","isPatch":true,"sender":{"key":"illia.bobyr@ronin-capital.com","avatar":null},"body":"On 7/14/2011 3:04 AM, Clemens Buchacher wrote:\n> On Tue, Jul 12, 2011 at 05:36:07PM -0400, Jeff King wrote:\n>> In the normal case of applying patch B on top of patch A, it doesn't\n>> matter if we use per-hunk patch-ids or normal patch-ids. Because even if\n>> we decide to actually go through with the merge of B on top of A, any\n>> hunks that _would have_ had their per-hunk patch-ids match will merge\n>> cleanly.\n>>\n>> But in the real world, it is about applying patch Z on top of patches\n>> A..Y, where Z has similar hunks to patch N. And then it _does_ make a\n>> difference, because it is about skipping hunks from Z that are already\n>> in N, but will end up applied on top of Y. And what's in Y and what's in\n>> N may be quite different.\n>>\n>> Does that sound right?\n> Yes, exactly.\n>\n> And one possible solution would be to drop all hunks from Z which\n> are already somewhere in A..Y. But that undermines the whole\n> changeset idea.\n>\n> If we detect the similarities between Z and N, then we could rebase\n> Z to N, make the user resolve any conflicts, which should make more\n> sense than what we would have between Z and Y. Then we have Z' on\n> top of N:\n>\n>    Z      Z'     Z\"\n>   /      /      /\n> A--..--N--..--Y\n>\n> Subsequently we rebase Z' to Y, at which point only changes remain\n> that we disagreed with. For those we may have to do conflict\n> resolution again. So, in some cases this approach could result in\n> more work.\n\nThis is where rerere helps, AFAIU.\nAnd if the conflict is non-trivial there is a chance that it is really \nsomething you would like to take a look at."}]}