Why Is My Spatial Hash So Slow?

Question

Why is my spatial hash so slow? I am working on a code that uses smooth particle hydrodynamics to model the movement of landslides. In smooth particle hydrodynamics each particle influences the particles that are within a distance of 3 "smoothing lengths". I am trying to implement a spatial hash function in order to have a fast look up of the neighboring particles.

For my implementation I made use of the "set" datatype from the stl. At each time step the particles are hashed into their bucket using the function below. "bucket" is a vector of sets, with one set for each grid cell (the spatial domain is limited). Each particle is identified by an integer.

To look for collisions the function below entitled "getSurroundingParticles" is used which takes an integer (corresponding to a particle) and returns a set that contains all the grid cells that are within 3 support lengths of the particle.

The problem is that this implementation is really slow, slower even than just checking each particle against every other particles, when the number of particles is 2000. I was hoping that someone could spot a glaring problem in my implementation that I'm not seeing.

//put each particle into its bucket(s)
void hashParticles()
{
    int grid_cell0;

    cellsWithParticles.clear();

    for(int i = 0; i<N; i++)
    {
        //determine the four grid cells that surround the particle, as well as the grid cell that the particle occupies
        //using the hash function int grid_cell = ( floor(x/cell size) ) + ( floor(y/cell size) )*width
        grid_cell0 = ( floor( (Xnew[i])/cell_spacing) ) + ( floor(Ynew[i]/cell_spacing) )*cell_width;

        //keep track of cells with particles, cellsWithParticles is an unordered set so duplicates will automatically be deleted
        cellsWithParticles.insert(grid_cell0);


        //since each of the hash buckets is an unordered set any duplicates will be deleted
        buckets[grid_cell0].insert(i); 

    }
}

set<int> getSurroundingParticles(int particleOfInterest)
{
     set<int> surroundingParticles;
     int numSurrounding;
     float divisor = (support_length/cell_spacing);
     numSurrounding = ceil( divisor );
     int grid_cell;

     for(int i = -numSurrounding; i <= numSurrounding; i++)
     {
         for(int j = -numSurrounding; j <= numSurrounding; j++)
         {
             grid_cell = (int)( floor( ((Xnew[particleOfInterest])+j*cell_spacing)/cell_spacing) ) + ( floor((Ynew[particleOfInterest]+i*cell_spacing)/cell_spacing) )*cell_width;
             surroundingParticles.insert(buckets[grid_cell].begin(),buckets[grid_cell].end());
         }
     }
    return surroundingParticles;
}

The code that looks calls getSurroundingParticles:

set<int> nearbyParticles;
//for each bucket with particles in it
for ( int i = 0; i < N; i++ )
 {
     nearbyParticles = getSurroundingParticles(i);
    //for each particle in the bucket

    for ( std::set<int>::iterator ipoint = nearbyParticles.begin(); ipoint != nearbyParticles.end(); ++ipoint )
    {
        //do stuff to check if the smaller subset of particles collide
    }
}

Thanks a lot!

Answer 1

Your performance is getting eaten alive by the sheer amount of stl heap allocations caused by repeatedly creating and populating all those Sets. If you profiled the code (say with a quick and easy non-instrumenting tool like Sleepy), I'm certain you'd find that to be the case. You're using Sets to avoid having a given particle added to a bucket more than once - I get that. If Duck's suggestion doesn't give you what you need, I think you could dramatically improve performance by using preallocated arrays or vectors, and getting uniqueness in those containers by adding an "added" flag to the particle that gets set when the item is added. Then just check that flag before adding, and be sure to clear the flags before the next cycle. (If the number of particles is constant, you can do this extremely efficiently with a preallocated array dedicated to storing the flags, then memsetting to 0 at the end of the frame.)

That's the basic idea. If you decide to go this route and get stuck somewhere, I'll help you work out the details.