CODEWITHSUNDEEP
javaperformanceoptimization
Emerson Mitchell
Emerson Mitchell

Reputation: 1

More efficient way to check if a value is included in an array?

Writing a game that does lots of comparisons, and it's lagging. I'm trying to speed it up, and this particular chunk of code is run thousands of times every frame, for different values of x y and z. Is there a better way to check if the values of x y and z are valid in the array? (java)

if (x >= 0 && x < blocksArr.length && y >= 0 && y < blocksArr[x].length && z >= 0 && z < blocksArr[x][y].length && blocksArr[x][y][z])

I've tried checking if blocksArr[x][y][z] != null and checking if blocksArr[x][y][z] != undefined but neither give results.

Upvotes: 0

Views: 265

Answers (4)

Qu&#226;n Anh Mai
Qu&#226;n Anh Mai

Reputation: 630

In general, the most efficient way of doing t >= 0 && t < u with u known to be positive is to compare the unsigned value of t and u using Integer.compareUnsigned(t, u) < 0. As a result, your if can be more efficiently expressed as

if (Integer.compareUnsigned(x, blocksArr.length) < 0 &&
    Integer.compareUnsigned(y, blocksArr[x].length) < 0 &&
    Integer.compareUnsigned(z, blocksArr[x][y].length) < 0 &&
    blocksArr[x][y][z])

However, I think your representation of blocksArr as a 3-dimensional array is really inefficient and results in a lot of indirections, which greatly hinders the potential performance. A more logical approach is to represent it as a single array and have length, width, height being stored separately. This would result in your code looks something like this:

if (Integer.compareUnsigned(x, length) < 0 &&
    Integer.compareUnsigned(y, width) < 0 &&
    Integer.compareUnsigned(z, height) < 0 &&
    blocksArr[x * (width * height) + y * height + z])

This however limits your block to around 2 billion elements, to overcome this limitation, you need to resort to the Memory Access API, which is currently in preview. It has an important advantage that it allows the allocation and deallocation of memory blocks to be deterministic, which is much more desirable for too large memory pieces. Using a memory segment to represent the blocksArr, your code would become:

if (Long.compareUnsigned(x, length) < 0 &&
    Long.compareUnsigned(y, width) < 0 &&
    Long.compareUnsigned(z, height) < 0 &&
    blocksArr.get(ValueLayout.JAVA_BOOLEAN, x * (width * height) + y * height + z))

Moreover, since blocksArr is a block of boolean values, packing them so that each element occupies only 1 bit will improve the memory consumption and cache pressure greatly. The check now can be expressed as:

long index = x * (width * height) + y * height + z;
long byteIndex = index >>> 3;
int shift = (int)(index & 7);
if (Long.compareUnsigned(x, length) < 0 &&
    Long.compareUnsigned(y, width) < 0 &&
    Long.compareUnsigned(z, height) < 0 &&
    blocksArr.get(ValueLayout.JAVA_BYTE, byteIndex) & (1 << shift) != 0)

Upvotes: 1

Big Guy
Big Guy

Reputation: 334

You have a box determined by three dimensions, x, y, and z.

If any of those indices are outside the boundaries of the box, then the entire if() statement is false. So there is no need to walk through things like blocksArr[x].length

Also, think about what is actually going on under the hood. The variable x is in fact a pointer to a location in memory which holds the value. To process a statement like x >= 0, the computer must locate the memory location for x, fetch that value and put it into one of its internal registers, say register A. It then takes that value 0 and puts it into register B. It compares Register A to register B. if A > B, then it goes on to the next operation, otherwise it compares A to B again. If the comparison is zero, then it goes to the next operation, otherwise it move the operation pointer past the if() statement.

For comparing x < blocksArr.length, it again fetches x, then fetches blocksArr calculates the offset to the length value, then fetches that into the register, where it does the comparison.

You can shorten all of this by using some static constants.

Consider that x >= 0 can be re-written as x > -1. This can potentially reduce 2 comparisons to 1, so a few CPU cycles saved.

An array construct is an immutable object, that is it cannot be changed after being created. So an array's length will never be different. So if you created an array with size 5, blocksArr.length will always return 5. in the comparison x < blocksArr.length you could substitute x < 5, which means the CPU does not need to fetch blocksArr.length, which saves CPU cycles.

So you could re-write the array creation, and your if statement to:

public static final int MAX_X = 10;
public static final int MAX_Y = 15;
public static final int MAX_Z = 20;

public boolean blocksArr[][][] = new boolean[MAX_X][MAX_Y][MAX_Z];
  
.
.
.

  if ( ( x > -1 && x < MAX_X ) && // validate for X dimension
       ( y > -1 && y < MAX_Y ) && // validate for Y dimension
       ( z > -1 && z < MAX_Z ) && // validate for Z dimension
       blocksArr[x][y][z] )       // check value

I think this is the least CPU intensive way of doing this.

Upvotes: 0

Big Guy
Big Guy

Reputation: 334

What you are doing is a bounds check, to make sure that the indexes x, y, and z are valid indices in the blocksArr[][][] array. In C, this is necessary as C allows you to go outside the array.

Java, however, does a bounds check every time you access the array. So you are doing a manual bounds check, then another check, plus Java is doing a check on two dimensions, and finally Java does another check on three dimensions.

All you really need to do is access the array, let Java do the bounds check, and catch an exception if any of the indices are out of bounds.

    boolean value;

    try
    {
        value = blocksArr[x][y][z];
    }
    catch (ArrayIndexOutOfBoundsException e )
    {
        value = false;
    }

There is some overhead in setting up a try/catch block, but overall it should be faster.

Upvotes: -1

Simon Goater
Simon Goater

Reputation: 1908

I don't know java but in general, I would expect the following to be at least as fast, possibly faster. Your compiler may do something like this anyway so it might not be faster. You can split the 'If' statement up so that it will do fewer lookups. Sorry, but I'll have to write it as c code. You can get the idea and translate to java.

if (x >= 0 && y >= 0 && z >= 0 && x < blocksArr.length) {
  if (y < blocksArr[x].length && z < blocksArr[x][y].length && blocksArr[x][y][z]) {
    .....
  }
}

Assuming user16320675 is correct about the evaluation order, you could use one 'if' statement. I don't know how the java compiler works.

if (x >= 0 && y >= 0 && z >= 0 && x < blocksArr.length && y < blocksArr[x].length && z < blocksArr[x][y].length && blocksArr[x][y][z]) .....

Upvotes: 0

Related Questions