2
\$\begingroup\$

For my Voxel like game I need to generate terrain meshes from an array of ids. Because of that I have no idea how big the final vertex array will be.

Currently I'm doing like this: generate mesh and save to arrayList, then in a few lines of code I convert the arrayList to a primitive array. This is working fine, but it's just really SLOW.

So now my question is is there a way I can use a primitive array, without knowing it's final size? If not is there a fast way I can take an array with a lot of empty elements, and then shrink it?

Edit: Heres how I convert it:

List <Float> vertices = new ArrayList <Float> ();

//Generating mesh

float[] doneVertices = new float[vertices.size()];
for(int i = 0; i < vertices.size(); i++) doneVertices[i] = vertices.get(i);
\$\endgroup\$
  • 1
    \$\begingroup\$ Make sure you are using this line of code to convert your ArrayList to an array: myArray = arrayList.toArray(new Type[0]); \$\endgroup\$ – Alexandre Desbiens Jun 10 '15 at 19:20
2
\$\begingroup\$

To get decent performance, you should define your own private class FloatArray which contains a float[] values; (lowercase f !) and an integer count which keeps track of the "logical" size. When there are no elements, set values to a new array of 16 items and count to zero.

Then when you need to add elements, check whether count is greater than or equal to the current length of the array. If so, create a new array which is twice as big, copy all the existing elements to it, and replace values with a reference to the new array. Once values.length is greater than count, store the array element and increment count.

Note that values may end up being up to twice as big as the largest number of elements that are actually needed, but that's generally not likely to be a problem. Further, on average no array element is going to end up getting copied more than twice. If one were to grow the array by a smaller amount each time, one would need to create more arrays and copy elements more times; the cost of doing that could likely exceed the cost of allocating a larger array than needed.

In any case, avoid using type Float (uppercase F) whenever possible, since converting a float to a Float is rather expensive. Using your own private type that stores values of float in a float[] will be much more efficient.

\$\endgroup\$
  • \$\begingroup\$ Won't ArrayList in Java take care of this resizing for you? \$\endgroup\$ – Evorlor Jun 11 '15 at 2:43
  • 2
    \$\begingroup\$ @Evorlor but ArrayList can't work with the primitive float array, so duplicating the ArrayList functionality tends to be the only option other than boxing (which has issues). \$\endgroup\$ – ratchet freak Jun 11 '15 at 9:03
  • 2
    \$\begingroup\$ @Evorlor: ArrayList will take care of the sizing for you, but it requires using Float rather than float, which imposes a major performance cost. If v and i are local variables and arr is a field of this, arr[i]=v; will often require 2-4 machine instructions. Converting a float to a Float will require dozens if not hundreds. Using an ArrayList<Float> may be okay when performance isn't an issue (if code would spend 1% of its time adding stuff to an array list, reducing that to 0.1% of its time would be meaningless) but this is not one of those times. \$\endgroup\$ – supercat Jun 11 '15 at 13:55
1
\$\begingroup\$

You cannot use a standard array without knowing its size. You must use an ArrayList. But that is not where your lag is coming from. You have an issue with your algorithm. If you share your code, we can help you beat it into submission.

I suggest just starting and finishing with an ArrayList. If you are creating a new ArrayList and adding the objects one at a time every frame, that could explain it.

UPDATE:

Change your code to:

List <Float> vertices = new ArrayList <Float> ();

//Generating mesh

Float[] doneVertices = vertices.toArray(new Float[0]); // Notice the capitalized Float.

But I doubt this is going to fix everything. You should check for other areas you can improve performance as well.

\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for beating code up to submission. Seriously though, this is the right answer. Converting a ArrayList<T> to a t[] should not take time, because an ArrayList stocks a primitive array for its values. \$\endgroup\$ – Alexandre Desbiens Jun 10 '15 at 19:16
  • \$\begingroup\$ I added the code \$\endgroup\$ – KaareZ Jun 10 '15 at 19:25
  • \$\begingroup\$ Even if this update does not fix everything, it answers the question well enough. \$\endgroup\$ – Alexandre Desbiens Jun 10 '15 at 19:29
  • 1
    \$\begingroup\$ I forgot the capital F for Float on my edit, will edit again. That said, this should be an easy error to see and fix yourself. \$\endgroup\$ – Alexandre Desbiens Jun 10 '15 at 19:44
  • 1
    \$\begingroup\$ @Evorlor Well what do you know, you can use toArray with a primitive type but you can't stock them into a List. Java is beautiful, isn't it? \$\endgroup\$ – Alexandre Desbiens Jun 10 '15 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.