[ConditionalEuclideanClustering::segment] std::(multi)thread (only) 21-46% faster on non organzied clouds, much faster appearantly on organized clouds

Open
#5,710 29 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 3 days

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
20/100
Issue type
Feature
Clarity
Needs clarification
Activity status
Stale
Tech stack
cpp

Research direction

Start with ConditionalEuclideanClustering::segment and review the multithreaded implementation on the attemptConditionalEuclideanMT fork branch. Reproduce the four benchmark settings described in the issue and compare the threading approaches; the issue does not define a specific accepted change or completion criterion.

Written by the indexing model from the issue text.

Description

status: triage

I have implemented a std multithread version of ConditionalEuclideanClustering::segment and called it
void
segmentMT (IndicesClusters &clusters, const size_t threadNumber=2);
on my fork branch attemptConditionalEuclideanMT
on my PC it improves of only 21-38% the time to produce the results using 3 or 4 threads
12th Gen Intel(R) Core(TM) i7-12700 2.10 GHz
20 Logical CPUs - 32.0 GB
Windows 10 Pro

Setting1:
cloud is dense and NOT organized and has 2 million points XYZRGB
so the search used is pcl::search::OrganizedNeighbor
which takes 350 msec just to execute searcher_->setInputCloud
11 clusters are segmented

5 threads: 2.1-2.3 sexc
4 threads: 1.9-2.2 sec
3 threads: 1.8-2 sec
2 threads: 2.1 sec
1 thread: 2.4sec
21% improvement

Setting2:
cloud is dense and NOT organized and has 300 000 points XYZRGB
3 threads: 268-295 msec
1 thread: 420msec
4 clusters are found
32% improvement

Setting3:
cloud is NOT dense and NOT organized and has 485 000 points XYZRGB
3 threads: 480-500 msec
1 thread: 790msec
1 clusters is found
38% improvement

Setting 4: like Setting 1 but running on a different computer, a laptop less stable (less reliable for benchmark) because with heavy sw running in background:
4 threads: 2.9-3.4 sec
1 thread: 5.6-6.1 sec
46% improvement

I am still investigating the reasons for this limited improvement. On a first analysis the main reason could be that the algorithm is intinsecally not much parallelizable. I can split in parallel the growing of the clusters by splitting the point sequence in subsequences, but then at the end I have to reconnect the clusters that have grown separately in different threads ( I record the connections to be made at the end)

you can check I have quite optimized the critical scetions using also shared_mutexes

still I think it would be an interesting alternative to openMP or CUDA also for other tools/features that like this one do not look feasible for openMP or CUDA

I have tried 3 versions one with a searcher for each thread, one with a unique searcher prpeared by the main thread and one with a unique searcher prepared by the first launched thread. The latter would be faster but once in a while it gets much slower, probably because I had to implement it with a std::condition_variable that when triggered probably it slows down the thread pool. So in the end I opted for the 2nd solution (no std::condition_variable)

Dominant language
C++
Stars
11.2k
Forks
4.7k
Avg merge
6d 13h
Merged PRs (30d)
10

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from PointCloudLibrary/pcl

All issues in PointCloudLibrary/pcl

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.