Geom2d benchmark

[noahgibbs]

Thomas Leitner wrote a benchmarking blog post where we did well (https://gettalong.org/blog/2021/benchmarking-rubies.html) on several benchmarks. One was the geom2d benchmark, written by Leitner himself. It looks like a decent one for us to monitor longer-term.

Geom2d: https://github.com/gettalong/geom2d

[maximecb]

Thanks for linking to this Noah. It looks pretty cool. I think we could add it 👍

[maximecb]

I was just looking at this for fun and it's not clear to me from the blog post what code actually gets run for the geom2d benchmark. There is no explicit benchmark in the geom2d repository that I can find 🤔

@gettalong Would you be willing to share the source code of the geom2d benchmark you wrote for your blog post? We'd like to include it in this repository and use it for benchmarking as well if you are ok with that :)

[gettalong]

@maximecb Sure, this is indeed missing from the post. Here is the benchmark.yaml file used:

prelude: |
  require 'geom2d'
  shape = Geom2D::Polygon([0.0, 0], [132.0, 0], [132.0, 97.0], [ 0.0, 97.0 ])
  polygon = Geom2D::Polygon([ 62.0, 7.0 ], [ 152.0, 7.0 ], [ 152.0, 97.0 ], [ 62.0, 97.0 ])

benchmark:
  small: 'Geom2D::Algorithms::PolygonOperation.run(shape, polygon, :difference)'

You can choose any two polygons shape and polygon for this, those two are representative of the ones HexaPDF has to deal with during layouting.

[noahgibbs]

Yeah, we would want to expand significantly on this. It's one reason I haven't gotten around to it yet. It does seem extra-relevant once object shapes are introduced to CRuby master, though.

[gettalong]

You should be able to just randomly generate points and create an arbitrarily big polygon from them. The higher the edge count the more needs to be computed.

There is, however, a bug somewhere in the Geom2D::Algorithms::PolygonOperation which I have yet to locate and which results in errors for arbitrary polygons. Since I only need to use boolean operations on rectilinear polygons in HexaPDF, it wasn't a priority for me to find the bug yet.

[maximecb]

I think we would ideally want more/bigger polygons and more operations. @gettalong any chance you could help us expand the benchmark to make it a bit more complex? :)

[gettalong]

@maximecb So, the PolygonOperation class encapsulates an algorithm to calculate the difference, union, intersection and xor of two arbitrary but non-self-overlapping polygons. The thing is that the runtime of the algorithm doesn't really depend on the operation itself, so it wouldn't make sense to benchmark all different operations. It is also the only complex algorithm I have implemented as of now for the library.

Working on more polygons is only possible in the sense that you can combine multiple polygons into a PolygonSet and use that instead of a single polygon, as the boolean operation needs exactly two polygon sets. You can also just keep adding points to the polygons until the get as big as you like ;) The more points the more intersections the algorithm needs to calculate.

For details on the algorithm itself: It is described in the paper "A simple algorithm for Boolean operations on polygons" by Martinez et al (see http://dl.acm.org/citation.cfm?id=2494701). The geom2d implementation is based on the public domain code from http://www4.ujaen.es/~fmartin/bool_op.html

[maximecb]

Given that this is already included in hexapdf and that it's a fairly small benchmark, it doesn't seem like a priority for now.