Improve Java Code

[Sanny]

I have a below code I use a lot in my Java Program.

u1,i,j,u2,ux,mz are integer
Arr1 is char[]
BigARRAY is int[]

----------------------INITIAL CODE

u1=i+1;u2=j+1;
ux=u1*3+u2;
if ((u1<9)&&(u2<9)) {
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
-----------------------

How can this code be made more efficient.

Here is one effort by me by putting ux=u1*3+u2; inside the if
(condition)

------------------- IMPROVED CODE
u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
------------------

What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Bye
Sanny

 

[Patricia Shanahan]

I have a below code I use a lot in my Java Program. ....
What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Presumably you have a testbed for measuring the performance effects of
your changes. Could you post that? It would save anyone else who is
interested the work of creating one.

How often are u1 and/or u2 at least 9? Could you modify your loop
conditions to cut off when those conditions are reached? The cheapest
iterations are the ones you do not execute.

How big an improvement did you get from moving the ux arithmetic?

Patricia

 

[Sanny]

Presumably you have a testbed for measuring the performance effects of
your changes. Could you post that? It would save anyone else who is
interested the work of creating one.

I do not have any testbed, Only when the program is run The speed is
estimated depending on time taken to complete the Program.

How often are u1 and/or u2 at least 9? Could you modify your loop
conditions to cut off when those conditions are reached? The cheapest
iterations are the ones you do not execute.

u1 and u2 are random number between -2 and 12 It can be
-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12 Any of them at random.

How big an improvement did you get from moving the ux arithmetic?

Not yet seen but I thing 10-20% faster. Will tell you once tested.

Bye
Sanny

 

[Patricia Shanahan]

Sanny wrote:
....

Not yet seen but I thing 10-20% faster. Will tell you once tested.

....

The actual measurement is important because I would have expected your
time to be dominated by the conditional branches and/or memory access.
Conditional branches are especially expensive if they are unpredictable.

I would be wrong about that if the integer arithmetic move produces a
significant improvement.

Patricia

 

[bugbear]

I have a below code I use a lot in my Java Program.

u1,i,j,u2,ux,mz are integer
Arr1 is char[]
BigARRAY is int[]

----------------------INITIAL CODE

u1=i+1;u2=j+1;
ux=u1*3+u2;
if ((u1<9)&&(u2<9)) {
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
-----------------------

How can this code be made more efficient.

Here is one effort by me by putting ux=u1*3+u2; inside the if
(condition)

------------------- IMPROVED CODE
u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
------------------

What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Yes. Get the caller to move anything it can outside the loop,
or more generally improve your algorithms and data structures.

Failing this "proper" solution...

u1=i+1
if(u1 < 9)

is the same as:
if(i < 8)

so:
if ( i< 8 && j < 8) {
u1=i+1;
u2=j+1;
ux=u1*3+u2;
if (Arr1[ux]=='B') {
BigARRAY[++mz]=ux;}
}
}

This may be a shade faster.

BugBear

 

[bugbear]

I do not have any testbed, Only when the program is run The speed is
estimated depending on time taken to complete the Program.


u1 and u2 are random number between -2 and 12 It can be
-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12 Any of them at random.

Hmm. What is the expected range of values for ux,
and what is the size of the array Arr1 ?

BugBear

 

[Eric Sosman]

I do not have any testbed, Only when the program is run The speed is
estimated depending on time taken to complete the Program.


u1 and u2 are random number between -2 and 12 It can be
-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12 Any of them at random.

... which means that there are 121 pairs of values that
meet the requirement u1 < 9 && u2 < 9. Of these, 15 pairs
give rise to ux values that are negative. The ensuing
ArrayIndexOutOfBoundsException is sure to slow you down ...

 

[Sanny]

Yes. Get the caller to move anything it can outside the loop,

or more generally improve your algorithms and data structures.

Failing this "proper" solution...

u1=i+1
if(u1 < 9)

is the same as:
if(i < 8)

Yes But there are many Such i+1, i-1; j+1, j-2 etc. So each has to be
updated.

so:
if ( i< 8 && j < 8) {
     u1=i+1;
     u2=j+1;
     ux=u1*3+u2;
     if (Arr1[ux]=='B') {
         BigARRAY[++mz]=ux;}
     }

}
This may be a shade faster.

Good Idea.

I got a new idea by looking your way.

ux=u1*3+u2;
if (Arr1[ux]=='B') {
BigARRAY[++mz]=ux;}
}

Instead of this if I use

if (Arr1[u1*3+u2]=='B') {
BigARRAY[++mz]=u1*3+u2;}
}
Just elliminating ux? Will it be faster

Secondly

BigARRAY[++mz] is it same as
mz++;BigARRAY[mz]

And what about BigARRAY[mz++] is it same as
mz++;BigARRAY[mz]

Bye
Sanny

 

[Sanny]

Hmm. What is the expected range of values for ux,
and what is the size of the array Arr1 ?

Both size of Arr1 is 60 and expacted range of ux is 1..60.

Bye
Sanny

 

[Sanny]

I have a below code I use a lot in my Java Program.

u1,i,j,u2,ux,mz are integer
Arr1 is char[]
BigARRAY is int[]

----------------------INITIAL CODE

    u1=i+1;u2=j+1;
    ux=u1*3+u2;
    if ((u1<9)&&(u2<9)) {
       if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
    }
-----------------------

How can this code be made more efficient.

Here is one effort by me by putting ux=u1*3+u2; inside the if
(condition)

------------------- IMPROVED CODE
u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}}

------------------

What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Bye
Sanny

Any idea if I use List instead of Arrays, Will that be faster?

In the Equation

u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}}


The Probablity of True Value for below conditions are something as
follows.

(u1<9): 80% times True
(u2<9): 80% times True
(Arr1[ux]=='B') 25% times True.

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;
}
}

Will above code will be faster?

Bye
Sanny

 

[Sanny]

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;

}
}
Will above code will be faster?

Or Better Still

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
mz++;BigARRAY[mz]=u1*3+u2;
}
}


So the Code now is I think 3-4 times faster than Original code I
posted?

Bye
Sanny

 

[Sanny]

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;

}
}
Will above code will be faster?

Or Better Still

 u1=i+1;u2=j+1;
 if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
 if ((u1<9)&&(u2<9)) {
 mz++;BigARRAY[mz]=u1*3+u2;
 }
 }

So the Code now is I think 3-4 times faster than Original code I
posted?

Bye
Sanny

Whats the difference between i++ and ++i;

I heard u1=i+1;

Can I use ++ Such as u1=i++; But I do not want to increment value of
i; Why is i+1 slower than i++?

Bye
Sanny

 

[Thomas Kellerer]

Sanny, 10.01.2008 17:48:

Whats the difference between i++ and ++i;

See:

<http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.14.2>
<http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.15.1>

 

[Thomas Kellerer]

Sanny, 10.01.2008 17:40:

Any idea if I use List instead of Arrays, Will that be faster?

You will need a performance testbed as Patricia has suggested. Then the
answer to your question is easy:

run the testbed, note down the execution time, change the code, run the
testbed, compare the results.

Or get yourself a profile and profile your application with the modified
code.

 

[Patricia Shanahan]

Sanny wrote:
.....

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;
}
}

Will above code will be faster?

It depends on things like the predictability of the branches. A single
mispredicted branch can cost a lot more than all the integer arithmetic
in your code snippet. In this sort of code, you want to put highly
predictable if statements on the outside, so that you only execture
unpredictable ones if you really have to.

You do need a testbed program that extracts the relevant portions of
your application in which you can measure proposed changes.

Patricia

 

[rossum]

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;

}
}
Will above code will be faster?

Or Better Still

 u1=i+1;u2=j+1;
 if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
 if ((u1<9)&&(u2<9)) {
 mz++;BigARRAY[mz]=u1*3+u2;
 }
 }

So the Code now is I think 3-4 times faster than Original code I
posted?

Bye
Sanny

Whats the difference between i++ and ++i;

++i is a pre increment, i++ is a post increment. In terms of speed
there is probably no difference for integers. For references ++i is
never slower and may possibly be faster - it never has to preserve two
values in parallel.

I heard u1=i+1;

Can I use ++ Such as u1=i++; But I do not want to increment value of
i; Why is i+1 slower than i++?

Have you tested that? A good compiler should recognise "i+1" and
output the same bytecode as for "i++".

If there is a speed difference then you could try:
u1 = i;
++u1;

which does not affect the value of i.

 

[bugbear]

Both size of Arr1 is 60 and expacted range of ux is 1..60.

Right. Valid indexes for an array of size 60 is 0..59
if u1 and u2 can go as low as -2

ux=u1*3+u2;

ux = -2*3+-2

ux = -8

Your code appears to be bugged?

BugBear

 

[rossum]

I have a below code I use a lot in my Java Program.

u1,i,j,u2,ux,mz are integer
Arr1 is char[]
BigARRAY is int[]

----------------------INITIAL CODE

u1=i+1;u2=j+1;
ux=u1*3+u2;
if ((u1<9)&&(u2<9)) {
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
-----------------------

How can this code be made more efficient.

Here is one effort by me by putting ux=u1*3+u2; inside the if
(condition)

------------------- IMPROVED CODE
u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;

It may be that one of:

ux = u1 + u1 + u1 + u2;

or

ux = (u1 << 1) + u1 + u2;

or even

ux = (u1 << 2) - u1 + u2;

is faster here - you need to experiment.

rossum

if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
------------------

What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Bye
Sanny

 

[Patricia Shanahan]

Sanny wrote:
....

So If I Use

u1=i+1;u2=j+1;
if (Arr1[u1*3+u2]=='B'){// is True 25% times only.
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
mz++;BigARRAY[mz]=ux;
}
}

Will above code will be faster?

It depends on things like the predictability of the branches. A single
mispredicted branch can cost a lot more than all the integer arithmetic
in your code snippet. In this sort of code, you want to put highly
predictable if statements on the outside, so that you only execture
unpredictable ones if you really have to.

You do need a testbed program that extracts the relevant portions of
your application in which you can measure proposed changes.

Most people in this thread seem to be primarily concerned with the
integer arithmetic, so maybe I should explain my preoccupation with the
conditional branches.

Most processors now have deep, wide pipelines. That means that at any
given time there are dozens of instructions at some stage of being
processed, going through a sort of production line. As long as the work
keeps flowing smoothly, multiple instructions complete each cycle.
Evaluating some small integer expression can be tucked into the corners
of memory accesses, and is practically free.

Now consider what happens when a conditional branch enters the pipeline.
The processor has to decide what to put in the pipeline after it. Should
it carry on fetching the next instruction in memory order, or should it
switch to fetching the branch target and its memory order successors?

The processor does not find out whether it guessed right or not until
the branch condition has been evaluated, much later on in the pipeline.
If it guessed wrong, all the work it has done on later instructions is
wasted. It has to flush out its pipeline and start fetching the other
list of instructions. At that point, it has wasted dozens of instruction
execution opportunities.

To compensate for this, processors take heroic measures to try to
predict branches based on history, but are not always successful. The
easiest are branches that almost always go the same way, such as an
error detection branch or the return to the top of a loop with a high
iteration count. Branches that have no pattern to whether they are taken
or not taken, and go either way about equally often, are really expensive.

We are dealing with a short code snippet with three conditional
branches, including one that depends on a value fetched from an array.
They may all have a high correct prediction rate, in which case each
branch is of similar cost to e.g. an integer add, and small tweaks to
the integer arithmetic will make measurable differences in the code
performance. At the other extreme, the Arr1 test could be being
mispredicted so often that the only thing that matters for the loop
performance is doing it as infrequently as possible.

Only measurements can tell.

Patricia

 

[Daniel Pitts]

I have a below code I use a lot in my Java Program.

u1,i,j,u2,ux,mz are integer
Arr1 is char[]
BigARRAY is int[]

----------------------INITIAL CODE

u1=i+1;u2=j+1;
ux=u1*3+u2;
if ((u1<9)&&(u2<9)) {
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}
}
-----------------------

How can this code be made more efficient.

Here is one effort by me by putting ux=u1*3+u2; inside the if
(condition)

------------------- IMPROVED CODE
u1=i+1;u2=j+1;
if ((u1<9)&&(u2<9)) {
ux=u1*3+u2;
if (Arr1[ux]=='B') {mz++;BigARRAY[mz]=ux;}}

------------------

What else can be done to improve the above code. As this is being used
100000's times in For Loops. So If it's speed is improve twice then
program will work twice faster.

Is there any way to further improve the above code?

Bye
Sanny

In order to truly help you optimize, you should give us the complete
context within which this snippet is executed.

Also, you could probably make significant progress on your own if you
used a profiler to determine the exact bottlenecks of your
application.

Not to mention, you should determine how fast it *needs* to run.
Don't waste time trying to squeeze every last nanosecond out of it
unless you have a goal or requirement.