linux-kernel - Re: [PATCH] perf_events: fix and improve x86 event scheduling

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]

Date:	Mon, 14 Nov 2011 22:43:09 +0100
From:	Peter Zijlstra <peterz@...radead.org>
To:	Stephane Eranian <eranian@...gle.com>
Cc:	Robert Richter <robert.richter@....com>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"mingo@...e.hu" <mingo@...e.hu>,
	"ming.m.lin@...el.com" <ming.m.lin@...el.com>,
	"ak@...ux.intel.com" <ak@...ux.intel.com>
Subject: Re: [PATCH] perf_events: fix and improve x86 event scheduling

On Mon, 2011-11-14 at 18:39 +0100, Stephane Eranian wrote:
> On Mon, Nov 14, 2011 at 5:00 PM, Peter Zijlstra <peterz@...radead.org> wrote:
> > On Mon, 2011-11-14 at 15:26 +0100, Stephane Eranian wrote:
> >> There is an edge from the source to all the events.
> >> There is an edge from all the counters to the sync.
> >> There is an edge between an event and a counter, if
> >> it can count the event.
> >>
> >> The capacity of any edge is 1.
> >
> > Ah indeed.
> >
> > So that gives:
> >
> >  E = e+e*c+c ~= O(c^2); since e<=c
> >  V = 2+e+c   ~= O(c)
> >
> > Then going by:
> >
> > http://en.wikipedia.org/wiki/Maximum_flow_problem
> >
> > we have to stay away from Edmonds-Karp.
> >
> > Ford-Fulkerson would end up being O(E * c) = O(c^3), since max |f| is c.
> > Which is pretty much identical to all these O(V^2 E) = O(c^3) as well.
> >
> > Dinitz blocking flow with dynamic trees looks more interesting at O(c^2
> > log(c)). Push relabel with dynamic trees looks to be best at O(c^2),
> > since V^2/E ends up being c^2/c^2 = 1.
> >
> > Creating the graph itself will be O(c^2) as well, due to E.
> >
> I think we are in the special case of a bi-partite graph with unit capacities,
> thus the complexity can be reduced even more.
> 
> See Special Cases in http://en.wikipedia.org/wiki/Dinic%27s_algorithm

Yeah, I found that, but that still reduces to O(c^2.5) which is over the
O(c^2) of Push relabel with dynamic trees.

I haven't managed to wrap my head around this stuff well enough to even
start to have an idea if this constraint (bi-partite and unit
capacities) will have any considerable effect on the other algorithms.

Also, we don't need an exhaustive max flow solution, any flow that's
high enough to fit the required capacity will do, this too could
possibly be used to lower the (average) complexity bound.

I would really really like it to not average to O(n^3), that's just
silly expensive.

Also, do you have any objections to me merging Roberts stuff (provided
it passes review etc.) while you poke at alternative solutions? We can
always replace the stuff again if we find anything that works better.
--
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/