Fewer mallocs in curl
daniel.haxx.se
daniel.haxx.se
Here's an old blog post describing it, by DHAT's author: https://blog.mozilla.org/jseward/2010/12/05/fun-n-games-with...
Here's another blog post in which I describe how I used it to speed up the Rust compiler significantly: https://blog.mozilla.org/nnethercote/2016/10/14/how-to-speed...
And here is the user manual: http://valgrind.org/docs/manual/dh-manual.html
...why is this the case?
The larger gain is explained better and comes simply from stack allocation of some structures (which live in a simple array, not a linked list or hash table).
I wonder why this wasn't the original design; I've seen the "two-allocate" method a few times in other code and it's always seemed rather silly to allocate that separate little structure just to point to the things you're linking together anyway, so I'm curious how that way of doing it became somewhat commonplace.
That use case is possible with the particular implementation that is now used by curl:
struct fileinfo {
struct curl_fileinfo info;
struct curl_llist_element list;
};
I think one of your other points is more likely, or simply "it was fast enough and we went for more interesting features than for such optimizations".
struct A {
int x, y;
};
struct B {
union {
struct A 2d;
struct { int x, y; };
}
int z;
};
...
struct B foo;
foo.x = foo.2d.y = foo.z = 0;
And when you have a memory overwrite then your meta data is corrupted and you loose the complete list. I keep my meta data and payload in two separate list for that very reason.
Arranging the code to "keep trucking" in case of spurious memory overwrites seems like setting it up to be hard to debug, and having programs run in some ill-defined state where some portion of data has been overwritten but nobody notices is just super-scary.
It's not every day that you see an example of someone examining and improving old code, that will result in a measurable benefit to direct and indirect users.
However, you lose 20 geek-points because FLAC and wav are not bit-to-bit identical. They are both lossless encodings and correct implementations will preserve the input material bit-to-bit.
In layman terms, it's like zipping and unzipping a .wav
One can say that FLAC is a lossless compression codec and as such it is homomorphic to the original raw binary encoding and the WAV encoding.
It might be pedantic, but saying "flac is bit-to-bit identical to wav" is just wrong. To me it sounds like saying: "The speed limit is 80 kilometers".
[0] http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012....
> also most players use malloc to get memory while new is the c++ method and sounds better.
Sidenote: "audio asylum", at least the name is appropriate, and it's https, I guess that's good too.
What's not cheap is requesting RAM from the OS piecemeal.
In this particular case the curl maintainer ended up saving a bit of RAM as a side-effect, but it's actually much more common for programs that benefit from this class of optimization to waste RAM as a side-effect, and yet be much faster.
For example a common optimization in high-level programming languages is to overallocate memory for strings. E.g. if the user requests "x" you allocate 16 bytes, if you need 17 bytes you allocate 32 etc.
This wastes RAM, a 513 byte string will malloc 1024 bytes, but ends up being much faster on overage exactly because RAM is cheap, but allocations are expensive.
the first time malloc() is invoked it will ask the OS for an oversized chunk of memory(probably using mmap() or sbrk())
allocations consist of incrementing a pointer, or pulling a a chunk off a freelist, both of which are effectively free
mmap() is very fast to call too, so I'm not sure what you're on about
regardless, curl is a piece of software that spends 99.99% of its time waiting for network traffic
> I'm not sure what you're on about.
> curl is a piece of software that spends 99.99%
> of its time waiting for network traffic.
libc is not the OS, it's the standard library for C, in the same way the java class library isn't the OS, it's the standard library for java
> once you remove two bottlenecks...
Yes, in a network library malloc overhead isn't usually a worthwhile thing to worry about, but libcurl is hardly just any random library.
> libc is not the OS, it's the standard library for C.
I was merely clarifying that in the context of my comment, which you replied to assuming I just meant the kernel, that I was talking about the C library as well.
FWIW lots of people use "Operating System" to mean the set of software you get by default. OpenBSD, GNU, OSX, Android etc. definitely consider libc to be part of the OS, and Android probably considers its java class library part of the base OS. If everyone meant "the kernel" by "the OS" we'd just say "the kernel".
You don't have to agree with that, but correcting people on that point is about as futile as trying to convince people that your use of "hacker" is correct.
that's what, 2 or 3 instructions? even if you push that upto a few hundred it's still effectively free compared to anything else curl is going to do (e.g. writing to the disk)
The allocation itself is not the bottleneck, it's the poor choice of data structure.
You'll spend 15 cycles doing work on 600 cycles of cache fetching. Plus you've just evicted some cache for your local scope.
But that said I would also keep in mind that `malloc` will generally be pretty fast - it's not going to hit up the OS every time you make a request. The advantage here isn't because `malloc` is slow, it is because copying is slow.
It'll take a bit longer (maybe 3-5x as long?) to write it to newly allocated memory (likely cache misses), the point is copying memory is just not as expensive as is often assumed.
I'm pretty sure malloc is the bottleneck in this case, pointer chasing is slow.
You also don't give enough weight to cache misses in this scenario. A L1 cache miss (So the memory is in L2) is going to be approximately a ~15x slow down from L1. A full main memory hit will be about ~200x slower. Not nearly the 3-5x you're guessing. More-over, the cache missing in `malloc` will likely be the same memory you're allocating anyway, meaning that the cache misses were likely going to happen regardless.
With that said, the `malloc` time should be somewhat constant regardless of the size of the allocation (Unless your allocation requires requesting memory from the OS), but the copying won't be. Once you start getting into structures that are fairly large in size, `malloc`ing new memory for them anytime you expand them will end-up being a fairly expensive operation that I would easily wager dwarfs any time spent in `malloc`.
But I mean, it's easy to argue basically any of these points without actual testing, so I've tried running a few basic tests on my own. Obviously your results would vary (I'm currently running on a fairly slow CPU):
First, I ran tests on different block sizes and number of allocations without freeing any of the allocated memory. In these tests, the copying tended to overshadow the allocations without copying when your block size was above around 8k. But because I wasn't calling `free`, allocating would quickly eat up most of the time if the number of allocations was increased (With most of the time being spent in the kernel). I did most of my tests with around the 40000 allocations, and above that things would get quite slow with the allocations alone even with block sizes larger then 8k.
With calling free, however, things tend to lean much more heavily in favor of the copying being more expensive. Right around a block size of 1k is where the allocation costs about the same time as the copy. The speed-up is of course due to `malloc` always have enough free memory available and not having to ask the OS for more (So this test represents the basic cost of the "pointer chasing" alone). Also, like I had assumed, the time for `malloc` without copying is 100% dependent on the number of allocations - changing the size of the block doesn't make any change to the time without copy.
Now that said, these tests are by no means definitive, but at the very least they do show that `malloc` is not necessarily expensive compared to the copying, especially once you go above a few k in your `malloc` size, and/or when the total number of allocations starts to ramp up very high. If your allocation size is fairly small though, then I would agree the `malloc` time is at least equivalent (or more) then the time spent copying.
"malloc" will need for the very least to keep lists of free areas and try to avoid virtual memory fragmentation. Fragmented heaps (="real life code" situation) are significantly slower than fresh clean heaps, because the are more allocation list entries to check.
Because amount of work malloc needs to do is variable, it's hard to give any numbers how long that pointer chasing operation will take.
Pointer chasing is slow, because non-sequential access patterns, such as following pointers, create a data dependency and cannot be prefetched. The CPU is likely to stall waiting for the dependency to be resolved. Typically each pointer dereferencing ("chasing") operation will also touch a different cache line, so cache misses are also common.
Synthetic tests are way more likely to reside in L1 cache (including allocation lists) than anything in real life.
Many malloc implementations mmap or equivalent allocations that exceed a certain threshold. In that case, copying is slow; you'll pay a lot extra for page faults during the copy. Page faults might also occur on a fresh heap in a synthetic test.
I know from personal experience lots of small size mallocs sometimes cause non-trivial performance issues.
Standard disclaimer concerning any optimizations: Always profile your code. Things work differently in real code than in benchmarks, and what was true last time in your real life scenario is no way guaranteed to be true next time.
It's even more impressive when you think about the absolute ubiquity of cURL in practically every device imaginable. He's probably single handedly saving many kilowatts of power consumption with fixes like this.
Your comment makes it sound like everyone should do this. Are there not reasons to have a non intrusive list as well? For example if the structure is used elsewhere and you don't want to tie it to that list implementation. Or if you want to point to the same structure many times in a list?
>"RAM is cheap"
Memory is cheap on servers and desktops. SSD can be treated as slow RAM.
For instance, a collection of Ts might want to have a list of the ones with property A and the ones with property B (independently, so any T could be on list A or B, or both, or neither). This could be done by having two std::list<std::shared_ptr<T>> (or something similar, like replacing the shared_ptrs with raw pointers, or indices into an external std::vector<House>), but this pays for the storage for each T, for the prev/next pointers, and also the storage for the pointer to the Houses (plus extra overhead of shared_ptr, etc.). With intrusive lists, one can have next_a/prev_a and next_b/prev_b pointers directly in the Ts and only pay that slight extra cost.
There's been talk of doing escape analysis for allocations on the mailing list, but so far nothing has been done as far as I know.
Anyway, the projects I mention above also define their own vectors.
> At this point I sorted all allocations based on size and checked all the smallest ones. One that stood out was one we made in curl_multi_wait(), a function that is called over and over in a typical curl transfer main loop. I converted it over to use the stack for most typical use cases. Avoiding mallocs in very repeatedly called functions is a good thing.
An example which I see all the time, looking at tons of python libraries which in the end do I/O against a TCP socket. Sometimes the representation between what the user passes to the library and what goes out to the socket can be retained as an array of buffers which are to be sent to the socket.
Instead of iterating on the array, and sending each block (if big enough) on it's own to the socket, the library author concat them to one buffer, and then send it over the socket.
When dealing with big data, this adds lots of fragmentation and overhead (measurable), yet some library authors don't care...
Even the basic httplib and requests has this issue when sending via POST a large file (it concats it to the header, instead of sending the header, then the large fiel).
Also - are you utterly certain your allocations will always be small? Could someone craft some input to your program to have you allocate more, and possibly use up the stack in some environments? There's environments which have much smaller stacks than have RAM available.
size_t example(const char in, const size_t in_size, char out, const size_t max_out_size)
{
size_t out_size = 0;
char stack_buf[32768];
char *buf = stack_buf;
char *heap_buf = NULL;
size_t req_size = in_size * 2;
if (req_size < sizeof(stack_buf)) {
buf = heap_buf = (char *)malloc(req_size);
}
// Do stuff
if (heap_buf) {
free(heap_buf);
}
return out_size;
}if (req_size < sizeof(stack_buf))
Should be:
if (req_size > sizeof(stack_buf))
size_t example(const char in, const size_t in_size, char out, const size_t max_out_size)
{
size_t out_size = 0;
char stack_buf[32768];
char *buf = stack_buf;
char *heap_buf = NULL;
size_t req_size = in_size * 2;
if (req_size < sizeof(stack_buf)) {
buf = heap_buf = (char *)malloc(req_size);
}
// Do stuff
if (heap_buf) {
free(heap_buf);
}
return out_size;
}Don't use a tree in that case? I don't see why you using a tree to store allocation info means that allocations are slow.
That not necessarily true. Modern allocators tend to use a bunch of fixed size-buckets.
But given that curl runs on lots of platforms it makes sense to just fix the code.
Moreover, the cache hit you take for an alloc likely would have happened anyways because, presumably, the program that made the allocation wants to write to the allocated memory (in theory, that doesn't imply the CPU has to _read_ the memory, but are there allocators that are that smart?)
For frees, the memory may, but need not be, already be in the cache when free is called.
Edit: I would also be tempted to remove the ufds_on_stack variable and just check if the ufds pointer points to the stack or not.
(Of course, he could get rid of "bool ufds_malloc" and just see if his pointer is NULL before calling free(); or not even bother checking, since free(NULL) is defined to be a no-op.)
Normal C caveats do apply here though: alloca is POSIX, not C (but is widely implemented outside of POSIX systems). VLAs are an optional standard feature. Neither is required to actually use the stack for storage.
Not sure if there are any platforms supported by curl which would prevent it's use of VLAs or alloca.
Alloca is somewhat more expensive on x86/x64 than a single instruction.
[0] shows the code generation for four functions that generate and sum an iota array. I used -O1 to make the differences more apparent.
iota_sum_alloca and iota_sum_vla generate similar code. They both require a frame pointer (RBP) and code to preserve the 16 byte alignment of the stack frame.
iota_sum_const_alloca and iota_sum_array generate identical code. Clang recognizes that alloca is invoked with a constant argument.
History of Alloca
Alloca was originally written for unix V7 [1]. Doug Gwyn wrote a public domain implementation [2] in the early 80s for porting existing programs. The FSF used Gwyn's alloca implementation in GDB, Emacs, and other programs. This helped to spread the idea.
Problems of Alloca
[3] is a comp.compilers thread that discusses some of the issues with alloca. Linus does not want either VLAs or alloca in the Linux kernel [4].
References:
[0] https://godbolt.org/g/1JyXhQ
[1] http://yarchive.net/comp/alloca.html
[2] https://github.com/darchons/android-gdb/blob/android-gdb_7_5...
[3] http://compilers.iecc.com/comparch/article/91-12-079
[4] https://groups.google.com/forum/#!msg/fa.linux.kernel/ROgkTB...
Edited for minor formatting changes.
If you compile with -O2 then iota_sum_const_alloca and iota_sum_array are both evaluated at compile time.
A similar option is a variable-length array, which is standard C. It does share the problem of not being available in some compilers, however.
That said, there are other problems with alloca/VLAs. For small enough sizes, like you said it's faster and simpler to statically allocate. For large enough sizes, you risk overflowing the stack, which might be more constrained than you'd expect (especially when using threads). There might be a sweet spot where it's better, but it's not worth the portability cost and the potential headaches.
Does anyone have a general sense of how these kinds of efficiencies translate to real-world battery life? I understand that the mechanisms (downclocking/sleeping the CPU) are there; I'm just curious as to how much it actually moves the needle in a real system.
Downclocking has negative impact because the CPU needs to be powered up longer and it is leaking current all the time it is not powergated.
"I can't think of any" is not a very scientific way to measure optimizations. Actually, this simple fact casts a doubt on whether it's this malloc optimization that led to the speed up or any of the 200+ commits OP is working on top of.
Why not eliminate that doubt by applying the malloc optimizations to the previous official release? I'm a bit skeptical about the speed up myself, since I would expect curl to be primarily IO bound and not CPU bound (much less malloc bound, given how little memory it uses).
For this function, a list of elements was kept inside each call, which began empty and a few calculations where performed, populating it before the main loop of the function kicked in. In python-land, this was obviously done by declaring an empty list `precalc_values = []` and then appending over it. When we cythonized it, the dev that took it went in with a `cy_malloc(size(int)*elements)` "dynamic array of ints", and called it a day, 70x speedup over plain python.
A few days later I came in and saw that code, and said "why not go with a simple array?", to which I was told "because we don't know the size of the strings beforehand". Did a test run with a small array plus a counter (to know up to where the array held real values, and not just zero-init fields) and got a 100x speedup.
In the end we went with both functions and a wrapper that would check the length of the strings involved and select one or the other, because the array version would massively crash from accessing an array out of bounds if a large string happened to come by.
> converted to become malloc-less (the way
> linked list functions should behave, really).
I don't see how a linked list can not use malloc().
You are "polluting" your payload with list information, but you gain malloc less lists.
2GB