Question about performance and arrays

[pereyra-m]

Hi!

I'm making some tests and trying to get the fastest way to insert JSON objects into an array.
The thing is that in my tests, it's faster to create an intermediate variable every time like this

  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.emplace_back(std::move(item));
  }

Than avoiding the intermediate variable and inserting directly the elements in the array

  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(
        nlohmann::json({{"description", "value"}, {"lang", "value"}}));
  }

Why is this? Is there something wrong in the second proposal?
Here you have the code I used for testing.

Details

#include "json.hpp"
#include <functional>
#include <iostream>

auto constexpr kIterations{1000000};

void test1() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.push_back(std::move(item));
  }
}

void test2() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.emplace_back(std::move(item));
  }
}

void test3() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(
        nlohmann::json({{"description", "value"}, {"lang", "value"}}));
  }
}

void measureTime(std::function<void(void)> func) {
  auto start = std::chrono::high_resolution_clock::now();
  func();
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << "Time: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end -
                                                                     start)
                   .count()
            << "ms" << std::endl;
}

int main() {

  std::cout << "** Perfomance test ** " << std::endl;

  std::cout << "Intermediate variable and push_back" << std::endl;
  measureTime(test1);
  std::cout << "Intermediate variable and emplace_back" << std::endl;
  measureTime(test2);
  std::cout << "No intermediate variable and emplace_back in place"
            << std::endl;
  measureTime(test3);
  return 0;
}

Output

** Perfomance test ** 
Intermediate variable and push_back
Time: 2424ms
Intermediate variable and emplace_back
Time: 2398ms
No intermediate variable and emplace_back in place
Time: 4687ms

Thank you.

[gregmarr]

The emplace_back function takes the provided parameters and calls the constructor of the type with those parameters. So push_back(std::move(item)) is always going to be at least as fast if not faster than emplace_back(std::move(item)) when the item is fully constructed. You only get savings with emplace_back if you are actually able to construct the element in-place in the vector.

The constructor that takes an initializer list has to do extra work to determine what kind of json it's creating. It's there for readability, not performance.

You are also not optimizing, which significantly reduces the cost. Run your tests again at -O2, just make sure that you actually return the data and use it after you measure the time so you're sure that doesn't get optimized away.

With -O2, the differences between push_back and emplace_back disappear into the noise. You do still see the costs of calling the initializer list constructor to create the object and then the move constructor into the array with the inline version.

You should also look at reserving the space in the array when you know that you're going to be writing a lot of elements:

subArray.get_ptr<nlohmann::json::array_t*>()->reserve(kIterations);

[pereyra-m]

Hello @gregmarr !
Thank you for your answer.

when the item is fully constructed. You only get savings with emplace_back if you are actually able to construct the element in-place in the vector.

You are right. Is it possible to construct the element directly in the vector in this case?

The constructor that takes an initializer list has to do extra work to determine what kind of json it's creating. It's there for readability, not performance.

I see. Can't I use another type of constructor? In the best below I've used literals, but it's slower.

You are also not optimizing.

Below you can see another test, optimizing really changed the final number, but we have the same relative results.

You should also look at reserving the space in the array when you know that you're going to be writing a lot of elements:

This was the fastest. But what happens when I don't know the size before calling the method, does it worth it to do some extra pre-allocation and free the rest at the end?

Details

#include "json.hpp"
#include <functional>
#include <iostream>

auto constexpr kIterations{1000000};

auto test1() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.push_back(std::move(item));
  }
  return subArray;
}

auto test2() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.emplace_back(std::move(item));
  }
  return subArray;
}

auto test3() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(
        nlohmann::json({{"description", "value"}, {"lang", "value"}}));
  }
  return subArray;
}

auto test4() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(
        nlohmann::json::object({{"description", "value"}, {"lang", "value"}}));
  }
  return subArray;
}

auto test5() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(
        nlohmann::json::parse(R"({"description": "value","lang": "value"})"));
  }
  return subArray;
}

auto test6() {
  auto subArray = nlohmann::json::array();
  for (auto i = 0; i < kIterations; ++i) {
    subArray.emplace_back(R"({"description": "value","lang": "value"})"_json);
  }
  return subArray;
}

auto test7() {
  auto subArray = nlohmann::json::array();
  subArray.get_ptr<nlohmann::json::array_t *>()->reserve(kIterations);
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";

    subArray.emplace_back(std::move(item));
  }
  return subArray;
}

void measureTime(std::function<nlohmann::json(void)> func) {
  auto start = std::chrono::high_resolution_clock::now();
  auto ret = func();
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << "Time: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end -
                                                                     start)
                   .count()
            << "ms" << std::endl;
  // Using the returned data to avoid unwanted optimizations
  std::cout << "Size: " << ret.size() << std::endl;
}

int main() {

  std::cout << "** Perfomance test ** " << std::endl;

  std::cout << "Intermediate variable and push_back" << std::endl;
  measureTime(test1);
  std::cout << "Intermediate variable and emplace_back" << std::endl;
  measureTime(test2);
  std::cout << "No intermediate variable and emplace_back in place with "
               "initializer list"
            << std::endl;
  measureTime(test3);
  std::cout << "No intermediate variable and emplace_back in place with "
               "initializer list and object constructor"
            << std::endl;
  measureTime(test4);
  std::cout << "No intermediate variable and emplace_back in place with "
               "parse and literal"
            << std::endl;
  measureTime(test5);
  std::cout << "No intermediate variable and emplace_back in place with "
               "_json literal"
            << std::endl;
  measureTime(test6);
  std::cout << "Intermediate variable and emplace_back with pre-allocation"
            << std::endl;
  measureTime(test7);
  return 0;
}

$ g++ -O2 -o test test.cpp && ./test                                                                                             [17:06:00]
** Perfomance test ** 
Intermediate variable and push_back
Time: 398ms
Size: 1000000
Intermediate variable and emplace_back
Time: 397ms
Size: 1000000
No intermediate variable and emplace_back in place with initializer list
Time: 707ms
Size: 1000000
No intermediate variable and emplace_back in place with initializer list and object constructor
Time: 686ms
Size: 1000000
No intermediate variable and emplace_back in place with parse and literal
Time: 1133ms
Size: 1000000
No intermediate variable and emplace_back in place with _json literal
Time: 1158ms
Size: 1000000
Intermediate variable and emplace_back with pre-allocation
Time: 287ms
Size: 1000000

[gregmarr]

You are right. Is it possible to construct the element directly in the vector in this case?

I don't think so, and I don't think it would matter. The cost is mostly in the constructing, not the inserting into the array.

If you want to see the construction cost of the various methods, you can remove the push_back and emplace_back and just test with something like this (without optimization so that it doesn't remove the creation):

auto test1() {
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();
    item["description"] = "value";
    item["lang"] = "value";
 }
}

auto test3() {
  for (auto i = 0; i < kIterations; ++i) {
        auto j = nlohmann::json({{"description", "value"}, {"lang", "value"}});
  }
}

This was the fastest. But what happens when I don't know the size before calling the method, does it worth it to do some extra pre-allocation and free the rest at the end?

Definitely not. If you don't know at least the approximate size, just let the push_back or emplace_back automatic reallocation handle it for you.

[pereyra-m]

I don't think so, and I don't think it would matter. The cost is mostly in the constructing, not the inserting into the array.

I'll take a look at that then.
It seems faster to use emplace()

Details

#include "json.hpp"
#include <functional>
#include <iostream>

auto constexpr kIterations{1000000};

void test1() {
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();

    item["description"] = "value";
    item["lang"] = "value";
  }
}

void test2() {
  for (auto i = 0; i < kIterations; ++i) {
    auto item = nlohmann::json::object();
    item.emplace("description", "value");
    item.emplace("lang", "value");
  }
}

void test3() {
  for (auto i = 0; i < kIterations; ++i) {
    auto object = nlohmann::json({{"description", "value"}, {"lang", "value"}});
  }
}

void test5() {
  for (auto i = 0; i < kIterations; ++i) {
    auto object =
        nlohmann::json::parse(R"({"description": "value","lang": "value"})");
  }
}

void test6() {
  for (auto i = 0; i < kIterations; ++i) {
    auto object = R"({"description": "value","lang": "value"})"_json;
  }
}

void measureTime(std::function<void(void)> func) {
  auto start = std::chrono::high_resolution_clock::now();
  func();
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << "Time: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end -
                                                                     start)
                   .count()
            << "ms" << std::endl;
}

int main() {

  std::cout << "** Perfomance test ** " << std::endl;

  std::cout << "test1" << std::endl;
  measureTime(test1);
  std::cout << "test2" << std::endl;
  measureTime(test2);
  std::cout << "test3" << std::endl;
  measureTime(test3);
  std::cout << "test5" << std::endl;
  measureTime(test5);
  std::cout << "test6" << std::endl;
  measureTime(test6);

  return 0;
}

$ g++ -o test2 test2.cpp && ./test2                                                                                              
** Perfomance test ** 
test1
Time: 2378ms
test2
Time: 2159ms
test3
Time: 4876ms
test5
Time: 7100ms
test6
Time: 6912ms

Definitely not.

Ok.

Thank you for the detailed information!

[gregmarr]

Yes, j.emplace(key, value) will likely be faster than j[key] = value as it is simply creating an entry in the map, while the other syntax does a lookup, returns a reference, and then the reference is assigned the value. There is however a behavior difference that you should be aware of, in case you have the possibility of trying to insert with the same key twice.

This results in the object { "key": "value1" }.

 j.emplace("key", "value1");
 j.emplace("key", "value2");  // this does nothing as "key" already exists.

This results in the object { "key": "value2" }.

 j["key"] = "value1";
 j["key"] = "value2"; // this overwrites the previously saved "value1"

https://en.cppreference.com/w/cpp/container/map/emplace