4 ms·

> A library author can spend ridiculous amounts of time That's true. But simply having knowledge of the goal and a few simplifying assumptions can beat all the

> A library author can spend ridiculous amounts of time That's true. But simply having knowledge of the goal and a few simplifying assumptions can beat all the optimization in the world. In other words, a polished sub-optimal approach isn't as good as just having a better approach. `std::unordered_map` is heavily optimized, but can't make any tradeoffs because it's a general tool. > plethora of generic C++ hash tables which would match, if not soundly outperform, their C counterpart. Post one. > not only is it possible to specialize generic code for particular types, but it's absolutely routine to do so. Yep, it can do type base specialization, not application based specialization though. That requires a programmer. > how do you explain qsort often being beaten by std::sort a standard library C function often cannot be inlined to remove the comparison function pointer call, whereas std::sort trivially can. If you wrote one yourself for a particular problem, it would not have this issue. This is actually a great example of where C excels because the choice of sorting algorithm so much depends on the kind of data you are sorting. Let me be clear about my claim: tailor made solutions to each problem will almost always be faster than generic solutions. Do you really disagree with that? If you want to argue that maybe it's not productive to work that way, that's a different argument.

SubjectToChange 3y ago
Let me be clear about my claim: tailor made solutions to each problem will almost always be faster than generic solutions. Do you really disagree with that? I disagree with it in the sense that I disagree with the statement "A human will always be able to write the same or better assembly than a C compiler, because humans can learn the compiler's tricks and make optimizations which the compiler is not allowed to make." It's a true statement, but it's so detached and irrelevant that it hardly matters. Generic code has proven itself time and time again, even Go caved in and supported it.
- commonlisp94 3y ago
  The assembly example isn't a good comparison. We have compilers that can generate a lot of assembly tricks most programmers wouldn't write. We don't have a way compiler that can analyze the logical constraints of a programming problem and simplify the data structures in the library. > Generic code has proven itself time and time again, even Go caved in and supported it. I'm not saying anything against the language feature generics. There is plenty of use for them even in a self contained code base.
c-cube 3y ago
> post one Abseil or folly both have optimized hashtables, I believe. Rust's standard HashMap follows the same design. It involves SIMD to look for a bucket whose hash matches the query's so redoing it in C every time you need a hash table will be quite impractical.
protomolecule 3y ago
"If you wrote one yourself for a particular problem, it would not have this issue. This is actually a great example of where C excels because the choice of sorting algorithm so much depends on the kind of data you are sorting." Did I get it right that you argue for re-implementation in every of your apps of some sorting algorithm which is most fit to your data? Why not use instead a generic library implementing a particular sorting algorithm parameterized by the data type and maybe by some policies specifying minor variations of the algorithm? "Let me be clear about my claim: tailor made solutions to each problem will almost always be faster than generic solutions. Do you really disagree with that?" I do. I don't think even you invent a special sorting algorithm for each of your applications that need sorting.
dureuill 3y ago
Getting generic data structures that are more efficient than his specialized C data structures is exactly what happened to Bryan Cantrill when he ported a carefully optimized C program to naive Rust. > Yes, you read that correctly: my naive Rust was ~32% faster than my carefully implemented C.[0] > As a result, this code spends all of its time constantly updating an efficient data structure to be able to make this decision. For the C version, this is a binary search tree (an AVL tree), but Rust (interestingly) doesn’t offer a binary search tree — and it is instead implemented with a BTreeSet, which implements a B-tree. B-trees are common when dealing with on-disk state, where the cost of loading a node contained in a disk block is much, much less than the cost of searching that node for a desired datum, but they are less common as a replacement for an in-memory BST[1] > So, where does all of this leave us? Certainly, Rust’s foundational data structures perform very well. Indeed, it might be tempting to conclude that, because a significant fraction of the delta here is the difference in data structures (i.e., BST vs. B-tree), the difference in language (i.e., C vs. Rust) doesn’t matter at all.[1] > Implementing a B-tree this way, however, would be a mess. The value of a B-tree is in the contiguity of nodes — that is, it is the allocation that is a core part of the win of the data structure. I’m sure it isn’t impossible to implement an intrusive B-tree in C, but it would require so much more caller cooperation (and therefore a more complicated and more error-prone interface) that I do imagine that it would have you questioning life choices quite a bit along the way. (After all, a B-tree is a win — but it’s a constant-time win.)[1] > All of this adds up to the existential win of Rust: powerful abstractions without sacrificing performance.[1] [0]: http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-rust/ http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-... [1]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

SubjectToChange 3y ago

Let me be clear about my claim: tailor made solutions to each problem will almost always be faster than generic solutions. Do you really disagree with that? I disagree with it in the sense that I disagree with the statement "A human will always be able to write the same or better assembly than a C compiler, because humans can learn the compiler's tricks and make optimizations which the compiler is not allowed to make." It's a true statement, but it's so detached and irrelevant that it hardly matters. Generic code has proven itself time and time again, even Go caved in and supported it.

commonlisp94 3y ago
The assembly example isn't a good comparison. We have compilers that can generate a lot of assembly tricks most programmers wouldn't write. We don't have a way compiler that can analyze the logical constraints of a programming problem and simplify the data structures in the library. > Generic code has proven itself time and time again, even Go caved in and supported it. I'm not saying anything against the language feature generics. There is plenty of use for them even in a self contained code base.

c-cube 3y ago

> post one Abseil or folly both have optimized hashtables, I believe. Rust's standard HashMap follows the same design. It involves SIMD to look for a bucket whose hash matches the query's so redoing it in C every time you need a hash table will be quite impractical.

protomolecule 3y ago

"If you wrote one yourself for a particular problem, it would not have this issue. This is actually a great example of where C excels because the choice of sorting algorithm so much depends on the kind of data you are sorting." Did I get it right that you argue for re-implementation in every of your apps of some sorting algorithm which is most fit to your data? Why not use instead a generic library implementing a particular sorting algorithm parameterized by the data type and maybe by some policies specifying minor variations of the algorithm? "Let me be clear about my claim: tailor made solutions to each problem will almost always be faster than generic solutions. Do you really disagree with that?" I do. I don't think even you invent a special sorting algorithm for each of your applications that need sorting.

dureuill 3y ago

Getting generic data structures that are more efficient than his specialized C data structures is exactly what happened to Bryan Cantrill when he ported a carefully optimized C program to naive Rust. > Yes, you read that correctly: my naive Rust was ~32% faster than my carefully implemented C.[0] > As a result, this code spends all of its time constantly updating an efficient data structure to be able to make this decision. For the C version, this is a binary search tree (an AVL tree), but Rust (interestingly) doesn’t offer a binary search tree — and it is instead implemented with a BTreeSet, which implements a B-tree. B-trees are common when dealing with on-disk state, where the cost of loading a node contained in a disk block is much, much less than the cost of searching that node for a desired datum, but they are less common as a replacement for an in-memory BST[1] > So, where does all of this leave us? Certainly, Rust’s foundational data structures perform very well. Indeed, it might be tempting to conclude that, because a significant fraction of the delta here is the difference in data structures (i.e., BST vs. B-tree), the difference in language (i.e., C vs. Rust) doesn’t matter at all.[1] > Implementing a B-tree this way, however, would be a mess. The value of a B-tree is in the contiguity of nodes — that is, it is the allocation that is a core part of the win of the data structure. I’m sure it isn’t impossible to implement an intrusive B-tree in C, but it would require so much more caller cooperation (and therefore a more complicated and more error-prone interface) that I do imagine that it would have you questioning life choices quite a bit along the way. (After all, a B-tree is a win — but it’s a constant-time win.)[1] > All of this adds up to the existential win of Rust: powerful abstractions without sacrificing performance.[1] [0]: http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-rust/ http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-... [1]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...