Messages in this thread | | | Subject | Re: [RFC PATCH v3 1/3] sched: schedule balance map foundation | From | Peter Zijlstra <> | Date | Thu, 21 Feb 2013 12:37:41 +0100 |
| |
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.
| |