lkml.org 
[lkml]   [2013]   [Feb]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [RFC PATCH v3 1/3] sched: schedule balance map foundation
From
Date
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.





\
 
 \ /
  Last update: 2013-02-21 13:21    [W:0.063 / U:0.396 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site