Storage of vertexes and planes in cpPolyShape

Discuss new features and future development.

Storage of vertexes and planes in cpPolyShape

Postby tomeksowi » Sun Jul 07, 2013 10:14 am

I guess this is a question/suggestion for the authors of Chipmunk or someone in the know of its implementation.

I noticed that upon creation of a cpPolyShape the verts and splitting planes are copied onto 2 newly allocated chunks of memory in setUpVerts. Why not put them in one chunk of mem?

I even thought of putting them in a variable length array in cpPolyShape but I then cpPolyShapeSetVerts would realloc the shape and thus could change the pointer, which can mess up things.

I don't expect it to make performance soar, but saving a malloc per shape on setup, some saved memory due to less fragmentation, and possibly a tiny improvement in read access times due to reduced cache thrashing may be worthwhile...
tomeksowi
 
Posts: 8
Joined: Sun Jul 07, 2013 9:40 am

Re: Storage of vertexes and planes in cpPolyShape

Postby tomeksowi » Sun Jul 07, 2013 10:45 am

One more thing. In cpPolyShapeNearestPointQuery I think having two loops, by verts and then by planes, is better than one. Less cache misses, especially with lots of vertexes.
tomeksowi
 
Posts: 8
Joined: Sun Jul 07, 2013 9:40 am

Re: Storage of vertexes and planes in cpPolyShape

Postby slembcke » Sun Jul 07, 2013 10:44 pm

So I used to have 4 allocated arrays (which was a little wasteful), and combined them into two. I also at the same time hacked up an implementation of the variable length array like you were saying. It had zero measurable effect on the performance, and made a small mess of the code. I decided to stick with the 2 array version. In the 6.2 branch of the code, the axis aren't used for collision detection anymore and I'm probably going to remove them anyway. I need to extend the poly point/segment to respect polygon beveling radius anyway, so they have some rewriting in their future.

I sort of doubt that running the loops separately will affect the cache usage. Unless you have a polygon with a thousand vertexes, you aren't going to run over the several KB of L1 cache that most CPUs have. Changing to an interleaved array might help *slightly*. Though point queries are one of the very last features that I worry about the performance of. They are relatively rare to perform, and already just a simple O(n) search.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Storage of vertexes and planes in cpPolyShape

Postby tomeksowi » Mon Jul 08, 2013 5:33 am

Thanks for the answer. Good to hear you're exploring options for speed-ups.

As for cpPolyShapeNearestPointQuery, cache locality isn't the only gain of separate loops -- you can break out of the planes loop once you know you're outside. It's true that queries don't weigh much overall, but who could resist snipping off some cycles:)
tomeksowi
 
Posts: 8
Joined: Sun Jul 07, 2013 9:40 am


Return to Features/Development

Who is online

Users browsing this forum: No registered users and 2 guests

cron