[MUSIC PLAYING]
TOM PAYNE: Good evening, everyone.
Slight change of title.
This one is just surviving without generics.
This is very much a Go experience report
of writing a library and having just geospatial types--
I talk a bit about that-- a scenario where having generics
would have been very helpful, and I
would have written it quite differently had I had them.
So I thought about a few of the problems I encountered
and the ways I worked around the lack of generics in Go.
The library itself.
It's go-geom, It's for having geospatial data.
This is the sort of thing you'll use
if you were going to write the back end for Google
Maps, Google Earth, or you want to about something like Strava,
where you're going to analyze GPS track
logs over time, that sort of thing.
This is something I do a lot for fun.
I want to create a nice, useful library with a clean API.
I was less worried about the implementation,
but I wanted it to be easy to use.
This handles different types of geometries.
I'll talk about those.
It converts things in various common formats like KML and GPX
and IGC and WKB and so on.
And it provides a number of operations on these geometries.
Underneath the hood, sometimes I'm
handling quite a lot of data.
For example, I used this in a project where for the big race,
for the Red Bull X-Alps, where we have people racing
across the Alps for 12 days, with data coming
in at one second from 30 different teams,
and I wanted to do a fair amount of analysis and presentation
of that data.
What's it doing?
It's using OpenGeo Consortium-style geometries.
This is the open-source geospatial world.
They have 33 different types of geometry points, lines,
strings, and polygons, which can exist
in either single individual items, or as multi-things.
Example, a point might be the location of your front door.
A multi-point might be all the water fountains in Zurich.
A line string might be a road, and a multi-line string
could be separate things, or it could be something like,
describe how a river would be, with all its tributaries,
as a single object, as a multi-line string.
Polygon, footprint of a building.
A multi-polygon-- think of a country
with many, many islands.
And multi-polygon with holes.
You've seen a map of Switzerland.
There's little bits of Germany inside Switzerland,
little bits of Switzerland--
[INAUDIBLE] is Switzerland inside Germany,
but it's definitely not--
it's a little bit complicated.
So overall, we've got many of these different types.
There's seven basic types there.
Linear ring is just a component of a polygon.
It's either the outer ring or what it holds inside.
They also define something called a geometry collection,
which I'm not going to talk much about, because it's just weird
and doesn't behave like anything else,
and it is definitely way beyond not having generics.
The sort of things the library includes
is operations on these computing bounding boxes, convex hulls,
et cetera, et cetera.
For just spatial stuff, there's a few different dimensions here
to this problem.
So people might have this--
I wanted it to be a generic useful library,
so people are going to have different types of data.
2D, 3D, 2D with a measure.
A measure is typically time.
Think of a running track, for example, a running track hull.
We've got some position evolving over time.
Maybe 3D with time, which would be--
so the next time you jump on a plane
and fly, you take your GPS and record your flight
to Berlin or something.
You are evolving in 3D over time.
You might want to add--
it's pretty convenient to be able to add extra
per coordinate numerical data.
In the case of a running track log,
it might be your heart rate, for example.
On top of that, for efficiency reasons,
people might want to use different types
as that particular coordinate.
Float64 obviously covers most things,
but maybe you only use float32s for efficiency
or to save space requirements.
Or you might want to use ints if you're using this in, say,
a game world, where you've got much more control
over the coordinate system.
So this is our first dimension of the problem,
is the different type-- we need to convert
different coordinate types.
And if we had generics, this would definitely
be a template parameter.
Combining two.
We've got six, seven different geometry types.
We've got different dimensionalities,
like 2D, 3D, 4D, or different types of actual ordinates.
It gives us multiple combinations.
And this is really where it would be nice
if we didn't have to write 72 bits of code to avoid this.
Of course, my first attack was code generation.
This is what it looked like at the point I abandoned it.
This is just doing points with either 2D, 2D with a measure,
3D, and 3D with a measure.
This goes text template library.
The formatting is a little bit weird,
because I wanted the outputs to be valid--
go from the code.
And that's why you see multiple things on a line here.
This quickly becomes very, very painful.
The problem is not particularly flexible.
This is only adding one dimension
to those three dimensions of the problem I have.
It's only coping with limited type system.
So this is still fixed on float64s.
That's not a parameter.
Of course you can extend it, but it just gets worse.
It's hard to read.
It's hard to write.
It's hard to modify.
This is the implementation for points.
If I'm doing it the line strings and polygons,
I duplicate this code six times.
And whenever you come up with a better way of doing it,
you've got to modify it in six different places.
It just doesn't scale.
So not fun.
So having version 2.
This is the crux of the talk really.
So trying to do this without using co-generation.
And actually with zero co-generation
until about a few weeks ago when I found a very good library.
The three different approaches I took
to work around lack of generics, simplifying the problem,
moving tracking information part time to run time [INAUDIBLE],,
and then exploiting common structure in the nature
of the [INAUDIBLE] I'm solving.
And I do use a little bit of limited generation
I'll talk about.
So firstly, simplify the problem.
And this is kind of it's silly to just say I'm just
going to support float64s.
But if you cut off one dimension, it really helps.
And when you're developing software--
the problem comes from having complex software.
If you can make your problem simpler,
you can massively reduce the development time,
just make it massive easier.
So by executive decision, I'm just going to do float64s.
It'll be OK.
The second aspect is moving type information from compiled time
to run time.
So particularly for the particular ordinates,
where you have multiple number of dimensions,
instead of having this parameter that's checked at compile time,
I now represent coordinates as a variable length slice.
This is not exactly the code that's in the library,
for reasons we'll go into later.
But it gives you a rough idea of what's going on.
A point now it has [INAUDIBLE] who's only length is only known
runtime, a layout which tells you which elements of the array
correspond to which dimension.
I'll talk about stride in a moment,
the implementation of layouts.
We then have to do runtime checks
to, basically, interrogate--
[INAUDIBLE] a point, does this have a Z index?
You can see the simple switch here.
Based on-- given the layout, it will tell me
where to find the Z coordinate if this particular coordinate
has one.
The stride is so that we can park
in those extra numerical dimensions,
like the heart rates, for example, that I talked about.
Now you can pack it into that same array.
And by having stride, that's longer,
the number of dimensions you need just for your layout,
you get your extra data in there.
What this does, what it means, it
changes the way the code looks.
Now, instead of getting the compiler
to catch when things are mismatched,
we have to actually check for errors ourselves at runtime.
The top level code is still reasonably nice.
But you see these are all now runtime parameters.
These sort of errors that you get here
is if I don't supply in a sufficiently
large enough array, if I want an XYZ,
am I going to give it two elements?
Or if I give it four elements, then there's
going to be a runtime error, which, of course,
you need to handle.
But this approach was helpful.
The final one, perhaps the more efficient one,
is exploiting common structure in the problem.
If you think back to the different types that we have--
I'll just go back to the slide--
you can observe that a point is just a single coordinate.
LineStrings and MultiPoints both have an array of coordinates,
or multiple coordinates.
If you take a polygon and a MultiLineString--
or all the better, a polygon with holes
and a MultiLineString in this particular picture,
the polygon with holes has got one
ring defining the outside, which is a set of coordinates, and--
actually, ordered set of coordinates,
and a hole, which is another order set.
And this is the same as the MultiLineString, which also
has two sets of coordinates.
And so on and so on.
So, taking half a step back and thinking, what we have actually
got here, we see that there is commonality
in the different structures themselves,
how the data is represented underneath.
You can see there a point, single coordinate, LineStrings,
LinearRings, et cetera, an array of coordinates,
and so on with different nesting depths.
So the approach then is to reduce this
from having to write the code seven times to having
to write the code four times, and then
implement this common code in private structs, which
are internal to the package.
And then we, the exported types embed these private structs,
which have methods implemented on them.
And with a little bit of wrapping,
we actually get a reasonably usable API.
What does this actually look like?
I'll go through step by step.
So the top level coordinate contains
a single n-dimensinoal point.
This has the layout and the stride from before.
Flat coords I'll explain in a moment.
But for a single coordinate, it's
just the values of that particular coordinate.
Then our [INAUDIBLE] exploited type just anonymously
embeds that particular structure.
geom1, which is this one-level depth we use for LineStrings
and MultiPoints, actually doesn't need much more
than what's in geom0.
But now, instead of having just one coordinate embedded
in our flat coordinate's array, we have them sequentially,
one after the other, in the flat coordinate's array,
every stride elements.
We can work out how many elements
we've got because we know the overall length of the slice.
We divide that by the stride.
That gives us the number of points in our MultiPoint
or our LineString.
For the next level up, MultiLineStrings here,
we use the same--
we embed all the coordinates into this single flat array.
That has some advantages.
But now we need to know which set of coordinates,
or range of coordinates within that array, correspond to which
particular LineString.
And so we maintain an extra ends slice,
which tells us the index of the end of each line,
or each component.
This embedding into flat coord stuff
has a couple of nice effects.
It means that we can write some code that operates on geom0s.
I'll give an example of that in a moment.
And then we get this code also used
for the other geometry types.
It has the most performance effects.
By embedding it into a single linear array,
you see it is very cache friendly.
CPUs are really good at just churning
through data when it's already in the cache lines,
ready to load.
If you use nested arrays, even though it's often easier
to write the code, the actual memory used
ends up scattered over your memory.
You might get page faults.
Stuff's not necessarily in cache.
And, in some benchmarking, I've found
that, by lining up everything out linearly in memory,
I've got about a 30% speed boost from that, which
is quite significant when you're dealing with larger geometries.
And it was nice because, even though Go is not the fastest
language around, it gave it good performance, good usable
performance.
What does this finally look like?
So three examples here-- firstly, computing the bounds--
I haven't given the code [INAUDIBLE]
because, basically, if you're computing
the bounding box of any particular geometric object,
the actual structure of the object doesn't matter at all.
You just care what the points are.
So you could just iterate over all your coordinates,
compute the minimum and maximum in each dimension,
and you get the bounds.
So this single implementation of bounds
now works for all seven geometry types, all--
and no matter how many dimensions there
are in the ordinate type.
This doesn't quite work all the ways, particularly
when it comes to return values.
So this example of set coords in a LineString, which
replaces the coordinate set in the existing LineString-- we
need to return a LineString type from this.
This is useful for--
you just thought you want to keep track of the types.
It's useful for method chaining.
But if we write this method on geom1,
which is our underlying data structure for things which have
arrays of coordinates, we cannot return a geom1 and just then
use it as a LineString elsewhere.
So we have to write an extra wrapper function, which
calls the embedded set coords, which is the common code,
and does the return stuff with the correct type.
That works, I assume, and massively reduces the amount
of code I had to write.
Now I've got-- actually, it turns out,
four coord geom types supporting seven different
publicly exported types.
The final one, which I'll talk very quickly about, very
briefly about because it's not my project,
but it's very cool--
this is the only bit of code generation that I'm now using.
It's a project.
It's called goderive.
And I have it open, hopefully.
And it's this [INAUDIBLE] person, next generation code,
codegen for Go.
What this does is, effectively, it
analyzes your Go code ahead of time--
I'm sorry, offline-- generates common methods
which are either annoying or difficult to get right for you.
The way you use it is actually very straightforward.
This is my deep copy method, which
I want every type to support.
All I write is I return derive clone LineString.
What matters here is goderive will pick out this derive clone
section and go, hey, I need to build a clone method for this.
It does.
It works out the types.
And it then generates the actual safe clone method from this.
This is actually-- Go is a little bit recursive.
There's a code for deep copy 2, which is
all [INAUDIBLE] generated code.
It does just full structural analysis.
But this just works.
I've found it to be much less painful to use than repeating
these methods myself.
Now it's one line rather than multiple lines.
And, of course, it's much less error-prone, for example, here.
The generated code includes proper nil checking.
It just works better.
So I'm using goderived, then cover these basic examples.
And that's it basically-- so surviving without generics,
the [INAUDIBLE],, I think, simplifying my requirements,
to just eliminate one of the combinations
of the causes of complexity.
We even compile time checks to runtime.
Yes, this is a little bit painful.
But it works-- exploiting the structure of the problem
to reduce the code that I had to write
and a little, just a bit of code generation here and there.
That's it.
Thank you.
[APPLAUSE]
[MUSIC PLAYING]