intersection suffers 70x performance decrease on shapely 2.0.1 compared to 1.7.1.

[fiftysevendegreesofrad]

Hi, test code here:

from shapely.geometry import LineString,MultiLineString 
import timeit 
x_gridlines = [((x,0),(x,100)) for x in range(100)] 
y_gridlines = [((0,y),(100,y)) for y in range(100)] 
gridlines = MultiLineString(x_gridlines+y_gridlines) 
line = LineString([(49,49),(51,49)]) 
print(timeit.timeit(lambda: line.intersection(gridlines),number=10)) 

With shapely 1.8.1 or 2.0.1 this takes around 0.5 seconds, as compared to 0.007 seconds with shapely 1.7.1.
Installed from PyPI on Windows 10 x64. Also verified similar results on Linux x64.
Best wishes

[mwtoews]

I can confirm a slowdown, but it is unrelated to shapely versions. The binary wheels from PyPI have unique versions of GEOS, which is why you see the differences. (Use from shapely import geos; print(geos.geos_version_string) to see it).

Looking at this example using shapely main branch on a linux laptop, I see some big differences:

• 3.9.2-CAPI-1.14.3 : 388 µs ± 5.33 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
• 3.10.0-CAPI-1.16.0 : 35.9 ms ± 735 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
• 3.11.1-CAPI-1.17.1 : 44.9 ms ± 751 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Here is a visualisation:

and the WKT is here:

gridlines_intersection.xml

<run>
<precisionModel type="FLOATING"/>

<case>
<desc> gridlines intersection </desc>
  <a>
LINESTRING (49 49, 51 49)
    </a>
  <b>
MULTILINESTRING ((0 0, 0 100), 
  (1 0, 1 100), 
  (2 0, 2 100), 
  (3 0, 3 100), 
  (4 0, 4 100), 
  (5 0, 5 100), 
  (6 0, 6 100), 
  (7 0, 7 100), 
  (8 0, 8 100), 
  (9 0, 9 100), 
  (10 0, 10 100), 
  (11 0, 11 100), 
  (12 0, 12 100), 
  (13 0, 13 100), 
  (14 0, 14 100), 
  (15 0, 15 100), 
  (16 0, 16 100), 
  (17 0, 17 100), 
  (18 0, 18 100), 
  (19 0, 19 100), 
  (20 0, 20 100), 
  (21 0, 21 100), 
  (22 0, 22 100), 
  (23 0, 23 100), 
  (24 0, 24 100), 
  (25 0, 25 100), 
  (26 0, 26 100), 
  (27 0, 27 100), 
  (28 0, 28 100), 
  (29 0, 29 100), 
  (30 0, 30 100), 
  (31 0, 31 100), 
  (32 0, 32 100), 
  (33 0, 33 100), 
  (34 0, 34 100), 
  (35 0, 35 100), 
  (36 0, 36 100), 
  (37 0, 37 100), 
  (38 0, 38 100), 
  (39 0, 39 100), 
  (40 0, 40 100), 
  (41 0, 41 100), 
  (42 0, 42 100), 
  (43 0, 43 100), 
  (44 0, 44 100), 
  (45 0, 45 100), 
  (46 0, 46 100), 
  (47 0, 47 100), 
  (48 0, 48 100), 
  (49 0, 49 100), 
  (50 0, 50 100), 
  (51 0, 51 100), 
  (52 0, 52 100), 
  (53 0, 53 100), 
  (54 0, 54 100), 
  (55 0, 55 100), 
  (56 0, 56 100), 
  (57 0, 57 100), 
  (58 0, 58 100), 
  (59 0, 59 100), 
  (60 0, 60 100), 
  (61 0, 61 100), 
  (62 0, 62 100), 
  (63 0, 63 100), 
  (64 0, 64 100), 
  (65 0, 65 100), 
  (66 0, 66 100), 
  (67 0, 67 100), 
  (68 0, 68 100), 
  (69 0, 69 100), 
  (70 0, 70 100), 
  (71 0, 71 100), 
  (72 0, 72 100), 
  (73 0, 73 100), 
  (74 0, 74 100), 
  (75 0, 75 100), 
  (76 0, 76 100), 
  (77 0, 77 100), 
  (78 0, 78 100), 
  (79 0, 79 100), 
  (80 0, 80 100), 
  (81 0, 81 100), 
  (82 0, 82 100), 
  (83 0, 83 100), 
  (84 0, 84 100), 
  (85 0, 85 100), 
  (86 0, 86 100), 
  (87 0, 87 100), 
  (88 0, 88 100), 
  (89 0, 89 100), 
  (90 0, 90 100), 
  (91 0, 91 100), 
  (92 0, 92 100), 
  (93 0, 93 100), 
  (94 0, 94 100), 
  (95 0, 95 100), 
  (96 0, 96 100), 
  (97 0, 97 100), 
  (98 0, 98 100), 
  (99 0, 99 100), 
  (0 0, 100 0), 
  (0 1, 100 1), 
  (0 2, 100 2), 
  (0 3, 100 3), 
  (0 4, 100 4), 
  (0 5, 100 5), 
  (0 6, 100 6), 
  (0 7, 100 7), 
  (0 8, 100 8), 
  (0 9, 100 9), 
  (0 10, 100 10), 
  (0 11, 100 11), 
  (0 12, 100 12), 
  (0 13, 100 13), 
  (0 14, 100 14), 
  (0 15, 100 15), 
  (0 16, 100 16), 
  (0 17, 100 17), 
  (0 18, 100 18), 
  (0 19, 100 19), 
  (0 20, 100 20), 
  (0 21, 100 21), 
  (0 22, 100 22), 
  (0 23, 100 23), 
  (0 24, 100 24), 
  (0 25, 100 25), 
  (0 26, 100 26), 
  (0 27, 100 27), 
  (0 28, 100 28), 
  (0 29, 100 29), 
  (0 30, 100 30), 
  (0 31, 100 31), 
  (0 32, 100 32), 
  (0 33, 100 33), 
  (0 34, 100 34), 
  (0 35, 100 35), 
  (0 36, 100 36), 
  (0 37, 100 37), 
  (0 38, 100 38), 
  (0 39, 100 39), 
  (0 40, 100 40), 
  (0 41, 100 41), 
  (0 42, 100 42), 
  (0 43, 100 43), 
  (0 44, 100 44), 
  (0 45, 100 45), 
  (0 46, 100 46), 
  (0 47, 100 47), 
  (0 48, 100 48), 
  (0 49, 100 49), 
  (0 50, 100 50), 
  (0 51, 100 51), 
  (0 52, 100 52), 
  (0 53, 100 53), 
  (0 54, 100 54), 
  (0 55, 100 55), 
  (0 56, 100 56), 
  (0 57, 100 57), 
  (0 58, 100 58), 
  (0 59, 100 59), 
  (0 60, 100 60), 
  (0 61, 100 61), 
  (0 62, 100 62), 
  (0 63, 100 63), 
  (0 64, 100 64), 
  (0 65, 100 65), 
  (0 66, 100 66), 
  (0 67, 100 67), 
  (0 68, 100 68), 
  (0 69, 100 69), 
  (0 70, 100 70), 
  (0 71, 100 71), 
  (0 72, 100 72), 
  (0 73, 100 73), 
  (0 74, 100 74), 
  (0 75, 100 75), 
  (0 76, 100 76), 
  (0 77, 100 77), 
  (0 78, 100 78), 
  (0 79, 100 79), 
  (0 80, 100 80), 
  (0 81, 100 81), 
  (0 82, 100 82), 
  (0 83, 100 83), 
  (0 84, 100 84), 
  (0 85, 100 85), 
  (0 86, 100 86), 
  (0 87, 100 87), 
  (0 88, 100 88), 
  (0 89, 100 89), 
  (0 90, 100 90), 
  (0 91, 100 91), 
  (0 92, 100 92), 
  (0 93, 100 93), 
  (0 94, 100 94), 
  (0 95, 100 95), 
  (0 96, 100 96), 
  (0 97, 100 97), 
  (0 98, 100 98), 
  (0 99, 100 99))
    </b>
</case>

</run>

Perhaps @dr-jts or @dbaston might shed some light on what changed in GEOS 3.10.0?

[jorisvandenbossche]

The news file lists two related overlay fixes: "Preserve ordering of lines in overlay results (Martin Davis)" and "Fix overlay handling of flat interior lines (JTS-685, Martin Davis)". Maybe some of those fixes also made it slower? (although it is a big difference)

[dr-jts]

I'll see if the same issue shows up in JTS. It might be related to those 3.10 changes - or it might not. It does look like it isn't an OverlayNG VS old overlay thing, though.

[dr-jts]

Something to try: does the slowdown occur when intersecting a diagonal line? Say LINESTRING (49 49, 51 51).

[mwtoews]

Trying with the diagonal, similar 70x difference:

• 3.9.2-CAPI-1.14.3 : 582 µs ± 11 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
• 3.11.1-CAPI-1.17.1 : 40.4 ms ± 8.98 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

[dr-jts]

Ok, good to know.

[dr-jts]

I see this as well using geosop. 3.10 and 3.11 are a lot slower than 3.9:

bin/geosop -a grid.wkt -b "LINESTRING (49 49, 51 49)" -t -r 100 intersection

• Ran 100 intersection ops ( 402 vertices) -- 11,413 usec (GEOS 3.9.4dev)
• Ran 100 intersection ops ( 402 vertices) -- 8,299,092 usec (GEOS 3.10.4dev)
• Ran 100 intersection ops ( 402 vertices) -- 7,312,082 usec (GEOS 3.11.1dev)

The good news is that 3.12 (current) is back to fast again:

• Ran 100 intersection ops ( 402 vertices) -- 6,840 usec (GEOS 3.12.0dev)

I'm not sure why this is. Perhaps @dbaston has an idea?

[mwtoews]

that is good news, and I can confirm a good speed bump to be expected. Running my tests as before, using shapely main and geos master:

• 3.12.0dev-CAPI-1.18.0 : 33.9 µs ± 118 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

that's 10x faster than 3.9 and 1000x faster than 3.11.

[fiftysevendegreesofrad]

Hi folks thank you for the very quick investigation. Sorry to ask, are you pointing your shapely 2.0.1s to a different GEOS version, if so how do I do this?

[dbaston]

I am not able to replicate this. The only thing I'm seeing is a modest improvement in 3.10. @dr-jts can you confirm that all four builds are Release builds?

for branch in main 311 310 39 ; do cd ~/dev/geos-${branch}/cmake-build-release/bin && ./geosop -a ~/data/grid.wkt -b "LINESTRING (49 49, 51 49)" -t -r 10000 intersection; done 
MULTILINESTRING ((49 49, 50 49), (50 49, 51 49))
Ran 10,000 intersection ops ( 402 vertices)  -- 195,540 usec    (GEOS 3.12.0dev)
Ran 10,000 intersection ops ( 402 vertices)  -- 187,725 usec    (GEOS 3.11.2dev)
Ran 10,000 intersection ops ( 402 vertices)  -- 195,959 usec    (GEOS 3.10.4)
Ran 10,000 intersection ops ( 402 vertices)  -- 292,690 usec    (GEOS 3.9.4)

[dr-jts]

@dbaston That occurred to me too after I posted. But I confirmed that all builds are of type Release. Still, it seems suspicious.

@mwtoews Can you confirm your builds are Release builds?

[dr-jts]

Update: did a pull on 3.10 to get to HEAD, and that fixes the performance regression.

Ran 100 intersection ops ( 402 vertices)  -- 7,453 usec    (GEOS 3.10.4)

So either there was something funky with my build, or there was an important recent fix?

[mwtoews]

Yes, Release builds here too. I can see the difference in the 3.11 branch too with a 1000x times performance difference, so I'll do a few bisections to find out the winning commit.

[pramsey]

@dr-jts found that 3.11 head was fast, but 3.11.1 was slow, and I replicated that. The critical commit seems to be this one.

libgeos/geos@711b4d7

If I reverse this commit things get slow on 3.11 head.

For some reason quieting those signals has had a massive effect. More confusing, at what point did we start suffering as a result of those signals?

[dbaston]

The signals would have started with libgeos/geos#407

[jorisvandenbossche]

That commit is not just about the signals, but also says "Fix incorrect result from Envelope::disjoint (GH-791, Dan Baston)" (so there is also some actual behaviour change)

[mwtoews]

my result is also libgeos/geos@711b4d7 xref libgeos/geos#791

[pramsey]

All things being equal, hopefully everyone finds that the head of 3.11 and 3.10 are running at speed? If so we can prioritize a patch release.

[mwtoews]

@fiftysevendegreesofrad see the manual to install shapely with a custom GEOS version. Otherwise, you'll need to wait until the next release / patch update of binary wheels on PyPI, which will most certainly use the latest and greatest GEOS version.

@pramsey patch releases are always welcome upstream, but no urgency. A shapely 2.0.2 could be planned with these changes (mostly changes to tests and refactoring).

[dr-jts]

In the spirit of lessons learned, digging further into the forensics of this...

@jorisvandenbossche found the smoking gun. The slowdown is due to OverlayNG processing all of the lines in the input, rather than taking advantage of the heuristic to discard input geometry elements which do not participate in the overlay (using EdgeNodingBuilder.isClippedCompletely). So, 202 lines are processed VS 6 when the heuristic is used.

This in turn is caused by a bug in change to the logic of Envelope.disjoint causing its result to be inverted. This logic bug was fixed in libgeos/geos#791.

The good news is that this only impacts performance when there are a lot of input geometry elements that can be discarded, which is by no means the most common use case.

Sure would be nice if there was a performance test suite that could catch major regressions like this. But that's a challenge, because of the wide variety of cases that might trigger issues, and the need to test across versions.

[jorisvandenbossche]

And thanks @pramsey for the patch releases! Then we can include GEOS 3.11.2 in Shapely 2.0.2

[joergbenndorf]

When is the release of version 2.0.2 scheduled?