Performance Issue in GB

[Deepak]

Hello,

I am trying to run a multi-threaded implementation of bubble sort on
Ginger Bread. Sometimes ( 5 out of 25) the performance of the
application degrades drastically. Upon some investigation, It appears
that the reason for performance degrade is due to the exception raised
due to the native code generated by the JIT compiler.

When the control returns from the JIT native code to interpreter to
handle the exception, it executes "dvJitToInterpPunt" function( The
punt count is unusually large in case of performance degrade). After
executing this function, control is transferred to interpreter to
interpret the following opcodes in the function. Since one of the
opcodes is "goto" and it is a backward branch, control goes to the
function "common_backwardBranch" . In this function it goes into a
tight loop, though there is none. ( Or is it an issue with gdb??).

I ran the same application in self verification mode to find if there
are any issues in the code generation, but it ran consistently all the
time.( 20 times).

This looks like a bug in JIT. Can someone help me in debugging the
native code ?

Thanks,
Deepak

[Ben Cheng]

I suspect the performance variance is due to some speculative optimizations done by the JIT. For example, if you have a virtual callsite that is resolved to more than one callee, some of them will be dispatched faster than the others. Depending on the timing of execution and distribution of the workload one can observe the performance variance from time to time.

If you can share with us your bubble sort implementation we'll be more than happy to root cause the behavior.

Thanks,

-Ben

--
You received this message because you are subscribed to the Google Groups "android-platform" group.
To post to this group, send email to android-...@googlegroups.com.
To unsubscribe from this group, send email to android-platfo...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/android-platform?hl=en.

[Deepak]

Below is our implementation.

import java.util.Random;

public class Bubble {
private int sortArraySize = 10000;
int nThreads = 8;
int unSorted[];
int sorted[];
int mTid = 0;
Object tidLock;
int oneUnit = 0;
int syncCnt = 0;
Object syncCntLock;
int arraySeed = 12345;
long baseTime = 0;

private int[] prepareData()
{
int toSort[] = new int[sortArraySize];
Random random = new Random(arraySeed);
for(int i = 0; i < sortArraySize; i++)
toSort[i] = random.nextInt();

return toSort;
}

class workerThread implements Runnable
{
private int myId;
private void sort(int toSort[], int stIdx, int edIdx)
{
boolean done = true;

for(int i = edIdx; i >= 0; i--)
{
int j = (stIdx + i) - 1;
for(int k = stIdx; k < j; k++)
if(toSort[k] > toSort[k + 1])
{
int tmp = toSort[k];
toSort[k] = toSort[k + 1];
toSort[k + 1] = tmp;
done = false;
}
if(done)
return;
done = true;
}
}

public void run()
{
synchronized (tidLock)
{
myId = mTid++;
}
long curTime;
curTime = System.currentTimeMillis();
System.out.println("["+myId+"] "+"sort begin, ms "+(curTime-
baseTime));
sort(unSorted, myId * oneUnit, oneUnit);
curTime = System.currentTimeMillis();
System.out.println("["+myId+"] "+"sort end, ms "+(curTime-
baseTime));
synchronized (syncCntLock)
{
syncCnt++;
if (syncCnt == nThreads)
syncCntLock.notifyAll();
}
}
}

public void doMain()
{
baseTime = System.currentTimeMillis();
unSorted = prepareData();
oneUnit = sortArraySize / nThreads;
for(int i = 0; i < nThreads; i++)
(new Thread(new workerThread())).start();

synchronized (syncCntLock)
{
try
{
if (syncCnt != nThreads)
syncCntLock.wait();
}
catch (Exception e)
{
throw new RuntimeException("Wait Failed!" + e.getMessage());
}
}
long curTime = System.currentTimeMillis();
System.out.println("======================");
System.out.println("Total time, ms: "+(curTime-baseTime));
}

Bubble()
{
tidLock = new Object();
syncCntLock = new Object();
}

Bubble(int threadNum)
{
tidLock = new Object();
syncCntLock = new Object();
nThreads = threadNum;
}

public static void main(String[] args) {
boolean androidTracing = false;
int threadNum = 8;
String traceFile = "bubbletrace";

System.out.println("argument: [threadnum] ");
if (args.length >= 1)
{
threadNum = Integer.parseInt(args[0], 10);

if ((threadNum < 1) || (threadNum > 8))
threadNum = 8;
}
System.out.println("Using " + threadNum + " threads..");


Bubble bubble = new Bubble(threadNum);
bubble.doMain();

> > android-platfo...@googlegroups.com<android-platform%2Bunsubscrib e...@googlegroups.com>
> > .

[Ben Cheng]

The performance variance you saw in your program was introduced by the call to resetTracehead() in interp/Jit.c. If you have access to the whole tree, try to comment it out and you should get a consistent number for your microbenchmark.

We will re-evaluate the heuristic to see if we can avoid the performance issues (as the comment said in the code).

Thanks for reporting,

-Ben

To unsubscribe from this group, send email to android-platfo...@googlegroups.com.