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.
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:
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.
For 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>).
Def 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.
It’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.
I'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.
It'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.
To 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?
Because 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.
Deprecate 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.
The 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.
> 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?
If 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.
> 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.
> 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?
Who or what tell you it's a learning test ? It is a pretty weak asumption.
The publication says nothing on the actual past experience of the developers in every language. They might very well be experienced in Go or Java.
From their C++, It is pretty obvious it is not their main language.
In my experience, this kind of code of nested shared_ptr everywhere is pretty typical of developers with a Java background just starting C++.
they clearly want the performance - the algorithms (as you can easily see in the repo) are trivial, its just a huge amount of data to process
C++ can shine here - and still looking nearly like the go or Java-Code (due to the simple algorithm) but some one tried to write highly sophisticated code (there is no tutorial or book about C++ that teaches you to do it that way) with the result that C++ is far more slower then possible - we definitly not talking about 10% gain here
> they clearly want the performance - the algorithms (as you can easily see in the repo) are trivial, its just a huge amount of data to process
> C++ can shine here
And my point is: it didn't. And it didn't because of the learning curve involved. It's only the better solution if the knowledge is invested in ahead of time, and if the gains don't outweigh those you'd get from Go by an amount that greatly exceeds the time invested to net them, then it's not the better choice.
but your point is just not correct - i know go, Java and C++ very well and i don't understand why the C++ code isn't just like the Java code - there is absolutely no need for this deep nested, ugly, container parties that are not in the Java code at all
The flip side to this is that for someone who knows roughly what a CPU does (you don't need in-depth knowledge to think about pre-fetching and branch prediction) C++ is going to be easier to use to leverage that. That's really the end of it.
I agree with you that writing C++ is harder than writing Go and that writing naïve C++ leading to disproportional pessimization of your program shows that it's not the right tool for people who lack the knowledge to use it.
At the same time it's really not hard to translate simple concepts into simple code for lower-level languages, that runs well on modern processors. Basic usage of (possibly) growable, homogenous arrays will get you far. Contrary to what most C++ app developers seem to think custom allocators aren't complicated either, and will guarantee that you get much better cache locality and memory management.
Most of these issues are made hard by people, including the premise of learning the basics of what you need to do for the processor to execute your code fast.
That being said if the time invested in learning C++ and the extra time needed to write it and optimise it doesn't exceed the performance of the same solution written in (optimised) Go by a factor larger than the time invested then it's not the right choice overall.
you are just wrong - someone without any good C++ knowlegde except porting the Java port plain to C++, ported it by using every crude feature and wild combination of shared-ptr, container nesting in a way you will nearly not find in any open source or tutorial project - its not about the ease of go, the the benchmark results are just wrong in so many ways
‘Esoteric’ is in the eye of the beholder. Even in Go you gain performance by avoiding boxing.
> 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?
Because C++17 code if written well is likely to be much faster. If you don’t care about that, by all means stick with Go. But keep in mind that learning is a one-time cost, and you can keep applying the same knowledge to project after project.
> I was hoping someone could prove this, actually.
Maybe this presentation by Jason Turner from CppCon 2016 can illustrate just what can be done in C++17. His target in the presentation is a C64, but I think it illustrates well just what you can do with the language, and hence what tools are available for writing fast code.
that is really not the case here - the Java and C++ implementatios are very plain boring algorithm code (some maps,lists,searching) non of the fancy language features are use to reduce or optimize the code - its absolutely not a C++-is-hard-to-get-right-thing
the C++ code is just using rarely used features in over-wild combinations - as stated: it seems that someone tried to port highly dynamic script code 1:1 to C++ without any knowledge about C++ and that just make no sense, even porting the current Java-Code 1:1 to plain old C++ Code would result in a much better performing version of the algorithm
everything (even the simplest stuff) is FORCED to be heap-allocated (with huge amount of code), in case of deque and shared_ptrs even double or tripple times - without any benefit of doing it
i would bet that a more clean, less every-feature-using version of the C++ algorithm would beat the Java, go code by a huge factor
The problem with that idea is that he actually used more advanced features to make it worse (any_cast). This is not how you would do it if you picked up a beginner C++ book and read the first few chapters.
>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.
std::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.
Yeah 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.
Depends 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.
Maybe 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.
> 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.
in 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."
For 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::”.
STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime.
Yes, it's embarrassing. I think it should be noted that the performance mantra is mostly for show with C++, though. The same people who spout it will also blatantly use pessimizing language features just because, when normal, procedural code would've done the job faster and ultimately simpler.
I think the performance overhead of a few things in C++ make sense, but in general you get performance in C++ by turning things off and abstaining from most of the features. Exceptions complicate mostly everything, so the best thing to do is to turn them off and not rely on anything that uses them, for example.
Modern C++ isn't fast and most of C++ wasn't even before the modern variant was invented. The C "subset" is.
> STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime.
It is NOT garbage. It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already).
If what you need is sub micro-second perf, then yes, redefined your data-structure.
BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fastforever-living data structure. They (almost) all become obsolete when architectures evolve. Red-Black Trees where state of art DS, teached-at-school 10 years ago, they are useless garbage nowadays if you seek for performance.
> It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already).
I really don't get this argument. If you don't need pedal-to-the-metal performance then why are you using C++ in the first place? (Unless, of course, your answer is "legacy code".)
C++ is being touted as being high performance, but basically every standard data structure besides `std::vector` is garbage for high performance, pedal-to-the-metal code. And not only data structures - `std::regex`'s performance is bad, `std::unique_ptr` doesn't optimize as well as a plain pointers, no vendor has a best-in-class `std::hash` implementation (they're neither DoS-safe nor the fastest), etc.
> BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fast forever-living data structure. They (almost) all become obsolete when architectures evolve.
Do you, though? Rust already replaced their standard hash map implementation with a completely different one which was faster, so it shows that it can be done.
> I really don't get this argument. If you don't need pedal-to-the-metal performance then why are you using C++ in the first place? (Unless, of course, your answer is "legacy code".)
There is many other things that pure compute-bound CPU performance that can drive you to a GC-less language like C++. Fine grain memory usage is one of them, latency control is an other.
> `std::regex`'s performance is bad. , `std::unique_ptr` doesn't optimize as well as a plain pointers
However, do you have any bench / source for std::unique_ptr ? You are the first one I hear giving critics on it.
> Do you, though? Rust already replaced their standard hash map implementation with a completely different one which was faster, so it shows that it can be done.
Rust does not have 25 years of code base behind him. We can talk to that again when he gets 10 years more.
C++ can not afford to randomly break API on one of its core STL component just to hypothetically gain few bit of performance.
It can be done, but it should be done with a depreciation process and an alternative implementation, like it has been done for auto_ptr -> unique_ptr.
Rust didn't break the API of HashMap. The trick is that the STL decided that certain algorithmic requirements were a part of the interface. For std::map, the case here is that it must be sorted. Its API also means you can't be polymorphic over a hashing strategy. This constrains possible valid algorithms. Rust made the opposite choices.
And so they did exactly what you say, for that reason. std::unordered_map is a better comparison.
std::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.
Thanks for the reference. But this is still specific to access patterns: You can use a deque as a queue without iterating, so iterators and their invalidation constraints should not matter.
Like what is this? https://github.com/ExaScience/elprep-bench/blob/master/cpp/f...
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: 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.