From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933111AbbFILPJ (ORCPT ); Tue, 9 Jun 2015 07:15:09 -0400 Received: from ns.horizon.com ([71.41.210.147]:48013 "HELO ns.horizon.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S932806AbbFILPF (ORCPT ); Tue, 9 Jun 2015 07:15:05 -0400 Date: 9 Jun 2015 07:15:02 -0400 Message-ID: <20150609111502.22465.qmail@ns.horizon.com> From: "George Spelvin" To: linux@horizon.com, peterz@infradead.org Subject: Re: [patch 2/7] timer: Remove FIFO guarantee Cc: linux-kernel@vger.kernel.org, tglx@linutronix.de, viresh.kumar@linaro.org In-Reply-To: <20150609102453.GT3644@twins.programming.kicks-ass.net> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Right, so while pairing (and fibonacci) heaps have O(log n) deletion, if you can delay heapification you can equally delay that extra cost. > But as you say, the heapification is a O(n) hit, which is not too > different from our current 'problem'. > But yes, interesting problem space this. It definitely gets my mind going. The issue that's occupying my thoughts right now is this... Given a "sublist" for a range of future times, the minimum time can be either a real timeout or a fake one. If it's a real one, there's a chance you might delete the minimum timeout on the list. you have to handle re-sorting after deletion to maintain a valid minimum time. You can have a fake list head, which avoids ever re-sorting, but you're bascially forcing a "tick": taking a timer interrupt at that time even though nothing needs it. One possibility that occurs to me would be to have fake heads on the sublists, but recognize them when they get selected as the "next timeout". If that happens, deletemin() them now from the remaining heap and find next *real* timeout. Basically, just like the current wheel, you'd have to do some scanning past possibly-empty sublists, but perhaps by using a much more efficient heap structure, the sublists could be made larger, so not as many heads would be needed. Radix sort isn't really O(n); it's O(n log N) with a small constant, where N is the range of *possible* values (e.g. N = 2^32, so log N = 32). But if you want high-resolution timers, N goes up a lot.