Bounding volume hierarchy

I'm building a bounding volume hierarchy in Golang. I can tell my code works because I did some test on it and it gives the same results as the brute force implementation (brute force is to test all possibilities, in \$O(n^2)\$).

My problem is that the code is slower than the brute force implementation (not by that much but enough to make me wonder why I bothered to implement this in the first place). Maybe that's normal, but I would like the opinion of my peers on this.

For those who don't know Golang but would still like to take a look. a chan is a primitive to send/receive messages from other threads (we call thread, goroutine in Go). If I have c <- m that means "send this message via this channel". Both the brute force and the BVH use this primitive so thats probably not the reason for the slowdown.

```
package tornago

// this line makes sure that *BVHNode is a valid Broadphase
var _ Broadphase = (*BVHNode)(nil)

// BVHNode represents a single node in a bounding volume hierarchy.
type BVHNode struct {
children [2]*BVHNode
parent *BVHNode
BoundingSphere
body *RigidBody
}

// NewBVHNode returns a new bvh node. Use this to start a bvh tree.
func NewBVHNode(b RigidBody, volume BoundingSphere) BVHNode {
return BVHNode{
body: b,
BoundingSphere: *volume,
}
}

// IsLeaf returns true if this node has no children.
func (n *BVHNode) IsLeaf() bool {
return n.body != nil
}

// GeneratePotentialContacts sends all colliding bounding sphere to the narrow
// phase detector.
func (n *BVHNode) GeneratePotentialContacts(narrowPhaseDetector chan<- PotentialContact) {
if n.IsLeaf() {
return
}
n.children[0].GeneratePotentialContactsWith(n.children[1], narrowPhaseDetector)
}

// GeneratePotentialContactsWith accepts a second node with a bounding volume to
// test against.
func (n BVHNode) GeneratePotentialContactsWith(o BVHNode, narrowPhaseDetector chan<- PotentialContact) {
//df("inspecting %

Since you say this method is slower than the (also not shown) O(n^2) brute force mechanism, I can only assume that you mean for any n.

This implies that your new algorithm is also an O(n^2) algorithm. In fact you can see in GeneratePotentialContactsWith that this is at least a O(ln(n)) function since it appears to use tree recursion; it may be an O(n) function - it's not clear to me.

You don't show your NewBoundingSphereFromSpheres function, does this recurse too? (giving another O(ln(n)) / O(n) function)

If GeneratePotentialContactsWith or NewBoundingSphereFromSpheres is an O(n) function then processing n points will yield an O(n^2) algorithm.

Note that if you want maximum performance for a given algorithm then avoid using channels. They are much much slower than function calls. Looping recursion is also significantly faster than function recursion since it avoids stack allocation and per function initialisation & exit overhead. Channels allow elegant concurrency but just make sure you are maximising the amount of productive work and minimising the amount of the channel concurrency golang runtime work that is being invisibly performed.

StackExchange Code Review Q#102194, answer score: 4