linux-kernel - Re: [PATCH 11/39] autonuma: CPU follow memory algorithm

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-next>] [day] [month] [year] [list]

Message-ID: <20120326203951.GZ5906@redhat.com>
Date:	Mon, 26 Mar 2012 22:39:51 +0200
From:	Andrea Arcangeli <aarcange@...hat.com>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	Hillf Danton <dhillf@...il.com>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Dan Smith <danms@...ibm.com>, Paul Turner <pjt@...gle.com>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Rik van Riel <riel@...hat.com>, Ingo Molnar <mingo@...e.hu>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Lee Schermerhorn <Lee.Schermerhorn@...com>, linux-mm@...ck.org,
	Suresh Siddha <suresh.b.siddha@...el.com>,
	Mike Galbraith <efault@....de>,
	Bharata B Rao <bharata.rao@...il.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Johannes Weiner <hannes@...xchg.org>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 11/39] autonuma: CPU follow memory algorithm

Hi,

On Mon, Mar 26, 2012 at 12:58:05PM -0700, Linus Torvalds wrote:
> On Mar 26, 2012 12:45 PM, "Andrea Arcangeli" <aarcange@...hat.com> wrote:
> >
> > As I wrote in the comment before the function, math speaking, this
> > looks like O(N) but it is O(1), not O(N) nor O(N^2). This is because N
> > = NR_CPUS = 1.
> 
> That's just stupid sophistry.

I agree, this is why I warned everyone in the comment before the
function with the adjective "misleading":

 * O(1) misleading math
 * aside, the number of cachelines touched with thousands of CPU might
 * make it measurable.

> No, you can't just say that it's limited to some large constant, and thus
> the same as O(1).

I pointed out it is O(1) just because if we use the O notation we may
as well do the math right about it.

I may not have been clear but I never meant that because it is O(1)
(NR_CPUS constant) it means it's already ok as it is now.

> 
> That's the worst kind of lie: something that's technically true if you look
> at it a certain stupid way, but isn't actually true in practice.
> 
> It's clearly O(n) in number of CPUs, and people told you it can't go into
> the scheduler. Stop arguing idiotic things. Just say you'll fix it, instead
> of looking like a tool.

About fixing it, this can be called at a regular interval like
load_balance() (which also has an higher cost than the per-cpu
schedule fast path, in having to walk over the other CPU runqueues) or
to be more integrated within CFS so it doesn't need to be called at
all.

I didn't think it was urgent to fix (also because it has a debug
benefit to keep it like this in the short term), but I definitely
intended to fix it.

I also would welcome people who knows the scheduler so much better
than me to rewrite or fix it as they like it.

To be crystal clear: I totally agree to fix this, in the comment
before the code I wrote:

 * it's good in the
 * short term for stressing the algorithm.

I probably wasn't clear enough, but I already implicitly meant it
shall be optimized further later.

If there's a slight disagreement is only on the "urgency" to fix it but
I will certainly change my priorities on this after reading your
comments!

Thanks for looking into this.
Andrea
--
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/