ConcurrentLinkedQueue padding

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

ConcurrentLinkedQueue padding

JSR166 Concurrency mailing list
Hi concurrency interest,

I was looking through ConcurrentLinkedQueue and noticed that unlike several of the other concurrent classes, the volatile Node pointers as well as the Nodes themselves don't have any padding.  This makes me wonder, could there be false sharing when using multiple producers to add to the queue?  I was under the impression that the GC tends to group fields of a class near each other, which would imply that there is going to likely be contention when quickly updating (and reading) from it.


Carl  

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue padding

JSR166 Concurrency mailing list
None of the linked list based node classes use @Contended.  Node classes tend to be small and @Contended adds a lot of memory overhead.  When multiple threads are enqueueing, you're likely instead to get "true sharing" contention as they all try to CAS the very same next link.

On Tue, Nov 21, 2017 at 1:33 PM, Carl Mastrangelo via Concurrency-interest <[hidden email]> wrote:
Hi concurrency interest,

I was looking through ConcurrentLinkedQueue and noticed that unlike several of the other concurrent classes, the volatile Node pointers as well as the Nodes themselves don't have any padding.  This makes me wonder, could there be false sharing when using multiple producers to add to the queue?  I was under the impression that the GC tends to group fields of a class near each other, which would imply that there is going to likely be contention when quickly updating (and reading) from it.


Carl  

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue padding

JSR166 Concurrency mailing list

Also, each thread most likely has its own Thread Local Allocation Buffer (TLAB).  With multiple threads enqueuing, each thread will create a node from its own TLAB.  Thus, the nodes from different threads will not be able to share the same cache line.  I could see this as being a bad thing.  Ideally, we would want all of the nodes to be packed as close as possible to each other to improve cache locality and hence performance.  If a thread is simply reading through the nodes, then this will definitely help performance.  If a thread is CASing, then only 1 thread should be accessing the cache line anyway.

-Nathan

On 11/22/2017 9:06 AM, Martin Buchholz via Concurrency-interest wrote:
None of the linked list based node classes use @Contended.  Node classes tend to be small and @Contended adds a lot of memory overhead.  When multiple threads are enqueueing, you're likely instead to get "true sharing" contention as they all try to CAS the very same next link.

On Tue, Nov 21, 2017 at 1:33 PM, Carl Mastrangelo via Concurrency-interest <[hidden email]> wrote:
Hi concurrency interest,

I was looking through ConcurrentLinkedQueue and noticed that unlike several of the other concurrent classes, the volatile Node pointers as well as the Nodes themselves don't have any padding.  This makes me wonder, could there be false sharing when using multiple producers to add to the queue?  I was under the impression that the GC tends to group fields of a class near each other, which would imply that there is going to likely be contention when quickly updating (and reading) from it.


Carl  

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-- 
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue padding

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Ah, I should have clarified, I was thinking of the MPSC/SPMC case.  I agree it would take more memory, but in some cases it would be convenient to let the user make that trade off.  The consumer would fight with the producers if the queue was small.     Is the recommendation to use a more specific class than the JDK ones, or do the JDK ones still usually win? 

On Wed, Nov 22, 2017 at 8:06 AM, Martin Buchholz <[hidden email]> wrote:
None of the linked list based node classes use @Contended.  Node classes tend to be small and @Contended adds a lot of memory overhead.  When multiple threads are enqueueing, you're likely instead to get "true sharing" contention as they all try to CAS the very same next link.

On Tue, Nov 21, 2017 at 1:33 PM, Carl Mastrangelo via Concurrency-interest <[hidden email]> wrote:
Hi concurrency interest,

I was looking through ConcurrentLinkedQueue and noticed that unlike several of the other concurrent classes, the volatile Node pointers as well as the Nodes themselves don't have any padding.  This makes me wonder, could there be false sharing when using multiple producers to add to the queue?  I was under the impression that the GC tends to group fields of a class near each other, which would imply that there is going to likely be contention when quickly updating (and reading) from it.


Carl  

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest