From 266c83777e21943f98cef4cb6cede367f083ba51 Mon Sep 17 00:00:00 2001
From: Yedidya Feldblum <yfeldblum@fb.com>
Date: Tue, 10 Jan 2017 11:57:31 -0800
Subject: [PATCH] Fix an inefficiency in json-serializing a dynamic with sorted
 keys

Summary:
[Folly] Fix an inefficiency in json-serializing a `dynamic` with sorted keys.

The inefficiency is that, at each level of the `dynamic` which is map-typed, we effectively make a full copy of the `dynamic` object. This can be expensive.

Reviewed By: Gownta

Differential Revision: D4389671

fbshipit-source-id: 223739397f913d3e65a421a9a4dcb089ec757ec6
---
 folly/json.cpp | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/folly/json.cpp b/folly/json.cpp
index 6f8ecdbc..4449e779 100644
--- a/folly/json.cpp
+++ b/folly/json.cpp
@@ -15,7 +15,11 @@
  */
 
 #include <folly/json.h>
+
+#include <algorithm>
 #include <cassert>
+#include <functional>
+
 #include <boost/next_prior.hpp>
 #include <boost/algorithm/string.hpp>
 
@@ -111,13 +115,13 @@ private:
     indent();
     newline();
     if (opts_.sort_keys) {
-      std::vector<std::pair<dynamic, dynamic>> items(
-        o.items().begin(), o.items().end());
-      std::sort(items.begin(), items.end(), [](auto const& a, auto const& b) {
+      using ref = std::reference_wrapper<decltype(o.items())::value_type const>;
+      std::vector<ref> refs(o.items().begin(), o.items().end());
+      std::sort(refs.begin(), refs.end(), [](ref a, ref b) {
         // Only compare keys.  No ordering among identical keys.
-        return a.first < b.first;
+        return a.get().first < b.get().first;
       });
-      printKVPairs(items.begin(), items.end());
+      printKVPairs(refs.cbegin(), refs.cend());
     } else {
       printKVPairs(o.items().begin(), o.items().end());
     }
-- 
2.34.1