9 ms·
After quickly glancing the code, I concluded that they wrote C++ like there is no static type. It seems they faithfully ported the very dynamic nature of their
by ezoe 7y ago
After quickly glancing the code, I concluded that they wrote C++ like there is no static type. It seems they faithfully ported the very dynamic nature of their existing code to C++ without thinking.
Like what is this?
https://github.com/ExaScience/elprep-bench/blob/master/cpp/filter_pipeline.cpp#L20-L33 https://github.com/ExaScience/elprep-bench/blob/master/cpp/f...
auto alns = any_cast<shared_ptr<deque<shared_ptr<sam_alignment>>>>(data);
So the data is sam_alignment type inside shared_ptr inside deque inside another share_ptr inside god forbid any? Why did they do that? What kind of abomination is this? Also from the context, it is the only possible type. they use:
try { any_cast<abomination_type>(data) ; }
catch ( bad_any_cast ) { throw runtime_error(...) ; }
If you're so sure an object of any only hold exactly one type and everything else is unexpected error, you shouldn't use any at all!
They really like std::deque<T> and use it everywhere even though the sizeof(T) is like a few dozen bytes at best so they should rather use std::vector. The data structure of deque is a list of array. while it can amortize the continious adding of the elements to front or back, since the element size is very small, they should rather use vector.
Speaking of data structure, they also use std::unordered_map<int, any>. the unordered_map is very slow(it's a node based hash map, not suitable for the modern hardware) and the sizeof(int) + sizeof(any) is like 20 bytes(sizeof(int) + two pointers) so they got no benefit of using node based data structure here. They should rather use sorted vector and binary search it.
My conclusion, it's slow because they wrote C++ like a dynamic typed language and they choose the wrong data structures.
- WesternStar 7y ago<unpopular opinion>We should break ABI on unordered map just to stop embarrassing ourselves in public and in front of new users.</unpopular opinion>
- RantyDave 7y agoWhat's wrong with unordered map?
- ezoe 7y agoIt's implementation is buckets divided node based hash map. Theoretically, its order is good, but not that efficient in modern hardware where the memory access is heavily cached so the data locality is more important than saving the memory copy or memory size. Using the linked list to save some memory copy doesn't benefit at all and the overhead is far greater than simply copying the contagious large chunk of memory. Especially so if the data type is trivial so the simple byte by byte memcpy is suffice.
- gpderetta 7y ago> contagious normally I wouldn't point out an obvious autocorrect mistake, but this is really season-appropriate (or, better, inappropriate) :).
- ezoe 7y agoOh that's... not intended really.
- TwoBit 7y agoSo use unordered_map with an allocator that returns nodes from a small local memory?
- josefx 7y agoTo be useful that would require that the nodes are allocated in the order they appear in the map (and still has pointer overhead). Is that a given with an unordered map or does it break down the moment the map is rehashed?
- ezoe 7y agoThe problem is, hash map isn't that effective in modern hardware, the overhead cost is greater than the benefit. If it's consists of clustered network connected computers, it may be, but not for the single local computer for the most of problem.
- cozzyd 7y agowhy not just define std::dict or something like that that is better?
- WesternStar 7y agoBecause you should be able to find a good hash data structure for your language. You shouldn't be able to accidentally get a bad one. It should arguably be the first data structure you reach for.
- gpderetta 7y agoI think the parent is proposing adding a better hash map to the standard library but with a different name to preserve backward compatibility.
- imtringued 7y agoDeprecate the old data structure. Even Java did that. Originally it had the Vector class as primary List type. Nowadays everyone uses the List interface and ArrayLists as default implementation. You can even find this in the javadoc of the Vector class: >As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.
- alexhutcheson 7y agoIt’s unfortunately not just ABI, but also API. The standard specifies that you can get iterations to specific buckets in O(1)[1], and also specifies bucket_count(), max_bucket_count(), bucket_size() (which is specified to be O(n)), and bucket(). Those functions and their specified performance make it effectively impossible to implement a standards-compliant std::unordered_map without using separate chaining. [1] https://en.cppreference.com/w/cpp/container/unordered_map/begin2 https://en.cppreference.com/w/cpp/container/unordered_map/be...
- SamReidHughes 7y agoYou can just remove those functions. The real problem is that the API break would invalidate iterators and create undefined behavior.
- UncleMeat 7y agoI'm not even sure that is an unpopular opinion. Its a minority opinion, but people on the committee have been grumbling about how ABI consistency is hamstringing C++ for a while now.
- gpderetta 7y agoThe use of 'any' and the ridiculous levels of boxing is bizarre. There is also absolutely no attempt at using std::move; the amount of gratuitous copies and refcount updates is staggering. Having said that, apart from the use of std::any, the code is fairly clean even though obviously is not even remotely written for performance..
- ezoe 7y agoIt's actually more surprising that the person who can write this otherwise clean and modern C++17 code produce this awful abomination. The only possible explanation is, he literally port the existing code written in a very dynamic language by hand. He is not stupid, far from it. It's just he also ported the dynamic part of the code so well.
- beached_whale 7y agoA copy in function arguments often is not expressed by the compiler and often allows more optimizations.
- gpderetta 7y agoFor relatively small objects with no internall allocation, definitely yes. Otherwise only a qualified yes: if you are copying it anyway in the body, pass by value allow moving object into and actually avoid copies, but the code linked doesn't use move at all anywhere. As they seem fairly versed in C++, the only reason for doing that is that they want their code to be modificable by non-programmers, so they want to use a style that is safe and avoids possible use after move. For this scenario, then yes, C++ is going to be slower than a language with a proper garbage collector (although I would like to see a version with a proper shared_string implementation instead of the abomination that is shared_ptr<std::string>).
- beached_whale 7y agoDef a qualified yes. The pass by value will often allow the compiler to deal with less as a pass by ref/ptr makes it more pessimistic. You see this play out in trying to get the auto-vectorizer going by copying N values to a local buffer in the loop prior to operating in them. The optimizer in c++ compilers are really good at inlining and if it's a single TU more so. So the size isn't the issue in those cases too. In addition, on the other size most optimizers have a form of return value optimization that elides the copy/move on the return value. Where they often get hit up or lacking is heap allocations. They seem to hide a lot and only some compilers can elide a heap allocation. Use after move is interesting. Many cases of move are not necessary anyways (returning an automatic storage object) but the complexity of the code already would be on part with using std::move. I don't think an optimizer will do that one even if it is that last usage.
- benibela 7y ago>the unordered_map is very slow(it's a node based hash map, not suitable for the modern hardware) It is very slow? I wrote my app in FreePascal. I need a hashmap, but FreePascal has no real standard hashmap, so I have been benchmarking Pascal hashmaps for weeks/months. Today I added std::unordered_map for comparison. It will still take a day to run the benchmark, but so far it looks that std::unordered_map is 25% faster than the fastest map in the FreePascal standard library. And the best map of 45 Pascal maps is only 30% faster than std::unordered_map. Only 10 maps are faster, and 35 maps are slower.
- gpderetta 7y agoDepends what you do. If you populate it only once and then you do a bunch of lookups, assuming a low load factor, you'll be paying for a modulo operation and an extra indirection, not great but not terrible either. If you do a lot of inserts and removal or your load factor is high, then the performance is going to be not great.
- benibela 7y agoMy benchmark is one insert, multiple lookups, repeat. I have no use for deletions. Although when I want to make a general benchmark, I probably should measure it once, too
- saagarjha 7y agostd::unordered_map is supposedly slow because it has fairly stringent iterator invalidation requirements. In my experience, unless you wring the most performance out of your code as you can, it's not a huge issue; it's generally faster than most casual implementations.
- TwoBit 7y agoYeah people here are dumping on it for being non-performance-optimal while ignoring that higher performing versions have restrictions and design limitations. unordered_map is fast enough for probably 98% of uses, and the other 2% may be better off finding a specialized version best for their particular case.
- tom_mellior 7y ago> They really like std::deque<T> and use it everywhere even though the sizeof(T) is like a few dozen bytes at best so they should rather use std::vector. The data structure of deque is a list of array. while it can amortize the continious adding of the elements to front or back, since the element size is very small, they should rather use vector. Are you saying that access patterns (push/pop front/back) never matter and std::vector is always better than std::deque if the element size is very small? I don't think that this is true in this generality.
- 04091948 7y agoin CppCon 2016: Chandler Carruth “High Performance Code 201: Hybrid Data Structures"[1] he says: "but the standard deque data type is really quite bad. I wouldn't recommend anyone use it for anything. if you look at the implementation constraints, the constraints placed upon its iterators, and its invalidation constraints, it's painted into a very unpleasant corner and it has very few opportunities to be an efficient data structure." [1] https://www.youtube.com/watch?v=vElZc6zSIXM https://www.youtube.com/watch?v=vElZc6zSIXM
- pansa2 7y agoFor a language whose purpose is high-performance, the std:: containers are an embarrassment. `deque` is slow, `map` is slow - so the language added `unordered_map` which is also slow... Are any of the containers (other than `vector`) worth using in high-performance code? I’m sympathetic to the game developers who I’ve heard say “we use C++, but nothing from std::”.
- Leherenn 7y agoArray is great as far as I know.
- kllrnohj 7y agostd::array is great except it's annoying to statically initialize. Really wish make_array or to_array were non-experimental a lot sooner (to_array finally did land in C++20 at least). But yeah it does mean you can finally stop doing that silly `sizeof(a)/sizeof(a[0]);` trick.
- movedx 7y ago> My conclusion, it's slow because they wrote C++ like a dynamic typed language Here's my conclusion without needing to look at the code: is C++17 so complicated a language that having to understand deeper concepts such as the ones you've mentioned means a reduced "time to market" for marginal gains over the same code written in Go? Or put another way: did you just further prove that Go is the better option because it's providing extremely similar performance yet doesn't require this very esoteric knowledge you've mentioned? If I can get the same work done in Go and I can learn Go in a week versus months for C++17 (which is far more complex), why would I pick C++17?
- kllrnohj 7y agoIf you know Go and don't know C++ then yes absolutely use Go. If you're trying to do a performance comparison though it doesn't seem unreasonable to have "basic" familiarity with the languages being compared? None of the knowledge mentioned is "esoteric". We're not talking hyper optimized insane C++ optimizations here with custom allocators and specialized code generation with templates. We're talking "basic" memory management & standard library data structures.
- movedx 7y ago> If you're trying to do a performance comparison though it doesn't seem unreasonable to have "basic" familiarity with the languages being compared? No. Because it's not just a performance comparison, really. Without realising it, it's also a learning test. The very fact they wrote sub-par C++ code, likely without realising it, and then proceeded to produce (sub-par?) Go code that was faster demonstrates the difficulty of one language over the other. It demonstrates the cognitive efforts required between the two options and one of them was easier to produce and the results were more than suitable. These technology comparisons are important, for sure, but at the end of the day people want an ROI from everything they do, even the things that don't involve money. So if something can be solved in six hours with one solution or 36 hours with another, and the latter only yields a 10% performance, then I'd rather my end goal be ready and "in the market" for 30 hours ahead of the other guy using the slower solution for a 10% speed improvement.
- brnt 7y agoWelcome to scientific programming :)
- IshKebab 7y agoMaybe they wrote it really badly so someone will take offence and rewrite it for them! Also in my experience `std::deque` is almost always slower than `std::vector`. In theory it shouldn't be, but copying contiguous data is so fast on modern CPUs that the reallocation of `std::vector` (or occasional front-insertion) is very cheap.
- grovellogic 7y agoIn theory copying contiguous data is faster than dealing with pointer indirection.
- techempower 7y agoHashmaps Benchmarks: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-05-conclusion/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-05-c...