What a Java Novice Does

seed · by **seed** » Tue May 04, 2010 2:14 pm

This is what a Java novice does:

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

        static public float[] add(float[] v1, float[] v2) {
                float[] result = new float[3];
                
                result[0] = v1[0]+v2[0];
                result[1] = v1[1]+v2[1];
                result[2] = v1[2]+v2[2];
                
                return result;
        }
 
        static public float[] scale(float[] v1, float s)
        {
                float[] v = new float[3];
                
                v[0] = v1[0] * s;
                v[1] = v1[1] * s;
                v[2] = v1[2] * s;
                
                return v;
        }
 
        static public float[] normalize(float[] v1)
        {
                float length = length(v1);
                float[] v = new float[3];
                
                if (length != 0)
                {
                        v[0] = v1[0] / length;
                        v[1] = v1[1] / length;
                        v[2] = v1[2] / length;
                }
                
                return v;
        }
 
        static public float dot_product(float[] v, float[] w) {
                float result;
                
                result = v[0]*w[0]+v[1]*w[1]+v[2]*w[2];
                
                return result;
        }
        
        static public float[] reflect(float[] v1, float[] v2) {
                float l = length(v1);
                float dot;
                float[] result = new float[3];
                
                v1 = normalize(v1);
                v2 = normalize(v2);
                dot = 2*dot_product(inverse(v1),v2);
                v2 = scale(v2,dot);
                result = add(v1,v2);
                result = scale(result,l);
                
                return result;
        }
 
 
Parsed in 0.035 seconds,  using GeSHi 1.0.8.4

I am that novice, new to Java and smitten with the idea that you don't need to delete stuff. Funny, that as an embedded software engineer in real life, I am constantly worrying about deterministic memory allocation.

Anyway, do the above in enough places and your nice little opengl app that is running smoothly at 30+ frames a second experiences 80+ msec hickups every couple seconds when the GC runs.

The question is, what is the best way to re-write the above? Most of this is really straightforward to fix. Here are all the new functions except for reflect which is where my question lies.

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

        static public void add(float[] result, float[] v1, float[] v2) {
                result[0] = v1[0]+v2[0];
                result[1] = v1[1]+v2[1];
                result[2] = v1[2]+v2[2];
        }
        
        static public void scale(float[] result, float[] v1, float s)
        {
                result[0] = v1[0] * s;
                result[1] = v1[1] * s;
                result[2] = v1[2] * s;
        }
        
        static public void normalize(float[] v, float[] v1)
        {
                float length = length(v1);
                
                if (length != 0)
                {
                        v[0] = v1[0] / length;
                        v[1] = v1[1] / length;
                        v[2] = v1[2] / length;
                }
        }
 
        static public float dot_product(float[] v, float[] w) {
                float result;
                
                result = v[0]*w[0]+v[1]*w[1]+v[2]*w[2];
                
                return result;
        }
Parsed in 0.033 seconds,  using GeSHi 1.0.8.4

Now with reflect, I need some local objects to do my work. But I don't want to new them in the function and I wasn't sure how to handle it. Since this is part of a static class, I did the following:

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

                
        static float[] reflect_v1 = new float[3];
        static float[] reflect_v2 = new float[3];
        static float[] reflect_v3 = new float[3];
        static public void reflect(float[] result, float[] v1, float[] v2) {
                float l = length(v1);
                float ratio;
                float dot;
                
                normalize(reflect_v1,v1);
                normalize(reflect_v2,v2);
                dot = dot_product(inverse(reflect_v1),reflect_v2);
                scale(reflect_v2,reflect_v2,dot);
                add(reflect_v3,reflect_v1,reflect_v2);
                ratio = length(reflect_v1);
                scale(reflect_v3,reflect_v3,l*ratio);
                copy(result,reflect_v3);
        }
Parsed in 0.034 seconds,  using GeSHi 1.0.8.4

I think this is really efficient and doesn't cause any GC but maybe I am wrong. Also, doing this makes the function so that it is not re-entrant. This is not an issue for my app, but it makes the class a little less generally useful.

Is there a better way to handle needing local objects but not wanting to have them collected by the GC?

Note, you might have figured out that "inverse", which is not shown but only called, has not yet been rewritten. I am rewriting stuff one at a time to make sure I am not lost trying to figure out any bugs I create in the rewrite.

zorro · by **zorro** » Tue May 04, 2010 3:01 pm

You can make a class called let's say MathUtil and put there all your functions and local variables for 'inside work'. In your functions, make sure to not have any new variables, just use the class members. Then create one MathUtil object and use it across the entire application. That should be efficient.

seed · by **seed** » Tue May 04, 2010 4:18 pm

zorro wrote:You can make a class called let's say MathUtil and put there all your functions and local variables for 'inside work'. In your functions, make sure to not have any new variables, just use the class members. Then create one MathUtil object and use it across the entire application. That should be efficient.

Thanks for your input.

OK. Again, as a Java novice, is it just objects created in a function that cause GC, or does any variable in the function cause GC? For example, does this cause GC?

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

public float length(float[] v)
{
   float len;
 
   len = Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
 
   return len;
}
 
Parsed in 0.035 seconds,  using GeSHi 1.0.8.4

... or do I need to write it like this?

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

float length_len;
public float length(float[] v)
{
   length_len= Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
 
   return length_len;
}
Parsed in 0.036 seconds,  using GeSHi 1.0.8.4

Also, regarding having one instance of my class that I use across the entire application, I am not sure how this is much different than just having a static class. For example, my class with the length function above is really like this.

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

static public class vector3d 
{
   static float length_len;
   public float length(float[] v)
   {
      length_len= Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
 
      return length_len;
   }
}
 
Parsed in 0.036 seconds,  using GeSHi 1.0.8.4

... and I call it like this

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

len = vector3d.length(vector);
Parsed in 0.035 seconds,  using GeSHi 1.0.8.4

Your suggestion works well if I have multiple threads that each are calling the methods because I can have an object for each thread eliminating re-entrance issues with members, but it makes me need to have access to the object from everywhere in my code, which I think drives me to a singleton, which brings back the re-entrance issues, which is why I am just thinking a static class.

Thoughts?

.

MichaelEGR · by **MichaelEGR** » Tue May 04, 2010 4:42 pm

You gave an example.. In this case you don't need the local variable.. Your's 1st.. 2nd how it should be

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

 
public float length(float[] v)
 
{
 
   float len;
 
   len = Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
 
   return len;
 
} 
 
Parsed in 0.036 seconds,  using GeSHi 1.0.8.4

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

 
public float length(float[] v)
 
{
 
   return (float)Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
 
} 
 
Parsed in 0.036 seconds,  using GeSHi 1.0.8.4

For methods like inverse, project, and reflect you can A) use a static local temporary vector object or B) unroll things. Here is my Vecmath.project() method. A as you know is not reentrant

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

 
   public static Tuple3f project(Tuple3f planePos, Vector3f planeNormal, Tuple3f posIn, Tuple3f posOut)
 
   {
 
      // projectVec.sub(posIn, planePos)
 
      float x = posIn.x - planePos.x;
 
      float y = posIn.y - planePos.y;
 
      float z = posIn.z - planePos.z;
 
      // projectVec.dot(planeNormal)
 
      float distance = x * planeNormal.x + y * planeNormal.y + z * planeNormal.z;
 
      // posOut.scaleAdd(-distanceD, planeNormal, posIn)
 
      posOut.x = -distance * planeNormal.x + posIn.x;
 
      posOut.y = -distance * planeNormal.y + posIn.y;
 
      posOut.z = -distance * planeNormal.z + posIn.z;
 
      return posOut;
 
   }
 
Parsed in 0.038 seconds,  using GeSHi 1.0.8.4

For more wide spread usage of local variables you can take a look at JStackAlloc and I do believe there is also object recycling functionality in Javolution.

seed · by **seed** » Tue May 04, 2010 7:25 pm

MichaelEGR wrote:You gave an example.. In this case you don't need the local variable.. Your's 1st.. 2nd how it should be...

Point taken

MichaelEGR wrote:For methods like inverse, project, and reflect you can A) use a static local temporary vector object or B) unroll things. Here is my Vecmath.project() method. A as you know is not reentrant

Wow, unroll things is a nightmare. But, it will definitely work. Obviously because you have done it. I hate (A) because it is not reentrant.

How about option (C), add a simple stack.

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

public class Vector 
{
        public x,y,z;
        
        // Static stack stuff
        private static final STACK_SIZE = 100;
        private static Vector[] stack;
        private static boolean initialized = false;
        private static int stack_index = 0;
        
        // Stack allocation and freeing
        public static Vector alloc()
        {
                if (!initialized)
                        init();
                
                return stack[stack_index++];
        }       
        
        public static void free()
        {
                if (!initialized)
                        init();
                
                if (stack_index > 0)
                        stack_index--;
        }
        
        private void init()
        {
                stack = new Vector[STACK_SIZE];
                for (int i=0; i<STACK_SIZE; i++)
                {
                        stack[i] = new Vector();
                }
                initialized = true;
        }
        
        // Constructor
        public Vector()
        {
                x = 0;
                y = 0;
                z = 0;
        }
        
        // Static math methods for manipulating Vectors
        static public void add(Vector v1, Vector v2, Vector v3) 
        {
                v1.x = v2.x + v3.x;
                v1.y = v2.y + v3.y;
                v1.z = v2.z + v3.z;
        }
        
        static public void copy(Vector v1, Vector v2) 
        {
                v1.x = v2.x;
                v1.y = v2.y;
                v1.z = v2.z;
        }
        
        static public void reflect(Vector result, Vector dir, Vector normal) 
        {
                float len;
                float ratio;
                float dot;
                
                Vector v1 = alloc();
                Vector v2 = alloc();
                Vector v3 = alloc();
                
                len = length(dir);
                normalize(v1,dir);
                normalize(v2,normal);
                inverse(v3,v1);
                dot = dot_product(v3,v2);
                scale(v2,v2,dot);
                add(result,v1,v2);
                ratio = length(v1);
                scale(result,result,len*ratio);
                
                free();
                free();
                free();
                
                return result;
        }
 
        static public float length(Vector v1)
        {
                return = Math.sqrt(v1.x*v1.x + v1.y*v1.y + v1.z*v1.z);
        }
        
        static public void normalize(Vector result, Vector v1)
        {
                float len = length(v1);
                if (length != 0)
                {
                        result.x = v1.x / len;
                        result.y = v1.y / len;
                        result.z = v1.z / len;
                }
        }
        
        // Written with temp vector in order to work when result is also one of  
        // other two parameters
        static public void cross_product(Vector result, Vector v1, Vector v2) 
        {
                Vector temp = alloc();
                
                temp.x = v1.y * v2.z - v1.z * v2.y;
                temp.y = v1.z * v2.x - v1.x * v2.z;
                temp.z = v1.x * v2.y - v1.y * v2.x;
                result.copy(temp);
                
                free();
                
                return result;
        }
        
        static public float dot_product(Vector v, Vector w) 
        {
                return( v.x * w.x + v.y * w.y + v.z * w.z);
        }
        
}
 
Parsed in 0.045 seconds,  using GeSHi 1.0.8.4

Edit - not sure why I had two classes. One Vector class is fine. I suck at Java.

Or model after something like the following which does the same thing but with a new stack per thread.

http://code.google.com/p/jmonkeyengine/ ... pVars.java

seed · by **seed** » Wed May 05, 2010 2:18 pm

The code above was written in a text editor and is riddled with bugs. But, I implemented this last night and it worked well. I still need to turn a lot of my variables into Vector's that were previously float[3] but for the ones I have converted already, the new class is working great. Nested calls work fine with stack allocated temp Vectors. I will post the good code at some point.

My next step is to do the same thing with my 3 and 4 dimensional matrixes and my quarternions. In the end, I think I will get rid of a bunch of GC.

Thanks for talking and getting me thinking.

MichaelEGR · by **MichaelEGR** » Fri May 07, 2010 1:51 am

For a utility class with static vector math methods I think it's best to do the unrolling approach as this code is going to be called a lot. It doesn't matter if it's ugly as long as there are no bugs and such; that is why I leave comments with the actual vector object methods that would be called instead of the unrolled code. The fewer internal method calls to a given vector math method the better. Think of the method overhead for billboarding and such when using an inverse matrix method which can be called each time a billboard is rendered.

IE get stack allocated vectors, set the vector values, then call methods on the stack allocated vectors then calling the free methods. Look at your reflect method as it has 14 method calls. This will slow down your code.

Obviously I don't recommend unrolling for everything as OO is nice, but in this case it's pertinent for high throughput.

---

Technically the stack you created is simple and works, but is not thread safe as the pool is shared between X threads.

You can look into ThreadLocal:
http://java.sun.com/javase/6/docs/api/j ... Local.html
And perhaps create and access your stack that way such that each thread will have its own object stack.

---

For wide spread local object usage JStackAlloc is a better option than your home rolled solution.
http://www.javagaming.org/index.php/topic,18843.0.html

There are other options too like I mentioned I'm sure there is a pool solution in Javolution. There are likely others as well.

---

One last general comment you may want to use a javax.vecmath implementation as rolling your own Vector and Matrix classes will make your code incompatible to a bunch of other math related Java code. While various Java 3D engines for instance started with their own implementations (Java Monkey Engine / JME) is an example if you want to interface with 3rd party code you'll have to create a bridge to marshal data from your vector format to likely javax.vecmath (most widely used vecmath API/library).

Here is a link to an independent version; yes created a long time ago!
http://www.objectclub.jp/download/vecmath_e

I actually have a modified the version above over the years and will likely release mine MIT licensed when I release TyphonRT.

seed · by **seed** » Fri May 07, 2010 1:25 pm

I agree with EVERYTHING you said above. But, for me right now, there is some definite time management issues. I am not having any performance issues with this code other than the GC stuff, so I don't think I need to spend my resources on any of the very wise optimizations that you suggest. I am not designing a general game engine like you are, but a specific one for a specific application. So I need to optimize only to how it effects the overall performance my app.

But, for those browsing this post, Michael is right and I am wrong. Listen to him, not me.

I am currently working a full time job, I am in the middle of getting lawyered up for a copywrite related law suit with a huge game manufacturer, I have three kids and a wife to consider, and I am trying to put in three or four hours every night learning this stuff.

I am really excited because I strongly believe that I have a great game on my hands. Even the early alpha build kicks ass. But I need to get it done so how I spend my time is really important. Tradeoffs.

Needless to say, I am really tired:) Your feedback on a lot of my questions has been really helpful. I appreciate it.

Thanks,
Seed

seed · by **seed** » Fri May 07, 2010 2:23 pm

For those reading, this is the current implementation of my 3d vector class.

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

public class Vector3
 
{
 
    public float x,y,z; 
 
    // Static stack stuff 
 
    private static int STACK_SIZE = 100; 
 
    private static Vector3[] stack; 
 
    private static boolean initialized = false; 
 
    private static int stack_index = 0; 
 
    // Stack allocation and freeing 
 
    public static Vector3 alloc() 
 
    { 
 
         if (!initialized) 
 
              init(); 
 
         return stack[stack_index++]; 
 
    }    
 
    public static void free() 
 
    { 
 
         if (!initialized) 
 
              init(); 
 
         if (stack_index > 0) 
 
              stack_index--; 
 
    } 
 
    private static void init() 
 
    { 
 
         stack = new Vector3[STACK_SIZE]; 
 
         for (int i=0; i<STACK_SIZE; i++) 
 
         { 
 
              stack[i] = new Vector3(); 
 
         } 
 
         initialized = true; 
 
    } 
 
    // Constructor 
 
    public Vector3() 
 
    { 
 
         x = 0; 
 
         y = 0; 
 
         z = 0; 
 
    } 
 
    public Vector3(float xin, float yin, float zin)
 
    {
 
        x=xin; y=yin; z=zin;
 
    }
 
    // Static math methods for manipulating Vectors 
 
    static public void add(Vector3 v1, Vector3 v2, Vector3 v3) 
 
    { 
 
         v1.x = v2.x + v3.x; 
 
         v1.y = v2.y + v3.y; 
 
         v1.z = v2.z + v3.z; 
 
    } 
 
    static public void subtract(Vector3 v1, Vector3 v2, Vector3 v3) 
 
    { 
 
         v1.x = v2.x - v3.x; 
 
         v1.y = v2.y - v3.y; 
 
         v1.z = v2.z - v3.z; 
 
    } 
 
    static public void copy(Vector3 v1, Vector3 v2) 
 
    { 
 
         v1.x = v2.x; 
 
         v1.y = v2.y; 
 
         v1.z = v2.z; 
 
    } 
 
    static public float[] to_float(Vector3 v)
 
    {
 
        float[] result = new float[3];
 
        result[0] = v.x;
 
        result[1] = v.y;
 
        result[2] = v.z;
 
        return result;
 
    }
 
    static public Vector3 to_Vector3(float[] f)
 
    {
 
        Vector3 result = new Vector3(f[0],f[1],f[2]);
 
        return result;
 
    }
 
    static public void reflect(Vector3 result, Vector3 dir, Vector3 normal, float damp) 
 
    { 
 
         float len; 
 
         float ratio; 
 
         float dot; 
 
         Vector3 v1 = alloc(); 
 
         Vector3 v2 = alloc(); 
 
         Vector3 v3 = alloc(); 
 
         len = length(dir); 
 
         normalize(v1,dir); 
 
         normalize(v2,normal); 
 
         inverse(v3,v1); 
 
         dot = (1+damp)*dot_product(v3,v2); 
 
         scale(v2,v2,dot); 
 
         add(result,v1,v2); 
 
         ratio = length(v1); 
 
         scale(result,result,len*ratio); 
 
         free(); 
 
         free(); 
 
         free(); 
 
    } 
 
    static public void inverse(Vector3 v1, Vector3 v2) 
 
    { 
 
         v1.x = -v2.x; 
 
         v1.y = -v2.y; 
 
         v1.z = -v2.z; 
 
    } 
 
    static public void scale(Vector3 v1, Vector3 v2, float s)
 
    {
 
        v1.x = v2.x * s;
 
        v1.y = v2.y * s;
 
        v1.z = v2.z * s;
 
    }
 
    static public float length(Vector3 v1) 
 
    { 
 
         return (float) Math.sqrt(v1.x * v1.x + v1.y * v1.y + v1.z * v1.z); 
 
    } 
 
    static public void normalize(Vector3 result, Vector3 v1) 
 
    { 
 
         float len = length(v1); 
 
         if (len != 0) 
 
         { 
 
              result.x = v1.x / len; 
 
              result.y = v1.y / len; 
 
              result.z = v1.z / len; 
 
         } 
 
    } 
 
    // Written with temp vector in order to work when result is also one of   
 
    // other two parameters 
 
    static public void cross_product(Vector3 result, Vector3 v1, Vector3 v2) 
 
    { 
 
         Vector3 temp = alloc(); 
 
         temp.x = v1.y * v2.z - v1.z * v2.y; 
 
         temp.y = v1.z * v2.x - v1.x * v2.z; 
 
         temp.z = v1.x * v2.y - v1.y * v2.x; 
 
         copy(result,temp); 
 
         free(); 
 
    } 
 
    static public float dot_product(Vector3 v, Vector3 w) 
 
    { 
 
         return( v.x * w.x + v.y * w.y + v.z * w.z); 
 
    } 
 
}
Parsed in 0.053 seconds,  using GeSHi 1.0.8.4

...and here is some sample code that uses it. Note that I am using the to_float and to_Vector3 functions because I haven't yet converted all of my variables to Vector3's. This allows me to change a little at a time and make sure it still works.

Syntax: [ Download ] [ Hide ]

Using java Syntax Highlighting

 
    // Called once a frame for movement for this object.
 
    public void move()
 
        {
 
                vector3d.insertionResult result;
 
                float l,tl;  // Length variables
 
                float[] adjust = LavaBall.getSense();
 
                Vector3 mvel = Vector3.alloc();
 
                Vector3 mpos = Vector3.alloc();
 
                Vector3 temp = Vector3.alloc();
 
                // copy position and velocity to local variables.
 
                // FIXME - change to time based rather than frame based movement.
 
                Vector3.copy(mpos,position);
 
                Vector3.copy(mvel,velocity);
 
                // Save the length of the velocity.  We use later to restore the velocity.
 
                l = Vector3.length(velocity);
 
                // Determine if any collisions by testing against the bsp.  Bsp will return a ratio
 
                // of your movement distance for when the first insertion into the world surfaces takes
 
                // place.
 
                // If there is an intersection, then reflect the move and move the remaining distance.
 
                result = World.bsp.testInsertion(Vector3.to_float(mpos), Vector3.to_float(mvel), radius,null, sequence_number++);
 
                while(result.intersection)
 
                {
 
                        // Shorten the movement vector by the ratio of the distance traveled.
 
                        Vector3.scale(temp, mvel, result.dist);
 
                        Vector3.add(mpos,mpos,temp);
 
                        // Subtract it from the overall movement vector.  This is the movement
 
                        // left to be made this frame.
 
                        Vector3.subtract(mvel,mvel,temp);
 
                        // Reflect the velocity based on the normal of collision.  Reflection is not
 
                        // perfectly elastic.  The constant at the end slows the outgoing velocity.
 
                        // Since we are only operating on the local velocity vector, we need to find
 
                        // the ratio of that velocity reduction and apply it to the l variable that will
 
                        // be used later to restore the member velocity variable.
 
                        tl = Vector3.length(mvel);
 
                        Vector3.reflect(mvel,mvel,Vector3.to_Vector3(result.normal),0.3f);
 
                        l = l * (Vector3.length(mvel)/tl);
 
                        // Test for another insertion on the next bit of our movement.
 
                        result = World.bsp.testInsertion(Vector3.to_float(mpos), Vector3.to_float(mvel), radius,null, sequence_number++);
 
                }
 
                // Add in the last bit of non-colliding movement
 
                Vector3.add(mpos,mpos,mvel);
 
                // Restore velocity
 
                Vector3.normalize(mvel,mvel);
 
                Vector3.scale(velocity, mvel, l);
 
                // Restore position
 
                Vector3.copy(position,mpos);            
 
                // New acceleration based on sensor orientation
 
                // Start with the normalized orientation acceleration.  
 
                acceleration.x=adjust[0];
 
                acceleration.y=adjust[1];
 
                acceleration.z=adjust[2];
 
                // Scale it to something that makes sense for this world.
 
                Vector3.normalize(acceleration,acceleration);
 
                Vector3.scale(acceleration,acceleration, 0.004f);
 
                // Update the velocity with the acceleration
 
                Vector3.add(velocity,velocity,acceleration);
 
                Vector3.free();  // temp
 
                Vector3.free();  // mpos
 
                Vector3.free();  // mvel
 
        }
Parsed in 0.044 seconds,  using GeSHi 1.0.8.4

seed · by **seed** » Tue May 18, 2010 7:54 pm

I finally finished all of my removing bad java coder stuff. My application now runs with zero real-time GC and it is running blazingly fast! Woop! Thanks for all the help and suggestions.

torpor · by **torpor** » Sat May 22, 2010 11:37 pm

This looks really nice .. I'm learning a lot from this!

What a Java Novice Does

What a Java Novice Does

Re: What a Java Novice Does

Re: What a Java Novice Does

Who is online