From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752253AbcFNM6E (ORCPT ); Tue, 14 Jun 2016 08:58:04 -0400 Received: from ns.sciencehorizons.net ([71.41.210.147]:28284 "HELO ns.sciencehorizons.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1751812AbcFNM6C (ORCPT ); Tue, 14 Jun 2016 08:58:02 -0400 Date: 14 Jun 2016 08:58:00 -0400 Message-ID: <20160614125800.18461.qmail@ns.sciencehorizons.net> From: "George Spelvin" To: linux@sciencehorizons.net, peterz@infradead.org Subject: Re: [patch 13/20] timer: Switch to a non cascading wheel Cc: edumazet@google.com, linux-kernel@vger.kernel.org, richardcochran@gmail.com, tglx@linutronix.de In-Reply-To: <20160614102022.GE30909@twins.programming.kicks-ass.net> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Peter Zijlstra wrote: > That did occur to me as well; however I think it would be best to > eradicate all forms of cascading entirely -- if at all possible. Agreed. >> to be replaced with __builtin_clz or similar: > Problem is for the archs that don't have that, the 5 layer branch is > trivial for all arches, while software clz/fls is far more expensive. And there's no way to tell if an architecture has a good one, so bleah. I was thinking about the flosting-point number representation and what the effect of a finer table spacing would be. The maximum error is determined by the difference between LVL_BITS (=6) and LVL_CLK_SHIFT(=3). If you dropped those both by 1, you'd get 2/3 as many bits of timer in 1/2 the space, which would be a slight space saving. The current 6 levels (64 * 6 = 384 lists) covering 6 + 3*5 = 21 bits be done 32 * 9 = 288 lists (5 + 2*8 = 21). Not enough to be interesting, and the extra levels increase processing time. If you need to shrink TIMER_ARRAYMASK to fit another flag bit, the easier way would be to encode only the level rather than the index, since you can derive the latter from level and expiry time trivially. A couple of really minor tweaks that could be folded in, if Thomas feels like it: * It would make sense to move all the TIMER_ARRAYSHIFT/TIMER_ARRAYMASK stuff out of patch 13 and into patch 20. * It would make sense to change the return type of mod_timer (& Co.) detach_if_pending, and del_timer to bool. ({try_to_,}del_timer_sync return 3 values.)