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
next prev parent 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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).