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...
Storage of vertexes and planes in cpPolyShape
-
- Posts: 8
- Joined: Sun Jul 07, 2013 9:40 am
- Contact:
-
- Posts: 8
- Joined: Sun Jul 07, 2013 9:40 am
- Contact:
Re: Storage of vertexes and planes in cpPolyShape
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.
- slembcke
- Site Admin
- Posts: 4166
- Joined: Tue Aug 14, 2007 7:13 pm
- Contact:
Re: Storage of vertexes and planes in cpPolyShape
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.
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/
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
-
- Posts: 8
- Joined: Sun Jul 07, 2013 9:40 am
- Contact:
Re: Storage of vertexes and planes in cpPolyShape
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:)
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:)
Who is online
Users browsing this forum: No registered users and 18 guests