Christoph Pahmeyer

A performance comparison for the times needed to perform the different steps involved to calculate the area of 1 million buildings in Utah using different geospatial tools, and visualizing them using deck.gl. 

Prototyping GeoParquet + GEOS in WebAssembly

Get inspired by the work of these amazing authors, nominated by members of the Observable team. 

Observable

Featured creators

Wait what, you're reprojecting the array in place without parsing the WKB?! Madness! 😂

Kyle Barron

haha yes :D https://i.kym-cdn.com/photos/images/newsfeed/001/946/559/443

The first version where I reprojected each WKB independently is below this cell (reprojectWKB), this version should also support all kinds of WKBs and not just polygons like the function above does!

Just a note that yes since WKB is binary you can transfer that, but the downsides are 1) it needs to be parsed on the wasm side and 2) you need to do a separate copy for _each_ WKB object, whereas with geoarrow because it's columnar you only need to do one copy for an entire _array_ of WKB objects. So copying in 1 million individual WKB buffers to WASM memory has its own perf cost.

With regards to passing the WKB, I've tried a different approach in this notebook: I'm sending the entire Uint8 WKB geometry column (all 1mio buildings) to WASM in one go (see "area" cell):

    console.time("allocating memory");
    // allocate a single pointer for the entire WKB feature array
    const values_ptr = geos.Module._malloc(
      reprojectedValues.length * reprojectedValues.BYTES_PER_ELEMENT
    );
    geos.Module.HEAPU8.set(reprojectedValues, values_ptr);
    console.timeEnd("allocating memory");

and then create the GEOS geometries by using the featureOffsets (values_ptr + valueOffsets[i] = beginning of the feature)

    console.time("creating geos geoms");
    const geomPtrs = new Int32Array(geometryColumn.length);
    for (let i = 0; i < valueOffsets.length - 1; i++) {
      // Get the pointer and size of the current feature
      const feature_ptr = values_ptr + valueOffsets[i];
      const feature_size = valueOffsets[i + 1] - valueOffsets[i];
      // Read the feature from the buffer
      geomPtrs[i] = geos.GEOSWKBReader_read(reader, feature_ptr, feature_size);
    }
    console.timeEnd("creating geos geoms");

So you are absolutely right, we still need to parse the WKB on the WASM side (shown as "Geometry creation (GEOS only)" in the table below), but at least we are copying the WKB feature column/array just once!

In a previous version of this notebook, I actually copied every single WKB to the Wasm heap, and it took forever just like you said. I didn't even know you could work with pointer offsets in Wasm like it's done here! Just stumbled upon it playing around yesterday 😊

Ah that makes a lot more sense! Yes, working with pointer offsets in wasm is possible and very powerful, though easy to get wrong! E.g. https://github.com/kylebarron/arrow-js-ffi is doing pointer arithmetic manually to understand these C structs https://arrow.apache.org/docs/format/CDataInterface.html#structure-definitions. For WKB parsing it should be pretty straightforward though

It's interesting to see the table laid out with line items! In terms of GeoArrow performance, the reprojection is indeed slow, so for this specific case we can remove that by computing chamberlain and duquette area directly like turf does. It's [already implemented](https://github.com/kylebarron/geoarrow-rs/blob/ccdd97af7344c70ff41a0eea3f83db945e7aa564/js/src/algorithm/geo/chamberlain_duquette_area.rs#L8-L15); I just need to publish a new version of the JS library. I'll do that soon.

I'm very surprised to see a full second difference in loading the Parquet file. I should probably benchmark this on the Rust side, and see what part of that is slow. I expect some large Parquet-wasm speedups and memory improvements in the near future when we remove needing IPC

Thanks for the comments! Sure using Chamberlain and Duquette would be faster than reprojecting in general, but my point was rather that I believe that reprojecting in Rust (geodesy) should be at least as fast as in JS (see reprojectedWKBArray function at the end of this notebook), if not even much faster. I haven't checked how geodesy is technically carrying out the reprojection but I'm naïvely assuming that there might be some performance gains possible there...

Regarding the Parquet parsing difference, I was also very surprised! Curious to hear if you find out what it is, and also let me know if I can be of help!

Using parquet-wasm 0.4.0 and the new FFI table interop, in https://observablehq.com/d/e5e07af5fb62b1f6 I got the parsing from 2600ms down to about 2100ms for the fixed size list array, but in https://observablehq.com/d/286090808f0cf4d3 I got the parsing from 1500ms down to 1300ms for the WKB array. My best guess is that the binary column is just plain faster to parse in Parquet, because you don't have to actually parse it. It's already binary... just decompress it and you're done! While the fixed size list array needs to provision a new array to copy the data into 🤷‍♂️

I even checked that both files are brotli-compressed, so I don't know how to perf test the files without digging in to each in rust.

I do agree that it should be possible to make the rust reprojection faster. I haven't looked into that at all.