Concurrency problems, please help

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Concurrency problems, please help

Pierre Abbat
https://github.com/phma/wolkenbase
I just published the repo. I've been racking my brains on this problem for
months. Wolkenbase reads a point cloud and makes an octree, in order to
classify points. The basic algorithm of building the octree is sound, but
slow, so I'm trying to multithread it.

Wolkenbase has to handle point clouds that are too big to fit in RAM, so it
allocates block buffers until RAM gets low, then swaps blocks out to files. So
that it can continue putting points in the octree while writing blocks to
files, it uses more files than there are threads.

I'm testing it with a small point cloud of 250024 points, so that it doesn't
have to write to disk while it constructs the octree, but still it loses
points. I've found and fixed bugs in the splitting routine. I currently have it
checking after each point it inserts to make sure that it's in there. I've
found, and I think I fixed, a bug where one thread checked a point while
another thread was splitting the block where the point was inserted, so it
didn't find it. Now it fails to find a point, but the point is not in the block
being split. It may fail to find 24 points while it's building the octree, but
when it's finished they're all there, or it's missing one or three of them.

I have a huge point cloud (19 files, 3.5 GB total) which I've tried Wolkenbase
on, but it complains that the point is already in the octree. This turned out
to be points scattered through the cloud that have been "deleted" by
overwriting with all zeros. (0,0,0) is offset to somewhere within the cube, and
is equal to (0,0,0), so I can't rely on the point count in the dump file.

I cut it down to one thread; it works perfectly. With two threads, it works
fine, but with three, it loses points. Usually two threads are sufficient to
allow a concurrency bug to happen.

Can someone look at the program and suggest how to make it work?

Pierre
--
li ze te'a ci vu'u ci bi'e te'a mu du
li ci su'i ze te'a mu bi'e vu'u ci



_______________________________________________
Discuss mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/discuss
Reply | Threaded
Open this post in threaded view
|

Re: Concurrency problems, please help

Martin Dobias
Hi Pierre

While I don't have concrete advice for your implementation, I would
like to suggest having a look at Entwine [1] and/or PotreeConverter
[2] projects and maybe reuse their code. Both of them have only a
single task - to build an octree from potentially massive amounts of
point cloud data.

I will start working on point cloud visualization in QGIS in the
coming months and I plan to use code from one of the projects to build
octrees for efficient visualization (more details here [3]).

Regards
Martin

[1] https://github.com/connormanning/entwine
[2] https://github.com/potree/PotreeConverter
[3] https://github.com/qgis/QGIS-Enhancement-Proposals/issues/194

On Wed, Sep 23, 2020 at 3:11 AM Pierre Abbat <[hidden email]> wrote:

>
> https://github.com/phma/wolkenbase
> I just published the repo. I've been racking my brains on this problem for
> months. Wolkenbase reads a point cloud and makes an octree, in order to
> classify points. The basic algorithm of building the octree is sound, but
> slow, so I'm trying to multithread it.
>
> Wolkenbase has to handle point clouds that are too big to fit in RAM, so it
> allocates block buffers until RAM gets low, then swaps blocks out to files. So
> that it can continue putting points in the octree while writing blocks to
> files, it uses more files than there are threads.
>
> I'm testing it with a small point cloud of 250024 points, so that it doesn't
> have to write to disk while it constructs the octree, but still it loses
> points. I've found and fixed bugs in the splitting routine. I currently have it
> checking after each point it inserts to make sure that it's in there. I've
> found, and I think I fixed, a bug where one thread checked a point while
> another thread was splitting the block where the point was inserted, so it
> didn't find it. Now it fails to find a point, but the point is not in the block
> being split. It may fail to find 24 points while it's building the octree, but
> when it's finished they're all there, or it's missing one or three of them.
>
> I have a huge point cloud (19 files, 3.5 GB total) which I've tried Wolkenbase
> on, but it complains that the point is already in the octree. This turned out
> to be points scattered through the cloud that have been "deleted" by
> overwriting with all zeros. (0,0,0) is offset to somewhere within the cube, and
> is equal to (0,0,0), so I can't rely on the point count in the dump file.
>
> I cut it down to one thread; it works perfectly. With two threads, it works
> fine, but with three, it loses points. Usually two threads are sufficient to
> allow a concurrency bug to happen.
>
> Can someone look at the program and suggest how to make it work?
>
> Pierre
> --
> li ze te'a ci vu'u ci bi'e te'a mu du
> li ci su'i ze te'a mu bi'e vu'u ci
>
>
>
> _______________________________________________
> Discuss mailing list
> [hidden email]
> https://lists.osgeo.org/mailman/listinfo/discuss
_______________________________________________
Discuss mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/discuss
Reply | Threaded
Open this post in threaded view
|

Re: Concurrency problems, please help

Pierre Abbat
On Wednesday, September 23, 2020 3:31:28 AM EDT Martin Dobias wrote:
> Hi Pierre
>
> While I don't have concrete advice for your implementation, I would
> like to suggest having a look at Entwine [1] and/or PotreeConverter
> [2] projects and maybe reuse their code. Both of them have only a
> single task - to build an octree from potentially massive amounts of
> point cloud data.

Could you tell me where the octree-building code is?

Pierre

--
The Black Garden on the Mountain is not on the Black Mountain.



_______________________________________________
Discuss mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/discuss
Reply | Threaded
Open this post in threaded view
|

Re: Concurrency problems, please help

Pierre Abbat
In reply to this post by Martin Dobias
I got it working. I made each thread insert points only into blocks whose
number matches the thread's number mod the number of threads. Locking the
cubes was not enough.

Pierre

--
Don't buy a French car in Holland. It may be a citroen.



_______________________________________________
Discuss mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/discuss