GC Tuning Confessions of a Performance Engineer(slideshare.net)
slideshare.net
GC Tuning Confessions of a Performance Engineer
http://www.slideshare.net/MonicaBeckwith/gc-confessions
96 comments
Having worked with all sorts of GCs in the past, I basically stopped using them altogether some years ago in favor of manual memory management. I have to say, it's been liberating and so much easier to write performant code since I know what memory I need instead of relying on the computer to guess (and giving the computer hints as to how to guess). I have no doubt that GC research and systems is making good forward progress, but I can't imagine myself using them again.
Manual memory management only works in small teams with highly skilled developers, and even then there is a reason why so many CVE exploits are related to memory corruption.
Even those highly skilled developers aren't failure prof.
Even those highly skilled developers aren't failure prof.
Manual memory management (i.e. not GC) is a little disingenuous because it implies that it's entirely manual. In fact, there are many patterns (e.g. RAII) which make "brain dead" manual memory management possible.
I'm not necessarily arguing this is a great way to go for a new team, but there are manual memory management strategies that can definitely scale. Among other things, it's not the only type of resource that needs managing, and GC only handles memory.
I'm not necessarily arguing this is a great way to go for a new team, but there are manual memory management strategies that can definitely scale. Among other things, it's not the only type of resource that needs managing, and GC only handles memory.
Agreed. Sometimes, you don't even need RAII. You just let the stack unwind :)
But yes, RAII can make it pretty braindead (which is good)
But yes, RAII can make it pretty braindead (which is good)
Do you have any book suggestions for learning modern C++ memory management techniques? I'm beginning to think maybe it's time to fill that gap in my programming knowledge.
Hmm, modern C++ memory management is not entirely different from before. You have std::unique_ptr which is a game changer. I recommend just learning the language itself well. The C++ Primer (latest edition) plus Effective Modern C++ would be a good start. Also, read that doc floating around about everything a programmer needs to know about memory.
Or arena allocation - which, by the way, is something I wish was more supported in mainstream languages
Man, the new generation of programmers are going to be in bad shape if the thought of stack unwinding or managing the heap yourself is left to the "highly skilled." Even if I was interviewing someone who only worked in a memory-managed language, I would hope that they'd at least be capable of understanding how to code without it.
These should be the fundamentals.
These should be the fundamentals.
Well I started coding in 1986, and have seen quite a few screw ups.
So yeah, small teams it works great.
Now scale that to developer teams > 30 on average, with high turnaround and multiple outside partners coming and going on project basis.
I have seen what off-shoring does to C and C++ code bases...
So yeah, small teams it works great.
Now scale that to developer teams > 30 on average, with high turnaround and multiple outside partners coming and going on project basis.
I have seen what off-shoring does to C and C++ code bases...
How many engineers work on, say, the Unreal Engine. The linux kernel? Windows? Do you think any of that stuff would work even marginally well running on the JVM (assuming the JVM had native driver support)?
I don't quite follow your claims, nor do I put any stock in the tenure of your programming career.
As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programming language.
I don't quite follow your claims, nor do I put any stock in the tenure of your programming career.
As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programming language.
> How many engineers work on, say, the Unreal Engine. The linux kernel? Windows?
So you just provided me examples where developers tend to be highly skilled just to get a foot in the door.
Yet, the CVE list gets updated regularly with memory corruption exploits for them.
https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=double+free
Or if you prefer, just for Linux
https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=linux+doubl...
> Do you think any of that stuff would work even marginally well running on the JVM (assuming the JVM had native driver support)?
Actually, are you aware that some military weapon systems are being driven with JVMs?
Anyway automatic memory management doesn't mean automatically a JVM, there are quite a few other ways.
Another fun fact, Unreal Engine and Windows are written mostly in C++. A language considered too bloated and slow to be usable for anything serious by mainstream developers in the early 90's.
Also both use automatic memory management on their systems. Unreal has a kind of GC library. Windows nowadays has COM almost everywhere with reference counting.
> I don't quite follow your claims, nor do I put any stock in the tenure of your programming career.
Apparently some well known Fortune 100 companies and research institutes had another opinion.
> As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programming language.
The point being that those projects tend to go for cheap developers, so no, not everyone can deal with manual memory management.
So you just provided me examples where developers tend to be highly skilled just to get a foot in the door.
Yet, the CVE list gets updated regularly with memory corruption exploits for them.
https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=double+free
Or if you prefer, just for Linux
https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=linux+doubl...
> Do you think any of that stuff would work even marginally well running on the JVM (assuming the JVM had native driver support)?
Actually, are you aware that some military weapon systems are being driven with JVMs?
Anyway automatic memory management doesn't mean automatically a JVM, there are quite a few other ways.
Another fun fact, Unreal Engine and Windows are written mostly in C++. A language considered too bloated and slow to be usable for anything serious by mainstream developers in the early 90's.
Also both use automatic memory management on their systems. Unreal has a kind of GC library. Windows nowadays has COM almost everywhere with reference counting.
> I don't quite follow your claims, nor do I put any stock in the tenure of your programming career.
Apparently some well known Fortune 100 companies and research institutes had another opinion.
> As for the off-shoring point, off-shoring is going to create questionable quality code regardless of the programming language.
The point being that those projects tend to go for cheap developers, so no, not everyone can deal with manual memory management.
> So you just provided me examples where developers tend to be highly skilled just to get a foot in the door.
Yep these are people I want to work with :)
> Yet, the CVE list gets updated regularly with memory corruption exploits for them
Security is not the concern of every piece of software. You can harden the pieces you care about. Honestly, not all of us are doing crypto, and for that, the recommendation is to leverage an existing library and sandbox it anyways (regardless of memory management strategy).
> Actually, are you aware that some military weapon systems are being driven with JVMs?
God help them
> Another fun fact, Unreal Engine and Windows are written mostly in C++. A language considered too bloated and slow to be usable for anything serious by mainstream developers in the early 90's.
I was developing in C and C++ in the 90s. C++ is a strict subset of C. The criticisms made no sense then and they make no sense now. C++03 was arguable an small incremental improvement over C++98 but C++11 is a huge step function in usability without sacrificing performance (which Rust has taken many good cues from). The point is, if something bad is happening, I can look at the dissassembly and see exactly what's going on. I can't do this with Java, Python, Ruby, etc.
> Also both use automatic memory management on their systems. Unreal has a kind of GC library. Windows nowadays has COM almost everywhere with reference counting.
The scripting engine in Unreal supports GC if you want it. It's trivial to embed Lua or something. That's part of the point. For the non-performance sensitive bits, sure do whatever. The COM interface is terrible, and a necessary evil for those in the industry. There's a reason DirectX12 is looked forward to. I don't want Windows reference counting my things any more unless I tell it to.
> Anyway automatic memory management doesn't mean automatically a JVM, there are quite a few other ways.
... yes, I honestly can't imagine anyone in this thread would think otherwise. Heck, I've written a GC for a homebrew scripting language.
> Apparently some well known Fortune 100 companies and research institutes had another opinion.
My point is that how long you worked is sort of irrelevant in an actual academic discussion. Where you worked is just as irrelevant.
Yep these are people I want to work with :)
> Yet, the CVE list gets updated regularly with memory corruption exploits for them
Security is not the concern of every piece of software. You can harden the pieces you care about. Honestly, not all of us are doing crypto, and for that, the recommendation is to leverage an existing library and sandbox it anyways (regardless of memory management strategy).
> Actually, are you aware that some military weapon systems are being driven with JVMs?
God help them
> Another fun fact, Unreal Engine and Windows are written mostly in C++. A language considered too bloated and slow to be usable for anything serious by mainstream developers in the early 90's.
I was developing in C and C++ in the 90s. C++ is a strict subset of C. The criticisms made no sense then and they make no sense now. C++03 was arguable an small incremental improvement over C++98 but C++11 is a huge step function in usability without sacrificing performance (which Rust has taken many good cues from). The point is, if something bad is happening, I can look at the dissassembly and see exactly what's going on. I can't do this with Java, Python, Ruby, etc.
> Also both use automatic memory management on their systems. Unreal has a kind of GC library. Windows nowadays has COM almost everywhere with reference counting.
The scripting engine in Unreal supports GC if you want it. It's trivial to embed Lua or something. That's part of the point. For the non-performance sensitive bits, sure do whatever. The COM interface is terrible, and a necessary evil for those in the industry. There's a reason DirectX12 is looked forward to. I don't want Windows reference counting my things any more unless I tell it to.
> Anyway automatic memory management doesn't mean automatically a JVM, there are quite a few other ways.
... yes, I honestly can't imagine anyone in this thread would think otherwise. Heck, I've written a GC for a homebrew scripting language.
> Apparently some well known Fortune 100 companies and research institutes had another opinion.
My point is that how long you worked is sort of irrelevant in an actual academic discussion. Where you worked is just as irrelevant.
> Yep these are people I want to work with :)
Which comes back to my point that only developers able to get hired at that level are able to do manual memory management in large scale.
And even then, they resort to automatic memory management at higher levels in their stacks.
> I can look at the dissassembly and see exactly what's going on. I can't do this with Java, Python, Ruby, etc.
Just get a commercial JVM compiler, JIT Watch, Intel Amplifier. All of them provide the option to show the generated machine code.
> There's a reason DirectX12 is looked forward to. I don't want Windows reference counting my things any more unless I tell it to.
Better stop developing for Windows then.
The Universal Windows Application model is the continuation of WinRT, an evolution of COM.
In case you missed the note, DirectX 12 is still based on COM.
Also the new User Driver Model is based on COM.
Which comes back to my point that only developers able to get hired at that level are able to do manual memory management in large scale.
And even then, they resort to automatic memory management at higher levels in their stacks.
> I can look at the dissassembly and see exactly what's going on. I can't do this with Java, Python, Ruby, etc.
Just get a commercial JVM compiler, JIT Watch, Intel Amplifier. All of them provide the option to show the generated machine code.
> There's a reason DirectX12 is looked forward to. I don't want Windows reference counting my things any more unless I tell it to.
Better stop developing for Windows then.
The Universal Windows Application model is the continuation of WinRT, an evolution of COM.
In case you missed the note, DirectX 12 is still based on COM.
Also the new User Driver Model is based on COM.
Yea still COM based but part of what is being removed is a huge swath of underlying automatic reference counting for a huge number of things. Constant buffers resources etc.
Sure you can look at machine code generated from a virtualized language but I'd have a tough time understanding it in the context of the whole runtime, let alone being able to practically do anything about it.
Sure you can look at machine code generated from a virtualized language but I'd have a tough time understanding it in the context of the whole runtime, let alone being able to practically do anything about it.
> Sure you can look at machine code generated from a virtualized language but I'd have a tough time understanding it in the context of the whole runtime, let alone being able to practically do anything about it.
It is no different than using -S and check what happens for several code patterns.
It is no different than using -S and check what happens for several code patterns.
Look man, I don't know what to tell you except that you view code fundamentally differently. My point is that yes, obviously everything gets turned into x64/x86 assembly at some point, and that yes, I'm sure seeing it is very easy. But if I need to prevent a GC pause from happening at some point in the frame my hands are tied. Debating this is like pulling teeth, and I'm inclined to say that if you can't follow at this point, just use your GC everywhere.
This whole thread started by my statement that I haven't seen large projects without errors doing manual memory management.
I doubt very seriously that anyone can write code in large teams where Valgrind will state there aren't double frees, bad frees, or dangling pointers happening.
Or a run with Coverity will state everything is nice and shinning.
Once upon a time I had to write a tool in a well known particle accelerator research institute to track down C++ memory errors in a multi-thread environment for cluster algorithms used in data analysis. As one common problem on that specific team was plugins bringing the cluster down due to memory corruption.
So I also do know one or two things about manual memory management.
And with what I know, I rather use automatic memory management, be it in the form of GC, RC, affine types or dependent types.
I doubt very seriously that anyone can write code in large teams where Valgrind will state there aren't double frees, bad frees, or dangling pointers happening.
Or a run with Coverity will state everything is nice and shinning.
Once upon a time I had to write a tool in a well known particle accelerator research institute to track down C++ memory errors in a multi-thread environment for cluster algorithms used in data analysis. As one common problem on that specific team was plugins bringing the cluster down due to memory corruption.
So I also do know one or two things about manual memory management.
And with what I know, I rather use automatic memory management, be it in the form of GC, RC, affine types or dependent types.
I think we will start to see less use of GCs in mobile going forward, especially now that Apple has deprecated GC in favor of automatic reference counting. The issues caused by the interaction between the memory hierarchy and the fragmentation that is naturally introduced by GC are difficult to measure, but nevertheless an important component of performance.
Lets not forget they did that, because they failed to produce a stable working GC for Objective-C.
Reference counting is still not the same as manual memory management, and there is a heavy cost to reference counting as well. Reference counting trades throughput for latency relative to a garbage collected runtime.
I love GCs. They give you better memory throughput (in exchange for more footprint and higher latency, although latency can be made rather low), and they let you build and use very scalable concurrent data structures. On large machines with lots of cores and lots of RAM, they let you work with large, in-memory data sets very efficiently.
You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores and lots of RAM just means you can eat the cost more easily. It just means you can afford to let the VM do the work instead of the programmer.
Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.
Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.
> You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such.
That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost.
When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC.
> cache line misses hurt.
What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.
That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost.
When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC.
> cache line misses hurt.
What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.
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.
>> 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.
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).
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.
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 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.
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.
>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.
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.
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".
Also, it's an open source database with no commercial support by the authors, so I wouldn't really call them "vendors".
[deleted]
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.
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.
> 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.
The pragmatic solution is to write the critical parts of the code either completely allocation-free or using some kind of automatic memory management. To write large amounts of boilerplate and non performance sensitive code using manual memory management is likely time that could be better spent elsewhere. Similarly, tweaking a compute intensive part of a CLR/Jvm/Python/ruby program to fix GC performance is probably more work than just rewriting that particular piece of code with allocations in mind, in C if necessary.
The great thing about stack unwinding and constructor/destructor semantics is that they are automatic. Except they are done at compile time instead of runtime.
Write the performance critical system that needs to do the bookkeepping. Then write the easy stuff on top of that.
Write the performance critical system that needs to do the bookkeepping. Then write the easy stuff on top of that.
As with everything in engineering, this is a tradeoff. Not all access patterns work well with mark-and-sweep (or equivalent full traversal patterns). In particular, without needing to release or allocate memory, a GC pass wastes cycles. Furthermore, data structures must be compatible with the GC: traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running.
Generational garbage collection helps this, but for large numbers of pointers, you're going to see performance decrease unless at some point you move the pointers out of collection contention--think an allocation pool to reduce the depth of traversal early. I believe google just released a library to help with this, though the semantics are specific enough you could easily make your problems much worse.
GC is never a flat win.
Generational garbage collection helps this, but for large numbers of pointers, you're going to see performance decrease unless at some point you move the pointers out of collection contention--think an allocation pool to reduce the depth of traversal early. I believe google just released a library to help with this, though the semantics are specific enough you could easily make your problems much worse.
GC is never a flat win.
> traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running.
That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking).
I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (that can be mitigated).
That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking).
I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (that can be mitigated).
A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.
Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.
You could but it's likely to perform worse for common case. Where are you going to record the addresses? How are you going to size that buffer? Card table is fixed size, and doesn't care whether you're using compressed pointers or full blown word sized ones. Cards also benefit from cache locality if recording objects in the same card. Marking a card clean is dirt cheap, and incremental cleaning is cheaper than removing entries individually from an exact buffer.
The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.
The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.
That's why I said proportional.
> Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking).
True. I was just trying to make the point that GC comes with complexity cost, and this should be considered—it's not "free" for an arbitrary algorithm.
True. I was just trying to make the point that GC comes with complexity cost, and this should be considered—it's not "free" for an arbitrary algorithm.
Not to mention that you get to hire performance engineers.
People may have overestimated their utility (that they are good for less things then commonly thought). Maybe not to the degree that the stereotypical C/++ would believe, but still an overestimation.
Maybe we just need to use more abstractions in the middle between manual and fully automatic memory management, like region-based memory management (just an example).
People may have overestimated their utility (that they are good for less things then commonly thought). Maybe not to the degree that the stereotypical C/++ would believe, but still an overestimation.
Maybe we just need to use more abstractions in the middle between manual and fully automatic memory management, like region-based memory management (just an example).
I think the solution is to use the right memory management tool for the job. pron is right that GC can be helpful for concurrent data structures (where the non-GC approach, hazard pointers, is basically just a GC), for instance. GC is also great when your objects have truly dynamic lifetime, such as open files in Unix from the kernel's point of view. But GC for all data tends to be overkill when your goal is to maximize performance: a pure number-crunching workload like a triangle rasterizer has no need for GC, since the memory management is so trivial that it's better for the programmer to manually specify it (and, ideally, have the compiler check that) than for the program to spend cycles figuring it out at runtime. So, in my view, the best memory management discipline is a flexible one that allows the choice between automatic and manual memory management on a case-by-case basis.
I think we should look at the problem the other way around: it is manual memory management that is overkill because there are exactly four kinds of object memory scope:
* stack scope * transaction scope (for some definition of transaction -- it can be, say, a frame in a game, or a request in a web server) * arbitrary (database or any shared data structure) * permanent
For the stack scope, we have the stack. For the arbitrary scope, a GC is invaluable. For the permanent scope, it doesn't matter too much whether you have a GC or not (yes, vitalyd is going to mention traversals, but if the traversals are interesting, they point to objects in the arbitrary cost anyway). This leaves us the transaction cost. Now, I think it is far easier to manage a stack scope in a GCed environment than an arbitrary scope in a manual environment, and, in fact, some GCs, such as HotSpot's G1 should (yes, vitalyd, it doesn't always work) figure out the tranaction boundary automatically, but even if they don't, it's fairly easy to get that functionality with object pooling. However, to get the absolute best we shouldn't add a GC to a manually managed environment, but add arena collections to a GCed environment, which is exactly what RTSJ (realtime Java) does with scoped memory (making sure there are no references from potentially longer scopes into the arena).
To sum up, for the absolute best performance, a GCed environment + arenas has all you need. There is absolutely no need for a per-object malloc/free, and reference counting is neither here nor there (contention, cycles).
* stack scope * transaction scope (for some definition of transaction -- it can be, say, a frame in a game, or a request in a web server) * arbitrary (database or any shared data structure) * permanent
For the stack scope, we have the stack. For the arbitrary scope, a GC is invaluable. For the permanent scope, it doesn't matter too much whether you have a GC or not (yes, vitalyd is going to mention traversals, but if the traversals are interesting, they point to objects in the arbitrary cost anyway). This leaves us the transaction cost. Now, I think it is far easier to manage a stack scope in a GCed environment than an arbitrary scope in a manual environment, and, in fact, some GCs, such as HotSpot's G1 should (yes, vitalyd, it doesn't always work) figure out the tranaction boundary automatically, but even if they don't, it's fairly easy to get that functionality with object pooling. However, to get the absolute best we shouldn't add a GC to a manually managed environment, but add arena collections to a GCed environment, which is exactly what RTSJ (realtime Java) does with scoped memory (making sure there are no references from potentially longer scopes into the arena).
To sum up, for the absolute best performance, a GCed environment + arenas has all you need. There is absolutely no need for a per-object malloc/free, and reference counting is neither here nor there (contention, cycles).
> yes, vitalyd is going to mention traversals, but if the traversals are interesting, they point to objects in the arbitrary cost anyway
I'm going to mention this too. I don't understand what you mean by "they point to objects in the arbitrary cost anyway". The fact of the matter is that you have to trace all objects at some point.
> Now, I think it is far easier to manage a stack scope in a GCed environment than an arbitrary scope in a manual environment, and, in fact, some GCs, such as HotSpot's G1 should (yes, vitalyd, it doesn't always work) figure out the tranaction boundary automatically, but even if they don't, it's fairly easy to get that functionality with object pooling.
Object pooling is just a (limited, error-prone, poorly-performing) form of manual memory management.
> reference counting is neither here nor there (contention, cycles).
Contention isn't a problem if you don't touch the reference counts much. Cycles aren't a problem if you don't have cycles.
I'm going to mention this too. I don't understand what you mean by "they point to objects in the arbitrary cost anyway". The fact of the matter is that you have to trace all objects at some point.
> Now, I think it is far easier to manage a stack scope in a GCed environment than an arbitrary scope in a manual environment, and, in fact, some GCs, such as HotSpot's G1 should (yes, vitalyd, it doesn't always work) figure out the tranaction boundary automatically, but even if they don't, it's fairly easy to get that functionality with object pooling.
Object pooling is just a (limited, error-prone, poorly-performing) form of manual memory management.
> reference counting is neither here nor there (contention, cycles).
Contention isn't a problem if you don't touch the reference counts much. Cycles aren't a problem if you don't have cycles.
> I'm going to mention this too.
What I mean is that either those refs are permanent -- in which case they won't be traced -- or arbitrary -- in which case it's really more of an "arbitrary" problem than a "permanent" one.
> Object pooling is just a (limited, error-prone, poorly-performing) form of manual memory management.
... And reference counting is just a (limited, error-prone, poorly-performing) form of garbage collection.
> Contention isn't a problem if you don't touch the reference counts much. Cycles aren't a problem if you don't have cycles.
But now you've added restrictions that are much more onerous than those of object-pools.
In any case, my main question is this: if absolute top performance is what you need, why not have a GC + arenas (like RTSJ) without ref counting/manual management? In my opinion, there's only one downside to that approach is RAM footprint. If that's your answer, then I agree (I think that that's pretty much the main reson not to use a GC).
What I mean is that either those refs are permanent -- in which case they won't be traced -- or arbitrary -- in which case it's really more of an "arbitrary" problem than a "permanent" one.
> Object pooling is just a (limited, error-prone, poorly-performing) form of manual memory management.
... And reference counting is just a (limited, error-prone, poorly-performing) form of garbage collection.
> Contention isn't a problem if you don't touch the reference counts much. Cycles aren't a problem if you don't have cycles.
But now you've added restrictions that are much more onerous than those of object-pools.
In any case, my main question is this: if absolute top performance is what you need, why not have a GC + arenas (like RTSJ) without ref counting/manual management? In my opinion, there's only one downside to that approach is RAM footprint. If that's your answer, then I agree (I think that that's pretty much the main reson not to use a GC).
>I'm going to mention this too. I don't understand what you mean by "they point to objects in the arbitrary cost anyway". The fact of the matter is that you have to trace all objects at some point.
I think he means that if you have object references, then those references are interesting for the application itself, and not just for the GC tracer. However, I don't buy this statement simply because, even if you elect to store things as references rather than interior allocs, your app will only pointer chase the things it cares about, whereas the GC tracer may chase pointers that your app wouldn't otherwise.
@Ron:
The "arbitrary" scope better not be really arbitrary since even GCs are typically tuned for the generational hypothesis: your objects better be either short lived or long lived, anything in between is likely to degrade GC performance. In fact, if you like at some of the big data java solutions, once they reach a certain heap size, GC starts killing them, and they end up building their own semi-hybrid solution of moving stuff off-heap, and then managing that memory themselves (using the exact same block/slab/arena allocation techniques being downplayed here!).
For things like databases where object lifetime is in the hands of the user, arena/slab allocators work just fine. The additional advantage here is that you rarely need to destroy just a single object somewhere, typically it's an entire blob of related stuff. Arena destruction is more efficient here than GC because it's it inherently has more context than GC (the engineer wrote it, afterall). Is it more challenging/harder to implement than simply punting to the GC? Probably yes. But if you run afoul of GC's ergonomics and/or need to start tuning the finer points of GC behavior (i.e. see above comment about most of the big data java projects hitting this wall), the time spent there may end up exceeding arena impl costs.
I think he means that if you have object references, then those references are interesting for the application itself, and not just for the GC tracer. However, I don't buy this statement simply because, even if you elect to store things as references rather than interior allocs, your app will only pointer chase the things it cares about, whereas the GC tracer may chase pointers that your app wouldn't otherwise.
@Ron:
The "arbitrary" scope better not be really arbitrary since even GCs are typically tuned for the generational hypothesis: your objects better be either short lived or long lived, anything in between is likely to degrade GC performance. In fact, if you like at some of the big data java solutions, once they reach a certain heap size, GC starts killing them, and they end up building their own semi-hybrid solution of moving stuff off-heap, and then managing that memory themselves (using the exact same block/slab/arena allocation techniques being downplayed here!).
For things like databases where object lifetime is in the hands of the user, arena/slab allocators work just fine. The additional advantage here is that you rarely need to destroy just a single object somewhere, typically it's an entire blob of related stuff. Arena destruction is more efficient here than GC because it's it inherently has more context than GC (the engineer wrote it, afterall). Is it more challenging/harder to implement than simply punting to the GC? Probably yes. But if you run afoul of GC's ergonomics and/or need to start tuning the finer points of GC behavior (i.e. see above comment about most of the big data java projects hitting this wall), the time spent there may end up exceeding arena impl costs.
> I think he means that if you have object references, then those references are interesting for the application itself, and not just for the GC tracer.
What I mean is that either those refs are permanent -- in which case they won't be traced -- or arbitrary -- in which case it's really more of an "arbitrary" problem than a "permanent" one.
> The "arbitrary" scope better not be really arbitrary since even GCs are typically tuned for the generational hypothesis
By arbitrary I mean long-lived (old-gen) but not permanent. In short: database data.
> For things like databases where object lifetime is in the hands of the user, arena/slab allocators work just fine.
What you are saying is that you never truly have arbitrary-lifetime objects, and I strongly disagree with that.
> the time spent there may end up exceeding arena impl costs.
Even if you're right about arenas (which I don't agree with), you believe that a runtime designed to target the vast majority of server software should force developers to figure out lifetimes and that that may be beneficial to them? I mean, I even mentioned arena just to get that much closer to 100% performance. Even without them Java gets to at least 90%. Are you suggesting that the vast majority of projects in the world are interested in doing more work that is likely error prone just to get that 10% at best?
What I mean is that either those refs are permanent -- in which case they won't be traced -- or arbitrary -- in which case it's really more of an "arbitrary" problem than a "permanent" one.
> The "arbitrary" scope better not be really arbitrary since even GCs are typically tuned for the generational hypothesis
By arbitrary I mean long-lived (old-gen) but not permanent. In short: database data.
> For things like databases where object lifetime is in the hands of the user, arena/slab allocators work just fine.
What you are saying is that you never truly have arbitrary-lifetime objects, and I strongly disagree with that.
> the time spent there may end up exceeding arena impl costs.
Even if you're right about arenas (which I don't agree with), you believe that a runtime designed to target the vast majority of server software should force developers to figure out lifetimes and that that may be beneficial to them? I mean, I even mentioned arena just to get that much closer to 100% performance. Even without them Java gets to at least 90%. Are you suggesting that the vast majority of projects in the world are interested in doing more work that is likely error prone just to get that 10% at best?
+1. This is why I'm so excited about GC libs in Rust (and am working on a GC myself with @mystor). Rust has a nice undertone about choosing your costs and your guarantees, and if it got a good GC* people would have a really complete ecosystem for memory management.
*so, not the one I'm working on :P
*so, not the one I'm working on :P
GC does help with ABA style concurrent problems, and it also simplifies the places where you simply don't care (slow/uncommon paths). But concurrent data structures are a special case, and likely, not always the best anyway since even though they scale much better than locks, with enough writers and cores, the cache coherence traffic is going to swamp the application.
I do agree with the flexibility comment. A hybrid environment where you can pick and choose the mem mgmt strategy (and, very important, not pay in perf for things you're not using) would be great.
I do agree with the flexibility comment. A hybrid environment where you can pick and choose the mem mgmt strategy (and, very important, not pay in perf for things you're not using) would be great.
> GC does help with ABA style concurrent problems
I wasn't just referring to that. GC helps with pretty much any concurrent data structure, lock-free or not. For example, read-write locks don't scale too well (certainly no beyond the core count we're quickly coming up against on servers), and GC enables easy optimistic locking.
I wasn't just referring to that. GC helps with pretty much any concurrent data structure, lock-free or not. For example, read-write locks don't scale too well (certainly no beyond the core count we're quickly coming up against on servers), and GC enables easy optimistic locking.
> I think the solution is to use the right memory management tool for the job.
That's like a generalization of my own argument. Generalized to the point where we are in the domain of truisms like "right tool for the job" (as opposed to what, the wrong tool for the job?).
That's like a generalization of my own argument. Generalized to the point where we are in the domain of truisms like "right tool for the job" (as opposed to what, the wrong tool for the job?).
Performance is nice, but correctness is more important. Complex programs written without any GC tend to have use-after-free and double-free vulnerabilities. Programs written using automatic reference counting only (without a way to catch cycles) tend to have memory leaks. If GC is killing performance, then that is a failure of the specific GC or programming language design. Don't blame the applications programmers for wanting GC semantics; that's a completely reasonable thing to want and something that language designers are capable of providing.
In the specific case of Java, I think the real problem is not having value objects (like C#'s struct) or generics with non-reference types. Serious GC problems happen not because GC is too hard, but because in Java an ArrayList<int> of a million items makes a million tiny objects. This problem is entirely Java-specific.
In the specific case of Java, I think the real problem is not having value objects (like C#'s struct) or generics with non-reference types. Serious GC problems happen not because GC is too hard, but because in Java an ArrayList<int> of a million items makes a million tiny objects. This problem is entirely Java-specific.
> This problem is entirely Java-specific.
Fully correct.
Back when Java was still in its infancy, we had Oberon(-2), Component Pascal and Modula-3 as system programming languages that allowed for C like memory allocation, coupled with a GC.
But Java was the one that made GCs finally go mainstream and now many equate GC with Java ones[0], thinking all GC are made alike.
[0] Forgetting in the process that Hotspot is just one JVM among many.
Fully correct.
Back when Java was still in its infancy, we had Oberon(-2), Component Pascal and Modula-3 as system programming languages that allowed for C like memory allocation, coupled with a GC.
But Java was the one that made GCs finally go mainstream and now many equate GC with Java ones[0], thinking all GC are made alike.
[0] Forgetting in the process that Hotspot is just one JVM among many.
> that's a completely reasonable thing to want and
> something that language designers are capable of
> providing.
Specifically about ArrayList<Integer> -- there are specifically a bunch of projects (Goldman Sachs Collections, trove, FastUtil, Koloboke) that solve the array of primitives problem.
I would say that's a Java-standard-libary-specific problem.
I would say that's a Java-standard-libary-specific problem.
And then you have to do a copy just to pass it around to any other external libraries. And you lose the advantages of generics.
You end up with 9 copies of everything, that are 99% the same except for a couple find-replaces. If not more. (For instance, if you have a method that takes two generic arrays, you need 81 copies! Even if they are the same type you still need 36 (!) copies.)
Not a good solution.
You end up with 9 copies of everything, that are 99% the same except for a couple find-replaces. If not more. (For instance, if you have a method that takes two generic arrays, you need 81 copies! Even if they are the same type you still need 36 (!) copies.)
Not a good solution.
How do you end up with 9 copies of everything? I'm not sure I follow that.
If you are passing in massive ArrayList<Integer> lists to external libraries, you need to re-evaluate what you're doing. What will that external library do with this?
If you are passing in massive ArrayList<Integer> lists to external libraries, you need to re-evaluate what you're doing. What will that external library do with this?
Look at java.util.Arrays for a concrete example of the problem:
Except that a relatively common thread goes like this:
You start by having a generic array that gets passed to said binary search. It works, but it's too memory-hungry when it gets called with a primitive. So, then what do you do?
Well, you go "huh, I could specialize". And then you start specializing, and realize that every function that calls binarySearch with a generic type also needs 8 implementations (would be 9, but no sane person would binary search a boolean[] ).
Basically, its complexity that you cannot even punt off to an external library. If you have code that needs to be able to be called with generics without inefficiencies for primitive types, you'll end up with ~9x code duplication at a minimum.
static int binarySearch(byte[] a, byte key)
static int binarySearch(char[] a, char key)
static int binarySearch(double[] a, double key)
static int binarySearch(float[] a, float key)
static int binarySearch(int[] a, int key)
static int binarySearch(long[] a, long key)
static int binarySearch(Object[] a, Object key)
static int binarySearch(short[] a, short key)
Except that a relatively common thread goes like this:
You start by having a generic array that gets passed to said binary search. It works, but it's too memory-hungry when it gets called with a primitive. So, then what do you do?
Well, you go "huh, I could specialize". And then you start specializing, and realize that every function that calls binarySearch with a generic type also needs 8 implementations (would be 9, but no sane person would binary search a boolean[] ).
Basically, its complexity that you cannot even punt off to an external library. If you have code that needs to be able to be called with generics without inefficiencies for primitive types, you'll end up with ~9x code duplication at a minimum.
For some reason, GC is on of those areas that I have zero desire to learn sufficiently to tune. That's probably why OP has a successful career as a consultant.
When making tradeoffs in development, a simpler GC with predictable behavior is worth losing a lot of raw performance to me. Thus I find myself drawn to platforms like erlang/elixir or Haskell where GC is isolated.
I suppose the rational approach is build on Hotspot and when it becomes a problem hire a consultant for instant performance gains (assuming low hanging fruit is in abundance).
When making tradeoffs in development, a simpler GC with predictable behavior is worth losing a lot of raw performance to me. Thus I find myself drawn to platforms like erlang/elixir or Haskell where GC is isolated.
I suppose the rational approach is build on Hotspot and when it becomes a problem hire a consultant for instant performance gains (assuming low hanging fruit is in abundance).
Yeah that is why I like the BEAM VM as well. It is a really awesome piece of engineering build for massive concurrency and fault tolerance. It is nice to see the whole Elixir ecosystem take advantage of it.
That model of concurrency is important to reduce cognitive load on the programmer. Having concurrent units and mutable state isolated makes it much easier to understand what is going on, rather than having some large class or shared memory state modified from many code paths concurrently (maybe via callbacks, threads, signals, etc.)
That model of concurrency is important to reduce cognitive load on the programmer. Having concurrent units and mutable state isolated makes it much easier to understand what is going on, rather than having some large class or shared memory state modified from many code paths concurrently (maybe via callbacks, threads, signals, etc.)
In 80% of the cases, simple GC ergonomics (i.e. let HotSpot figure out the tuning) are more than ok, and in 95% of the cases, trivial tuning is enough.
The thing with Erlang is that the GC doesn't work on any shared memory data structure (like ETS), so you pretty much have to delegate any shared data to an out-of-process database, even in simple cases that are easily addressed with ConcurrentHashMap, ConcurrentSkipListMap/Set, or CopyOnWriteArrayList/Set on the JVM.
The thing with Erlang is that the GC doesn't work on any shared memory data structure (like ETS), so you pretty much have to delegate any shared data to an out-of-process database, even in simple cases that are easily addressed with ConcurrentHashMap, ConcurrentSkipListMap/Set, or CopyOnWriteArrayList/Set on the JVM.
Good point, but ETS is still managed and owned by a process. So it still can be cleaned up taken care of. Moreover at the API level ETS even behaves as if there is a process that manages data (even though implementation-wise it is all done in C).
Also in Erlang large binaries are not copied but shared as well.
And whether large shared data-structures are needed is dependent on the application. I imagine since you've done work with spatial relationships, in that case for anything interesting to happen data has to be indexed, shared, queried in one place. But say building a large concurrent chat or messaging application with many but small state machine actor that might have lots of peer to peer interaction, then shared data is not as crucial.
Also in Erlang large binaries are not copied but shared as well.
And whether large shared data-structures are needed is dependent on the application. I imagine since you've done work with spatial relationships, in that case for anything interesting to happen data has to be indexed, shared, queried in one place. But say building a large concurrent chat or messaging application with many but small state machine actor that might have lots of peer to peer interaction, then shared data is not as crucial.
I generally use an Agent in Elixir for anything shared and there's very little cognitive overhead (though perf does take a hit). Agent.cast/2 is helpful for low latency modifications (at the cost of losing back pressure).
As stated, it's a tradeoff.
As stated, it's a tradeoff.
But, if I'm not mistaken, an agent isn't concurrent. You make your shared data a bottleneck which is exactly what concurrent data strctcures are meant to prevent.
Shared memory data structures are rarely necessary. When one is, I would be willing to go the extra mile to facilitate it. Seems like a reasonable tradeoff.
The slides are interesting enough that I went looking to see if the actual talk that goes with them was online anywhere; found it at
http://chariotsolutions.com/screencast/philly-ete-2015-7-mon...
http://chariotsolutions.com/screencast/philly-ete-2015-7-mon...
presentation video: https://www.youtube.com/watch?v=PnPzeavMjmE
Interesting article. What I see is another failure of industry to solve the root of the problem: different GC strategies work for different applications and should be selectable. Might even allow pluggable GC's. This is the path taken in JX Operating System and certain academic works on improving Java runtime. JX's first tier of memory management just gives a certain amount of resources a component/process/app can use. The second tier is its GC, which can be different per application. So, you could partition your application into components with associated GC's that focused on throughput, low-latency, or productivity. Then the problem shifts to making an optimal scheduler for the app and GC runtimes. There's already good schedulers, strategies for building them, and even tools for automated planning of scheduling strategies. Any of these might be integrated to optimize that aspect.
Overall, using pluggable garbage collectors, feeding a planner some constraints, and compiling the result sounds much easier that this person's day job. Embedded Java already does some of this while some systems did it in hardware to avoid most issues entirely. Enterprise Java should adopt such a method. Meanwhile, reading of these nightmares, I'll continue avoiding such GC-based tools wherever possible in my work.
JX Operating System for reference http://www4.cs.fau.de/Projects/JX/publications/jx-usenix.pdf
Overall, using pluggable garbage collectors, feeding a planner some constraints, and compiling the result sounds much easier that this person's day job. Embedded Java already does some of this while some systems did it in hardware to avoid most issues entirely. Enterprise Java should adopt such a method. Meanwhile, reading of these nightmares, I'll continue avoiding such GC-based tools wherever possible in my work.
JX Operating System for reference http://www4.cs.fau.de/Projects/JX/publications/jx-usenix.pdf
I wonder, isn't it working on the stack much faster than working on the heap anyway?
So when you query data on the heap, shouldn't you just query larger objects to put it on the stack, and work from there, instead of using the heap so often ?
With that in mind wouldn't that render garbage collecting almost irrelevant if your code is well designed, by not working too much on the heap ?
It's true that more ram makes the GC more relevant, but if it's an excuse for negligent software design, maybe GCs are not such a good idea. It's good to have features that make the job of the programmer easier, but if it only save the time of the skilled programmers who knows a little about how it works underneath, is it such a good idea ?
You can hardly convince that simple tools and predictable behaviors in machines are not the safest way of having fair results.
A programming language is already a big shortcut to work faster, and I doubt you should try to work even faster if it means creating new drawbacks.
So when you query data on the heap, shouldn't you just query larger objects to put it on the stack, and work from there, instead of using the heap so often ?
With that in mind wouldn't that render garbage collecting almost irrelevant if your code is well designed, by not working too much on the heap ?
It's true that more ram makes the GC more relevant, but if it's an excuse for negligent software design, maybe GCs are not such a good idea. It's good to have features that make the job of the programmer easier, but if it only save the time of the skilled programmers who knows a little about how it works underneath, is it such a good idea ?
You can hardly convince that simple tools and predictable behaviors in machines are not the safest way of having fair results.
A programming language is already a big shortcut to work faster, and I doubt you should try to work even faster if it means creating new drawbacks.
The stack and the heap are both just regions of memory, so there's nothing inherently faster about using the stack. The difference is the memory management strategy: Usually, stack variables are all allocated at the beginning of a function, and all deallocated at the end. If all of the memory your program needs is tied to a particular scope like that, then it's certainly faster than any other memory-management strategy. If you need to share data between scopes, build complicated data structures of indeterminate compile-time size, or allocate large blocks of memory (the stack is usually limited in size), then you have to do something different (like use the heap).
That said, I think the Rust approach to memory management is really interesting: try to tie all allocated memory to some scope, and keep track of when ownership is borrowed by or moved to a different scope.
That said, I think the Rust approach to memory management is really interesting: try to tie all allocated memory to some scope, and keep track of when ownership is borrowed by or moved to a different scope.
The inherent benefit to the stack is the memory region stays hot in cache due to natural use of the stack. That's your fast reusable buffer for temporaries.
In addition, of course, cleanup/reclaim of the stack space is pointer bump, so you get pointer bump allocation and deallocation, effectively.
In addition, of course, cleanup/reclaim of the stack space is pointer bump, so you get pointer bump allocation and deallocation, effectively.
True, but you could do the same thing in any region of memory. The only thing that using "the stack" buys you is that there are a few special instructions to allocate / deallocate one machine word at a time (if you store the "top-of-heap" pointer in a specific register), and you get a bit more locality by virtue of return addresses being stored next to your locals and temporaries. (For x86 processors at least; maybe other architectures treat the stack in a more special way, I don't know.)
> True, but you could do the same thing in any region of memory. The only thing that using "the stack" buys you is that there are a few special instructions to allocate / deallocate one machine word at a time (if you store the "top-of-heap" pointer in a specific register)
This is pretty much what a TLAB is in Hotspot JVM, except of course the pointer never moves backwards (once the TLAB is filled up, it retires, and then can get assigned to a different thread to start allocating from the beginning). Each allocation into the TLAB moves allocations further into the region -- there's never any reuse until the TLAB starts afresh.
The stack locality comes from the rest of the stack execution mechanics keeping this region very warm, and the majority of the read/write action to the stack is localized (apart from large stack allocations that may temporarily expand the region's use).
This is pretty much what a TLAB is in Hotspot JVM, except of course the pointer never moves backwards (once the TLAB is filled up, it retires, and then can get assigned to a different thread to start allocating from the beginning). Each allocation into the TLAB moves allocations further into the region -- there's never any reuse until the TLAB starts afresh.
The stack locality comes from the rest of the stack execution mechanics keeping this region very warm, and the majority of the read/write action to the stack is localized (apart from large stack allocations that may temporarily expand the region's use).
Except that a TLAB is worse for cache than a stack.
Look at what happens when you call a bunch of small methods that each allocate a couple things. With a stack, everything stays in nice proximity automaticially. With a TLAB, you quickly fill the TLAB, get another one, get another one, and so on.
Effectively: the stack does any garbage collection that can be statically determined for free, keeping data in cache that actually matters, whereas with TLABs you need to wait for it to pass through GC before any of it is reused.
Look at what happens when you call a bunch of small methods that each allocate a couple things. With a stack, everything stays in nice proximity automaticially. With a TLAB, you quickly fill the TLAB, get another one, get another one, and so on.
Effectively: the stack does any garbage collection that can be statically determined for free, keeping data in cache that actually matters, whereas with TLABs you need to wait for it to pass through GC before any of it is reused.
Right, that's why it bothers me when TLAB and stack are compared.
I'm almost positive that x86 doesn't really have special stack instructions, aside from call (push pc +sizeof(call)) onto $esp and jump.
I know MIPS (and possibly other RISC architectures) don't have an implicit 'stack' register, just one that used by convention. They do have jump and link instructions which write $pc+4 into another register.
Afaik, LLVM and quite possibly GCC just add/subtract $esp for the initial allocation / final deallocation of the stack.
More recent intel x86 process I believe have a small separate d-cache for the stack.
I know MIPS (and possibly other RISC architectures) don't have an implicit 'stack' register, just one that used by convention. They do have jump and link instructions which write $pc+4 into another register.
Afaik, LLVM and quite possibly GCC just add/subtract $esp for the initial allocation / final deallocation of the stack.
More recent intel x86 process I believe have a small separate d-cache for the stack.
Garbage collection worries about reachability of objects, not of access patterns. Some GC setups may not apply read/write barriers to stack objects as they are not required.
The difficultly with stack centric working is that you have to ensure that any object produced that is put back into the heap only references heap objects. Otherwise, by any sane language/style definition, you've made a mistake in referencing stack objects from the heap.
Accesses to the stack or heap, except in very specific circumstances[1] are equal but allocation/deallocation process are widely different.
Avoiding introducing GC work has/(can have) the tendency to "fight the language" problems. Consider writing Haskell code that does not allocate on the heap for example, it's damn near impossible. Otoh a Java program can shift some heap allocations into stack allocations.
[1] Afaik, some intel processors have small dedicated D-caches from stack relative load/stores. On the order of 128 bytes. I am probably wrong though.
The difficultly with stack centric working is that you have to ensure that any object produced that is put back into the heap only references heap objects. Otherwise, by any sane language/style definition, you've made a mistake in referencing stack objects from the heap.
Accesses to the stack or heap, except in very specific circumstances[1] are equal but allocation/deallocation process are widely different.
Avoiding introducing GC work has/(can have) the tendency to "fight the language" problems. Consider writing Haskell code that does not allocate on the heap for example, it's damn near impossible. Otoh a Java program can shift some heap allocations into stack allocations.
[1] Afaik, some intel processors have small dedicated D-caches from stack relative load/stores. On the order of 128 bytes. I am probably wrong though.
Sure, but on modern servers, the amount of data you can put on the stack (or stacks) amounts to no more a few percent of RAM. The smartest thing you can do with the rest, is put as much of your DB data there, and that data has an arbitrary lifetime, and is read -- and written -- concurrently. So most of the memory activity on large servers is going to be on the heap. If you put on the stack everything that can be done on the stack, you've reduced your heap usage by, say, 2%. True, the kind of memory work on the stack and on the heap is very different, but the two problems are of entirely different magnitude and nature.
I think the reason many people say "just use the stack more", is that most people delegate the hard work to a DB, and let the DB engineers worry about using the heap well. But the best way to use a DB is if it is in memory and in process.
I think the reason many people say "just use the stack more", is that most people delegate the hard work to a DB, and let the DB engineers worry about using the heap well. But the best way to use a DB is if it is in memory and in process.
> I wonder, isn't it working on the stack much faster than working on the heap anyway?
Working on GC-managed memory is faster still.
Remember, not all allocations involve an actual heap allocation. Conversely, not all deletions cause a 'free()' operation on the heap.
Working on GC-managed memory is faster still.
Remember, not all allocations involve an actual heap allocation. Conversely, not all deletions cause a 'free()' operation on the heap.
> Working on GC-managed memory is faster still.
Care to elaborate?
Care to elaborate?
Replying to GP comment and you as such.
Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads.
This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform general heap allocations into thread local or stack allocations.
[1] Let me define reachability type as {can be accessed from anything, can be accessed from this thread only but is of indefinite lifetime, can be accessed from this thread only and it's reference is not take by any object allocated onto my local heap, ...}
Hypothetically, (I'm not sure how widespread this technique is), some (Java) compilers turn heap allocations into stack allocations when they can prove that transitively an allocated object does not become reachable from other threads.
This general technique "escape analysis", i.e. "a reference to this object /escapes/ a given reachability type[1]", can be used to transform general heap allocations into thread local or stack allocations.
[1] Let me define reachability type as {can be accessed from anything, can be accessed from this thread only but is of indefinite lifetime, can be accessed from this thread only and it's reference is not take by any object allocated onto my local heap, ...}
Hotspot JVM C2 compiler does this optimization, with varying degree of success but generally brittle and completely opaque. It doesn't actually stack allocate them technically speaking, just scalarizes them into registers. Should also mention that this requires sufficient inlining to take place at minimum (unfortunately, hotspot does not do flow sensitive analysis so any conditional logic that makes the object escape, even if not taken, will be regarded as escaping - graal handles this better), which doesn't always happen for a variety of reasons.
But what does this have to do with heap being faster than stack? This is doing roughly the same thing as a compiler that supports explicit stack allocations.
But what does this have to do with heap being faster than stack? This is doing roughly the same thing as a compiler that supports explicit stack allocations.
I don't see why people put so much work into GC before even bothering to do any work to avoid objects becoming garbage in the first place beyond simple escape analysis.