🚀 go-pugleaf

Move semantics has been proposed for C++0X:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

In a nutshell, this proposal is about performance.  Move semantics is 
just an organized way of doing a shallow copy of heavy weight types when 
you don't care what happens to the source (i.e. you only need a cheap 
move, not an expensive copy).

The full move semantics proposal requires some (backwards compatible) 
language changes, and is not available in Pro 9.  However, a limited 
version of move has been coded into the Pro 9 std::vector.  
Specifically, when you have a std::vector<any other std or 
Metrowerks::container>, then the vector will internally move its 
elements instead of copy them during insert and erase.  There is no 
change in interface.  Your vector will simply be higher performance.  
There is nothing you need to do to achieve this performance gain except 
recompile your code against Pro 9.

For example, consider the vector vs set debate.  Sometimes an ordered 
vector can be higher performance than the equivalent set.  This can be 
especially true if the elements to be ordered are light weight and/or if 
the application is mostly concerned with lookup instead of inserting new 
elements (inserting into a vector can be slow).

While the above statement remains true, exactly when and where set is 
superior to an ordered vector has radically changed with Pro 9.  To 
demonstrate, below is a test that pits vector vs set, using what used to 
be a relatively heavy weight element:  std::string, and it does so for 
vector's weakest point:  ordered insertion.

The test below creates a randomized vector<string>, where each string is 
fairly long (a path/file is used in this example).  The file used in 
this test can be found at:

http://home.twcny.rr.com/hinnant/tip_archive/keys.txt

The set test merely times the construction of the set from the 
randomized vector of keys.

The vector test times the effort required to insert each key into the 
vector, keeping it ordered at each step.  Naturally it would be much 
faster to just build the vector in random order, and then sort it.  But 
this test is investigating the cost of inserting a string into a sorted 
vector, and how that relates to inserting a string into a set.

Here is the full source of the test:

#include <vector>
#include <string>
#include <time.h>
#include <stddef.h>
#include <numeric>

template <class F>
float test(F f)
{
    std::vector<float> t;
    int i;
    for (i = 0; i < 10; ++i)
        t.push_back(f());
    while (i < 1000 && std::accumulate(t.begin(), t.end(), 0.0) < 1.0)
    {
        t.push_back(f());
        ++i;
    }
    std::sort(t.begin(), t.end());
    return (float)
        (
            std::accumulate(t.begin(),
                            t.end()-(ptrdiff_t)(t.size()/10),
                            0.0
                           )
            / (t.size()-(t.size()/10))
        );
}

#include <set>
#include <iostream>
#include <fstream>

std::vector<std::string> keys;

float test_vector_insert_string()
{
    typedef std::vector<std::string>::const_iterator ci;
    clock_t t = clock();
    std::vector<std::string> v;
    for (ci i = keys.begin(), e = keys.end(); i != e; ++i)
        v.insert(std::lower_bound(v.begin(), v.end(), *i), *i);
    t = clock() - t;
    return (float)(t/(double)CLOCKS_PER_SEC);
}

float test_set_insert_string()
{
    clock_t t = clock();
    std::set<std::string> s(keys.begin(), keys.end());
    t = clock() - t;
    return (float)(t/(double)CLOCKS_PER_SEC);
}

int
main()
{
    std::ifstream infile("keys.txt");
    if (!infile.is_open())
    {
        std::cout << "Can't open keys.txt\n";
        return 1;
    }
    std::istream_iterator<std::string> in(infile), eof;
    keys.assign(in, eof);
    std::cout << "number of keys = " << keys.size() << '\n';
    std::random_shuffle(keys.begin(), keys.end());
    std::cout << std::scientific;
    float v = test(test_vector_insert_string);
    float l = test(test_set_insert_string);
    std::cout << "vector speed = " << v << '\n';
    std::cout << "set    speed = " << l << '\n';
    std::cout << std::fixed;
    std::cout << "vector/set  = " << v/l << '\n';
}

The templated test function is just me being fastidious.  This function 
will take a test-functor, and run it at least 10 times, but no more than 
1000 times.  Each run results in a timing (represeted by a float).  To 
keep from waiting all day for tests to complete, test stops repeating 
the function run if the accumulated times exceed 1 second (once at least 
10 runs are made).  The slowest 10% of the runs are tossed out the 
window and the remaining fastest 90% of the runs are averaged and that 
is returned as the speed of the functor.  This heuristic has resulted in 
very repeatable timing results.

As described eariler, test_vector_insert_string simply inserts the 
strings one at a time into a vector, each time using lower_bound to find 
the right place to insert the string.  The resulting vector is sorted.

The test_set_insert_string times the same functionality for set, which 
is simply constructed from the randomized keys.

The main function reads the keys from keys.txt, prints out the number of 
keys so there is some confidence that the read was done correctly, runs 
the tests and compares the times.

In Pro 8.x the results are:

Carbon:

number of keys = 530
vector speed = 3.075024e-02
set    speed = 2.983515e-03
vector/set  = 10.306715

and for Mach-O:

number of keys = 530
vector speed = 3.103448e-02
set    speed = 2.829457e-03
vector/set  = 10.968351

Actaully I'm simulating Pro 8 by simply turning off move semantics in 
Pro 9, so please feel free to correct these figures for me.  These 
results reflect conventional wisdom.  If you're inserting a lot of heavy 
weight objects into a vector, you should probably use set instead.

In Pro 9 the results are:

Carbon:

number of keys = 530
vector speed = 3.223833e-03
set    speed = 3.000515e-03
vector/set  = 1.074427

and for Mach-O:

number of keys = 530
vector speed = 2.696629e-03
set    speed = 2.676580e-03
vector/set  = 1.007491

The important thing to notice here is that the Pro 9 ordered 
vector<string> is nearly as fast as set<string>.  In comparison the Pro 
8 vector (without move semantics) is 10 to 11 times slower than set!

That is a very significant difference.

Now of course your results may differ, especially for different input 
sets.  And as the size of the input gets sufficiently large, set is 
still going to be the clear winner.  It is just that the range of 
conditions over which vector is competative with set has now been 
greatly expanded.

You should see similar performance improvements with vector::erase.  And 
this effects not only vector<string>, but also vector<vector<T>>, 
vector<set<T>>, vector<Metrowerks::hash_map<K,V>>, etc.  There is no 
effect on vector<int>, vector<pod>, etc.  These instantiations will run 
at the same speed as before.  It is only heavy-weight objects which our 
std::vector knows about that have been optimized within vector.

It is our hope that one day vector will be just as efficient for your 
user-defined heavy-weight objects.  But for that, we really need the 
full move semantics proposal to be standardized.

-Howard

The C++ lib guy
Metrowerks