Requesting suggestions and feedback

[rohitkprasad123]

Hello UberH3 community members,

I am currently working on having UberH3 as one of the potential candidate workloads in the next version of SPEC CPU benchmark and need some feedback about the workload. SPEC is very well established industry consortium that develops performance benchmarks and more details about SPEC CPU can be found here (https://www.spec.org/cpu2017/).

Geospatial Indexing is an interesting domain and therefore UberH3 presents an exciting opportunity for SPEC CPU. For my candidate workload (based off UberH3), I have used a slightly modified version of benchmarkVertex.c, benchmarkIsValid.c and benchmarkGridDiskCells.c (taken from the github location (https://github.com/uber/h3/tree/master/src/apps/benchmarks). These benchmarks were selected to meet certain criteria and requirements specific to the nature of SPEC CPU (I can provide more details on this if necessary).

I would like to get feedback from the community to see what they think of these benchmarks. In particular, I want to make sure that that the underlying APIs used by these benchmarks are considered as one of the central set of APIs and therefore, are representative of the real-world geospatial workload execution code path.

Any insights or suggestions from any of you would be greatly appreciated.

Thanks in advance.
-Rohit

[dfellis]

Hi Rohit,

Excited to see this. :)

In terms of which APIs are the "central" ones, though, I am surprised that latLngToCell was not included. I haven't worked at Uber for over 6 years, so the following is a bit out of date, but I can't imagine it has changed that much. The first step in working with rider and driver data using H3 is to convert the GPS-provided coordinates into a cell of the desired resolution. This conversion will only happen once for static datasets like geographic or political boundaries (usually using polygonToCells for that, as it's dealing with areas instead of points), but any system performing geospatial analysis on things that move over time (whether that's people, cars, buses, trains, boats, airplanes, ...) will need to re-index the object in question constantly.

Uber would update rider and driver locations roughly once every 4 seconds, which gets you on the order of millions of latLngToCell calls per second.

After that, for surge pricing, gridDiskCells is definitely an important function, as well. The surge pricing system would get a collection of data per cell for a geographic region (a "city", but often including the suburbs and sometimes neighboring cities, as well), for each cell in the collection there's a set of digested data, such as the number of riders and drivers in each cell, grouped by their current state (not on a trip, on a trip, and a few others), as well as prior pricing in the cell, etc. So there's a service that takes the tagged stream of data and produces these digests for surge pricing to use.

The surge system then uses a parallel map system where each layer of the map has a specific cell it it computing for but has access to all of the cells in the region from the prior layer. Because dispatching a driver to a rider has an impact on the availability of drivers for other riders, changes to the state of one H3 cell will have an impact on neighboring cells, with more distant cells having less and less of an impact.

So for each cell to be computed, it will use the indexed data for its own cell, as well as neighbors, using either gridDiskCells or gridDiskDistances, depending on whether or not it needs to treat further-away cells differently in its calculation, so these functions are being called for every cell that Uber operates in every few minutes when surge pricing is updated.

Then on the driver side, a mapping of these surge prices are shown to indicate to drivers where there's a strong demand. Exactly how this is done has varied a lot. At first we used cellToBoundary to generate GeoJSON with a surge multiplier associated that the driver app could then render with a color corresponding to each value, later it was done by a backend service to generate bitmap tiles that the driver app could overlay on the map, and deck.gl has its own wizardry involving an assumption that hexagon shape distortion is too low to perceive at high enough zoom levels so it can "stamp" a singular hexagon shape in the right location without calling cellToBoundary on every single cell.

In any case, the rendering of cells by getting the lat, lng boundary to provide to mapping software (that is not H3 aware, at least) is also pretty frequently called. If done naively, it would be called for all visible cells for each viewport area defined, which could be many times a second on viewport panning, so I think cellToBoundary could also be a candidate for benchmarking.

The cell validation logic really only needs to be called when ingesting a dataset from a source you don't fully trust. Within Uber's services it was assumed that all H3 indexes provided between them were valid and generated by the same source code, and so fully compatible with each other, and validation checks were not generally performed.

H3's vertex mode is much newer, so I'll have to let @nrabinowitz chime in on how "tight" of a loop they're used in the system they were designed for, but at least for the original purpose of H3 at Uber, indexing and "de-indexing" were just as important as grid traversal tooling from a performance perspective.

[rohitkprasad123]

Thank you @dfellis and @nrabinowitz for your detailed insights and also, thank you @heshpdx for adding more context. These are really valuable and I will be digesting these recommendations and making appropriate changes to my workload. Will reach out to you all again, if I need more assistance.
Appreciate your help & support.
Thanks,
-Rohit

[nrabinowitz]

As context, I'd say we usually have built benchmarks for things we're testing or iterating on, so not all of the benchmarks we include are what I'd consider a core execution path. I would not include benchmarkVertex.c for this reason - it was used for iteration, but the codepath is likely not widely exercised.

Of our current benchmarks, I would suggest:

• benchmarkH3Api.c
• benchmarkGridDisk.c
• benchmarkIsValidCell.c
• benchmarkCellToChildren.c

These probably cover the most commonly used functions in the library, though benchmarkH3Api.c, which covers the core functions (latLngToCell, cellToLatLng, and cellToBoundary) could definitely be more comprehensive (right now just uses a single fixed input).

[heshpdx]

Thank you friends! I'm one of @rohitkprasad123's collaborators. Your input is invaluable as we try to craft a great benchmark. SPEC CPUv8 is a cross-industry effort, so when we have more eyeballs it improves the candidacy of h3 (this continuing scrutiny is what brought you #790).

Let me share some of the characteristics valued by the SPEC CPUv8 committee when building benchmarks. Hopefully these tips help guide the discussion.

• Runs should have reproducible work and be verifiable to ensure all systems completed the same amount of work. We noticed some of the apps in the h3 benchmark directory do not create any output which makes it difficult to know if the work was completed. grid_disk_cells comes to mind.
• We are looking for representation of the real-world scenarios, using realistic input data. If the benchmarks are using the same input over and over in a loop, a memoizing compiler optimization can reduce the benchmark down to nothing (we actually observed this with the is_valid_cell benchmark when built using -flto). Same data for every loop iteration is unrealistic, but totally random data is also unrealistic; we prefer an array of real geo points to spin through. Is this possible? This is also useful for future consumers of SPEC CPU who may be doing research on microarchitectural techniques on data values, such as value prediction or cache line deduplication.
• The mixture of workloads is important. Of the ones you mention above, how do we choose which ones to include, and at what percentage of the aggregate? We must fit within a runtime of 3 to 5 minutes on a "single core on a modern CPU", to give you a rough idea of the scale.
• The function profile is also important; for example it would not be useful to have a benchmark that spends 90% of time in a small function like _ijkAdd - it is better to have more coverage of the code.
• SPEC CPU benchmarks live for decades, because the committee ensures compatibility with future architectures by making sure no intrinsics are used and no platform specific features are used. We also check that the code can be built with the "pedantic" mode of the contemporary compilers. There are a handful of errors that -Werror=pedantic exposes that we could use help with, and would be useful to fix in the mainline.

Anyway, hope that helps see things from the committee's perspective.

[heshpdx]

@dfellis and @nrabinowitz, any thoughts on my comments above? Can anyone help select the mix, and/or craft scenarios? How about the pedantic errors?

[dfellis]

Well, I do have a comment on this point:

The function profile is also important; for example it would not be useful to have a benchmark that spends 90% of time in a small function like _ijkAdd - it is better to have more coverage of the code.

I don't fully agree here. If the vast majority of use-cases end up spending their time in this function, it demonstrates it as the bottleneck and something worth optimizing. Some of that falls on us as the H3 maintainers -- can we make that function (if it is 90% of the time for a collection of realistic benchmarks) more efficient by rewriting it? But if optimization becomes CPU-specific, it may be better to fall on the compiler backend layer to spot the pattern in the code that could be rewritten to use vector instructions and perform said optimization.

This is assuming that it's dominance is a realistic representation of how people use H3. If it's not, of course we should alter the benchmarks to better represent this and pushing those improvements to the benchmarking suite that you mention in your first two points. (Did you notice any other deficient benchmarks besides grid_disk_cells and is_valid_cell?) My answer covers a few different major use cases that I recall at Uber. (I realize now that I forgot about cellsToLinkedMultiPolygon as another intensive path that could also be in the "hot path" in a service: generating an outline of a group of H3 cells based on live data may never be cacheable, so it's performance can be very important for certain use-cases.) But even Uber is just one user of H3, so it would be prudent to find other large users (maybe Foursquare and Snowflake?) and see what they're doing and consider it in the balance.

Basically, to answer this question:

The mixture of workloads is important. Of the ones you mention above, how do we choose which ones to include, and at what percentage of the aggregate?

We can only give you one perspective, and that might not be enough.

But if 90% of the time in a realistic benchmark is spent in a small inner function like _ijkAdd even after considering all of these use cases, then I don't see the problem with the benchmark focusing on that, since that's what actually impacts people. It might be a bit disappointing that H3 can only help with one facet of CPU performance comparisons if that's true, but that in itself could be a useful lesson and you can reduce the benchmark to a narrower slice of the project and use other projects, whether it deals with geospatial data or not, to stress other factors in CPU performance?

I still think the following functions are "the most useful" and cover a lot of ground

• latLngToCell (point data ingest)
• polygonToCells (area data ingest)
• gridDiskCells ("neighborhood" analysis)
• gridDiskDistances (also neighborhood analysis, but with more precision on distance from the epicenter)
• cellToBoundary (visualization for individual cells)
• cellsToLinkedMultiPolygon (visualization for groups of cells)
• and maybe include compactCells for a lossless compression technique, but I don't think this one would be used by too many people. It's like the directed edge and vertex modes; advanced features for very particular use-cases and not on the "main path", but compactCells might have more uses in database contexts.

[dfellis]

Also,

There are a handful of errors that -Werror=pedantic exposes that we could use help with, and would be useful to fix in the mainline.

Thanks for pointing this out. I think I'll try and tackle that today or tomorrow if my other PR gets merged soon. :)