Re: [RFC PATCH v3 1/3] sched: schedule balance map foundation

[Peter Zijlstra]

On Thu, 2013-02-21 at 12:58 +0800, Michael Wang wrote:
> 
> You are right, it cost space in order to accelerate the system, I've
> calculated the cost once before (I'm really not good at this, please
> let
> me know if I make any silly calculation...), 

The exact size isn't that important, but its trivial to see its quadric.
You have a NR_CPUS array per-cpu, thus O(n^2).

( side note; invest in getting good at complexity analysis -- or at
least competent, its the single most important aspect of programming. )

...

> And the final cost is 3000 int and 1030000 pointer, and some padding,
> but won't bigger than 10M, not a big deal for a system with 1000 cpu
> too.

Maybe, but quadric stuff should be frowned upon at all times, these
things tend to explode when you least expect it.

For instance, IIRC the biggest single image system SGI booted had 16k
cpus in there, that ends up at something like 14+14+3=31 aka as 2G of
storage just for your lookup -- that seems somewhat preposterous.

The domain levels are roughly O(log n) related to the total cpus, so
what you're doing is replacing an O(log n) lookup with an O(1) lookup,
but at the cost of O(n^2) storage. 



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/