Cc: <linux-kernel@...>, Linus Torvalds <torvalds@...>, Andrew Morton <akpm@...>, Mike Galbraith <efault@...>, Arjan van de Ven <arjan@...>, Thomas Gleixner <tglx@...>, Dmitry Adamushko <dmitry.adamushko@...>, Srivatsa Vaddagiri <vatsa@...>
Hi Ingo,
sorry for the long delay, I've spent a week doing non-kernel work.
On Tue, Jul 10, 2007 at 12:39:50AM +0200, Ingo Molnar wrote:
Yes, that's what I tried to explain to a guy once : what I like with log(N)
algos is that even with N very large, log(N) is always small, and it's
sometimes faster to perform log(N) fast operations than 1 slow operation.
That's also why I don't care about balanced trees : my unbalanced trees may
hold 32 levels for 32 carefully chosen values, while balanced trees will
have 5 levels (worst difference between both). If I can insert and delete
a node 6 times faster, I always win. And quite frankly, I'm not interested
at the 32 entries case in a tree :-)
Well, I borrowed two 1GB sticks because I discovered that one of my 512MB
had one defect bit. It was finally an opportunity for me to push the test
this far.
indeed :-)
Yes, and in fact, I suspect that we still have an O(N) or O(N^2) pid
allocation algo somewhere (I did not look at the code), because forking
was very very slow when reaching those numbers. I'll possibly check this
when I have some spare time, because it reminds me a trivial source port
ring allocator I wrote a few years ago which was O(1). With 32k pids, it
will only require 64kB RAM for the whole system, and we may even optimize
it to spread CPUs entry points in order to nearly always avoid lock
contention.
I may probably try some time later (not this week-end, I have some 2.4 to
work on).
Yes but I prefer to merge it where it really bring something (I'll have a
look at epoll, I noticed epollctl() was 30% slower under 2.6 with an rbtree
as it is under 2.4 with a hash). Then people will tell me "you're completely
dumb, you could have improved it that way!" and then, once it's optimized to
be always faster than the rbtree, we can switch CFS to it again ;-)
Cheers,
Willy
-
