{"thread":{"id":"43906","subject":"[PATCH 0/7] tweaking the delta base cache","startedAt":"2016-08-22T21:57:44Z","lastAt":"2016-08-24T18:01:17Z","messageCount":17,"participants":["Jeff King","Eric Wong","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"299867","messageId":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","threadId":"43906","inReplyTo":null,"subject":"[PATCH 0/7] tweaking the delta base cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:57:26Z","receivedAt":"2016-08-22T21:57:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"After the experiments I did with --depth=50 recently, I noticed there\nseemed to be a lot of room for improvement in the delta-base-cache (and\nin particular, there seemed to be a lack of actual numbers).\n\nSo I tried a series of experiments, and these are the tweaks I came up\nwith. There are a lot of numbers and analysis in the commit messages\nthemselves. The most dramatic effect I got was that before this patch,\nbumping core.deltaBaseCacheLimit for the kernel gets you basically\nnothing, whereas with it, I get:\n\n  core.deltaBaseCacheLimit    time to run git log -Sfoo --raw\n  ------------------------    -------------------------------\n                      128m    4m56.486s\n                      256m    4m33.769s\n                      512m    4m12.968s\n                     1024m    3m32.623s\n\nNote that I don't actually propose bumping the memory limit in this\nseries. That's a bit more contentious, as it's really using more\nresources to do a space/time tradeoff, and people may not want to spend\nthe RAM. Whereas this series just adjusts the actual data structures to\nlet us use the RAM we've already been allocated more efficiently.\n\nThe interesting changes are really patches 5 and 6, which adjust the LRU\nmanagement and the underlying hash structure.\n\nThere are a few ideas I thought of or saw in past threads but didn't\nexplore. I don't plan on digging further on them right now, so if\nanybody else wants to do so, be my guest:\n\n  - limiting the size of items entering the cache (e.g., to avoid a\n    single giant blob blowing out all of the other entries)\n\n  - something more clever than LRU, like weighting by a mix of size and\n    recency\n\n  - I didn't look at the criteria for adding entries to the cache at all\n\n  - we seem to drop cache entries as we use them in unpack_entry(); I'm\n    not sure if we would do better to retain them and let them leave via\n    LRU expiration\n\nSo there may be more work, but I think these improvements stand on their\nown.\n\n  [1/7]: cache_or_unpack_entry: drop keep_cache parameter\n  [2/7]: clear_delta_base_cache_entry: use a more descriptive name\n  [3/7]: release_delta_base_cache: reuse existing detach function\n  [4/7]: delta_base_cache: use list.h for LRU\n  [5/7]: delta_base_cache: drop special treatment of blobs\n  [6/7]: delta_base_cache: use hashmap.h\n  [7/7]: t/perf: add basic perf tests for delta base cache\n\n-Peff\n"},{"id":"299868","messageId":"20160822215744.nc3yqv64gf3hwcv4@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 1/7] cache_or_unpack_entry: drop keep_cache parameter","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:57:45Z","receivedAt":"2016-08-22T21:57:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There is only one caller of cache_or_unpack_entry() and it\nalways passes 1 for the keep_cache parameter. We can\nsimplify it by dropping the \"!keep_cache\" case.\n\nAnother call, which did pass 0, was dropped in abe601b\n(sha1_file: remove recursion in unpack_entry, 2013-03-27),\nas unpack_entry() now does more complicated things than a\nsimple unpack when there is a cache miss.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 13 +++----------\n 1 file changed, 3 insertions(+), 10 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 3045aea..2333911 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2129,25 +2129,18 @@ static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n }\n \n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n-\tunsigned long *base_size, enum object_type *type, int keep_cache)\n+\tunsigned long *base_size, enum object_type *type)\n {\n \tstruct delta_base_cache_entry *ent;\n-\tvoid *ret;\n \n \tent = get_delta_base_cache_entry(p, base_offset);\n \n \tif (!eq_delta_base_cache_entry(ent, p, base_offset))\n \t\treturn unpack_entry(p, base_offset, type, base_size);\n \n-\tret = ent->data;\n-\n-\tif (!keep_cache)\n-\t\tclear_delta_base_cache_entry(ent);\n-\telse\n-\t\tret = xmemdupz(ent->data, ent->size);\n \t*type = ent->type;\n \t*base_size = ent->size;\n-\treturn ret;\n+\treturn xmemdupz(ent->data, ent->size);\n }\n \n static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n@@ -2755,7 +2748,7 @@ static void *read_packed_sha1(const unsigned char *sha1,\n \n \tif (!find_pack_entry(sha1, &e))\n \t\treturn NULL;\n-\tdata = cache_or_unpack_entry(e.p, e.offset, size, type, 1);\n+\tdata = cache_or_unpack_entry(e.p, e.offset, size, type);\n \tif (!data) {\n \t\t/*\n \t\t * We're probably in deep shit, but let's try to fetch\n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299869","messageId":"20160822215753.xy7hlho7niex3wpm@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 2/7] clear_delta_base_cache_entry: use a more descriptive name","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:57:53Z","receivedAt":"2016-08-22T21:58:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The delta base cache entries are stored in a fixed-length\nhash table. So the way to remove an entry is to \"clear\" the\nslot in the table, and that is what this function does.\n\nHowever, the name is a leaky abstraction. If we were to\nchange the hash table implementation, it would no longer be\nabout \"clearing\". We should name it after _what_ it does,\nnot _how_ it does it. I.e., something like \"remove\" instead\nof \"clear\".\n\nBut that does not tell the whole story, either. The subtle\nthing about this function is that it removes the entry, but\ndoes not free the entry data. So a more descriptive name is\n\"detach\"; we give ownership of the data buffer to the\ncaller, and remove any other resources.\n\nThis patch uses the name detach_delta_base_cache_entry().\nWe could further model this after functions like\nstrbuf_detach(), which pass back all of the detached\ninformation. However, since there are so many bits of\ninformation in the struct (the data, the size, the type),\nand so few callers (only one), it's not worth that\nawkwardness. The name change and a comment can make the\nintent clear.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 2333911..1d0810c 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2120,7 +2120,12 @@ static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n \treturn eq_delta_base_cache_entry(ent, p, base_offset);\n }\n \n-static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n+/*\n+ * Remove the entry from the cache, but do _not_ free the associated\n+ * entry data. The caller takes ownership of the \"data\" buffer, and\n+ * should copy out any fields it wants before detaching.\n+ */\n+static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n {\n \tent->data = NULL;\n \tent->lru.next->prev = ent->lru.prev;\n@@ -2243,7 +2248,7 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\t\ttype = ent->type;\n \t\t\tdata = ent->data;\n \t\t\tsize = ent->size;\n-\t\t\tclear_delta_base_cache_entry(ent);\n+\t\t\tdetach_delta_base_cache_entry(ent);\n \t\t\tbase_from_cache = 1;\n \t\t\tbreak;\n \t\t}\n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299870","messageId":"20160822215758.uamavr7koin3ze6c@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 3/7] release_delta_base_cache: reuse existing detach function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:57:58Z","receivedAt":"2016-08-22T21:58:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This function drops an entry entirely from the cache,\nmeaning that aside from the freeing of the buffer, it is\nexactly equivalent to detach_delta_base_cache_entry(). Let's\nbuild on top of the detach function, which shortens the code\nand will make it simpler when we change out the underlying\nstorage in future patches.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1d0810c..8264b39 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2152,10 +2152,7 @@ static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n {\n \tif (ent->data) {\n \t\tfree(ent->data);\n-\t\tent->data = NULL;\n-\t\tent->lru.next->prev = ent->lru.prev;\n-\t\tent->lru.prev->next = ent->lru.next;\n-\t\tdelta_base_cached -= ent->size;\n+\t\tdetach_delta_base_cache_entry(ent);\n \t}\n }\n \n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299871","messageId":"20160822215942.nm2jcrkyib7acr4u@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 4/7] delta_base_cache: use list.h for LRU","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:59:42Z","receivedAt":"2016-08-22T22:00:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We keep an LRU list of entries for when we need to drop\nsomething from an over-full cache. The list is implemented\nas a circular doubly-linked list, which is exactly what\nlist.h provides. We can save a few lines by using the list.h\nmacros and functions. More importantly, this makes the code\neasier to follow, as the reader sees explicit concepts like\n\"list_add_tail()\" instead of pointer manipulation.\n\nAs a bonus, the list_entry() macro lets us place the lru\npointers anywhere inside the delta_base_cache_entry struct\n(as opposed to just casting the pointer, which requires it\nat the front of the struct). This will be useful in later\npatches when we need to place other items at the front of\nthe struct (e.g., our hashmap implementation requires this).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI think the result is much nicer, but I found list_entry() a little\ndisappointing, because we lack typeof(). So you are stuck writing:\n\n  struct delta_base_cache_entry *f =\n    list_entry(p, struct delta_base_cache_entry, lru);\n\nI waffled on adding something like:\n\n  LIST_ITEM(struct delta_bas_cache_entry, f, p, lru);\n\nto declare \"f\" as above. But it's getting rather magical and un-C-like.\n\n sha1_file.c | 38 ++++++++++++++++----------------------\n 1 file changed, 16 insertions(+), 22 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 8264b39..c02e785 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -24,6 +24,7 @@\n #include \"streaming.h\"\n #include \"dir.h\"\n #include \"mru.h\"\n+#include \"list.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -2077,13 +2078,10 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \n static size_t delta_base_cached;\n \n-static struct delta_base_cache_lru_list {\n-\tstruct delta_base_cache_lru_list *prev;\n-\tstruct delta_base_cache_lru_list *next;\n-} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };\n+static LIST_HEAD(delta_base_cache_lru);\n \n static struct delta_base_cache_entry {\n-\tstruct delta_base_cache_lru_list lru;\n+\tstruct list_head lru;\n \tvoid *data;\n \tstruct packed_git *p;\n \toff_t base_offset;\n@@ -2128,8 +2126,7 @@ static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n {\n \tent->data = NULL;\n-\tent->lru.next->prev = ent->lru.prev;\n-\tent->lru.prev->next = ent->lru.next;\n+\tlist_del(&ent->lru);\n \tdelta_base_cached -= ent->size;\n }\n \n@@ -2168,24 +2165,24 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n {\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n \tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n-\tstruct delta_base_cache_lru_list *lru;\n+\tstruct list_head *lru;\n \n \trelease_delta_base_cache(ent);\n \tdelta_base_cached += base_size;\n \n-\tfor (lru = delta_base_cache_lru.next;\n-\t     delta_base_cached > delta_base_cache_limit\n-\t     && lru != &delta_base_cache_lru;\n-\t     lru = lru->next) {\n-\t\tstruct delta_base_cache_entry *f = (void *)lru;\n+\tlist_for_each(lru, &delta_base_cache_lru) {\n+\t\tstruct delta_base_cache_entry *f =\n+\t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n+\t\tif (delta_base_cached <= delta_base_cache_limit)\n+\t\t\tbreak;\n \t\tif (f->type == OBJ_BLOB)\n \t\t\trelease_delta_base_cache(f);\n \t}\n-\tfor (lru = delta_base_cache_lru.next;\n-\t     delta_base_cached > delta_base_cache_limit\n-\t     && lru != &delta_base_cache_lru;\n-\t     lru = lru->next) {\n-\t\tstruct delta_base_cache_entry *f = (void *)lru;\n+\tlist_for_each(lru, &delta_base_cache_lru) {\n+\t\tstruct delta_base_cache_entry *f =\n+\t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n+\t\tif (delta_base_cached <= delta_base_cache_limit)\n+\t\t\tbreak;\n \t\trelease_delta_base_cache(f);\n \t}\n \n@@ -2194,10 +2191,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tent->type = type;\n \tent->data = base;\n \tent->size = base_size;\n-\tent->lru.next = &delta_base_cache_lru;\n-\tent->lru.prev = delta_base_cache_lru.prev;\n-\tdelta_base_cache_lru.prev->next = &ent->lru;\n-\tdelta_base_cache_lru.prev = &ent->lru;\n+\tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299872","messageId":"20160822215956.kuqnucvfodxjrawn@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 5/7] delta_base_cache: drop special treatment of blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T21:59:56Z","receivedAt":"2016-08-22T22:00:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When the delta base cache runs out of allowed memory, it has\nto drop entries. It does so by walking an LRU list, dropping\nobjects until we are under the memory limit. But we actually\nwalk the list twice: once to drop blobs, and then again to\ndrop other objects (which are generally trees). This comes\nfrom 18bdec1 (Limit the size of the new delta_base_cache,\n2007-03-19).\n\nThis performs poorly as the number of entries grows, because\nany time dropping blobs does not satisfy the limit, we have\nto walk the _entire_ list, trees included, looking for blobs\nto drop, before starting to drop any trees.\n\nIt's not generally a problem now, as the cache is limited to\nonly 256 entries. But as we could benefit from increasing\nthat in a future patch, it's worth looking at how it\nperforms as the cache size grows. And the answer is \"not\nwell\".\n\nThe table below shows times for various operations with\ndifferent values of MAX_DELTA_CACHE (which is not a run-time\nknob; I recompiled with -DMAX_DELTA_CACHE=$n for each).\n\nI chose \"git log --raw\" (\"log-raw\" in the table) because it\nwill access all of the trees, but no blobs at all (so in a\nsense it is a worst case for this problem, because we will\nalways walk over the entire list of trees once before\nrealizing there are no blobs to drop). This is also\nrepresentative of other tree-only operations like \"rev-list\n--objects\" and \"git log -- <path>\".\n\nI also timed \"git log -Sfoo --raw\" (\"log-S\" in the table).\nIt similarly accesses all of the trees, but also the blobs\nfor each commit. It's representative of \"git log -p\", though\nit emphasizes the cost of blob access more, as \"-S\" is\ncheaper than computing an actual blob diff.\n\nAll timings are best-of-3 wall-clock times (though they all\nwere CPU bound, so the user CPU times are similar). The\nrepositories were fully packed with --depth=50, and the\ndefault core.deltaBaseCacheLimit of 96M was in effect.  The\ncurrent value of MAX_DELTA_CACHE is 256, so I started there\nand worked up by factors of 2.\n\nFirst, here are values for git.git (the asterisk signals the\nfastest run for each operation):\n\n    MAX_DELTA_CACHE    log-raw       log-S\n    ---------------   ---------    ---------\n                256   0m02.212s    0m12.634s\n                512   0m02.136s*   0m10.614s\n               1024   0m02.156s    0m08.614s\n               2048   0m02.208s    0m07.062s\n               4096   0m02.190s    0m06.484s*\n               8192   0m02.176s    0m07.635s\n              16384   0m02.913s    0m19.845s\n              32768   0m03.617s    1m05.507s\n              65536   0m04.031s    1m18.488s\n\nYou can see that for the tree-only log-raw case, we don't\nactually benefit that much as the cache grows (all the\ndifferences up through 8192 are basically just noise; this\nis probably because we don't actually have that many\ndistinct trees in git.git). But for log-S, we get a definite\nspeed improvement as the cache grows, but the improvements\nare lost as cache size grows and the linear LRU management\nstarts to dominate.\n\nHere's the same thing run against linux.git:\n\n    MAX_DELTA_CACHE    log-raw       log-S\n    ---------------   ---------    ----------\n                256   0m40.987s     5m13.216s\n                512   0m37.949s     5m03.243s\n               1024   0m35.977s     4m50.580s\n               2048   0m33.855s     4m39.818s\n               4096   0m32.913s     4m47.299s*\n               8192   0m32.176s*    5m14.650s\n              16384   0m32.185s     6m31.625s\n              32768   0m38.056s     9m31.136s\n              65536   1m30.518s    17m38.549s\n\nThe pattern is similar, though the effect in log-raw is more\npronounced here. The times dip down in the middle, and then\ngo back up as we keep growing.\n\nSo we know there's a problem. What's the solution?\n\nThe obvious one is to improve the data structure to avoid\nwalking over tree entries during the looking-for-blobs\ntraversal. We can do this by keeping _two_ LRU lists: one\nfor blobs, and one for other objects. We drop items from the\nblob LRU first, and then from the tree LRU (if necessary).\n\nHere's git.git using that strategy:\n\n    MAX_DELTA_CACHE    log-raw      log-S\n    ---------------   ---------   ----------\n                256   0m02.264s   0m12.830s\n                512   0m02.201s   0m10.771s\n               1024   0m02.181s   0m08.593s\n               2048   0m02.205s   0m07.116s\n               4096   0m02.158s   0m06.537s*\n               8192   0m02.213s   0m07.246s\n              16384   0m02.155s*  0m10.975s\n              32768   0m02.159s   0m16.047s\n              65536   0m02.181s   0m16.992s\n\nThe upswing on log-raw is gone completely. But log-S still\nhas it (albeit much better than without this strategy).\nLet's see what linux.git shows:\n\n    MAX_DELTA_CACHE    log-raw       log-S\n    ---------------   ---------    ---------\n                256   0m42.519s    5m14.654s\n                512   0m39.106s    5m04.708s\n               1024   0m36.802s    4m51.454s\n               2048   0m34.685s    4m39.378s*\n               4096   0m33.663s    4m44.047s\n               8192   0m33.157s    4m50.644s\n              16384   0m33.090s*   4m49.648s\n              32768   0m33.458s    4m53.371s\n              65536   0m33.563s    5m04.580s\n\nThe results are similar. The tree-only case again performs\nwell (not surprising; we're literally just dropping the one\nuseless walk, and not otherwise changing the cache eviction\nstrategy at all). But the log-S case again does a bit worse\nas the cache grows (though possibly that's within the noise,\nwhich is much larger for this case).\n\nPerhaps this is an indication that the \"remove blobs first\"\nstrategy is not actually optimal. The intent of it is to\navoid blowing out the tree cache when we see large blobs,\nbut it also means we'll throw away useful, recent blobs in\nfavor of older trees.\n\nLet's run the same numbers without caring about object type\nat all (i.e., one LRU list, and always evicting whatever is\nat the head, regardless of type).\n\nHere's git.git:\n\n    MAX_DELTA_CACHE    log-raw      log-S\n    ---------------   ---------   ---------\n                256   0m02.227s   0m12.821s\n                512   0m02.143s   0m10.602s\n               1024   0m02.127s   0m08.642s\n               2048   0m02.148s   0m07.123s\n               4096   0m02.194s   0m06.448s*\n               8192   0m02.239s   0m06.504s\n              16384   0m02.144s*  0m06.502s\n              32768   0m02.202s   0m06.622s\n              65536   0m02.230s   0m06.677s\n\nMuch smoother; there's no dramatic upswing as we increase\nthe cache size (some remains, though it's small enough that\nit's mostly run-to-run noise. E.g., in the log-raw case,\nnote how 8192 is 50-100ms higher than its neighbors). Note\nalso that we stop getting any real benefit for log-S after\nabout 4096 entries; that number will depend on the size of\nthe repository, the size of the blob entries, and the memory\nlimit of the cache.\n\nLet's see what linux.git shows for the same strategy:\n\n    MAX_DELTA_CACHE    log-raw      log-S\n    ---------------   ---------   ---------\n                256   0m41.661s   5m12.410s\n                512   0m39.547s   5m07.920s\n               1024   0m37.054s   4m54.666s\n               2048   0m35.871s   4m41.194s*\n               4096   0m34.646s   4m51.648s\n               8192   0m33.881s   4m55.342s\n              16384   0m35.190s   5m00.122s\n              32768   0m35.060s   4m58.851s\n              65536   0m33.311s*  4m51.420s\n\nIt's similarly good. As with the \"separate blob LRU\"\nstrategy, there's a lot of noise on the log-S run here. But\nit's certainly not any worse, is possibly a bit better, and\nthe improvement over \"separate blob LRU\" on the git.git case\nis dramatic.\n\nSo it seems like a clear winner, and that's what this patch\nimplements.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 8 --------\n 1 file changed, 8 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex c02e785..33564d6 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2175,14 +2175,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n \t\tif (delta_base_cached <= delta_base_cache_limit)\n \t\t\tbreak;\n-\t\tif (f->type == OBJ_BLOB)\n-\t\t\trelease_delta_base_cache(f);\n-\t}\n-\tlist_for_each(lru, &delta_base_cache_lru) {\n-\t\tstruct delta_base_cache_entry *f =\n-\t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n-\t\tif (delta_base_cached <= delta_base_cache_limit)\n-\t\t\tbreak;\n \t\trelease_delta_base_cache(f);\n \t}\n \n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299873","messageId":"20160822220007.lh3wzv6orlupfjmr@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 6/7] delta_base_cache: use hashmap.h","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T22:00:07Z","receivedAt":"2016-08-22T22:00:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The fundamental data structure of the delta base cache is a\nhash table mapping pairs of \"(packfile, offset)\" into\nstructs containing the actual object data. The hash table\nimplementation dates back to e5e0161 (Implement a simple\ndelta_base cache, 2007-03-17), and uses a fixed-size table.\nThe current size is a hard-coded 256 entries.\n\nBecause we need to be able to remove objects from the hash\ntable, entry lookup does not do any kind of probing to\nhandle collisions. Colliding items simply replace whatever\nis in their slot.  As a result, we have fewer usable slots\nthan even the 256 we allocate. At half full, each new item\nhas a 50% chance of displacing another one. Or another way\nto think about it: every item has a 1/256 chance of being\nejected due to hash collision, without regard to our LRU\nstrategy.\n\nSo it would be interesting to see the effect of increasing\nthe cache size on the runtime for some common operations. As\nwith the previous patch, we'll measure \"git log --raw\" for\ntree-only operations, and \"git log -Sfoo --raw\" for\noperations that touch trees and blobs. All times are\nwall-clock best-of-3, done against fully packed repos with\n--depth=50, and the default core.deltaBaseCacheLimit of\n96MB.\n\nHere are timings for various values of MAX_DELTA_CACHE\nagainst git.git (the asterisk marks the minimum time for\neach operation):\n\n    MAX_DELTA_CACHE    log-raw      log-S\n    ---------------   ---------   ---------\n                256   0m02.227s   0m12.821s\n                512   0m02.143s   0m10.602s\n               1024   0m02.127s   0m08.642s\n               2048   0m02.148s   0m07.123s\n               4096   0m02.194s   0m06.448s*\n               8192   0m02.239s   0m06.504s\n              16384   0m02.144s*  0m06.502s\n              32768   0m02.202s   0m06.622s\n              65536   0m02.230s   0m06.677s\n\nThe log-raw case isn't changed much at all here (probably\nbecause our trees just aren't that big in the first place,\nor possibly because we have so _few_ trees in git.git that\nthe 256-entry cache is enough). But once we start putting\nblobs in the cache, too, we see a big improvement (almost\n50%). The curve levels off around 4096, which means that we\ncan hold about that many entries before hitting the 96MB\nmemory limit (or possibly that the workload is small enough\nthat there is simply no more work to be optimized out by\ncaching more).\n\n(As a side note, I initially timed my existing git.git pack,\nwhich was a base of --aggressive combined with some pulls on\ntop. So it had quite a few deeper delta chains. The\n256-cache case was more like 15s, and it still dropped to\n~6.5s in the same way).\n\nHere are the timings for linux.git:\n\n    MAX_DELTA_CACHE    log-raw      log-S\n    ---------------   ---------   ---------\n                256   0m41.661s   5m12.410s\n                512   0m39.547s   5m07.920s\n               1024   0m37.054s   4m54.666s\n               2048   0m35.871s   4m41.194s*\n               4096   0m34.646s   4m51.648s\n               8192   0m33.881s   4m55.342s\n              16384   0m35.190s   5m00.122s\n              32768   0m35.060s   4m58.851s\n              65536   0m33.311s*  4m51.420s\n\nAs we grow we see a nice 20% speedup in the tree traversal,\nand more modest 10% in the log-S. This is probably an\nindication that we are bound less by the number of entries,\nand more by the memory limit (more on that below). What is\ninteresting is that the numbers bounce around a bit;\nincreasing the number of entries isn't always a strict\nimprovement.\n\nPartially this is due to noise in the measurement. But it\nmay also be an indication that our LRU ejection scheme is\nnot optimal. The smaller cache sizes introduce some\nrandomness into the ejection (due to collisions), which may\nsometimes work in our favor (and sometimes not!).\n\nSo what is the optimal setting of MAX_DELTA_CACHE? The\n\"bouncing\" in the linux.git log-S numbers notwithstanding,\nit mostly seems like bigger is better. And even if we were\nto try to find a \"sweet spot\", these are just two\nrepositories, that are not necessarily representative. The\nshape of history, the size of trees and blobs, the memory\nlimit configuration, etc, all will affect the outcome.\n\nRather than trying to find the \"right\" number, another\nstrategy is to just switch to a hash table that can actually\nstore collisions: namely our hashmap.h implementation.\n\nHere are numbers for that compared to the \"best\" we saw from\nadjusting MAX_DELTA_CACHE:\n\n        |       log-raw        |       log-S\n        | best       hashmap   | best       hashmap\n\t| ---------  --------- | ---------  ---------\n  git   | 0m02.144s  0m02.144s | 0m06.448s  0m06.688s\n  linux | 0m33.311s  0m33.092s | 4m41.194s  4m57.172s\n\nWe can see the results are similar in most cases, which is\nwhat we'd expect. We're not ejecting due to collisions at\nall, so this is purely representing the LRU. So really, we'd\nexpect this to model most closely the larger values of the\nstatic MAX_DELTA_CACHE limit. And that does seem to be\nwhat's happening, including the \"bounce\" in the linux log-S\ncase.\n\nSo while the value for that case _isn't_ as good as the\noptimal one measured above (which was 2048 entries), given\nthe bouncing I'm hesitant to suggest that 2048 is any kind\nof optimum (not even for linux.git, let alone as a general\nrule). The generic hashmap has the appeal that it drops the\nnumber of tweakable numbers by one, which means we can focus\non tuning other elements, like the LRU strategy or the\ncore.deltaBaseCacheLimit setting.\n\nAnd indeed, if we bump the cache limit to 1G (which is\nprobably silly for general use, but maybe something people\nwith big workstations would want to do), the linux.git log-S\ntime drops to 3m32s. That's something you really _can't_ do\neasily with the static hash table, because the number of\nentries needs to grow in proportion to the memory limit (so\n2048 is almost certainly not going to be the right value\nthere).\n\nThis patch takes that direction, and drops the static hash\ntable entirely in favor of using the hashmap.h API.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1_file.c | 94 +++++++++++++++++++++++++++++++++++++++----------------------\n 1 file changed, 60 insertions(+), 34 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 33564d6..a57b71d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2074,48 +2074,69 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \treturn buffer;\n }\n \n-#define MAX_DELTA_CACHE (256)\n-\n+static struct hashmap delta_base_cache;\n static size_t delta_base_cached;\n \n static LIST_HEAD(delta_base_cache_lru);\n \n-static struct delta_base_cache_entry {\n-\tstruct list_head lru;\n-\tvoid *data;\n+struct delta_base_cache_key {\n \tstruct packed_git *p;\n \toff_t base_offset;\n+};\n+\n+struct delta_base_cache_entry {\n+\tstruct hashmap hash;\n+\tstruct delta_base_cache_key key;\n+\tstruct list_head lru;\n+\tvoid *data;\n \tunsigned long size;\n \tenum object_type type;\n-} delta_base_cache[MAX_DELTA_CACHE];\n+};\n \n-static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n+static unsigned int pack_entry_hash(struct packed_git *p, off_t base_offset)\n {\n-\tunsigned long hash;\n+\tunsigned int hash;\n \n-\thash = (unsigned long)(intptr_t)p + (unsigned long)base_offset;\n+\thash = (unsigned int)(intptr_t)p + (unsigned int)base_offset;\n \thash += (hash >> 8) + (hash >> 16);\n-\treturn hash % MAX_DELTA_CACHE;\n+\treturn hash;\n }\n \n static struct delta_base_cache_entry *\n get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)\n {\n-\tunsigned long hash = pack_entry_hash(p, base_offset);\n-\treturn delta_base_cache + hash;\n+\tstruct hashmap_entry entry;\n+\tstruct delta_base_cache_key key;\n+\n+\tif (!delta_base_cache.cmpfn)\n+\t\treturn NULL;\n+\n+\thashmap_entry_init(&entry, pack_entry_hash(p, base_offset));\n+\tkey.p = p;\n+\tkey.base_offset = base_offset;\n+\treturn hashmap_get(&delta_base_cache, &entry, &key);\n }\n \n-static int eq_delta_base_cache_entry(struct delta_base_cache_entry *ent,\n-\t\t\t\t     struct packed_git *p, off_t base_offset)\n+static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,\n+\t\t\t\t   const struct delta_base_cache_key *b)\n {\n-\treturn (ent->data && ent->p == p && ent->base_offset == base_offset);\n+\treturn a->p == b->p && a->base_offset == b->base_offset;\n+}\n+\n+static int delta_base_cache_hash_cmp(const void *va, const void *vb,\n+\t\t\t\t     const void *vkey)\n+{\n+\tconst struct delta_base_cache_entry *a = va, *b = vb;\n+\tconst struct delta_base_cache_key *key = vkey;\n+\tif (key)\n+\t\treturn !delta_base_cache_key_eq(&a->key, key);\n+\telse\n+\t\treturn !delta_base_cache_key_eq(&a->key, &b->key);\n }\n \n static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n {\n-\tstruct delta_base_cache_entry *ent;\n-\tent = get_delta_base_cache_entry(p, base_offset);\n-\treturn eq_delta_base_cache_entry(ent, p, base_offset);\n+\treturn !!get_delta_base_cache_entry(p, base_offset);\n }\n \n /*\n@@ -2125,9 +2146,10 @@ static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n  */\n static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n {\n-\tent->data = NULL;\n+\thashmap_remove(&delta_base_cache, ent, &ent->key);\n \tlist_del(&ent->lru);\n \tdelta_base_cached -= ent->size;\n+\tfree(ent);\n }\n \n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n@@ -2136,8 +2158,7 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \tstruct delta_base_cache_entry *ent;\n \n \tent = get_delta_base_cache_entry(p, base_offset);\n-\n-\tif (!eq_delta_base_cache_entry(ent, p, base_offset))\n+\tif (!ent)\n \t\treturn unpack_entry(p, base_offset, type, base_size);\n \n \t*type = ent->type;\n@@ -2147,27 +2168,27 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \n static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n {\n-\tif (ent->data) {\n-\t\tfree(ent->data);\n-\t\tdetach_delta_base_cache_entry(ent);\n-\t}\n+\tfree(ent->data);\n+\tdetach_delta_base_cache_entry(ent);\n }\n \n void clear_delta_base_cache(void)\n {\n-\tunsigned long p;\n-\tfor (p = 0; p < MAX_DELTA_CACHE; p++)\n-\t\trelease_delta_base_cache(&delta_base_cache[p]);\n+\tstruct hashmap_iter iter;\n+\tstruct delta_base_cache_entry *entry;\n+\tfor (entry = hashmap_iter_first(&delta_base_cache, &iter);\n+\t     entry;\n+\t     entry = hashmap_iter_next(&iter)) {\n+\t\trelease_delta_base_cache(entry);\n+\t}\n }\n \n static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tvoid *base, unsigned long base_size, enum object_type type)\n {\n-\tunsigned long hash = pack_entry_hash(p, base_offset);\n-\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\tstruct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));\n \tstruct list_head *lru;\n \n-\trelease_delta_base_cache(ent);\n \tdelta_base_cached += base_size;\n \n \tlist_for_each(lru, &delta_base_cache_lru) {\n@@ -2178,12 +2199,17 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t\trelease_delta_base_cache(f);\n \t}\n \n-\tent->p = p;\n-\tent->base_offset = base_offset;\n+\tent->key.p = p;\n+\tent->key.base_offset = base_offset;\n \tent->type = type;\n \tent->data = base;\n \tent->size = base_size;\n \tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n+\n+\tif (!delta_base_cache.cmpfn)\n+\t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, 0);\n+\thashmap_entry_init(ent, pack_entry_hash(p, base_offset));\n+\thashmap_add(&delta_base_cache, ent);\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n@@ -2227,7 +2253,7 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\tstruct delta_base_cache_entry *ent;\n \n \t\tent = get_delta_base_cache_entry(p, curpos);\n-\t\tif (eq_delta_base_cache_entry(ent, p, curpos)) {\n+\t\tif (ent) {\n \t\t\ttype = ent->type;\n \t\t\tdata = ent->data;\n \t\t\tsize = ent->size;\n-- \n2.10.0.rc1.118.ge2299eb\n\n"},{"id":"299875","messageId":"20160822220109.567ez5kslxggcb7a@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822215725.qdikfcaz3smhulau@sigill.intra.peff.net","subject":"[PATCH 7/7] t/perf: add basic perf tests for delta base cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-22T22:01:10Z","receivedAt":"2016-08-22T22:01:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This just shows off the improvements done by the last few\npatches, and gives us a baseline for noticing regressions in\nthe future. Here are the results with linux.git as the perf\n\"large repo\":\n\nTest                origin                HEAD\n-------------------------------------------------------------------\n0003.1: log --raw   43.41(40.36+2.69)     33.86(30.96+2.41) -22.0%\n0003.2: log -S      313.61(309.74+3.78)   298.75(295.58+3.00) -4.7%\n\n(for a large repo, the \"log -S\" improvements are greater if\nyou bump the delta base cache limit, but I think it makes\nsense to test the \"stock\" behavior, since that is what most\npeople will see).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI also got good times for \"log -S\" when measuring git.git (but _not_\nwhen measuring \"log --raw\", because of its size). So I guess perhaps the\nscript could measure both. I'm not sure if the perf framework is ready\nfor using both test_default_repo and test_large_repo, though.\n\n t/perf/p0003-delta-base-cache.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n create mode 100755 t/perf/p0003-delta-base-cache.sh\n\ndiff --git a/t/perf/p0003-delta-base-cache.sh b/t/perf/p0003-delta-base-cache.sh\nnew file mode 100755\nindex 0000000..62369ea\n--- /dev/null\n+++ b/t/perf/p0003-delta-base-cache.sh\n@@ -0,0 +1,31 @@\n+#!/bin/sh\n+\n+test_description='Test operations that emphasize the delta base cache.\n+\n+We look at both \"log --raw\", which should put only trees into the delta cache,\n+and \"log -Sfoo --raw\", which should look at both trees and blobs.\n+\n+Any effects will be emphasized if the test repository is fully packed (loose\n+objects obviously do not use the delta base cache at all). It is also\n+emphasized if the pack has long delta chains (e.g., as produced by \"gc\n+--aggressive\"), though cache is still quite noticeable even with the default\n+depth of 50.\n+\n+The setting of core.deltaBaseCacheLimit in the source repository is also\n+relevant (depending on the size of your test repo), so be sure it is consistent\n+between runs.\n+'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+# puts mostly trees into the delta base cache\n+test_perf 'log --raw' '\n+\tgit log --raw >/dev/null\n+'\n+\n+test_perf 'log -S' '\n+\tgit log --raw -Sfoo >/dev/null\n+'\n+\n+test_done\n-- \n2.10.0.rc1.118.ge2299eb\n"},{"id":"299877","messageId":"20160822231806.GA26148@starla","threadId":"43906","inReplyTo":"20160822215942.nm2jcrkyib7acr4u@sigill.intra.peff.net","subject":"Re: [PATCH 4/7] delta_base_cache: use list.h for LRU","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2016-08-22T23:18:06Z","receivedAt":"2016-08-22T23:18:12Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King <peff@peff.net> wrote:\n> We keep an LRU list of entries for when we need to drop\n> something from an over-full cache. The list is implemented\n> as a circular doubly-linked list, which is exactly what\n> list.h provides. We can save a few lines by using the list.h\n> macros and functions. More importantly, this makes the code\n> easier to follow, as the reader sees explicit concepts like\n> \"list_add_tail()\" instead of pointer manipulation.\n\nYay!\n\n> As a bonus, the list_entry() macro lets us place the lru\n> pointers anywhere inside the delta_base_cache_entry struct\n> (as opposed to just casting the pointer, which requires it\n> at the front of the struct). This will be useful in later\n> patches when we need to place other items at the front of\n> the struct (e.g., our hashmap implementation requires this).\n\nOn a side note, I think we should s/list_entry/container_of/ and\nuse container_of for hashmap.\n\nLinux kernel defines list_entry to use container_of,\nbut I'd rather avoid introducing the duality entirely.\n\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> I think the result is much nicer, but I found list_entry() a little\n> disappointing, because we lack typeof(). So you are stuck writing:\n> \n>   struct delta_base_cache_entry *f =\n>     list_entry(p, struct delta_base_cache_entry, lru);\n> \n> I waffled on adding something like:\n> \n>   LIST_ITEM(struct delta_bas_cache_entry, f, p, lru);\n> \n> to declare \"f\" as above. But it's getting rather magical and un-C-like.\n\nRight.  I'd rather keep the list_entry/container_of usage\nidentical to what developers familiar using userspace-rcu,\nccan/list, or the Linux kernel expect.\n\n>  sha1_file.c | 38 ++++++++++++++++----------------------\n>  1 file changed, 16 insertions(+), 22 deletions(-)\n\nGood to see the code reduction.\n"},{"id":"299890","messageId":"20160823004811.n3yuthgrxaheivzn@sigill.intra.peff.net","threadId":"43906","inReplyTo":"20160822231806.GA26148@starla","subject":"Re: [PATCH 4/7] delta_base_cache: use list.h for LRU","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-23T00:48:11Z","receivedAt":"2016-08-23T00:48:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 22, 2016 at 11:18:06PM +0000, Eric Wong wrote:\n\n> > As a bonus, the list_entry() macro lets us place the lru\n> > pointers anywhere inside the delta_base_cache_entry struct\n> > (as opposed to just casting the pointer, which requires it\n> > at the front of the struct). This will be useful in later\n> > patches when we need to place other items at the front of\n> > the struct (e.g., our hashmap implementation requires this).\n> \n> On a side note, I think we should s/list_entry/container_of/ and\n> use container_of for hashmap.\n> \n> Linux kernel defines list_entry to use container_of,\n> but I'd rather avoid introducing the duality entirely.\n\nThat does make it slightly more annoying to use, since container_of()\nrequires naming the original type again (because of our lack of typeof),\nwhereas now you can freely cast between \"struct hashmap_entry\" and the\nactual item. But if you are proposing to actually fix the hashmap to\neliminate the requirement to put the entry at the front, that might have\nvalue (I'm not sure how easy it is to do, though; a lot of those casts\nhappen inside the hashmap code which is type-agnostic).\n\n> > Signed-off-by: Jeff King <peff@peff.net>\n> > ---\n> > I think the result is much nicer, but I found list_entry() a little\n> > disappointing, because we lack typeof(). So you are stuck writing:\n> > \n> >   struct delta_base_cache_entry *f =\n> >     list_entry(p, struct delta_base_cache_entry, lru);\n> > \n> > I waffled on adding something like:\n> > \n> >   LIST_ITEM(struct delta_bas_cache_entry, f, p, lru);\n> > \n> > to declare \"f\" as above. But it's getting rather magical and un-C-like.\n> \n> Right.  I'd rather keep the list_entry/container_of usage\n> identical to what developers familiar using userspace-rcu,\n> ccan/list, or the Linux kernel expect.\n\nMakes sense. I am not familiar with those APIs myself, but I do not see\nany reason to deviate from them for no good reason.\n\n> >  sha1_file.c | 38 ++++++++++++++++----------------------\n> >  1 file changed, 16 insertions(+), 22 deletions(-)\n> \n> Good to see the code reduction.\n\nYep. I realized the \"hashmap must go at the front of the struct\" thing\nlater. My initial reason for converting was actually to make the\n\"separate blob LRU\" patch easier (since without this patch, it literally\ndoubles the amount of pointer manipulation required).\n\nFor reference, in case anybody wants to duplicate my experiments from\npatch 5, that patch looks like this:\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 2cd1b79..e82be30 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2076,7 +2076,8 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \n static size_t delta_base_cached;\n \n-static LIST_HEAD(delta_base_cache_lru);\n+static LIST_HEAD(delta_base_cache_lru_blobs);\n+static LIST_HEAD(delta_base_cache_lru_other);\n \n static struct delta_base_cache_entry {\n \tstruct list_head lru;\n@@ -2170,15 +2171,14 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \trelease_delta_base_cache(ent);\n \tdelta_base_cached += base_size;\n \n-\tlist_for_each(lru, &delta_base_cache_lru) {\n+\tlist_for_each(lru, &delta_base_cache_lru_blobs) {\n \t\tstruct delta_base_cache_entry *f =\n \t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n \t\tif (delta_base_cached <= delta_base_cache_limit)\n \t\t\tbreak;\n-\t\tif (f->type == OBJ_BLOB)\n-\t\t\trelease_delta_base_cache(f);\n+\t\trelease_delta_base_cache(f);\n \t}\n-\tlist_for_each(lru, &delta_base_cache_lru) {\n+\tlist_for_each(lru, &delta_base_cache_lru_other) {\n \t\tstruct delta_base_cache_entry *f =\n \t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n \t\tif (delta_base_cached <= delta_base_cache_limit)\n@@ -2191,7 +2191,10 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tent->type = type;\n \tent->data = base;\n \tent->size = base_size;\n-\tlist_add_tail(&ent->lru, &delta_base_cache_lru);\n+\tif (type == OBJ_BLOB)\n+\t\tlist_add_tail(&ent->lru, &delta_base_cache_lru_blobs);\n+\telse\n+\t\tlist_add_tail(&ent->lru, &delta_base_cache_lru_other);\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n\n-Peff\n"},{"id":"299994","messageId":"xmqq60qrupl7.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160822215744.nc3yqv64gf3hwcv4@sigill.intra.peff.net","subject":"Re: [PATCH 1/7] cache_or_unpack_entry: drop keep_cache parameter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-23T21:45:24Z","receivedAt":"2016-08-23T21:46:15Z","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> There is only one caller of cache_or_unpack_entry() and it\n> always passes 1 for the keep_cache parameter. We can\n> simplify it by dropping the \"!keep_cache\" case.\n>\n> Another call, which did pass 0, was dropped in abe601b\n> (sha1_file: remove recursion in unpack_entry, 2013-03-27),\n> as unpack_entry() now does more complicated things than a\n> simple unpack when there is a cache miss.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  sha1_file.c | 13 +++----------\n>  1 file changed, 3 insertions(+), 10 deletions(-)\n\nMakes sense.  Thanks.\n"},{"id":"299997","messageId":"xmqqwpj7tauc.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160822215758.uamavr7koin3ze6c@sigill.intra.peff.net","subject":"Re: [PATCH 3/7] release_delta_base_cache: reuse existing detach function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-23T21:49:15Z","receivedAt":"2016-08-23T21:49:49Z","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> This function drops an entry entirely from the cache,\n> meaning that aside from the freeing of the buffer, it is\n> exactly equivalent to detach_delta_base_cache_entry(). Let's\n> build on top of the detach function, which shortens the code\n> and will make it simpler when we change out the underlying\n> storage in future patches.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  sha1_file.c | 5 +----\n>  1 file changed, 1 insertion(+), 4 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 1d0810c..8264b39 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2152,10 +2152,7 @@ static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n>  {\n>  \tif (ent->data) {\n>  \t\tfree(ent->data);\n> -\t\tent->data = NULL;\n> -\t\tent->lru.next->prev = ent->lru.prev;\n> -\t\tent->lru.prev->next = ent->lru.next;\n> -\t\tdelta_base_cached -= ent->size;\n> +\t\tdetach_delta_base_cache_entry(ent);\n\nIf we were designing this from scratch, we might have made detach_*\nto return the pointer to minimize direct access to ent->data, but I\ndo not think it is worth it.  Looks very sensible.\n"},{"id":"299998","messageId":"xmqq1t1fuphq.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160822215753.xy7hlho7niex3wpm@sigill.intra.peff.net","subject":"Re: [PATCH 2/7] clear_delta_base_cache_entry: use a more descriptive name","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-23T21:47:29Z","receivedAt":"2016-08-23T21:50:49Z","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> The delta base cache entries are stored in a fixed-length\n> hash table. So the way to remove an entry is to \"clear\" the\n> slot in the table, and that is what this function does.\n>\n> However, the name is a leaky abstraction. If we were to\n> change the hash table implementation, it would no longer be\n> about \"clearing\". We should name it after _what_ it does,\n> not _how_ it does it. I.e., something like \"remove\" instead\n> of \"clear\".\n>\n> But that does not tell the whole story, either. The subtle\n> thing about this function is that it removes the entry, but\n> does not free the entry data. So a more descriptive name is\n> \"detach\"; we give ownership of the data buffer to the\n> caller, and remove any other resources.\n\nOK.  Sounds sensible.\n"},{"id":"300003","messageId":"xmqqshtvt9h9.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160822215956.kuqnucvfodxjrawn@sigill.intra.peff.net","subject":"Re: [PATCH 5/7] delta_base_cache: drop special treatment of blobs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-23T22:18:42Z","receivedAt":"2016-08-23T22:18:50Z","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> Let's run the same numbers without caring about object type\n> at all (i.e., one LRU list, and always evicting whatever is\n> at the head, regardless of type).\n> ...\n> So it seems like a clear winner, and that's what this patch\n> implements.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n\nNice work.  You make your readers expect some clever data structures\nthat may perform better than the obvious two-separate-list approach\nand end up using the simplest way.  Quite nice.\n\n\n\n>  sha1_file.c | 8 --------\n>  1 file changed, 8 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index c02e785..33564d6 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2175,14 +2175,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n>  \t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n>  \t\tif (delta_base_cached <= delta_base_cache_limit)\n>  \t\t\tbreak;\n> -\t\tif (f->type == OBJ_BLOB)\n> -\t\t\trelease_delta_base_cache(f);\n> -\t}\n> -\tlist_for_each(lru, &delta_base_cache_lru) {\n> -\t\tstruct delta_base_cache_entry *f =\n> -\t\t\tlist_entry(lru, struct delta_base_cache_entry, lru);\n> -\t\tif (delta_base_cached <= delta_base_cache_limit)\n> -\t\t\tbreak;\n>  \t\trelease_delta_base_cache(f);\n>  \t}\n"},{"id":"300004","messageId":"xmqqoa4jt94q.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160822220007.lh3wzv6orlupfjmr@sigill.intra.peff.net","subject":"Re: [PATCH 6/7] delta_base_cache: use hashmap.h","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-23T22:26:13Z","receivedAt":"2016-08-23T22:26:20Z","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> So while the value for that case _isn't_ as good as the\n> optimal one measured above (which was 2048 entries), given\n> the bouncing I'm hesitant to suggest that 2048 is any kind\n> of optimum (not even for linux.git, let alone as a general\n> rule). The generic hashmap has the appeal that it drops the\n> number of tweakable numbers by one, which means we can focus\n> on tuning other elements, like the LRU strategy or the\n> core.deltaBaseCacheLimit setting.\n>\n> And indeed, if we bump the cache limit to 1G (which is\n> probably silly for general use, but maybe something people\n> with big workstations would want to do), the linux.git log-S\n> time drops to 3m32s. That's something you really _can't_ do\n> easily with the static hash table, because the number of\n> entries needs to grow in proportion to the memory limit (so\n> 2048 is almost certainly not going to be the right value\n> there).\n>\n> This patch takes that direction, and drops the static hash\n> table entirely in favor of using the hashmap.h API.\n\nSounds very sensible.\n"},{"id":"300085","messageId":"20160824174122.372c7pi4ub5bxcat@sigill.intra.peff.net","threadId":"43906","inReplyTo":"xmqqwpj7tauc.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 3/7] release_delta_base_cache: reuse existing detach function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-24T17:41:22Z","receivedAt":"2016-08-24T17:41:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 23, 2016 at 02:49:15PM -0700, Junio C Hamano wrote:\n\n> > diff --git a/sha1_file.c b/sha1_file.c\n> > index 1d0810c..8264b39 100644\n> > --- a/sha1_file.c\n> > +++ b/sha1_file.c\n> > @@ -2152,10 +2152,7 @@ static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n> >  {\n> >  \tif (ent->data) {\n> >  \t\tfree(ent->data);\n> > -\t\tent->data = NULL;\n> > -\t\tent->lru.next->prev = ent->lru.prev;\n> > -\t\tent->lru.prev->next = ent->lru.next;\n> > -\t\tdelta_base_cached -= ent->size;\n> > +\t\tdetach_delta_base_cache_entry(ent);\n> \n> If we were designing this from scratch, we might have made detach_*\n> to return the pointer to minimize direct access to ent->data, but I\n> do not think it is worth it.  Looks very sensible.\n\nI actually looked into that during the conversion in patch 2/7. I didn't\nwant to just return ent->data, because there are actually several bits\nof information to \"rescue\" from the entry. So it looks more like:\n\n  char *data = detach_delta_base_cache_entry(ent, NULL, NULL);\n  free(data);\n\nhere, and\n\n  data = detach_delta_base_cache_entry(ent, &type, &size);\n\nin unpack_entry().\n\nThat is not too bad, I guess. I can switch it if you prefer that way.\nSince there are only these two callers with two different sets of needs\n(and the function is static), I just let them continue inspecting the\nelements directly.\n\n-Peff\n"},{"id":"300092","messageId":"xmqq60qqqc85.fsf@gitster.mtv.corp.google.com","threadId":"43906","inReplyTo":"20160824174122.372c7pi4ub5bxcat@sigill.intra.peff.net","subject":"Re: [PATCH 3/7] release_delta_base_cache: reuse existing detach function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-24T17:59:54Z","receivedAt":"2016-08-24T18:01:17Z","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> That is not too bad, I guess. I can switch it if you prefer that way.\n> Since there are only these two callers with two different sets of needs\n> (and the function is static), I just let them continue inspecting the\n> elements directly.\n\nI do not think it is too hard to refactor later when need arises; it\nis not like we have too many callers and this is a file-scope static\nhelper to begin with.\n"}]}