6 ms·

Concurrent Memory Deallocation in the Objective-C Runtime

58 points by chmaynard 11y ago

pron 11y ago
That's a cool GC algorithm, but it has two big drawbacks: 1. It works well only if the number of GCed data structures -- i.e. the number of entry/exit points -- is relatively small (in this case, just the method cache). 2. It prevents inlining of the data structure's access functions, which adds quite a bit of overhead to each access (though not as much as two fenced CASes). It can, however, be very useful for hot code swapping (provided there's no inlining or you have a JIT that can un-inline).
- pcwalton 11y ago
  I think the way to look at this is more of as a synchronization technique as opposed to a general-purpose GC algorithm. I don't understand the objection about inlining--could you explain? You could in principle not use function boundaries to delimit the critical section: a range of PC addresses within a function would do just as well.
  - pron 11y ago
    > a range of PC addresses within a function would do just as well Yes, but you'll need to know where those ranges are (i.e. you'll need some feedback from the compiler), and then be very careful that no tool injects any instructions into, or moves code around your executable/library.
pcwalton 11y ago
Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the uncontended lock acquisition and release time down to zero in the case where no synchronization needs to be performed. Now I'm trying to think of other places to use this trick. :)
- rayiner 11y ago
  Clozure CL and I believe SBCL do this in their GCs to allow threads to be stopped for GC preemptively while dealing with sequences that must be atomic (like allocation). Clozure calls it PC lusering: http://ccl.clozure.com/manual/chapter17.1.html http://ccl.clozure.com/manual/chapter17.1.html
- pron 11y ago
  It's a take on kernel-mode RCU.
  - 1amzave 11y ago
    Yes, this essentially just a form of RCU. Note however that RCU isn't just for the kernel anymore though: http://urcu.so/ http://urcu.so/
    - pron 11y ago
      Userspace RCU algorithms are experimental, quite brittle, and/or have little in common with RCU. They're certainly not usable as a production-ready scalable synchronization solution.
      - 1amzave 11y ago
        I haven't actually used it myself and am certainly willing to believe it's immature, but how do you mean it has "little in common with RCU"? Comparing personnel between that library and this set of people --> https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/MAINTAINERS#n8218 https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... there's certainly at least some authorship in common...
        pron 11y ago
        RCU basically works by having a critical section only within which a reader may access the data structure. To know when to GC the old copy of the data, you wait until all readers leave the critical section. If you're in the kernel, this can be very efficient: you disable all interrupts within the CS, so you know a thread is never preempted while in it. This means that no matter how many threads there are, only those currently running on the available cores (say, there are 8 of them) can be in the CS, so no matter how many threads there are, you only need to wait for 8, and you know that that waiting period is going to be short because there are no interrupts. So the efficiency of the algorithms stems from disabling interrupts within the reader's critical section, which can only be done in kernel mode (otherwise you could do really bad things). A similar algorithm in userspace will need to find another mechanism to wait for all readers to exit the CS, which may or may not be efficient. They may share then name "RCU", but not its desirable qualities. There are, AFAIK, several different algorithms calling themselves userspace RCU. One userspace RCU algorithm I've seen essentially protects the deallocation with a read-write, which isn't known for terrific scalability, but I don't know, they may have come up with something better. Garbage collection is the Achille's heel of all nonblocking data structures. As far as I know, there is no algorithm more efficient than a general purpose GC just yet, which is both generally applicable and efficient. Common authorship, BTW, says little. Most concurrent algorithms out there were invented by a handful of people.

58 points by chmaynard 11y ago

pron 11y ago

That's a cool GC algorithm, but it has two big drawbacks: 1. It works well only if the number of GCed data structures -- i.e. the number of entry/exit points -- is relatively small (in this case, just the method cache). 2. It prevents inlining of the data structure's access functions, which adds quite a bit of overhead to each access (though not as much as two fenced CASes). It can, however, be very useful for hot code swapping (provided there's no inlining or you have a JIT that can un-inline).

pcwalton 11y ago
I think the way to look at this is more of as a synchronization technique as opposed to a general-purpose GC algorithm. I don't understand the objection about inlining--could you explain? You could in principle not use function boundaries to delimit the critical section: a range of PC addresses within a function would do just as well.
- pron 11y ago
  > a range of PC addresses within a function would do just as well Yes, but you'll need to know where those ranges are (i.e. you'll need some feedback from the compiler), and then be very careful that no tool injects any instructions into, or moves code around your executable/library.

pcwalton 11y ago

Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the uncontended lock acquisition and release time down to zero in the case where no synchronization needs to be performed. Now I'm trying to think of other places to use this trick. :)

rayiner 11y ago
Clozure CL and I believe SBCL do this in their GCs to allow threads to be stopped for GC preemptively while dealing with sequences that must be atomic (like allocation). Clozure calls it PC lusering: http://ccl.clozure.com/manual/chapter17.1.html http://ccl.clozure.com/manual/chapter17.1.html
pron 11y ago
It's a take on kernel-mode RCU.
- 1amzave 11y ago
  Yes, this essentially just a form of RCU. Note however that RCU isn't just for the kernel anymore though: http://urcu.so/ http://urcu.so/
  - pron 11y ago
    Userspace RCU algorithms are experimental, quite brittle, and/or have little in common with RCU. They're certainly not usable as a production-ready scalable synchronization solution.
    - 1amzave 11y ago
      I haven't actually used it myself and am certainly willing to believe it's immature, but how do you mean it has "little in common with RCU"? Comparing personnel between that library and this set of people --> https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/MAINTAINERS#n8218 https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... there's certainly at least some authorship in common...
      - pron 11y ago
        RCU basically works by having a critical section only within which a reader may access the data structure. To know when to GC the old copy of the data, you wait until all readers leave the critical section. If you're in the kernel, this can be very efficient: you disable all interrupts within the CS, so you know a thread is never preempted while in it. This means that no matter how many threads there are, only those currently running on the available cores (say, there are 8 of them) can be in the CS, so no matter how many threads there are, you only need to wait for 8, and you know that that waiting period is going to be short because there are no interrupts. So the efficiency of the algorithms stems from disabling interrupts within the reader's critical section, which can only be done in kernel mode (otherwise you could do really bad things). A similar algorithm in userspace will need to find another mechanism to wait for all readers to exit the CS, which may or may not be efficient. They may share then name "RCU", but not its desirable qualities. There are, AFAIK, several different algorithms calling themselves userspace RCU. One userspace RCU algorithm I've seen essentially protects the deallocation with a read-write, which isn't known for terrific scalability, but I don't know, they may have come up with something better. Garbage collection is the Achille's heel of all nonblocking data structures. As far as I know, there is no algorithm more efficient than a general purpose GC just yet, which is both generally applicable and efficient. Common authorship, BTW, says little. Most concurrent algorithms out there were invented by a handful of people.