# \[ANN\] CellListMap.jl: short-ranged particle pairwise computations (lennard-jones, gravitational, etc)

**URL:** <https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585>\
**Category:** Package Announcements\
**Created:** [June 8, 2021, 3:09pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585 "2021-06-08T15:09:57Z")\
**Posts on this page:** 19\
**Page:** 2

<div class="post-metadata">

**Author:** ![cortner](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cortner/32/204_2.png) [@cortner](https://discourse.julialang.org/u/cortner)\
**Post date:** [August 8, 2021, 7:43pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/21 "2021-08-08T19:43:18Z")

</div>

Cf JuliaMolSim activities - please join the slack if you haven’t yet!

[https://juliamolsim.github.io/](https://juliamolsim.github.io/)

---

<div class="post-metadata">

**Author:** ![cortner](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cortner/32/204_2.png) [@cortner](https://discourse.julialang.org/u/cortner)\
**Post date:** [August 8, 2021, 7:45pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/22 "2021-08-08T19:45:01Z")

</div>

Since this is not an urgent transition fir me I will wait until the community has agreed on an abstract interface for Atoms and Structures at which point I will retire about half to 2/3 of JuLIP including the neighbour lists and much of the structure management and focus just in potentials again.

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 8, 2021, 9:02pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/23 "2021-08-08T21:02:29Z")

</div>

@lmiq thanks for taking time to write this package.

Looks very interesting to test this using SPH too 🙂

I have one question though, is the goal of the package you are making to be able to perform molecular simulations or is it simply to be able to generate neighbour lists?

Kind regards

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 8, 2021, 9:12pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/24 "2021-08-08T21:12:29Z")

</div>

Actually the goal is the computation of the objective function and gradient for Packmol. That is closer to what is needed for a MD simulation than for neighbor lists. My comparison there is just because that was a good package to compare with.

Ps. What is SPH?

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 8, 2021, 9:18pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/25 "2021-08-08T21:18:42Z")

</div>

Ah I see.

SPH stands for Smoothed Particle Hydrodynamics, which is a numerical particle simulation method. Can be used in different fields, I mostly use it in fluid dynamics. Has some similarities to molecular dynamics I suppose, but in SPH we solve the Navier-Stokes equation for each particle to model flow fields, pressure, forces on objects etc.

Nice visualization here

[![](https://global.discourse-cdn.com/julialang/original/3X/1/2/12f8f74d39a8916693b14f4e8e90efef2c080fa6.jpeg "DualSPHysics example: CaseWaterMill") ](https://www.youtube.com/watch?v=nwPsYJdx7J0)

Kind regards

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 8, 2021, 9:52pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/26 "2021-08-08T21:52:06Z")

</div>

I guess it could be used for that, if those simulations require the computation of interactions within a cutoff.

---

<div class="post-metadata">

**Author:** ![yewalenikhil65](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yewalenikhil65/32/26873_2.png) [@yewalenikhil65](https://discourse.julialang.org/u/yewalenikhil65)\
**Post date:** [September 11, 2021, 6:09am UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/27 "2021-09-11T06:09:56Z")

</div>

@lmiq  
There is a similar package called CellLists.jl

[https://github.com/jaantollander/CellLists.jl](https://github.com/jaantollander/CellLists.jl)

It would be nice to know how CellListMap.jl is different from CellLists.jl in terms of performance !

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 11, 2021, 11:29am UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/28 "2021-09-11T11:29:01Z")

</div>

The easiest comparison is probably with the neighbour lists functions of both packages:

```julia
julia> using CellListMap

julia> import CellLists

julia> n, d, r = 10_000, 3, 10.; p = 100*rand(n,d);

julia> using BenchmarkTools

julia> @btime let p = $p, r = $r
          c = CellLists.CellList(p, r)
          CellLists.near_neighbors(c,p,r)
       end
  114.365 ms (3387927 allocations: 361.06 MiB)
186283-element Vector{Tuple{Int64, Int64}}:
 (2190, 3458)
 (2190, 3516)
⋮
 (9932, 2019)
 (9932, 9024)

julia> x = [p[i,:] for i in 1:n ];

julia> @btime CellListMap.neighbourlist($x,10,parallel=false)
  11.073 ms (4979 allocations: 8.97 MiB)
186283-element Vector{Tuple{Int64, Int64, Float64}}:
 (1, 383, 8.399067107896867)
 (1, 1316, 9.936877451715944)
 ⋮
 (9755, 7861, 8.58091039978657)
 (9755, 8268, 9.898527922742463)

julia> @btime CellListMap.neighbourlist($x,10,parallel=true)
  5.533 ms (5288 allocations: 19.61 MiB)
186283-element Vector{Tuple{Int64, Int64, Float64}}:
 (1, 383, 8.399067107896867)
 (1, 1316, 9.936877451715944)
 ⋮
 (9755, 7861, 8.58091039978657)
 (9755, 8268, 9.898527922742463)

julia> Threads.nthreads()
4

```

---

<div class="post-metadata">

**Author:** ![yewalenikhil65](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yewalenikhil65/32/26873_2.png) [@yewalenikhil65](https://discourse.julialang.org/u/yewalenikhil65)\
**Post date:** [September 11, 2021, 11:57am UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/29 "2021-09-11T11:57:38Z")

</div>

That sounds like a huge speed up with CellListMap.jl  
Does CellListMap use bucketing approach also?? Means only searching for cells with indices with indices more than current index?  
[http://efekarakus.github.io/fixed-radius-near-neighbor/](http://efekarakus.github.io/fixed-radius-near-neighbor/)  
I think this might give additional performance

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 11, 2021, 4:53pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/30 "2021-09-11T16:53:31Z")

</div>

> [@yewalenikhil65](#):
>
> Does CellListMap use bucketing approach also?? Means only searching for cells with indices with indices more than current index?

Yes, it does for orthorhombic cells. For general triclinic cells it does not (yet?), it is a little bit trickier in that case. Indeed it can result in an almost 2x speedup (the inputs below are artificial in terms of the interface, just to force the cell type in the example):

```julia
julia> @btime let x = $x
           box = Box(limits(x).limits .+ 10,10, UnitCellType=TriclinicCell)
           cl = CellList(x,box,parallel=false)
           CellListMap.neighbourlist(box,cl,parallel=false)
       end;
  17.324 ms (4976 allocations: 8.97 MiB)

julia> @btime let x = $x
           box = Box(limits(x).limits .+ 10,10, UnitCellType=OrthorhombicCell)
           cl = CellList(x,box,parallel=false)
           CellListMap.neighbourlist(box,cl,parallel=false)
       end;
  9.880 ms (4976 allocations: 8.97 MiB)

```

(edit: that is not the only difference between the algorithms, but probably the most significant one. There are other small optimizations that can be done for orthorhombic cells).

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 11, 2021, 5:16pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/31 "2021-09-11T17:16:38Z")

</div>

This is an update of the benchmark shown in the first post (which apparently cannot be edited anymore), for one recent version and also fixing the comparison with NearestNeighbours.jl, because the time of both packages if very much dependent on which set is chosen as the one for which the lists or trees will be built. In general building the list for the smallest set is the most efficient choice (which is made by default in the CellListMap.neighbourlist function).

Computing pairwise velocities of “galaxies”:

![image](https://global.discourse-cdn.com/julialang/original/3X/a/2/a20c92357d7a3d56511a73c23fa365ece4b8d61c.png)

![image](https://global.discourse-cdn.com/julialang/original/3X/c/a/ca1e23239a3357ce4886db87fb8802b403568be3.png)

In-range neighbour search (the fastest of the two options of which set is used to build the list is shown. Parallelization with 4 physical cores - 8 threads; nl: NearestNeighbour.jl `inrange` function; cl: `CellListMap.neighbourlist` function):

```julia
----------------------------------
N1 = 1 ; N2 = 1000000 ; PASS TEST = true
nl (x,y): 102.679 ms (1000761 allocations: 83.96 MiB)
cl serial (y,x): 133.007 ms (39 allocations: 23.01 MiB)
cl parallel (y,x): 54.008 ms (98 allocations: 23.05 MiB)
----------------------------------
N1 = 10 ; N2 = 1000000 ; PASS TEST = true
nl (x,y): 146.351 ms (1006920 allocations: 84.24 MiB)
cl serial (y,x): 131.896 ms (68 allocations: 23.34 MiB)
cl parallel (y,x): 67.706 ms (136 allocations: 23.63 MiB)
----------------------------------
N1 = 100 ; N2 = 1000000 ; PASS TEST = true
nl (x,y): 294.152 ms (1064619 allocations: 86.89 MiB)
cl serial (y,x): 139.902 ms (288 allocations: 27.51 MiB)
cl parallel (y,x): 58.175 ms (369 allocations: 32.01 MiB)
----------------------------------
N1 = 1000 ; N2 = 1000000 ; PASS TEST = true
nl (x,y): 831.164 ms (1491040 allocations: 106.46 MiB)
cl serial (y,x): 259.863 ms (2216 allocations: 49.02 MiB)
cl parallel (y,x): 100.269 ms (2322 allocations: 71.60 MiB)
----------------------------------
N1 = 10000 ; N2 = 1000000 ; PASS TEST = true
nl (x,y): 2.318 s (3027684 allocations: 224.04 MiB)
cl serial (x,y): 761.103 ms (59024 allocations: 305.87 MiB)
cl parallel (x,y): 539.894 ms (59172 allocations: 454.62 MiB)
----------------------------------
N1 = 100000 ; N2 = 1000000 ; PASS TEST = true
nl (y,x): 6.452 s (987257 allocations: 1.51 GiB)
cl serial (x,y): 7.514 s (69905 allocations: 1.55 GiB)
cl parallel (x,y): 4.441 s (70059 allocations: 3.16 GiB)
----------------------------------

```

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [September 11, 2021, 7:12pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/32 "2021-09-11T19:12:01Z")

</div>

Out of curiosity, do you believe it would be hard to apply the same algorithm you are using now on GPU?

Kind regards

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 11, 2021, 7:33pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/33 "2021-09-11T19:33:50Z")

</div>

I think it is doable, and it is on my plans. But I don’t have much experience porting things to GPUs, so I cannot wright now anticipate how much work is needed to do that effectively. (MD codes run on GPUs well, so one way or the other that has to be possible)

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [September 11, 2021, 7:41pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/34 "2021-09-11T19:41:15Z")

</div>

I see thanks for the comment, very interesting. I once tried to write some simulation code with the idea of being able to use the same code for cpu and gpu, but I really struggled with it. Just wanted to hear about others experience.

Still, very impressive what CellListsMap is able to do right now!

Kind regards

---

<div class="post-metadata">

**Author:** ![jgreener64](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jgreener64/32/2483_2.png) [@jgreener64](https://discourse.julialang.org/u/jgreener64)\
**Post date:** [October 21, 2021, 11:03am UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/35 "2021-10-21T11:03:05Z")

</div>

Here’s a snapshot of a simulation using Molly.jl with CellListMap.jl used to obtain neighbour lists.

It’s the designed protein Foldit1 (PDB ID 6MRR) in the a99SB-ILDN force field with explicit solvent (not shown).

![movie](https://global.discourse-cdn.com/julialang/original/3X/d/5/d5082769f52f1eda3d93141d24640d340ebd5f65.gif)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [October 21, 2021, 12:36pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/36 "2021-10-21T12:36:52Z")

</div>

👏 👏 👏

Thanks for sharing! If you don’t mind I will add that to the showcase in CellListMap 🙂

One curiosity: do you have already a good PME implementation to deal with the long-range electrostatics? I searched some time ago but there didn’t seem to be a package available for that yet, and I was wandering if it was the case of implementing one.

---

<div class="post-metadata">

**Author:** ![jgreener64](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jgreener64/32/2483_2.png) [@jgreener64](https://discourse.julialang.org/u/jgreener64)\
**Post date:** [October 21, 2021, 12:46pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/37 "2021-10-21T12:46:54Z")

</div>

> [@lmiq](#):
>
> If you don’t mind I will add that to the showcase in CellListMap

Yes sounds good!

> [@lmiq](#):
>
> do you have already a good PME implementation to deal with the long-range electrostatics?

No not yet, I am using the reaction field approximation for this example. I think it’s a case of implementing it, see some discussion at [Electrostatics in Julia](https://discourse.julialang.org/t/electrostatics-in-julia/41633).

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [June 23, 2022, 9:09pm UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/38 "2022-06-23T21:09:45Z")

</div>

I am happy to announce that the article describing this package is now published, and available for free access for 50 days here:

[CellListMap.jl: Efficient and customizable cell list implementation for calculation of pairwise particle properties within a cutof](https://authors.elsevier.com/a/1fHy52OInkASk). Computer Physics Communications, Volume 279, October 2022, 108452.

The pre-print is also available at arXiv, [here](https://arxiv.org/abs/2202.06427).

Associated to the paper, there are some Pluto notebooks explaining each of the examples shown at: [GitHub - m3g/CellListMapArticleCodes: Code blocks of the CellListMap paper.](https://github.com/m3g/CellListMapArticleCodes).

One more time, I feel obliged to acknowledge all the contributions from this forum (and from anonymous and not so anonymous referees of the article 🙂 ), which allowed me to develop this and other Julia tools. It has been a very productive and exciting programming journey.

---

<div class="post-metadata">

**Author:** ![liuyxpp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/liuyxpp/32/9870_2.png) [@liuyxpp](https://discourse.julialang.org/u/liuyxpp)\
**Post date:** [June 24, 2022, 2:07am UTC](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585/39 "2022-06-24T02:07:34Z")

</div>

Congratulations! A very interesting and informative article to read.

[Previous page](https://discourse.julialang.org/t/ann-celllistmap-jl-short-ranged-particle-pairwise-computations-lennard-jones-gravitational-etc/62585.md?page=1)