5 ms·

> It could be more performant No, it almost always is. The designers of a generic library can't anticipate the use case, so can't make appropriate tradeoffs.

> It could be more performant No, it almost always is. The designers of a generic library can't anticipate the use case, so can't make appropriate tradeoffs. For example, compare `std::unordered_map` to any well written C hash table. The vast majority of hash tables will never have individual items removed from them, but a significant amount of complexity and performance is lost to this feature.

SubjectToChange 3y ago
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?
- commonlisp94 3y ago
  > 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.
- memefrog 3y ago
  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.
  - protomolecule 3y ago
    "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 https://godbolt.org/z/M1v8azojT
mcguire 3y ago
For one example, https://github.com/tmmcguire/rust-toys/blob/master/alternatives/anagrams-hash.c https://github.com/tmmcguire/rust-toys/blob/master/alternati... is a program that mmap's an anagram dictionary file and builds a fast-n-dirty hashmap dictionary over the file data. It took about an afternoon to write and was pretty decent. https://maniagnosis.crsr.net/2014/08/letterpress-cheating-in-rust-0110-part-2.html https://maniagnosis.crsr.net/2014/08/letterpress-cheating-in...
snovv_crash 3y ago
Unordered map is a known design issue, on the same order as std::vector<bool>. C doesn't even have std::vector<int>>

SubjectToChange 3y ago

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?

commonlisp94 3y ago
> 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.
memefrog 3y ago
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.
- protomolecule 3y ago
  "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 https://godbolt.org/z/M1v8azojT

mcguire 3y ago

For one example, https://github.com/tmmcguire/rust-toys/blob/master/alternatives/anagrams-hash.c https://github.com/tmmcguire/rust-toys/blob/master/alternati... is a program that mmap's an anagram dictionary file and builds a fast-n-dirty hashmap dictionary over the file data. It took about an afternoon to write and was pretty decent. https://maniagnosis.crsr.net/2014/08/letterpress-cheating-in-rust-0110-part-2.html https://maniagnosis.crsr.net/2014/08/letterpress-cheating-in...

snovv_crash 3y ago

Unordered map is a known design issue, on the same order as std::vector<bool>. C doesn't even have std::vector<int>>