[ https://issues.apache.org/jira/browse/YARN6361?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=16115449#comment16115449
]
YunFan Zhou edited comment on YARN6361 at 8/6/17 3:04 PM:

[~yufeigu] Thank you very much, Yufei.
I have to say that this JIRA's description describes a very good idea, and I have achieved
the corresponding code.
I used *O(N)* complexity before sorting to calculate the properties of each application,
and then according to the computed properties of each application ordering all applications
using O(n*log(n)) complexity.
It does look a lot faster. And I'll test the bench mark tomorrow, and see how the optimization
of this approach improves performance compared to the unoptimized performance.
was (Author: daemon):
[~yufeigu] Thank you very much, Yufei.
I have to say that this JIRA's description describes a very good idea, and I have achieved
the corresponding code.
I used *O(N)* complexity before sorting to calculate the properties of each application,
and then according to the computed properties of each application ordering all applications
using O(n*log(n)) complexity.
It does look a lot faster. And I'll test the bench mark tomorrow, and see how the optimization
of this approach improves performance compared to the unoptimized performance.
Here are some snippets of the code I've written, and many of the details have to be changed.
But I think our general idea is similar, using O(N) complexity to calculate each of the Schedulable
attribute values (such as the *SchedulableInnerAttr*). Then, order N of the SchedulableInnerAttr
using O(n*log(n)) time complexity.
Because every member variable of the *SchedulableInnerAttr* is the base type, it can be very
fast in sorting. And it will be much faster than the traditional sort. I will upload the corresponding
detailed code and bench mark for the test tomorrow.Agree with what I said?
{code:java}
private Schedulable sched;
private boolean isDemandNotNone;
private boolean isNeedy;
private double minShareRatio;
private boolean isWeightExceedZero;
private double memorySizePerWeight;
private long startTime;
private String name;
public SchedulableInnerAttr(Schedulable sched) {
this.sched = sched;
this.isDemandNotNone = sched.getDemand().equals(Resources.none());
Resource resourceUsage = sched.getResourceUsage();
Resource minShare = Resources.min(RESOURCE_CALCULATOR, null,
sched.getMinShare(), sched.getDemand());
this.isNeedy = Resources.lessThan(RESOURCE_CALCULATOR, null,
resourceUsage, minShare);
this.minShareRatio = (double) resourceUsage.getMemorySize() /
Resources.max(RESOURCE_CALCULATOR, null, minShare, ONE)
.getMemorySize();
double weight = sched.getWeights().getWeight(ResourceType.MEMORY);
this.isWeightExceedZero = weight > 0.0;
this.memorySizePerWeight = resourceUsage.getMemorySize();
if (this.isWeightExceedZero) {
this.memorySizePerWeight /= weight;
}
this.startTime = sched.getStartTime();
this.name = sched.getName();
}
{code}
{code:java}
@Override
public int compare(SchedulableInnerAttr s1, SchedulableInnerAttr s2) {
int res = 0;
if (s1.isDemandNotNone() && !s2.isDemandNotNone()) {
res = 1;
} else if (!s1.isDemandNotNone() && s2.isDemandNotNone()) {
res = 1;
}
if (res == 0) {
if (s1.isNeedy() && !s2.isNeedy()) {
res = 1;
} else if (!s1.isNeedy() && s2.isNeedy()) {
res = 1;
}
}
if (res == 0) {
res = (int) Math.signum(s1.getMinShareRatio()  s2.getMinShareRatio());
}
if (res == 0) {
if (s1.isWeightExceedZero() && !s2.isWeightExceedZero()) {
res = 1;
} else if (!s1.isWeightExceedZero() && s2.isWeightExceedZero()) {
res = 1;
}
}
if (res == 0) {
res = (int) Math.signum(s1.getMemorySizePerWeight()  s2.getMemorySizePerWeight());
}
if (res == 0) {
res = (int) Math.signum(s1.getStartTime()  s2.getStartTime());
}
if (res == 0) {
res = s1.getName().compareTo(s2.getName());
}
return res;
}
{code}
> FairScheduler: FSLeafQueue.fetchAppsWithDemand CPU usage is high with big queues
> 
>
> Key: YARN6361
> URL: https://issues.apache.org/jira/browse/YARN6361
> Project: Hadoop YARN
> Issue Type: Subtask
> Reporter: Miklos Szegedi
> Assignee: YunFan Zhou
> Attachments: dispatcherthread.png, threads.png, YARN6361.001.pre.patch
>
>
> FSLeafQueue.fetchAppsWithDemand sorts the applications by the current policy. Most of
the time is spent in FairShareComparator.compare. We could improve this by doing the calculations
outside the sort loop {{(O\(n\))}} and we sorted by a fixed number inside instead {{O(n*log\(n\))}}.
This could be an performance issue when there are huge number of applications in a single
queue. The attachments shows the performance impact when there are 10k applications in one
queue.

This message was sent by Atlassian JIRA
(v6.4.14#64029)

To unsubscribe, email: yarnissuesunsubscribe@hadoop.apache.org
For additional commands, email: yarnissueshelp@hadoop.apache.org
