Re: Question about list_sort() RCU version.

From: Chaitanya Kulkarni <Chaitanya.Kulkarni@wdc.com>
To: "paulmck@kernel.org" <paulmck@kernel.org>,
	Steven Rostedt <rostedt@goodmis.org>
Cc: Josh Triplett <josh@joshtriplett.org>,
	"rcu@vger.kernel.org" <rcu@vger.kernel.org>,
	"mathieu.desnoyers@efficios.com" <mathieu.desnoyers@efficios.com>,
	"jiangshanlai@gmail.com" <jiangshanlai@gmail.com>
Subject: Re: Question about list_sort() RCU version.
Date: Tue, 16 Jun 2020 23:21:56 +0000	[thread overview]
Message-ID: <BYAPR04MB49657ED94E122D33B9C53403869D0@BYAPR04MB4965.namprd04.prod.outlook.com> (raw)
In-Reply-To: 20200616222933.GH2723@paulmck-ThinkPad-P72

On 6/16/20 3:29 PM, Paul E. McKenney wrote:
> If you want things sorted, why not a search tree?  Or, depending on the
> purpose of the sorting, a hash table?
That was my first question but the way code is written right not which 
uses linked list and then it calls list_sort() which is not a ideal data 
structure to start with.
> 
> It actually is kind-of sort-of possible to do an in-place sort of a
> linked list in the presence of readers, but the simpler ways of doing
> this are not at all pretty.  Or efficient while the sort is in progress.
> 
That is what I felt after reading a code and I'm not an expert in this 
area.
> o	Find the largest element in the yet-to-be-sorted portion of
> 	the list.  Pull that largest element to the front of the list
> 	as follows:
> 
> 	o	Set its ->next pointer to reference the first
> 		element of the list.  (Yes, the list is now
> 		looped, and readers looking for later elements
> 		will follow that loop.  Readers must do loop
> 		detection, and restart their traversal after
> 		momentarily exiting their read-side critical
> 		sections.)
> 
> 	o	Set the header pointer to reference the element
> 		being moved.  The list is still looped.
> 
> 	o	Wait for a grace period.  This is why looping
> 		readers must momentarily exit their read-side
> 		critical sections.
> 
> 	o	Make the moved item's predecessor point to the
> 		moved item's successor.
> 
> o	Repeat until the list is sorted.
> 
> Another approach is similar to Steven's suggestion, but uses a
> separate set of pointers to do the sorting, then switches the
> readers to the sorted set.  This allows better sorting algorithms
> to be used.
> 
This is the most easy approach with high memory usage.

> But why not just insert each element into its proper place in the list
> to start with?  If the list is too long for this to be efficient, you
> most likely should be using some other data structure.
> 
Agree, again not my design, and after these emails I do have questions 
on the data structure since with an efficient data structure set of the
items are also be cached that will furthermore improve the performance 
given that size of the ids is cacheline friendly.

> 						Thanx, Paul

Thanks again everyone for replying promptly and in detailed manner.