Since # particles is usually >> # cells, it is a huge performance bottleneck to acquire/release the lock once for each particle.

Another option seems to be trying to make thread safe lists. If we can append to a list in an atomic way, then we don't need locks and this approach would work fine. It seems like this is possible to implement! See: https://stackoverflow.com/questions/24563000/concurrently-appending-to-list-tail-without-a-mutex-lock. I wonder how the performance of this compares to the other methods in practice.

The major concern in this implementation is that we lock for every particle p, which reduces our throughput by a lot since we're taking more time.

Looking back at this comment, I just wanted to finish the thought by saying we take more time because of the overhead incurred by locking and unlocking locks repeatedly.