Memory – Part 4: Intersec’s custom allocators
techtalk.intersec.com
techtalk.intersec.com
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.
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.
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.
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.
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.
Also, the choice of lot of allocations + lot of deallocations pattern was chosen because this is an issue we ran into quite recently: we allocated a huge tree structure progressively and sometimes we flushed it to disk. The flush was quite efficient, but the deallocation blocked the program during approximatively 30s. As a quick fix, we put the deallocation in background, but this slowed the tree construction down by approximatively 50% because of the contention of the allocator. Even if the size of the chunks in the article were not realistic, the results were near-realistic enough to be considered publishable.
I provided (in a separate comment) the result of the benchmarks with a 32-bytes payload (in that benchmark, all the allocators had the same 12% overhead in term of memory, but we clearly see the same performance pattern as with the 8-bytes payload).
It's a little like those C programmers who try to use 256 byte static arrays for all their strings because they don't quite grok malloc/realloc.
But if I were writing a bigger application entirely in C/C++, I could totally see lots of small allocations happening at different points (and getting into wackiness with custom pooled allocators and auto_ptr).
Incidentally, good common case for 8-byte allocations that is actually common in real-world C code: 32 bit linked list nodes (4 bytes nextptr, 4 bytes dataptr).
Linked lists are bad because they have big overhead (8 bytes for every element in your case - which dominates by a large margin if you store an int in each node for example) and they are really bad for CPU caches (they have very little spatial locality), thus slowing down your code.
I much rather prefer the "growing array" approach.
As you say, most mallocs have this overhead. But with a bit of alignment trickery and bit masking you can put the header storage at the start of a page, bringing per-allocation overhead down to just a few bits.
Non-Contented test:
* ptmalloc: alloc 39M/s, free 49M/s
* tcmalloc: alloc 42M/s, free 40M/s
* jemalloc: alloc 21M/s, free 21M/s
* t_stack: alloc 110M/s
Contended test:
* ptmalloc: alloc 6.1M/s, free 6.4M/s
* tcmalloc: alloc 25M/s, free 11M/s
* jemalloc: alloc 18M/s, free 6.5M/s
Note that the results are less accurate that those provided in the article since the number of allocations per batch is smaller (due to the limited amount of RAM available on my desktop).
That's said, the article does not pretend benching realistic patterns.
This is more like Go's defer, and is far more appropriate for my use cases.
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;
}
Expanding that into something providing at least most of what Go's "defer" does shouldn't be too hard.
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.
#include <cstdio>
template <typename tFunc>
class ScopeFunc {
private:
tFunc mFunc;
public:
ScopeFunc(tFunc func) : mFunc(func) {}
~ScopeFunc() {
mFunc();
}
};
template <typename tFunc>
ScopeFunc<tFunc> on_return(tFunc func)
{
return ScopeFunc<tFunc>(func);
}
int main() {
auto first = on_return([]() { std::puts("first"); });
auto second = on_return([]() { std::puts("second"); });
std::puts("Hello");
}
It also optimizes nicely, which yours may not because the loop unrolling may be complicated and there's a higher chance of aliasing of the function pointers in the vector:
0000000000400600 <main>:
400600: 53 push %rbx
400601: bf e4 07 40 00 mov $0x4007e4,%edi
400606: e8 b5 ff ff ff callq 4005c0 <puts@plt>
40060b: bf ea 07 40 00 mov $0x4007ea,%edi
400610: e8 ab ff ff ff callq 4005c0 <puts@plt>
400615: bf f1 07 40 00 mov $0x4007f1,%edi
40061a: e8 a1 ff ff ff callq 4005c0 <puts@plt>
40061f: 31 c0 xor %eax,%eax
400621: 5b pop %rbx
400622: c3 retq int64_t delta = tv2->tv_sec - tv1->tv_sec;
return delta * 1000 + (tv2->tv_usec - tv1->tv_usec) / 1000;
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;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.
The average string length in most programs is about 5 to 10 bytes. Plenty of well written software works with strings like that.
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.
The other commonly used backend for malloc() is mmap() without underlying file:
void *chunk = mmap(NULL, length, PROT_READ|PROT_WRITE, MAP_ANONYMOUS, -1, 0);
> 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?
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 :^)
Nowadays there is so little intelligence in the PHP that we only consider it as a pass-through layer.
It would be great to compare the results they give against alloca =)
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.