Lisp Programmers Knows The Value Of Everything And The Cost Of Nothing - Alan Perlis

Our team at Walmart are well known for our use of Clojure and GraphQL.

As I've said recently, if you are doing it right, you're creating an orchestration layer, and that's the bread and butter of our team; we're responsible for customer purchase history - your history of in-store transactions and on-line orders at Walmart. Other teams write the front end (web, iOS, and Android) that allow our customers to view their orders, initiate returns, reorder products, and so forth - our job is to facilitate the efforts of those front end teams by exposing all the necessary data, sliced and diced and organized for their convenience.

That means that we need to interact with many (many) back-end systems, then integrate all the data about the customer, their orders, product information, details about returns ... this list goes on and on.

And we have to do this fast. Part of Walmart's home page is based on our service, so we're on a tight performance budget to meet our service level agreements.

A recent cross-team stress test revealed some problems in our service; partly our cluster was too small for the amount of simulated traffic, but at the same time, we also determined (using JDK Mission Control) that we had a fair amount of CPU bound, not I/O bound, performance issues.

Part of this was due to some inefficiencies in Lacinia, since corrected, but we also found other hot-spots specific to our application's code.

The Challenge

One hot-spot in particular was ... interesting. As I mentioned above, our code does a lot of integrating and organizing data from multiple systems; internally, a major piece of that was the "pre-processed order line", a map that contains a flattening of data from many systems around a single line of a single order; we then use that pre-processed data to organize order lines into categories and groups and generate the final GraphQL structured output.

Roman defined a defrecord for this PreprocessedOrderLine, and just using that had some measurable benefits, but also introduced a new hot-spot: constructing the PreprocessedOrderLine record itself.

We ended up with three bad options:

• Create a hash map, then call the map->PreprocessedOrderLine constructor function - We're creating a map to avoid the cost of creating a map?

• Create an empty PreprocessedOrderLine record, then use assoc to add in the keys and values - We're creating a record then doing 60 mutations on it?

• Use the ->PreprocessedOrderLine constructor function, and pass 60 positional arguments into it - Although nominally just a wrapper around new, if there are more than 20 parameters Clojure creates a much less efficient variadic function.

Which leaves us with:

• Invoke the constructor directly

But this approach didn't sit well from a maintainability viewpoint; we frequently add new keys (now, new fields) to this record, and have to be very careful at construction time to pass all the parameters to the PreprocessedOrderLine constructor in exactly the right order.

What to do? Well, the nature of problem solving in Clojure is to look at where you are, look at where you want to be, and find the way to bridge that gap.

Bridging That Gap

My thinking was this: What if we had an additional constructor for the record, kv->PreprocessedOrderLine, that would accept key/value pairs (like the hash-map function), but would instead figure out the correct parameters, in the correct order, to invoke the PreprocessedOrderLine instance constructor?

For this to make sense, we'd need to figure out how to map keyword keys to PreprocessedOrderLine constructor argument positions. And for this to not be a new hot-spot, the ordering calculation would have to happen once, at compile time, not on each execution of kv->PreprocessedOrderLine.

Unavoidably, since we're talking about moving what would normally be execution time behavior to compile time, we're talking about writing a macro.

My goal here was to write a new macro, defkvrecord, whose purpose would be to do everything that defrecord does, but then add a third way to construct a record instance, the kv-> prefixed macro.

Here's where we'll end up:

(defkvrecord Point [x y z])
=> #'user/kv->Point

We can define our record type, as normal.

(kv->Point :y 2 :z 3 :x 1)
=> #user.Point{:x 1, :y 2, :z 3}

Evaluating the kv->Point macro results in a new instance of Point, and the order of the keys doesn't matter.

(macroexpand-1 '(kv->Point :y 2))
=> (new user.Point nil 2 nil)

macroexpand-1 shows shows how kv->Point expands into a new constructor call. Unspecified fields receive a nil.

(macroexpand-1 '(kv->Point :y 2 :color :red))
=> (clojure.core/assoc (new user.Point nil 2 nil) :color :red)

When extra keys, not matching a field, are provided, a call to assoc is used to add those extra keys.

(doc kv->Point)
-------------------------
user/kv->Point
([& key-values])
Macro
  Factory function for class user.Point taking keywords and field values.
=> nil

The macro has proper documentation.

It's worthwhile to reflect here that in this scenario, our final goal is to create a macro that defines another custom macro.

If writing a macro is potentially shooting yourself in the foot, what is this? I guess it's building a machine to shoot yourself in the foot, automatically.

The Solution

It's intimidating to jump from nothing to the final implementation of the defkvrecord macro; instead, let's break our thinking down into smaller steps.

First, imagine just writing kv->Point by hand, but as a function:

(defrecord Point [x y z])

(defn kv->Point 
  [& key-values]
  (let [kv-map (apply hash-map key-values)
        params (map kv-map [:x :y :z])]
    (apply new Point. params)))

This is the general idea; but note that this code won't actually work, - I've used apply with new, which won't compile because new is a special form. Let's ignore that for the moment.

What's important is that we go from keys and values, to a map, to a correctly ordered list of constructor parameters.

Next, let's handle the case where there are keys that don't match fields:

(defn kv->Point
  [& key-values]
  (let [field-kws [:x :y :z]
        kv-map (apply hash-map key-values)
        extras (reduce dissoc kv-map field-kws)
        extra-kvs (seq (reduce into [] extras))
        params (mapv kv-map field-kws)
        point (apply new Point. params)]
    (if extra-kvs
      (apply assoc point extra-kvs)
      point))) 

Here, extras is a map of any keys that don't match a field; we convert that to a seq of keys and values as extra-kvs and, if there are any, we use apply assoc to add them to the Point record.

At this point, we're ready to build the kv->Point macro:

(defmacro kv->Point
  [& key-values]
  (let [field-kws [:x :y :z]
        kv-map (apply hash-map key-values)
        extras (reduce dissoc kv-map field-kws)
        extra-kvs (reduce into [] extras)
        params (mapv kv-map field-kws)
        base (concat (list 'new user.Point) params)]
    (if (seq extra-kvs)
      (concat (list 'assoc base) extra-kvs)
      base)))

Remember, a macro returns forms that will be evaluated; this is often done using the syntax quote, but it is also valid to just build up the forms using list and concat, as we've done here.

Now, in terms of generalizing from this specific record type to any record type, we need to adapt for:

• The correct kv-> macro name
• The actual field names
• The actual class name

In addition, we want (doc kv->Point) to work correctly.

Knowing how we built to this point, the final code should not be too daunting to understand:

(defmacro defkvrecord
  "Extension to clojure.core/defrecord, but adds an additional macro, kv->RecordType,
  that accepts keyword keys and values and constructs an instance of the record directly,
  via its constructor.

  This is intended for use with records that have a very large number of fields, and
  where creating a map to invoke the record's map-> constructor is a performance hotspot;
  this code is more manageable than attempting to call the ->RecordType positional
  constructor function, which is untenable when there are more than a few fields.

  The macro is of the form:

    (defmacro kv->RecordType [& key-values] ...)

  The keys are keywords, and the values are expressions that will be plugged into the new record
  instance via its constructor (when the keyword matches the name of a field of the record)
  or via an optional call to assoc (after the record has been constructed).

  Any field whose value is not supplied as a key value pair is passed to the constructor as nil."
  [record-name fields & opts+specs]
  (let [strip-ns (fn [sym] 
                   (with-meta (-> sym name symbol) 
                              (meta sym)))
        record-name' (strip-ns record-name)
        kv-symbol (symbol (str "kv->" record-name'))
        ns-part (namespace-munge *ns*)
        classname (symbol (str ns-part "." record-name'))
        field-names (map strip-ns fields)
        field-kws (mapv #(-> % name keyword) fields)]
    `(do
       (defrecord ~record-name' [~@field-names] ~@opts+specs)
       (defmacro ~kv-symbol
         {:doc ~(str "Factory function for class "
                      classname 
                      " taking keywords and field values.")
          :arglists '([& ~'key-values])}
         [& key-values#]
         (let [kv-map# (apply hash-map key-values#)
               extras# (reduce dissoc kv-map# ~field-kws)
               extra-kws# (seq (reduce into [] extras#))
               params# (map kv-map# ~field-kws)
               base# (concat (list 'new ~classname) params#)]
           (if extra-kws#
             (reduce concat (list 'assoc base#) extras#)
             base#))))))

This is the final version of defkvrecord; it's more complicated since we need to go from a list of field symbols to the list of field keywords and we have do some extra work - duplicating code from defrecord's implementation - to work out the class name and other details.

Still, in 27 lines of code, we've added a significant extension to Clojure's built-in record support, and done so without compromising on performance.

In the long run, going from map->PreprocessedOrderLine to kv->PreprocessedOrderLine changed the time to instantiate a single instance from 11.5 microseconds to 104.0 nanoseconds, a speedup of about 99%. Of course, it would be necessary to instantiate hundreds of PreprocessedOrderLines per request to shave even a single millisecond off of the request processing time, which calls into question the usefulness of the entire exercise.

Wrap Up

This was a fun journey because the end result was a case of having your cake and eating it too - we got the improved performance without any penalty in terms of the maintainability of our application's code.

And finally, a bonus tip: when developing macros, always (set! *print-meta* true). You need to see the meta-data on the forms your macros output!