11 ms·

Fewer mallocs in curl

392 points by dosshell 9y ago

makerbraker 9y ago
I think this is fantastic engineering work towards performance, without falling back on the "RAM is cheap" line and instead doing nothing. 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.
- throwanem 9y ago
  Also, when you download FLAC files with it, they'll sound warmer.
  - nayuki 9y ago
    There is actually a corner on the web where people debate about FLACs and WAVs sounding different
    - user5994461 9y ago
      That's fun considering they are bit-to-bit identical :D
      - edejong 9y ago
        Yes, you got the pun, bravo, 2 geek-points for you. 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.
        bcook 9y ago
        Perhaps he's referring the the bits sent out from the codec rather than the bits received by the codec?
        user5994461 9y ago
        FLAC is bit to bit identical to WAV after decoding. In layman terms, it's like zipping and unzipping a .wav
        edejong 9y ago
        Yes, I understand how the FLAC codec works. My comment was pointing out that FLAC can either represent the codec or the binary and that in neither case one can say that FLAC is bit-to-bit identical, since in the former case you're referring to the specification and in the latter case you are referring to the binary executable. 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".
    - lucideer 9y ago
      This is probably true in non-blind listening comparison though. Similar to food tasting different when served in different coloured receptacles[0] [0] http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012.00397.x/abstract http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012....
      - mikeash 9y ago
        If you had to summarize the audiophile community in a few words, it would be "does not understand the point of blind testing."
        venture_lol 9y ago
        All audophiles eventually will reach the stage where my hearing aid is better than yours :)
        deleted 9y ago
        [deleted]
        mikeass 9y ago
        That's terribly judgmental, friend.
        sctb 9y ago
        We've banned this account and the main one for repeatedly violating the guidelines and creating new accounts to do so.
    - nayuki 9y ago
      For example: http://forums.naimaudio.com/topic/flac-vs-wav-audio-quality http://forums.naimaudio.com/topic/flac-vs-wav-audio-quality
  - Cyph0n 9y ago
    Especially when played over my diamond coated high fidelity wires. I'll probably pair that with my fully 24K gold HDMI cables when watching a movie.
  - noway421 9y ago
    Disagree, they sounds the best with wget.
    - tehabe 9y ago
      You've never experienced FLACs downloaded via scp. The encryption makes all the difference.
      - reinhardt1053 9y ago
        Is this reddit?
        mfukar 9y ago
        What is the difference?
        throwanem 9y ago
        Worth preserving.
    - venture_lol 9y ago
      You know all those memory sloshing around does create a different sound stage, rippling contextual frequencies affecting DACs and such?
  - Rusky 9y ago
    https://www.audioasylum.com/messages/pcaudio/119979/re-a-revolution-in-audio-rendering https://www.audioasylum.com/messages/pcaudio/119979/re-a-rev... > also most players use malloc to get memory while new is the c++ method and sounds better.
    - jrimbault 9y ago
      This is a new rabbit hole of "audiophile". Sidenote: "audio asylum", at least the name is appropriate, and it's https, I guess that's good too.
- avar 9y ago
  RAM is cheap. 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.
  - blibble 9y ago
    it doesn't go to the OS each time you call malloc() 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
    - avar 9y ago
      > I'm not sure what you're on about. You clearly interpreted OS to mean "the kernel" in my comment. To be clear I'm including the C library which implements malloc() in "the OS". > curl is a piece of software that spends 99.99% > of its time waiting for network traffic. You're commenting on an article that shows that in some cases 30% of the time was spent on malloc() overhead.
      - pjmlp 9y ago
        Which C library from which C compiler?
      - blibble 9y ago
        well yes, they removed the network overhead and disk overhead by running it on localhost and writing to /dev/null, and once you remove two bottlenecks you'll find that something else becomes the new bottleneck 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
- aphextron 9y ago
  >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. 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.
- srean 9y ago
  Indeed. Roadways are cheap to use but those who behave as if its all theirs are still called dicks for a reason.
- lkjalsdkfjasdf 9y ago
  This only shows the naivete of the author. There are plenty of C programmers that aren't malloc abusers and like to avoid any potential syscall usage. Instrusive linked lists is a beginner C topic.
  - circular_logic 9y ago
    I'm a C beginner so I found it quite useful. ;) 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?
- ed_balls 9y ago
  This is a completely different scenario than an average app. Curl is used in cars and other embedded devices. This things matter for this scale. >"RAM is cheap" Memory is cheap on servers and desktops. SSD can be treated as slow RAM.
rumcajz 9y ago
My rule of thumb is to look at application's design and only ever use malloc where there is 1:N (or N:M) relationship between entities. Everything that's 1:1 should be allocated in a single step.
- areyousure 9y ago
  Your heuristic sounds interesting. Can you say a little more about which entities and how to determine their relationship? Thanks.
- maccard 9y ago
  Weve had data that was fixed size but wouldn't fit on the stack.
snksnk 9y ago
Optimization backed by comparative statics. These reads are so satisfying. Thank you for submitting.
deleted 9y ago
[deleted]
tom_mellior 9y ago
For the benefit of others who found the description in the blog post unclear and can't or don't want to dig through the code changes themselves: "fixing the hash code and the linked list code to not use mallocs" is a bit misleading. Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload. So it's one malloc instead of two per dynamically allocated list element. This explains the "down to 80 allocations from the 115" part. 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).
- dom0 9y ago
  AKA intrusive (sometimes "invasive") containers / lists.
- userbinator 9y ago
  Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload. 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.
  - masklinn 9y ago
    Mayhaps because the structure was originally stack-allocated, or because the developer was unfamiliar or uncomfortable with intrusive datastructures. Or because the structure is used outside of linked list contexts and the memory overhead of the intrusion was considered not compensated for?
    - tom_mellior 9y ago
      > Or because the structure is used outside of linked list contexts 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; }; You can use the payload (struct curl_fileinfo) outside of a list without incurring any overhead. 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".
vertex-four 9y ago
Note that this pattern[0] is essentially "copy-on-write", which can be encapsulated safely as such in a reasonably simple type (in a language with generics) and used elsewhere. I use a similar mechanism pervasively in some low-level web server code to use references into the query string, body and JSON objects directly when possible, and allocated strings when not. [0] https://github.com/curl/curl/commit/5f1163517e1597339d https://github.com/curl/curl/commit/5f1163517e1597339d
- Asooka 9y ago
  But why not use alloca instead of always allocating 10 elements on the stack you might not need? 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.
  - drfuchs 9y ago
    Because always allocating them on the stack costs zero cycles in the typical case, while alloca costs more than zero cycles in the typical case. And assuming that "struct pollfd" isn't big, and the function isn't very recursive, there's no practical downside to wasting a little stack space for the life of the function. (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.)
    - codyps 9y ago
      `alloca` is a simple addition to the stack pointer, so a single instruction, presuming it isn't folded into the normal bump of the stack pointer to allocate the fixed size local variables. There isn't really much cost to doing a dynamic stack allocation rather than a fixed one. Variable length arrays (VLAs) allow the same thing but can be slightly more portable. 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.
21 9y ago
> Doing very small (less than say 32 bytes) allocations is also wasteful just due to the very large amount of data in proportion that will be used just to keep track of that tiny little memory area (within the malloc system). Not to mention fragmentation of the heap. 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.
- __s 9y ago
  & often those fixed-size buckets smallest size is 32 bytes. It still has to at least have a freelist
  - notacoward 9y ago
    There has to be a free list somewhere, but a single bucket only needs a bitmap. I think the GP's point is that such a structure amortizes the cost of the free-list metadata over more items, reducing total overhead.
    - 21 9y ago
      The free list can be stored inside the empty cells, meaning you put the pointer to the next empty cell inside the previous empty cell, and you need a single additional pointer to store the location of the first empty cell. When you free a cell you just make that the first empty cell.
      - exDM69 9y ago
        This isn't free either because the free list is scattered around in memory and all that pointer chasing is bad for caches.
        dbaupp 9y ago
        I'm curious if any allocators with size classes/buckets actually do much pointer chasing. One can theoretically have a free-list for each class, so at most one pointer needs to be dereferenced: work out the size class, load the front of the appropriate list, read its tail pointer and store that as the new front of the list.
0xcde4c3db 9y ago
> The point is rather that curl now uses less CPU per byte transferred, which leaves more CPU over to the rest of the system to perform whatever it needs to do. Or to save battery if the device is a portable one. 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.
- maccard 9y ago
  Not sure in hard numbers, but mobile processors are designed to work this way - do a small amount of work at full power and then sleep.
  - zkms 9y ago
    Race to idle~
- 59nadir 9y ago
  In any one single instance it's not that interesting, but considering probably half (if not more) of the stuff you interact with uses libcurl, it adds up to a lot.
- exDM69 9y ago
  30℅ less CPU use is roughly 30℅ less energy usage. The CPU will power down when it's done. 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.
__s 9y ago
> The point here is of course not that it easily can transfer HTTP over 20GB/sec using a single core on my machine 2GB
- fastest963 9y ago
  He said gigabit, or at least that's how I read it. 2900MB/sec * 8 is over 20gb/s
ape4 9y ago
> This time the generic linked list functions got > 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().
- rumcajz 9y ago
  Look for intrusive containers.
  - ape4 9y ago
    TIL, thanks.
- hota_mazi 9y ago
  Have each node of data contain the `prev` and `next` link. You are "polluting" your payload with list information, but you gain malloc less lists.
  - Someone 9y ago
    And cache locality. That can have considerable impact if you frequently search that list for an item satisfying some condition.
hota_mazi 9y ago
> There have been 213 commits in the curl git repo from 7.53.1 till today. There’s a chance one or more other commits than just the pure alloc changes have made a performance impact, even if I can’t think of any. "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).
- dr_zoidberg 9y ago
  I'm not skeptical about it. Last time I did something similar to this optimization, I had a python function that was doing some work over strings to get a similarity metric. 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.
faragon 9y ago
Explicit dynamic memory handling in low level languages hurts in a similar way garbage collectors do in high level languages: hidden and often unpredictable execution costs (malloc/realloc/free internally usually implement O(n log n) algorithms, or worse). So the point for performance, no matter if you work with low level or high level languages is to use preallocated data structures, when possible. That way you'll have low fragmentation and fast execution because not calling the allocator/dealocator in the case of explicit dynamic memory handling, and lower garbage collector pressure because of the same reasons in the case of a garbage-collected languages.
- maccard 9y ago
  An allocator doesn't have to be slow. You can implement allocator yourself that asks for memory from the OS up front, and just hands pointer back to the caking application. If you know the order of allocations is the reverse of the deallocstiond (as an example) you can do allocations with a pointer bump!
  - faragon 9y ago
    Sure. Imagine you have a process with 2^20 active allocations (e.g. 2^20 calls to malloc()), i.e. you have a tree with the metainformation, and every time you de-allocate and allocate you have to search trough one or more trees. So no matter how "smart" is your library for avoiding OS system calls, you already have a hell to maintain (search through a tree or a list, delete, split, etc.). Things get ugly when a process has lots of dynamic memory calls, on non-trivial cases.
    - vertex-four 9y ago
      An alternative, if you have a well-defined portion of code by the end of which you know you're not going to touch any data which was allocated in it, is to use arenas - allocation is then a pointer bump, and you can deallocate all of it at once.
      - faragon 9y ago
vbezhenar 9y ago
Underlying problem is that C doesn't have comprehensive standard collections, so many developers reinvent the wheel over and over again, and usually that wheel is far from best in the world. If curl was written with C++, those optimizations would be applied automatically by using STL collections.
- wolf550e 9y ago
  He turned his containers into intrusive ones. The standard C++ STL containers are not intrusive. Boost comes with intrusive containers, but if you need a third party library, you can do that in C too.
  - dbaupp 9y ago
    They have many of the same properties as being intrusive, e.g. one can write a list type that can store any type and store it directly inline next to the next/previous pointers, not needing an allocation like the common C strategy of using void*.
  - eropple 9y ago
    What, in your view, is meaningfully different between an intrusive container and std::list allocating memory right next to the prev/next pointers for your data?
    - dbaupp 9y ago
      For data in a single list, they're essentially equivalent, but they differ when one wants to put things in multiple lists. 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.
iamalurker 9y ago
My problem with excessive allocations is usually what happens in interpreted languages. People think, hey it's already slow ass interpreted so lets not care about allocation at all. 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).
nnethercote 9y ago
There is a little-known Valgrind tool called "DHAT" (short for "Dynamic Heap Analysis Tool") that's designed to help find exactly these sorts of excessive allocations. Here's an old blog post describing it, by DHAT's author: https://blog.mozilla.org/jseward/2010/12/05/fun-n-games-with-dhat/ 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-up-the-rust-compiler/ 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 http://valgrind.org/docs/manual/dh-manual.html
- wyldfire 9y ago
  > I previously had -Ccodegen-units=8 in RUSTFLAGS because it speeds up compile times. ... the resulting rustc was about 5–10% slower. So I’ve stopped using it now. ...why is this the case?
  - detaro 9y ago
    It breaks the code into smaller modules that are processed independently, thus limiting the scope of optimizations to those modules.
amenghra 9y ago
You would think curl's perf is bound by the network latency/bandwidth and that intrusive lists wouldn't make a signifiant difference.

392 points by dosshell 9y ago

I think this is fantastic engineering work towards performance, without falling back on the "RAM is cheap" line and instead doing nothing. 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.

throwanem 9y ago
Also, when you download FLAC files with it, they'll sound warmer.
- nayuki 9y ago
  There is actually a corner on the web where people debate about FLACs and WAVs sounding different
  - user5994461 9y ago
    That's fun considering they are bit-to-bit identical :D
    - edejong 9y ago
      Yes, you got the pun, bravo, 2 geek-points for you. 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.
      - bcook 9y ago
        Perhaps he's referring the the bits sent out from the codec rather than the bits received by the codec?
      - user5994461 9y ago
        FLAC is bit to bit identical to WAV after decoding. In layman terms, it's like zipping and unzipping a .wav
        edejong 9y ago
        Yes, I understand how the FLAC codec works. My comment was pointing out that FLAC can either represent the codec or the binary and that in neither case one can say that FLAC is bit-to-bit identical, since in the former case you're referring to the specification and in the latter case you are referring to the binary executable. 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".
  - lucideer 9y ago
    This is probably true in non-blind listening comparison though. Similar to food tasting different when served in different coloured receptacles[0] [0] http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012.00397.x/abstract http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012....
    - mikeash 9y ago
      If you had to summarize the audiophile community in a few words, it would be "does not understand the point of blind testing."
      - venture_lol 9y ago
        All audophiles eventually will reach the stage where my hearing aid is better than yours :)
      - deleted 9y ago
        [deleted]
      - mikeass 9y ago
        That's terribly judgmental, friend.
        sctb 9y ago
        We've banned this account and the main one for repeatedly violating the guidelines and creating new accounts to do so.
  - nayuki 9y ago
    For example: http://forums.naimaudio.com/topic/flac-vs-wav-audio-quality http://forums.naimaudio.com/topic/flac-vs-wav-audio-quality
- Cyph0n 9y ago
  Especially when played over my diamond coated high fidelity wires. I'll probably pair that with my fully 24K gold HDMI cables when watching a movie.
- noway421 9y ago
  Disagree, they sounds the best with wget.
  - tehabe 9y ago
    You've never experienced FLACs downloaded via scp. The encryption makes all the difference.
    - reinhardt1053 9y ago
      Is this reddit?
      - mfukar 9y ago
        What is the difference?
        throwanem 9y ago
        Worth preserving.
  - venture_lol 9y ago
    You know all those memory sloshing around does create a different sound stage, rippling contextual frequencies affecting DACs and such?
- Rusky 9y ago
  https://www.audioasylum.com/messages/pcaudio/119979/re-a-revolution-in-audio-rendering https://www.audioasylum.com/messages/pcaudio/119979/re-a-rev... > also most players use malloc to get memory while new is the c++ method and sounds better.
  - jrimbault 9y ago
    This is a new rabbit hole of "audiophile". Sidenote: "audio asylum", at least the name is appropriate, and it's https, I guess that's good too.
avar 9y ago
RAM is cheap. 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.
- blibble 9y ago
  it doesn't go to the OS each time you call malloc() 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
  - avar 9y ago
    > I'm not sure what you're on about. You clearly interpreted OS to mean "the kernel" in my comment. To be clear I'm including the C library which implements malloc() in "the OS". > curl is a piece of software that spends 99.99% > of its time waiting for network traffic. You're commenting on an article that shows that in some cases 30% of the time was spent on malloc() overhead.
    - pjmlp 9y ago
      Which C library from which C compiler?
    - blibble 9y ago
      well yes, they removed the network overhead and disk overhead by running it on localhost and writing to /dev/null, and once you remove two bottlenecks you'll find that something else becomes the new bottleneck 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
aphextron 9y ago
>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. 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.
srean 9y ago
Indeed. Roadways are cheap to use but those who behave as if its all theirs are still called dicks for a reason.
lkjalsdkfjasdf 9y ago
This only shows the naivete of the author. There are plenty of C programmers that aren't malloc abusers and like to avoid any potential syscall usage. Instrusive linked lists is a beginner C topic.
- circular_logic 9y ago
  I'm a C beginner so I found it quite useful. ;) 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?
ed_balls 9y ago
This is a completely different scenario than an average app. Curl is used in cars and other embedded devices. This things matter for this scale. >"RAM is cheap" Memory is cheap on servers and desktops. SSD can be treated as slow RAM.

rumcajz 9y ago

My rule of thumb is to look at application's design and only ever use malloc where there is 1:N (or N:M) relationship between entities. Everything that's 1:1 should be allocated in a single step.

areyousure 9y ago
Your heuristic sounds interesting. Can you say a little more about which entities and how to determine their relationship? Thanks.
maccard 9y ago
Weve had data that was fixed size but wouldn't fit on the stack.

snksnk 9y ago

Optimization backed by comparative statics. These reads are so satisfying. Thank you for submitting.

deleted 9y ago

[deleted]

tom_mellior 9y ago

For the benefit of others who found the description in the blog post unclear and can't or don't want to dig through the code changes themselves: "fixing the hash code and the linked list code to not use mallocs" is a bit misleading. Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload. So it's one malloc instead of two per dynamically allocated list element. This explains the "down to 80 allocations from the 115" part. 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).

dom0 9y ago
AKA intrusive (sometimes "invasive") containers / lists.
userbinator 9y ago
Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload. 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.
- masklinn 9y ago
  Mayhaps because the structure was originally stack-allocated, or because the developer was unfamiliar or uncomfortable with intrusive datastructures. Or because the structure is used outside of linked list contexts and the memory overhead of the intrusion was considered not compensated for?
  - tom_mellior 9y ago
    > Or because the structure is used outside of linked list contexts 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; }; You can use the payload (struct curl_fileinfo) outside of a list without incurring any overhead. 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".

vertex-four 9y ago

Note that this pattern[0] is essentially "copy-on-write", which can be encapsulated safely as such in a reasonably simple type (in a language with generics) and used elsewhere. I use a similar mechanism pervasively in some low-level web server code to use references into the query string, body and JSON objects directly when possible, and allocated strings when not. [0] https://github.com/curl/curl/commit/5f1163517e1597339d https://github.com/curl/curl/commit/5f1163517e1597339d

Asooka 9y ago
But why not use alloca instead of always allocating 10 elements on the stack you might not need? 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.
- drfuchs 9y ago
  Because always allocating them on the stack costs zero cycles in the typical case, while alloca costs more than zero cycles in the typical case. And assuming that "struct pollfd" isn't big, and the function isn't very recursive, there's no practical downside to wasting a little stack space for the life of the function. (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.)
  - codyps 9y ago
    `alloca` is a simple addition to the stack pointer, so a single instruction, presuming it isn't folded into the normal bump of the stack pointer to allocate the fixed size local variables. There isn't really much cost to doing a dynamic stack allocation rather than a fixed one. Variable length arrays (VLAs) allow the same thing but can be slightly more portable. 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.

21 9y ago

> Doing very small (less than say 32 bytes) allocations is also wasteful just due to the very large amount of data in proportion that will be used just to keep track of that tiny little memory area (within the malloc system). Not to mention fragmentation of the heap. 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.

__s 9y ago
& often those fixed-size buckets smallest size is 32 bytes. It still has to at least have a freelist
- notacoward 9y ago
  There has to be a free list somewhere, but a single bucket only needs a bitmap. I think the GP's point is that such a structure amortizes the cost of the free-list metadata over more items, reducing total overhead.
  - 21 9y ago
    The free list can be stored inside the empty cells, meaning you put the pointer to the next empty cell inside the previous empty cell, and you need a single additional pointer to store the location of the first empty cell. When you free a cell you just make that the first empty cell.
    - exDM69 9y ago
      This isn't free either because the free list is scattered around in memory and all that pointer chasing is bad for caches.
      - dbaupp 9y ago
        I'm curious if any allocators with size classes/buckets actually do much pointer chasing. One can theoretically have a free-list for each class, so at most one pointer needs to be dereferenced: work out the size class, load the front of the appropriate list, read its tail pointer and store that as the new front of the list.

0xcde4c3db 9y ago

> The point is rather that curl now uses less CPU per byte transferred, which leaves more CPU over to the rest of the system to perform whatever it needs to do. Or to save battery if the device is a portable one. 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.

maccard 9y ago
Not sure in hard numbers, but mobile processors are designed to work this way - do a small amount of work at full power and then sleep.
- zkms 9y ago
  Race to idle~
59nadir 9y ago
In any one single instance it's not that interesting, but considering probably half (if not more) of the stuff you interact with uses libcurl, it adds up to a lot.
exDM69 9y ago
30℅ less CPU use is roughly 30℅ less energy usage. The CPU will power down when it's done. 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.

__s 9y ago

> The point here is of course not that it easily can transfer HTTP over 20GB/sec using a single core on my machine 2GB

fastest963 9y ago
He said gigabit, or at least that's how I read it. 2900MB/sec * 8 is over 20gb/s

ape4 9y ago

> This time the generic linked list functions got > 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().

rumcajz 9y ago
Look for intrusive containers.
- ape4 9y ago
  TIL, thanks.
hota_mazi 9y ago
Have each node of data contain the `prev` and `next` link. You are "polluting" your payload with list information, but you gain malloc less lists.
- Someone 9y ago
  And cache locality. That can have considerable impact if you frequently search that list for an item satisfying some condition.

hota_mazi 9y ago

> There have been 213 commits in the curl git repo from 7.53.1 till today. There’s a chance one or more other commits than just the pure alloc changes have made a performance impact, even if I can’t think of any. "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).

dr_zoidberg 9y ago
I'm not skeptical about it. Last time I did something similar to this optimization, I had a python function that was doing some work over strings to get a similarity metric. 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.

faragon 9y ago

Explicit dynamic memory handling in low level languages hurts in a similar way garbage collectors do in high level languages: hidden and often unpredictable execution costs (malloc/realloc/free internally usually implement O(n log n) algorithms, or worse). So the point for performance, no matter if you work with low level or high level languages is to use preallocated data structures, when possible. That way you'll have low fragmentation and fast execution because not calling the allocator/dealocator in the case of explicit dynamic memory handling, and lower garbage collector pressure because of the same reasons in the case of a garbage-collected languages.

maccard 9y ago
An allocator doesn't have to be slow. You can implement allocator yourself that asks for memory from the OS up front, and just hands pointer back to the caking application. If you know the order of allocations is the reverse of the deallocstiond (as an example) you can do allocations with a pointer bump!
- faragon 9y ago
  Sure. Imagine you have a process with 2^20 active allocations (e.g. 2^20 calls to malloc()), i.e. you have a tree with the metainformation, and every time you de-allocate and allocate you have to search trough one or more trees. So no matter how "smart" is your library for avoiding OS system calls, you already have a hell to maintain (search through a tree or a list, delete, split, etc.). Things get ugly when a process has lots of dynamic memory calls, on non-trivial cases.
  - vertex-four 9y ago
    An alternative, if you have a well-defined portion of code by the end of which you know you're not going to touch any data which was allocated in it, is to use arenas - allocation is then a pointer bump, and you can deallocate all of it at once.
    - faragon 9y ago

vbezhenar 9y ago

Underlying problem is that C doesn't have comprehensive standard collections, so many developers reinvent the wheel over and over again, and usually that wheel is far from best in the world. If curl was written with C++, those optimizations would be applied automatically by using STL collections.

wolf550e 9y ago
He turned his containers into intrusive ones. The standard C++ STL containers are not intrusive. Boost comes with intrusive containers, but if you need a third party library, you can do that in C too.
- dbaupp 9y ago
  They have many of the same properties as being intrusive, e.g. one can write a list type that can store any type and store it directly inline next to the next/previous pointers, not needing an allocation like the common C strategy of using void*.
- eropple 9y ago
  What, in your view, is meaningfully different between an intrusive container and std::list allocating memory right next to the prev/next pointers for your data?
  - dbaupp 9y ago
    For data in a single list, they're essentially equivalent, but they differ when one wants to put things in multiple lists. 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.

iamalurker 9y ago

My problem with excessive allocations is usually what happens in interpreted languages. People think, hey it's already slow ass interpreted so lets not care about allocation at all. 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).

nnethercote 9y ago

There is a little-known Valgrind tool called "DHAT" (short for "Dynamic Heap Analysis Tool") that's designed to help find exactly these sorts of excessive allocations. Here's an old blog post describing it, by DHAT's author: https://blog.mozilla.org/jseward/2010/12/05/fun-n-games-with-dhat/ 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-up-the-rust-compiler/ 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 http://valgrind.org/docs/manual/dh-manual.html

wyldfire 9y ago
> I previously had -Ccodegen-units=8 in RUSTFLAGS because it speeds up compile times. ... the resulting rustc was about 5–10% slower. So I’ve stopped using it now. ...why is this the case?
- detaro 9y ago
  It breaks the code into smaller modules that are processed independently, thus limiting the scope of optimizations to those modules.

amenghra 9y ago

You would think curl's perf is bound by the network latency/bandwidth and that intrusive lists wouldn't make a signifiant difference.