# Using NearestFunction in ParallelMap: why the slowdown?

## Intro

I am trying to do various calculations (call some Analyze[point, neighbourhood] function) over the large datasets of points in 2D space. The nature of the calculations is irrelevant, but basic scenario is this:

• for each point we get all the neighbours within a certain window around it;
• apply the Analyze[...] function to the list of the neighbours.

I use Nearest[...] to generate NearestFunction, which I then apply to each point as needed to obtain list of neighbours.

## The problem

The issue is that I cannot parallelise it automatically. An example is below, with Analyze[...] reproducing the work of native MeanShift[...]:

data = RandomReal[{0, 1}, {10000, 2}];

AbsoluteTiming[
nf = Nearest[data]
]

Print["Native MeanShift[...]:"]
AbsoluteTiming[a = MeanShift[data, 0.1]; Short[a]]
Print["Serial Map of custom meanshift:"]
AbsoluteTiming[b = Map[Mean[nf[#, {All, 0.1}]] &, data]; Short[b]]
Print["ParallelMap of custom meanshift:"]
AbsoluteTiming[c = ParallelMap[Mean[nf[#, {All, 0.1}]] &, data];Short[c]]

Chop[a - b] // Norm
Chop[a - c] // Norm

"Native MeanShift[...]:"
Out= {0.196895,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

"Serial Map of custom meanshift:"
Out= {0.316036,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

"ParallelMap of custom meanshift:"
Out= {2.45064,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

Out= 0
Out= 0


## Question

As you can see, the ParallelMap is slower than serial execution. Why? What are the actual guts of the NearestFunction[...] that in ParallelMap version it experiences a slowdown?

I'm guessing there might be some access conflicts, with different parallel kernels using their own automatically distributed copies of index function (if that what NearestFunction[...] is) but trying to access the global data list simultaneously.

If that's the case, what is the workaround – distribute the data itself and create nearest function within each parallel kernel?

• It might be faster if you use DistributeDefinitions on the NerestFunction. Also granularity matters here. If you divvy the data into chunks you might get improvment. But best is probably to take advantage of listability and do Mean[nf[data, {All, 0.1}]] . Under the hood the NearstFunction will use parallel mapping I believe. – Daniel Lichtblau Jul 9 '17 at 14:48
• Note that MeanShift is already parallelized (via the Math Kernel Library, probably). – Michael E2 Jul 9 '17 at 20:41