Re: ask for help to implement a high performance sliding window

Re: ask for help to implement a high performance sliding window

[Paul E. McKenney]

Hello, LoopJump,

Glad you like the book!  Adding perfbook@vger.kernel.org on CC in case
someone there has some good ideas.

First, I do feel the need to ask if you have actually benchmarked the
system and seen maximum computation to be a problem, perhaps on a profile.
After all, there is little payoff in optimizing portions of the system
that are not bottlenecks!

Second, let me make sure that I understand the problem:

1.	Your system receives sequence numbers on incoming packets.

2.	Each packets is processed, after which the corresponding sequence
	number should be included in a global "max" computation.

3.	If the whole thing isn't protected by a global lock, we know
	that the thread reading out the maximum value will get a snapshot
	that immediately becomes stale.  The reason for this instant
	staleness is that some other thread might immediately complete
	processing for another packet, and that packet's sequence number
	might update the maximum.

4.	I am assuming that the sequence number is large enough that
	overflow is not a problem.  If overflow is possible, things
	become quite interesting when a given packet's processing takes
	a very long time.

5.	I am assuming that packets are processed very quickly.	If this
	assumption is incorrect and packets take (say) ten milliseconds
	to process, then you should be able to use pretty much any method
	of updating the maximum.  But if packet processing was that slow,
	you probably wouldn't be asking me this question.

Third, some thoughts on implementing this efficiently.

By #3 above, we know that the thread reading out the maximum can have
a stale value.  Just how much staleness can be tolerated?

If (say) a millisecond of staleness is OK, one approach is to have each
thread maintain the maximum sequence number that it has encountered
thus far.  Maintaining this per-thread value should be extremely
efficient.  Then a separate thread (or function or whatever) can run
every millisecond, taking the maximum of the per-thread maxima.

Alternatively, each thread can periodically update the global maximum
based on that thread's local state.

Either way, the point is to update the global maximum less frequently
and thus have less problem with cache misses associated with such updates.

							Thanx, Paul

On Fri, Dec 08, 2017 at 09:21:16AM +0800, LoopJump wrote:
> Hi Paul,
> 
> I am a database kernel developer, I really love your book about parallel programming.
> 
> Now I encounter a question about a high performance sliding window in a multi threads program.
> 
> In my question, incoming request has a consecutive sequence(integer), these requests will be pushed into a thread pool(16 threads), what I want is to track the max_consecutive_sequence that has been processed.
> 
> I tried to use a bitmap (a bit for one sequence or replace a bit with 64bytes item to avoid false sharing) to mark each sequence. Everytime a request is processed, it check if it can advance the max_consecutive_sequence and determine how many sequence it can advance. 
> 
> I do not know if there is a better way to implement such a sliding window.
> 
> Thanks a lot for your help. 
> 
> 
> 
> LoopJump