`getwkb` allocates ~O(n²) on multi things because of sizehint!

[asinghvi17]

getwkb allocates far more than its output size for any geometry whose subgeometries carry their own header (MultiPolygon, MultiPoint, GeometryCollection), growing linearly with the subgeometry count at constant output size.

import GeoInterface as GI, GeoFormatTypes as GFT, WellKnownGeometry as WKG

ring(n)  = GI.LinearRing([(Float64(i), Float64(i)) for i in 1:n])
mpoly(k) = GI.MultiPolygon([GI.Polygon([ring(100_000 ÷ k)]) for _ in 1:k])  # 100k vertices total

WKG.getwkb(mpoly(2))  # warm up
for k in (1, 25, 100, 400)
    mp = mpoly(k)
    nb = length(GFT.val(WKG.getwkb(mp)))
    a  = @allocated WKG.getwkb(mp)
    println("k=$k\tout=$nb B\tallocated=$a B\t$(round(a/nb, digits=1))x")
end

geometry	subgeoms	output	allocated	amplification
MultiPolygon	1	1.60 MB	6.25 MB	3.9x
MultiPolygon	25	1.60 MB	52.4 MB	32.8x
MultiPolygon	100	1.60 MB	216.8 MB	135.4x
MultiPolygon	400	1.61 MB	877.4 MB	546.6x
GeometryCollection	400	1.61 MB	949.6 MB	591.6x
MultiPoint	100k	2.10 MB	297.1 GB	141461x
Polygon (control)	1 → 400 rings	1.60 MB	6.25 MB	3.9x (flat)

Polygon stays flat because PolygonTrait goes through repeat=false, while the multi-* traits are <: GI.AbstractGeometryCollectionTrait and so take _getwkb!(..., repeat=true), which passes first=true for every subgeometry — and the if first branch calls sizehint!(data, 42) (src/wkb.jl:113; sizehint!(data, 21) at src/wkb.jl:68 for points); since sizehint! below the current length shrinks capacity down to length, every subgeometry discards the amortized doubling growth and the next push! reallocates the whole buffer. Emitting the 5-byte subgeometry header on that path is correct per the WKB spec — only the sizehint! is accidental.

Guarding both call sites with isempty(data) && flattens every row to 3.9x (MultiPolygon k=400: 877.4 MB → 6.25 MB; MultiPoint: 297.1 GB → 6.25 MB) with byte-identical output (sha256-verified on all three shapes).

WellKnownGeometry v0.2.6, GeoInterface v1.6.1, Julia 1.12.6.

[asinghvi17]

I know this is a bit ridiculous in terms of scaling, but it can be important in some cases. In any case I am prototyping a faster reader in GeometryOps which I will PR here at some point.

[evetion]

Ah, good catch. How did you notice? Can you make a PR, or post the diff?

I'm fine with a better implementation, although it's not straightforward with all the variants. And don't take this the wrong way, but GeometryOps seems to become a bit bloated?

[asinghvi17]

I put the implementation in the GeometryOpsTestHelpers subpackage mostly for that reason, I didn't want to have a WKB reader/writer in GeometryOps either.

It could definitely be useful to put some things in subpackages or even independent packages. For now to simplify development i've kept them in GeometryOps, but e.g. FlexibleRTrees could be easily moved outside of GeometryOps, or be a subpackage of it.