{"thread":{"id":"7311","subject":"[PATCH] Limit the size of the new delta_base_cache","startedAt":"2007-03-19T05:14:37Z","lastAt":"2007-03-19T18:08:36Z","messageCount":8,"participants":["Shawn O. Pearce","Linus Torvalds","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"37468","messageId":"20070319051437.GA22494@spearce.org","threadId":"7311","inReplyTo":null,"subject":"[PATCH] Limit the size of the new delta_base_cache","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-19T05:14:37Z","receivedAt":"2007-03-19T05:14:37Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Round two, based on comments on IRC from Junio:\n\n-->8--\n[PATCH] Limit the size of the new delta_base_cache\n\nThe new configuration variable core.deltaBaseCacheLimit allows the\nuser to control how much memory they are willing to give to Git for\ncaching base objects of deltas.  This is not normally meant to be\na user tweakable knob; the \"out of the box\" settings are meant to\nbe suitable for almost all workloads.\n\nWe default to 16 MiB under the assumption that the cache is not\nmeant to consume all of the user's available memory, and that the\ncache's main purpose was to cache trees, for faster path limiters\nduring revision traversal.  Since trees tend to be relatively small\nobjects, this relatively small limit should still allow a large\nnumber of objects.\n\nOn the other hand we don't want the cache to start storing 200\ndifferent versions of a 200 MiB blob, as this could easily blow\nthe entire address space of a 32 bit process.\n\nWe evict OBJ_BLOB from the cache first (credit goes to Junio) as\nwe want to favor OBJ_TREE within the cache.  These are the objects\nthat have the highest inflate() startup penalty, as they tend to\nbe small and thus don't have that much of a chance to ammortize\nthat penalty over the entire data.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n Documentation/config.txt |   13 +++++++++++++\n cache.h                  |    1 +\n config.c                 |    5 +++++\n environment.c            |    1 +\n sha1_file.c              |   31 ++++++++++++++++++++++++++-----\n 5 files changed, 46 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 953acae..8796929 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -240,6 +240,19 @@ the largest projects.  You probably do not need to adjust this value.\n +\n Common unit suffixes of 'k', 'm', or 'g' are supported.\n \n+core.deltaBaseCacheLimit::\n+\tMaximum number of bytes to reserve for caching base objects\n+\tthat multiple deltafied objects reference.  By storing the\n+\tentire decompressed base objects in a cache Git is able\n+\tto avoid unpacking and decompressing frequently used base\n+\tobjects multiple times.\n++\n+Default is 16 MiB on all platforms.  This should be reasonable\n+for all users/operating systems, except on the largest projects.\n+You probably do not need to adjust this value.\n++\n+Common unit suffixes of 'k', 'm', or 'g' are supported.\n+\n alias.*::\n \tCommand aliases for the gitlink:git[1] command wrapper - e.g.\n \tafter defining \"alias.last = cat-file commit HEAD\", the invocation\ndiff --git a/cache.h b/cache.h\nindex 3818e10..9a3c8c8 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -228,6 +228,7 @@ extern const char *apply_default_whitespace;\n extern int zlib_compression_level;\n extern size_t packed_git_window_size;\n extern size_t packed_git_limit;\n+extern size_t delta_base_cache_limit;\n extern int auto_crlf;\n \n #define GIT_REPO_VERSION 0\ndiff --git a/config.c b/config.c\nindex d537311..6479855 100644\n--- a/config.c\n+++ b/config.c\n@@ -331,6 +331,11 @@ int git_default_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.deltabasecachelimit\")) {\n+\t\tdelta_base_cache_limit = git_config_int(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.autocrlf\")) {\n \t\tif (value && !strcasecmp(value, \"input\")) {\n \t\t\tauto_crlf = -1;\ndiff --git a/environment.c b/environment.c\nindex 0151ad0..ef2f490 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -27,6 +27,7 @@ const char *apply_default_whitespace;\n int zlib_compression_level = Z_DEFAULT_COMPRESSION;\n size_t packed_git_window_size = DEFAULT_PACKED_GIT_WINDOW_SIZE;\n size_t packed_git_limit = DEFAULT_PACKED_GIT_LIMIT;\n+size_t delta_base_cache_limit = 16 * 1024 * 1024;\n int pager_in_use;\n int pager_use_color = 1;\n int auto_crlf = 0;\t/* 1: both ways, -1: only when adding git objects */\ndiff --git a/sha1_file.c b/sha1_file.c\nindex ee64865..0d039a3 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1354,6 +1354,7 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \n #define MAX_DELTA_CACHE (256)\n \n+static size_t delta_base_cached;\n static struct delta_base_cache_entry {\n \tstruct packed_git *p;\n \toff_t base_offset;\n@@ -1384,9 +1385,10 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \treturn unpack_entry(p, base_offset, type, base_size);\n \n found_cache_entry:\n-\tif (!keep_cache)\n+\tif (!keep_cache) {\n \t\tent->data = NULL;\n-\telse {\n+\t\tdelta_base_cached -= ent->size;\n+\t} else {\n \t\tret = xmalloc(ent->size + 1);\n \t\tmemcpy(ret, ent->data, ent->size);\n \t\t((char *)ret)[ent->size] = 0;\n@@ -1396,14 +1398,33 @@ found_cache_entry:\n \treturn ret;\n }\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\tent->data = NULL;\n+\t\tdelta_base_cached -= ent->size;\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+\tunsigned long i, hash = pack_entry_hash(p, base_offset);\n \tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n \n-\tif (ent->data)\n-\t\tfree(ent->data);\n+\trelease_delta_base_cache(ent);\n+\tdelta_base_cached += base_size;\n+\tfor (i = 0; delta_base_cached > delta_base_cache_limit\n+\t\t&& i < ARRAY_SIZE(delta_base_cache); i++) {\n+\t\tstruct delta_base_cache_entry *f = delta_base_cache + i;\n+\t\tif (f->type == OBJ_BLOB)\n+\t\t\trelease_delta_base_cache(f);\n+\t}\n+\tfor (i = 0; delta_base_cached > delta_base_cache_limit\n+\t\t&& i < ARRAY_SIZE(delta_base_cache); i++)\n+\t\trelease_delta_base_cache(delta_base_cache + i);\n+\n \tent->p = p;\n \tent->base_offset = base_offset;\n \tent->type = type;\n-- \n1.5.0.5.1030.gc69a\n"},{"id":"37514","messageId":"Pine.LNX.4.64.0703190906320.6730@woody.linux-foundation.org","threadId":"7311","inReplyTo":"20070319051437.GA22494@spearce.org","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-19T16:10:39Z","receivedAt":"2007-03-19T16:10:39Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Shawn O. Pearce wrote:\n>\n> Round two, based on comments on IRC from Junio:\n\nOne more change: please don't even *add* objects to the cache that are \nbigger than 10-20% of the cache limit!\n\nIf you start adding big objects, and you have some cache limit, that will \nmake the cache seriously less useful by causing eviction of potentially \nmuch more interesting objects, and also obviously causing the cache code \nitself to spend much more time picking objects (since it's enough to have \njust a few big objects to make the cache eviction decide it needs to \nevict).\n\nLimiting by size is also effective since anything that is more than a \nmegabyte is likely to be a blob anyway, and thus much less useful for \ncaching in the first place. So there are just tons of reasons to say \n\"don't even add it in the first place\" if you decide to go with any limit \nat all.\n\n\t\tLinus\n"},{"id":"37519","messageId":"alpine.LFD.0.83.0703191218190.18328@xanadu.home","threadId":"7311","inReplyTo":"Pine.LNX.4.64.0703190906320.6730@woody.linux-foundation.org","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-19T16:41:10Z","receivedAt":"2007-03-19T16:41:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 19 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Mon, 19 Mar 2007, Shawn O. Pearce wrote:\n> >\n> > Round two, based on comments on IRC from Junio:\n> \n> One more change: please don't even *add* objects to the cache that are \n> bigger than 10-20% of the cache limit!\n> \n> If you start adding big objects, and you have some cache limit, that will \n> make the cache seriously less useful by causing eviction of potentially \n> much more interesting objects, and also obviously causing the cache code \n> itself to spend much more time picking objects (since it's enough to have \n> just a few big objects to make the cache eviction decide it needs to \n> evict).\n> \n> Limiting by size is also effective since anything that is more than a \n> megabyte is likely to be a blob anyway, and thus much less useful for \n> caching in the first place. So there are just tons of reasons to say \n> \"don't even add it in the first place\" if you decide to go with any limit \n> at all.\n\nOn the other hand......\n\nEither you parse blobs or you don't.  If you only do logs with path \nlimiting then you won't add blobs to the cache anyway.\n\nIf you do end up adding blobs to the cache that means you have blob \ndeltas to resolve, and even that operation should benefit from the cache \nregardless of the object size.\n\nIn fact, the bigger is the object, the more effective will be the cache.  \nBecause you certainly don't want to have a complete breakdown in \nperformance just because a blob just crossed the 20% treshold.\n\nAnd because we usually walk objects from newest to oldest, and because \ndeltas are usually oriented in the same direction, we only need to tweak \nthe current eviction loop a bit so on average the oldest objects are \nevicted first so next time around the current base will still be there \nfor the next delta depth.  Given the nature of the hash containing the \nobject's offset that means starting the loop at the next entry index \ninstead of zero which should do the trick pretty well.\n\nOf course if you end up in a condition where you have to prune the cache \ncontinuously, you'll spend more cycles picking up the object to evict, \nbut it is likely to be so much less work than reintering that O(n!) \nbehavior with deflate we had without the cache, and even worse since we \nmean big objects in this case.\n\nSo I wouldn't add any rule of that sort unless it is actually proven to \nbe bad.\n\n\nNicolas\n"},{"id":"37522","messageId":"alpine.LFD.0.83.0703191248360.18328@xanadu.home","threadId":"7311","inReplyTo":"alpine.LFD.0.83.0703191218190.18328@xanadu.home","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-19T16:54:12Z","receivedAt":"2007-03-19T16:54:12Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 19 Mar 2007, Nicolas Pitre wrote:\n\n> And because we usually walk objects from newest to oldest, and because \n> deltas are usually oriented in the same direction, we only need to tweak \n> the current eviction loop a bit so on average the oldest objects are \n> evicted first so next time around the current base will still be there \n> for the next delta depth.  Given the nature of the hash containing the \n> object's offset that means starting the loop at the next entry index \n> instead of zero which should do the trick pretty well.\n\nOK. Two flaws above: to be clear it is the newest objects in terms of \nabsolute age should be evicted first, which means the oldest to have \nbeen cached.  Then the hash cannot be representative of the object \nordering because it is reduced to 8 bits and objects are often enough \nmore than 256 bytes apart to make this hash based ordering completely \nrandom.  A simple LRU might be quite effective instead.\n\n\nNicolas\n"},{"id":"37524","messageId":"Pine.LNX.4.64.0703191004560.6730@woody.linux-foundation.org","threadId":"7311","inReplyTo":"alpine.LFD.0.83.0703191218190.18328@xanadu.home","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-19T17:07:43Z","receivedAt":"2007-03-19T17:07:43Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Nicolas Pitre wrote:\n> \n> In fact, the bigger is the object, the more effective will be the cache.  \n\nYes. BUT ONLY IF THE CACHE ISN'T SIZE-LIMITED!\n\nOnce you limit the size of the cache, you change the whole equation.\n\nIt's usually *more* expensive to re-parse two half-sized objects than it \nis to parse one large object. So if you have to choose between \nthrowing out two small objects or throwing out one large one, you \nshould choose the single large one.\n\nWhich totally throws your argument out of the window. It's simply not true \nany more: the cache will *not* be more effective the larger the objects \nare, because you are ignoring the fact that adding a large object will \n*remove* many small ones.\n\nSo if I were Junio, I wouldn't accept your patch as it is now. Your \nargument is simply fundamentally flawed.\n\n\t\tLinus\n"},{"id":"37525","messageId":"Pine.LNX.4.64.0703191008400.6730@woody.linux-foundation.org","threadId":"7311","inReplyTo":"Pine.LNX.4.64.0703191004560.6730@woody.linux-foundation.org","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-19T17:17:50Z","receivedAt":"2007-03-19T17:17:50Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Linus Torvalds wrote:\n> \n> Which totally throws your argument out of the window. It's simply not true \n> any more: the cache will *not* be more effective the larger the objects \n> are, because you are ignoring the fact that adding a large object will \n> *remove* many small ones.\n\nAnd btw, if you are adding a delta-base object that is bigger than 10%-20% \n(those particular numbers taken out of where the sun don't shine, but they \nare reasonable) of your cache size, you are pretty much *guaranteed* to be \nremoving many small ones.\n\nWhy? \n\nThe whole *point* of the delta-base cache is that it wants to avoid the \nO(n**2) costs of the long cache-chains. So a delta-base object on its own \nis almost not interesting for the cache: the cache comes into its own only \nif you have a *chain* of delta-base objects.\n\nSo rather than thinking about \"one big object\", you need to think about \"a \nchain of objects\", and realize that if one of them is big, then the others \nwill be too (otherwise they'd not have generated a delta-chain in the \nfirst place).\n\nSo at an object size of 10-20% of the total allowed cache size, and a \ntotal cache _index_ of 256 entries, if you start adding big objects, you \ncan pretty much be guaranteed that either\n\n (a) the delta-base cache won't be effective for the big object anyway, \n     since there's just one or two of them (and the cache size limit isn't \n     triggered)\nOR\n (b) you start probing the cache size limit, and you'll be throwing out \n     many small object.\n\nFinally, since the delta-chain cache is likely not as useful for blobs \nanyway (you don't tend to use tons of big related blobs anyway, and if you \ndo, the real costs are likely the xdl diff generation between them rather \nthan the object creation itself!), you're also likely optimizing the wrong \ncase, since big delta-base objects are almost certainly goign to be blobs.\n\nAnd no, I don't have any \"hard numbers\" to back this up, but if you want \nanother argument, realize that delta chains are limited to a depth of ten, \nand if a *single* chain can overflow the delta-chain cache, then the cache \nends up being 100% *in*effective. And do the math: if the object size is \n10-20% of the total allowed cache size, how many objects in the chain are \nyou going to fit in the cache?\n\nSo there are multiple different reasons to think that big objects are \nactually *bad* for caching when you have a total size limit, not good.\n\n\t\tLinus\n"},{"id":"37526","messageId":"Pine.LNX.4.64.0703191018180.6730@woody.linux-foundation.org","threadId":"7311","inReplyTo":"alpine.LFD.0.83.0703191248360.18328@xanadu.home","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-19T17:18:54Z","receivedAt":"2007-03-19T17:18:54Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Nicolas Pitre wrote:\n>\n> A simple LRU might be quite effective instead.\n\nI definitely agree on that. A simple LRU is probably the right replacement \nstrategy.\n\n\t\tLinus\n"},{"id":"37528","messageId":"alpine.LFD.0.83.0703191332240.18328@xanadu.home","threadId":"7311","inReplyTo":"Pine.LNX.4.64.0703191008400.6730@woody.linux-foundation.org","subject":"Re: [PATCH] Limit the size of the new delta_base_cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-19T18:08:36Z","receivedAt":"2007-03-19T18:08:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nFirst this is Shawn's patch not mine.  But I still don't think it is \nthat bad even as is, and it was already merged by Junio.  I believe it \ncan be made better without segregating big objects though.\n\nOn Mon, 19 Mar 2007, Linus Torvalds wrote:\n\n> And no, I don't have any \"hard numbers\" to back this up, but if you want \n> another argument, realize that delta chains are limited to a depth of ten, \n> and if a *single* chain can overflow the delta-chain cache, then the cache \n> ends up being 100% *in*effective.\n\nNo.  You forget what I said about delta direction.\n\nDeltas are meant to be ordered so a newer object should be a base for an \nolder objects.  And we usually parse objects from newer to older ones \ntoo.\n\nSo let's suppose that the cache has only two entries.  If there was only \none delta chain in the pack and it is ideally laid out so the delta \nchain is effectively going deeper with older objects as we currently \nmean it to, then the cache would still be perfectly effective because, \nas we move further back in history, objects deeper in the delta chain \nwill be requested, and the delta base a single level up will be there to \nbe used just before being evicted.  And so on all through the delta \nchain.\n\n> And do the math: if the object size is \n> 10-20% of the total allowed cache size, how many objects in the chain are \n> you going to fit in the cache?\n\nOnly 5 objects in the 20% case.  But as I say you could effectively have \nonly _one_ entry in the cache and it would still be 100% effective in \nthe single perfect delta chain I described above.\n\nOf course in practice there is more than a single delta chain, and the \ndelta direction might be the other way around.  But on _average_ it \nshould work fine pretty well.\n\nAnd notice how blobs are the first victims for cache eviction.  So for a \nmixed tree+blob usage case, if big blobs are to trash the cache, then \nwith LRU eviction performance should auto-regulate itself quite fine.  \nOf course a single blob might clear the cache entirely in the worst \ncase.  But there is a possibility that this big blob could be the base \nfor the next delta.  Adding a size treshold simply throw that \npossibility away in which case your performance will suffer _anyway_ \nbecause you'll experience the O(n**2) behavior with that delta chain of \nbig blobs.  Compared to that the lost cache of small objects won't even \nbe on the radar.  But if you let large objects reach the cache then \nthere is at least some possibility that those large objects might be the \nnext wanted delta base effectively saving big time on performance \nespecially if that base was itself a deep delta object.\n\nSo to resume:\n\n - the issue concerns only operations needing blob parsing\n\n - if large deltified blobs are denied the cache you will _always_ have\n   a sudden and drastic performance degradation when the size treshold \n   is crossed as the O(n**2) behavior on those big blob deltas will \n   dominate the profile\n\n - if you instead don't impose any treshold then performance will \n   degrade smoothly with object size down to the absolute worst case of \n   a single object in the cache, and for some cases it might even be \n   quite effective!\n\nI think it is therefore best to let the cache regulate itself with LRU \neviction than using arbitrary size treshold to segregate objects.  The \ncache will quickly repopulate itself if the big blob happens to be  an \nodd ball in a repository anyway.\n\n\nNicolas\n"}]}