3 ms·

No, you don't need a GC to implement lock-free data-structures. RCU allows you to generically defer work on a piece of data until it is no longer accessible. I

by ratt 13y ago

No, you don't need a GC to implement lock-free data-structures. RCU allows you to generically defer work on a piece of data until it is no longer accessible. I personally find the idea behind it to be very elegant and I'd recommend reading up on it. While it isn't as simple as a full-blown GC, once you have a working implementation that suits your needs (eg. urcu), it's usually pretty straightforward to introduce in a lock-free data-structure and has far less overhead. In fact, when it comes to real-time systems (eg. games), the GC is usually something you want to avoid at all costs. Note that there are various other tricks (eg. hazard pointers, reference counters, etc.) to get around the same problem but they're mostly specialized to various situations. As an example, last time I checked gcc's std::shared_ptr implementation on x86, it used some lock-free magic to implement its thread-safe reference counter. In fact, I think it could even be used to build entire lock-free data-structures and never have to worry about deleting anything.

pron 13y ago
Several things: First, various techniques for avoiding GC in lock-free data structures are not in wide use and for good reason: they are far more complicated to implement in a general fashion than you think. Sometimes they're very specific, sometimes they require cooperation by the kernel, and sometimes you end up writing a buggy and inefficient garbage collector just to get around implementation problems. Java's lock-free data structures are used everywhere today and with great results. Second, regarding real-time. There are hard real-time GCs for Java, and they work great, only they tend to cost a lot of money. But hard real time systems often sacrifice performance for the sake of worst-case guarantees -- that's a whole other set of tradeoffs. In general, and certainly when it comes to throughput, a good GC is both the easiest and the most efficient way to manage memory. Finally, because, as I've shown, for every Java program there exists a C++ program that performs as efficiently or better, you could, given enough effort, always surpass Java. In practice, doing that is extremely hard (unless it's a very specific, well understood problem), and the returns are hardly worth the effort. What you gain in integer compression you lose in method invocation. What you gain with SIMD you lose on malloc. What you gain in cache-friendliness you lose in multi-threading. And the gap is only narrowing in Java's favor so that there are fewer and fewer things you gain when using C++. This is not to say that C++ doesn't have it's place. First, you need it to write the JVM :) You need it in a resource constrained environment where memory is limited, and you may not want to spare a thread for concurrent GC. You need it when startup time is crucial. You need it (or Fortran) for some well-understood numeric computing problems. But for general, large, long-running server side applications - Java is king. And BTW, games are years, if not a decade or more, behind advances in software engineering (I've had some experience in that). In the past decade they've literally progressed on one front only (though, an important one): graphics and GPGPU (for physics and AI). I know that some AAA studios literally forbid any multithreaded code on the CPU (beyond a simple and predefined division of labor among a few threads). MMO game engines, for examples, are practically primitive compared to advanced server-side systems in other markets.
- ratt 13y ago
  RCU is in wide use today. In fact, you probably rely on it everyday: inside the Linux kernel. The biggest problem holding back RCU is not how hard it is to use (if you're qualified to write lock-free data-structures then it should be cake) but that it's relatively unknown and there are not many user-land libraries. I know of 4 available user-land implementations: two that I've written, one that we use at work and only the fourth, liburcu, would I consider mature and stable enough for wide-use. There's a third reason but I'll let you figure that one out by reading the Wikipedia article. Note that it's not a magic bullet either because there are various possible implementations and they offer various trade-offs. A bit like the various GC mechanisms really. Funny thing is that I usually introduce RCU as a GC mechanism; albeit one that's far more specialized and offers many advantages over a traditional GC when it comes to lock-free data-structures. Final note, I've written various mechanism for cleaning up lock-free data-structures and I'm fully aware of how difficult they can be to implement correctly. If nothing else, it's more complicated then using a GC where there's nothing for you to do. The point of my previous post was not to say that one approach or language is better then another but merely to point out that a full-blown GC is not required to build a scalable lock-free data-structure. Good thing for me since that's exactly what I do for fun :)
  - pron 13y ago
    I see that while RCU doesn't rely on GC, it does rely on safepoints (or a specific kind of safepoint - a task switch). A little unrelated, but internally, the JVM makes use of safepoints, not only for GC but for other purposes as well (I think JIT-ing and maybe other things). There are some "phase changes" that can only occur when all, or some, threads are at a safepoint. JVM data structure gurus like Doug Lea sometimes structure their code with that knowledge. For example, if I'm not mistaken (and I may very well be mistaken on this point), there's a safepoint at every back jump, and this somehow makes Doug use a while loop and a do-while loop for different occasions.
    - ratt 13y ago
      While the Linux kernel may rely on task-switch safe-points, user-land implementations can't which means they require an entirely different grace-period mechanism to work. This is what makes user-land implementations tricky to get right. I won't go into the details here since it's somewhat involved and I need a white board to explain it properly. That being said, if you feel brave, head over to my github repo[1] and look for src/rcu.h and src/grcu.* . [1]: https://github.com/RAttab/lockless https://github.com/RAttab/lockless

by ratt 13y ago

pron 13y ago

Several things: First, various techniques for avoiding GC in lock-free data structures are not in wide use and for good reason: they are far more complicated to implement in a general fashion than you think. Sometimes they're very specific, sometimes they require cooperation by the kernel, and sometimes you end up writing a buggy and inefficient garbage collector just to get around implementation problems. Java's lock-free data structures are used everywhere today and with great results. Second, regarding real-time. There are hard real-time GCs for Java, and they work great, only they tend to cost a lot of money. But hard real time systems often sacrifice performance for the sake of worst-case guarantees -- that's a whole other set of tradeoffs. In general, and certainly when it comes to throughput, a good GC is both the easiest and the most efficient way to manage memory. Finally, because, as I've shown, for every Java program there exists a C++ program that performs as efficiently or better, you could, given enough effort, always surpass Java. In practice, doing that is extremely hard (unless it's a very specific, well understood problem), and the returns are hardly worth the effort. What you gain in integer compression you lose in method invocation. What you gain with SIMD you lose on malloc. What you gain in cache-friendliness you lose in multi-threading. And the gap is only narrowing in Java's favor so that there are fewer and fewer things you gain when using C++. This is not to say that C++ doesn't have it's place. First, you need it to write the JVM :) You need it in a resource constrained environment where memory is limited, and you may not want to spare a thread for concurrent GC. You need it when startup time is crucial. You need it (or Fortran) for some well-understood numeric computing problems. But for general, large, long-running server side applications - Java is king. And BTW, games are years, if not a decade or more, behind advances in software engineering (I've had some experience in that). In the past decade they've literally progressed on one front only (though, an important one): graphics and GPGPU (for physics and AI). I know that some AAA studios literally forbid any multithreaded code on the CPU (beyond a simple and predefined division of labor among a few threads). MMO game engines, for examples, are practically primitive compared to advanced server-side systems in other markets.

ratt 13y ago
RCU is in wide use today. In fact, you probably rely on it everyday: inside the Linux kernel. The biggest problem holding back RCU is not how hard it is to use (if you're qualified to write lock-free data-structures then it should be cake) but that it's relatively unknown and there are not many user-land libraries. I know of 4 available user-land implementations: two that I've written, one that we use at work and only the fourth, liburcu, would I consider mature and stable enough for wide-use. There's a third reason but I'll let you figure that one out by reading the Wikipedia article. Note that it's not a magic bullet either because there are various possible implementations and they offer various trade-offs. A bit like the various GC mechanisms really. Funny thing is that I usually introduce RCU as a GC mechanism; albeit one that's far more specialized and offers many advantages over a traditional GC when it comes to lock-free data-structures. Final note, I've written various mechanism for cleaning up lock-free data-structures and I'm fully aware of how difficult they can be to implement correctly. If nothing else, it's more complicated then using a GC where there's nothing for you to do. The point of my previous post was not to say that one approach or language is better then another but merely to point out that a full-blown GC is not required to build a scalable lock-free data-structure. Good thing for me since that's exactly what I do for fun :)
- pron 13y ago
  I see that while RCU doesn't rely on GC, it does rely on safepoints (or a specific kind of safepoint - a task switch). A little unrelated, but internally, the JVM makes use of safepoints, not only for GC but for other purposes as well (I think JIT-ing and maybe other things). There are some "phase changes" that can only occur when all, or some, threads are at a safepoint. JVM data structure gurus like Doug Lea sometimes structure their code with that knowledge. For example, if I'm not mistaken (and I may very well be mistaken on this point), there's a safepoint at every back jump, and this somehow makes Doug use a while loop and a do-while loop for different occasions.
  - ratt 13y ago
    While the Linux kernel may rely on task-switch safe-points, user-land implementations can't which means they require an entirely different grace-period mechanism to work. This is what makes user-land implementations tricky to get right. I won't go into the details here since it's somewhat involved and I need a white board to explain it properly. That being said, if you feel brave, head over to my github repo[1] and look for src/rcu.h and src/grcu.* . [1]: https://github.com/RAttab/lockless https://github.com/RAttab/lockless