Should nested strategy not be faster than concurrent files strategy for parallelization?

[wiesehahn]

You state that the nested strategy "is the fastest option", but in my understanding the consurrent file strategy should be at least as fast when some stages are also parallelized. Do I misunderstand this or is this left from a documentation prior to concurrent strategy?

Btw., there is a typo under concurrent file stragety vignette, its written as set_parallel_strategy(conccurent_files(4)) instead of concurrent_files()

[Jean-Romain]

The documentation states:

concurrent-files is likely the most desirable and fastest option.

If I wrote something different somewhere, please let me know.

Nested strategy may or may not be faster. Parallelism is a complex topic and the answer is usually: benchmark it. We are currently running some benchmark but right now I do not know if nested strategy brings significant improvement. Basically, you can see the code of lasR as something like:

for (file in files)
{
   # stage 1
   for (point in points)
   {
   }

   # stage 2
   for (point in points)
   {
   }

   ...
}

The outer loop is parallelized. Some inner loops are parallelized. concurrent-files is the outer loop. concurrent-points is the inner loops (those parallelized) . Nested is to get both parallelized. Is it faster? Not necessarily, especially there is no control internally to prevent users to do stupid things like nested(20,20) with 20 cores available.

My prediction is: no significant improvement. The gain at parallelizing the full pipeline on 4 cores is much more significant than the gain at parallelizing 1 stages on 10 cores. Especially decompressing and reading 4 LAZ files simultaneously in a game changer compared to computing e.g. 10 pixels simultaneously in a rasterization for example.

If you find something drastically different from my prediction (in good or bad), please let me know. The stages that are parallelized are: rasterize with a triangulation and with internal metrics, local_maximum, geometry_features (devel branch), transform_with with a triangulation.

What I can tell is that concurrent-files is a great improvement globally. concurrent-files is a great improvement locally if you have a single file and can't use concurrent-files and your pipeline implies computationally intensive stages. nested exist because the loops are already parallelized, and it requires not additional effort to implement, but should be benchmarked because parallelization is not a magic trick the makes everything faster for free.

[wiesehahn]

The documentation states:

concurrent-files is likely the most desirable and fastest option.

If I wrote something different somewhere, please let me know.

I quoted from https://r-lidar.github.io/lasR/articles/multithreading.html#concurrent-files-strategy, where you wrote:

With modern and fast SSD disks and a significant amount of RAM, this is the fastest option.

Nested strategy may or may not be faster. Parallelism is a complex topic and the answer is usually: benchmark it. We are currently running some benchmark but right now I do not know if nested strategy brings significant improvement.

The outer loop is parallelized. Some inner loops are parallelized. concurrent_file is the outer loop. concurrent_points is the inner loops (those parallelized) . Nested is to get both parallelized. Is it faster? Not necessarily

So if we are using the same number of cores for the outer loop to parallelize on files (e.g. conccurent_files(4) and nested(4, 2)) nested processing should be as fast as concurrent processing if no stages are parallelizable, but it should be faster if parallelizable stages are processed. On the other hand concurrent processing would be faster in the first case if we initially assign all 6 available cores to conccurent_files(6).
Is this more or less correct? (I dont want to bother you with this, actually its not that important to me atm, but I am just trying to sort my thoughts)

[Jean-Romain]

should be as fast as concurrent processing if no stages are parallelizable

Absolutely. In theory at least.

but it should be faster if parallelizable stages are processed.

Absolutely, In theory. In practice, it is hard to say and should be benchmarked. In case of nested(4,2) on a 20 cores machine I'd say yes, very likely. In case of (4,2) on a 10 cores machine, in my opinion it is not obvious at all. 4x2 = 8 cores involved. On a 10 cores machine, there is usually no significant gains after half cores. Also, you must consider the overheads, parallelization has a cost. Then you must consider how synchronized are each cores in the outer loop. Imagine stage 3 is parallelized and you are processing 4 files simultaneously. It is unlikely that the computations on each file are strictly synchronized, so the stage 3 may occur at a different moment for each file. Thus, maybe nested parallelism (4,2) requires only 4+2 = 6 cores when the pipelines are out of sync. Maybe 8 cores will be involved, who knows. And if you try nested(10,10) you need in theory 100 cores. In practice, it should work with some locking mechanism and slow down the computation. But maybe it will run faster because the pipeline are out of sync and only 20 cores will actually be necessary.

As I said, parallelism is a big topic and the good answer is always benchmark it. For concurrent-file and concurrent-point, parallelism are guaranteed to be faster but if you want to figure out how many cores perform best you must benchmark it. Usually, from my tests, half cores is the best and there is nothing to gain with more cores.

[Jean-Romain]

On the other hand concurrent processing would be faster in the first case if we initially assign all 6 available cores to conccurent_files(6).

Absolutely. If 6 cores is faster than 4 and you have enough memory. Which depends on your machine. Again: benchmark it on a subset of your dataset. On a modern computer with 12 or 20 cores, the answer is likely yes.