[OSGeo-Discuss] 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