[lkml]   [2007]   [Jun]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [patch 1/2] ufd v1 - unsequential O(1) fdmap core
On Mon, 4 Jun 2007 16:12:35 +0200
Ingo Molnar <> wrote:

> * Eric Dumazet <> wrote:
> > O(1) lookup doesnt imply it needs to be super-fast. You make a
> > confusion about this.
> Davide has written many good speedups for the kernel and he is one of
> the best scalability experts the Linux kernel has today. You could learn
> from Davide a thing or two, instead of lecturing him about O(1) ...

I know who is Davide, thank you :)

> For example, the recent futex.c changes you did in commit 34f01cc1 are,
> and unfortunately there's no better word i can find: plain disgusting.
> You apparently have plopped the 'fshared' code into the existing logic
> via conditionals and have blown up the complexity of the functions for
> no good reason - instead of neatly separating them out. You have added
> _33_ (thirty-three!) new 'if' branches to futex.c! The feature you
> introduced is nice and useful, but for heaven's sake please work on
> cleanliness of your code some more and undo that colossal damage ...
> preferably before working on other areas of the kernel.

This code took the normal path for inclusion and discussion. If you find it so horrible,
you should complained before. Fact is that you Acked it :)

If you wanted to make a joke, I find it quite misplaced.

> > O(128) is still O(1) for instance. Having to search a bit in a PAGE is
> > a sensible compromise, if we dont add overhead on each fget() calls.
> hm, i'm not sure what you are talking about here. Look at Davide's stuff
> - it's clearly not O(128)...

I am talking about my suggestion to use a bitmap search limited to one page.

So I named it O(128), this clearly should be labeled O(PAGE_SIZE/L1_CACHE_BYTES)

> > You add conditional branches on very hot spots.
> >
> > When you open/close a file, you need to access previous and next
> > cells, so you need 3 cache lines, exactly like current *legacy* code.
> > (one for file pointer, one on each bitmap flags(open/close_on_exec) )
> the fd spaces will be separated _no matter what_, that is a physical
> inevitability of the ABI in question. Whether you hide that into 'extra
> complexity by trying to bend bitmaps in a way that the new users dont
> need' or do it explicitly like Davide, i'll go for the explicit
> separation. Davide's approach, besides being cleaner, simpler and faster
> also has the advantage of enabling the possible demoting of the 'legacy'
> fd space in the future. Or demoting the 'new' fd space in the future, if
> the interface does not take off.
> Ingo

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2007-06-04 16:29    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean