All of lore.kernel.org
 help / color / mirror / Atom feed
From: Ingo Molnar <mingo@elte.hu>
To: Robert Richter <robert.richter@amd.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
	Stephane Eranian <eranian@google.com>,
	LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH 4/4] perf, x86: Fix event scheduler to solve complex scheduling problems
Date: Sun, 17 Apr 2011 10:18:27 +0200	[thread overview]
Message-ID: <20110417081827.GC29733@elte.hu> (raw)
In-Reply-To: <20110417081540.GL31407@erda.amd.com>


* Robert Richter <robert.richter@amd.com> wrote:

> > I'd really prefer not to do this for .39, and I'll have to sit down and 
> > actually read this code. It looks like we went from O(n^2) to O(n!) or 
> > somesuch, also not much of an improvement. I'll have to analyze the solver 
> > to see what it does for 'simple' constraints set to see if it will indeed 
> > be more expensive than the O(n^2) solver we had.
> 
> It wont be more expensive, if there is a solution. But if there is no one we 
> walk all possible ways now which is something like O(n!).

So with 6 counters it would be a loop of 720, with 8 counters a loop of 40320, 
with 10 counters a loop of 3628800 ... O(n!) is not fun.

Thanks,

	Ingo

  reply	other threads:[~2011-04-17  8:18 UTC|newest]

Thread overview: 38+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-04-16  0:27 [PATCH 0/4] perf, x86: Fixes for v2.6.39 Robert Richter
2011-04-16  0:27 ` [PATCH 1/4] perf, x86: Fix pre-defined cache-misses event for AMD family 15h cpus Robert Richter
2011-04-19 12:03   ` [tip:perf/urgent] " tip-bot for Andre Przywara
2011-04-16  0:27 ` [PATCH 2/4] perf, x86: Fix AMD family 15h FPU event constraints Robert Richter
2011-04-19 12:04   ` [tip:perf/urgent] " tip-bot for Robert Richter
2011-04-16  0:27 ` [PATCH 3/4] perf, x86: Use ALTERNATIVE() to check for X86_FEATURE_PERFCTR_CORE Robert Richter
2011-04-18 20:00   ` Andi Kleen
2011-04-19 10:39     ` Robert Richter
2011-04-19 18:21       ` Andi Kleen
2011-04-19 12:04   ` [tip:perf/core] " tip-bot for Robert Richter
2011-04-16  0:27 ` [PATCH 4/4] perf, x86: Fix event scheduler to solve complex scheduling problems Robert Richter
2011-04-16  8:51   ` Peter Zijlstra
2011-04-16  9:43     ` Ingo Molnar
2011-04-16 10:08       ` Peter Zijlstra
2011-04-16 10:14         ` Ingo Molnar
2011-04-16 10:15           ` Peter Zijlstra
2011-04-16 14:26         ` Valdis.Kletnieks
2011-04-17  8:15     ` Robert Richter
2011-04-17  8:18       ` Ingo Molnar [this message]
2011-04-17  8:53         ` Peter Zijlstra
2011-04-17 11:23           ` Robert Richter
2011-04-18  8:17             ` Robert Richter
2011-04-16 15:52   ` Stephane Eranian
2011-04-17  8:44     ` Robert Richter
2011-04-17  9:05       ` Stephane Eranian
2011-04-19 10:26   ` [PATCH v2] perf, x86: Fix event scheduler for constraints with overlapping counters Robert Richter
2011-04-19 11:29     ` Ingo Molnar
2011-04-19 13:55       ` Robert Richter
2011-04-28  9:50         ` Robert Richter
2011-05-18 21:16     ` Peter Zijlstra
2011-05-18 21:20       ` Ingo Molnar
2011-05-18 21:36         ` Peter Zijlstra
2011-05-19 10:49           ` Robert Richter
2011-05-19 18:06           ` Ingo Molnar
2011-05-20  3:18             ` Robert Richter
2011-09-01 12:56               ` Peter Zijlstra
2011-09-01 14:12                 ` Robert Richter
2011-09-01 16:37                   ` Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20110417081827.GC29733@elte.hu \
    --to=mingo@elte.hu \
    --cc=eranian@google.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peterz@infradead.org \
    --cc=robert.richter@amd.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.