Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756144AbbDXJET (ORCPT ); Fri, 24 Apr 2015 05:04:19 -0400 Received: from mail.skyhub.de ([78.46.96.112]:60738 "EHLO mail.skyhub.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S934577AbbDXJEP (ORCPT ); Fri, 24 Apr 2015 05:04:15 -0400 Date: Fri, 24 Apr 2015 11:04:03 +0200 From: Borislav Petkov To: Steven Noonan Cc: David Herrmann , Greg Kroah-Hartman , "Eric W. Biederman" , Linus Torvalds , Andrew Morton , Arnd Bergmann , One Thousand Gnomes , Tom Gundersen , Jiri Kosina , Andy Lutomirski , linux-kernel , Daniel Mack , Djalal Harouni Subject: Re: [GIT PULL] kdbus for 4.1-rc1 Message-ID: <20150424090402.GA24014@pd.tnic> References: <20150413190350.GA9485@kroah.com> <8738434yjk.fsf@x220.int.ebiederm.org> <20150422085827.GA6962@pd.tnic> <20150423191433.GB13607@kroah.com> <20150423205640.GR28327@pd.tnic> <20150423214111.GT28327@pd.tnic> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2390 Lines: 54 On Thu, Apr 23, 2015 at 10:02:52PM -0700, Steven Noonan wrote: > On Thu, Apr 23, 2015 at 2:41 PM, Borislav Petkov wrote: > > On Thu, Apr 23, 2015 at 11:22:39PM +0200, David Herrmann wrote: > >> No it's not. O(256) equals O(1). > > > > Ok, you're right. Maybe O() was not the right thing to use when trying > > to point out that iterating over 256 hash buckets and then following the > > chain in each bucket per packet broadcast looks like a lot. > > > > Heh. I guess you could call it an "expensive O(1)". While big-O > notation is useful for describing algorithm scalability with respect > to input size, it falls flat on its face when trying to articulate > impact in measurable units. Right, so in thinking about this more today, on a fresh head, it still is O(n) because we do broadcast the packet to n recipients - the hash_for_each() thing iterates over 256 hash buckets and also follows the linked list chain in each bucket. Its length is depending on how many connections are in the bucket, i.e. recipients. And I'd guess that number changes dynamically so probably linear. And then there's the collection of, let's call it metadata of questionable use, *per* packet which is pretty expensive in my book. It becomes even more expensive if it is completely useless as in, the receiving side doesn't need it all. Now, one might argue that you have to do O(n) work when broadcasting to n recipients anyway and you can't get that cheaper but maybe the design is not optimal. Maybe it could be made to not broadcast at all, or broadcast to a subset of recipients, only those which are actually interested in the broadcast. That's why I was looking at some simple token-based schemes. And that's why I think Andy has some very cool ideas which we should definitely pay attention to: https://lkml.kernel.org/r/CALCETrXXUiYKAhsXsdqH2uZMddDhK5hX6V9%2BrZcHwa1X5WC%2B1g@mail.gmail.com before we go and commit this thing and cast it stone. Because if it goes in, there's no changing it because we'll be then breaking userspace and that's no-no. -- Regards/Gruss, Boris. ECO tip #101: Trim your mails when you reply. -- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/