3

From https://learn.microsoft.com/en-us/cpp/cpp/value-types-modern-cpp?view=vs-2019, we have:

#include <set>
#include <vector>
#include <string>
using namespace std;

//...
set<widget> LoadHugeData() {
    set<widget> ret;
    // ... load data from disk and populate ret
    return ret;
}
//...
widgets = LoadHugeData();   // efficient, no deep copy

vector<string> v = IfIHadAMillionStrings();
v.insert( begin(v)+v.size()/2, "scott" );   // efficient, no deep copy-shuffle
v.insert( begin(v)+v.size()/2, "Andrei" );  // (just 1M ptr/len assignments)
//...
HugeMatrix operator+(const HugeMatrix& , const HugeMatrix& );
HugeMatrix operator+(const HugeMatrix& ,       HugeMatrix&&);
HugeMatrix operator+(      HugeMatrix&&, const HugeMatrix& );
HugeMatrix operator+(      HugeMatrix&&,       HugeMatrix&&);
//...
hm5 = hm1+hm2+hm3+hm4+hm5;   // efficient, no extra copies

I think I can see how the set is efficient, set stores its data on the heap so I assume returning the set creates a copy of the set where each pointer in the underlying array refers to the same memory locations as the set we're copying from. I assume you could make this even faster by using std::move which will not even have to use new pointers pointing to the same memory location, it will use the same pointers.

I can't see how inserting into a vector can be efficient if vectors in C++ are stored continuously. If they're stored contiguously, I would think that you definitely have to do a "copy-shuffle". What am I missing?

273K
  • 29,503
  • 10
  • 41
  • 64
Aloysius
  • 97
  • 1
  • 8
  • 4
    @d4rk4ng31 That would directly violate the C++ standard. – eesiraed Aug 04 '20 at 03:54
  • @d4rk4ng31 https://en.cppreference.com/w/cpp/container/vector says that vectors have to be contiguous since C++03. Even before C++03 I'm sure vectors couldn't have been implemented as link lists for reasons such as not having constant time random access. – eesiraed Aug 04 '20 at 03:57
  • Vectors are inefficient if you don't set the size or the capacity before you load data into them. But it still follows the standard move-semantics, which means returning a vector from a function is as "efficient" as any other container. Besides, vector also allocate their storage of the heap. And element access is *much* more efficient than for e.g. `std::set`. – Some programmer dude Aug 04 '20 at 04:06
  • So returning a vector or any container is automatically the same as returning `std::move(vector)`? (as opposed to other objects where you explicitly have to write `std::move`)? – Aloysius Aug 04 '20 at 04:09
  • Also remember that `std::set` is *ordered* so each insertion needs extra operations for the ordering. See `std::unordered_set` for unordered data. You can also combine sets and vectors, where you load data into an unordered set, then use it to create a vector. If the data inside the set can be moved, it will be. – Some programmer dude Aug 04 '20 at 04:11

3 Answers3

5

I assume returning the set creates a copy of the set where each pointer in the underlying array ...

Your assumption is wrong. A std::set doesn't have an "underlying array". It is generally implemented as a balanced search tree.

where each pointer in the underlying array refers to the same memory locations as the set we're copying from.

A copy of set does not refer to the data of the original set. It will be a deep copy; each element is copied to the new set.

In the example however, your return a local variable, so it will be moved instead of copied. A move is a shallow copy, and the resulting object will indeed to refer to data that was originally owned by the other object.

What is likely to happen however, is that the compiler does optimisation, and makes it so that the locally declared set actually creates the set that is used on the outside of the function. Because of this "magic trick", there is only one set in practice and no copy nor move needs to be made.

I assume you could make this even faster by using std::move

Actually, return std::move(local) is hardly ever faster than return local. Latter will invoke move constructor anyway, but also allows the before mentioned optimisation. std::move prevents that optimisation.

I can't see how inserting into a vector can be efficient if vectors in C++ are stored continuously.

"Efficiency" is subjective and depends a lot on context.

Sure, node based data structures like list and set have very good worst case for insertion - O(1) asymptotic complexity versus O(N) of vector. But often that is not relevant to your program. What is often more relevant is how well the data structure works with the CPU cache. In short, arrays work very well with cache, while linked nodes do not.

Note that vector is implemented with a clever algorithm that allows insertion of N elements into back of the vector to have O(N) asymptotic complexity, which is same as the linked node structures.

So, when you know how many elements the vector will have and can insert the elements in order, then you can simply reserve sufficient space initially and then there will be no need for shuffling.

If they're stored contiguously, I would think that you definitely have to do a "copy-shuffle". What am I missing?

It does have to do a shuffle. But it is more efficient than copy-shuffle, because it is a move-shuffle, and moving a std::string is efficient.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • "What is likely to happen in the example however, is that the compiler does optimisation, and makes it so that the locally declared set actually creates the set that is used on the outside of the function. " -> So are you saying that for containers in C++, `std::move` is automatically used even when it's not explicit specified? – Aloysius Aug 04 '20 at 04:17
  • @Aloysius I didn't say that, but that is actually true in this case. When you return a local variable, the returned object will implicitly be move-constructed if possible. But what I'm saying is that this optimisation is better than even moving. A move implies that two objects have been created; this optimisation means that one object never existed, and there was no need to even move construct it. – eerorika Aug 04 '20 at 04:19
  • Yeah sorry, you didn't say that, but someone else implied it in one of the comments so I wanted to ask a leading question. I'm not sure I understand the optimization though. So does the compiler automatically see that the so called "local variable" should actually be in the outer scope and automatically store it there so that it doesn't get popped off the stack when the local function goes out of scope. Is there a way to explicitly write code to do this optimization or can only the compiler do it? And lastly, given these crazy compiler optimizations, should you never use std::move? – Aloysius Aug 04 '20 at 04:33
  • (sorry for all the questions) – Aloysius Aug 04 '20 at 04:33
  • @Aloysius `So does the compiler ...` essentially, yes. `Is there a way to explicitly write code to do this optimization` Sort of, but it is very inconvenient. Don't return a value, but instead accept a pointer to uninitialised memory as a parameter, which the caller has to provide. I recommend to not bother trying that. `should you never use std::move` When returning a local, never use `std::move`. In other contexts, use `std::move` if you have an lvalue that you want to move from. – eerorika Aug 04 '20 at 04:44
3

The first assignment from LoadHugeData is efficient because of copy elision or return value optimization, the set is never actually copied.

The insertion in the middle of a vector does indeed require some or all of the existing items to be moved. This is made more efficient because the move semantics don't require any new allocations or copies to be made - the new item will simply take over the internals of the old item, including the pointer to an actual string buffer. No deep copies required.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • Thanks, but I'm not sure I understand the second part. If I have a vector where: vec[0] = Obj1 -> memory address = 0x00000. vec[1] = Obj2 -> memory address = 0x00004. vec[2] = Obj4 -> memory address = 0x00008. and I want to insert Obj3 for index 2, then what can I move to do this without deep copying. It seems to me that Obj2 is inherently next to Obj4 now and there's no way to move Obj3 in between the two without copying Obj4 and moving it to 0x00012. – Aloysius Aug 04 '20 at 04:26
  • @Aloysius you have to realize just what data `std::string` contains. Probably it's just a pointer to the heap for a buffer that holds the characters, and an integer for the length. Moving that object is as easy as `Obj3.ptr = Obj2.ptr` and `Obj3.len = Obj2.len`. – Mark Ransom Aug 04 '20 at 04:39
  • So what is contiguous if the vector's pointers can be pointed at random non-contiguous locations on the heap? Is it the vector's pointers pointers? Like is it something like vec[0] = 0x00000 where at memory location 0x00000 we store the memory location on the heap (let's say 0Xf48fj) where that vector value of Obj1 is stored? – Aloysius Aug 04 '20 at 04:46
  • @Aloysius what's contiguous is the objects themselves. In the case of `std::string` the actual characters making up the string are *not* contained within the object itself, usually. That's because the objects themselves are fixed size and anything they need variable storage for must come from the heap. – Mark Ransom Aug 04 '20 at 15:08
  • Isn't it contiguous because a vector stores an array in implementation? For example, if you create `vector vec` then I think vec creates a `Object[]` internally on the heap (which will be stored contiguously). It seems to me that if you insert in the middle of this array, you have to move everything over by one. – Aloysius Aug 06 '20 at 02:43
  • @Aloysius you're correct. The thing that makes it efficient is that moving a very simple object such as `string` which contains only a pointer and an int can be done easily and quickly. – Mark Ransom Aug 06 '20 at 02:49
2

I think the comment means that the strings are moved instead of deep copied. It's still a linear time operation with respect to the number of strings in the vector, but it won't copy all the characters in the strings (maybe except for SSO). That's what "just 1M ptr/len assignments" means. I guess you could consider that "efficient" when compared to copying every character.

eesiraed
  • 4,626
  • 4
  • 16
  • 34