Was trying to figure out what defrecord does in the impl of ILookup it generates and I absolutely do not understand that magic. Essentially it amounts to (get __extmap key)  and I can’t even figure out how this magical __extmap gets into scope (a global or some special runtime thing?) and this isn’t even used. Confused

zerusski on Clojurians Slack

This post on Clojurians sent me down the rabbit hole looking for where this “mysterious” __extmap comes from. It really isn’t obvious at first, but when I found it, it was “wow” times “duh”.

The conclusion

The __extmap (short for “extension map”) isn’t created until you assoc something into a record. You can check its initial value by calling .__extmap on a record: nil. The “magic” is that you can assoc into nil and it will kindly create a new map for you:

user=> (assoc nil :a 42)
 {:a 42}

This is surprising behavior (at least it sure surprised me), but I figure it’s why assoc-in works. In the case of records this means that the nil __extmap will have the values that are assoc‘d into the record other than its defined field (thus “extension map”). associng into the named record fields will “override” the field without using __extmap:

user=> (defrecord MyRecord [my-field])
user.MyRecord
user=> (let [record (->MyRecord "hello")]
         ;; empty by default
         (println (.__extmap record))
         ;; assoc in "extension field"
         (println (.__extmap (assoc record :foo "bar")))
         ;; assoc into record field
         (println (.__extmap (assoc record :my-field 42))))
nil
{:foo "bar"}
nil

The wrong way

At first I was really confused. defrecord (and emit-defrecord don’t do anything to create __extmap, just use it as a symbol. So where does it come from then?

I ran rounds looking into the Clojure Compiler, trying to track down this “mysterious” __extmap. I looked at the RecordIterator too, but that just gets called by defrecord instead, closing the loop.

The right way

I was at the point of questioning the laws of physics (and computer science) and the existence of the universe in general, but first I appealed to common sense and questioned myself instead. Is the initial assumption (that valAt on a record just resolves to (get __extmap key)) really correct?

Turns out it isn’t. valAt only tries geting from the __extmap if the key requested isn’t one of the record’s defined fields. The __extmap line is the default (fallback) of the case in the definition.

`(valAt [this# k# else#] 
    (case k# ~@(mapcat (fn [fld] [(keyword fld) fld]) 
                        base-fields)
          (get ~'__extmap k# else#)))

The mapcat generates keyword-value pairs out of base-fields which are then unquote-spliced into the case. This means that “lookup” of record fields is a “constant time dispatch” and not a map lookup: case generates the bytecode for a Java tableswitch which does O(1) lookup (except if there are hash clashes for the conditions in which case it falls back to a lookupswitch and yells a reflection warning). If the requested key isn’t one of the fields (the else of the case) it goes on to check the __extmap for the key, which is a good old Clojure map (or nil) meaning map lookup.

This can be reproduced by any macro generating a case to mimic a map, with the catch that case requires constant tests (so you can’t test against a value passed into your function for example). This smells like with enough macro magic it could be used to create O(1) lookup map types, though I’m not sure just yet if it’s actually feasible.