Simplex3D Port

[Hicks, Matt]

The porting is almost complete as the code now compiles and all the "render" tests work but most of the "ui" package is still broken.

Lex, I'm finding that I have to change calls like:

worldMatrix := Mat3x4d.Identity.translate(Vec3d(0.0, 0.0, -101.0)).scale(2.02 / height)

to

worldMatrix := Mat3x4d.Identity.scale(2.02 / height).translate(Vec3d(0.0, 0.0, -101.0))

for them to work as they are supposed to.  That seems odd to me as I would expect simplex to work the same way as Sgine's math library does in that respect?

[Hicks, Matt]

I just committed some updates that resolve a few of the problems and now some of the "ui" package tests work.

It would seem order of operations is causing some problems and mouse-picking is broken now.  The following tests in the "ui" package are still not working as they should:

• TestButton
• TestCube
• TestFocus
• TestLayout
• TestMousePicking
• TestScale9
• TestStates

The easiest to see there's a problem with is TestStates as it works, but it's not updating to the right position. I believe it has to do with it scaling before moving, so doesn't apply properly.

[Hicks, Matt]

Alright, I flipped the mix-in order for Scale, Location, and Rotation and now things look better.

However, now TestCube works but it's incredibly choppy.  I went back to the default branch and ran it and it's perfectly smooth running at 3800fps.  With the simplex3d branch it runs about 2500fps and is horrible.

Lex, I'm going to take a step back and let you look into this and see if you can resolve it.  This is the exact problem I was concerned about by creating new objects so frequently.  I know there hasn't really been any tuning yet, so hopefully you've got some magic up your sleeve to make this work.

Until I hear back on this item I'm going back to the default branch.

[Lex]

With simplex3d transformation operations happen in the order they
appear: so rotate() translate() scale() will rotate first, then
translate, then scale.
In sgine math package it was the other way around: rotate()
translate() scale() would scale first, then translate and finally
rotate.
The order is a matter of taste, I thought it would be easier to follow
what is going on when transformations happen in the same order they
are written.

I have update to the latest simplex3d branch and running
org.sgine.renderer.TestCuboid on jdk 6. As far as I can tell the speed
is the same as with sgine default branch. Also I have tried running it
while monitoring with VisualVM. The GC plugin shows 5 collections PER
MINUTE.
I have found that when a part of the test window is behing another
window, the FPS goes up. With the test window completely covered the
FPS goes from 1500 to 4300. Please ensure that you are not covering
the window while testing. Also double check that you donot have other
processes running in the background affecting tests (switching from
one branch to another could cause eclipse to perform different tasks).

Infomration about your jdk version and any vm arguments would help as
well. I do not posess the magic to fix something I cannot replicate.


On Jul 3, 8:41 am, "Hicks, Matt" <mhi...@captiveimagination.com>
wrote:

> Alright, I flipped the mix-in order for Scale, Location, and Rotation and
> now things look better.
>
> However, now TestCube works but it's incredibly choppy.  I went back to the
> default branch and ran it and it's perfectly smooth running at 3800fps.
> With the simplex3d branch it runs about 2500fps and is horrible.
>
> Lex, I'm going to take a step back and let you look into this and see if you
> can resolve it.  This is the exact problem I was concerned about by creating
> new objects so frequently.  I know there hasn't really been any tuning yet,
> so hopefully you've got some magic up your sleeve to make this work.
>
> Until I hear back on this item I'm going back to the default branch.
>
> On Sat, Jul 3, 2010 at 7:26 AM, Hicks, Matt
> <mhi...@captiveimagination.com>wrote:
>
> > I just committed some updates that resolve a few of the problems and now
> > some of the "ui" package tests work.
>
> > It would seem order of operations is causing some problems and
> > mouse-picking is broken now.  The following tests in the "ui" package are
> > still not working as they should:
>

> >    - TestButton
> >    - TestCube
> >    - TestFocus
> >    - TestLayout
> >    - TestMousePicking
> >    - TestScale9
> >    - TestStates

[Lex]

I have tested org.sgine.ui.TestCube (I assume this is the one you are
talking about, not the TestCuboid).

The restults:
Simplex3d branch: (Large Cube) 4000FPS; ~1.2 seconds spent in GC over
2 minutes
Default brnach: (Small Cube) 4500FPS; ~0.4 seconds spent in GC over 2
minutes

I have to say that framerates above the display refresh rate are not
an accurate measure of performance. In this case the cube sizes are
not the same, so the test is not accurate, because a lot of FPS can be
gained due do a different fillrate (similarly to how a lot of FPS can
be gained by covering a part of the test window).
The demo looks equally smooth to me in both cases. I have noticed for
this particular demo that mouse-over causes a printout to the
System.out. This goes through OS I/O pipes and could cause the thread
to block, resulting in choppiness. Another reason could be a process
running in the background.
Please make sure you have nothing running on the background, no mouse
over the test window, no windows covering the test window and run the
test again.

[Lex]

I have re-analyzed the test results of "org.sgine.ui.TestCube". Here
is what I came up with.
When running the test from the default branch, GC occures more often,
at the average rate of 3 GC per second. When running the simplex3d
branch, GC occurs at the rate of 1.5 GC per second. So GC occurs LESS
OFTEN and takes LONGER. This could be the cause of choppiness.

Most of the garbage during the test from the default branch gets
collected in yong generation with old generation being relatively
stable. On the other hand in simplex3d branch, the old generation
grows very quickly. I think objects are "leaking" from eden into
survivor and old generation space, causing GC to occure less often and
with longer pauses.

If that causes choppiness, then the solution is to copy the result of
computations into existing objects instead of updating the references.
This would keep the stable old generation and let most of the objects
die yong, causing GC to occure more often and take less time, reducing
the maximum delay between frames and removing choppiness.

In this particular demo, the references are most likely leaking
through Property updates. I would need you help to change that and
retest.

[Hicks, Matt]

More and more I keep coming back to the issue of garbage creation being a big problem long-term.  Having a math library that does not lend itself well to mutability seems to be problematic in that regard.  Ideally I would like it to be possible to create a game that creates almost no garbage at all.  There's no way that would be possible with Simplex3D, right?

I've done quite a bit of testing on performance with a Vector3 / Vec3d to determine speed of adding values and on one billion iterations here's what I've come up with:

• Sgine (default) Immutable - 96.7s
• Sgine (default) Mutable - 20.2s
• Simplex Immutable - 18.6s
• Sgine (new test implementation) Array Immutable - 117.4s
  
• Sgine (new test implementation) Array Mutable - 55.6s
• Sgine (new test implementation) Buffer Immutable - 159.3s
• Sgine (new test implementation) Buffer Mutable - 65.4s
• Sgine (new test implementation) DirectBuffer Immutable - never finishes
• Sgine (new test implementation) DirectBuffer Mutable - 63.3s

The "new test implementation" is similar to the test I created previously but a bit cleaner (http://captiveimagination.com/download/sgine-math2/org/sgine/math/).  The performance is much less than that of both the current Sgine implementation and the Simplex implementation but these times are based on one billion operations.  If you take a look at the slowest one (Buffer Immutable) it's still processing 6,277 updates every MILLISECOND.  I've been comparing performance concerned that the math library will be creating unnecessary lag in the engine but after realizing how minimal of an impact this should have on the overall performance of the engine performance is really less of a concern.

Lex, I think you've done amazing things with Simplex and I really hope we can resolve the problems in the port but I'd really like to get some feedback from everyone on this topic as the math library is a critical piece of our engine and the direction we take with it is not one I want to take lightly.

As I see it we have three options:

1. Stick with what we've got. It's working well right now and although it's got some potential problems (like every Matrix4 being backed by a direct buffer) it's clean and straight-forward.
2. Switch to Simplex3D. We've been working on the branch to do this and although it is mostly working now we've hit a snag where garbage creation is causing some serious choppiness issues in animations.  Unfortunately I fear this will not easily be fixed because of the design of Simplex focusing mostly on immutability and creation of new instances rather than modifying existing.  Lex, you can speak more to the current possibilities of making this fit.
3. Switch to the "sgine-math2" concept I've outlined in the link above. There's a lot of work that needs to go into it, it's slower than either of the other options, but provides an incredibly smooth and tight foundation for any math operations.  It supports both mutable and immutable well, can be backed by an array, buffer, direct buffer, or any other pluggable store.

Lex, it sounds like you've got some ideas of improving performance, but no matter what we do is there any way Simplex is doing to support mutability like I'm asking for?  Everyone else, am I crazy for wanting the math library to so foundationally support mutability?

All responses are extremely welcome here.

-Matt

[Lex]

I think the problem is not so much in creating garbage as it is in
creating old-generation garbage. Right now references to computation
results are assigned to permanent objects and reassigned each frame.
This ceares old-generation garbage that is more expensive to collect,
and collecion happens in bigger chunks, causing the choppness. Having
mutable instances and setting them to computation results should fix
it. Basically making garbage is ok, while leacking it into the
permanent structures is not ok.

If that does not fix the problem, then other options should be
explored.

I am not planning to support operations that modify objects locally
and lead to manual garbage management. Such design requires a lot more
effort to use, and the resulting code is much harder to read and
maintain. Also when jdk 7 comes, such code will not provide any
performance benefits and may in fact be slower.

I want to have a solution that is reasonable to work with now, and
does not get outdated so quickly. I am looking into possibility of
creating semi-automated garbage managenement by injecting temporary
objects using implicits. This way you would be able to maintain source-
code level compatibility with simplex3d api, so you can recompile
without the garbage management. This solution would be equally good
for both java6 and java7.


On Jul 3, 8:58 pm, "Hicks, Matt" <mhi...@captiveimagination.com>
wrote:

> More and more I keep coming back to the issue of garbage creation being a
> big problem long-term.  Having a math library that does not lend itself well
> to mutability seems to be problematic in that regard.  Ideally I would like
> it to be possible to create a game that creates almost no garbage at all.
> There's no way that would be possible with Simplex3D, right?
>
> I've done quite a bit of testing on performance with a Vector3 / Vec3d to
> determine speed of adding values and on one billion iterations here's what
> I've come up with:
>

>    - Sgine (default) Immutable - 96.7s
>    - Sgine (default) Mutable - 20.2s
>    - Simplex Immutable - 18.6s
>    - Sgine (new test implementation) Array Immutable - 117.4s
>    - Sgine (new test implementation) Array Mutable - 55.6s
>    - Sgine (new test implementation) Buffer Immutable - 159.3s
>    - Sgine (new test implementation) Buffer Mutable - 65.4s
>    - Sgine (new test implementation) DirectBuffer Immutable - never finishes
>    - Sgine (new test implementation) DirectBuffer Mutable - 63.3s

>
> The "new test implementation" is similar to the test I created previously
> but a bit cleaner (http://captiveimagination.com/download/sgine-math2/org/sgine/math/).  The
> performance is much less than that of both the current Sgine implementation
> and the Simplex implementation but these times are based on one billion
> operations.  If you take a look at the slowest one (Buffer Immutable) it's
> still processing 6,277 updates every MILLISECOND.  I've been comparing
> performance concerned that the math library will be creating unnecessary lag
> in the engine but after realizing how minimal of an impact this should have
> on the overall performance of the engine performance is really less of a
> concern.
>
> Lex, I think you've done amazing things with Simplex and I really hope we
> can resolve the problems in the port but I'd really like to get some
> feedback from everyone on this topic as the math library is a critical piece
> of our engine and the direction we take with it is not one I want to take
> lightly.
>
> As I see it we have three options:
>

>    1. Stick with what we've got. It's working well right now and although

>    it's got some potential problems (like every Matrix4 being backed by a
>    direct buffer) it's clean and straight-forward.

>    2. Switch to Simplex3D. We've been working on the branch to do this and

>    although it is mostly working now we've hit a snag where garbage creation is
>    causing some serious choppiness issues in animations.  Unfortunately I fear
>    this will not easily be fixed because of the design of Simplex focusing
>    mostly on immutability and creation of new instances rather than modifying
>    existing.  Lex, you can speak more to the current possibilities of making
>    this fit.

>    3. Switch to the "sgine-math2" concept I've outlined in the link above.

[Hans Häggström]

Well, my thoughts as a future user of the library and minor contributor are:

* The Simplex math library is very user friendly to work with, and
based on the widely used glsl which was one of the better library
designs to come out of OpenGL standardization.

* Garbage collection hick-ups is maybe _the_ reason why the JVM is not
widely used on the client side in games. It's very important to avoid
long garbage collection pauses.

So, I'm in favor of trying to get the simplex math library to work
smoothly in one form or another.
Some thoughts, not sure if you guys tried them yet:

* Some kind of pool system for math object instances - keep weak
references to created instances, and re-use unused ones when a new one
is needed instead of creating a new instance. I've seen something
like this done with the special Java references (weak etc.) for data
access, not sure if it would work in this case.

* Can the garbage collector be configured to run more often? Or to be
more aggressive about collecting? With suitable command line
arguments or programmatically.

* Are there alternative garbage collectors for real-time systems that
could be used?

* Could some Scala type level- or implicit magic be used to eliminate
the need for creating new math object instances in cases where the
created objects are immediately passed as parameters to other math
objects, math object buffers, or properties?

-- Hans

On Sun, Jul 4, 2010 at 3:58 AM, Hicks, Matt

[Landei]

I pretty much agree. If we could do without mutability in math, it
would simplify the design. As the overall performance looks good, we
should look hard how to resolve the GC problem. If it turns out that
Java 7 will solve that problem for us, I think we can even live some
time with a (not too bad) suboptimal solution.

Unfortunately I have not enough experience with GC tweaking in order
to make suggestions or to comment the existing ones. The only thing
coming to my mind is to look at other JVMs, and give a recommendation
if one behaves better (as "serious" games usually bundle their JVMs).

Cheers,
Daniel

> ...
>
> Erfahren Sie mehr »

[Hicks, Matt]

Though I agree that determining the optimal configuration and bundling is the ideal for any game and something game developers should endeavor to do, I disagree that we should be forcing ourselves into a box and forcing the developers into a box of what they can develop against.

What about applets and webstarts?  Are we going to force them to upgrade to the unreleased Java 7?  Even after Java 7 is released it will be a long time before it's generally available on machines and even then it will probably be at least a year before Apple decided to release an update to use Java 7.

My goal for Sgine is to make a 3D engine that is easy to use but extremely powerful.  I think forcing specific requirements to run on the developers is a bad thing to do if we can avoid it and I think we can.  Yes, the ideal would be to use immutables as they simplify design and reduce the likelihood of bugs, but it looks more and more likely that this isn't going to work at least with Java 6.

[Hicks, Matt]

I just pushed an update to remove the hack Lex put in.  Lex, I updated all callers to properly update instead of assign and that seems to have done the trick.

Okay, so I've done some testing with all the updates in place and here's where we stand:

• Simplex (1.6u20x32-bit) - 2500fps, 0.003 max delay
• Default (1.6u20x32-bit) - 2700fps, 0.003 max delay
• Simplex (1.6u20x64-bit) - 3100fps, 0.003 max delay
• Default (1.6u20x64-bit) - 3200fps, 0.003 max delay
• Simplex (1.6u20x64-bit server) - 3200fps, 0.003 max delay
• Default (1.6u20x64-bit server) - 3300fps, 0.003 max delay
• Simplex (1.6u12x32-bit) - 2600fps, 0.04 max delay
• Default (1.6u12x32-bit) - 2600fps, 0.003 max delay

We're finally to the point everything seems to be relatively smooth except Simplex branch on u12 32-bit.  It's still pretty choppy.  Does anyone have a Mac?  If so I'd like to know what the current default runtime version is, if it's past u12 then it might be acceptable to move forward as we are.

Lex, there are two final concerns if we decide this is acceptable:

1. As you can see from the above tests Simplex is showing to be slower than the default branch.  Is there anything you can do to improve this?  Seems like a bad idea to switch libraries and lose performance as a result. :o
2. The mouse-picking is broken now.  Can you take a look at that when you get a chance?

If we can resolve these issues there will be just a bit more testing and cleanup and then we can merge the simplex3d branch back to default.  Any further concerns with making this change should be brought up now before it's too late.  Once the merge is done the final decision is made.

Thanks,

Matt

[Lex]

The test cases (at 6000fps) were affected by the changes to the label
displayed on the screen more than anything else. The only performance
issue is with java6u12 which is simply outdate, it was released 1.5
years ago (in february 2009).

The new test with lots of cubes and sane fps shows that simplex is
faster than the original math library. There is a big issue with the
performance of sgine itself, since rendering 100 object brings the
speed down to 60 to 100 fps. JNI on java is certanly a big bottleneck,
however I have tested rendering 5000 objects with about the same fps
as sgine with 100 objects. Even breaking down each cube into 6 sides
and counting 600 objects is still not enough to explain such low fps.
Given that the bottleneck is somewhere else, and simplex branch is
already performing 5-10% faster, you can expect the simplex branch to
perform much better when the issue with slow rendering is resolved.

On Jul 4, 1:01 pm, "Hicks, Matt" <mhi...@captiveimagination.com>
wrote:

> I just pushed an update to remove the hack Lex put in.  Lex, I updated all
> callers to properly update instead of assign and that seems to have done the
> trick.
>
> Okay, so I've done some testing with all the updates in place and here's
> where we stand:
>

>    - Simplex (1.6u20x32-bit) - 2500fps, 0.003 max delay
>    - Default (1.6u20x32-bit) - 2700fps, 0.003 max delay
>    - Simplex (1.6u20x64-bit) - 3100fps, 0.003 max delay
>    - Default (1.6u20x64-bit) - 3200fps, 0.003 max delay
>    - Simplex (1.6u20x64-bit server) - 3200fps, 0.003 max delay
>    - Default (1.6u20x64-bit server) - 3300fps, 0.003 max delay
>    - Simplex (1.6u12x32-bit) - 2600fps, 0.04 max delay
>    - Default (1.6u12x32-bit) - 2600fps, 0.003 max delay

>
> We're finally to the point everything seems to be relatively smooth except
> Simplex branch on u12 32-bit.  It's still pretty choppy.  Does anyone have a
> Mac?  If so I'd like to know what the current default runtime version is, if
> it's past u12 then it might be acceptable to move forward as we are.
>
> Lex, there are two final concerns if we decide this is acceptable:
>

>    1. As you can see from the above tests Simplex is showing to be slower

>    than the default branch.  Is there anything you can do to improve this?
>    Seems like a bad idea to switch libraries and lose performance as a result.
>    :o

>    2. The mouse-picking is broken now.  Can you take a look at that when you

>    get a chance?
>
> If we can resolve these issues there will be just a bit more testing and
> cleanup and then we can merge the simplex3d branch back to default.  Any
> further concerns with making this change should be brought up now before
> it's too late.  Once the merge is done the final decision is made.
>
> Thanks,
>
> Matt
>
> On Sun, Jul 4, 2010 at 10:12 AM, Hicks, Matt
> <mhi...@captiveimagination.com>wrote:
>
> > Though I agree that determining the optimal configuration and bundling is
> > the ideal for any game and something game developers should endeavor to do,
> > I disagree that we should be forcing ourselves into a box and forcing the
> > developers into a box of what they can develop against.
>
> > What about applets and webstarts?  Are we going to force them to upgrade to
> > the unreleased Java 7?  Even after Java 7 is released it will be a long time
> > before it's generally available on machines and even then it will probably
> > be at least a year before Apple decided to release an update to use Java 7.
>
> > My goal for Sgine is to make a 3D engine that is easy to use but extremely
> > powerful.  I think forcing specific requirements to run on the developers is
> > a bad thing to do if we can avoid it and I think we can.  Yes, the ideal
> > would be to use immutables as they simplify design and reduce the likelihood
> > of bugs, but it looks more and more likely that this isn't going to work at
> > least with Java 6.
>

> >> ). The

> ...
>
> read more »

[Landei]

I haven't made a benchmark to proove it, but I still think that the
BubbleSort used in NodeView is a typical candidate for code that works
fine for a few objects but doesn't scale.

Cheers,
Daniel

> ...
>
> Erfahren Sie mehr »

[Hans Häggström]

The average case for bubble sort is quadratic O(n2)
http://en.wikipedia.org/wiki/Bubble_sort

I wouldn't recommend bubble sort for any use.

Quicksort is pre-implemented for arrays in Java as well as most
programming languages, and has an average performance of O(n log n)
http://en.wikipedia.org/wiki/Quicksort

Merge sort is also often used, it has the nice property of being O(n)
in the case where the input is already sorted, and O(n log n) average
case (if I recall correctly Javas collections framework was using some
variant of it).
http://en.wikipedia.org/wiki/Merge_sort

-- Hans

[Hicks, Matt]

The only requirement I have for it's removal is that someone write the alternative. ;)

2010/7/7 Hans Häggström <hans.ha...@iki.fi>

[Landei]

We can "borrow" the simple iterative in-place quicksort from
http://www.scala-lang.org/node/57

It would look like this (not tested):

def quicksort[A](a: ResizableArray[A], sortFunction: (A, A) =>
Boolean): ResizableArray[A] = {

def swap(i: Int, j: Int) {
val t = a(i); a(i) = a(j); a(j) = t
}

def sort1(l: Int, r: Int) {
val pivot = a((l + r) / 2)
var i = l
var j = r
while (i <= j) {
while (sortFunction(a(i), pivot)) i += 1
while (sortFunction(pivot, a(j))) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}

if (a.length > 0)
sort1(0, a.length - 1)
a
}

As further improvement we could consider to use the more standard
Ordered trait instead of sortFunction.

Cheers,
Daniel

On 7 Jul., 14:36, "Hicks, Matt" <mhi...@captiveimagination.com> wrote:
> The only requirement I have for it's removal is that someone write the
> alternative. ;)
>

> 2010/7/7 Hans Häggström <hans.haggst...@iki.fi>

>
> > The average case for bubble sort is quadratic O(n2)
> >http://en.wikipedia.org/wiki/Bubble_sort
>
> > I wouldn't recommend bubble sort for any use.
>
> > Quicksort is pre-implemented for arrays in Java as well as most
> > programming languages, and has an average performance of O(n log n)
> >http://en.wikipedia.org/wiki/Quicksort
>
> > Merge sort is also often used, it has the nice property of being O(n)
> > in the case where the input is already sorted, and O(n log n) average
> > case (if I recall correctly Javas collections framework was using some
> > variant of it).
> >http://en.wikipedia.org/wiki/Merge_sort
>
> > -- Hans
>

> > On Wed, Jul 7, 2010 at 10:15 AM, Landei <danielgro...@googlemail.com>

> ...
>
> Erfahren Sie mehr »

[Hans Häggström]

Well, the problem with quicksort is that it actually has a worst case
for already sorted lists.
So mergesort would probably be the best bet.

Googling around, it seems timsort is a well optimized merge sort that
does quite well for data that is already sorted or partially sorted.
It's in use in python and Java 7. I found a Java version of it
online, but it was GPL2 licensed.

As Java 6- already has a merge sort for collections, I was thinking of
just using it - swapping out ListBuffer to an ArrayList inside
nodeview. It should still be quite fast, and reap any advantages of
Java library development. The only outside view of the collection is
an iterator getter, but I couldn't find the utility method for
converting a Java iterator to a Scala one.

(The sort algorithm provided by scala appears to be a standard
quicksort, so not a good idea for a renderlist which is going to be
almost sorted most of the time).

-- Hans

[Hicks, Matt]

What about this?

http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/

2010/7/7 Hans Häggström <hans.ha...@iki.fi>