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.
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
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.
> 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.
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.
> 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.
[0] http://onlinelibrary.wiley.com/doi/10.1111/j.1745-459X.2012....
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".
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.
>"RAM is cheap"
Memory is cheap on servers and desktops. SSD can be treated as slow RAM.
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?