7 ms·
Memory – Part 4: Intersec’s custom allocators
- cs648 13y agoVery interesting article, especially the t_scope allocator - I never knew you could get GCC to perform that cleanup automagically. One minor grammar point: isn't a lock under contention a contended lock, not a contented lock?
- fruneau 13y agoWording issue fixed.
- dman 13y agoIs the source for the allocators freely available? Would love to study those.
- fruneau 13y agoUnfortunately, not for the moment.
- aktau 13y agoI'd also like to put in a request for either open-sourcing or a more detailed overview of the implementations, they sound really interesting.
- fruneau 13y agoI'll consider writing a more detailed article on the subject. Open-sourcing the code will not be possible in the short-term.
- deletes 13y ago+1, for request of implementation details. I'm really curious about this.
- robjh 13y agoIn lieu of the implementation, I'd like to know if these allocators are themselves based on malloc or if you have some tricky assembly/kernel code going on somewhere.
- fruneau 13y agoThese allocators are based on mmap to build the arenas.
- epistasis 13y agoYes, I wish that cleanup was a portable C feature! Glad to see that GNU is trying something here, as it would serve as a prototype for standardization. Perhaps in a future version of C...
- qznc 13y agoThere is an extended version of C, which is has this feature and is nearly as widely ported as C. They aptly named it C++.
- epistasis 13y agoC++ has an IMHO worse version of this feature, that requires a custom type, and that only allows a single function to be called for that type. This is more like Go's defer, and is far more appropriate for my use cases.
- vidarh 13y agoI haven't written much C++ in quite a few years - mostly do Ruby these days, so I'm sure I'm making some terribly embarrassing faux pas or other with the example below. But you don't need more than the C++ functionality to compose your own variations if you want more flexibility. For example: #include <vector> #include <iostream> class Scope { private: typedef std::vector<void (*)()> FV; FV fv; public: void on_return(void (* f)()) { fv.push_back(f); } ~Scope() { for (FV::iterator it = fv.begin(); it != fv.end(); ++it) { (*it)(); } } }; void foo() { std::cout << "Hello "; } void bar() { std::cout << "World" << std::endl; } int main() { Scope scope; scope.on_return(foo); scope.on_return(bar); std::cout << "Hi" << std::endl; } With C++11 lambda syntax you can do quite a bit better. Expanding that into something providing at least most of what Go's "defer" does shouldn't be too hard.
- epistasis 13y agoGood idea, this definitely accomplishes the same functionality, but it's done at runtime, rather than the compiler knowing all the functions at compile time. Perhaps a minor difference for most cases, though... I would still prefer a C extension... Perhaps I should just use Go these days, though ironically all these memory allocation policies are useless in a GC language.
- exDM69 13y agoIt should be obvious that a lot of 8 byte mallocs will give bad performance and horrible memory use. This article and in particular the benchmarks in it would be a lot more informative if the test case was more realistic. Please add at least 32 or 64 bytes of payload to the linked list structure and re-run the benchmarks. Even that is a very small allocation block, but is on the lower end of realistic allocation sizes although not a good practice.
- barrkel 13y ago8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. IOW, you're angle is that instead of finding a solution to the problem, instead choose a different problem. You don't always have that luxury. My background on this problem is compilers. Compilers allocate lots of little structures that represent tree nodes, values, tokens, etc. Forcing them all to be a minimum of 32 or 64 bytes in size on the basis that would justify using malloc for them, would be more than a little bizarre. Arena allocation - both per module (for structures that need to persist for the whole compilation) and stack based (for structures that are discarded after e.g. evaluation or codegen) - makes far more sense than contorting the problem so that malloc makes sense.
- exDM69 13y ago> 8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. I guess if the objective of the article is to point out the obvious fact that mallocing 8 bytes at a time is a bad idea, then showing up some actual numbers from actual malloc implementations is a good idea. However, even small objects in practical problems are usually bigger than 8 bytes, so making the allocation size a bit bigger would give more realistic figures. Overall I think the article was informative and well written but more realistic test case would better point out when to write a custom allocator and what allocator to choose for a particular usage pattern.
- fruneau 13y ago
- eeadc 13y agoThe fact that returning memory to the Kernel is hard is supported by the circumstance, that most allocators will use brk/sbrk to resize the data segment of the executing process to allocate memory, at least if they shall allocate few memory. The other fact, that allocators have to lock global data structures is also not true. Most modern operating systems supports thread-local storage and therefore you don't need locking because you can keep much per-threads allocators, and only if you want to release memory of a foreign thread you have to lock (but that's also bad practice in most cases). Therefore, this article is great if your horizon end at the default allocators tcmalloc, ptmalloc and jemalloc, but the reality is much more complex. The fact that such a thing doesn't exists isn't founded in the fact that it's hard to implement, it's founded in the fact that there is no need for such an allocator, because most well-written software will allocate large chunks of memory.
- ori_b 13y ago> because most well-written software will allocate large chunks of memory. The average string length in most programs is about 5 to 10 bytes. Plenty of well written software works with strings like that.
- vidarh 13y ago> Most modern operating systems supports thread-local storage and therefore you don't need locking because you can keep much per-threads allocators The article explicitly points this out, and points out the problem with it: It means wasting memory on per-thread pools, and the more threads you use, the larger the pools needs to be if you want to prevent contention, compounding the problem. > because most well-written software will allocate large chunks of memory. 1. Most software is not well written. 2. Most large pieces well written pieces of software that allocates only large chunks of memory has some custom allocator of some sort (or horrible abuses of arrays) embedded somewhere to work around exactly the problems noted in the article. In many cases people end up wasting time writing the same types of specialised allocators over and over. I've seen plenty of large C and C++ apps that'd have benefitted greatly from a simple arena allocator for example... And I have also seen countless of implementations of arena allocators and various pool allocators and tons of other variations. In other words: These things do exist. They're common, to the point where they're often covered in books on C/C++. Especially for C++ where there is specific built in (though weak) support for custom allocators.
- dkhenry 13y agoI cannot for the life of me find this t_stack allocator he talks about. Anyone have a link ?
- vineel 13y agoIt's a custom allocator internal to Intersec.
- zwieback 13y agoReally interesting and well written, thanks for that. If you wrote some more about heap allocation strategies (best-fit, worst-fit, first-fit, etc.) to round out the discussion I'd love to read that as well, especially if you add varying allocation sizes to your benchmark.
- ArbitraryLimits 13y agoNot about heap allocators but I followed the "About" link to this text: > At Intersec, technology matters…Because it’s the core of our business, we aim to provide our clients with the most innovative and disruptive technological solutions. We do not believe in the benefits of reusing and staking external software bricks when developing our products. Our software is built in C language under Linux, with PHP/JavaScript for the web interfaces and it is continuously improved ... So now I'm wondering whether PHP is actually perceived as being hard-core? Also, how would one stake a brick?
- xamuel 13y agoC+PHP+Ajax(+SCGI or FastCGI) is my go-to when I want to create essentially a custom webserver but don't actually want to reinvent an entire http daemon from scratch. The PHP is used to simplify routine annoying tasks, while letting the custom server do the fun stuff.
- dexen 13y agoPHP can be thought of as ``configuration + templating language for your C application'', with the C application being both the http server, and stock and your custom PHP plugins. Yes, the whole stack can get hardcore, as long as you don't force PHP to do what other parts of the stack (SQL, JS) excel at, if you end up processing large datasets in short time :^)
- chris_wot 13y agoI think the really hard stuff isn't done via PHP. Seems to me they use PHP as the front end because they want to focus on their really valuable technology - their C code.
- fruneau 13y agoPHP is used as a small layer that enables talking to our C code from javascript. We have a custom (Protocol Buffer-like) protocol to manage our RPC, the PHP embeds a native module that implements that protocol and exposes a webservice to which our Javascript code can talk in order to provide some valuable user-experience on top of our C-written technologies. Nowadays there is so little intelligence in the PHP that we only consider it as a pass-through layer.
- blue11 13y agoSorry to nitpick, but I believe the time difference code has an error of 1 millisecond 25% of the time: int64_t delta = tv2->tv_sec - tv1->tv_sec; return delta * 1000 + (tv2->tv_usec - tv1->tv_usec) / 1000; One way to fix it is: int64_t deltasec = tv2->tv_sec - tv1->tv_sec - 1; int64_t deltausec = tv2->tv_usec - tv1->tv_usec + 1000000; return deltasec * 1000 + deltausec / 1000;
- fruneau 13y agoThe diff is a truncation. The actual error rate is 0.5ms on average. By using a round instead of truncation, we can reduce the error to 0.25ms on average.
- blue11 13y agoWell, that much is obvious. But if you are going to truncate, you should be consistent. Always truncate towards 0, not sometimes towards 0 and sometimes towards infinity.
- deweerdt 13y agoWhich version of jemalloc was used in the benchmark?
- fruneau 13y agojemalloc 3.4.0 (current package in debian sid)
- rayiner 13y agoThe thread test is janky. Most multithreaded allocators optimize for the (common) case that objects are freed by the same thread that creates them. When objects are freed by different threads than the ones that allocated them, typically some sort of slow-path is invoked. Older allocators with per-thread caches used to behave very badly with cross-thread frees, accumulating tons of freed objects in threads that didn't necessarily allocate a lot of objects. Tcmalloc uses a garbage collection process to move those objects back to the central free list. The test in the article, where one thread does all the allocations and another does all the frees, basically subverts the thread-caching in tcmalloc, and just tests how quickly the garbage collection process can move freed objects from the free()-thread's cache back to the central heap where they can be reused by the malloc()-thread.
- fruneau 13y agoI admit that test stress some corner cases (at least some cases that the allocator designer consider as corner cases). That said, malloc has no choice but supporting that use case. A use case for such pattern is a message-posting with workers: you queue some messages that are later unqueued and processed by a different thread. This is an increasingly common pattern in modern programs. In that pattern the message is allocated in one thread (let say the main one) and processed then deallocated by another thread. If your implementation of message allocation is malloc-based, then you will stress the exact same code paths the benchmark is stressing.
- JoachimSchipper 13y agoYou're not wrong that malloc-based message passing causes that load on malloc, but if performance of the message-passing code is important, you'd want to use a ring buffer anyway - cross-CPU or not, malloc is pretty slow.
- fruneau 13y agoClearly, we go back to the initial statement: for specific use cases, we need specific allocators.
- bd_at_rivenhill 13y agoIn thinking about the t_stack allocator, I think I can see some cases for which you might want to use this instead of the alloca function, but there is not enough information to be sure if I am going down the correct mental path. Can you please explain when/why I should use t_stack instead of alloca?
- professorTuring 13y agoIn fact, I was thinking of alloca the whole article and I really don't see the benefits of implementing a "custom solution" in detriment of a well working existing one. It would be great to compare the results they give against alloca =)
- fruneau 13y agoalloca has its drawbacks. See the previous article in the series: https://techtalk.intersec.com/2013/08/memory-part-3-managing-memory/#Stack https://techtalk.intersec.com/2013/08/memory-part-3-managing...
- fruneau 13y agoThere are two main issues with alloca: first you cannot deallocate or reallocate the memory, you just append more data to your frame. As a consequence, it is not suitable for dynamic allocations while the t_stack is. The second drawback is that alloca allocates on the stack, as a consequence it is limited by the size of the stack (a few megabytes on recent linux distribution, and the actual size of remaining stack depends on the callstack, since each frame consumes some stack and may have put huge buffers/alloca on it already). The t_stack has no hard-limit. Additionally, by being totally separated from the stack, the t_stack provides a flexible alternative to the stack: you have finer-grained control on allocation/deallocation patterns. As said in another comment, the drawbacks of alloca are explained in the previous article of the series.