Re: [GIT PULL] kdbus for 4.1-rc1

[Borislav Petkov <bp@alien8.de>]

On Thu, Apr 23, 2015 at 10:02:52PM -0700, Steven Noonan wrote:
> On Thu, Apr 23, 2015 at 2:41 PM, Borislav Petkov <bp@alien8.de> 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.
--