bc-vnt Posted September 30, 2012 Report Posted September 30, 2012 Introduction This is an attempt to explain new && reference present in latest versions of compillers as part of implenmenting the new C++ 11 standard. Such as those shiping with Visual studio 10-11-12 and gcc 4.3-4, or beautifull fast( equally if not more) opensource alternative to gcc CLang. Why you should start using it ? In short : Nontrivial performance gain. For example inserts to std::vector (or in fact any array creation) will not cost huge amount of allocs/copies anymore. But before we go to detail of new c++ 11 "Move semantics" we need to understand the core of problem. We need to understand why performance problem of c++ language with = assign operation often resulting to useless alloc/copy exists. We live in the world where we need to work with a lot of data. We need to store and process it in an effective manner. Problem with c and c++ is that we got used to do it inefectively. a = 1 // we assigned (we could say copied) number to variable And since in natural language we think about "assigning" data to arrays too.It was only natural and could be expected that we continued to assign to arrays in C language the same way. textures[1] = new Texture(640*480*32,"cube.jpg");The real price for copying via = was small since pointers are just numbers (containing memory addresses). But with objects the story is different. How the performance problem startedNow I will try to keep this short but it is important to really understand why && operator was born.In C++ working with references become prevalent since they are safer alternative to pointers and very importanty new language features such as automatic call of constructors or destructors (automatic cleanup) or operators worked only with them. Now make no misteake. References are internally still just pointers but this time made little bit safer and automaticaly dereferenced. Period. How are they made safer? Well. They always point to existing static data. But whenever you pass reference to function in fact it is still just pointer that is internally pushed on stack. void proc( Texture * texture ) { Save(texture); } // unsafe since invalid pointer can be passed invoid proc( Texture & texture ) { Save(texture); } // safer if Texture don't contain invalid pointer inside. C++ wanted to make our life easier by doing routine pointer de/referencing for us (and hiding this pointer wizardry from us). Illusion of passing or working with objects instead of pointers to them was so perfect that many lost sense what is actually reference and what is object.Exactly this ambiguity had unfortunate side effect that led us into beliving that this Texture texture[1000];texture[1] = Texture("sky.jpg"); // we are assigning reference to what ? array of references? is just is safer alternative to this Texture * texture[1000]; texture[1] = new Texture("sky.jpg"); // we are assigning pointer to array of pointersWe just got rid of unsafe pointers in favor of safer references like everywhere else.But more importantly this has given us automatic call of constructors destructor and operators.Right? Wrong. There is no such thing as array of references in C++. No pointer magic behind the scene is going on this time like it is within functions.So what we actualy created is algorithmically very bad decision.We created an array of objects stored by value. And no. Removing * from declaration doesnt automaticaly make pointer variable reference.From performance point of view there is really no alternative to array of pointers . With big objects containing static structured data there is big performance difference when creating sorting searching and mainly reallocating 100mb array of values. Then it is with few bytes of pointers to them. It pretty much kills the possibility to work within processor cache with as much data as possible. So we sort/search/reallocate etc on the speed of main memory order of magnitude slover instead of cpu cache which we now uselesly pollute with unimportant object data. With objects containing big dynamic data situation is better when sorting etc. But still bad when assigned to array. Since then we need to allocate and copy large chunks of dynamic mem plus rest of object.But I would say mentioned reallocation is worst consequence of storing object by values. So every time you think of "nah lets put vector<largeobject> there".Your memory requirements will be twice of what they need to be and your performance abysmal due to fact that whole allocated mem will be uselesly moved around after each realloc. One would think that this is just price we indeed agreed to pay for generic approaches and lazyness. But by my opinion this is the price for storing objects instead of pointers for the oo reasons (automatic constructors destructors operators) mentioned above. But back to the topic. As we remember assign = "actually" copies data. And this leads us to another big performance problem with arrays. How to efficiently build array of large objects.Suppose you wana build a city full of scyscrappers and you obviously (due to large scale) can't afford any waste of time or resources. Now think of city as an array analogy. So what you actually do is you "create" building inside city you allocate large space for building inside of city and obviously you just build building in this space. But thanks to our habit of using = operator to store object pointers to array in good old C. Its only natural that we attempt to use the same "create and assign" paradigm with references too; In other words. We simply got used to it and what's worse every c++ book teaches as to do it this ineffective way. Skyscrapper city[1000];city[1] = Skyscrapper("Empire State Building"); So instead of "create inside array" which we learned from city analogy. you allocate large temporary space outside city // = Skyscrapper(); you build scyscrapper in this temporary space you allocate the same large space inside city // city[1].operator = (Skyscrapper &in) you use large amount uf trucks gas and time to move this scyscrapper to space in city Now worst is the useless copy part. Why? Its an order of magnitude slower than all the steps combined. Because when usually even the largest objects are created this large memory is merely preallocated. That means usually no usefull data are yet in them. Yet by forcing copy operation we are forced to move them byte by byte no matter wether data is valid or not. The larger the object static+dynamic memory the larger the performance drop. How big is the performance drop ? Now It would seem unbelivable but as we speakevery usual object assigned by reference and not by pointer in c++ suffers this and assigning to arrays is worst. just check benchmark results in middle of article.That is pretty much most of the code around you. Go ahead an check nearest code It manifests with arrays so strongly because of sheer number of inefective assigments. In case of our benchmark its 500 assigments but if you do any reference assigment that can be handled by moving (as explained later) and not copying in loop with 500 iterations you have basically the same problem.But back to the arrays. So are there ways in c++ to store object to array effectively ?(damn... I got used to it too Wink | <img src= . I mean create object in a array effectively) without wasted cpu and mem?Since as you seen in benchmark. The larger the objects are the more it matters. Yes there are but they are nor intuitive or obvious and are hack like in nature.Now if C++ did allow us to invoke specialized constructor and create objects using already allocated space inside array(that was allocated just once for all elements by one efficient alloc).Then this could saved zillion of allocs/copies most of us usually do by assining new objects via = ; Skyscrapper city[1000];city[1]("empire state building") //not possible in c++ will not compile Still. There are some ways to do it. You can for example move all your initialization code to method and invoke it on array element explicitly. Skyscrapper city[1000];city[1].create("empire state building"); you allocate large space for building inside city you build building in this space. Hurray. The problem introduced by using = is gone. That means now it doesn't matter if object have large static array or structure. No copy no problem.Most importantly the wasted cpu on moving mostly usleless empty bytes is gone. Also positive is the fact that reading and writing such a large chunk of memory which pretty much flushed all cpu caches bringing down performance of the rest of the application is gone too. That's all nice and great. But chances that people will stop puting code to constructors in favor of some standard create method are pretty slim. Using constructors to create everything is paradigm that we got so used to and love.Exactly as we got trained by misleading books and used = operator for storing data to arrays. Still.There is way to do it with constructor via little known variant of operator new Its called "placement new" where you construct object on existing memory with this pointer provided by you. But now we are entering very weird confusing and little bit danferous territory due to word new flying around static array. New that doesnt allocate anything. New that is here just as a kludge to invoke constructor. Why dangerous? The moment you overload something as fundamental as allocator New brace yourself for all kind of troubles Dr. Dobb's | Sutter’s Mill: To New, Perchance To Throw [1] (Part 1 of 2) | March 01, 2001 .#include <new>Skyscrapper city[1000];// we allocate static array with all objectsall just oncenew (&city[1]) Skyscraper("empire state building"); //no object alloc just calls constructor city[1].~Skyscraper(); // frees resources allocated by previous constructor callnew (&city[1]) Skyscraper("renovated empire state building"); city[1].~Skyscraper(); // frees resources allocated by previous constructor callIt's unnatural and this time problematic plus very confusing too.But Storing objects was always very bad idea anyway as you can see in sorting results in benchmark bellow. So what about returning to storing just pointers? As we mentioned above no oo goodies for pointers. { vector<Texture*> textures(100); // no constructors called textures[1] = new Texture(640*480*32,"cube.jpg"); //no operators invoked on textures[1]} // leaving scope but no destructors called on vector items ;(Most importantly when vector goes out of scope no destructors are automaticaly called. it can be done manually but it reintroduces source of bugs.C++ could solve it by introducing scoped version of new. like new_local. In such case compiller would generate calling destructors when leaving scope exactly as it is doing today with static objects.Is automatic cleanup of objects stored by pointers really that imposible in current c++? Now consider following weird but perfectly working example. Remember stack is defaultly limited (unless you change it in linker settings) resource. So take this as purely academic example that aray of pointers that automatically calls destructors when going out of scope is possible. struct A{ int no; operator A* () { return this; } // just typecast };void array_of_objects_stored_by_pointers_with_autocleanup() { A* a[10000]={0}; // an array of references which was not supposed to exist ? a[7] = A(); a[7]->no=7; // no "new A()". Since "A()" is the same just not on heap but on stack a[4] = A(); a[4]->no=4; // and auto cleanup of stack is build-in } The moment array of objects stored by pointers goes out of scope they are automatically deallocated without any manual destructor invocation; How come this works ? What is going on?= A() is internally the same as = new A();the same constructor is invoked. Except for first stack is used by allocator and heap for second.both return pointers. references are pointers(just meeting certain criteria to deserve label reference) as we remember right ? Yes for heap pointers (created by new) there is kludge of wrapping all pointers to objects simulating pointers via operator overloading aka(smart pointers) in std::shared_ptr and alike. and store just those. So if you dont mind wraping all your variables to functionality hiding impossible to debug macros/templates then this is very good solution for you. But I strongly belive that simple things shall not be encrypted or hidden from sight nor does every variable. Programmer must be avare of what is going on as much as possible like it was in C. without having template and macro expander build in his head. And if you ask Linus to obfuscate every pointer to template wrapper he would most probably kill you. I remember strong backlash against excesive macro usage in C. And there was rational reason for that. That reason was "complexity and hiding code logic is source of bugs". The possibly best solution is to fix C++ compillers = operation After all those attempts to store anything via = without waste I think that compiller should do "placement new" transparently for us whenever he encounters = on movable object. Instead of forcing us to implement zillion operators that solve only heap side of problem. Deciding what kind of "this" object should use is easy since static analysis deciding what object is movable is already part of new compillers as part of support for &&.Skyscrapper city[1000]; // instead of temp on any assigncity[1] = Skyscrapper("Empire State Building"); // compiller should use &city[1] as this pointerSo this internally can be optimized (via explicit optimization switch) to something like Skyscrapper city[1000]; // we mark every element as in default constructor initialized statetry { // to enable this optimization default constructor can contain only memset calls to solve reinvocation problem new (&city[1]) Skyscrapper("Empire State Building");} catch(...) { // in case of exception new (&city[1]) Skyscrapper() // we restore object to post default constructor state to keep standard behavior of C++ standard throw; // and we rethrow any exception } This would fix heap and static waste = zero alloc/copy since elements are created just once in already allocated memory as it always should had been for performance reasons. Why is static mem waste equally if not more important? Majority of objects are small thus majority of their memory is static. And when you look at benchmark bellow storing static array took 5662 ms yet storing dynamic array took 1372 ms. Also. After such change to compiller all old code using big static objects would start pretty much flying at completely different speeds just by recompiling. Because I am curious person I am attempting to implement and test it in clang fantastic open source c++compiller as a optimization switch or pragma. Should you wana lend a hand I will be more than thankfull Clang Developers - Proposed C++ optimization with big speed gains with big objects | Threaded View .But let's focus on latest C++ solution to it (unfortunately only for heap mem in your objects and with a lot of code changes)The new C++ 11 Move semanticsMove semantics enables you to write code that transfers dynamically allocated memory from one object to another. Move semantics works because it enables this memory to be transferred from temporary objects(by copying just pointers) that cannot be referenced elsewhere in the program. Unfortunatelly large static data must still be uselessly copied since they are contained within temp object themself that is about to be destroyed. To implement move semantics, you typically provide a move constructor, and optionally a move assignment operator= to your class. Copy and assignment operations whose sources are (temp objects or data that can't change) then automatically take advantage of move semantics. Unlike the default copy constructor, the compiler does not provide a default move constructor. You can also overload ordinary functions and operators to take advantage of move semantics. Visual C++ 2010 introduces move semantics into the Standard Template Library (STL). For example, the string class implements operations that perform move semantics. Consider the following example that concatenates several strings. string s = string("h") + "e" + "ll" + "o";Before && references existed, each call to operator+ allocated and returned a new temp object. operator+ couldn't append one string to the other because it didnt know whether content of the source can be tampered with (temps) or not (variables). If the source strings are both variables, they might be referenced elsewhere in the program and therefore must not be modified.But now thanks to && reference we now know that temp (which cannot be referenced elsewhere in the program) was passed in. Therefore, operator+ can now safely append one string to another. This can significantly reduce the number of dynamic memory allocations that the string class must perform. Move semantics also helps when the compiler cannot use Return Value Optimization (RVO) or Named Return Value Optimization (NRVO). In these cases, the compiler calls the move constructor if the type defines it. As an another example consider the example of inserting an element into a vector object. If the capacity of the vector object is exceeded, the vector object must reallocate memory for its elements and then copy each element to another memory location to make room for the inserted element. When an insertion operation copies an element, it creates a new element, calls the copy constructor to copy the data from the previous element to the new element, and then destroys the previous element. Move semantics enables you to move objects directly without having to perform expensive memory allocation and copy operations.So. To take advantage of move semantics to allow efficient insert of your objects in the std::vector, you must write a move constructor to allow moving of data from one object to another. So let's see what is going on within our usual inefficient city copy operator = example but with move operator = implemented Well. Aditionally to your copy operator = (&) where you always just copy assigned variable data Now you define aditional move operator = (&&) that will be called instead when data that canot change (such as temp object created when assigning to array) is passed in. Skyscrapper city[1000];city[1] = Skyscrapper("Empire State Building"); you allocate large space for building outside of city // notice = Skyscrapper(); you build building in this space. you just mark this already created building as part of city // no trucks (copying) needed void operator = ( Skyscraper && in ) { // temp obj was passed in mem = in.mem; // We copy just data pointer from temp (ie we move data) size = in.size; // which is safe since temp obj can't change in.mem = 0; // THIS IS KEY PART: we prevent deallocation when temp is destroyed}~Skyscrapper() { if(mem) delete mem; } //BUT destructor must have delete as conditional Hurray no allocate/copy from temp object = finally no cpu is wasted and cache trashed Smile | <img src=Memory allocated and initialized by temp is not released since it has new owner. For complete compilable example copy benchmark code bellow to dev env of your choice. No for those who thing everything was clear and obvious in previous example.Dont' let the eyes fool you. void operator = ( Skyscraper && in ) { // From now on in is of type Skyscrapper & and not && next_proc(in); // Skyscrapper & is passed in and is not movable anymore next_proc((Skyscrapper &&)in); // we need to explicitly retype it && temp to be movable again} Skyscraper && in is not actually of type && anymore. The moment it enters function its & again. So if you wana forward && to another function you need to cast it to && again (in stl via std::move). Why c++ decided to do this behind your back hidden functionality ? Well I am being told that it's security precaution. That any && having name is in risk of being referenced somewhere else in code and thus it's not deemed safe for keeping "moveable" status. Seems like some unfinished c++ business to me since I can't imagine referencing local variable outside of this proc.Also there is little know feature of ref-specifiers where you can restrict operator/methods to accept just temps or just variables.struct string { string& operator=(string const& other) & { /* ... */ }}; Now, you can't anymore say string() = "hello";Unfortunatelly this doesn't yet seem to be supported in Visual Studio 2012 RC1 that I am using right now. So to summarize. Unless you use contained big static arrays the result is significant speedup of your existing code. Tho see how much you can speedup your existing code (well... actually you stop slowing it down)I created simple practical && example along with benchmark results. But if you do more than just stupid memset in your constructors/destructors speedups will be significantly higher. Benchmark Results:store objects containing static array took 5662 ms // even with && this is still problem sort objects containing static array took 17660 ms // this is why you should not store objects store objects containing dynamic array by copying took 1372 msstore objects containing dynamic array by moving (c++ 11) took 500 msstore just pointers to objects took 484 ms sort just pointers to objects took 0 ms Benchmark CodeTo have an idea how bad the usual careless assign = is.I created example storing 500 large objects to array via different methods and measured time it takes.Texture represents standard large object we work in c++ on daily basis = just large chunk of data and its sizeplus mandatory operator = to be able to be stored by value. Now it's stripped to bare minimum on purpose(no chaining consts etc) . with only simple types so you can focus only on those two operators. And sort has < reversed to simulate worst case scenario. #include <stdio.h>#include <stdlib.h>#include <windows.h> #include <algorithm> using namespace std;// current C++ Average Joe Objectstruct Texture { int size; int color; void* mem; Texture() : size(0), color(0), mem(0) {} ~Texture() { if(mem) delete mem; mem = 0; } Texture ( int Size, int Color ) { mem=new char[size=Size]; memset(mem,color=Color,size); } void operator = ( Texture & in ) { // variable passed in color = in.color; mem = new char[size=in.size]; // so we need copy memcpy(mem,in.mem,in.size); // since variables change }};// C++ 11 Enhanced version struct Texture2 : virtual Texture { void operator = ( Texture && in ) { // temp obj is passed in color= in.color; mem = in.mem; // We copy just data pointer from temp (ie we move data) size = in.size; // which is safe since temp obj can't change in.mem = 0; // THIS IS KEY PART: we prevent deallocation when temp is destroyed }}; // C++ 11 unfortunately cant solve the need to copy static object data// so this object can't by stored in c++ via = efficiently without useless copy// and even new operator && will not help since he solves only heap part of the problem. // Point is. Don't use large static arrays/structures/too many members // or = with objects containing them if you care about speed.struct Texture2StaticArray : Texture2 { Texture2StaticArray() : Texture() {} Texture2StaticArray( int Size, int Color ) { memset(static_array,color=Color,sizeof(static_array)); } char static_array[640*480*8];}; #define TEXTURES 500void store_objects_containing_static_array() { Texture2StaticArray* texture =new Texture2StaticArray[TEXTURES]; DWORD start = GetTickCount(); for(int i=0;i<TEXTURES;i++) { texture[i] = Texture2StaticArray(0,i); } printf("\nstore objects containing static array took %d ms", GetTickCount()-start ); start = GetTickCount(); sort(texture,texture+TEXTURES, [] (Texture2StaticArray& a, Texture2StaticArray& { return a.color > b.color; } ); printf("\nsort objects containing static array took %d ms", GetTickCount()-start ); delete [] texture;}void store_objects_containing_dynamic_array_current_standard() { Texture texture [TEXTURES]; DWORD start = GetTickCount(); for(int i=0;i<TEXTURES;i++) { texture[i] = Texture(640*480*8,i); } printf("\nstore objects containing dynamic array by copying took %d ms", GetTickCount()-start );}void store_objects_containing_dynamic_array_new_standard() { Texture2 texture [TEXTURES]; DWORD start = GetTickCount(); for(int i=0;i<TEXTURES;i++) { texture[i] = Texture(640*480*8,i); } printf("\nstore objects containing dynamic array by moving (c++ 11) took %d ms", GetTickCount()-start );}void store_pointers_to_any_object() { Texture* texture [TEXTURES]; DWORD start = GetTickCount(); for(int i=0;i<TEXTURES;i++) { texture[i] = new Texture(640*480*8,i); } printf("\nstore just pointers to objects took %d ms", GetTickCount()-start ); start = GetTickCount(); sort(texture,texture+TEXTURES, [] (Texture* a, Texture* { return a->color > b->color; }); printf("\nsort just pointers to objects took %d ms", GetTickCount()-start ); for(int i=0;i<TEXTURES;i++) { // We need to call destructors manually delete texture[i]; }}void main() { store_objects_containing_static_array(); store_objects_containing_dynamic_array_current_standard(); store_objects_containing_dynamic_array_new_standard(); store_pointers_to_any_object(); Sleep(-1);}Now the more observable of you would probably would start arguing... "This is nothing new I could do this data "moving" (or just passing data along between objects without copying) the same way in current standard c++ operator = & so why do I need new && operator ? Yes you can and No you can't. If you did moving in operator = & like this. Imagine what would happen... // This will not work as intended. Explanation bellow void operator = ( const string & in ) { mem = in.mem; // We move data by pointing to it size = in.size; in.mem = 0; } ...string a("white"),b("yellow"); string c=b; // c is "yellow" now ...b="gotcha..." // but c is now "gotcha..." too -> should not happen !!! If we moved = copied just pointers to data in standard operator = & Then whenewer b changes c changes too; And this was not intended so we actually wana make copy when assigning from data that can change and we just copy pointers to data that we are sure will not change Unfortunately & up to c++ 11 could not distingush if passed data can changeso moving was not possible in current c++ standard for the reasons explained in c=b example.the new && in turn can distingush that data which cant change was passed in and thus its safejust point to its data and skip copying.So to summarize.in new c++ 11 standard you are now supposed to keep two sets of operators and constructors operator = and constructor taking & where you copy from data that can change (variables etc,) operator = and constructor taking && where you just point to data that will not change and save mem and cpu by skipping copying (temp objects,etc) Unfotunately that means you will now have to implement two sets of pretty much every operator under the sun that you declared with generic copy/paste like code yet still fixing only heap side of the performance problem. So reconsider using = on objects at all. At least until compiller writers fix heap and static mem waste by doing internal placement new for = on movable objects.string b(a); //compiller invokes constructor (&) on b and we make copy since a can changestring c=b; //compiller invokes operator = & on c and we make copy since b can changestring texts[10]; texts[1]= string("white fox"); //compiller invokes =&& on texts[1] since temp obj was passed in Why it's called rvalue reference &&Now the whole article I was deliberately was not using termins like rvalues(cant change) and lvalues(can change) since they are not what their names imply. lvalue should had been named something like "variable" rvalue should had been named something like "temp" So whenever you read text using lvalue and rvalue just replace those two and sudenly text will make sense Wink | <img src= They are just technical grammar remnants confusing people.the were born from how C grammar in lex and yacc was described eg on what side of"that particular grammar rule they vere located = left or right" BUT that particular rule can be part of larger expression and lvalue is sudenly rvalue.Or let me explain it this way.Anything not having name is rvalue otherwise it's lvalue Take care Smile | <img src= http://www.codeproject.com/Articles/453022/The-new-Cplusplus-11-rvalue-reference-and-why-you Quote
