Colliders slow for crowds?

I have 800 boids with SphereColliders on them. I use them to determine neighbor boids for each bird. At the beginning when the boids are close to each other I get lots of collisions and my frame rate drops to 5fps. But when they spread my frame rate jumps to 20fps.

Why the speed difference is so high? Is there some internal Unity/PhysX messaging that is so expensive? I don't do anything on OnTriggerEnter (yet) but obviously physics engine has to check for collisions between all the colliders every frame because I make them kinematic and animate them by myself.

The physics engine can accelerate the check whether objects do collide by checking whether the bounding boxes collide. This is very fast. Example of what the engine is probably doing:

BAD implementation would be:

// Checking for sphere collisions
if((a.position - b.position).magnitude < (a.radius + b.radius))
{
  // the spheres collide
}

GOOD implementation would be:

var dist = a.radius + b.radius;
// first checking for bounding box collisions
if
(
  (Mathf.Abs(a.position.x - b.position.x) < dist) &&
  (Mathf.Abs(a.position.y - b.position.y) < dist) &&
  (Mathf.Abs(a.position.z - b.position.z) < dist) &&
  ((a.position - b.position).magnitude < (a.radius + b.radius))
)
{
  // there spheres collide
}

The second thing is incredibly faster, because it will stop checking when the first condition evaluates to "false" and only do the (slower) full check if all the other conditions meet. For example: `A` is far left from `B`, so there is no need to calculate the distance of them - you already know they don't collide.

But if all objects are close to each other, the full test has to be made, and this will really slow down - you notice it by the frame rate drop.