[GRASS-user] v.lidar.edgedetection very slow

GRASS GRASS user
1

ok, I had a chance to look using a 1km^2 block of LIDAR data I had around.
(0.5M pts, uses ~ 750mb RAM on 64bit Linux)

I've never used the v.lidar tools much (I usually just do something
simple with r.in.xyz) so I can't offer too much expert help. But...

[half of what follows is aimed at developers]

John:

I have recently joined the user group and I'm working on LiDAR data.
I am running GRASS GIS 6.4.0svn (the one that came out last week) on
an Intel quad core 6600 with 2gb RAM.

OS = XP Pro

I have seperated my data into 1000mx1000m which have around
1.5 million points per tile.

I use the -tbzr on v.in.ascii and v.build after for topology.
I have also utilised the sqlite db.

AFAICT topology is not required for v.lidar modules.
If you only use 3D x,y,z data then database is not needed and will just
take up space and memory. (v.in.ascii -z)

After running v.outlier on first and last returns, the time come for
edge detection.

I run this module (v.lidar.edgedetection) and it works (only using
25% of cpu as per usual (guessing there is no quad cpu support = shame))

Nope, awaiting a volunteer -- could be a really nice threading project
for someone.

- the v.lidar code is reasonably straight forward & compartmentalized
- experimental support for Pthreads is already added to r.mapcalc in
   grass 7 as a template, but this could be an even better example as
   r.mapcalc is typically hard drive-limited not CPU-limited.
- IIUC there is an OpenMP version of i.atcorr by Yann Chemin which
   may provide a OpenMP example.
- not really sure if Pthreads or OpenMP is more appropriate here

tcholDec() could probably be split up into multiple threads at the
for(i;:wink: stage. (??)
https://trac.osgeo.org/grass/browser/grass/trunk/vector/lidar/lidarlib/TcholBand.c#L6

see also http://grass.osgeo.org/wiki/OpenMP

However, I have not finished a process yet as it writes at about
1kb per second, using 1% of cpu.

I can only assume that is due to page swapping. Running without a DB
and with no topology may help to save quite a bit of memory/time there.

no idea why it would drop to 1% of CPU if there is no page swapping
going on.

As it is writing the file (was at 6Mb after 3hrs), the mem usage is
on 114Mb with 1.4Gb free at the moment. It is not using the PageFile.

.... is that at 100%/4(25%) or 1% CPU?

Is it supposed to be this slow? is there a bug? The tile as .txt/.las
is c.47Mb.

the vector engine doesn't scale as well as the raster engine (which can
easily handle gigabytes of data), but it should handle 47mb with ease.

Does the edge file equate to a similar size, e.g. will it
take about 47000 seconds to write the file? Is there a rough percentage
of the size of edge file compared to original txt file? I notice it is
also writing to the sqlite.db at the same time.

no idea about file sizes. In 6.5svn and 7svn I've just added some
verbose messages (add --verbose) and some percent done indicators
so it will seem like less of a black box now.

It turns out that ~95% of the computational time is spent in the 3-deep
nested for loops of the Tcholetsky decomposition function.
(lidarlib/tcholDec())

for my data it ran 16 loops of:
{
  1. Bilinear interpolation
  2. Bicubic interpolation
  3. Point classification (fast)
}

maybe these loops are another thing that could be sent out to different
threads? (not sure if these are multiple passes or independent segments)
Better to concentrate on the library level first? i.e. lidarlib/tcholDec()
or is tcholDec() just written in a very inefficient way?

also you can turn on some debug messages to follow the action:
g.gisenv set="DEBUG=1"

Have I done something wrong?

one thing to check: did you run 'g.region vect=lidar_points res=2 -ap'
before starting? v.lidar.edgedetection seems to use the current
computational region settings for something.

The book and manual says it needs topology for lidar tools to work.
Does it need the database?

I don't think it needs either. Where abouts does it say that?

v.build and thought a db could help.

.... I think it just adds overheads to the process.

Hamish

2

As it is writing the file (was at 6Mb after 3hrs), the mem usage is
on 114Mb with 1.4Gb free at the moment. It is not using the PageFile.

.... is that at 100%/4(25%) or 1% CPU?

The RAM was increasing gradually also. It's at 1% CPU.

I tried again with a 182kb tile and the process took 10mins or so. It was using the RAM, increasing up to around 50Mb and 25% CPU usage then drops to minimal RAM and 1%CPU. It did this twice during the process. Presumeably for the two files, cleaned and oultiers. At the point it starts writing the file, it is at the slow speeds mentioned.

Does the edge file equate to a similar size, e.g. will it
take about 47000 seconds to write the file? Is there a rough percentage
of the size of edge file compared to original txt file? I notice it is
also writing to the sqlite.db at the same time.

no idea about file sizes. In 6.5svn and 7svn I've just added some
verbose messages (add --verbose) and some percent done indicators
so it will seem like less of a black box now.

This 182kb file equated to 408kb edge file.

also you can turn on some debug messages to follow the action:
g.gisenv set="DEBUG=1"

Cheers, will try this.

Have I done something wrong?

one thing to check: did you run 'g.region vect=lidar_points res=2 -ap'
before starting? v.lidar.edgedetection seems to use the current
computational region settings for something.

yes, though at 'res=1' for this dataset and didn't use '-ap'

The book and manual says it needs topology for lidar tools to work.
Does it need the database?

I don't think it needs either. Where abouts does it say that?

p252 of 3rd edition '#build topology so that we can use all vector tools'. However, the method on p256-257 does not mention db or topology. Also, when I have tried to run v.oultier without db/topology it says it cannot as there is no database. I will look at this again later. Maybe I am not selecting 3D when I have tried without db etc.

John

3

Hamish wrote:

It turns out that ~95% of the computational time is spent in the 3-deep
nested for loops of the Tcholetsky decomposition function.
(lidarlib/tcholDec())

for my data it ran 16 loops of:
{
  1. Bilinear interpolation
  2. Bicubic interpolation
  3. Point classification (fast)
}

maybe these loops are another thing that could be sent out to different
threads? (not sure if these are multiple passes or independent segments)
Better to concentrate on the library level first? i.e. lidarlib/tcholDec()
or is tcholDec() just written in a very inefficient way?
  

Some of the nested for(;:wink: loops could be improved by adjusting start
and end values. Maybe the attached patch for
vector/lidar/lidarlib/TcholBand.c helps. No warranty!

Markus M

(attachments)

TcholBand.patch (4.84 KB)

4

I actually get the same thing. For the first while the process runs in full use of one core, but once the process starts writing results to the db, the whole process bogs down to a grinding halt. CPU usage for v.lidar.edgedetection drops down to ~1% (1% of one core) and sqlite usage rises to ~16%. Maybe I’m wrong, but my impression was that the bottle neck was the modifications to the database.

However, I have not finished a process yet as it writes at about

1kb per second, using 1% of cpu.

I can only assume that is due to page swapping. Running without a DB
and with no topology may help to save quite a bit of memory/time there.

no idea why it would drop to 1% of CPU if there is no page swapping
going on.

As it is writing the file (was at 6Mb after 3hrs), the mem usage is

on 114Mb with 1.4Gb free at the moment. It is not using the PageFile.

… is that at 100%/4(25%) or 1% CPU?

On 19-Jun-09, at 5:43 AM, John Tate wrote:

Also, when I have tried to run v.oultier without db/topology it says it cannot as there is no database. I will look at this again later. Maybe I am not selecting 3D when I have tried without db etc.

Note that there is a bug in v.outlier. v.outlier creates a temporary table by the name of outfilename_aux (LN #137 /lidar/v.outlier/main.c) but elsewhere in the code it is hardwired to Auxiliar_outlier_table (LN’s # 239 & 258 /lidar/v.outlier/outlier.c) , so when it actually tries to write to the table it complains and fails. You can get around it by manually creating this table using;

db.copy from_table=outfilename_aux to_table=Auxiliar_outlier_table

I’m not sure why, but it looks like the system doesn’t always need to use the Auxiliar_outlier_table, and when it doesn’t, it continues on merrily without complaint. Unfortunately, when it does require the table, on my system the program continues on only to segmentation fault further down the line (at least it does on my system). Maybe it’s because of the changes that I made to the code to correct the above error, but I can’t see why that would be true. I was planning on looking further into it, but haven’t had the time to start debugging. In the mean time I’ve added the files with my changes to the code for the developers. I’m a hack, so the changes are probably in poor coding practice. Someone more savvy that I will need to clean it up.

Cheers,

Mike

PS. IF I find what I think are errors or possible improvements to the code, what is the most appropriate place and method to submit them?

(attachments)

main.c (11.1 KB)
outlier.c (8.47 KB)
outlier.h (784 Bytes)

5

Note that there is a bug in v.outlier. v.outlier creates a temporary table by the name of outfilename_aux (LN >#137 /lidar/v.outlier/main.c) but elsewhere in the code it is hardwired to Auxiliar_outlier_table (LN’s # 239 >& 258 /lidar/v.outlier/outlier.c) , so when it actually tries to write to the table it complains and fails. You can >get around it by manually creating this table using;

db.copy from_table=outfilename_aux to_table=Auxiliar_outlier_table

Mike

I tried this yesterday but the command didn’t work for me. What I did discover however, is the error (unable to write to table Auxiliar_outlier_table) occurs when using spline steps of soe=4 son=4. I tried 10 and 5 for both and those worked. So not sure if there is a bug there. I will have to stick to 5 for now even though i wanted to use 4. I have not tried any other variations.

Just an update on my original thread, v.lidar.edgedetection was working fine with the 47MB file. Didn’t take too long either.

John