SpatialHashTables.jl (v0.2.0)
This package implements a cell list method via spatial hash tables in Julia.
The primary aim is to speed up computations of short-range interactions between particles in large particle systems, e.g. for terms like F_i = \sum_{j} F(X_i,X_j) for given X_1,\dots,X_n \in \mathbb{R}^d and provided that F(X_i,X_j) \approx 0 for distances larger than a cutoff radius \Vert X_i - X_j \Vert > R.
The aim is similar to that of the excellent CellListMap.jl package. (@lmiq I’m also open to merging, it was just easier to try the idea in a new package first.)
As of now, the main features of SpatialHashTables.jl are:
- Support for unbounded domains and also bounded domains,
- No allocations, neither during the update of positions nor at the iteration of all neigbours (for single-threaded code).
- Can be used on GPUs (but still a bit slow),
- Minimal but flexible interface, arbitrary dimension, fast CPU multi-threading.
- Core implementation is less than 200 lines of code (without docs).
Is it fast?
-
On bounded domains, the implemenation has comparable performance to CellListMap.jl for single-threaded calls, but
2x or more timesslower in the multi-treaded case [*], see benchmarks and lmiq’s example. -
For unbounded domains, I lack a reference to compare to, but it seems to be reasonably fast.
-
GPU performance is not optimal yet. On my system
10x slowerthan the CPU. I’m working on it
[*] Note that my current implementation visits both (i,j) and (j,i), which might cause the doubling of the runtime. This might be fixed in the future, but currently, GPU support is the main focus.
Example usage
Please check out the readme and the docs for more details.
Below, we compute F_i = \sum_{j} V(\Vert X_j - X_i \Vert) (X_j - X_i) for given points X_1,\dots,X_N \in \mathbb{R}^3 and a function V(d) = 1/d^3. Note that we only need to provide a tablesize (number of hashes) and a cellsize (defines binning of particles into cells). No domain bounds are needed, which is often convenient.
using StaticArrays, SpatialHashTables
N = 1_000_000
X = randn(SVector{3, Float64}, N)
F = zeros(SVector{3, Float64}, N)
V(d) = 1/d^3
r = 1/N^(1/3)
cellsize = 1/N^(1/3)
tablesize = 1_000_000
ht = SpatialHashTable(X, cellsize, tablesize)
Threads.@threads for i in eachindex(X)
for j in neighbours(ht, X[i], r)
d² = sum(x -> x^2, X[i] - X[j])
if 0 < d² < r^2
d = sqrt(d²)
F[i] += V(d) * (X[i] - X[j])
end
end
end
# Timing: 0.230324 seconds (190 allocations: 20.023 KiB)
I currently decided to leave the parallelization mostly up to the user to give maximal control and allow use that goes beyond energy/force computations. (E.g. collision detection). There are no helper functions such as CellListsMap.map_pairwise and also no support for periodic domains.
I hope this package is useful for the Julia ecosystem. If you have any questions or comments, please open an issue or contact me.