Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (121)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  [JOODE] Contribution  (Read 5540 times)
0 Members and 1 Guest are viewing this topic.
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Posted 2007-01-23 08:20:54 »

Since everybody seems to be adding little additions to JOODE, here's mine:

1  
2  
3  
4  
5  
6  
7  
8  
public static final float inverseSqrt( float value ) {
      float xhalf = 0.5f * value;
      int i = Float.floatToIntBits( value );
      i = 0x5f375a86 - (i >> 1);
      value = Float.intBitsToFloat( i );
      value = value * ( 1.5f - xhalf * value * value );
      return value;
   }


That code as you probably know is from the Quake3 src code, however, my implementation has a different initial guess which is slightly more accurate over only 1 loop. Use this instead of the 1/Math.sqrt(...); in Real.normalize(), Vector3.normalize();

Edit, forgot to say, this only works on x86.

Enjoy Smiley

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline Amos Wenger

Senior Duke




Everything's possible, but not everything's fun...


« Reply #1 - Posted 2007-01-23 20:15:28 »

What's the advantage ? I guess it's faster, right ?

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #2 - Posted 2007-01-23 21:51:57 »

Yup, faster by a long way.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #3 - Posted 2007-01-24 03:55:16 »

Edit, forgot to say, this only works on x86.

What is platform specific about it?  The docs for Float don't mention anything platform specific about the bit representations.  It's all IEEE 754.

Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #4 - Posted 2007-01-26 10:44:01 »

Im not sure to be honest, i'll try running it on a 64bits machine and see what the outcome is. Hopefully its the same.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline t_larkworthy

Senior Duke


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #5 - Posted 2007-01-30 13:37:50 »

Yeah I am not so sure about those sytle of optimizations. Although great for gaming purposes, it does somewhat undermine any sense of fidelity. Maybe it could be used as an option

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #6 - Posted 2007-01-30 13:41:05 »

Works on x64 swpalmer.

You could have a FastMath class and put optimisations such as this in there (along side sin/cos look up tables).

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #7 - Posted 2007-01-30 15:47:57 »

This code is in Real, but I left it commented out because it's no longer as fast to do it in integer as in floating point instructions. Esp. for Java, it's probably slower.

@t_larkworthy: I sent you a PM a while back! Check you PMs! Wink
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #8 - Posted 2007-01-30 17:06:38 »

Quote
commented out because it's no longer as fast to do it in integer as in floating point instructions. Esp. for Java, it's probably slower.

Not according to my benchmarks. 1f/Math.sqrt(...); is multiple times slower than invSqrt. It has also resulted in a substantial FPS increase with CPU based skeletal character animation.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #9 - Posted 2007-01-30 17:13:38 »

Results:

Quote
Math.sqrt: 17.3895012
invsqrt: 9.667625

1/Math.sqrt(...); is nearly twice as slow as invSqrt. Thats definetly not something to be laughed at since sqrt is one of the more expensive math operations on the CPU (along with trig).

Benchmark:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
public class TestInvSqrt {

   public static void main( String args[] ) {
      // warm up loops
      int loops = 10000000;
      for ( int i = 0; i < loops; i++ ) {
         float v1 = 1 / (float)Math.sqrt( i );
         float v2 = invSqrt( i );

         float v3 = v2 * v1;
      }

      // do the proper loops now
      long nano = System.nanoTime();
      for ( int i = 0; i < loops; i++ ) {
         float v1 = 1f / (float)Math.sqrt( i );
         // to prevent dead code removal
         v1 *= 2;
      }
      long after = System.nanoTime();
      System.out.println( "Math.sqrt: " + (double)( after - nano ) / (double)loops );

      nano = System.nanoTime();
      for ( int i = 0; i < loops; i++ ) {
         float v2 = invSqrt( i );
         // to prevent dead code removal;
         v2 *= 2;
      }
      after = System.nanoTime();
      System.out.println( "invsqrt: " + (double)( after - nano ) / (double)loops );
   }

   private static float invSqrt( float value ) {
      float xhalf = 0.5f * value;
      int i = Float.floatToIntBits( value );
      i = 0x5f3759df - ( i >> 1 );
      // i = 0x5f375a86 - ( i >> 1 );
      value = Float.intBitsToFloat( i );
      value = value * ( 1.5f - xhalf * value * value );
      return value;
   }

}


Edit: Clarified benchmark

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #10 - Posted 2007-01-30 17:50:38 »

Ok, it checks out for pure speed. But two hurdles remain:

1. Correctness of computed values
2. Portability to other platforms (and correctness there too)

Also, if it is decided that JOODE should use javax.vecmath throughout, we would rely on the vecmath implementation for vector length (Math.sqrt()):

https://vecmath.dev.java.net/source/browse/vecmath/src/javax/vecmath/Vector3f.java?rev=1.3&view=auto&content-type=text/vnd.viewcvs-markup

Because, as referenced here: http://www.java-gaming.org/forums/index.php?topic=15677.msg125477#msg125477 the biggest slow-down that JOODE currently experiences is in the implementation of the Real class, and its derivatives.
Offline Marvin Fröhlich

Senior Duke




May the 4th, be with you...


« Reply #11 - Posted 2007-01-30 18:41:45 »

Also, if it is decided that JOODE should use javax.vecmath throughout, we would rely on the vecmath implementation for vector length (Math.sqrt()):

https://vecmath.dev.java.net/source/browse/vecmath/src/javax/vecmath/Vector3f.java?rev=1.3&view=auto&content-type=text/vnd.viewcvs-markup

Because, as referenced here: http://www.java-gaming.org/forums/index.php?topic=15677.msg125477#msg125477 the biggest slow-down that JOODE currently experiences is in the implementation of the Real class, and its derivatives.

Well, we are using (a slight modification of) Kenji Hiranabe's vecmath implementation in Xith3D. The difference to Sun's vecmath is that it is as GC-cheap as possible, though not thread safe. And we can modify it if needed. If you would use this lib, too, there wouldn't be a problem to make use of the above optimization.

Marvin
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #12 - Posted 2007-01-30 18:44:19 »

Quote
1. Correctness of computed values

It is accurate to 4 decimal places. Iterations over the last line in the algorithm produces more accurate results. If you look at the optimisation, one line has been commented out as I have replaced the initial guess with one that yields more accurate results.

Quote
2. Portability to other platforms (and correctness there too)
You do realise this is java right?


This is a contribution, take it or leave it, its up to you.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline Amos Wenger

Senior Duke




Everything's possible, but not everything's fun...


« Reply #13 - Posted 2007-01-30 19:01:20 »

I agree both with Marvin and darkprophet.

I'd find cool if you, biggeruniverse, would use the same version of vecmath (Kenji Hiranabe modified) as us (in Xith3D) so that we can add these optimisations (if you don't want to change regular sin()/cos()/sqrt() methods we could have fastXXX() ones).

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #14 - Posted 2007-01-30 19:14:54 »

It is accurate to 4 decimal places. Iterations over the last line in the algorithm produces more accurate results. If you look at the optimisation, one line has been commented out as I have replaced the initial guess with one that yields more accurate results.

Well, what accuracy is JOODE guaranteeing to the user? Is accuracy v. speed configurable? At what point of accuracy is this slower than Math.sqrt?

You do realise this is java right?

JOODE is Java, that code is converted C code. It was written to be close to the hardware, which of course makes me suspicious of it. Has this Java code been shown to work on any non-x86 environment? (It should of course, but better to test these things before they are relied upon to be always correct)

This is a contribution, take it or leave it, its up to you.

I hope we take it, as it is faster, but first it has to be proven out.

I agree both with Marvin and darkprophet.

I'd find cool if you, biggeruniverse, would use the same version of vecmath (Kenji Hiranabe modified) as us (in Xith3D) so that we can add these optimisations (if you don't want to change regular sin()/cos()/sqrt() methods we could have fastXXX() ones).

Well, first thing first, let me finish the conversion to pure vecmath. I'll branch it for easy testing, and then it can be decided what to do about optimizations.
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #15 - Posted 2007-01-30 19:26:22 »

non-x86 platform? So that implies PPC right? Which means older macs and PS3.

Quote
Well, what accuracy is JOODE guaranteeing to the user? Is accuracy v. speed configurable? At what point of accuracy is this slower than Math.sqrt?

If you read above, the Accuracy VS Speed is configurable depending on the number of loops on the last line. As for the accuracy of JOODE, your depending on LCP in the first place, which isn't highly accurate, but achieves visually convincing results and is stable. If you want accuracy, im afraid your going to have to change all of JOODE.

If you want to re-prove what Quake3 and I (and countless others) already have proved that it is a worthwhile optimisation, then by all means go ahead Smiley

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline t_larkworthy

Senior Duke


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #16 - Posted 2007-01-30 22:10:19 »

myeah, fairly convincing argument. 4dp is pretty nice. Probably should go for it after a good test

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline t_larkworthy

Senior Duke


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #17 - Posted 2007-01-30 22:19:24 »

@biggeruniverse
your PM inbox is full! I don't know your sourceforge UNIX username

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #18 - Posted 2007-02-01 09:57:03 »

o noes! Well, it's biggeruniverse. I know, I ought to be more creative...
Offline t_larkworthy

Senior Duke


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #19 - Posted 2007-02-01 13:53:08 »

OK your now a developer biggeruniverse

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #20 - Posted 2007-02-01 15:57:41 »

non-x86 platform? So that implies PPC right? Which means older macs and PS3.

Try SPARC, anything MIPS, or Cell.

If you read above, the Accuracy VS Speed is configurable depending on the number of loops on the last line. As for the accuracy of JOODE, your depending on LCP in the first place, which isn't highly accurate, but achieves visually convincing results and is stable. If you want accuracy, im afraid your going to have to change all of JOODE.

*Is JOODE accuracy v. speed configurable

If you want to re-prove what Quake3 and I (and countless others) already have proved that it is a worthwhile optimisation, then by all means go ahead Smiley

Did they prove it in Java?

If you look at the change log, you will notice that this code is already in place (with a different initial value). I put it there myself (well, with Amos' help). However, I left it commented out, since there is currently no way to choose, nor was there a concensus on its use.
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #21 - Posted 2007-02-01 16:24:17 »

Sorry, only machine I have and is accessible to me is a AMD Athlon X2. I doubt anybody with a SPARC/MIPS will run JOODE tho given that SPARCS or MIPS aren't exactly gaming machines Smiley

In any case, what basis do you have for the results being different other than "just in case"?

1: Java gurantees that the code runs the same on all platforms and as swpalmer noted, its all IEEE 754....
2: In that paper you referenced in the comments, it clearly states it works on common hardware.

I think you are not giving me the real reason why you dont want this included and frankly, I dont care anymore. Like I said before, its a contribution, the polite thing to do say thanks for the contribution, encourage more people to contribute and do what the hell you please with the code thats given. I personally doubt I will be contributing to JOODE again given the poor spirit of the project.

DP


Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #22 - Posted 2007-02-01 16:49:36 »

Don't take me as any indication of the larger project community. It is still a very young project, and has no general "spirit" yet. Tom has already stated he's happy with the contrib, and the thread is becoming an off-topic about Java portability when using "magic" algorithms that rely on specific standards and/or architectures.

I don't like to simply say "Thanks for the contribution, move along." I prefer a public discussion of the patch, what the submitter has done and why, as per the spirit and guidelines of the project. It leads to a better quality of patches. I'm not saying it has to be a hearing before a committee either, but it does not justice to the patch writer to simply take their patch and trash it.

I hope that you will contribute in the future, and I hope you will at least consider JOODE for volatile.
Offline cylab

JGO Ninja


Medals: 52



« Reply #23 - Posted 2007-02-01 21:39:46 »

This algorithm is actually covered in a book of mine (3D Game Engine Architecture) and is part of the Wild Magic 3d Engine . It seems to be a quote common "hack" in 3D engines, so I believe it's save. It is described here and here. The documentation section on http://www.geometrictools.com has a lot of probably useful stuff...

Mathias - I Know What [you] Did Last Summer!
Offline Amos Wenger

Senior Duke




Everything's possible, but not everything's fun...


« Reply #24 - Posted 2007-02-02 16:03:32 »

Well, what accuracy is JOODE guaranteeing to the user? Is accuracy v. speed configurable? At what point of accuracy is this slower than Math.sqrt?
Why not let the user configure that ?
Just a "Math Optimizations" Enable/Disable options.

JOODE is Java, that code is converted C code. It was written to be close to the hardware, which of course makes me suspicious of it. Has this Java code been shown to work on any non-x86 environment? (It should of course, but better to test these things before they are relied upon to be always correct)
biggeruniverse, see the beginning of this thread. It has been reported to work on a 64bit processor.

I hope we take it, as it is faster, but first it has to be proven out.
See DP benchmark. Or were you talking about non-x86 platform compatibility ?

Well, first thing first, let me finish the conversion to pure vecmath. I'll branch it for easy testing, and then it can be decided what to do about optimizations.
OK, no problem.
Anyway, change from sun vecmath to our modified vecmath is pretty straight-forward.

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #25 - Posted 2007-02-02 17:39:17 »

Why not let the user configure that ?
Just a "Math Optimizations" Enable/Disable options.
That's what I was getting at.

OK, no problem.
Anyway, change from sun vecmath to our modified vecmath is pretty straight-forward.

cool. I plan to commit the branch (mostly complete) this evening.
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #26 - Posted 2007-02-03 04:35:19 »

Sorry, only machine I have and is accessible to me is a AMD Athlon X2. I doubt anybody with a SPARC/MIPS will run JOODE tho given that SPARCS or MIPS aren't exactly gaming machines Smiley

In any case, what basis do you have for the results being different other than "just in case"?

1: Java gurantees that the code runs the same on all platforms and as swpalmer noted, its all IEEE 754....
2: In that paper you referenced in the comments, it clearly states it works on common hardware.

I think you are not giving me the real reason why you dont want this included and frankly, I dont care anymore. Like I said before, its a contribution, the polite thing to do say thanks for the contribution, encourage more people to contribute and do what the hell you please with the code thats given. I personally doubt I will be contributing to JOODE again given the poor spirit of the project.

I don't think the hostility in your message is warranted.  I see no hidden motives for rejecting the code, only straight-forward, honest inquiry as to whether it works in all Java environments, where the JOODE project as a whole is drawing the line in terms of trade-off vs. speed, and how this fits in with those decisions.

I also don't think dismissing SPARC/MIPS is in the "spirit" of Java.  JOODE may be developed primarily for game physics, but there is no reason to limit it to gaming unless there is a significant gain.

I agree with the idea of a on/off switch for faster less-accurate math routines, but I wonder if adding such an option will impose a performance penalty of its own?  I would hope that if the math code is called through an interface that HotSpot will inline the virtual calls since there will likely only be one implementation in use anyway.

Offline Amos Wenger

Senior Duke




Everything's possible, but not everything's fun...


« Reply #27 - Posted 2007-02-03 09:08:27 »

I agree with the idea of a on/off switch for faster less-accurate math routines, but I wonder if adding such an option will impose a performance penalty of its own?  I would hope that if the math code is called through an interface that HotSpot will inline the virtual calls since there will likely only be one implementation in use anyway.
Yeah just what I thought... but are calls via an interface inlined ? (I have very limited knowlege of the JVM internals)

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline cylab

JGO Ninja


Medals: 52



« Reply #28 - Posted 2007-02-03 11:11:08 »

An option could be to use a preprocessor (e.g. vpp) to produce two different vecmath-jars, an accurate and a fast one, so you could at least change the implementation by setting up the classpath accordingly.

Mathias - I Know What [you] Did Last Summer!
Offline darkprophet

Senior Duke




Go Go Gadget Arms


« Reply #29 - Posted 2007-02-03 15:21:09 »

Quote
I don't think the hostility in your message is warranted.  I see no hidden motives for rejecting the code, only straight-forward, honest inquiry as to whether it works in all Java environments, where the JOODE project as a whole is drawing the line in terms of trade-off vs. speed, and how this fits in with those decisions.

I also don't think dismissing SPARC/MIPS is in the "spirit" of Java.  JOODE may be developed primarily for game physics, but there is no reason to limit it to gaming unless there is a significant gain.

Your using java, yet your questioning its most core value before you have even tested the code out on the various archs ? Just seems a bit naff to me to be honest. Its like saying "oh, i shouldn't take a step forward, because the marble floor infront of me has a slightly different shade than the one im stepping on now, lets test it with an anvil!"

Also, the LCP iterator is pretty much usless for simulations anyway, so im not sure what applications JOODE or even ODE has outside of gaming...

cylab: why vpp? you could use APT which comes with javac and eclipse these days anyway. LWJGL uses it for generation of their GL classes and extensions. Saves introducing another dependancy, but thats up to you guys.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

theagentd (19 views)
2014-10-25 15:46:29

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (46 views)
2014-10-16 15:22:06

Norakomi (34 views)
2014-10-16 15:20:20

lcass (39 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (68 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (74 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!