Page 1 of 1

Blog post: Blazing Fast Trees

Posted: Mon Sep 21, 2015 4:23 am
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

Re: Blog post: Blazing Fast Trees

Posted: Mon Sep 21, 2015 10:54 am
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!

Re: Blog post: Blazing Fast Trees

Posted: Mon Sep 21, 2015 4:38 pm
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.

Re: Blog post: Blazing Fast Trees

Posted: Mon Sep 28, 2015 9:03 am
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!

Re: Blog post: Blazing Fast Trees

Posted: Mon Sep 28, 2015 5:10 pm
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.)

Re: Blog post: Blazing Fast Trees

Posted: Wed Oct 21, 2015 8:57 am
by sergiusz308
Hi Norbo, looking through the code it seems you use unsafe contexts a lot - why so?

Thanks,
Sergiusz

Re: Blog post: Blazing Fast Trees

Posted: Wed Oct 21, 2015 6:02 pm
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.