Hacker News Reader

Comparing to malloc and free directly isn't very useful because that's pretty much the worst way to manage memory. Aside from memory arenas, you can just pool memory or preallocate too. I think concurrent data structures have very niche usage in practice (compared to say, a thread safe system).

>> cache line misses hurt.

> What does that have to do with GCs?

Everything. Sure you can use a copying GC and hope related objects go together. I tell the compiler to lump them together and exploit the prefetcher wherever possible.

> I tell the compiler to lump them together and exploit the prefetcher wherever possible.

That's a memory layout issue. What does a GC have to do with that? .NET and Go already allow good memory layout control, and Java will, too, once it gets value types. Conversely, one could create a manually-managed language that doesn't support object/array embedding, either. Memory layout control and GCs are completely orthogonal issues.

I really dislike the comparisons of TLAB to stack allocation. Stack, by its nature, is going to be hot in cache. TLAB, once filled up, will be retired and possibly assigned to a different thread. But even if it's not assigned, it's constantly moving forwards, and not revisiting the same space. You'd need prefetch to be perfect, and then on top of that, you'd need to make sure that by the time you go to allocate again, the prefetched cachelines have not been evicted.

Languages/platforms with a GC should still use, support, and encourage stack allocation for temporary memory -- this is your TLAB!

There is a cost to traversing references; card marking and generational collectors just reduce the amount of references you need to visit, but it doesn't mean reference chasing isn't requiring extra instructions. Finally, don't forget that card marking requires write barriers, which is extra instructions (and possible cache misses) on each reference store (modulo trivial ones, such as new allocations, where JIT knows it's not required).

While everything you say is 100% true, it is also a second-order effect, with a much lower magnitude than the primary GC performance behavior for short-lived objects.

Obviously stack allocation is preferable to TLAB allocation (and there's no reason to allocate objects with stack scope on the heap), if only for the fact that it never triggers a collection. Nevertheless, Java allocation/collection of short-lived object is much closer in cost to stack allocation than to malloc/free.

I'm not sure memory locality effects can be considered secondary, unless their effects are completely dwarfed by something else the app is doing (e.g. there's no point in discussing this topic for i/o bound workloads).

I don't think malloc/free should enter this conversation because languages that use malloc/free do so very infrequently, and for the cases where dynamic memory needs to be allocated frequently, they use specialized memory managers within the application. This is also subject to which allocator is used and what the application's allocation pattern is. There're suboptimal GC mechanics as well in some cases, such as CMS tenured space using free chunk lists with no compaction, so any young GC that requires promotion can possibly increase the young GC time because the GC needs to find appropriate free block size, and if there's fragmentation, this may take a while. Point being is that malloc/free vs GC isn't quite as clear cut on its own, nevermind that malloc/free aren't called that often. Generally speaking, though, if you can give GC ample headroom in terms of RAM, it'll have better throughput than incessant malloc/free use (which, I argue, is rare in properly written applications).

> I'm not sure memory locality effects can be considered secondary

What is secondary isn't the TLAB/stack performance ratio, but that ratio vs malloc/TLAB.

Also, I'm not sure why you think locality matters much here in the case of stack reuse. Within each frame, the stores always come first, and those go in the store buffer (and the reads are from the store buffer, too), so those are pretty benign cache misses.

> which, I argue, is rare in properly written applications

Sure, it is rare in "well written applications", but how costly is it to write a well-written application in a large team, and how much extra performance can you get? Remember, we're not talking about a DSP, a microcontroller or a net router when we're discussing GCs, but big, complex applications. Nobody is claiming you can't beat a GC given enough work (though it's harder the more concurrency is involved).

Also, think about what kind of data we're talking about. The interesting data is database data, and that has both arbitrary lifetime as well as concurrent read/write. And if you don't use malloc/free, at best you need to write your own manual memory allocator which is just as complex, and at worst you basically need to write your own GC.

Ok, we keep talking about malloc -- which malloc impl are you specifically referring to? There are many allocators out there these days, so let's be a bit more concrete. If not specific name, at least the class of allocator. Most of the common ones you'll find support thread-local allocation buffers, for starters.

>Sure, it is rare in "well written applications", but how costly is it to write a well-written application in a large team, and how much extra performance can you get?

>Also, think about what kind of data we're talking about. The interesting data is database data, and that has both arbitrary lifetime as well as concurrent read/write. And if you don't use malloc/free, at best you need to write your own manual memory allocator which is just as complex, and at worst you basically need to write your own GC.

If we're going to talk about databases, then "well-written" better be one of the top concerns, and team size should be irrelevant to that. And the more mechanically sympathetic of a product you're building (and db's are right up there in pretty much all aspects: cpu, i/o, net, mem, etc), the more you need to have control over those resources.

Have you, for example, looked at how postgresql manages memory? sqlite? redis? memcached? nginx? varnish? And, as I mentioned in the other reply, most of the big data java solutions end up rolling their own off-heap mem management infra using the same techniques as you'd use without GC.

> Most of the common ones you'll find support thread-local allocation buffers, for starters.

And what about concurrent deallocation?

> Have you, for example, looked at how postgresql manages memory? sqlite? redis? memcached?

Not too well (basically lots and lots of locking, much of it is very coarse-grained). Our spatial in-memory Java database (SpaceBase) offers an order-of-magnitude better performance in concurrent usage (and much better scalability with core number). We do over 200K transactions (with lots of contention) per second on a single 4-core laptop without breaking a sweat (concurrently with the application itself), and over a million on a large server (with some careful tuning).

But even for less super-concurrent databases, C++ databases don't outperform Java ones. In this benchmark, the Java databases (H2 and HSQLDB) almost always outperform MySQL and Postgres: http://www.h2database.com/html/performance.html (and I don't even know how the Java solutions handle concurrency, whether they do locking, optimistic locking or a clever combination, like SpaceBase).

In both cases, the amount of effort put into the Java solutions is orders of magnitude less than the C/C++ solutions.

> nginx? varnish?

Those are (virtually) read-only use cases. That is very easy to do concurrently no matter how you manage concurrency. The trick is concurrent writes, not reads.

> But even for less super-concurrent databases, C++ databases don't outperform Java ones. In this benchmark, the Java databases (H2 and HSQLDB) almost always outperform MySQL and Postgres: http://www.h2database.com/html/performance.html (and I don't even know how the Java solutions handle concurrency, whether they do locking, optimistic locking or a clever combination, like SpaceBase).

It's hardly surprising that a vendor's own benchmark shows it as winning against the competition.

Let's suppose for a second that the numbers are biased in the Java databases' favor. I doubt that other benchmarks would show such dramatically different results that would have those databases losing by much. So maybe they're not ahead as those number show (though I have little reason to doubt them), but a little behind. The difference would still not justify the claim that C++ provides superior performance for databases.

Also, it's an open source database with no commercial support by the authors, so I wouldn't really call them "vendors".

A stupid question: what's TLAB?

Thread local allocation buffer.

I have to completely disagree. Generation GC beats malloc/free in the case of 'all objects allocated on the heap' when: sizeof(survivors) + cost of traversing survivors pointer fields + rewriting the remembered set < traversing malloc/free trees for allocation/freeing.

Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live objects there can be identified. I. E. For the stack, all "Global" variables, and the set of marked cards/(The record of objects updated with old to new references) : Find all live objects, copy them into the next arena while rewriting references.

Oh, were write barriers that not mentioned? Generation GC requires write barriers. Every update through a pointer unless provably required by a compiler turns "a->b = c"; into "if(b is in generational region) { record update of b;} a->b = c".

If you want to be able to move objects arounds cheaply, writes through pointers transform into small subroutines. For some GCs, reads through pointers are also small subroutines.

And some Generational GCs do card marking over object marking. Let's traverse $CHUNKOFMEMORY on the probabilistic notion that if something was updated, something close by was updated. (Otherwise we can have Sequential Store Buffers which record exactly which objects were changed)

Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas.

Full disclosure: Despite my whining about GCs, I did do my Phd in them.

You mean sizeof(survivors whose references changed since last collection). You pay for those write barriers for a reason.

> Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas.

I agree, but on large servers with lots of RAM, the total amount of memory that can possibly be managed on stacks is < 3% of total RAM. What do you do then? Most of the RAM will be filled with database data, with arbitrary lifetime and concurrent access for both reads or writes, because that's precisely the kind of data that would most significantly help the program's performance if it's in RAM.

Now you can say that with all that data in RAM, the GC heap is a huge waste of RAM and the worst-case GC pause would be terrible, to which I say (I write in-memory databases in Java) that most of that data is user data and is kept off heap. Its lifetime is indeed arbitrary, but objects are deleted precisely when the user chooses to delete them, and that happens when they're protected by a lock. The much more interesting data is the indices, for which a GC helps greatly by allowing optimistic locking and other forms of scalable concurrency, and only those are kept on the heap.