Optimizing PraxisMapper 2: Drawing MapTiles
After loading the initial data set, which is the single slowest operation in the process of setting up a new server, the next most important task for PraxisMapper is drawing maptiles. The current codebase for PraxisMapper went through quite a few improvements to get maptiles to draw quickly.
Improvements
##Change Libraries Originally, I used ImageSharp from SixLabors, as I wanted to do the entire project with managed code. It worked, but as I looked into things, I felt like this could be done faster. Every note on optimization in this library was marked 'todo later'. Eventually, I concluded that it was worth switching to a more performance-focused library and started using SkiaSharp. SkiaSharp was at least twice as fast, even before doing any other optimizations to the maptile drawing logic.
SkiaSharp is a little tricky to get working in Linux, however, so I may re-implement ImageSharp at a later date to make getting cheaper servers running with less effort. The 'secret' motivation to make everything faster and more efficient is to reduce the cost of running the software.
##Reuse Logic PraxisMapper lets you draw a tile in multiple styles, and allows you to write custom styles for drawing game data. So you can have background tiles that match what you'd expect from OpenStreetMap, and then gameplay tiles that tint areas to match a team that claimed an element, or overlays monsters in PlusCode cells where players can encounter them. Making these paths use as much core code as possible helped highlight which parts of code were hot paths that needed attention and care, and made development a little faster than trying to make 2 different rendering paths.
##Saving Images to the Database It was clear early on that since map data itself wasn't going to change often but would be requested very often, it would be best to draw a maptile once and save it for reuse. I chose to save the image to the database. Some people will immediately decry this decision, saying files belong in the file system and not a database. I think it's conditional, and conditions here favor using the existing database.
Tracking metadata is the key reason I went this way. I want to know which PlusCode a maptile covers, which style it's drawn for, when it was drawn and when it expired (or expires). One thing I realized working on gameplay maptiles was that I had to be able to know when to redraw a tile if the underlying data changed, but figuring out which standalone files needed to change from a baseline OSM element was extremely difficult. This meant that the best solution was to index the area covered by each tile in the database, so that I can quickly find all the maptiles that intersect the area that needs updated.
I also prefer this setup for security reasons, since writing files to a folder as a web application means there's a possibility for attackers to use the site as an attack point. Saving all data to a database makes it much more difficult to compromise PraxisMapper and the server it runs on without any write access.
##Do Work Late As I mentioned above, I need to know when a tile needs updated to match underlying data. However, I want the server to be as responsive as possible, so it doesn't redraw every tile as soon as that data changes. All that happens here is a single SQL query to set the expiration date of each maptile that intersects the changed data to DateTime.Now. Then, the next time that map tile is requested, PraxisMapper will notice the tile is expired and redraw it. A baseline maptile is one 8-character PlusCode in size (roughly 1 or 2 city blocks depending on your city), and it's not uncommon for much larger areas to require changing lots of tiles at once. Central Park in NYC takes up about 70 maptiles, for reference.
This also shifts the difficulty of keeping an updated data set to the client, rather than the server. A game written with a PraxisMapper server will need to decide how often it should refresh data and any tricks to save data usage are client-side code. The server only ensures that it gives out the latest, accurate data, rather than being perfectly efficient for all clients.
##Batch Creation Creating maptiles on-demand isn't particularly complicated. However, it's also not particularly fast. Each tile has the overhead of a search, loading data, drawing data, then saving results. It's much faster to load data once and then search that multiple tiles and to save data in batches.
Larry, the main utility for creating a PraxisMapper server, will create maptiles in bulk after loading data from a file. The simple algorithm it uses is to load all the data for a full row of maptiles from the database, and then make a thread to draw each tile in that row, and save all the data when all those threads are complete. The Entity Framework handles all of the database work much faster in batches than when doing single tiles, though it also has a point where its internal tracking logic slows down dramatically.
##Search Style Rules Faster Since all maptiles are drawn by styling rules, it's important that searching those is as fast as possible. This is the most micro-optimization of the changes detailed here, but this is the hottest of hot paths and needs the effort involved.
Styles are a list of tags and values, and a rule for how an element matching those should be drawn. The drawing rule itself is optimized simply by creating all of those paint commands when the server starts up, and pulling those objects in to draw once we get to the actual draw step of maptile creation.
Matching those styles is run once for every element that intersects with the maptile area to draw, and so must be as fast as possible. Since each style can have multiple rules, the fastest way to evaluate them is to return false as soon as any value isn't matched. We also stop searching as soon as we find one matching style, to avoid wasting time searching invalid styles once we have one, so styles with overlapping rules need to be in most-to-least-specific order while searching.
The only rule that can't be evaluated early is an OR style rule, where 1 of X tags must apply, since we can't return false when one of those is missed (we can only do that once ALL of them are missed). So we simply make a flag to indicate if any OR value was found to start, set it if we do find an OR rule, and after all other rules have matched if we DO have an OR match we return true.
With this logic in place and the default style set with 36 rules, PraxisMapper can check 1,600 elements per millisecond with no tags, 14 elements per millisecond that each have 45 tags that don't match anything, or (for a more likely example) 125 elements per millisecond with 9 tags that match the water style rule.
##Learn the Library The most difficult things to draw are elements with holes in them. My original answer for this was to draw the full outline shape, save that to a bitmap, then use a special 'eraser' paint to draw the holes into that bitmap, and then when all the holes were drawn to merge that bitmap back into the original maptile in progress.
Turns out, SkiaSharp automatically cuts out holes if you put the points for that hole in the opposite orientation of the outer edge at the end of the current path. Dramatically faster and cheaper on RAM than my original logic. This point doesn't have a nice mathematical trick or funny moral to it. Just remembering to read the docs and finding the right way to do things will make some stuff faster.
##Retest Everything For a while, I was cropping map elements to match the maptile being drawn, thinking it was faster to trim large areas down than to draw stuff out of bounds. It was, but that was much earlier in development with ImageSharp. After everything else had been done, repeating performance testing discovered that this crop operation was slowing down drawing. So, it was removed and performance increased in line with the number of elements being drawn.
#Results The performance from all of these is good, but it varies on how complex the tiles being drawn are. On a 4 year old home PC, my initial speed were about 14 tiles a second. After all of these changes and improvements, Larry can draw about 150 mostly-empty tiles per second (lakes, fields, other tiles with 1-2 elements being drawn). In busy areas, that drops to 80-90 tiles per second this way. By comparison, hitting the endpoints and drawing on demand will create roughly 5-10 tiles per second, but it will also have to handle all the other requests of an active game in addition. For long-lasting data like baseline map tiles, batching is obviously preferable. Gameplay data that can change frequently is better served with the on-demand code and making sure it's as fast as possible.
(For reference, official OSM tile generation looks like it would be very happy with the on-demand performance that PraxisMapper creates, but their styling rules are roughly 10x more complex, and they don't store NTS geometry. They store individual nodes to maximize storage efficiency instead of runtime speed.)