Blog post: Blazing Fast Trees

Discuss topics related to BEPUphysics or physics engine development.
Post Reply
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Blog post: Blazing Fast Trees

Post by Norbo »

If you haven't seen it, check out the new blog post for information about early development for BEPUphysics v2.0.0:
http://www.bepuphysics.com/blog/2015/9/ ... trees.html
KakCAT
Posts: 32
Joined: Mon Apr 14, 2014 2:08 pm

Re: Blog post: Blazing Fast Trees

Post by KakCAT »

Hi Norbo,

the results seem impressive so far. I see the tests have been done in a quite powerful processor. Do you think the improvements in less powerful processor or even mobile devices (I'm mainly using Windows Phone with MonoGame) would be similar, or there'd be a big impediment in this new version which could affect mobile performance? (i.e. using far more memory than before).



Thanks!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Blog post: Blazing Fast Trees

Post by Norbo »

I haven't tested it on mobile, but my guess is it would behave similarly. The gap might actually be a little bit larger since mobile processors may still lack some of the desktop's coping skills when it comes to poor code and data flow. The old broadphase was filled with indirections of every kind, and it takes some pretty complex hardware to compensate.

Memory use should actually be lower on the new version, though again I haven't measured it specifically. The heap complexity is also hugely reduced. The one thing I could see a problem with is large object heap fragmentation caused by backing array resizes at high leaf counts, since all nodes are stored in a big contiguous array. This can only happen when adding additional leaves to the tree, so it's probably a good idea to specify an initial capacity large enough to handle the simulation upfront.
test44x
Posts: 15
Joined: Tue Jan 20, 2015 1:40 am

Re: Blog post: Blazing Fast Trees

Post by test44x »

Hi Norbo,

Great job as usual.

I haven't read all of the report, but from a glance, it seems the tests were done using multi-threading. Since BEPU is only deterministic using single-thread, will the performance be similar for single threaded use?

Also, will v2.0 be deterministic as well?


Thanks!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Blog post: Blazing Fast Trees

Post by Norbo »

I haven't read all of the report, but from a glance, it seems the tests were done using multi-threading. Since BEPU is only deterministic using single-thread, will the performance be similar for single threaded use?

Also, will v2.0 be deterministic as well?
Towards the end, the post has a single threaded versus single threaded case. The performance improvement is actually a little more significant for single threaded, since the new version's refinement phase doesn't scale optimally on many threads in 'easy' simulations yet.

v2.0.0 aims to be deterministic while multithreaded in terms of velocities output by the solver. So, while the tree might output different orderings of overlaps and the narrow phase may generate constraints in different orders, the solver should still be able to produce the same result. I can't guarantee that this will be the case yet, though. The pipeline isn't fully fleshed out yet and a few questions remain.

(And of course, it will only be locally deterministic; different processors could still easily produce different results.)
sergiusz308
Posts: 49
Joined: Mon Oct 08, 2012 4:57 pm

Re: Blog post: Blazing Fast Trees

Post by sergiusz308 »

Hi Norbo, looking through the code it seems you use unsafe contexts a lot - why so?

Thanks,
Sergiusz
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Blog post: Blazing Fast Trees

Post by Norbo »

Depending on which part, performance, memory, or convenience. For example, the early n-ary tree node implementations needed to have an easy way to select the properties of a particular child by index. Storing children as managed arrays on a per node basis would destroy locality and introduce a bunch of unnecessary bounds checking. Switch statements avoid the locality issues, but create really nasty code. Fixed buffers require unsafe anyway. So, the easiest and fastest way was to treat the struct fields as a c-style array.

Another example are the memory pools used by the refinement process. It makes use of a bunch of different blittable value types. I could have used only managed code and created a bunch of typed arrays (as I do in some other areas), but it would have spawned a bunch of arrays that I couldn't really reuse because of their specific types. Instead, it was easier to just grab a big chunk of memory in the form of a common managed type array and then suballocate the various other blittable types within it using unsafe code.

For similar reasons, I'd really like C# to support generic pointers.
Post Reply