Thursday, November 8, 2012

GIS clipping benchmark: jgrasstools & uDig (on JTS & geotools)

I hate this. I hate it when I see a callout for a benchmark and am not able to not give it a try. And I hate it even more when I have tons of work to do. But yeah, I love the thrill :)

So here it goes. This morning Markus called out for the GIS Clipping benchmark contest revisited. Well, I somehow felt invited as part of the "other FOSS GIS", so I had to run for it. :)

On thing I noticed at once, is that the reported processing times were quite high. I had no proof, but in the last years I worked (also on editing) withmany 1.5 giga shapefiles in uDig. And to be honest I aslo found it was the only software (FOSS and non) that was able to handle the thing properly without making one get mad.

I wanted to have a look how the geotools/jgrasstools/uDig Spatial Toolbox would perform. I am not a real benchmark guy, but well, I can run some modules to have an idea about more or less what it takes. So I grabbed the testdata and gave them a run.

I have also to say that I ceated a bit because we didn't have a clipping tool inside the spatial toolbox up to now, since in uDig this would be done with the Axios tools. So I quickly wrote one, the VectorClipper.

The machine I tested this on is a 2 years old windows 7 64bit machine with 8 gigs of RAM and java 1.6.
It has 4 cores.

The first run was really simple, reading in the features, create an index to quickly get the features that might be involved in the clipping and clip one by one.

Result using one core: ~201 seconds

Interesting. GRASS takes about 5 minutes, but that is ok (or better, great), since it also does topology. QGIS seems to take about 5 minute, which looks a bit like bad performance to me, considered that our worst case scenario takes a bit over 3 minutes.

Anyways, let's focus on making things better.

The VectorClipper can run in multithreading mode. So I enabled it for my 4 cores.

Result using 4 cores: ~152 seconds

Hey, hey. Nice!
But We can do better than that.

Since the creation of the spatial index was taking quite some time, I decided to drop that one, and use instead JTS prepared geometries, which would make the intersects query faster.

So without an index but with fast intersect query I got:

Result using 1 core: ~130 seconds
Result using 4 core: ~110 seconds

So I though: what if I was wrong about the index thing?
So I added the index back...

Result using 4 core: ~102 seconds

Then I noticed that in the multithreading part I had some lists that got copied instead of just passed as indexes. Once that was fixed I got a nice:

Result using 4 core: ~82 seconds

Which is where I was very satified and stopped my tests.

So the above could be called the geotools/JTS/jgrasstools benchmark, since I was running the module from my development environment.

Running this inside uDig has some more overhead, so it made sense to test that, since that is what the user would get.

Here the result I got:






as you can see from the console output, the processing took about 117 seconds, which is anyways a good performance, considered the available benchmarks.


I can't take much credit on this, all the work is done by JTS and geotools, so the credit goes there.

I loaded the used jgrasstools libs on the site, so they could be used in uDig. If you need help in getting started with uDig's spatial toolbox, have a look at this video.

-------------------------------
UPDATE
Just for the interest/fun of doing it, I ran this on amazon AWS on an cc2.8xlarge instance with 32 cores. It took about 25 seconds, 2 of which for reading the data, 7 of which for writing the result, and most f the rest of the time for creating the index.





11 comments:

Andrea Aime said...

I see this is not your case, but if you ever have to clip over a rectangle you should have a look at Geotools GeometryClipper class, it's a lot faster than JTS for that specific case

moovida said...

Hi Andrea, thanks, I was hoping for your comment here. I did some easy performance tweaks, I can't think how much the time would go down with some of your black magic :)

Thanks for the hint on the GeometryClipper, I will look at it.

Dr JTS said...

Great to see this benchmark done with JTS! And that it turned in a pretty good time.

moovida said...

Definitely Martin! I am expecting some reaction from the C world on this, since JTS is performing great :) and I think it could be tweaked further. Let's see what happens :)

Unknown said...

Without surprise, OpenJUMP, which is also based on JTS (1.13 NB for the test) takes almost the same time as uDig.
From 6 measurements, I get
- A fluctuating time of 20 to 66 s for data loading.
- A constant time of 61 to 64 s for clipping or overlay.
- And 4 to 5 s more to export clipped data.

Windows vista 64b + Intel Core i7 (quad core).
java7 with 8 Gb mem.

moovida said...

Hi Unknown :),
that is very interesting!

For the clipping operation the fastest I got is 75 seconds. I would really love to know how you get 10 seconds less, since I assume you are on JTS as well.

Is the code multithreaded?
The only thing I can think of is that I am loosing time during the reading of the data in memory (for the index), instead of sequentially handle them.

Nice!

Unknown said...

Hi Andrea,

Sorry, I'm Michaël Michaud from OpenJUMP project.
I just had a look to the ClipToFence Plugin which does the following.
- Index collection B with default STRtree parameters (contours)
- For B features intersecting the fence envelope (obtained using the index) :
- Compute intersection with EnhancedPrecisionOp.intersection method
- Create new Feature and transfer attributes

No, I don't use multithreading, but it seems to be an intersesting place for parallelization.
Did you use a fresh JTS version ?

Michaël

moovida said...

Hi Michaël, good to hear from you. I know you from your dxf work, which I ported into jgrasstools. Never got a chance to thank you. So thanks! :)

About the workflow:

> Index collection B with default STRtree parameters (contours)

ok, doing the exact same thing here.

> For B features intersecting the fence envelope (obtained using the index) :
> Compute intersection with EnhancedPrecisionOp.intersection method

Since the index holds only the envelope, I am doing an additional if(intersects) using the preparedgeometry. And then I use the geometry's own intersection method. I was assuming that would be faster, it might not.

I also wonder if EnhancedPrecisionOp is better/faster. The name would suggest slower, but, well...

> Create new Feature and transfer attributes

Also here I should be faster, since I just substitute in the old feature the new geometry.

I am really wondering where I loose all the time :)
Would you mind a link to the code?

> No, I don't use multithreading, but it seems to be an intersesting place for parallelization.

Yes, I thought so, but honestly i was hoping for more push :)
I want to try it on a 36 core on AWS, just to see if that changes a lot or not.

> Did you use a fresh JTS version ?

The 1.12

Cheers,
Andrea

Michaël Michaud said...

Even if intersects is (maybe) fastest than intersection, I don't think it worth the overhead.
EnhancedPrecisionOp has no overhead if no problem is encountered using the normal intersection (just take care of normal intersection generating exceptions)

Here is a link to the code :
http://jump-pilot.svn.sourceforge.net/viewvc/jump-pilot/core/trunk/src/com/vividsolutions/jump/tools/OverlayEngine.java?revision=859&view=markup

Michaël

moovida said...

Just for the interest/fun of doing it, I ran this on amazon AWS on an cc2.8xlarge instance with 32 cores. It took about 25 seconds, 2 of which for reading the data, 7 of which for writing the result, and most f the rest of the time for creating the index.


PS: thanks for the link Michaël

Dr JTS said...

@Andrea/Micheal:

EnhancedPrecisionOp should be basically the same performance as Geometry.intersection. I would recommend just using the standard intersection method, since then you will get the benefit of all heuristics it contains.

In my testing it is worth using PreparedGeometry.intersects as a primary filter. I'm not using an index, however - I just stream in the entire file.

I also use PreparedGeometry.contains as a quick test for lines which are wholly contained, and thus don't have to be intersected.