Flattening a nested map [closed]

We're migrating our streaming ETL application from Python into Clojure, the hottest part of the code isn't yet performing as well as our existing implementation. This looks to be down to the algorithmic complexity of our flattening function.

Take a nested map, flatten the data structure and rename keys. We take data from multiple sources and have to smudge the data to fit a legacy format. For this all of the keys/values need to be at the root level of the map with the correct keys. Any 'new' keys can be left as is and not renamed.

The transformation was originally a threading macro, with a flatten and a set/rename-keys, this has been improved to rename variables while looping through each level of the map. The flatten however still accounts for ~80% of the time spent processing a record.

An example input would be as follows:

{:foo {:foo-host "host-1" :user {:foo-user "user-1" :foo-id "id-1"}}
:bar {:bar-var "potato"}}


With an expected output of:

{:host "host-1" :user "user-1" :id "id-1" :var "potato"}


We've gone through and removed any java reflection, and type hinted the hottest parts of our code so no more gains can be found there. The last slow pieces of code are as follows:

(def match-table {:foo-host :host
:foo-user :user
:foo-id :id
:bar-var :var})

(defn flatten-record
"Take a nested record and recursively flatten."
[^clojure.lang.PersistentArrayMap record]
(into {}
(for [[k v] record]
(if (map? v)
(flatten-record v)
{(get match-table k k) v}))))


The flatten-record function consumes the stack as it's lacking any tail call optimisation, trampoline may be a better solution? The records transformed are a maximum of 5 deep, so there's no risk of a recursion overflow.

I'm mainly concerned about performance here, so am open to any hints!

Larger examples are available here.

closed as off-topic by 23fc9a62-56de-47fb-97b4-737890, Graipher, Vogel612♦, Marc-Andre, Malachi♦Jan 19 '17 at 17:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

• I don't like type hinting ^clojure.lang.PersistentArrayMap. For any map with more than 16 entries, this fails. ^clojure.lang.APersistentMap might be better. – Thumbnail Jan 18 '17 at 16:12
• It's actually ^flatland.protobuf.PersistentProtocolBufferMap in reality as it's protobuf we're deserialising. I just grabbed that as an example. Cheers for that though as I didn't know that behaviour. – Sam Pegler Jan 18 '17 at 16:24
• You should post the real code and as complete as possible/necessary. The less you show us, the harder it gets to recommend any changes. – Graipher Jan 19 '17 at 9:29
• Not sure how this has been marked as off topic, the only change is I'm passing in a marginally different data structure. The hot part of the code is still whats been presented. – Sam Pegler Jan 20 '17 at 10:16

A couple of things to try:

• You assemble a map at every level of nesting. It is probably quicker to pass up sequences of key/value pairs.
• Even the single entries return a map. We can cope with a MapEntry directly using reduce instead of for.

We might end up with ...

(defn flatten-record [record]
(reduce
(fn [a [k v]]
(if (map? v)
(into a (flatten-record v))
(conj a (clojure.lang.MapEntry. (match-table k k) v))))
[]
record))


I'm assuming it's quicker to build a MapEntry than a small vector or list.

The above returns a sequence. We have to convert the product into a map:

(def example-input {:foo {:foo-host "host-1" :user {:foo-user "user-1" :foo-id "id-1"}}
:bar {:bar-var "potato"}})

(into {} (flatten-record example-input))
;{:host "host-1", :user "user-1", :id "id-1", :var "potato"}


The recursive call of flatten-recordis not in tail position, so neither recur nor trampolineare available.