- Forum
- Lounge
- Garbage Collection - Why?
- Page 2
Garbage Collection - Why?
Whether they are faster or slower than lock-based algorithms depends on usage and platform (that article you linked correctly says "In some cases, lock-free approaches can bring performance benefit") |
I'm not discussing whether they are slower or faster. This is wrong question. The right question is what scales better. And lock-based algorithms don't scale well. Which means, given enough load and enough cores, they will be always slower than lockfree counterparts.
Whatever, I'm only pointing out that in C++ you've got limited choice. Basically you can't go lockless unless you code all the things from scratch. And coding them from scratch is 10x harder than in any GCed language, because basically you have to emulate some kind of a GC first, and it is *not possible* to implement a highly performant GC for C++.
What did you look at, forum posts? |
Mostly. The problem is, there is no standard implementation, so every kid is rolling their own. Usually incorrect and underperforming ones. And professionals just go with global locks and then wonder why it does't scale. See: Mongo. So no high quality libraries exist.
This reminds me of the times when most of C++ coders were putting everything in an std::map and their code was in fact much slower than if they coded that in Java with hash maps. Proffessionals are generally lazy, and if you give them a suboptimal, standard container, even though there is a choice to write a hand optimized one, 9 out of 10 will take the suboptimal, ready to use container over rolling their own. Of course, beginners will roll their own, then blog post about it, because they still don't know how hard it is to develop bug-free, optimal code in C++.
Last edited on
| The right question is what scales better. And lock-based algorithms don't scale well. Which means, given enough load and enough cores, they will be always slower than lockfree counterparts. |
Good lock-based design will scale where bad lockfree design won't, and vice versa. "scaling" is nowhere in the definition of "lockfree".
Synchronization primitives are just tools: explicit timing, locking, message passing, shared atomic variables, data ownership, transactional memory (potentially), each has strengths and weaknesses, each can be used poorly even in its own area of applicability.
But anyway, that's mostly off-topic. It is true that if you're implementing a lock-free data structure from scratch, and the algorithm you've chosen is susceptible to ABA problems, and you don't need the guarantees offered by any of the existing solutions, then GC makes the implementation easier.
True, but good lock-based is often worse than good lock-free approach, used in a language that fully supports it. GC-less languages are seriously limited in the area of lock-free programming, because efficient GC is essential for implementing persistent data structures. It is not just making it "slightly easier". GC is a game-changer here.
E.g. show me a mutable thread-safe concurrent queue with the following performance characteristic:
1. no synchronization for iterating the elements (not even a single CAS)
2. at most *one* CAS per enqueue / dequeue op.
3. O(1) enqueue and dequeue
No need to write the code, just show me an opensource implementation that does this.
E.g. show me a mutable thread-safe concurrent queue with the following performance characteristic:
1. no synchronization for iterating the elements (not even a single CAS)
2. at most *one* CAS per enqueue / dequeue op.
3. O(1) enqueue and dequeue
No need to write the code, just show me an opensource implementation that does this.
I think I can figure out what you're asking, but it's really a jumble of misused buzzwords. Which reminds me,
What are you smoking??
| This reminds me of the times when most of C++ coders were putting everything in an std::map and their code was in fact much slower than if they coded that in Java with hash maps. |
What are you smoking??
Nothing. The facts are facts: C++ did not have standard hash maps until C++11. So people were either rolling their own, or sticking with std::map, which is slower, or eventually using non-standard STL extensions (e.g SGI, but it wasn't portable to VC++). Which resulted in tons of suboptimal code. I was contributing to KDE some time ago, and the "roll your own structures" mindset was sooo common in that world. Of course 99% of those structures were suboptimal and/or buggy.
A similar state is in scalable multicore coding now - C++ doesn't give standard and easy to use tools, so most of professionals switched language (Go, Erlang, Scala, Java, C#, JS) or some (niche) C++ projects just roll their own solutions. It is very unlikely you ever see something as insanely scalable as MapR, Hadoop, Cassandra, Akka written in C++. Or it is very unlikely Mongo (C++) would ever scale as good as Cassandra given a similar feature-set. They are still struggling with making it production-level quality, while Java DBMSes are simply adding new features and taking over the whole market.
Writing lockless / distributed code is hard. So hard, that even smartest coders / scientists have problems with this (and it is easier to write a scientific paper than to write production quality code - just try to implement some of those published lockless or distributed algorithms in reality, and immediately you realize how many cases were missed by the authors; this is sometimes true even for such big names like Leslie Lamport).
On the other hand using proper libraries for lockless / distributed code is much easier. You don't need to be a genius to use a concurrent distributed cache or queue. So although, theoretically you can do whatever you wish in C++, in practice almost no-one would go that hard way and they would just use what is there: locks.
A similar state is in scalable multicore coding now - C++ doesn't give standard and easy to use tools, so most of professionals switched language (Go, Erlang, Scala, Java, C#, JS) or some (niche) C++ projects just roll their own solutions. It is very unlikely you ever see something as insanely scalable as MapR, Hadoop, Cassandra, Akka written in C++. Or it is very unlikely Mongo (C++) would ever scale as good as Cassandra given a similar feature-set. They are still struggling with making it production-level quality, while Java DBMSes are simply adding new features and taking over the whole market.
Writing lockless / distributed code is hard. So hard, that even smartest coders / scientists have problems with this (and it is easier to write a scientific paper than to write production quality code - just try to implement some of those published lockless or distributed algorithms in reality, and immediately you realize how many cases were missed by the authors; this is sometimes true even for such big names like Leslie Lamport).
On the other hand using proper libraries for lockless / distributed code is much easier. You don't need to be a genius to use a concurrent distributed cache or queue. So although, theoretically you can do whatever you wish in C++, in practice almost no-one would go that hard way and they would just use what is there: locks.
Last edited on
All this wonder a GC provides. I had no idea.
What has a GC to do with persistent data structures?
if you want to be lock free you can perform a single atomic action only (i.e. O(1)).
How will this be accomplish in case of dequeue?
Ok if you just want to delete the data, but usually you want to do something with the data.
How's a GC generally implemented? My idea is a timeout that is added to any dynamic memory. The data will be discarded when it elapse. Is this true?
Even in a GC driven world lock freeness is hard to achieve and is not even required in most cases.
The price you have to pay for a GC is an uncontrollable thread that does permanentely some annoying things.
What has a GC to do with persistent data structures?
if you want to be lock free you can perform a single atomic action only (i.e. O(1)).
How will this be accomplish in case of dequeue?
Ok if you just want to delete the data, but usually you want to do something with the data.
How's a GC generally implemented? My idea is a timeout that is added to any dynamic memory. The data will be discarded when it elapse. Is this true?
Even in a GC driven world lock freeness is hard to achieve and is not even required in most cases.
The price you have to pay for a GC is an uncontrollable thread that does permanentely some annoying things.
What has a GC to do with persistent data structures? |
Ehm, it enables them? How could you do persistent structures without GC?
if you want to be lock free you can perform a single atomic action only (i.e. O(1)) |
Nope. You can do more actions in one atomic batch and "commit" them with one CAS. But they can't be destructive actions (= noone can see you are changing something until you do the final CAS). This is what persistent data structures are all about. Again: you can't do it, without some kind of a GC. In C++ implementing such structures would require using shared_ptrs everywhere, which would be dead slow. That doesn not contradict my statement - shared_ptrs are in fact a poor-man's GC.
How's a GC generally implemented? My idea is a timeout that is added to any dynamic memory. The data will be discarded when it elapse. Is this true? |
No, it is not true. The data is discarded when it is no longer referenced, directly or indirectly.
The price you have to pay for a GC is an uncontrollable thread that does permanentely some annoying things. |
The price you pay for GC is usually lower than the price you pay for additional manual memory bookkeeping you have to do in C++. The GC cost can be moved to a separate CPU core and done in parallel, without slowing down the threads doing the real work, while in C++ that cost accumulates incrementally and takes time from the threads doing actual work.
Last edited on
| ResidentBiscuit wrote: |
|---|
| Why is this a thing? Is manually deleting your memory really that hard to do? This is an honest question, not meant to flame. From my experience, deleting memory isn't very hard. I can't imagine needing to rely on GC of some sort. |
Yes!
| maeriden wrote: |
|---|
| Even if it's not hard it's still an issue. With GC you don't have to worry about it at all. |
But it *is* hard.
| But it *is* hard. |
its hard if you're lazy or you are working in a team of lazy programmers who are the source of memory leaks. This is one of the reasons why automatic garbage collection is a feature in for a language as universal (cross-platform) as java.
Last edited on
Does the circular reference problem even ever happen? I've never run into such a situation in practical programming.
@DeXecipher and LB, what are some largest and most complex things you've written, how many modules and how many threads did it have? Note that pretty much nothing is that hard while you're at 1000 LOC (or rather, that at this point most problems are algorithmic rather than structural). In general hobby projects might not be representative of some real world programming problems. Though I don't have much experience either. I wish someone else could elaborate on the difference.
Last edited on
Since there's a call for personal experiences, I've never ran into circular reference issues with shared ownership in real world programming either or dealt with manual memory management in C++ in general. Designs where such things are possible don't make it past the blackboard.
(to use hamsterman's metrics, the largest chunk of C++ code that I wrote largerly alone was somewhere about 50k lines of code and involved about 350 threads, but I usually work as part of larger projects, as large as 150 MLoC today -- incidentally, new/delete are effectively banned on this one, we have special memory layouts and a dozen or so allocators to handle them)
(to use hamsterman's metrics, the largest chunk of C++ code that I wrote largerly alone was somewhere about 50k lines of code and involved about 350 threads, but I usually work as part of larger projects, as large as 150 MLoC today -- incidentally, new/delete are effectively banned on this one, we have special memory layouts and a dozen or so allocators to handle them)
@DeXecipher and LB, what are some largest and most complex things you've written, |
Lines of code don't have crap all to do with anything. Thats why you're supposed to split things up to different processes. If you are at the point where you have to think too much about new/delete you should probrably invest in a memory manager or at least smart pointers. My library that I'm working on is averaging 200-300 lines per source file, and don't get me wrong I've a few that are over 1000 but if THAT got any bigger I'd probably at least split the implementation up. There are 172 files (including the IDE files for code blocks) in my project and 172-35 = 137 (coded files). Lines of code has little to do with the worth of a project, but some relevance with the complexity. Not using new/delete free/malloc is an issue of discipline. You can't use threads as an excuse either because many implementations of free/malloc new/delete are thread safe.
edit:
I guess new/delete can be a problem if you are using them exclusively. But that is the purpose of testing. If it takes too long to compile one of your sources into an object file, then you probrably should have at least divided you source and interface into another set of implementations.
Last edited on
I don’t understand this anti-gc attitude. Every tiny-winy detail you have to think about decreases your capability of actually thinking about the problem you need to solve. And times when gc caused 1s pauses are long gone.
You say you don’t encounter situations when manual memory management would be complex. This is exactly because you’re doing manual memory management. You simply (unconsciously?) disregard solutions that would be too complex from the memory management standpoint. Or even can’t think about such solutions because you never programmed in a language with gc.
For me, the best thing about gc is that I don’t need to think about ownership. This may not seem like a big deal, but it is, once you learn how to take advantage of it.
You say you don’t encounter situations when manual memory management would be complex. This is exactly because you’re doing manual memory management. You simply (unconsciously?) disregard solutions that would be too complex from the memory management standpoint. Or even can’t think about such solutions because you never programmed in a language with gc.
For me, the best thing about gc is that I don’t need to think about ownership. This may not seem like a big deal, but it is, once you learn how to take advantage of it.
@Cubbi, that's very interesting. Does the 150 MLOC project use special layouts and allocators for purposes of efficiency or thread safety, or is it something else?
@DeXecipher, lines of code correlate to some extent with complexity. I asked about threads because they seem like a natural cause for memory issues. If you have better metrics, do speak up.
I'm not sure why you're sharing your directory statistics, I assume that sums up to some 40 KLOC? cool.
@DeXecipher, lines of code correlate to some extent with complexity. I asked about threads because they seem like a natural cause for memory issues. If you have better metrics, do speak up.
I'm not sure why you're sharing your directory statistics, I assume that sums up to some 40 KLOC? cool.
Last edited on
I don't dislike garbage collection because I'm tricked into thinking it is inefficient, I dislike garbage collection because it basically circumvents scope-based object lifetime when it really shouldn't, and it makes it near-impossible to implement destructors (t least Java has "finalize" which is 'close-enough'). Why do you think they added the try-with-resources statement? RAII.
Garbage collection is definitely useful when you're creating and passing around objects like a madman, but I've never been creating and passing around objects like a madman except in Java where it seems you have no choice but to do that. They seem to rely too heavily on GC in Java, so you end up with so many excess objects that need to be GC'd that the garbage collector can hang the game or application for a few seconds.
Basically, I don't like GC because it's too often and too easily misused. If it could be used properly, I'd like it.
Garbage collection is definitely useful when you're creating and passing around objects like a madman, but I've never been creating and passing around objects like a madman except in Java where it seems you have no choice but to do that. They seem to rely too heavily on GC in Java, so you end up with so many excess objects that need to be GC'd that the garbage collector can hang the game or application for a few seconds.
Basically, I don't like GC because it's too often and too easily misused. If it could be used properly, I'd like it.
| special layouts and allocators for purposes of efficiency or thread safety, or is it something else? |
Something else: different memory areas have different function. Some can be snapshotted and moved to another server, some are shared, etc.
closed account (o1vk4iN6)
| DeXecipher wrote: |
|---|
| Lines of code don't have crap all to do with anything. ... Lines of code has little to do with the worth of a project, but some relevance with the complexity. |
So you disagree'd with him then agree'd with him ?
The more lines of code program statements, the poorer job you're doing as a programmer.
Last edited on
^ Not necessarily. You have to factor functionality into that. If programmer A can get the same functionality as programmer B with less code, then it stands to reason that programmer A is better. But there are still other factors. Whose code is easier to read and understand? Is all the functionality necessary or even useful? Whose code is more robust (usually less code => less bugs, but not necessarily)?
Metrics of code size, be it lines of code or statements or whatever,is are not really useful in determining the quality of code, either positively or negatively, because there are so many other factors that might cause one program to have more or less code than another. Only with all else being equal can you say a shorter program is better than a longer one.
Metrics of code size, be it lines of code or statements or whatever,
Last edited on