Comparison of C++17, Go, and Java for a next-generation sequencing tool
bmcbioinformatics.biomedcentral.com
bmcbioinformatics.biomedcentral.com
Like what is this? https://github.com/ExaScience/elprep-bench/blob/master/cpp/f...
auto alns = any_cast<shared_ptr<deque<shared_ptr<sam_alignment>>>>(data);
try { any_cast<abomination_type>(data) ; }
catch ( bad_any_cast ) { throw runtime_error(...) ; }
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.
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..
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.
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>).
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.
[1] https://en.cppreference.com/w/cpp/container/unordered_map/be...
normally I wouldn't point out an obvious autocorrect mistake, but this is really season-appropriate (or, better, inappropriate) :).
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.
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?
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.
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.
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++.
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
> 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.
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.
> 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.
Go has boxing?
> Because C++17 code if written well is likely to be much faster.
I was hoping someone could prove this, actually. I don't have the means or the knowledge.
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.
https://www.youtube.com/watch?v=zBkNBP00wJE
edit: If you just want a quick fix, check out what a simple keyword does here: https://youtu.be/zBkNBP00wJE?t=1616
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
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.
[1] https://abseil.io/docs/cpp/guides/container#hash-tables
[2] https://github.com/facebook/folly/blob/master/folly/containe...
It's just not as fast as some other implementations: https://tessil.github.io/2016/08/29/benchmark-hopscotch-map....
I have no use for deletions. Although when I want to make a general benchmark, I probably should measure it once, too
None of them stands out, as being THE standard Pascal map to use for everything.
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.
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.
"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."
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::”.
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.
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 fast forever-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.
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.
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
std::regex is not defendable, specially when there is much better implementation already available (https://github.com/hanickadot/compile-time-regular-expressio...)
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.
And so they did exactly what you say, for that reason. std::unordered_map is a better comparison.
Chandler Carruth talks about this at CppCon 2019 [0]. From a quick review he says part of the reason std::unique_ptr isn't zero-cost right now is:
- Objects passed by value (like std::unique_ptr) are passed on the stack instead of in registers, and changing that will be an ABI break
- No destructive move means extra temporaries will be created/retained
Look forward to all your users ignoring your return codes and never calling valid() on your objects that can only signal construction failed that way.
Also the impact of exceptions on performance is overblown, even in high perf situations:
https://news.ycombinator.com/item?id=20342183
Throwing is slow, but throwing is supposed to be rare. Don't use it as flow control.
The remaining 99% are happy to be able to deliver fast enough portable code without having to reinvent data structures all the time.
But yeah it does mean you can finally stop doing that silly `sizeof(a)/sizeof(a[0]);` trick.
As suspected, everything is dynamically allocated and no memory mapping (see e.g. http://man7.org/linux/man-pages/man2/mmap.2.html) is used. No wonder this is slow and eats a lot of memory. At the moment I have no information about why this design was chosen, if there is a justification for it, or if the developers only knew this option. Maybe I can find some hints in the paper. From what I've seen up to now it can be savely assumed that with optimal use of data structures and system functions the C++ results are at least one order of magnitude better.
There may be many reasons why scientists who are not computer scientists feel more comfortable with Go than with C++, but performance is certainly not one of them.
> C++ provides many features for more explicit memory management than is possible with reference counting. For example, it provides allocators [35] to decouple memory management from handling of objects in containers. In principle, this may make it possible to use such an allocator to allocate temporary objects that are known to become obsolete during the deallocation pause described above. Such an allocator could then be freed instantly, removing the described pause from the runtime. However, this approach would require a very detailed, error-prone analysis which objects must and must not be managed by such an allocator, and would not translate well to other kinds of pipelines beyond this particular use case. Since elPrep’s focus is on being an open-ended software framework, this approach is therefore not practical.
However, a certain level of proficiency must be expected, and in the case of C++ this includes "know when to use const&, unique_ptr<T> or shared_ptr<T>". If this cannot be expected of the user, the comparison becomes less a question about performance and more about which language is the best at being the lowest common denominator.
> Phase 1 allocates various data structures while parsing the read representations from BAM files into heap objects. A subset of these objects become obsolete after phase 1.
> Therefore, manual memory management is not a practical candidate for elPrep,
TL;DR: it's non-deterministic which objects will be garbage when so some for of dynamic memory management is needed.
If you disagree, what would you use instead?
Or like this:
auto alns = make_shared<deque<shared_ptr<sam_alignment>>>();
It's like make_shared is the only way they know to allocate an object. They even put string inside of shared_ptr:
class istream_wrapper {
...
shared_ptr<string> buffer;
EDIT: And they don't even seem to use std::move anywhere :/ There's a huge gap between this code and custom allocator territory.
Edit: It might help to keep in mind that string is essentially an alias for unique_ptr<char[]>. As in, string is already heap allocated. They heap allocated a pointer to a heap allocation.
I would use std::monotonic_buffer_resource added in C++17. It's implementation is consists of just a pointer point to large contagious memory. You want a n bytes of memory? return the pointer while adding ptr += n. Deallocation do nothing. Destructing std::monotonic_buffer_resource object deallocate the memory. If the objects has trivial destructor, as that is the case based on glancing the code, this is very efficient.
Why? This is a batch program, interruptions don't matter, only the end-to-end time does.
> The goal of elPrep is to simultaneously keep both the runtime and the memory use low.
Why? Keeping runtime low lets you get more work done. Keeping memory use low means what? They are using a machine with 384 GB RAM, make use of it.
Worth noting also that they used GCC 7.2.1, Go 1.9.5, and Java 10. That's a pretty old GCC.
They don't seem to explicitly select a GC with Java, so they'll be using G1. G1 is still not entirely mature. It got much faster between 9 and 10, and somewhat faster from 10 to 11. For a batch process like this, though, the parallel collector is still probably a better choice. Using a newer JDK and a different collector should give better performance - but admittedly, probably won't reduce heap usage.
I wonder if they capped the java max heap size to what the go implementation used, how much it would have affected the runtime.
This may indeed have some performance benefits, but it's a very impractical approach from a hardware point of view. Few places doing processing of genomic data will have many compute nodes with > 256GB memory, yet that would barely process 1 sample with this framework. God forbid you have a family of samples or tumor/normal comparison samples to analyse and need several genomes in memory together.
Genomes are for the most part massively parallelisable and nearly every other toolkit I have seen has put that first and foremost in its design approach. Ensuring tools process data in a streaming manner and pipe between each other is a basic expectation of most genomic data tools.
Which is all to say ... this is a very strange beast and I'm not sure a lot of conclusions can be drawn from it that generalise to other activities or approaches.
The authors go in more detail around this topic in: https://journals.plos.org/plosone/article?id=10.1371/journal...
This isn't some electron framework where it is unexcusable to use that much RAM. The hardware that is available to scientists is more than capable of handling these workloads.
They don't seem to take into account that their results depend on their own proficiency in each programming language.
If they're going to implement it as well, then that's perfect. They now know which language they should be using with their proficiency.
In some other team, Java might have been #1. The overall best results with a great team would almost certainly be achievable by using C++.
But this is what worked for them.
They could've just saved themselves the trouble and said "Anyone fancy doing this in C++? No. Great, that's that tricky question off the table!" Rather thna going through this ridiculous exercise of writing bad C++ in order to justify not using C++. If we really believe that this is just a way of idnetifying a revealed preference fine, but engineers should be smart enough to not need to trick thesmlves into coming to the obvious conclusion.
And like another commenter mentioned, if you're writing a program which streams a lot of data sequentially from disk, and where throughput is important (such as in sequencing), you should always be using mmap
If you are seeking randomly and doing small reads, then mmap will help quite a bit: the data will be faulted in, and accessing it a second, third, or hundredth time will not cost much.
As the paper states: it is not possible to manually determine the object lifetimes due to the nature of the problem, data and openness of the configurable analysis pipeline. Manual alloc/free would in their case mean holding on to much more memory than a GC/refcounting solution would.
if you look at their code it's like they have no clue that the stack even exists. seriously. they heap allocate EVERYTHING
But anyone working on language perf should take note even though it’s just one result from one team and one application. Of course they probably used C++ in a not great way and probably use Go in a better way. But maybe that is caused by something in Go that encourages good behavior or at least encourages the kind of behavior that Go optimizes for.
So, even if this result doesn’t mean that C++ devs should switch to Go to get more speed, it’s a result that is worth pondering at least a bit, particularly if you like thinking about what it is that makes languages fast or slow.
Which part of the results are you referring to? It's well-known that reference counting has significantly lower throughput that tracing garbage collectors, so the fact that C++ is outperformed here isn't surprising at all.
So, there is no universal answer to how C++ reference counting compares to GC.
There is a well known answer, that you’re probably referring to, if you reference count every object and you do it soundly by conservatively having every pointer be a smart pointer. But it just isn’t how everyone who does reference counting in C++ does it, and I was surprised because I’m used to folks going in the other direction: being unsound as fuck but hella fast.
There are but critically there are also a lot of ways to not do ref counting at all. C++ isn't a refcounted language, it's a language where you can use refcounting (shared_ptr), but you don't have to (unique_ptr, value types). It's not even recommended to be primarily refcounted.
They chose a really odd subset of C++ to use here (shared_ptr exclusively), very unorthodox and not something I've ever seen elsewhere or recommended.
The rest is a lot of string manipulation. If you are not taking advantage of being able to layout your objects carefully and avoid memory avoiding allocations, I wouldn't expect C++ to have any particular advantage over Go or Java in in this particular scenario.
Lattner on Swift (2016): "...while it is true that modern GC's can provide high performance, they can only do that when they are granted much more memory than the process is actually using. Generally, unless you give the GC 3-4x more memory than is needed, you’ll get thrashing and incredibly poor performance..."
Designed by apple (I think using ARM instruction set) and made using some of the latest, most advanaced, process nodes by TMSC.
If you look at raw benchmarks, they handidly beat the best Qualcom/"android SOC" chips out there.
I think this changes very rapidly - given the market segment of high end phones has a yearly turn around. However, I did read an article today that claimed the "cheapest iPhone" (the new SE model) is faster than the most expensive android phone currently out there.
Apple has been leading the mobile processor market by quite a bit for the last five years.
> elPrep allows users to specify arbitrary combinations of SAM/BAM operations as a single pipeline in one command line.
The assumption is that your native environment for data analysis is bash and you have to expose anything that you might want to do in bash. Further,
> elPrep also accommodates functional steps provided by third-party tool writers
That is, they are attempting to provide general semantics in a bash command line that they can handle arbitrary functions being dropped into their program.
Remember, the average salary of a job requiring both programming and biology knowledge is much lower than the average salary of a job requiring programming knowledge alone, so as bioinformaticists build skill to the point where they can be employable as programmers, they mostly leave bioinformatics.
Those who have escaped bash have usually done so into Python these days, which creates a class system of those gluing things together in Python versus those implementing algorithms in C or C++.
> Most existing Common Lisp implementations use stop-the-world, sequential garbage collectors. To achieve good performance, it was therefore necessary to explicitly control how often and when the garbage collector would run to avoid needless interruptions of the main program, especially during parallel phases. As a consequence, we also had to avoid unnecessary memory allocations, and reuse already allocated memory as far as possible, to reduce the number of garbage collector runs. However, our more recent attempts to add more functionality to elPrep (like optical duplicate marking, base quality score recalibration, and so on) required allocating additional memory for these new steps, and it became an even more complex task and a serious productivity bottleneck to keep memory allocation and garbage collection in check.
https://github.com/ExaScience/elprep-bench/blob/master/cpp/m...
I am sure they didn't benchmark it like this but it would be interesting to see the flags that /were/ used.
That said, some of the code used is quite... odd.
> A comparison of three programming languages for a full-fledged next-generation sequencing tool
Java was slightly faster than go but used significantly more memory. C++17 was slower than both and used more memory than go.
I’m still reading for more details on the implementations, but the results are certainly not what I would’ve predicted.
It permits really fast allocation, defragmentation and is sometime the only way to manage memory (cyclic datastructures for which reachability cannot be known directly from program text).
Reference-counted GC on the other hand is notoriously slow, incomplete, and exhibit lots of bad performance patterns (that can be somehow managed by taking some elements of tracing GCs).
The drawback is that tracing GCs are very hard to implement, to tune, and sometimes not all of the benefits are available at the same time. And because they are so counter intuitive, programmers in general have a hard time understanding their runtime behavior... Even GC experts struggle (the skills required range from low-level hardware to control theory, otherwise performance at scale is unpredictable).
They clearly wanted automatic memory management, so the C++ implementation is reasonable. A fairer comparison might have used MPS or boehm instead of refcounting, but I suspect the results would have been similar.
Fig. 4 shows that deallocation, presumably of objects allocated during the first phase, takes half as long as the first phase itself. Unless the nature of the problem solved by the program requires you to have a ton of objects with shared mutability (the use case for shared_ptr), and requires you to make a lot of allocations up-front without knowing if you will need them, the memory thrashing occurring does not seem reasonable.
But not without allocating dynamic memory and copying data.
> They clearly wanted automatic memory management
Most likely because of some misconceptions.
> so the C++ implementation is reasonable.
How so?
> but I suspect the results would have been similar
Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
> But not without allocating dynamic memory and copying data.
Sure it does. In SBCL you can force a stack allocation (though rarely does it improve performance), and very short-lived values do not leave registers in any case.
> > They clearly wanted automatic memory management
> Most likely because of some misconceptions.
There are both good and bad reasons to want automatic memory management. At least one good reason it it would decrease the porting effort by keeping the code similar.
> > so the C++ implementation is reasonable.
> How so?
Using reference counting is a reasonable way to get automatic memory management in C++
> > but I suspect the results would have been similar
> Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
Which is going to be rough on any automatic memory management system, which makes using a language with a better ecosystem of automatic memory management more performant.
> Which is going to be rough on any automatic memory management system
You could equally say that it makes the case for actually designing memory allocation strategy (which only C++ really supports) that much more important.
You always see this in Java programs for large data analysis. They pick java because of memory management and the tooling. But it's just SO slow and after optimisation the only thing that stubbornly remains up there in the profiler data is memory and GC. And what do they do?
A global object of the following form:
class DataStore {
float theFloatsWeNeed[constHowMany];
int theIntsWeNeed[anotherConst];
}
The truth is you don't want memory management for large amounts of data. You don't want to allocate it, track it or deallocate it at all. You leave it in it's on-disk data format and never serialize/deserialize it at all. You want to mmap it into your program, operate on it and then just close the mmap when you're done. C++ definitely has the best tools for this way of working.
Ref counting: only makes sense in a few special cases.
Avoiding dynamic memory management: have a look at mmap.
Going back to my original point, you are suggesting a complete rearchitecture of their allocation system. That does not require switching languages to C++. If we are talking about working with 100s of GB of data, that's probably even the correct approach!
TFA does not, however, claim that they have a working set of 100s of GB of data. The data is 100s of GB at rest, but can be processed in chunks with a single pass. That, by itself, does not scream "mmap" to me. On top of that, the data is compressed at rest, so copying is inevitable.
https://news.ycombinator.com/item?id=22959600
1. Reference counting is a form of GC; you could implement a JVM that used reference counting (though in order to be general a small amount of additional work is needed)
2. Reference counting causes extra work every time a reference appears or disappears. Tracing GCs amortize that cost across many allocations.
2.b. This is particularly hurtful to performance for short-lived objects, since most tracing GCs have zero GC overhead for short-lived objects (the cost of a nursery collection under most implementations scales with the amount of live data in the nursery, so objects that appear and disappear in the time-span of a single nursery GC are freed at zero extra cost). Furthermore a tracing GC
3. Malloc cannot move allocated data, so many implementations have a lot of complexity to avoid heap fragmentation, which comes at a cost to both allocating and freeing data. Many GC'd languages allocate small objects with a single instruction in the typical (just incrementing a pointer, the non-typical case would be when the nursery is full and a GC happens).
4. the JVM and Go both have a lot of effort put into their GC; the ref-counting implementation used by this test is probably a bit more naive. In particular they talk about large delays when a chain of links cause many allocations to die at the same time. A less naive refcounting implementation would queue deleted objects and spread that work out across a larger time period.
https://www.researchgate.net/publication/221321424_A_unified...
Performance characteristics depend where on that continuum your workload falls. For example, Erlang/BEAM uses a generational GC for most common heap objects, but refcounts large binary blobs. This is pretty much a perfect case for refcounting: new references are created infrequently, copying or moving is expensive, destruction is deterministic and happens immediately after the last reference disappears, and there're no pointers within the blob that would require tracing or cycle-detection.
Similarly, UI components within a GUI is another good case for refcounting (and presumably why Apple continues to use this for Objective-C and Swift in Cocoa). New references happen only in non-performance-critical code, most data remains live across collections, and copying/moving existing data would a.) be slow and b.) would invalidate any C pointers into contained data.
Sounds like the particular problem domain described in this article is one where heap allocations are frequent, which makes generational GCs more appropriate. That's probably the case with the vast majority of computational algorithms, but there are definitely problem domains where refcounting continues to beat GC.
It would leak memory - reference counting cannot collect cycles (you need tracing GC for that, defeating the purpose of refcounting).
> (though in order to be general a small amount of additional work is needed)
Not also that there are two methods of cycle detection for a reference counted GC that are not just a backup tracing-GC
1. Trial deletion (known since at least the mid 80s)
2. Various tracing systems that exploit extra information known to reference-counted systems e.g. Levanoni/Petrank[1] which actually implemented a reference counted GC for Java.
There are three primary performance penalties for reference counting:
1. This, where dropping one link causes a deallocation chain.
2. A typical heap implementation will leave live objects scattered throughout memory, leading to cache issues.
3. Maintaining the reference counts may cause writes to memory, leading to other cache issues, plus atomicity.