SPMC Queue in URCU

All,
Is there a data structure offered by Userspace RCU that provides a bounded single producer multiple consumer queue? Or are we better off just using the linked list URCU data structure despite the cpu cache implications?

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Hi,

What we have in URCU is an unbounded SPMC queue (wfcqueue.h). You could theoretically use it with a counter to make it bounded, but it might not be as efficient as a bounded SPMC queue, since we use a linked list rather than a circular buffer. It would be interesting to compare the performance of the two approaches.

Note that wfcqueue is wait-free on the enqueue, blocking on the dequeue. It is used internally by URCU to implement the call_rcu scheme.

Thanks,

Mathieu

Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Ah, so even the wfcqueue is a linked list under the covers? No ring buffer or other cache-friendly data structure types available?

From: Mathieu Desnoyers <[email protected]>
To: "Mark E. Dawson, Jr." <[email protected]>
Cc: lttng-dev <[email protected]>
Sent: Monday, June 6, 2016 3:08 PM
Subject: Re: [lttng-dev] SPMC Queue in URCU

----- On Jun 6, 2016, at 2:48 PM, Mark E. Dawson, Jr. <[email protected]> wrote:

All,
Is there a data structure offered by Userspace RCU that provides a bounded single producer multiple consumer queue? Or are we better off just using the linked list URCU data structure despite the cpu cache implications?

Hi,
What we have in URCU is an unbounded SPMC queue (wfcqueue.h).You could theoretically use it with a counter to make it bounded, butit might not be as efficient as a bounded SPMC queue, since we usea linked list rather than a circular buffer. It would be interesting tocompare the performance of the two approaches. Note that wfcqueue is wait-free on the enqueue, blocking on the
dequeue. It is used internally by URCU to implement the call_rcu
scheme.

Thanks,
Mathieu

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Yes it's a linked list, but wfcqueue does no allocations under the covers; but rather the structure is embedded into whatever struct you give it (similar to the well-known Linux kernel linked list, using the container_of macro).

In other words, you may use a cache-friendly allocator for all the structs you might place into it. But you already get some cache friendliness by avoiding the extra pointer to the struct you're actually storing.
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

All,
I've read the documentation regarding reader throughput drop-offs with high update rates due to the pointer exchanging between readers-writers, and the general admonition of using URCU only for mostly-read workloads with relatively infrequent updates.
However, is there a general rule-of-thumb suggestion for highest recommended update rate sustainable for optimal performance with URCU (in particular, the QSBR flavor) for highly threaded applications deployed on high core count machines (Intel)? The example case would be a single updater and 20 - 30 reader threads.

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Hi Mark,

We have some relevant measurements in the supplementary material of:

Desnoyers, Mathieu, McKenney, Paul. E., Stern, Alan S., Dagenais, Michel R. and Walpole, Jonathan, User-Level Implementations of Read-Copy Update . IEEE Transaction on Parallel and Distributed Systems , 23 (2): 375-382 (2012).

A copy can be found at http://www.efficios.com/publications

See p. 10 of supplementary material, Fig. 14:

"Comparison of Pointer Exchange and Ideal RCU Update Overhead, 8-core Intel Xeon, Logarithmic Scale"

Since you are doing pointer exchange, you will want to look at the "QSBR" line, which stays at 1000M reads/s up to 100000 updates/s, and then starts dropping.

On the 64-core POWER5+ (Fig. 15), read speed starts dropping near 100000 updates/s too.

Thanks,

Mathieu

Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Thanks!

From: Mathieu Desnoyers <[email protected]>
To: Mark E. Dawson <[email protected]>
Cc: lttng-dev <[email protected]>
Sent: Thursday, July 21, 2016 4:58 PM
Subject: Re: [lttng-dev] Practical recommendation for max update rate with QSBR

----- On Jul 21, 2016, at 4:47 PM, Mark E. Dawson <[email protected]> wrote:

All,
I've read the documentation regarding reader throughput drop-offs with high update rates due to the pointer exchanging between readers-writers, and the general admonition of using URCU only for mostly-read workloads with relatively infrequent updates.
However, is there a general rule-of-thumb suggestion for highest recommended update rate sustainable for optimal performance with URCU (in particular, the QSBR flavor) for highly threaded applications deployed on high core count machines (Intel)? The example case would be a single updater and 20 - 30 reader threads.

Hi Mark,

We have some relevant measurements in the supplementary material of:

Desnoyers, Mathieu, McKenney, Paul. E., Stern, Alan S., Dagenais, Michel R. and Walpole, Jonathan, User-Level Implementations of Read-Copy Update. IEEE Transaction on Parallel and Distributed Systems, 23 (2): 375-382 (2012). A copy can be found at http://www.efficios.com/publications

See p. 10 of supplementary material,  Fig. 14:

"Comparison of Pointer Exchange and Ideal RCU Update Overhead, 8-core Intel Xeon, Logarithmic Scale"

Since you are doing pointer exchange, you will want to look at the "QSBR"line, which stays at 1000M reads/s up to 100000 updates/s, and then startsdropping. On the 64-core POWER5+ (Fig. 15), read speed starts dropping near 100000updates/s too.

Thanks,
Mathieu

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev