[lttng-dev] [RFC URCU PATCH] wfqueue: ABI v1, simplify implementation, 2.3x to 2.6x performance boost

[Lai Jiangshan]

ping

On 08/21/2012 11:41 AM, Lai Jiangshan wrote:
> On 08/20/2012 09:16 PM, Mathieu Desnoyers wrote:
>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>>> On 08/16/2012 05:31 AM, Mathieu Desnoyers wrote:
>>>> This work is derived from the patch from Lai Jiangshan submitted as
>>>> "urcu: new wfqueue implementation"
>>>> (http://lists.lttng.org/pipermail/lttng-dev/2012-August/018379.html)
>>>>
>>>
>>
>> Hi Lai,
>>
>>> Hi, Mathieu
>>>
>>> please add this part to your patch.
>>>
>>> Changes(item5 has alternative):
>>>
>>> 1) Reorder the head and the tail in struct cds_wfq_queue
>>>    Reason: wfq is enqueue-preference
>>
>> Is this a technical improvement over the original order ? Both cache
>> lines are aligned, so it should not matter which one comes first. So I'm
>> not sure why we should favor one order vs the other.
>>
>>> 2) Reorder the code of ___cds_wfq_next_blocking()
>>>    Reason: short code, better readability
>>
>> Yes, I agree with this change. Can you extract it into a separate patch ?
>>
>>>
>>> 3) Add cds_wfq_dequeue_[un]lock
>>>    Reason: the fields of struct cds_wfq_queue are not exposed to users of lib,
>>> 	but some APIs needs to have this lock held. Add this locking function
>>> 	to allow the users use such APIs
>>
>> I agree with this change too. You can put it into the same patch as (2).
>>
>>>
>>> 4) Add cds_wfq_node_sync_next(), cds_wfq_dequeue_all_blocking()
>>>    Reason: helper for for_each_*
>>
>> Points 4-5-6-7 will need more discussion.
>>
>> I don't like exposing "cds_wfq_node_sync_next()", which should remain an
>> internal implementation detail not exposed to queue users.  The
>> "get_first"/"get_next" API, as well as the dequeue, are providing an
>> abstraction that hide the node synchronization, which makes it harder
>> for the user to make mistakes. Given that the fast-path of
>> cds_wfq_node_sync_next is just a pointer load and test, I don't think
>> that skipping this the second time we iterate on the same queue would
>> bring any significant performance improvement, but exposing sync_next
>> adds in API complexity, which I would like to avoid.
> 
> If the name "cds_wfq_node_sync_next()" is bad and exposes the implementation,
> we can rename it to "__cds_wfq_next_blocking_nocheck()" to hide the implementation.
> 
> "get_next_nocheck": get next node of a queue, the caller ensure that the next node is existed.
> "get_next": get next node of a queue, it also finds out that whether the next node is existed or not.
> 
> Or just remove "cds_wfq_node_sync_next()", use "get_next" instead.
> 
>>
>> About cds_wfq_dequeue_all_blocking(): the "cds_wfq_splice()" I
>> introduced performs the same action as "cds_wfq_dequeue_all_blocking()",
>> but ensures that we can splice lists multiple times (rather than only
>> once), which is a very neat side-effect. Let's imagine a use-case like
>> Tree RCU, where each CPU produce a queue of call_rcu callbacks, and we
>> need to merge pairs of queues together recursively until we reach the
>> tree root: by doing splice() at each level of the tree, we can combine
>> the queues into a single queue without ever needing to do an iteration
>> on each node: no node synchronization is needed until we actually need
>> to traverse the queue at the root node level.
>>
>> The cost of exposing dequeue_all is that we need to expose sync_next
>> (more complexity for the user). As you exposed in your earlier email,
>> the gain we get by exposing dequeue_all separately from splice is that
>> dequeue_all is 1 xchg() operation, while splice is 2 xchg() operations.
>> However, given that this operation is typically amortized over many
>> nodes makes performance optimization a less compelling argument than
>> simplicity of use.
> 
> Reducing the temporary big struct is also my tempt.
> 
> ---
> Related to "internal", see the bottom.
> 
>>
>>>
>>> 5) Add more for_each_*, which default semantic is dequeuing
>>>    Reason: __cds_wfq_for_each_blocking_undequeue is enough for undequeuing loops
>>> 	don't need to add more.
>>> 	looping and dequeuing are the most probable use-cases.
>>> 	dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
>>>    Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*
>>
>> I notice, in the iterators you added, the presence of
>> "cds_wfq_for_each_blocking_nobreak", and
>> "cds_wfq_for_each_blocking_nobreak_internal", which document that this
>> special flavor is needed for loops that do not have a "break" statement.
>> That seems to be very much error-prone and counter-intuitive for users,
>> and I would like to avoid that.
> 
> __cds_wfq_for_each_blocking_safe(remove-all) is also "no-break"(*), is it error-prone and ...?
> 
> So this is not a good reason to reject cds_wfq_for_each_blocking_nobreak(), if the user
> don't know how to use it, he should use cds_wfq_for_each_blocking() (the version in my
> patch which is dequeue()-based and we can break from the loop body)
> 
> __cds_wfq_for_each_blocking_safe() and cds_wfq_for_each_blocking_nobreak() are exactly the
> same semantic in "remove-all" and "no-break". but cds_wfq_for_each_blocking_nobreak()
> does NOT CORRUPT the queue.
> 
> So cds_wfq_for_each_blocking_nobreak() is yet another __cds_wfq_for_each_blocking_safe()
> and it don't corrupt the queue, it is really safer than __cds_wfq_for_each_blocking_safe().
> 
> """"footnote: (*)
> __cds_wfq_for_each_blocking_safe() should be used for "remove-none" or "remove-all"
> We should use __cds_wfq_for_each_blocking_undequeue() instead of __cds_wfq_for_each_blocking_safe(remove-none)
> """
> 
>>
>> The "internal" flavor, along with "sync_next" are then used in the
>> call_rcu code, since they are needed to get the best performance
>> possible. I don't like to use special, internal APIs for call_rcu: the
>> original motivation for refactoring the wfqueue code was testability,
>> and I would really like to make sure that the APIs we use internally are
>> also exposed to the outside world, mainly for testability, and also
>> because if we need to directly access internal interfaces to have good
>> performance, it means we did a poor job at exporting APIs that allow to
>> do the same kind of highly-efficient use of the queue. Exposing an API
>> with the "internal" keyword in it clearly discourages users from using
>> it.
> 
> Related to "internal" see the bottom.
> 
>>
>>
>>>
>>> 6) Remove __cds_wfq_for_each_blocking_safe
>>>    Reason: its semantic is not clear, hard to define a well-defined semantic to it.
>>> 	when we use it, we have to delete none or delete all nodes, even when we delete all nodes,
>>> 	struct cds_wfq_queue still becomes stale while looping or after loop.
>>
>> The typical use-case I envision is:
>>
>> - enqueue many nodes to queue A
>>
>> - then, a dequeuer thread splice the content of queue A into its temporary
>>   queue T (which head is local on its stack).
>>
>> - now, the thread is free to iterate on queue T, as many times as it
>>   likes, and it does not need to change the structure of the queue while
>>   iterating on it (read-only operation, without side-effect). The last
>>   time it iterates on queue T, it needs to use the _safe iteration and
>>   free the nodes.
>>
>> - after the nodes have been deleted, the queue T can be simply discarded
>>   (if on stack, function return will do so; if dynamically allocated,
>>   can be simply reinitialized to an empty queue, or freed).
> 
> My for_each_*() can do exactly the same thing in this use-case since we still
> have splice() and cds_wfq_for_each_blocking_nobreak()(safer **_safe()). Doesn't it?
> 
> The memory represented a struct queue is big.(two cache line), something we need to
> avoid to use it in the stack.(shorten the stack size or avoid to cost 2 or 3 additional cache line).
> 
> -----------a use case
> All these local field are hot in the stack(and for some reason, it is not in the registers)
> 	int count;
> 	struct cds_wfq_queue tmp;
> 	struct cds_wfq_node *node, *next;
> 
> It will use 4 cache line. Should we always recommend the users use splice()+tmp?
> 
>>
>> As you certainly noticed, we can iterate both on a queue being
>> concurrently enqueued to, and on a queue that has been spliced into.
>> Being able to use iterators and dequeue on any queue (initial enqueue,
>> or queue spliced to) is a feature: we can therefore postpone the
>> "sync_next" synchronization to the moment where loop iteration is really
>> needed (lazy synchronization), which keeps optimal locality of reference
>> of synchronization vs node data access.
>>
>>>
>>> 7) Rename old __cds_wfq_for_each_blocking() to __cds_wfq_for_each_blocking_undequeue()
>>>    Reason: the default semantic of the other for_each_* is dequeuing.
>>
>> I'm not convinced that "__cds_wfq_for_each_blocking_nobreak",
>> "__cds_wfq_for_each_blocking_nobreak_internal", and sync_next APIs are
>> improvements over the API I propose. For call_rcu, this turns
>>
>> cds_wfq_enqueue()
>> cds_wfq_splice_blocking()
>> __cds_wfq_for_each_blocking_safe() for iteration
>>
>> into:
>>
>> cds_wfq_enqueue()
>> __cds_wfq_dequeue_all_blocking()
>> __cds_wfq_for_each_blocking_nobreak_internal() for iteration
>>
>> Maybe we could do some documentation improvement to
>> "__cds_wfq_for_each_blocking(_safe)", __cds_wfq_first_blocking(),
>> __cds_wfq_next_blocking() API members I proposed. Maybe I did not
>> document them well enough ?
>>
> 
> It does be not enough for __cds_wfq_for_each_blocking_safe().
> 
> I *STRONGLY OPPOSE* __cds_wfq_for_each_blocking_safe()(although it is suggested by me).
> 
> If you oppose the dequeue_all(), I agreed with this list:
> 	Remove old __cds_wfq_for_each_blocking_safe()
> 	Use manual splice()+get_first()+get_next() for call_rcu_thread().
> 	Remove my proposed cds_wfq_for_each_blocking_nobreak()
> 	Remove my proposed sync_next(), dequeue_all().
> 	Keep dequeue-based for_each() (alternative: introduce it in future)
> 
> If you also agreed this list, could you please partially merge my patch to your patch
> and send it for review to reduce the review cycle. (don't forget the other minimal fixes in my patch)
> 
> ==========
> About internals:
> 
> I want to expose the for_each_*, I don't want to expose these helpers:
> 	cds_wfq_node_sync_next()
> 	cds_wfq_dequeue_all_blocking()
> 	__cds_wfq_dequeue_all_blocking()
> 	__cds_wfq_for_each_blocking_nobreak_internal()
> (and I want to disallow the users use these helpers directly).
> 
> but the for_each_* use these helpers, so I have to declare it in the urcu/wfqueue.h,
> and they become a part of ABI.
> 
> So these helpers become internal things, how to handle internal things
> in a exposed *.h?
> 
> I found "__cds_list_del()" and "__tls_access_ ## name ()" are also
> internals, and they are exposed. Are they exposed correctly?
> 
> In my view, exposed internals is OK, what we can do is disallowing
> the users use it directly and ensuring the compatibility.
> 
> And we don't need to test exposed internals directly via testcases, because they are
> internals, just like we don't need to test so much un-exposed internals.
> When we test the exposed API, the internals will be also tested.
> 
> The call_rcu_thread() use the internal directly and can't be tested as you mentioned.
> It is not totally true. call_rcu_thread() need to inject a "synchronize_rcu()"
> to __cds_wfq_for_each_blocking_nobreak(), so I have to use
> __cds_wfq_for_each_blocking_nobreak_internal().
> Tests for __cds_wfq_for_each_blocking_nobreak() are enough for call_rcu_thread().
> 
> In one word, I don't agreed full of your disgust to the exposed internals,
> but I agree to remove the ones introduced in my patch.
> 
> Thanks,
> Lai
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>