Subject: [boost] GGL Review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-11-15 17:10:44
Here is my review of GGL:
I have attempted to try the same examples that I did for my
Boost.Polygon review. Unfortunately limited time has made it
impossible for me to be as thorough as I would have liked. Here is
what I have done, and the issues that I encountered along the way.
(You may want to look at my Boost.Polygon review for background. It
can be seen here:
My first exercise was a GUI application in which I wanted to merge a
large number of small rectangles into a single more complex polygon.
Unfortunately I failed at the first step with this: I wanted to teach
the library about my existing types (point, box, etc), but how to do
this is not properly documented. It seems that there are some macros
(with not-Boost-style names) but their only mention in the
documentation is in an example. Yes, I could probably have worked out
what to do from the example, but I have limited time and furthermore I
don't think it's acceptable to expect a library end-user to learn
something relatively fundamental like this from an example. (From my
brief look at the example, it does look as if this mechanism is
significantly less verbose that what I had to do to teach Boost.Polygon
about my types, which is a good thing.)
So I moved on to my second example, which reads a file containing the
borders of the states and provinces of the US and Canada and determines
which ones contains points that the user enters. I implemented this
using the geometry types provided by the library, so the question of
adapting to types did not arise. This all worked quite smoothly,
though I did encounter the following issues, mainly with the
documentation, which I imagine could be corrected quite easily:
- The docs do not say what the C template parameter in point_xy<T,C> is.
- The "complete list of members" for ggl::linear_ring is empty.
(Presumably the issue here is that the members are all inherited from
the std::container; it could at least say that.)
- The documentation for ggl::linear_ring says that V is a "container
type e.g. std::vector, list, deque"; it should describe this in terms
of std concepts (presumably bidirectional container) so that I know if
my own custom type will work. Looking at the code I don't see any
concept-checking for this; that would be nice.
- The args to the within() function are reversed wrt the equivalent
function in Boost.Polygon. This is a good example of the issue that I
raised in a previous email, where the generic nature of the
concisely-named functions can lead to mistakes.
- Doxygen doesn't give the full path to the headers, i.e.
"point_xy.hpp" rather than "geometries/point_xy.hpp".
- There seems to be a dependency on Boost.Math that isn't mentioned on
the list of dependent libraries.
- The library doesn't seem to be in namespace boost. I guess the
intention is to add this later. This is unusual.
- I was surprised that the box class doesn't have width and height members.
- I got a page full of warnings from my test program; the cause seemed
to be unused parameters in within.hpp, lines 118 and 178. Since I have
touched only a small fraction of the library, I imagine there are other
places with the same issue.
As I said, these are minor issues that I imagine could be corrected
quickly. However they did give me the impression that the library is
still very much a work-in-progress - especially the documentation -
rather than a fully-formed finished work. I don't necessarily believe
that a library has to be perfect before it can be accepted into Boost,
but I think it needs to be a little less rough around the edges than this.
That unfortunately was all of the actual testing that I have been able
to do. I'll now discuss other issues:
Firstly there's the situation concerning Boost.Polygon. My feeling is
that the situation that has developed here is very unfortunate. I
think it's extraordinary that Boost can even consider having two
incompatible, overlapping Geometry libraries reviewed within a few
weeks of each other, with authors who are so publicly antagonistic
towards each other. How on earth did we get into this situation?
(Answer: IMO, the progress towards review flowed to the current
situation by following the path of least resistance, and "someone" - a
"leader" ? - should have jumped in earlier to steer things in a more
constructive direction.) Anyway, Boost.Polygon has now been accepted
(within an hour of this review starting! I mean, was that calculated to
be antagonistic?) and we have to consider what that implies.
One option is to imagine the two libraries in parallel universes. That
may be the most stress-free way. But it's not what would deliver the
best results for Boost's end users. What I would prefer to see is some
work to investigate how more common ground can be introduced. For example:
- Common terminology. ("within" vs. "contains", "extents" vs.
"envelope", and dozens more. GGL's not-unreasonable adoption of OGC
terminology is an issue here.)
- Inter-operable types. I would like to hope that the basic geometry
traits classes could be shared. Failing that, perhaps a method of
forwarding from one set of traits to the other could be used.
I am unsure how deeply the choice of tag dispatch vs. SFINAE makes
inter-operation more difficult. Maybe someone could comment on that.
Let me say a little about performance. There has been a great deal of
discussion about this on the list. My feeling is that all libraries
should document the worst-case complexity of all of their functions.
In the current case we have polygon boolean operations where I believe
I learnt as an undergraduate 20 years ago that they should be O(n log
n). Here IIUC the implementation is worst-case O(n^2) but typically
better. I feel uncomfortable with that, however many benchmarks and
years of real-world use have gone in to it. Is it not possible to
contrive an introsort-like "fallback" solution that gives both good
typical case performance and an optimally-bounded worst case guarantee?
The other controversial implementation issue is floating-point
robustness. I'm still not clear what the position of this library is
on that. Are we just given assurances that it seems to be robust in
real-world use, or is it believed that it actually is certainly
robust? I expected to see this discussed in the library documentation,
but I don't see anything - maybe I've missed it. If it is "believed to
be robust in real-world use", it would be helpful to describe the
possible failure modes (e.g. segfault, runs forever, or just outputs
the wrong answer.)
Congratulations to the authors on getting their library to this point.
I'm sure that it contains much useful code.
At this time, the library is let down by incomplete documentation, and
I feel it should be rejected for that.
I believe it is also essential that some effort is done to find common
ground (I'm avoiding saying "merge") with Boost.Polygon.
If the authors are unable to work together, then I would prefer that
Boost keep things simple for its end users, and avoid years of
antagonism on the mailing list, but suggesting that one (or other!)
library should exist outside of Boost.
To answer the usual questions:
- What is your evaluation of the potential usefulness of the library?
- Did you try to use the library? With what compiler?
Yes; gcc-4.x on Linux.
- How much effort did you put into your evaluation?
I've spent about 5 hours in all.
- Are you knowledgeable about the problem domain?
I'm not a geometry expert, but I have done projects that could make use
of this sort of library.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk