On 06/05/2014 12:56 PM, Peter Zijlstra wrote: > On Thu, Jun 05, 2014 at 01:37:25AM +0530, Srivatsa S. Bhat wrote: >> On 06/05/2014 01:17 AM, Peter Zijlstra wrote: >>> On Thu, Jun 05, 2014 at 01:09:35AM +0530, Srivatsa S. Bhat wrote: >>>> The current implementation of lockless list (llist) has a drawback: if we >>>> want to traverse the list in FIFO order (oldest to newest), we need to >>>> reverse the list first (and this can be expensive if the list is large, >>>> since this is an O(n) operation). >>> >>> Have you actually looked at the queue depth of this thing? Large queues >>> are a problem for interrupt latency. >>> >> >> Actually, I wrote this patch just by looking at the code and realizing >> that we don't need to reverse the list. In practice, I haven't actually >> seen any noticeable interrupt latencies or large queues so far. So I think >> this patch is just a very tiny optimization, that's all. > > So conceptually it makes sense to service in FIFO because the first > entry is waiting longest, by servicing them in LIFO order you get far > more variance in latency. > > And if the list is small, the cost isn't high. > > Then again, we don't have any good numbers one way or the other. >
Hmm, right. I thought hard to see if there is a clever way to maintain the llist in the FIFO order itself, while still preserving the atomicity guarantees, but I couldn't think of anything sane :-( Regards, Srivatsa S. Bhat -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
