Comment by SubjectToChange | Hacker News Reader

Comment by SubjectToChange | Hacker News Reader

Parent Full thread

SubjectToChange

No, it almost always is.

A library author can spend ridiculous amounts of time refining and optimizing their implementations, far more than any application programmer could afford or justify.

The designers of a generic library can't anticipate the use case, so can't make appropriate tradeoffs.

This is definitely not true. Take C++ for instance, not only is it possible to specialize generic code for particular types, but it's absolutely routine to do so. Furthermore, with all sorts of C++ template features (type traits, SFINAE, CRTP, Concepts, etc) even user-defined types can be specialized, in fact it's possible to provide users with all sorts of dials and knobs to customize the behavior of generic code for their own use case. This functionality is not just a quality-of-life improvement for library users, it has profound implications for performance portability.

For example, compare `std::unordered_map` to any well written C hash table.

std::unordered_map is a strawman. There are a plethora of generic C++ hash tables which would match, if not soundly outperform, their C counterpart. Also, even if we blindly accepted your claim, then how do you explain qsort often being beaten by std::sort or printf and its variants being crushed by libfmt? What about the fact that Eigen is a better linear algebra library than any alternative written in C?

> 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.

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.

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.

> 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.

"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.

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-...

[1]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

Yes a library author can spend a lot of time refining and optimising their generic data structure, but can never escape that it is generic.

No amount of optimisation will make a hash table designed for items to be removed competitive with one where items do not need to be removed.

>Take C++ for instance, not only is it possible to specialize generic code for particular types, but it's absolutely routine to do so.

So it's not a generic data structure, then. When you specialise a template, you essentially write a concrete data structure for a particular type. Rather than writing a big generic data structure that's inefficient then specialise it to the particular type, it is much easier just to write that specialised data structure in the first place.

>std::unordered_map is a strawman. There are a plethora of generic C++ hash tables which would match, if not soundly outperform, their C counterpart.

How is it a strawman? It's in the standard library.

>Also, even if we blindly accepted your claim, then how do you explain qsort often being beaten by std::sort or printf and its variants being crushed by libfmt?

printf is on the order of 50 years old. libfmt as written about 5 minutes ago. Do you take into account in your comparison the many more years in which printf has been useful? Do you take into account the amount of time it takes printf to compile vs a huge C++ library like libfmt?

Do you take into account all the code that has been slowed down by C++ programmers writing bad code and assuming a sufficiently smart compiler will inline everything for them? Do you take into account all the horrifically slow iostreams code out there?

qsort and std::sort do completely different things. Comparing them is absurd. qsort takes the size and comparison operator at runtime. std::sort requires them to be specified at compile times. I frequently use qsort in a way that you simply could not use std::sort, because those things are runtime-variable.

The proper comparison to std::sort is the implementation of a sorting algorithm written in C, specialised to the code it was written to work with. Then you can debate 'is it worth using this for the minor performance gain' etc. But comparing it to qsort is inane and demonstrates you don't even know what the two functions do.

"So it's not a generic data structure, then."

In generic C++ code, you can specialize a part of the generic algorithm to tune it to a particular use case. Usually it takes the form of a small class template which can be specialized for a particular type and is used by the generic algorithm operating on that type. This class template is called trait, policy or strategy depending on the way it is used.

"qsort and std::sort do completely different things. Comparing them is absurd. qsort takes the size and comparison operator at runtime. std::sort requires them to be specified at compile times."

Not at all, you can pass a function pointer to std::sort just as well if you need to [0]. Most of the time you don't need this indirection but in C you are stuck with it unless you copy-paste-edit qsort.

[0] https://godbolt.org/z/M1v8azojT

Reply on news.ycombinator.com