[BUG] Hashing function causing slow insert for SPH grid

[dsfenn]

Summary

The provided CoordHash for hashing ChVector3i arrays causes large slowdowns when dealing with a large number of particles. Improving the hashing function reduces execution time by over a factor of 1000x on my system.

Chrono Version and Platform

RHEL 9
Chrono hash: 6cdcdbc
CPU: i9-14900K
CPU cores: 32
RAM: 92 GB

Expected Behavior

The SPH particle domain should be constructed with reasonable overhead.

Actual Behavior

As the number of particles grows, the overhead for insertion into the grid becomes very high. On my system, a domain of 75 million SPH particles takes ~7 hours just to initialize.

I was able to ameliorate this by redefining the hashing function like this:

static inline std::uint64_t mix64(std::uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    struct CoordHash {
        std::size_t operator()(const ChVector3i& p) const noexcept {
            // Pack the three ints into 64-bit lanes; mix each, then combine.
            std::uint64_t x = static_cast<std::uint32_t>(p.x());
            std::uint64_t y = static_cast<std::uint32_t>(p.y());
            std::uint64_t z = static_cast<std::uint32_t>(p.z());
            std::uint64_t h = mix64(x);
            h ^= mix64(y) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
            h ^= mix64(z) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
            return static_cast<std::size_t>(h);
        }
    };

I additionally modified ChFsiProblemCartesian::Construct() with the following:

m_sph.max_load_factor(0.5f);
m_sph.reserve(num_sph);

I'm not sure if it's good to use a max load factor of 0.5 in general, but that's what I tested with. With these changes, initialization time was reduced to less than 20 s for the same problem.

Steps to Reproduce

Set up an SPH simulation with a large number of particles. I specifically used the test rig, with a particle spacing of 0.003 m.

Further Information, Files, and Links

[rserban]

@dsfenn - thank you for posting this. I got a chance to look into this a bit more carefully today.

I have to say that I have been seeing very different results on different systems (VS on Windows and GCC on Linux) with different hardware (CPU and GPU). The most baffling thing is that the original implementation (no reserve for the unordered maps and the old hash function) is significantly faster on my Windows machine than on Linux! I don't have an explanation for that yet.

Having said that, I see good performance boosts on both systems with the changes you suggested. As such, I adopted and pushed them. The new code is in the feature/fsi branch, where I also added a simple test program (btest_FSI_Initialization; you need to enable BUILD_BENCHMARKING during configuration to build that test) to measure performance of these operations. As pushed, the test creates a problem with about 8 millions SPH markers and around 850 thousand BCE markers. You can easily scale this up by increasing the fluid domain at the top of the source file.

I'd be curious to see what you get on our system with this test.

(I will merge that feature branch into main in a few days)

[dsfenn]

Interesting that you get such different results on different systems. My guess is that the slowdowns are coming from hash collisions, and I wonder if the VS implementation handles those collisions more effectively than gcc.

I ran the benchmark on my RHEL 9 system, compiled with GCC, and here are the results:

ChFsiProblemSPH::Construct():  1.03981
ChFsiProblemSPH::Initialize(): 0.809512
Total initialization time:     1.84933

Num. SPH particles: 8120601
Num. BCE markers:   847124

Computational domain:
   min: -0.54  -0.54  -0.04
   max: 0.54  0.54  1.04

Is this comparable to what you see? Also, after these updates, are the VS and gcc initialization times similar?

[rserban]

It's difficult to compare these numbers across different machines, as they depend on CPU, RAM, and GPU.

My windows machine has an older Ryzen 7 3700 processor, only 16 GB RAM and a GeForce RTX 2060 GPU (8 GB memory):

ChFsiProblemSPH::Construct():  2.05485
ChFsiProblemSPH::Initialize(): 2.22897
Total initialization time:     4.28384

I'm about to upgrade the processor to a Ryzen 9 5950X and add 32GB of RAM. It will be interesting to see how these numbers change (probably not the Initialize() time since that likely depends more on the GPU).

My Linux laptop has a faster processor (Ryzen 9 8945 and 32GB RAM), but a GeForce RTX 4070 mobile with only 8GB memory:

ChFsiProblemSPH::Construct():  1.86696
ChFsiProblemSPH::Initialize(): 3.1515
Total initialization time:     5.01847

Both machines less performant than yours (although you never mentioned what GPU you have). I think the numbers are consistent with hardware.

[dsfenn]

My GPU is an RTX 4090 with 24 GB memory, which seems right in line for these results being consistent with hardware.

Thanks for getting this fix in the code