\nA common performance trick is to reduce time spent in the heap manager\nby caching the last item freed (or maybe the last few)\nso that a subsequent allocation can just re-use the item rather\nthan having to go make a new one.\nBut you need to be careful how you do this or you can end up\nmaking things worse rather than better.\nHere’s an example motivated by\nan actual problem the Windows performance team researched.\n<\/p>\n
\nConsider a cache of variable-sized buffers.\nI will use only a one-entry cache for simplicity.\nIn real life, the cache would be more complicated:\nPeople tend to have a deeper cache of four to ten entries,\nand you would have to ensure that only\none thread used the cache at a time; typically this is done\nby associating the cache with something that has thread affinity.\nFurthermore, you probably would keep the size of the cached buffer\nin a member variable instead\nof calling \nIf a request for a memory buffer arrives and it can be\nsatisfied from the cache, then the cached buffer is returned.\nOtherwise, a brand new buffer is allocated.\n<\/p>\n \nWhen a buffer is returned to the cache, we compare it\nagainst the item already in the cache and keep the bigger\none, since that is more likely to satisfy a \nWhy is this a flawed design?\nI’ll let you think about this for a while.\n<\/p>\n \nNo really, I want you to think about it.\n<\/p>\n \nAre you thinking?\nTake your time; I’ll be here when you’re done.\n<\/p>\n \nOkay, since I know you haven’t actually thought about it but are\njust sitting there waiting for me to tell you,\nI’ll give you a bit of a nudge.\n<\/p>\n \nThe distribution of buffer sizes is rarely uniform.\nThe most common distribution is that small buffers are popular,\nwith larger and larger buffers being required less and less often.\nLet’s write a sample program that allocates and frees memory\naccording to this pattern.\nTo make the bad behavior easier to spot in a short run,\nI’m going to use a somewhat flat distribution and say that half\nof the buffers are small,\nwith larger buffers becoming less popular\naccording to exponential decay.\nIn practice, the decay curve is usually much, much steeper.\n<\/p>\n \nThis short program randomly allocates and frees memory\nfrom the buffer cache, printing (rather cryptically) the\nsize of the blocks allocated and freed.\nWhen memory is allocated, it prints “A1\/2” where “1” is the\nsize of the block actually allocated and “2” is the size requested.\nWhen freeing memory, it prints “F3” where “3” is the size of the\nblock allocated.\nRun this program, let it do its thing for maybe ten, fifteen\nseconds, then pause the output and study it.\nI’ll wait.\nIf you’re too lazy to actually compile and run the program,\nI’ve included some sample output for you to study:\n<\/p>\n \nStill waiting.\n<\/p>\n \nOkay, maybe you don’t see it. Let’s make the effect even more\nobvious by printing some statistics periodically.\nOf course, to generate the statistics, we need to keep track\nof them, so we’ll have to remember how big the requested buffer\nwas (which we’ll do in the buffer itself):\n<\/p>\n \nThis new version keeps track of how many bytes were allocated\nas opposed to how many were actually needed, and prints\na summary of those statistics every hundred allocations.\nSince I know you aren’t actually going to run it yourself,\nI’ve run it for you.\nHere is some sample output:\n<\/p>\n \nBy this point, the problem should be obvious:\nWe’re wasting insane quantities of memory.\nFor example, after step 37900, we’ve allocated 1.8MB\nof memory when we needed only 30KB,\nfor a waste of over 98%.\n<\/p>\n \nHow did we go horribly wrong?\n<\/p>\n \nRecall that most of the time, the buffer being allocated is\na small buffer, and most of the time, a small buffer is freed.\nBut it’s the rare case of a large buffer that messes up everything.\nThe first time a large buffer is requested, it can’t\ncome from the cache, since the cache has only small buffers,\nso it must be allocated.\nAnd when it is returned, it is kept, since the cache keeps\nthe largest buffer.\n<\/p>\n \nThe next allocation comes in, and it’s probably one of the common-case\nsmall buffers, and it is given the cached buffer—which is big.\nYou’re wasting a big buffer on something that needs only 100 bytes.\nSome time later, another rare big buffer request comes in,\nand since that other big buffer got wasted on a small allocation,\nyou have to allocate a new big buffer.\nYou allocated two big buffers even though you need only one.\nSince big buffers are rare, it is unlikely that a big buffer\nwill be given to a caller that actually needs<\/strong>\na big buffer; it is much more likely to be given to a caller\nthat needs a small buffer.\n<\/p>\n \nBad effect 1: Big buffers get wasted on small callers.\n<\/p><\/blockquote>\n \nNotice that once a big buffer enters the system,\nit is hard to get rid of,\nsince a returned big buffer will be compared against what\nis likely to be a small buffer,\nand the small buffer will lose.\n<\/p>\n \nBad effect 2: Big buffers rarely go away.\n<\/p><\/blockquote>\n \nThe only way a big buffer can get freed is if the\nbuffer in the cache is itself already a big buffer.\nIf instead of a one-entry cache like we have here,\nyou keep, say, ten buffers in your buffer cache,\nthen in order to free a big buffer, you have to have\neleven consecutive \nBad effect 3: The more efficient you try to make your\ncache, the more wasteful it gets!\n<\/p><\/blockquote>\n \nWhat’s more, when that eleventh call to \nBad effect 4: When a big buffer does go away,\nit’s only because you are keeping an even bigger buffer!\n<\/p><\/blockquote>\n \nCorollary: The biggest buffer never gets freed.\n<\/p><\/blockquote>\n \nWhat started out as an “obvious” decision in choosing\nwhich buffer to keep has turned into a performance disaster.\nBy favoring big buffers, you allowed them to “poison” the cache,\nand the longer you let the system run, the more allocations\nend up being big “poisoned” buffers.\nIt doesn’t matter how rare those big blocks are;\nyou will eventually end up in this state.\nIt’s just a matter of time.\n<\/p>\n \nWhen the performance team tries to explain this problem to people,\nmany of them get the mistaken impression that the problem is\nmerely that there is wasted space in the cache.\nBut look at our example:\nOur cache has only one entry and we are still wasting over 90%\nof the memory.\nThat’s because the waste is not in the memory being held by the\ncache, but rather is in the memory that the cache hands out<\/i>.\n(It’s sort of like that scene in It’s a Wonderful Life<\/i>\nwhere George Bailey is explaining where all the money is.\nIt’s not in the bank; it’s in all the places that got money from<\/i>\nthe bank.)\n<\/p>\n \nMy recommendations:\n<\/p>\n \nHere’s a new \nWith this one seemingly-minor change, our efficiency stays above 90%\nand occasionally even gets close to 100%:\n<\/p>\n \nDon’t forget to check out performance guru\n\nRico Mariani<\/a>‘s\nreminder that\n\nCaching implies Policy<\/a>.\nAs he explained to me,\n“Cache policy is everything\nso you must be dead certain that your policy is working as you intended.\nA cache with a bad policy is another name for a memory leak.”<\/p>\n","protected":false},"excerpt":{"rendered":" A common performance trick is to reduce time spent in the heap manager by caching the last item freed (or maybe the last few) so that a subsequent allocation can just re-use the item rather than having to go make a new one. But you need to be careful how you do this or you […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-31333","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":" A common performance trick is to reduce time spent in the heap manager by caching the last item freed (or maybe the last few) so that a subsequent allocation can just re-use the item rather than having to go make a new one. But you need to be careful how you do this or you […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/31333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=31333"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/31333\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=31333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=31333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=31333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}LocalSize<\/code> all the time.\nI’ve left out all these complications to keep the presentation simple.\n<\/p>\n\nclass BufferCache {\npublic:\n BufferCache() : m_pCache(NULL) { }\n ~BufferCache() { LocalFree(m_pCache); }\n void *GetBuffer(SIZE_T cb);\n void ReturnBuffer(void *p);\nprivate:\n void *m_pCache;\n};\n<\/pre>\n\nvoid *BufferCache::GetBuffer(SIZE_T cb)\n{\n \/\/ Satisfy from cache if possible\n if (m_pCache && LocalSize(m_pCache) >= cb) {\n void *p = m_pCache;\n m_pCache = NULL;\n return p;\n }\n return LocalAlloc(LMEM_FIXED, cb);\n}\n<\/pre>\nGetBuffer<\/code>\nin the future.\n(In the general case of a multiple-entry cache,\nwe would free the smallest entry.)\n<\/p>\n\n\/\/ Flawed design - see discussion\nvoid BufferCache::ReturnBuffer(void *p)\n{\n SIZE_T cb = LocalSize(p);\n if (!m_pCache || cb > LocalSize(m_pCache)) {\n \/\/ Returned buffer is bigger than the cache:\n \/\/ Keep the returned buffer\n LocalFree(m_pCache);\n m_pCache = p;\n } else {\n \/\/ Returned buffer is smaller than the cache:\n \/\/ Keep the cache\n LocalFree(p);\n }\n}<\/i>\n<\/pre>\n\n#include <vector>\n#include <iostream>\n\/\/ Since this is just a quick test, we're going to be sloppy\nusing namespace std; \/\/ sloppy\nint __cdecl main(int argc, char **argv)\n{\n BufferCache b;\n \/\/ seeding the random number generator is not important here\n vector<void *> v; \/\/ keeps track of allocated memory\n for (;;) {\n \/\/ randomly allocate and free\n if (v.size() == 0 || (rand() & 1)) { \/\/ allocate\n SIZE_T cb = 100;\n while (cb < 1024 * 1024 && (rand() & 1)) {\n cb *= 2; \/\/ exponential decay distribution up to 1MB\n }\n void* p = b.GetBuffer(cb);\n if (p) {\n cout << \" A\" << LocalSize(p) << \"\/\" << cb;\n v.push_back(p);\n }\n } else { \/\/ free\n int victim = rand() % v.size(); \/\/ choose one at random\n cout << \" F\" << LocalSize(v[victim]);\n b.ReturnBuffer(v[victim]); \/\/ free it\n v[victim] = v.back();\n v.pop_back();\n }\n }\n}\n<\/pre>\n\nF102400 A102400\/400 F800 F200 A800\/100 A200\/200 A400\/400\nA400\/400 A200\/200 F1600 A1600\/100 F100 F800 F25600 A25600\/200\nF12800 A12800\/200 F200 F400 A400\/100 F200 A200\/100 A200\/200\nA100\/100 F200 F3200 A3200\/400 A200\/200 F51200 F800 F25600\nF1600 F1600 A51200\/100 F100 A100\/100 F3200 F200 F409600 F100\nA409600\/400 A100\/100 F200 F3200 A3200\/800 A400\/400 F800 F3200\nF200 F12800 A12800\/200 A100\/100 F200 F25600 F400 F6400\nA25600\/100 F100 F200 F400 F200 F800 F400 A800\/800 A100\/100\n<\/pre>\n
\nint __cdecl main(int argc, char **argv)\n{\n BufferCache b;\n \/\/ seeding the random number generator is not important here\n vector<void *> v; \/\/ keeps track of allocated memory\n SIZE_T cbAlloc = 0, cbNeeded = 0;\n for (int count = 0; ; count++) {<\/font>\n \/\/ randomly allocate and free\n if (v.size() == 0 || (rand() & 1)) { \/\/ allocate\n SIZE_T cb = 100;\n while (cb < 1024 * 1024 && !(rand() % 4)) {\n cb *= 2; \/\/ exponential decay distribution up to 1MB\n }\n void* p = b.GetBuffer(cb);\n if (p) {\n *(SIZE_T*)p = cb;\n cbAlloc += LocalSize(p);\n cbNeeded += cb;<\/font>\n v.push_back(p);\n }\n } else { \/\/ free\n int victim = rand() % v.size(); \/\/ choose one at random\n cbAlloc -= LocalSize(v[victim]);\n cbNeeded -= *(SIZE_T*)v[victim];<\/font>\n b.ReturnBuffer(v[victim]); \/\/ free it\n v[victim] = v.back();\n v.pop_back();\n }\n if (count % 100 == 0) {\n cout << count << \": \" << v.size() << \" buffers, \"\n << cbNeeded << \"\/\" << cbAlloc << \"=\"\n << cbNeeded * 100.0 \/ cbAlloc << \"% used\" << endl;\n }<\/font>\n }\n}\n<\/pre>\n\n0: 1 buffers, 400\/400=100% used\n100: 7 buffers, 4300\/106600=4.03377% used\n200: 5 buffers, 1800\/103800=1.7341% used\n300: 19 buffers, 9800\/115800=8.46287% used\n400: 13 buffers, 5100\/114000=4.47368% used\n500: 7 buffers, 2500\/28100=8.8968% used\n...\n37200: 65 buffers, 129000\/2097100=6.15135% used\n37300: 55 buffers, 18100\/2031400=0.891011% used\n37400: 35 buffers, 10400\/2015800=0.515924% used\n37500: 43 buffers, 10700\/1869100=0.572468% used\n37600: 49 buffers, 17200\/1874000=0.917823% used\n37700: 75 buffers, 26000\/1889900=1.37573% used\n37800: 89 buffers, 30300\/1903100=1.59214% used\n37900: 91 buffers, 29600\/1911900=1.5482% used\n<\/pre>\n
ReturnBuffer<\/code> calls,\nall of which pass a big buffer.\n<\/p>\nReturnBuffer<\/code>\nis made with a big buffer, it is only the smallest of the\nbig buffers that gets freed.\nThe biggest buffers stay.\n<\/p>\n\n
ReturnBuffer<\/code> implementation that takes\nsome of the above advice into account.\nInstrumentation shows that three quarters of the allocations\nare in the 100–200 byte\nrange, so let’s cap our cache at 200 bytes.\n<\/p>\n\nvoid BufferCache::ReturnBuffer(void *p)\n{\n if (m_pCache == NULL && LocalSize(p) <= 200) {\n m_pCache = p;\n } else {\n LocalFree(p);\n }\n}\n<\/pre>\n\n0: 1 buffers, 400\/400=100% used\n100: 7 buffers, 4300\/4400=97.7273% used\n200: 5 buffers, 1800\/1800=100% used\n300: 19 buffers, 9800\/9800=100% used\n400: 13 buffers, 5100\/5100=100% used\n500: 7 buffers, 2500\/2600=96.1538% used\n...\n37200: 65 buffers, 129000\/130100=99.1545% used\n37300: 55 buffers, 18100\/18700=96.7914% used\n37400: 35 buffers, 10400\/11000=94.5455% used\n37500: 43 buffers, 10700\/11000=97.2727% used\n37600: 49 buffers, 17200\/18000=95.5556% used\n37700: 75 buffers, 26000\/26800=97.0149% used\n37800: 89 buffers, 30300\/31900=94.9843% used\n37900: 91 buffers, 29600\/30600=96.732% used\n<\/pre>\n