Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Language
English













SourceForge.net Logo



Moveable

First important node: U++ Moveable is not to be confused with C++ standard library move semantics.

Moveable concept represents basic requirement for types stored in Vector flavor of containers (namely Vector, BiVector, Index, VectorMap, InVector, SortedIndex, SortedVectorMap). To explain what it is and why it is so important let us first create a very primitive Vector-like container template

template <class T>

class SimpleVector {

    T  *vector;

    int capacity;

    int items;

 

    void Expand() {

        capacity = max(1, 2 * capacity);

        T *newvector = (T *) new char[capacity * sizeof(T)];

        for(int i = 0; i < items; i++) {

            new(newvector[i]) T(vector[i]);

            vector[i].T::~T();

        }

        delete[] (char *) vector;

        vector = newvector;

    }

public:

    void Add(const T& x) {

        if(items >= capacity) Expand();

        new(vector[items++]) T(x);

    }

    T& operator[](int i) { return vector[i]; }

    SimpleVector() {

        vector = NULL;

        capacity = items = 0;

    }

    ~SimpleVector() {

        for(int i = 0; i < items; i++)

            vector[i].T::~T();

        delete[] (char *)vector;

    }

};

This SimpleVector stores added elements in the vector member field. If there is no more empty storage space left in vector, SimpleVector simply doubles its capacity using Expand method. This method is what interests us - because Expand requires means to copy values of elements from the original memory area to the newly allocated one. The version above uses placement new and copy constructor for this purpose. This also means that SimpleVector requires T to have copy constructor (in standard C++ library terms: it must be copy-constructible). Now let us create a typical element that can be stored in such container

class SimpleString {

    char *text;

public:

    SimpleString(const char *txt) {

        text = new char[strlen(txt)+1];

        strcpy(text, txt);

    }

    SimpleString(const SimpleString& s) {

        text = new char[strlen(s.text)+1];

        strcpy(text, s.text);

    }

    void operator=(const SimpleString& s) {

        delete[] text;

        text = new char[strlen(s.text)+1];

        strcpy(text, s.text);        

    }

    ~SimpleString() {

        delete[] text;

    }

};

and see what happens when SimpleVector of SimpleStrings is expanded: First, copies of all elements are created, that means allocating new storage for text member of new element and copying source text to it using strcpy. A moment later, Expand invokes destructor for element, thus deleting all texts in the original elements. Does not it seem we are wasting a lot of CPU cycles just to make copies of things that we throw away a moment later anyway? What if instead of making copies we could find a way to transfer original elements' text members to new elements and somehow disallow delete[] text in destructor? See how primitive it can be:

template <class T>

class SimpleVector {

    T  *vector;

    int capacity;

    int items;

 

    void Expand() {

        capacity = max(1, 2 * capacity);

        T *newvector = (T *) new char[capacity * sizeof(T)];

        memcpy(newvector, vector, items * sizeof(T));

        delete[](char *)vector;

        vector = newvector;

    }

public:

    void Add(const T& x) {

        if(items >= capacity) Expand();

        new(vector[items++]) T(x);

    }

    SimpleVector() {

        vector = NULL;

        capacity = items = 0;

    }

    ~SimpleVector() {

        for(int i = 0; i < items; i++)

            vector[i].T::~T();

        delete[] (char *)vector;

    }

};

For the moment please ignore fact that by using memcpy to move non-POD types we are violating C++ standard (we will discuss it later). Now, what we get here is exactly what we wanted - instead of a series of copy construction and destruction we simply copy raw binary data to the new location. This way we simply transfer the old value in the text member of elements into the new expanded vector. We need to invoke neither copy constructor nor destructor when expanding vector. Not a single CPU cycle is lost.

The types that can be moved in memory using memcpy are called moveable.

Clearly not all types are moveable. Being moveable has a lot to do with not storing references to the object itself or to it's parts. E.g.

struct Link {

    Link *prev;

public:

    Link()        { prev = NULL; }

    Link(Link *p) { prev = p; }

};

is not moveable, because memcpy-ing to a new location would break the existing links. All of the following requirements should be fullfilled for moveable types:

It does not have any virtual method nor virtual base class.

Base classes (if any) and any instance member variables are moveable.

No references or pointers are stored to the object itself or to subobjects in the methods of the type, into variables that exist after the method finishes execution.

Fundamental types fulfills these requirements so they are moveable.

Example:

struct Foo;

 

Foo *global_foo;

 

struct Foo {

    int a;

    Foo *foo;

    int *ptr;

public:

    void Set(Foo * f) {

        foo = f;

    }

    void Ok1() {

        Foo *x = this;

    // local variable will not exist outside method

    // -> does not prevent Foo from being moveable

    }

    void Ok2() {

        memset(&a, 0, sizeof(int));

    // pointer will not exist outside method

    // -> does not prevent Foo from being moveable

    }

    void Bad1() {

        foo = this;

    // member variable foo exists outside method

    // -> makes Foo non-moveable

    }

    void Bad2() {

        ptr = &a;

    // pointer to subobject stored, ptr exists outside method

    // -> makes Foo non-moveable

    }

    void Bad3() {

        global_foo = this;

    // pointer stored to global variable

    // -> makes Foo non-moveable

    }

    void Bad4(Foo& another) {

        another.Set(this);

    // pointer stored indirectly in object that exist outside method

    // -> makes Foo non-moveable

    }

};

These requirements satisfies fairly large number of types, incidentally most of the types you ever wanted to store in a container of elements of a single type are moveable. Most important, all NTL containers are moveable.

Now we have an effective method how to organize the storing of elements in containers. We have to deal with the fact that being moveable is part of an object's interface, and we should ensure that only movable elements are stored into NTL containers. For this we need a way to declare at compile time that a certain type is moveable and also a way to check it.

To achieve this goal, you can mark moveable types by deriving them from the Moveable template class e.g.:

class SimpleString : Moveable<SimpleString> { ... }

Alternatively the NTL_MOVEABLE macro can be used to mark types as moveable if the class interface can not be changed, such as in:

NTL_MOVEABLE(std::string);

Now that we can mark types as moveable, we need a way to check a type for being moveable. This is done by adding the line:

AssertMoveable<T>()

to one of the methods of a template that gets compiled for any template argument - the destructor is the most obvious place. The AssertMovable function is defined only if T is marked as moveable, so it results in compilation error for non-moveable T types.

Finally, time has come to deal with the C++ standard. Current C++ defines memcpy only for POD types. The moveable concept requires memcpy of non-POD types to be defined. In fact, difference between POD and moveable non-POD types is the existence of constructors and non-virtual destructor. To get things work, all we need is that the result of memcpy-ing non-POD type T is same as memcpy-ing the POD T1 type which you would get by removing the destructor and the constructors from T. While this operation is still undefined by C++, it is really hard to imagine an optimal C++ implementation that would break this rule. Indeed, all current implementation we have met so far support moveable semantics in the way we have defined here. Performance and other gains realized by using the moveable concept are too big to ignore.

Last edit by cxl on 03/16/2014. Do you want to contribute?. T++