search

Bersaelor / KDTree

Swift implementation of a k-dimensional binary space partitioning tree.
MIT License
155 stars 27 forks source link

Performance improvement #49

Closed peteraisher closed 5 years ago

peteraisher commented 5 years ago

Use UnsafeMutablePointer instead of ArraySlice during KDTree.init.

Performance improvement of approximately 4x for tree build.

Performance comparison Array vs UnsafeMutablePointer
Bersaelor commented 5 years ago

Wow, those are impressive results!

We are going down to c-level arrays during the tree creation though, which does add a higher barrier for people trying to understand the codebase.
I started programming in C , so it I'm into it, but give me a day to think about the larger picture ?

( @hsnetzer what is your opinion? Or @chriseidhof if you read this)

peteraisher commented 5 years ago

If readability/understandability is important, I imagine it would be possible to wrap the scary bits of the UnsafeMutablePointer code into a custom struct (say FastArray) that behaves exactly like ArraySlice for the methods that are actually called during tree building. That ought to retain (most of) the performance advantage of using pointers without sacrificing code readability.

After all, ArraySlice is already a little confusing (and un-Swift-y) to the uninitiated, being non-zero-indexed, not owning it’s own memory, etc.

chriseidhof commented 5 years ago

To me, it seems like it isn't a huge change in code, and if well documented, it might actually be very useful for people when reading the code. It's not an uncommon thing to resort to UnsafeMutablePointer when you need performance. I also like that it's self-contained (not exposed to the user).

hsnetzer commented 5 years ago

I agree that the current use of ArraySlice and inout isn't the Swiftiest thing. UnsafeMutablePointer actually makes the code a bit more concise and consistent. I don't think public init(values: ArraySlice<Element> is needed anymore if we go this way.

I tested UnsafeMutablePointer against just using inout [Element] and UnsafeMutablePointer is 3x faster. What makes it so fast?

Bersaelor commented 5 years ago

Thanks for your replies, I agree.

@peteraisher : @hsnetzer is correct, we can probably remove public init(values: ArraySlice<Element> as part of this PR.

Bersaelor commented 5 years ago

I tested UnsafeMutablePointer against just using inout [Element] and UnsafeMutablePointer is 3x faster. What makes it so fast?

That probably has to do with the way Swift Arrays are implemented. If the element is pretty small (like < 8 Byte, but I don't know the specific number), then the elements will be stored inline similar to a C array. If the elements are larger they are stored separately, and the only thing stored in the Swift Array is a pointer to the value that is stored somewhere else. In our case our KDTreePoints can get pretty big and therefore the Swift arrays has pretty bad memory access pattern. Compared to the plain UnsafeMutablePointer which has a linear storage of positions in RAM. I remember a WWDC lecture with pretty graphs about this (maybe this one but probably it was a year before that ).

Anyway, gtm!