std::vector vs. array - FIGHT (or: STL vs CSL)

[Arrow]

Interesting. You're sure the .NET framework isn't the factor here(if it JITed the whole thing into MSIL, Microsoft may have a few tricks of their own to make things faster)?

Shouldn't be a factor, since this just standard stuff (no .NET libraries included). The speed is probably from my work machine - P4 3.6GHz with 4GB RAM.

I also did a run with Xilinx tools running in the background, and those results were 21 for the vector vs 20 for the array.

[Durandal]

You're doing 6 dereferences, 6 additions (array offset), and 3 XOR operations. My swap does 4 dereferences, 4 additions, and 3 assignments. In other words, mine is faster, even if it doesn't look as fancy.

You're right, of course. I forgot that we were swapping array values. XOR should be the faster method for non-pointer swaps though.

[Beowulf]

it should be

Code: Select all

for(i=0; i<itr; ++i)
    {
        swap1 = rand()%SIZE;
        swap2 = rand()%SIZE;
        val = aa[swap1];
        aa[swap1] = aa[swap2];
        aa[swap2] = val;
    } 

I hate people who double-indent their loops.

A better swap would be something like this.

Code: Select all

for( i = 0; i < SIZE; i++ ) {
    swap1 = rand() % SIZE;
    swap2 = rand() % SIZE;
    aa[swap1] ^= aa[swap2];
    aa[swap2] ^= aa[swap1];
    aa[swap1] ^= aa[swap2];
}

I don't know if the XOR or XOR-equal operators are overridden in the std::vector class, but if they're not, I'd be willing to bet that the code above for a standard array would spank a vector silly.

Copy-paste job, with the beginning indent not copied. *shrug* shoulda been single indent. Your indent style sucks, because it's harder to find the open brace, when you've seen the close brace. Also, it's apparent you need more C++ experience, otherwise you'd never would have made such a silly mistake, as the comment above.

[Mad]

What would be more interesting is dynamically altering the size of the array / vector and see which one wins. That is the main advantage of a vector anyway; resizing without worring about details like realloc'ing it yourself. It is late tonight, but if no one tackles this by the time I wake up tomorrow morning, I will write up a sample program to test it out. Should be fascinating.

For any significantly-sized array, most of the time spent resizing is going to be in memcpy(). Any overhead from the vector class's management would be insignificant (constant time overhead as opposed to linear time memcopy()). And as we've seen so far, the overhead may mostly be removed by turning optimization on.

And if you're going for speed, you shouldn't be allocating memory during your time-intensive operations anyway. You should guess how much you'll need and preallocate it anyway.

And if you're contemplating using standard arrays for performance instead of a vector (not that it matters as seen here), then you probably know how much memory you're going to need for a static array anyway. (What serious programmer doing serious work is going to roll their own memory management solution and risk introducing unnecessary bugs and memory leaks when the STL is available at essentially no performance cost? Outside of a few rare circumstances, it just doesn't make any sense.)

[Xon]

One major preformance enhancement to either static arrays or vectors is to allocate common memory usage as the default allocation size instead of the built in before you even get into any resizing.

STL::Vector.reserve can set the capacity of the backstore, which can dramatically improve preformace. Intelligently setting the pre-allocated value on a dynamically allocated structure is something any semi-serious developer should know how todo.