Slowness of Vectors

[foyuliu]

paste piece of vector code, i am leaving now-.

    vector<int> numbers(ROW*COLUMN) ;
    int i ,j ;

    clock_t allocate = clock();
    cout << "allocate time " << difftime(allocate, now) << endl;

    for( i = 0 ; i< ROW ; i++ )
    {
        //    int x = i*COLUMN;
        for( j = 0 ; j < COLUMN ; j++)
        {
            numbers[i*COLUMN+j] = rand();
        }
    }

    clock_t assign = clock();
    cout << "assgn time " << difftime(assign, now) << endl;

    if (1)
        for ( i = 0; i < ROW; ++i)
            sort ( numbers.begin() + i*COLUMN, numbers.begin() + (i+1) * COLUMN);
    else
        sort( numbers.begin() , numbers.end());

    clock_t then = clock();
    cout << "Total time for vector " << difftime(then,now) << " msec." << endl;    

[jsmith]

Try this version:

void vectorFun( clock_t )
{
    typedef vector< int >  VInt;
    typedef vector< VInt > VVInt;

    VVInt numbers;
    numbers.resize( ROW );
    for( VVInt::iterator i = numbers.begin(); i != numbers.end(); ++i )
        i->resize( COLUMN );

    for( VVInt::iterator i = numbers.begin(); i != numbers.end(); ++i )
        for( VInt::iterator j = i->begin(); j != i->end(); ++j )
            *j = rand();

    for( VVInt::iterator i = numbers.begin(); i != numbers.end(); ++i )
        sort( i->begin(), i->end() );
}

The problem is memory accesses.

operator[] returns begin() + n, and begin() returns this->_M_impl._M_start.

There are several more memory accesses involved in this equation than in the array case.

[Dufresne]

jsmith
You suggestion , decreased time a little bit for vector.
Btw , I get different results with different compilers.

With Dev-C++ IDE version 4.9.9.2, total time of vector is 6 times bigger than total time of array. But with Microsoft Visual C++ 6.0 total time of vector is quite small, nearly equal to array.

Result of Dev-C++
For Array , 46
For Vector , 298

Result of Microsoft Visual C++ 6.0
For array , 78
For Vector , 109

With default settings of compilers

[helios]

Use. Optimizations. They'll reduce the run time by even more.

[Dufresne]

Wow,thanks helios, I didn't know about optimization settings of compilers.
this is the result that i'm looking for :)

Now they're almost equal with quite small numbers