Hello, On Mon, Oct 28, 2013 at 11:00:55AM +0800, Wei Yang wrote: > >Does this actually matter? If so, it'd probably make a lot more sense > >to start inner loop at @cpu + 1 so that it becomes O(N). > > One of the worst case in my mind: > > CPU: 0 1 2 3 4 ... > Group: 0 1 2 3 4 ... > (sounds it is impossible in the real world)
I was wondering whether you had an actual case where this actually matters or it's just something you thought of while reading the code. > Every time, when we encounter a new CPU and try to assign it to a group, we > found it belongs to a new group. The original logic will iterate on all old > CPUs again, while the new logic could skip this and assign it to a new group. > > Again, this is a tiny change, which doesn't matters a lot. I think it *could* matter because the current implementation is O(N^2) where N is the number of CPUs. On machines, say, with 4k CPU, it's gonna loop 16M times but then again even that takes only a few millisecs on modern machines. > BTW, I don't get your point for "start inner loop at @cpu+1". > > The original logic is: > loop 1: 0 - nr_cpus > loop 2: 0 - (cpu - 1) > > If you found one better approach to improve the logic, I believe all the users > will appreciate your efforts :-) Ooh, right, I forgot about the break and then I thought somehow that would make it O(N). Sorry about that. I blame jetlag. :) Yeah, I don't know. The function is quite hairy which makes me keep things simpler and reluctant to make changes unless it actually makes non-trivial difference. The change looks okay to me but it seems neither necessary or substantially beneficial and if my experience is anything to go by, *any* change involves some risk of brekage no matter how innocent it may look, so given the circumstances, I'd like to keep things the way they are. Thanks a lot! -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
