Multi-Backend Support in the cartokit Compiler

This post comes originally from a notebook of mine on Observable. Head over there to view it in its original context with interactive editing.

Note: This notebook is part of my final project submission for CS265: Compiler Optimization and Code Generation at UC Berkeley. For that reason, it is slightly more academic-flavored (academish?) than my other notebooks.

Over the past two years during my PhD at Berkeley, I’ve been developing a new direct manipulation programming system for geospatial analysis and visualization, cartokit. Selfishly, I think it’s pretty neat! At a high level, cartokit allows users to load, transform, and style geospatial data using familiar interactions from direct manipulation interfaces (e.g., Figma, Adobe Illustrator) while simultaneously generating JavaScript programs that produce a corresponding interactive map. The system’s design was heavily influenced by my prior observational research in the data journalism, Earth and climate science, and social science communities, in which I found that many domain expert mapmakers are extremely proficient GUI users but struggle to translate static map designs to code. cartokit is an attempt to fill that gap, marrying the best of direct manipulation with the rigorous correctness guarantees of a formal programming system.

Internally, cartokit is structured a lot like a traditional compiler, translating programs written in a high-level, JavaScript-embedded domain-specific language (DSL) into plain JavaScript programs using Mapbox GL JS. Users modify DSL programs through interface interactions, which produce small syntactic diffs ($\delta$) that are applied to the current program in a patch procedure. On every call to patch, the compiler’s backend performs a lightweight analysis of the updated DSL program and generates a corresponding updated JavaScript program. But that’s all the under-the-hood stuff — here’s what that process looks like in practice from a user’s perspective.

Since cartokit’s earliest versions, I have only targeted JavaScript paired with Mapbox GL JS as the system’s primary backend. However, the ecosystem of languages and libraries available for interactive mapping today is incredibly rich, and the choice to use one pairing over another — or even switch between them — is highly context-dependent. MapLibre GL JS is an increasingly popular alternative with a similar WebGL2 API and first-class support for a new, efficient tile format for geospatial data, PMTiles. deck.gl has best-in-class rendering performance and is a popular choice for geospatial datasets in the 1+ million feature range. D3 and Leaflet are older standbys, but have been the de facto standard in newsrooms for nearly a decade. Extending beyond the JavaScript ecosystem, the Python and R ecosystems have their own bindings to these renderers to facilitate interactive cartography from languages with first-class geospatial analysis capabilities.

Given this abundant landscape of tooling, I’ve long wanted to implement “multi-backend” support in cartokit — in essence, code generation for arbitrary combinations of language-library targets. In addition to being a feature several cartokit users in the data journalism community have requested, it also aligns with my deeper dreams of making cartokit’s DSL the LLVM of the mapping world. And as a research venture, implementing multiple backends is a great way to assess whether my DSL is expressive enough to support diverse language and API constraints while enabling backend-specific optimization.

Objectives

So that’s all well and good, but what does multi-backend support entail concretely? For the scope of this work, I decided to focus on two primary objectives.

1. Extending cartokit’s code generator to support MapLibre GL JS as a library target and TypeScript as a language target. Accomplishing this objective would give users a total of four possible backends:

   • Mapbox GL JS with JavaScript
   • Mapbox GL JS with TypeScript
   • MapLibre GL JS with JavaScript
   • MapLibre GL JS with TypeScript

   It may not seem like much, but this is a 4$\times$ growth in the space of possible platforms cartokit can support. Anecdotally, I’ve seen all four in use in production in my time in industry and the newsroom.

2. Supporting dynamic, on-demand loading of compiler backends. With more backends comes more code, and with more code comes larger bundles that need to be fetched, parsed, and executed by the browser’s JavaScript engine (e.g., V8, JavaScriptCore, etc.). Large bundles end up being a problem for several reasons:

   • Network speed. If a user is on a slow 3G or 4G connection — or even if they’re using UC Berkeley’s WiFi on a bad day — a larger bundle increases the time it takes for all of your code from your web server to reach the user’s browser.
   • JavaScript parse time. Once your code has been transferred to the client, the JavaScript engine needs to parse it! Thankfully, parsing JavaScript in modern engines is “blazingly” fast. Still, more code to parse means longer parse times.
   • JavaScript execution time. We’ve fetched the code, we’ve parsed it, and now we need to run it! Again, it’s the same story here — more code to execute amounts to more time before the main content of our interface loads.

   In short, adding more backends could have compounding negative impacts on application performance if we’re not careful. Thankfully, modern JavaScript build tools like Rollup have a great solution for this problem: code splitting. In essence, code splitting allows you to dice your application code into separate chunks that can be loaded efficiently (e.g., via HTTP/2 multiplexing) or “just-in-time” (i.e., dynamically) using JavaScript’s dynamic import statement. Code splitting is going to play a big role in making multi-backend support feasible from a performance perspective.

Implementation

With our objectives in place, let’s dive into the implementation. We’ll discuss the system’s previous single-backend architecture, the evolution of this architecture to support multiple backends, and how I added support for dynamic, on-demand loading of backends.

The Single-Backend Architecture

cartokit’s backend through v0.5.3 was structured as a hierarchy of small code generation functions (hereafter, codegen* functions) that each peek at specific portions of the cartokit DSL program to generate a JavaScript program fragment (i.e., a portion of the final output program). In this setup, functions at a higher level in the hierarchy determine where program fragments generated by callees are inserted into the generated program. All-in-all, pretty straightforward! The figure below provides a representation of the call graph for the code generation algorithm.

One observation about this structure is that the codegen* functions are skewed more closely towards the API structure of the compilation target (i.e., Mapbox GL JS) than the source program (i.e., the cartokit DSL program). For example, the cartokit DSL has no notion of a data source, but our code generator has a dedicated function (codegenSource) that produces JavaScript code for a Mapbox GL JS source. I think this is largely a relic of the fact that, when I started out, I was really only thinking about supporting one backend. At the time, it just made sense to me to skew code generation more closely to that target. However, an alternative design could just as easily skew towards the DSL. For example, I could have captured the creation of a data source and a layer together in a single codegenLayer function and never created codegenSource. This would more closely mimic the design of cartokit’s DSL, which has its own layer abstraction (CartoKitLayer) that stores a map layer’s geospatial data alongside its stylistic definition. Alas, choices in language design — can’t escape them!

The relevant portions of cartokit’s original backend can be found here.

Evolving the Implementation to Support Multiple Backends

While evolving cartokit to support a new library (MapLibre GL JS) and language (TypeScript) backend, I actually decided to reuse much of this same structure. Practically, this meant separating each backend into its own collection of JavaScript modules, each with a single entry point (this will be important later). In source, this amounted to creating a separate directory of code generation functions for every language-library combination (e.g., lib/codegen/mapbox/javascript/codegen*, lib/codegen/maplibre/typescript/codegen*, etc.). While the given hierarchy of code generation functions (the one shown in Figure 2) is consistent across all backends, this is not a strict requirement of the approach — we could arbitrarily add, remove, or restructure functions independently for a new backend as needed.

From one perspective, this sounds like a maintenance nightmare — every new addition of a language or library target requires adding a lot of new code. Moreover, for certain targets where elements of code generation are basically identical (e.g., fill-* or stroke-* expressions in Mapbox GL JS and MapLibre GL JS), we now have multiple versions of every codegen* function floating around in source. This is an even more pronounced problem for the addition of the TypeScript backends, which — owing to TypeScript’s pretty darn good type inference — can be fully identical to their JavaScript equivalents in many cases.

But, from another perspective, this architecture also allows for extreme specialization of generated code that does not require run time computation. For example, my first attempt at adding TypeScript code generation involved just passing a Boolean flag, typed, to all of the JavaScript codegen* functions. Then, at run time, each function could check the value of the typed flag to determine whether and where it needed to insert static type annotations (e.g., geojson: FeatureCollection) or type assertions (e.g., await response.json() as FeatureCollection) in its template. Something like this:

In practice, I found that this approach quickly became unwieldy. Nearly every template became littered with conditionals checking the typed flag, which made them more difficult to read, check, and extend to new features. Moreover, while evaluating a conditional has almost no run time overhead, it is still more overhead than having no conditionals at all!

Moreover, when it comes to handling library discrepancies in code generation, full separation of backends is almost required from both a maintenance and performance perspective. While Mapbox GL JS and MapLibre GL JS have (intentionally) very similar APIs, they do diverge significantly in areas where I’m targeting future work (e.g., Mapbox GL JS has no support for MapLibre GL JS’s addProtocol API and MapLibre GL JS does not yet support custom projections). Moreover, while prototyping deck.gl code generation as part of this project, I’ve found that the code generation template boundaries (e.g., layers, sources, paint, transformations, etc.) that I use for Mapbox GL JS and MapLibre GL JS feel stretched by deck.gl’s APIs. For example, deck.gl’s definition of layers — which colocate data and style properties — actually matches the cartokit DSL much more closely. For this backend target, a codegenSource function just doesn’t make a whole lot of sense.

Generalizing Program Analysis

While I embraced the “separate-all-the-things” mentality when it came to code generation, I did find one area where generalization made more sense — analysis of the cartokit DSL program. cartokit’s analysis phase is critical for code generation and handles determining:

1. Requirements around the program’s library and file imports. For example, if a user triggers an interface action that requires geometric transformation of the underlying GeoJSON data (e.g., changing a Choropleth layer to a Proportional Symbol layer), cartokit needs to import specific functions of the Turf.js library (e.g., centroid) to encode this transformation into the program.
2. Requirements around data fetching and asynchronous execution. For example, if a user supplies an API endpoint to a GeoJSON file as a data source, the generated map.on('load') callback can still be marked as a synchronous function using Mapbox GL JS’s and MapLibre GL JS’s support for urls as valid values for a GeoJSON source’s data property. However, if a user triggers an interface action to transform this data in any way, cartokit must fetch the data from the API endpoint and store the result in memory for later local transformation. This involves inserting an asynchronous function, fetchGeoJSON, into the program’s top-level scope, inserting a call site for this function inside the map.on('load') callback and, finally, marking the callback as asynchronous using the async keyword.
3. Requirements around transformation composition. For example, if a user applies both a geometric transformation and a separate tabular transformation to a layer’s GeoJSON data, cartokit needs to compose those transformations in the correct order in the generated program. We do this by importing lodash’s flow function and determining the proper scope for inserting a call to flow that composes the two transformations.

Previously, in the single-backend architecture, analysis of a cartokit DSL program was intermixed with code generation and ran on demand when a particular codegen* function needed information for program fragment production. Now, analysis runs in a separate pass before code generation, mimicking the structure of a more traditional compiler. The information returned from analysis is an Object whose values are Boolean flags indicating whether certain libraries and functions are required; many of these flags are also used as proxies by codegen* functions to insert or elide parts of their program fragments. Every backend takes the analysis Object, in addition to the cartokit DSL program, as input.

Code Splitting and Dynamic, On-Demand Loading of Backends

Earlier, we discussed the negative performance implications of larger bundle sizes. With our multi-backend architecture — in which each language-library pairing has a fully isolated set of code generation modules — it may seem that we’ve set ourselves up for a big performance hit. We now have to load four backends instead of just one. But recall the solution we discussed before: code splitting. If we can effectively split each backend into its own separate chunk, then only one backend will be loaded (i.e., fetched from the web server, parsed, and run over the cartokit DSL program) at a given time. This should give us tantamount performance to our prior single-backend architecture.

The key to making this all work is to pair our build system’s support for code splitting with JavaScript’s dynamic import. cartokit uses Vite as its build tool, which is backed by Rollup under the hood. Rollup automatically code splits modules that are imported dynamically, placing these modules into their own “chunk”. In order to determine the full set of additional modules that should be included in this chunk, Rollup builds and analyzes a module dependency graph. For our purposes, we can exploit this behavior by:

1. Creating a single module entry point for each backend (remember when I said this was important?)
2. Dynamically importing just that module when a new backend is requested by the user

From a code perspective, this is actually pretty lightweight; it looks something like the following:

If we actually pop open the Network tab in the browser on cartokit, we can see this in action! Notice that as I change the choice of backend using the radio buttons in the bottom right corner of the interface, the code generation modules for just the selected language-library backend are requested from the server.

Et voilà! With a few small changes and some big help from modern JavaScript build tooling, we’re now loading new backends on-demand when a user requests them rather than loading them all up front when the page first loads. Beautiful!

Evaluation

With the implementation finished off, my last step was to evaluate my multi-backend architecture. The implementation gave me a hunch that I had successfully enabled this feature without sacrificing correctness of the generated code or system performance. But, until you measure it, you never really know!

Benchmark Suite

As part of my evaluation (and some of my prior research), I developed a set of six benchmarks based on maps published by two national newsrooms: The New York Times and The Washington Post. Using the original data published by these newsrooms, I reproduced each target map in cartokit and recorded the program generated by each of the four backends. The table includes information on each benchmark. LOC (Max) indicates the maximum number of lines of code generated by any of the four cartokit backends to produce the final map. In all cases, the TypeScript / Mapbox GL JS backend generated the largest number of LOC.

Correctness

To start off, I worked to evaluate the correctness of generated programs for each backend. Correctness always feels like a fuzzy notion to me in programming languages. Correct with respect to what? A formal specification? Some imaginary notion of user intent? It’s a can of worms, but for the purposes of this evaluation I used the following criteria:

1. Syntactic and semantic validity of generated programs with respect to the language-library combination of the backend
2. “Perceptual” equivalence to outputs yielded by other backends, as well as the ground truth map

I evaluated the former metric by executing the program generated by each backend in a newly scaffolded Vite project and ensuring (1) syntactic validity, (2) absence of run time errors, and (3) absence of type errors for programs generated by the TypeScript backends. I evaluated the latter metric by a qualitative assessment, comparing the generated maps to each other and the original benchmark. I deemed two maps equivalent if they demonstrated the same visual symbology modulo small rendering discrepancies between libraries. Figure 4 shows one example of what this evaluation looked like, with the original map from The Washington Post, the map developed in cartokit, and the four output maps produced by the four backends.

Results

Excitingly, all six benchmarks met our correctness criteria! Not surprising, and these six benchmarks are only a portion of the program space that cartokit-generated programs can occupy, but hey, it’s closing time on the semester.

Performance

Let’s move on to the more interesting evaluation — performance. On the performance front, I decided to conduct two studies:

1. I benchmarked the run time performance of each backend’s code generation algorithm on the six benchmark maps.
2. I compared the bundle sizes and largest contentful paint (LCP) run times of the single-backend and multi-backend versions of cartokit.

The first experiment aimed to assess the overall performance of cartokit’s code generation while identifying whether any particular language-library backend degraded performance. The second experiment aimed to assess whether code splitting allowed us to preserve the bundle size and initial load performance of the single-backend architecture while opening up the functionality of multiple backends.

I conducted all experiments in Google Chrome 130.0.6723.70 on a laptop running macOS 14.6.1 with a 2.3 GHz Quad-Core Intel Core i7 processor and 32GB RAM.

Setup: Code Generation Performance

To capture code generation run times for each backend, I instrumented cartokit’s source code with calls to the browser’s native Performance API. Specifically, I used performance.mark to delineate start and end points for the algorithm’s execution. For the starting point, I chose the program location just before analysis of the cartokit DSL program began. For the ending point, I chose the program location just after the final program string is generated and just before it is returned to the caller of the algorithm.

I recorded 10 executions of code generation for each of the four backends across each benchmark. This resulted in a total of 240 discrete code generation executions (40 executions per benchmark $\times$ six benchmarks).

Results: Code Generation Performance

Code generation was extremely consistent across backends, with the following median run times for each backend across all benchmarks:

1. MapLibre GL JS with JavaScript: 4.60ms
2. Mapbox GL JS with JavaScript: 4.60ms
3. MapLibre GL JS with TypeScript: 4.60ms
4. Mapbox GL JS with TypeScript: 4.55ms

In many ways, this isn’t surprising. The discrepancies between the implementations of our four backends are quite minor, and all backends currently use the same analysis procedure. Moreover, the benchmarks do not exercise some of the more involved TypeScript code generation (e.g., typing user-defined functions, functions for asynchronous data fetching), meaning that, in many cases, they are identical to the generated JavaScript programs (thanks to type inference). Figure 5 below provides strip plots showing the distribution of code generation run times across each backend and each benchmark. Very consistent, much wow.

Setup: Bundle Size

To measure bundle size for the multi-backend and single-backend versions of cartokit, I summed the sizes of all JavaScript modules requested by the client on initial load. This information was available in the Network Tab of the Chrome Developer Tools.

Results: Bundle Size

Examining the sum size of all JavaScript modules loaded on initial render in a production build, the multi-backend version of cartokit loads 499.1kb while the single-backend version of cartokit loads 665.25kb. Thus, multi-backend support actually decreases our initial bundle size by ≈25%.

This result feels like a resounding success for code splitting. While it may seem paradoxical that we added more code (4$\times$ the number of backends) and yet have a smaller initial bundle, recall how Rollup creates chunks while building cartokit. Previously, in our single-backend architecture, our backend was statically (not dynamically) imported. In this setting, Rollup had no way to infer from the module graph alone that our backend would not be needed for the initial page load and, thus, opted to include it in the main chunk. In our multi-backend architecture, all backends are dynamically imported. The use of dynamic import acts almost like a chunking hint to Rollup here, indicating that a given backend doesn’t need to be loaded until requested. Given that the generated program in cartokit is not shown to the user unless they choose to view it by clicking the View Editor button, it’s actually safe to load none of the backends on initial load. This helps to explain why we actually observe a decrease in initial bundle size rather than a stable value in the switch to the multi-backend architecture.

Setup: Largest Contentful Paint

Beyond bundle size, I also wanted to capture some explicit metric of page load speed across the single-backend and multi-backend approaches. I decided to use Largest Contentful Paint (LCP) for this purpose, which captures the render time of the largest block-level element with text children (relative to when the user navigates to the page). In our case, the largest element fulfilling this requirement is the map itself (or, more precisely, the div element with id="map").

To collect LCP values, I ran Lighthouse 10 times each on the production builds of both the single-backend and multi-backend versions of cartokit.

Results: Largest Contentful Paint

The median LCP across the runs was 0.5s for the single-backend version and 0.55s for the multi-backend version — again, nearly identical. This one was actually somewhat surprising for me. Given that we shaved off roughly 165kb of our bundle, I thought we might see a drop in LCP values. But, I think there are two things at play here:

1. cartokit includes a lot of application code for the user interface, and it’s this code that needs to execute to actually render the map (and, thus, has the impact on LCP). We didn’t remove any of this code using code splitting.
2. cartokit’s bundles are still relatively small. A 400-600kb gzipped bundle is pretty small as far as web applications go these days. And browsers — well yeah, they’re actually, truly blazingly fast.

So, a bit of a womp womp. If I still worked in industry, maybe I could list this 150kb reduction on my KPIs for the quarter. In this instance, it’s just a footnote at the long end of this increasingly unhinged project report. Figure 6 shows a strip plot of each LCP value from our ten runs across each condition.

Conclusion

If you’ve made it this far in this write up, you are either (1) Professor Max Willsey or (2) someone who could probably be spending their time more wisely elsewhere, but who I’m ever so grateful to have in my little corner of nerdery.

Ultimately, I’d call this whole venture a success. Code splitting worked as advertised, the “separate-all-the-things” approach to new backends seems like it has some great runway for the near term, and deck.gl support is already in the works. I’m very excited to roll out this iteration of multi-backend support in v0.7.0 in cartokit, releasing as soon as I finish up some pressing work in my other role as a data journalist in the newsroom at Grist. For the sickos, MapLibre support was added in this PR and TypeScript support is up on a branch. If you liked this post, let me know by hitting me up on Bluesky, @parkie-doo.sh 🦋 Until such time, happy mapping 🗺️