Re: Use of std::vector slower than arrays?

On Nov 12, 5:09 pm, Mark P <use...@fall2005REMOVE.fastmailCAPS.fm>
wrote:


<snip>


Well, here's a complete testing program, then.

---------------------------------------------------

// Performance comparison of std::vector vs C-style array for
// bignum arithmetic.
#include <iostream>
#include <iomanip>
#include <vector>
#include <time.h>

using namespace std;

typedef unsigned long Digit; // should be equal to the machine's
wordsize

// Note: All arrays are stored in little-endian format.

// Test routine: Adds two digit strings together, stored as C arrays.
Digit arradd(Digit *a, Digit *b, Digit *c, int len)
{
    // set up pointers
    Digit *ap(a), *bp(b), *cp(c);

    // loop through the digits
    Digit carry(0);
    while(len--)
    {
       Digit tmp(*bp + *cp + carry); // add b/c's digits
       carry = carry ? (tmp <= *bp) : (tmp < *bp); // check overflow/
carry
       *ap = tmp; // set result
       ap++; bp++; cp++; // increment pointers
    }

    return(carry);
}

// Test routine: Adds two digit strings together, stored with vector.
Digit vecadd(vector<Digit> *a,
             const vector<Digit> *b,
             const vector<Digit> *c,
             int len)
{
    // set up iterators
    vector<Digit>::iterator ai(a->begin());
    vector<Digit>::const_iterator bi(b->begin());
    vector<Digit>::const_iterator ci(c->begin());

    // loop through the digits
    Digit carry(0);
    while(len--)
    {
       Digit tmp(*bi + *ci + carry); // add b/c's digits
       carry = carry ? (tmp <= *bi) : (tmp < *bi); // check overflow/
carry
       *ai = tmp; // set result
       ai++; bi++; ci++; // increment iterators
    }

    return(carry);
}

// The main routine.
int main()
{
    // Create the digit arrays and vectors.
    Digit a[4], b[4];
    vector<Digit> av, bv;

    // Set up the vectors' memory storage.
    av.reserve(4);
    bv.reserve(4);

    // Set the test values.
    a[0] = 0x4B9F0101UL; av.push_back(0x4B9F0101UL); // LSD
    a[1] = 0x56092310UL; av.push_back(0x56092310UL);
    a[2] = 0x56238413UL; av.push_back(0x56238413UL);
    a[3] = 0x44042121UL; av.push_back(0x44042121UL); // MSD
    b[0] = 0x4B9F0101UL; bv.push_back(0x4B9F0101UL); // LSD
    b[1] = 0x56092310UL; bv.push_back(0x56092310UL);
    b[2] = 0x56238413UL; bv.push_back(0x56238413UL);
    b[3] = 0x44042121UL; bv.push_back(0x44042121UL); // MSD

    // Now run the tests.
    time_t startt, endt;
    clock_t startcpu, endcpu;

    // Test 1
    cout << "Test 1: 100 million 128-bit additions using C arrays..."
<< endl;

    startt = time(0);
    startcpu = clock();

    for(int i(0);i<100000000;i++)
       arradd(a, a, b, 4); // a = (a + b) % (1<<128)

    endcpu = clock();
    endt = time(0);

    cout << "Test 1 complete." << endl;
    cout << "CPU time elapsed: " << (endcpu - startcpu) /
CLOCKS_PER_SEC << " seconds" << endl;
    cout << "Wall time elapsed: " << difftime(endt, startt) << "
seconds" << endl;;
    cout << "Final sum: " << hex << uppercase << setfill('0');
    for(int i(3);i>=0;i--)
       cout << setw(8) << a[i] << " ";
    cout << dec << nouppercase << endl;
    cout << endl;

    // Test 2
    cout << "Test 2: 100 million 128-bit additions using vector..." <<
endl;

    startt = time(0);
    startcpu = clock();

    for(int i(0);i<100000000;i++)
       vecadd(&av, &av, &bv, 4); // av = (av + bv) % (1<<128)

    endcpu = clock();
    endt = time(0);

    cout << "Test 2 complete." << endl;
    cout << "CPU time elapsed: " << (endcpu - startcpu) /
CLOCKS_PER_SEC << " seconds" << endl;
    cout << "Wall time elapsed: " << difftime(endt, startt) << "
seconds" << endl;
    cout << "Final sum: " << hex << uppercase << setfill('0');
    for(int i(3);i>=0;i--)
       cout << setw(8) << av.at(i) << " ";
    cout << dec << nouppercase << endl;
    cout << endl;

    // Done.
    return 0;
}

---------------------------------------------------