C++: Hidden array copy operation

A fixed-size array type in C++ does not have a copy constructor or a copy assignment. The following code won't compile: 

int a[2] = {1, 2};
int b[2] = a;

A recommended way to fix this is to use std::array from the header <array> instead because it supports copying (and more): 

std::array<int, 2> a = {1, 2};
std::array<int, 2> b = a;

Alternatively, one can resort to std::copy in <algorithm>, or the old school std::memcpy in <cstring>.

Interestingly, the C++ language does have a way to copy fixed-size arrays, but it can only be accessed via a lambda capture. Here's an example that demonstrates that an array copy is actually done when it's captured by value into a lambda expression: (click this repl.it link if you want to play with the code) 

#include <functional>
#include <iostream>

using namespace std;

struct LoudInt {
  int v;
  LoudInt(int v): v{v} {
    cout << "LoudInt created: " << v << endl;
  }
  LoudInt(LoudInt const& other): v{other.v} {
    cout << "LoudInt copied: " << v << endl;
  }
  LoudInt(LoudInt&& other): v{other.v} {
    cout << "LoudInt moved: " << v << endl;
  }
  ~LoudInt() {
    cout << "LoudInt destroyed: " << v << endl;
  }
  operator int() const { return v; }
};

int main() {
  function<void()> f;
  {
    LoudInt a[2] = {1, 2};
    cout << "Capturing" << endl;
    f = [=]() {
      for (auto const& i : a) {
        cout << i << ' ';
      }
      cout << endl;
    };
    cout << "Destroying the original" << endl;
  }
  cout << "Original destroyed" << endl;
  f();
  return 0;
}

The output from my repl.it session looks like this 

LoudInt created: 1
LoudInt created: 2
Capturing
LoudInt copied: 1
LoudInt copied: 2
LoudInt moved: 1
LoudInt moved: 2
LoudInt moved: 1
LoudInt moved: 2
LoudInt destroyed: 2
LoudInt destroyed: 1
LoudInt destroyed: 2
LoudInt destroyed: 1
Destroying the original
LoudInt destroyed: 2
LoudInt destroyed: 1
Original destroyed
1 2 
LoudInt destroyed: 2
LoudInt destroyed: 1

We see that in the construction of the lambda expression, the copy constructor of LoudInt is called. The captured a inside f is indeed a copy of the original array! This proves that the language itself does contain an array copy operation. Unfortunately we can only use it to copy an array into a closure, not outside of it.

Digression: What about the move constructor?

The output above shows that the move constructor of LoudInt is called twice for each array element. This implies that the move operation for raw fixed-size arrays also exists!

But why is it needed anyway? Let's look into the documentation of std::function::operator=. In our code, we use the overload that takes an r-value reference of a callable type. The documentation suggests that 

f = [=]() { ... }

should be equivalent to 

function([=]() { ... }).swap(f)

So I tried to convert the code manually by replacing the assignment statement with 

    function<void()>{[=]() {
      for (auto const& i : a) {
        cout << i << ' ';
      }
      cout << endl;
    }}.swap(f);

(The repl.it link for the modified code is here.) It turns out that one move operation is actually removed! Here's the output: 

LoudInt created: 1
LoudInt created: 2
Capturing
LoudInt copied: 1
LoudInt copied: 2
LoudInt moved: 1
LoudInt moved: 2
LoudInt destroyed: 2
LoudInt destroyed: 1
Destroying the original
LoudInt destroyed: 2
LoudInt destroyed: 1
Original destroyed
1 2 
LoudInt destroyed: 2
LoudInt destroyed: 1

Another interesting thing is that if we explicitly call std::move on the lambda expression before feeding it to the constructor of std::function, we get back the 2 move operations. Here's the code that's actually equivalent to the original code: 

    function<void()>{move([=]() {
      for (auto const& i : a) {
        cout << i << ' ';
      }
      cout << endl;
    })}.swap(f);

This is indeed more consistent with the documentation of std::function::operator=. But if we look at the documentation of the constructor of std::function, we'll see that a std::move is supposed to be called in the previous case too, yet somehow the move operation didn't happen.

What we can conclude from all these experiments is that it would be wrong to write code of which the correctness relies on how many times the move operation will occur.

Sidenote: Moving or swapping std::function objects of the same type doesn't seem to trigger the move constructor of LoudInt in my experiment. This suggests that if every lambda expression was internally represented the same way as a std::function object, it would be possible for the constructor of std::function of a sufficiently-compatible type to move all the captured values out of a lambda expression without calling its values' move constructors. This doesn't mean it is always a good thing to do though. It's also possible that things that need to be done to avoid those move operations could cost more than the move operations.

Fun project: Making the copied array look "real"

Even though we cannot use the built-in copy operation to copy an array out of a closure, we can provide an interface for accessing the array inside the closure that makes it look like std::array. We can do this even without using <functional> header! Here's my attempt: repl.it link 

#include <iostream>

using namespace std;

template <typename T, size_t N>
struct ClosedArray {
  using Raw = T[N];
  using This = ClosedArray<T, N>;
  ClosedArray(Raw& a): cls{store(a)} {}
  This& operator=(Raw& a) {
    cls = store(a);
    return *this;
  }
  operator Raw&() { return *cls(); }
  T& operator[](size_t i) { return (*cls())[i]; }
  size_t size() const { return N; }
private:
  static auto store(Raw& a) {
    auto storage = [a]() mutable -> Raw* {
      return &a;
    };
    return storage;
  }
  using Storage = decltype(store(declval<Raw&>()));
  Storage cls; // Holds the storage
};

template <typename T, size_t N>
ClosedArray<T, N> copyArray(T (&a)[N]) {
  return ClosedArray<T, N>(a);
}

int main() {
  int a[4]{1, 2, 3, 4};
  auto b = copyArray(a);
  b[2] = 4;
  b[3] = 8;
  auto c = b;
  c[0] = -4;
  c[1] = 0;
  for (size_t i = 0; i < b.size(); ++i) {
    cout <<
      "a[" << i << "] = " << a[i] << "; "
      "b[" << i << "] = " << b[i] << "; "
      "c[" << i << "] = " << c[i]
      << endl;
  }
  return 0;
}

Here's the output: 

a[0] = 1; b[0] = 1; c[0] = -4
a[1] = 2; b[1] = 2; c[1] = 0
a[2] = 3; b[2] = 4; c[2] = 4
a[3] = 4; b[3] = 8; c[3] = 8

Note: copyArray is just a convenience method that calls the constructor of ClosedArray with correct template arguments.

Caution: Lambda captures with initializers

A lambda capture has 2 variants: with and without an initializer. Here's an example of a lambda capture with an initializer: 

int x = 3;
[&y = x]() {
  ++y;
}();
cout << x << endl;

This will output 4.

The syntax might look a little strange if we don't know how it's interpreted. For example, &y = x does not imply that the type of x is the pointer of y. Rather, the C++ standard says that the above code is equivalent to 

int x = 3;
{
  auto& y = x;
  ++y;
};
cout << x << endl;

More precisely, the capture with an initializer works as if it was a variable declaration with auto appended on the left. We can use a different initialization syntax like [&y{x}] and it will work just like auto& y{x};. There are some differences though.

  • A capture initialization allows the new variable to have the same name as outside variables being captured. This does not cause any problem because the new variable is made available only inside the lambda expressions' body. This is somewhat similar to how the member initializer list works in a constructor if the member has the same name as the input argument. Example: MyClass(int x): x{x} is valid, as is [x = x], but declaring int x = x; is not.
  • Because the new capture variable is only available inside the body, it cannot be used in the initialization of another capture. For example, [y = x, z = y + 1] won't compile if y doesn't exist in the enclosing context. This is different from the member initializer list in a constructor where a member variable is referenceable in the initialization of other variables that are declared after it.
    For the curious: In a member initializer list, we can choose between MyClass(int x): x{x}, y{x + 1} and MyClass(int x): x{x}, y{this->x + 1}, but in the lambda capture, there is no equivalent for the second choice.

Essentially, the lambda capture initializer works like the member initializer list with an ability to declare auto member type, and without the ability to refer to other members (through this).

Now that we know the rules, things make a lot more sense, right? There should be no difference between writing 

[a]

and 

[a = a]

provided that a has a copy constructor. This condition is unfortunately not satisfied by fixed-size arrays! When we initialize an auto variable to an array of type T[N], the variable type becomes T*, not T[N]. (This may be due to some legacy reasons.) That means the secret array copy operation cannot happen in a capture with an initializer! Only the pointer gets copied.

The code below demonstrates how this could yield a surprising result: repl.it link 

#include <iostream>

using namespace std;

template <typename T>
void printInc(T& x) {
  cout << x[0] << " -> ";
  ++(x[0]);
}

int main() {
  int a[1]{0};

  [=]() mutable { printInc(a); }();
  [a]() mutable { printInc(a); }();
  [a = a]() mutable { printInc(a); }();
  [&a]() mutable { printInc(a); }();

  cout << a[0] << endl;
  return 0;
}

Output: 

0 -> 0 -> 0 -> 1 -> 2

Each arrow "->" in the output shows the effect of each lambda expression on a[0]. We can see that the first two lambda expressions do not modify a[0], but the third does even though its capture expression looks quite similar to the second one. In fact, the capture expressions [a] and [a = a] should behave the same way except when a is a raw array.

Note: The first two lambda expressions must be declared mutable, but the last two do not need to. The fact that the third lambda expression can be immutable is a warning sign because if whatever is done inside the function body does not affect the captured value, it must affect something else!

Conclusion

A rule of thumb is to be cautious about capturing an array by value. If a new copy is needed, don't use an initializer. If you really really need a different name for the new copy inside the lambda expression's body, declare a new reference at the top of the body instead, like this: 

[a]() {
  auto& b = a;
  ...
}

Comments

  1. peamSeptember 27, 2020 at 1:02:00 AM PDT

    wtf... [a = a]

    ReplyDelete
    Replies
    1. TunococSeptember 27, 2020 at 3:11:00 PM PDT

      That was just an example. No one probably would write that 😛, but [b = a] suffers the same problem.

      Delete

Post a Comment

Popular posts from this blog

Adding code snippets to Blogger posts (or any HTML pages)

As a preparation for writing a blog post about coding, I had to look for a way to show code snippets nicely on my post. I found highlight.js to be the best solution but the way to use it is not super straightforward. I'll explain how I use it on this blog post. Using highlight.js To "install" highlight.js, simply add the following code inside the <head> section: <link href='//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.1.2/styles/default.min.css' rel='stylesheet'/> <script src='//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.1.2/highlight.min.js'/> <script>hljs.initHighlightingOnLoad();</script> If you're using Blogger, this should be done in the theme html file, which you can get to by going to the "Theme" tab, clicking the "Customize" button, and choosing "Edit HTML". This is just like how I added MathJax to Blogger . After we have installed highlight.j...
Read more

You could have invented the determinant

Image
I'm going to talk about how a geometric intuition becomes the definition of the determinant. As many of you already know, the determinant of a matrix is the (hyper)volume of the (hyper)parallelepiped whose edges are the (row or column) vectors of the matrix. This page on Wolfram gives you an interactive visualization of a parallelogram or a parallelepiped while showing the corresponding determinant. There are abundant sources on the internet (many on math.stackexchange.com ) that give more-or-less the same explanation as I just said above, but most of them don't explain why. That's what I want to discuss in this post. First goal: Define area in 2D I'll motivate this discussion with a simple question: how to define volume in a Euclidean space? I'm kidding. That question is actually not that simple, and people have gone to great lengths to answer that. Let me simplify it a bit more, quite gratuitously, so that we ...
Read more