#114 n-dimensional array optimization

[Fabio Insaccanebbia]

I've got an idea for a couple of new rules reading this
article:

http://forums.java.net/jive/thread.jspa?threadID=2151&tstart=0

"cowwoc" said that the compiler is not capable of
extracting inner variable from loops. I've tried a
couple of microbenchmark and it seems he's right.

So here the 2 rules:
1 - ExtractArrayFromSingleLoop
2 - ExtractArrayFromNestedForLoop

<rule name="ExtractArrayFromSingleLoop" message="Save the subarray in a temporary variable to minimize memory access" class="net.sourceforge.pmd.rules.XPathRule">
<description>
Save the subarray in a temporary variable to minimize
memory access
</description>
<properties>
<property name="xpath">
<value>
//Statement[ForStatement or
WhileStatement]//PrimaryExpression[./PrimaryPrefix/Name
and
./PrimarySuffix[1]/Expression/PrimaryExpression/PrimaryPrefix/Literal
and
./PrimarySuffix/Expression/PrimaryExpression/PrimaryPrefix/Name]
</value>
</property>
</properties>
<priority>3</priority>
<example>
<![CDATA
class Test {
void method() {
int myArray[[];
int sum = 0;
for (int i=0; i<100000; ++i)
{
sum += myArray[0][ i ]; //this will trigger the rule
}
}

void method2() {
int myArray[][];
int sum = 0;
int[] myArr=myArray[0];
for (int i=0; i<100000; ++i)
{
sum += myArr[ i ]; //this won't trigger the rule
}
}

}
]]>
</example>
</rule>

<rule name="ExtractArrayFromNestedForLoop" message="Save the subarray in a temporary variable to minimize memory access" class="net.sourceforge.pmd.rules.XPathRule">
<description>
Save the subarray in a temporary variable to minimize
memory access
</description>
<properties>
<property name="xpath">
<value>
<![CDATA
//PrimaryExpression[
./PrimaryPrefix/Name
and
./PrimarySuffix[1[@ArrayDereference='true']/Expression/PrimaryExpression/PrimaryPrefix/Name
[@Image =
ancestor::ForStatement[count(./ForStatement)<2]/ForInit//VariableDeclaratorId/@Image]
and
./PrimarySuffix[2][@ArrayDereference='true']/Expression/PrimaryExpression/PrimaryPrefix/Name
[@Image =
ancestor::ForStatement[count(./ForStatement)<2]/ForInit//VariableDeclaratorId/@Image]]
]]>
</value>
</property>
</properties>
<priority>3</priority>
<example>

public class TestNested {

int myArray[][];

public static final int TOT=1000;

public TestNested() {
super();
myArray=new int[TOT][TOT];
for (int i=0; i<TOT; i++)
{
for (int j=0; j<TOT; j++)
{
myArray[i][j]=i; //this will trigger the rule
}
}
}

void method() {
int sum = 0;
for (int i=0; i<TOT; i++)
{
for (int j=0; j<TOT; j++)
{
myArray[i][j]=i; //this will trigger the rule
}
}
}

void method2() {
int sum = 0;
for (int i=0; i<TOT; i++)="" {="" int[]="" myArr="myArray&lt;span">[i]; for (int j=0; j<TOT; j++)="" {="" myArr<span="">[j]=i; //this won't trigger the rule } }
}
} </example>
</rule>

[Fabio Insaccanebbia]

Logged In: YES
user_id=762447

The "ExtractArrayFromNestedForLoop" could be improved in
this way (it avoids "false positive" when the two array
indexes are in the wrong order).

//PrimaryExpression
./PrimaryPrefix/Name
and
./PrimarySuffix[1
[@ArrayDereference='true']/Expression/PrimaryExpression/Prim
aryPrefix/Name
[@Image =
ancestor::ForStatement/../ancestor::ForStatement/ForInit//Va
riableDeclaratorId/@Image]
and
./PrimarySuffix[2]
[@ArrayDereference='true']/Expression/PrimaryExpression/Prim
aryPrefix/Name
[@Image = ancestor::ForStatement[count(./ForStatement)
=0]/ForInit//VariableDeclaratorId/@Image]
]

[Tom Copeland]

Logged In: YES
user_id=5159

Hm, that's very interesting - so it doesn't do code
hoisting, eh? Cool, yup, something else for the
optimizations ruleset then.

Moving this to Patches, thanks much!

Yours,

Tom

[Romain PELISSE]

@Andreas: This patch has been lingering for a while, but it seems still somewhat applicable/relevant. Would mind take a look at it ? If you feel, like me, that it still make sense, we'll add it. Thanks !