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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1361446661.26780.15.camel@laptop>
Date:	Thu, 21 Feb 2013 12:37:41 +0100
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Michael Wang <wangyun@...ux.vnet.ibm.com>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>, Paul Turner <pjt@...gle.com>,
	Mike Galbraith <efault@....de>,
	Andrew Morton <akpm@...ux-foundation.org>, alex.shi@...el.com,
	Ram Pai <linuxram@...ibm.com>,
	"Nikunj A. Dadhania" <nikunj@...ux.vnet.ibm.com>,
	Namhyung Kim <namhyung@...nel.org>
Subject: Re: [RFC PATCH v3 1/3] sched: schedule balance map foundation

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/