4 ms·
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
by vbezhenar 10y 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 10y agoHe 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 10y agoThey 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 10y agoWhat, 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 10y agoFor 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.
- eropple 10y agoThat's a really good point and I hadn't considered it. Thanks!
- dooglius 10y agoI don't believe C++ compilers can do optimizations around allocation. A quick test at https://godbolt.org/g/lFQcKf https://godbolt.org/g/lFQcKf reveals that gcc does not appear to coalesce STL operations, or move the allocation to the stack. The compiler is much dumber than most people think it is.
- pcwalton 10y agoLLVM can remove allocations that are unused, but that's it. 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.
- vbezhenar 10y agoI'm not sure I follow you, but std::list implementation stores object data inside node, so it's only a single allocation per node, as it should be.
- tom_mellior 10y agoSomewhat true, but many C++ programs implement their own containers because they find the STL "slow" or "bloated" or whatever. (For concreteness, both GCC and LLVM do this.) So I guess the same might eventually happen to curl, in which case we'd get this same kind of article on Hacker News ;-)
- adrianN 10y agoSTL maps are pretty slow and can be beat without too much effort.
- tom_mellior 10y agoYou mean with hash tables? Different underlying structure, so I wouldn't call that a reimplementation. Anyway, the projects I mention above also define their own vectors.
- lorenzhs 10y agoeven std::unordered_map is easy to beat on most workloads if you relax the standard's requirements a litte, because the standard more or less requires hashing with chaining ("The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket"). A good linear probing hash table will be faster most of the time, e.g. Google's dense_hash_map.
- jononor 10y agoGCC used to be written in C (not C++) until couple of years back, and the codebase origins predates both the STL and C++. So they are not the greatest example.
- tom_mellior 10y agoAs you say, GCC switched to C++ just a few years ago, when the STL had already existed for decades. I don't understand how you conclude that they couldn't have just used the STL when they did the switch to C++. Implementing their own containers was more work without any gain in portability.
- halayli 10y agono that's not the problem. STL containers rely on mallocs internally. also the major saving came from curl_multi_wait: > 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.