There is nuance here. They claimed that their project is faster than a specific hand optimized project. Not faster than a theoretical peak performance c++ program.
I've run into similar situations where python reimplementation s are faster than java because python is easier to change and fixup algorithms. And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java.
You also have people on rust subreddit or discourse asking for optimization help when their rust is not as fast as a Go example they wrote. Often you get buffered IO going and it's on par. But to melt faces like ripgrep and friends you often need to drop pretences and work on Vec<u8>s.
Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile".
With that said: yes, I've also seen Java programs that run faster than the Rust or C counterpart. I suspect what OP saw falls into this category: a rare example that you take as a rule (maybe I misinterpreted the claim, I admit, but it does sound OP meant his Haskell program and, I assume, others which you write in the same style, cannot be beaten by the equivalent C++).
You're right that the java tooling is powerful. But getting numbers out of the JVM is not the black magic. The dark arts are setting up an experiment, managing the JIT warm-up, and interpreting the results. In my experience it's just hell trying to turn those numbers into a convincing argument that we have confidence in our performance. Concrete example: convincing openjdk11 to use AES instructions Vs conscrypt using AES out of the box with no warm-up...
The whole song and dance means that we just don't take it as a priority because it's a tiring sink of effort. On the other hand %timeit is so easy and remains consistent that you can use it with unit tests and offer algorithm fixes in PRs.
shared_ptr and unique_ptr have pretty significant overhead and are common practice, even for optimized codebases, so I wouldn't say it's impossible at all.
shared_ptr is expensive and easy to build leaks with, so a lot of code bases avoid it where possible. Though it's only expensive when you copy it, moving it is ~free.
From what I've been told, C++ games do another thing and just use arena allocators, which make allocations cheap (just an integer addition, provided you know a reasonable upper bound on the size of an arena, and if you don't, you may reserve a large piece of virtual memory, and commit it later in reasonably small, but also not too large chunks) and free-s even cheaper (either reset the integer, so that the arena can be reused, or a single syscall to unmap the whole arena in one go). That's a different strategy than making a lot of little allocs and frees, and then trying to minimize them by reusing objects, which is also quite hairy.
It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.
fun replace_head_with_1 (_::xs) = 1::xs;
val a = [2, 3, 4];
val b = replace_head_with_1 a;
And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.
However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you will likely get a slightly better result than your GC algorithm.
Which is a very good reason to develop an optimized GC algorithm, the domain experts can crank out code without having to optimize every single memory (de)allocation which sounds like a waste of their time.
It’s funny, people don’t usually doubt that a modern compiler can do a better optimization job than an expert but add a memory management algorithm and that’s a bridge too far.
However, a GC is a lot slower than manual memory management, which contrasts with the fact that most compiler activities are actually pretty low in overhead (now - it didn't used to be this way). Really, the only cost overhead left is the abstraction mismatch, and that is not too bad, when you compare to how bad humans are at writing assembly.
That said, this case looks like one where the C++ experts spent very little time optimizing (mostly writing business logic), and probably made a very poor choice of tools.
There is a triangle of GC performance; througput, latency (i.e. pause length), and memory overhead. Manual memory management will often be slower (in the throughput sense) than a throughput-tuned GC because:
1. Manual memory management typically precludes moving live data
2. Manual memory management often frees data as soon as it is dead
GC will often have faster allocations than manual memory management because #1 makes it possible to just use a pointer-increment for allocation. GC will often have faster freeing of data because of #2; in particular using a nursery with Cheney's algorithm makes it O(1) to free an arbitrary amount of data.
Where a throughput optimized GC falls down is in that any code that allocates may have an unpredictable amount of delay.
Also note that for video games, both typical GC and malloc/free are often too slow for per-frame data, so arena allocators are used, which sidestep #2, and allow a pointer-increment allocation without needing #1. This is specifically because there are a lot of objects with exactly the same bounds on their lifetime. Special-purpose algorithms will almost always trump general-purpose algorithms when run on the workload they are optimized for.
extern void foo(T *p); // some arbitrary function
void bar1(bool cond)
{
..
auto p = std::make_unique<T, your_deleter>();
if (cond) { return foo(p.release()); }
...
}
void bar2(bool cond)
{
..
auto p = new T();
if (cond) { return foo(p); }
...
your_deleter()(p);
}
In an ideal world, though, you could have an optimizer smart enough to do that transformation automatically. C++ compilers already do that in trivial cases, but they can't do it in general. My impression is that their Haskell compiler exploits the internal knowledge of what your_deleter does (i.e. reference counting) in order to optimize the code in various ways, like optimizing out such code, consolidating refcount updates, etc. And if I understand this correctly, there's no surprise at all that it can be faster than idiomatic C++ code written even by experts.
The question for me isn't the expertise of their programmers. Perhaps in their case they genuinely do need to have lots of objects on the heap, have (say) tight loops where they (for whatever reason) nevertheless cannot avoid the heap allocations, and don't have much of a use for finalizers besides freeing memory. In which case, I'm not surprised their solution clearly delivers better results than the C++ equivalent. The question from me, instead, is how well they think that generalizes, such as to (a) well-written Haskell programs in general, (b) well-written C++ programs in general, and/or (c) other domains. It would be one thing if their solution delivers better results in Haskell than C++ for their use case; it would be another thing if they could claim their solution delivers better results in Haskell than C++ for most use cases.
This is a non-issue.
The point is that check itself is an extra instruction (or two, rather) that would otherwise be skipped entirely.
I'm not saying this commonly makes a difference. I'm just saying this might be something that does make a difference for them in their particular use case.
Also note that I was trying to describe the general phenomenon with a simple example, but this obviously isn't limited to std::unique_ptr.
Or you can do what Erlang does: Erlang has neither mutation nor laziness, so you can't create cycles. The GC also lays out object in topological order in memory, so that you can detect garbage without tracing every life object.
Though I’ve been hacking on a UI framework written in Nim. Its ui nodes form a tree structure that only tracks parent => child. When it needs the parent info it makes a stack of parents during processing.
Essentially it moves the cycle collector / GC work to extra work during processing. But it’s cheaper since you’re already accessing the memory.
I just prefer to write cycle free code when I can and turn off the cycle collector. Though Nim’s cycle collector performs well and does some tricks using the RCs.
It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
That only works when you have infinite memory (or infinite CPU resources).
> It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everything at some later point). When your memory is bounded, you will eventually have to stop/crash once you have run out of it.
AFAIK, the best modern state of art garbage collectors have stop-the-world pauses, proportional to size of root set and/or thread count. I'd love to see an RC implementation, that does not have stop-the-world pauses at all, but that sounds as audacious as claims of perpetual motion machine.
The Linux kernel uses RCU to manage data structures that are concurrently read and updated. When an old value (after an update) is no longer needed, a thread can either:
(a) block for a while to make sure no other thread is using it using synchronize_rcu() and then free the memory (see https://www.kernel.org/doc/html/latest/core-api/kernel-api.h...)
(b) if the thread cannot block, it will use call_rcu to register a callback to free the memory at a later time (https://www.kernel.org/doc/html/latest/core-api/kernel-api.h...). That callback generally runs in some other thread to do the cleanup.
Now, moving the concepts to user space, a typical user space implementation will just launch a dedicated thread to free all memory that is no longer needed by any RCU data structures.
You could go a bit further and have multiple concurrent threads mark the references, then sweep them up in a separate thread, too. Some sort of concurrent sweep and mark reference count system.
Alloc/free can introduce arbitrary pauses last I checked, so yes, there are pauses. Any time doing book keeping for resources rather than running your code counts as GC time.
Perhaps a nitpick: memory management time, yes, but not GC time.
alloc/free is manual memory management, not garbage collection.
More nitpicking: on x86-64, SMI interrupts can cause arbitrary pauses even without any software control involved. Hard realtime on x86-64 is not possible.
Orrrrr, GC pause just means pauses caused by the GC as part of its implementation's work to manage memory.
There appear to be two ways the terms are categorized:
1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation.
2. "reference counting" and "tracing garbage collection" are two types of garbage collection.
I think mbrodersen is using #1.
(Back in the 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)
Furthermore, pretty much every language has I/O, but that doesn't make the term useless.
Note that this mostly reflects automatic reference counting, like you have in Python or Swift, not so much manual reference counting like std::shared_ptr or Rc.