6 ms·

Very nice. RCU like this can be very effective (we have a custom per-cpu version based on https://lwn.net/Articles/650333/ https://lwn.net/Articles/650333/ here

by ahh 11y ago

Very nice. RCU like this can be very effective (we have a custom per-cpu version based on https://lwn.net/Articles/650333/ https://lwn.net/Articles/650333/ here, which scales better than per-thread versions for obvious reasons.) I'm glad to see more wide use of the techniques.

haberman 11y ago
Cool! Who is "we" and where can this code be found? You say "RCU like this", but AIUI RCU and epoch-based collection like in this article are quite different from each other. RCU involves no-synchronization reads of a data structure and writers that wait for a "quiescent" state to delete old nodes. It is used for data structures that have pure readers (like a frequently read but infrequently-updated list of things). Epoch-based GC involves lock-free writes but puts garbage in freelists to be collected at a later time. It is used for data structures that are mostly based around writes (for a stack or queue, both push and pop are mutating operations).
- arielby 11y ago
  Could someone explain the big difference between RCU and epoch-based reclamation? It seems that the only difference is that RCU has quiescent periods between reschedules and epoch-based has them when you don't have a Guard struct active. Seems like six of one, half a dozen of the other.
  - aturon 11y ago
    They are very similar; I think of the epoch scheme as a particular way of doing RCU that does not impose the need to find quiescent states yourself (RCU can be employed in userspace as well if your application can provide quiescent states in some way). This paper (linked from the blog post) was very helpful in comparing them: http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc0...
    - arielby 11y ago
      According to the paper, it simply makes everywhere outside of data structure code a quiescent state. This may be a big difference in practice through, because one of the appeals of RCU is being able to interact with data structures with no fear of following dangling pointers. However, with both RCU and the epoch-based scheme, you can make quiescent states as fine- or coarse-grained as you desire.
      - aturon 11y ago
        "According to the paper, it simply makes everywhere outside of data structure code a quiescent state" -- yes, from a per-thread point of view, but of course all the hard work is in detecting global quiescence.
    - haberman 11y ago
      I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage. This approach wouldn't make much sense for data structures like stacks and queues where every operation is a write. I see Epoch based GC as an approach that defers the deletion to make the write path cheaper.
      - anarazel 11y ago
        > I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage. A rather common, in my opinion, way to use something like rcu is to delay freeing (or reusing) memory to the next grace period, without blocking until then. E.g. in the kernel you can use kfree_rcu(..); instead of synchronize_rcu(); kfree(..); for that. That's basically what the epoch based approach does with a the lists of to-be-freed allocations.
  - sbahra 11y ago
    RCU is a higher-level abstraction. You can implement RCU with epoch reclamation, typically there are more performant ways to detect grace periods in kernel space.
- ahh 11y ago
  "We" is "infrastructure teams at Google". You apparently work there too, my username is the same. RCU is an overloaded name; it's both a family of implementations of epochs, and a pattern for using epoch-like systems. The name literally refers to the latter (a read-mostly RWlock setup where we don't bother protecting the read side of a data structure, but _copy_ and atomically update access to the data, using epochs to dispose of the old version safely) but is often used to describe the whole system (tracking quiescence and determining when disposal is safe.) One could easily use the kernel's RCU (our my userspace one) to build a data structure like this.

by ahh 11y ago

haberman 11y ago

Cool! Who is "we" and where can this code be found? You say "RCU like this", but AIUI RCU and epoch-based collection like in this article are quite different from each other. RCU involves no-synchronization reads of a data structure and writers that wait for a "quiescent" state to delete old nodes. It is used for data structures that have pure readers (like a frequently read but infrequently-updated list of things). Epoch-based GC involves lock-free writes but puts garbage in freelists to be collected at a later time. It is used for data structures that are mostly based around writes (for a stack or queue, both push and pop are mutating operations).

arielby 11y ago
Could someone explain the big difference between RCU and epoch-based reclamation? It seems that the only difference is that RCU has quiescent periods between reschedules and epoch-based has them when you don't have a Guard struct active. Seems like six of one, half a dozen of the other.
- aturon 11y ago
  They are very similar; I think of the epoch scheme as a particular way of doing RCU that does not impose the need to find quiescent states yourself (RCU can be employed in userspace as well if your application can provide quiescent states in some way). This paper (linked from the blog post) was very helpful in comparing them: http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc0...
  - arielby 11y ago
    According to the paper, it simply makes everywhere outside of data structure code a quiescent state. This may be a big difference in practice through, because one of the appeals of RCU is being able to interact with data structures with no fear of following dangling pointers. However, with both RCU and the epoch-based scheme, you can make quiescent states as fine- or coarse-grained as you desire.
    - aturon 11y ago
      "According to the paper, it simply makes everywhere outside of data structure code a quiescent state" -- yes, from a per-thread point of view, but of course all the hard work is in detecting global quiescence.
  - haberman 11y ago
    I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage. This approach wouldn't make much sense for data structures like stacks and queues where every operation is a write. I see Epoch based GC as an approach that defers the deletion to make the write path cheaper.
    - anarazel 11y ago
      > I think a key property of RCU as traditionally presented is that writers always wait for global quiescence directly after their write, and then immediately delete the garbage. A rather common, in my opinion, way to use something like rcu is to delay freeing (or reusing) memory to the next grace period, without blocking until then. E.g. in the kernel you can use kfree_rcu(..); instead of synchronize_rcu(); kfree(..); for that. That's basically what the epoch based approach does with a the lists of to-be-freed allocations.
- sbahra 11y ago
  RCU is a higher-level abstraction. You can implement RCU with epoch reclamation, typically there are more performant ways to detect grace periods in kernel space.
ahh 11y ago
"We" is "infrastructure teams at Google". You apparently work there too, my username is the same. RCU is an overloaded name; it's both a family of implementations of epochs, and a pattern for using epoch-like systems. The name literally refers to the latter (a read-mostly RWlock setup where we don't bother protecting the read side of a data structure, but _copy_ and atomically update access to the data, using epochs to dispose of the old version safely) but is often used to describe the whole system (tracking quiescence and determining when disposal is safe.) One could easily use the kernel's RCU (our my userspace one) to build a data structure like this.