A plan to isolate and kill global statics ...

Discussions for core devs and contributors. Read only for normal forum members to keep the noise low

A plan to isolate and kill global statics ...

Postby bitiotic » Mon Feb 18, 2013 6:50 am

Hi all!

Thanks for including me in the developer forum! I've been using libGDX for a year or so, and am glad to be able to contribute back to it.

I'm here to expand a bit on my comments (as "rootbeer" on github) on Xoppa's new Vector interface about the global temporaries exported by Vector2 and Vector3. Short version: Let's not worsen the libGDX API by propagating these temporaries. Let's keep the `tmp()` method out of the Vector API (and in general out of future APIs in libGDX).

First, the problem: In general, global, unlocked, mutable state isn't safe in a multi-threaded application. For examples, see the `tmp`, `tmp2`, and `tmp3` fields in Vector2 and Vector3, and similar things in Matrix*, Rectangle, and Quaternion. These global objects are also potentially unsafe within a single thread if they're used across method invocations that themselves use the same temporaries.

Currently, in practice these objects are used safely (and very efficient) in libGDX. Most uses are only on one thread (the render thread), and the uses are well contained or in leaf functions. Using these objects prevents allocating many temporary objects (creating GC pressure, etc).

However, the semantics on these fields are sketchy enough that I do not think its a good idea to export outside the library as it is impossible to document the restrictions on them without being rather draconian. For example, I think Vector3 needs a documentation note like "many Vector3 methods are only safe on the render thread", and that seems too stringent.

I propose the following for dealing with these APIs:

* General utility classes (e.g., com.badlogic.gdx.math.*) that may be used on other threads should not provide static global temporaries as service to other modules. Stamping these out will require cleaning up existing users.

* Existing uses of global shared temporaries should, where possible be avoided. If that is not possible, a parameter for passing in a temporary object should be added to the method in question (pushing the problem up to the caller). For one example, look at Vector3.lerp(), which can probably be changed to remove the need for a temporary, vs. Quaternion.setFromCross() which, AFAICT, probably needs some temporary storage passed in.

* Packages and classes that are already tied to a single thread can freely use private global state because the usage would be private to code in that package that can be reasoned about within the context of that package. Specifically, I would like to migrate all the uses of the Vector2.tmp* temporaries in stage2d into new stage2d-private global static objects.

I realize there are no current, concrete problems with the global temporaries, but they seem like the sort of thing that will create really awful bugs someday in the future for some multi-threaded client. So, even if no one ever gets around to cleaning up the current uses, it seems worthwhile to me to prevent new uses from being added.

For the specific case of Xoppa's diff, I think this just means leaving "tmp()" off the new Vector.java interface. I believe Xoppa updated rest of the diff to not depend on the temporaries in any way, so there should be no (additional) immediate impact on that change. (Right?)

I am working on some diffs to clean up global temp usage in Vector2. I'll try to send something out shortly that will make the above steps clearer and more concrete.
bitiotic
 
Posts: 81
Joined: Tue Feb 05, 2013 2:59 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Mon Feb 18, 2013 6:49 pm

The temps where a quick and dirty hack to remove GC pressure as you identified. The implications (mutability, thread-safety) are of course horrible, and i too would like to get rid of those if possible. While temp usage can be reduced, for some cases there's no way around needing temporary storage. Question is how to cope with that? Thread locals would be one option, but that will introduce considerable overhead. It also doesn't solve the mutability issue, where you can run into problems on the same thread.

Open for any pull requests and concrete suggestions! Thanks for taking the initiative.
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm

Re: A plan to isolate and kill global statics ...

Postby xoppa » Mon Feb 18, 2013 11:00 pm

I agree that deprecating the tmp members is a good initiative. What about a (static) pool for these classes and a .obtain and #free method? The #cpy method could have a boolean pooled argument. To maintain backwards compatibility the methods that use a tmp value can obtain and free a tmp value and also expose a signature accepting a tmp value (like I did in Bezier and BSpline).

BTW here's the pull request with the Vector interface bitiotic is refering.
xoppa
 
Posts: 689
Joined: Thu Aug 23, 2012 11:27 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Tue Feb 19, 2013 3:17 pm

Gah, forgot about the Vector pull. Merged. I removed the tmp() method from the interface.

We have three options (thanks for Nate for some input on this as well):

Pooling
Requires explicit freeing, which makes usage really bad. Also, needs synchronization for thread-safety if pool is shared across threads. Would need additional ThreadLocal lookup if we have one pool per thread. All of that's bad :/

ThreadLocal
Would solve the threading issue, but doesn't solve the issue of using tmp() multiple times in the same calculation. Also, ThreadLocal access is costly, and not portable to GWT.

Synchronization
Gdx classes that use tmp() could be synchronized to guarantee thread-safety. Very leaky, hard to do it everywhere, high overhead for the common use case (single-threaded).

"Unroll" temp usage
Many of the methods using temps could be "unrolled" to avoid usage of temporaries. E.g. Vector2/3 or Matrix4. If we cleaned those up at first to not use temp scratch vectors/matrices then we'd have at least made those classes thread-safe, without additional storage requirements, e.g. per instance scratch vectors. We could then try to do the same for classes that depend on the temps. This will result in more code, and be potentially error prone, but i think that's the cleanest solution.

I don't think any of these solutions is satisfactory. Any other ideas?
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Tue Feb 19, 2013 3:47 pm

I've been running through a few things, and it seems the best option is to modify the APIs so users have to provide scratch vectors matrices themselves. In case of Intersector, which makes the most use of temps, we could change things so you need an instance of an Intersector instead of having everything be public static. That way you'd be responsible to use one intersector per thread.

I would also be in favor of getting rid of the tmp field in Matrix4. Whoever (me...) thought that was a good idea should be executed...

Objections?
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm

Re: A plan to isolate and kill global statics ...

Postby bitiotic » Tue Feb 19, 2013 11:03 pm

No objections. I think pushing the decision of where/how to host the temporary out to a "clean" place where you can reason about the threading issues makes sense. For lots of code (most of the math.* utils, I think), that just means pushing the temporary out to the caller. For example, demos/pax-britannica/pax-britannica/src/de/swagner/paxbritannica/Ship.java can safely have a private static Vector2 object that it uses in `goTowardsOrAway` instead of using `Vector2.tmp()`.

As another example, I looked closely over stage2d, and I think all the places it uses the current Vector2 temporaries can be replaced with new stage2d-private statics. (Most of the uses are on a thread that is already tied to the render thread, and are clearly scoped to a single function). Some functions may need some API doc that says they're only safe on the render thread, but that doesn't seem like a new restriction to me.

Your solution for Intersector (instance with private temporary instances) seems like another approach that won't overly impact single-threaded code (which is probably the majority). Alternatively, you could add an "Intersector.Temporaries" parameter to those methods that reference tmp objects (if you feel the cost of converting all those static Intersector methods to instance methods is high). Thankfully, Intersector doesn't seem to be used directly by other library methods, so the change doesn't propagate.

Note that the farther down the stack the temporary is used (e.g., Quaternion -> Matrix -> Vector -> tmp) the more painful the API changes will be. That may push the unrolling harder in some places than in others. I do not have a sense for what the worst case in the current library is, though.

I think your summary of the more generic solutions like Pooling/ThreadLocal/Synchronization/etc is all spot on (sadly). I am hoping the "unrolling" doesn't get too outrageous, but I don't really have a strong handle on the current usage of static public temporaries outside of Vector{2,3}.


So, I think we can get away with these sorts of solutions to stamp out temporaries:

private static temporaries
For code that is already single-threaded for some reason, moving from public static temporaries to private static ones that can be reasoned about within that code.

API changes to pass temporaries into methods that need them
Generally pushes the temporaries into the application (which will generally just allocate a static object).

Instance temporaries
For code (like Intersector) that all shares a small number of temporary objects putting those temporaries in a convenient object instance that callers can deal with (sort of an advanced version of the API change).

Unrolling "temp" usage
Replace code that uses temporary objects with "straight-line" code that doesn't need a temporary. (Please copy the old implementation into a test case for the new implementation.)

As an aside on unrolling: do you have a sense of the cost of unrolling something like "Matrix4.tra()"? I would just create 16 local floats on the stack, but I vaguely recall JVMs having some problems with lots of local variables. (But that may be from 1997 and no longer relevant ...)

I vote we stay Mario's execution for putting the tmp field in Matrix4 since he seems so sorry about it.
bitiotic
 
Posts: 81
Joined: Tue Feb 05, 2013 2:59 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Thu Feb 21, 2013 9:47 am

Looked through your Vector2 PR, well done. It doesn't seem to impact the code to much, as you identified, scene2d is one of those "render-thread" only APIs anyways. Going forward, that's how we should deal with those things.

Making Intersector instancable only has a tiny drawback: object methods are a tad bit slower on Dalvik than static methods, virtual dispatch and all. Not to worried about that, the impact is likely not noticable.

I think the hardest pieces to unroll will be Vector3/Matrix4/Quaternion. Especially the mixture of Matrix4/Quaternion is quite a bit of work to get right. We might end up having to add quite a few additional method parameters here. Storing temporary results of Matrix.tra() in local vars should not be an issue, especially if we mark them as final for Dalvik (we do something similar in Sprite).

Agree to your steps, let's do it that way. I'll fix Intersector today (cause it's easy and i'm on sick leave). After that i'm ready to be hanged for Matrix#tmp.
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Thu Feb 21, 2013 10:59 am

Merged the Vector2 changes, added a blog post to tell folks. Also hinted at Vector3/Matrix/Quaternion being cleaned up. That may take a while though.
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm

Re: A plan to isolate and kill global statics ...

Postby arielsan » Thu Feb 21, 2013 11:29 am

About my mails to the Github pull request, I totally agree with removing tmp from vectors and about cleaning the math stuff, I was just wondering if having the private statics in scene2d classes is the best solution but it is ok for now, we are on a better state now :). In our code we are already using local tmp vectors when needed instead of using the Vector2.tmp()
Image
arielsan
 
Posts: 195
Joined: Sat Apr 02, 2011 3:58 pm

Re: A plan to isolate and kill global statics ...

Postby mzechner » Fri Feb 22, 2013 1:26 pm

Ahh, now i understand. Scene2d classes will never be thread-safe, and only make sense on the rendering thread. Hence the statics. Yeah, you heard me. NEVER!
mzechner
Site Admin
 
Posts: 4879
Joined: Sat Jul 10, 2010 3:50 pm


Return to Libgdx Development

Who is online

Users browsing this forum: No registered users and 1 guest