Benchmark of flattening nested maps ({ "parent": { "child": 123 }}` -> `{ "parent.child": 123 }): Recursion vs. iteration

flatten_test.go

package main

import (
	"encoding/json"
	"strings"
	"testing"
)

var nested map[string]interface{}

func init() {
	js := []byte(`
		{
			"a": {
				"b": {
					"c": 2,
					"d": {
						"e": [1]
					}
				},
				"f": {
					"g": 3
				}
			},
			"h": 123,
			"i": {
				"j": 123,
				"k": {
					"l": 123
				}
			}
		}
	`)
	json.Unmarshal(js, &nested)
}

func BenchmarkFlattenRecurse(b *testing.B) {
	b.ReportAllocs()
	for n := 0; n < b.N; n++ {
		b.StopTimer()
		mp := CopyMap(nested)
		b.StartTimer()

		FlattenRecurse(mp, nil, ".")
	}
}
func BenchmarkFlattenIterate(b *testing.B) {
	b.ReportAllocs()
	for n := 0; n < b.N; n++ {
		// CopyMap is used because the function empties the map
		// on each run.
		b.StopTimer()
		mp := CopyMap(nested)
		b.StartTimer()

		FlattenIterate(mp, ".")
	}
}

func FlattenRecurse(m map[string]interface{}, keys []string, delim string) map[string]interface{} {
	var (
		out = make(map[string]interface{})
	)

	flattenRecurse(m, keys, delim, out)
	return out
}

func flattenRecurse(m map[string]interface{}, keys []string, delim string, out map[string]interface{}) {
	for key, val := range m {
		// Copy the incoming key paths into a fresh list
		// and append the current key in the iteration.
		kp := make([]string, 0, len(keys)+1)
		kp = append(kp, keys...)
		kp = append(kp, key)

		switch cur := val.(type) {
		case map[string]interface{}:
			// Empty map.
			if len(cur) == 0 {
				newKey := strings.Join(kp, delim)
				out[newKey] = val
				continue
			}

			// It's a nested map. Flatten it recursively.
			flattenRecurse(cur, kp, delim, out)
		default:
			newKey := strings.Join(kp, delim)
			out[newKey] = val
		}
	}
}

// FlattenIterate iteratively flattens a nested map.
// eg: `{ "parent": { "child": 123 }}` becomes `{ "parent.child": 123 }`
// This is an (inefficient) prototype that iterats the parent map over and over
// until keys are "drained" and deleted from mp.
// WARNING: This mutates and empties the incoming map `mp`.
func FlattenIterate(mp map[string]interface{}, delim string) map[string]interface{} {
	var (
		out  = make(map[string]interface{}, len(mp))
		last = mp
	)

	// Bencharked and picked against strings.Join([]key) and string + concatenation.
	key := strings.Builder{}

	for {
		// If the map is empty, we're done.
		if len(mp) == 0 {
			break
		}

		// Start iterating over the current "view". On the first run, this is
		// the full incoming map.
		for k, v := range mp {
			// Form the flat key while iterating deeper.
			// parent. child. next. ...
			key.WriteString(k)
			key.WriteString(delim)

			// If the current value is a nested map, break the iteration of the parent
			// view and set the view to be sub map. This causes the iteration to restart
			// from the outerloop until all items of the sub maps are iterated and the
			// empty ones deleted.
			sub, ok := v.(map[string]interface{})
			if ok {
				// Sub map is empty. Delete it and reset the iteration view.
				if len(sub) == 0 {
					key.Reset()
					delete(mp, k)
					mp = last
					break
				}

				// Sub map isn't empty. Set the view to iterate the submap and restart
				// iteration.
				mp = sub
				break
			}

			// Reached a value that isn't a map. Add the value and the flattened key to out.
			// eg: out[parent.child.next] = 123
			ks := key.String()
			out[ks[0:key.Len()-len(delim)]] = v

			// Delete the item from the map and reset the flat key tracker.
			// Reset the iteration.
			delete(mp, k)
			key.Reset()
			mp = last
			break
		}
	}

	return out
}

func CopyMap(m map[string]interface{}) map[string]interface{} {
	cp := make(map[string]interface{})
	for k, v := range m {
		vm, ok := v.(map[string]interface{})
		if ok {
			cp[k] = CopyMap(vm)
		} else {
			cp[k] = v
		}
	}

	return cp
}